A.1 SVRG and SCSG Here we provide the pseudocode for SVRG (Algorithm 2) and SCSG (Algorithm 3) seen in Lei et al. [35]. The idea of SVRG (Algorithm 2) is to reuses past full gradient computations (line 3) to reduce the variance of the current stochastic gradient estimate (line 7) before the parameter update (line 8). Note that N = 1 corresponds to a GD step (i.e., v SVRG achieves linear convergence O(1/T) using the semi-stochastic gradient. The key difference is that SCSG (Algorithm 3) considers a sequence of time-varying batch sizes (Bt and bt) and employs geometric sampling to generate the number of parameter update steps Nt in each iteration (line 6), instead of fixing the batch sizes and the number of updates as done in SVRG. Particularly when finding an -approximate solution (Definition 1) for optimizing smooth non-convex objectives, Lei et al. [35] proves that SCSG is never worse than SVRG in convergence rate and significantly outperforms SVRG when the requiredis small.

When|Nk| = 1,one can easily validate that this condition holds. We use mini-batch gradient descent with batch size of 10. We tune the step-sizes and forgetting factors from the interval(0,1) and find the best empirical performance by setting them to be µk = 0.01andνk = 0.05for every normal agentk. Byzantine agents are designed tosend amodel with very small noisy elements for each dimension from the interval [0,0.1] at each iteration. Figure5andFigure6ashow the mean and range of the averagetrainingloss and classification accuracy of the normal agents in the case of no attack, with 10 random selected Byzantine agents, and with 29 Byzantine agents.

Distributed multi-task learning provides significant advantages in multi-agent networkswithheterogeneous datasources where agents aimtolearndistinctbut correlated models simultaneously. However, distributed algorithms for learning relatedness among tasks arenotresilient inthepresence ofByzantine agents. In this paper, we present an approach for Byzantine resilient distributed multi-task learning. We propose an efficient online weight assignment rule by measuring the accumulated loss using an agent's data and its neighbors' models. A small accumulated loss indicates a large similarity between the two tasks.

Decentralized cooperative multi-agent multi-armed bandits (DeCMA2B) considers how multiple agents collaborate in a decentralized multi-armed bandit setting. Though this problem has been extensively studied in previous work, most existing methods remain susceptible to various adversarial attacks. In this paper, we first study DeCMA2B with adversarial corruption, where an adversary can corrupt reward observations of all agents with a limited corruption budget. We propose a robust algorithm, called DeMABAR, which ensures that each agent's individual regret suffers only an additive term proportional to the corruption budget. Then we consider a more realistic scenario where the adversary can only attack a small number of agents. Our theoretical analysis shows that the DeMABAR algorithm can also almost completely eliminate the influence of adversarial attacks and is inherently robust in the Byzantine setting, where an unknown fraction of the agents can be Byzantine, i.e., may arbitrarily select arms and communicate wrong information. We also conduct numerical experiments to illustrate the robustness and effectiveness of the proposed method.

L-Lipschitz continuous gradient, if there exists a constant L > 0, such that null f (x) f (y)null Lnull x y null, x,y. If f is m-strongly convex and has an L-Lipschitz continuous gradient, then it is obvious that m L. Let λ be the Lagrange multiplier. Using Jensen's inequality, we have r We next prove the convergence of the algorithm with the proposed weight assignment rule. An edge between two agents means they are neighbors. This is to model the realistic scenario in which some of the agents may have less data samples and they may learn slowly than others.

However, distributed algorithms for learning relatedness among tasks are not resilient in the presence of Byzantine agents. In this paper, we present an approach for Byzantine resilient distributed multi-task learning. We propose an efficient online weight assignment rule by measuring the accumulated loss using an agent's data and its neighbors' models. A small accumulated loss indicates a large similarity between the two tasks.

We also characterize the lower and upper bounds of the predictive variance.