DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs
Authors: Chaouki Ben Issaid
Anis Elgabli
Mehdi Bennis
Venue: Accepted by TMLR ()

Abstract: In this paper, we propose to solve a regularized distributionally robust learning problem in the decentralized setting, taking into account the data distribution shift. By adding a Kullback-Liebler regularization function to the robust min-max optimization problem, the learning problem can be reduced to a modified robust minimization problem and solved efficiently. Leveraging the newly formulated optimization problem, we propose a robust version of Decentralized Stochastic Gradient Descent (DSGD), coined Distributionally Robust Decentralized Stochastic Gradient Descent (DR-DSGD). Under some mild assumptions and provided that the regularization parameter is larger than one, we theoretically prove that DR-DSGD achieves a convergence rate of  $\mathcal{O}\left(1/\sqrt{KT} + K/T\right)$, where $K$ is the number of devices and $T$ is the number of iterations. Simulation results show that our proposed algorithm can improve the worst distribution test accuracy by up to $10\%$. Moreover, DR-DSGD is more communication-efficient than DSGD since it requires fewer communication rounds (up to $20$ times less) to achieve the same worst distribution test accuracy target. Furthermore, the conducted experiments reveal that DR-DSGD results in a fairer performance across devices in terms of test accuracy.


Published in Transactions on Machine Learning Research (08/2022)
DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs
Chaouki Ben Issaid
chaouki, Benissaddooouh.
Centre for Wireless Communications University of Oulu, Finland
Anis Elgabli
anis. waa.scllaalloouuu..o
Centre for Wireless Communications
University of Oulu, Finland
Mehdi Bennis
meldi, Bownis
Centre for Wireless Communications
University of Oulu, Finland
Reviewed on OpenReview: /ttps://openneee net/ forum? VcXNAr5Rur
Abstract
In this paper, we propose to solve a regularized distributionally robust learning problem in the decentralized setting, taking into account the data distribution shift. By adding Kullback-Liebler regularization function to the robust min-max optimization problem, the learning problem can be reduced to modified robust minimization problem and solved efficiently. Leveraging the newly formulated optimization problem, propose robust ver- sion of Decentralized Stochastic Gradient Descent (DSGD), coined Distributionally Robust Decentralized Stochastic Gradient Descent (DR-DSGD). Under some mild assumptions and provided that the regularization parameter is larger than one, we theoretically prove that DR-DSGD achieves convergence rate of O (1/VKT+ + K/T). where K is the number of devices and T is the number of iterations. Simulation results show that our proposed algo- rithm can improve the worst distribution test accuracy by up to 10%. Moreover, DR-DSGD more commaicatiion-fficccn than DSGD since requires fewer communication rounds (up to 20 times less) to achieve the same worst distribution test accuracy target. Fur- thermore, the conducted experiments reveal that DR-DSGD results in fairer performance across devices in terms of test accuracy.
1 Introduction
Federated learning (FL) is a learning framework that allows the training of a model across multiple devices under the orchestration of a parameter server (PS). Unlike the traditional way of training ML models, where the individual data of the devices are shared with the PS, FL hides the raw data, so can significantly reduce the communication cost. When combined with a privacy-preservatiee privacy. Training using FedAvg presents several challenges that need to be tackled. It often fails to address the data heterogeneity issue. Though many enhanced variants of federated averaging (FedAvg) (Li et al. 2020b Liang et al., 2019. Karimireddy et al. 2020b a Wang et al. 2020 Mitra et al. 2021 Horváth et al. 2022) were proposed lo solve this issue in the mean risk minimizatiion ion setting, local data distributions might differ greatly from the average distribution. Therefore, a considerable drop in the global model performance on local data seen, suggesting that the mean risk minimization may not be the right objective. Another major issue in FL is fairness. In many cases, the resultant learning models are biased unfair in the sense that they discriminate against certain device groups (Hardt et al. 2016). Finally, FL. relies on the existence
mechanism, it further ensures

---

Published in Transactions on Machine Learning Research (08/2022)
of a PS to collect and distribute model parameters, which is not always feasible or even accessible to devices that are located lar away.
Even though several FL algorithms (Karrouz et al. 2021 Yang et al. 2019 Li et al. 2020a) have been proposed for the distributed learning problem, FeclAvg-style methods MMcMahan et al 2017 Li et al. 2020b; Wang et al.] 2020) remain the state-of-the--rt algorithm. Specifically, FedAvg entails performing one or multiple local iterations at each device before communicating with the PS, which in turn performs periodic averaging. However, because FedAvg is based on the empirical risk minimization (ERM) to solve the distributed learning problem, i.e. FedAvg minimizes the empirical distribution of the local losses, its performance deteriorates when the local data are distributed non-identically across devices. While the ERM formulation assumes that all local data come from the same distribution, local data distributions might siguificantly diverge from the average distribution. As a result, even though the global model has a good average test accuracy, its performance locally drops when the local data are heterogeneous. In fact, increasing the diversity of local data distributions has been shown to reduce the generalization ability of the global model derived by solving the distributed learning problem using FedAvg (Li et. al. 2020e Zhao et al. 2018
While there are many definitions of robustness, the focus of our work is on distributionally robustness, that is, being robust to the distribution shift of the local data distributions. We consider distributionally robust learning perspective by seeking the best solution for the worst-case distribution. Another key focus of this work is to investigate the fairness of the performance across the different devices participating in the learning. Fairness aims to reduce the difference in performance on the local datasets to ensure that the model performance is uniform across the devices participating in the learning process. In the FL context, achieving fair performance among devices is critical challenge. In fact, existing techniques in FL, such as Fed (McMahan et al., 2017) lead to non-uniform performance across the network, especially for large networks, since they favour or hurt the model performance on certain devices. While the average performance is high, these techniques do not ensure a uniform performance across devices.
PS-based learning (star topology) incurs a significant bottleneck in terms of communication latency, scal- ability, bandwidth, and fault tolerance. Decentralized topologies circunvent. these limitations and hence have significantly greater scalability to larger datasets and systems. In fact, while the communication cost increases with the number of devices in the PS-based topology, it is generally constant (in a ring or torus topology), slowly increasing function in the nunber of devices since decentralizing learning only requires on-device computation and local communication with neighboring devices without the need of a PS. Several works investigated the decentralizing learning problem (Yuan et al.] 2016 ZZng & Yin 2018 Wang et al. however, while
2019
Wei & Ozdaglar 2012 Shi et al. 2014 Ben Issaid et al.) 2021 Duchi et al. 2011];
interesting none of these works has considered solving the decentra lized learning problem in a distributionally robust manner.
Summary of Contributions. The main contributions of this paper are summarized as follows
We propose a distributionally robust learning algorithm, dubbed Distributionally Robust Decentralized Stochastic Gradient Descent (DR-DSGD), that solves the learning problem in a de- centralized manner while being robust to data distribution shift. To the best of our knowledge, our framework is the first to solve the regularized distributionally robust optimization problem in a decentralized topology.
Under some mild assumptions and provided that the regularization parameter is larger than one, we prove that DR-DSGD achieves a fast convergence rate of VKT + T
K) where is the number
of devices and T is the number of iterations, shown in Corollary D Note that, unlike existing FL frameworks that rely on the unbiasedness of the stochastic gradients, our analysis is more challenging and different from the traditional analyses for decentralized SGD since it involves biased stochastic gradients stemming from the compositional nature of the reformulated loss function.
We demonstrate the robustness of our approach compared to vanilla decentralized SGD via numerical simulations. It. is shown that. DR-DSGD leads to an improvement of up to 10% in the worst distri-
2

---

Published in Transactions on Machine Learning Research (08/2022)
bution test accuracy while achieving a reduction of up to 20 times less in terms of communication rounds.
Furthermore, we show by simulations that DR-DSGD leads to a fairer performance across devices in terms of test accuracy. In fact, our proposed algorithm reduces the variance of test accuracies across all devices by up to 60% while maintaining the same average accuracy.
Paper Organization. The remainder of this paper is organized as follows. In Section 3 we briefly describe the problem formulation and show the difference between the ERM and distributionally robust optimization (DRO) formulation. Then, we present our proposed framework, DR-DSGD, for solving the decentralized learning problem in distributionally robust manner in Section 4 In Section 5 we prove the convergence of DR-DSGD theoretically under some mild conditions. Section validates the performance of DR-DSGD by simulations and shows the robustness of our proposed approach compared to DSGD, Finally, the paper concludes with some final remarks in Scction 7 The details of the proofs of our results are deferred to the appendices.
2 Related Works
Robust. Federated Learning. Recent robust FL. algorithms (Mohri et al., 2019: Reisizadeh et al. 2020;
Deng et al. 2020 Hamer et al. 2020) have been proposed for the learning problem in the PS- based topology. Instead of minimizing the loss with respect to the average distribution among the data distributions from local clients, the authors in (Mohri et al. 2019) proposed agnostic federated learning (AFL), which optimizes the global model for target distribution formed by any mixture of the devices' distributions. Specifically, AFL casts the FL problem into min-max optimization problem and finds the worst loss over all possible convex combinations of the devices' distributions. Reisizadeh et al. (2020) proposed FedRobust, a variant of local stochastic gradient descent ascent (SGDA), aiming to learn a model for the worst-case affine shift by assuming that a device's data distribution an affine transformation of a global one. However, FedRobust requires each client to have enough data to estimate the local worst-case shift; otherwise, the global model performance on the worst distribution deteriorates. The authors in (Deng et al.) 2020) proposed a distribu- tionally robust federated averaging (DRFA) algorithm with reduced communication. Instead of using the ERM formulation, the authors adopt DRO objective by formulating distributed learning problem to minimize distributionally robust empirical loss, while periodically averaging the local models as done in FedAvg (McMahan et al. 2017). Using the Bregman Divergence as the loss function, the authors in (Hamer ct al., 2020) proposed FedBoost, a commuicattion-effiieett FL algorithm based on learning the optimal mix- ture weights on an ensemble of pre-trained models by communicating only a subset of the models to any device. The work of (Pillutia et al., 2019)) tackles the problem of robustness to corrupted updates by applying robust aggregation based the geometric median. Robustness to data and model poisoning attacks also investigated by (Li et al. 2021b DRO has been applied in multi-regional power systems to improve reliability by considering the uncertainty of wind power distributions and constructing a multi-objectivg function that maintains a trade-off between the operational cost and risk (Li & Yang. 2020 Hu et al.) 2021) However, none of these works provides any convergence guarantecs. Furthermore, our analysis is different from these works since it involves biased stochastic gradients.
Fairness in Federated Learning. Recently, there has been a growing interest in developing FL algorithms that guarantee fairness across devices (Mohri al. 2019 Li et al. 2020d 2021ah. Inspired by works in fair resource allocation for wircless networks, the authors in (Li ct al. 2020d) proposed q-FFL, FL algorithm that addresses fairness issues by aninimizing an average reweighted loss parameterized by q- The proposed algorithm assigns larger weights to devices with higher losses to achieve uniform performance across devices. Tilted empirical risk minimization (TERM), proposed in (Li ct al. 2021a), has a similar goal as q-FFL, i.c. to achieve fairer accuracy distributions among devices while ensuring similar average performance.
Decentralized Learning. Decentralized optimization finds applications in various arcas including wircless sensor networks (Mihaylov et al. 2009 Avei et al.) 2018 Soret et al. 2021),, networked multi-agent systems [Tnalan et al. 2002 Ren et al.
2007
Johansson
2008 well as the area of smart grid implementations
3

---

Published in Transactions on Machine Learning Research (08/2022)
Kekktoos & Giannakis 2012). Several popular algorithms based gradient descent Yuuan al. 2016 Zeng & Yin 2018 Wang et. al. 2019), alternating direction method of multipliers (ADMM) (Wei & Ozdaglar 2012 Shi et al. 2014 Ben Issaid et al. (2221, or dual averaging (Duchi et al. 2011 have been proposed to tackle the decentralized learning problem.
3
Notations & Problem Formulation
3.1 Notations
Throughout the whole paper, we use bold font for vectors and matrices. The notation V stands for the gradient of the function f. and E[]] denotes the expectation operator. The symbols I Il, and || || denote the f2-norm of vector, and the Frobenius norm of matrix, respectively. For positive integer number The set of veclors of size K with all entries being positive is denoted by I& The notations 0 and 1 denote vector with all entries equal to 2ero, or one, respectively (its size is to be understood from the context). Furthermore, we define the matrices: I the identity matrix and J = & 11 For a square matrix A, Tr(A) is the trace A, i.. the sum of elements on the main diagonal. Finally, for the limiting behavior of functions, f (g) means that f bounded above up to constant factor by g. asymptotically.
write [n] A
3.2 Problem Formulation
We consider connected network consisting of set of K devices. Each device i E [K] has its data distribution D; supported on domain E. : (X, D1). The connectivity among devices is represented as an undirected connected communication graph g having the set C V V of edges, as illustrated in Fig. [ The set of neighbors of device i is defined as N (il(i,)) E} whose cardinality is [Wil d3. Note that (i,j) E E if and only if devices i and j are connected by communication link; in other words, these devices can exchange information directly. All devices collaborate to solve the optimization problem given by
(()) where ʃi(O): [
(1)
DERA
where & : (24, 9i) denotes the set of features and labels of device i. The function ((O), Ei) is the cost of predicting ys from F;, where θ denotes the model paramcters, c.g., the weights/biase of a neural network. Here, n, denotes the number of training examples drawn from D; and = -EK ny is the total number of examples.
Without loss generality, we assume in the remainder that all devices have the same number of samples, and therefore n:/n 1/K, Vi [K]. In this case, problem 1 writes as
1 K
min @ER
Σ (().
(2)
K
One way solve [1] a decentralized way use vanilla decentralized SGD (DSGD) (Yuan el al. 2016). As shown Algorithm each device in DSGD performs two steps: (i) a local stochastic gradient
Algorithm VANILLA DECENTRALIZED SGD (DSGD) for in O.....77 - do in parallel for all devices E [K]
2: Sample mini-batch of size { compute gradient (0)) := 1 E VE(O,))
0 + : 0 1g (0.)
4: Send 0 1 to neighbors
0 = W +
6: end for

---

Published in Transactions on Machine Learning Research (08/2022)
D2
D
D
Da
Dg
Figure 1: Musttaaiio of graph topology (K 8) and the interactions between the devices (D1 D2).
update (Line 3) using the learning rate and (ii) consensus operation in which it averages its model with its neighbors' models (Lines 4-5) using the weights of the connectivity (mixing) matrix of the network W = [W,) E Rx The mixing matrix W is often assumed to be a symmetric (W WT) and doubly ==
stochastic (W1 1 = 11") matrix, such that Waz [0, 1], and if (i.j) & &, then Wi = 0. Assuming
W to be symmetric and doubly stochastic is crucial to ensure that the devices achieve consensus in terms of converging to the same stationary point.
While formulating problem
2 we assume that the target distribution is given by
D K DD. D
However, the hetcrogeneity of local data owned by the devices involved in the learning presents a significant challenge in the FL. setting. In fact, models resulting from solving and are vulnerable to adversarial attacks (Bhagoji et al. 2019). This is mainly due to the fact that the target distribution may be significantly different from D in practice.
(2) lack robust.ness to distribution shifts
4 Proposed Solution
Our aim is to learn a global model + from helerogeneous data coming from these possibly non-identical data distributions of the devices in decentralized manner. To account for heterogeneous data distribution across devices, the authors in (Mohri et al. 2019 proposed agnostic FL, where the target distribution is given by
K Dx = Σ A,D
(4)
where the weighting vector À belongs to the K-dimensional simplex, A {A (AI,..., Ax) E R ===A1 Note that this target distribution is more general than D and il reduces to D when X; L/K.vie(A]
Unlike D which gives equal weight to all distributions K devices' dist distributions, where the unknown mixture weight À is learned during training and not known priori. In this case, the distributionally robust empirical loss problem is given by the following min-max optimization problem
K during training, Dx is rather a mixture of
min max GcRd
(5)
5

---

Published in Transactions on Machine Learning Research (08/2022)
Algorithm DISTRIBUTTIOAAIYY ROBUST DECENTRALIZED SGD (DR-DSGD)
1: for in ...... T do in parallel for all devices E [K] Sample mini-batchh of size {5}})=1> compute the gradient g::))) B Ei=1 V and
h(0%: p)) == exp ( Σド= f ())11)
0, 0++ = 0: - h.(0)p)) (0:)
3:
Send 0 2/2 to neighbors
0 Σド= W ++
6: end for
Although several distributed algorithms Mohri et al. 2019 Reisizadeh et al. 2020 Deng et al 2020 Hamer
ct al. 2020) have been proposed for (5) solving it in decentralized fashion (in the absence of PS) is a
challenging task. Interestingly, when introducing a regularization term in 5 and by appropriately choosing
the regularization function, the min-max optimization problem can be reduced to a robust minimization problem that can be solved in decentralized manner, as shown later on. Specifically, the regularized version of problem (5) can be written as follows
(6) where μ > 0 is a regularization parameter, and ((x, I)K is a divergence mcasure between {Ar) and the uniform probability that assigns the same weight 1/K to every device's distribution. The function 6 can be seen as a penalty that ensures that the weight D not far away from 1/K. Note that μ -> gives the distributionally robust problem (5) while when μ + oo, we recover the standard empirical risk minimization problem
min max x.((9)) - 10, GER XEA
1=1
Although different choices of the ø-divergence can be considered in 66, the robust optimization community has been particularly interested in the Kullback Leibler (KL) divergence owing to its simplified formulation Esfahani & Kuhn 2018 In fact, when consider the KL divergence, ie. o(A, 60A,1/K) E X log(A,K), then by exactly maximizing over À E A, the min-max problem, given in is shown to be equivalent to Lemma 1)
(Huang et al.
2021
K Σ exp (1(O))))
min log @cr
(7)
K
=11
Since log(-) is monotonically increasing function, then instead of solving 7 we simply solve the following problem
min F(O)= eER
A K
Σ ((()),
where F((0)= exp (fi(O)/k),
Remark Note that problem O equivalent problem (5) as p The prorimity of the solutions
to 5 in the conver is discussed in Appendür A. In the remainder of this work, we focus
solving the regulorized distributional robust optimization problem Mohri et al,, 2019: Deng et ol. 2020 given in
Although any decentralized learning algorithm can be used to solve 8 the focus of this paper is to pro- pose a distributionally robust implementation DSGD. Our framework, coined Distributionally Robust Decentralized SGD (DR-DSGD), follows similar steps as DSGD with the main difference in the local update step
K
0
Wij 0
" hh ((00:)))0000)) #
(9)

---

Published in Transactions on Machine Learning Research (08/2022)
where p() exp B E (00 and B is the mini-batch size 16) Introducing the term (10%))/ in line 3 of Algorithm 2 makes the algorithm more robust the heterogeneous setting and ensures fairness across devices, will be shown in the numerical simulations section.
5 Convergence Analysis
This section provides a theoretical analysis of the convergence rate of the DR-DSGD algorithm. Before stating the main results of the paper, we make the following assumptions. Assumption 1. (Smoothness) There exist constants LF and L1, such that V01, 02 R we have
[VF((1)) VF(02)) - Lr|101 - 0211.
(10)
(0,) g: (0a))ll - 01|00 0211-
(11)
Assumption 2. (Gradient Boundedness) The gradient of fi(+) is bounded, i.c. there exits G1 such that v0 R we have
Vf < G1.
(12)
Assumption 3. (Variance Boundedness) The variances of stochastic gradient 9i(+) and the function 4(,E)) are bounded, i.c. there exit positive scalars and such that 40 E Idd we have
E [1((, [1 < oo
(13)
E (0) (s(00) S oz.
(14)
Assumption 4. (Function Boundedncss) The function F(-) is lower bounded, i.. Fins = inf F(0)
BeRd
such that Fin oo and the functions ((:,.)) are bounded, ie. there exists M > such that v0 Rdd we have
E [|8((8, &.)1 < M.
(15)
Assumption 5. (Spectral Norm) The spectral norm, defined as p = |[E W] [|, is assumed be less than 1.
Assumptions 1-5 are key assumptions that are often used in the context of distributed and compositional optimization (Wang et al.) 2016; 2017 Li et al.) 2020e Huang et al. 2021). Note that (15) can be fulfilled by imposing loss clipping Xu et al. 2006 Wu & Liu 2007: Yang et al. 2010 to most commonly-used loss functions. Furthermore, although the categorical cross-entropy function is not bounded upwards, it will only take on large values if the predictions are wrong. fact, under some mild assumptions, the categorical cross- entropy will be around the entropy of M-class uniform distribution, which is log(M) (refer to Appendix A.1 for more in-depth discussion). Considering relatively moderate number of classes, e.g,, M 100, we get log(M) < 5. Thus, the cross-entropy will generally be relatively small in practice, and the assumption will hold in practice.
Remark 2. It is worth mentioning that since the erponential function is convez, and non-decreasig func- lăon, then (exp(J(())) is conver when ( is convex. In this case, the convergence of the proposed method follows directly from eristing results in the literature (Yuan et al. 2016).
In the remainder of this section, we focus on the non-convex setting and we start by introducing the following matrices
0' (oi....,o 0%]
(16)
V (F)) ...., (Ok)
(17)
U' 1 _
(18)

---

Published in Transactions on Machine Learning Research (08/2022)
Remark 3. In the non-conver case, the convergence analysis is more challenging than in the case of DSGD. In fact, due to the compositional nature of the local loss functions, the stochastic gradients are biased, i.e.
E Txx (e(O), ((()) + exp (f(0))/)
(19)
To proceed with the analysis, we start by writing the matrix form of the update rule (9 as
0 (0' 1 U)) W.
(20)
Multiplying both sides of the update rule (20 by 1/K, we get
0+ 0³ 1'
(21)
where 0 is the averaged iterate across devices defined l K E 0%. Now, we in position to introduce first Lemma. Lemma 1. For any matriz A Bd we have
| J) [b2] S A'
(22)
Proof. The details of the proof can be found in Appendix A.4
The following lemmn provides some of the inequalities that we need for the proof of the main result.
Lemma 2. From Assumplion 4, we have that
(a) There erists constant L2(1) such that Vy1, y22 V, we have
expe (y1) exp (y2) L2(1))y y2l:
(23)
where y a (v E(0, 61/1 such that A E Rdd is the range of functions {E(0, 6///).
(b) There erists constant G2(p) such that 4O E Rd, we have
(10x)((((0&)//m111 s G2(u).
(24)
(c) There erists consland (p)) such that vo Rdd, we have
E [xxp(x(( &.)p) (xpp(/))))(((((0/))))))))))))))) s (aa(11)2
(25)
Proof. The details of the proof can be found in Appendix A.5
Using Lemmas and we can now state Lemma which gives an upper bound on the discrepancies among the local models.
(P) Lemma 3. Let y satisfy hh < 4G, Provided that all local models are initiated at the same point, the discrepancies among the local models (I-) can be upper bounded by
27 PG² pC +
+) GB1
E 0 (I-
(26)
KT
- -1-1-7 7m 2
16n² PL3 G2
where o, = max 02 (p)) G₁ = max (mxx(G,,G,()), L, = max(LFF L,, Lz(n)}, and 7
p=11-pp)
Proof. The proof is deferred Appendix A.6 In a nutshell, the proof uses the update rule of DR-DSGD,
given in 20 the special property of the mixing matrix, and Lemma 1
8

---

Published in Transactions on Machine Learning Research (08/2022)
Next, present the main theorem that states the convergence of our proposed algorithm.
Theorem 1. Let yi sotisfy nlu < min ( 8GuvD 1 (} and provided that all local models are initiated at the
point, then the averaged gradient norm is upper bounded as follows
E [[I 2(F(0') - Finf)
2G + v²)
16pm L.G. + +1)18880212 +
+1++
n/T
1
31 vD)
(27)
Proof. The proof of Theorem
1 is detailed in Appendix A.7
The first term of the right-hand side of 27 is neither affected by the graph parameters nor by the regular- ization parameter and it exhibits a linear speedup in T. This term exists also in the convergence analysis of DSGD (Wang et al.) 2019 Lian et al.) 2017). The graph topology affects the third term via the value of the spectral norm p. In fact, a smaller value of makes the third term smaller. Finally, the regularization parameter μ has an impact on both the second and third terms. weakness of the derived bound is that as μ gets smaller, both the second and third terms grow larger. In the limit case, when - 0, both terms grow to infinity. In the next corollary, we limit ourselves the case when μ and show that under this setting DR-DSGD is guaranteed to converge.
Remark 4. Our analysis is still valid in the case where the miring matris changes at every ileration. Similar theoretical guorantees hold provided that the matrices {W')T Jt=1 are independent and identically distributed and their spectral norm p² < 1.
When μ 2 1, it can be seen from the proof of Lemma 2 that can find constants, L2, G2, and 03, that do not depend on In this case, 27 can be written as
E [IF 2(F Fong)
+ (1) G2]
+
1/T
B
3(1 vp)²
(28)
Furthermore, if the learning rate n and the mini-batch size B are chosen properly, obtain the following corollary. Corollary 1. If a 2 1 and if choose 7 2L+VT/K and B = VTT, then we have
1 E = T
K VKT T
(29)
We show empirically in the next section that considering a regularization parameter such that μ 2 still leads to significant gains in terms of the worst distribution test accuracy and improves fairness across devices compared to DSGD.
6 Experiments
In this section, we validate our theoretical results and show the commuicationn-ciiiinnnng robustness and fairness of our proposed approach, DR-DSGD, compared non-robust counterpart. DSGD.
6.1 Simulation Settings
For our experiments, we consider the image classification task using two main datasets: FASHION MNIST (Xiao et al. (017)) and CIFARI0 (Krizhevsky et al., 2009). We implement DR-DSGD and DSGD algorithms using PoTorc. For FASHION MNIST, we use an MLP model with ReLU activations having two hidden layers with 128 and 64 neurons, respectively. For the CIFAR10 dataset, we CNN model composed of
9

---

Published in Transactions on Machine Learning Research (08/2022)
9.14
DSGD
0.12
DR-DSGO
0.30
0.7
0.5
0.03
Wove Deerocti
0.09
0.5
DSGD DR-0SGD
DSGD
0.04
DR DR-DSGD
0.02
100
175
23
50
100
125
150
175
25
500
320
127
150
175
(a)
(c)
Figure 2: Performance comparison between DR-DSGD and DSGD in terms of: (a) average test accuracy, (b) worst test accuracy, and (c) STDEV of test accuracy for FASIIION MNIST dataset.
0.1
0.10
DSGD
0.2
DR-DSGD
Accosee
0.67
0:3
0.60
DSGD DR-DSGD
DSGD DR-DSGD
0.06
0.3
0
30
75
108
150
375
200
25
50
120
125
120
375
200
50
100
325
175
202
Nomber Commursation Rounds
Numberd of Comn municatiioonn Rou
(a)
(b)
(c)
Figure Performance comparison between DR-DSGD and DSGD terms of: (a) average test accuracy, (b) worst test accuracy, and (c) STDEV of test accuracy for CIFAR10 dataset.
three convolutional layers followed by two fully connected layers, each having 500 neurons. For each dataset, distribute the data across the K devices in pathological non-IID way, as in (McMahan et al. (017); to mimic an actual decentralized learning setup. More specifically, first order the samples according to the labels and divide data into shards of equal sizes. Finally, we assign each device the same number of chunks. This will ensure a pathologica non-IID partitioning of the data, as most devices will only have access to certain classes and not all of them. Unless explicitly stated, we choose the learning rate r KK/T and the mini-batch size B = KT.
For the graph generation, we generate randomly a network consisting of K devices with a connectivity ratio p using the networkx package (Hagberg et al. 2008 The parameter p measures the sparsity of the graph. While smaller values p lead sparser graph, the generated graph becomes denser as p approaches We use the Metropolis weights construct the mixing matrix W as follow
1/ (1+ max ddi,,,)), We {
(j. e E, (j. i) & and ii, i
EIEN, Wa.,
if
Unless otherwise stated, the graphs used in our experiments are of the Erdös-Rényi type.
6.2 Robustness & Conmunication-Effiicee
In this section, we consider K 10 devices and μ = 6. For FASHION MNIST, we consider value of 0.3 while we take p 0.5 for CIFAR10. For each experiment, we report both the average test accuracy, the worst distribution test accuracy, and their corresponding one standard enror shaded area based on five runs. The worst distribution test accuracy is defined as the worst of all test accuracics. The performance comparison between DR-DSGD and DSGD for FASHION MNIST and CIFAR10 dataset is reported in Figs. and respectively. Both experiments show that while DR-DSGD achieves almost the same average test
10

---

Published in Transactions on Machine Learning Research (08/2022)
3.0
DR DR_DSGD
DSGD
DSGD
3.0
Devices
2.0
Devices
2.5
1.5
2.0
1.5
1.0
0.5
0.0
0.0
0.4
0.3
0.7
0.8
0.9
0.3
0.4
0.5
0.6
0.7
Worst Test Accuracy
Worst Test Accuracy
(a)
(b)
Figure 4: Performance comparison between DR-DSGD and DSGD in terms of worst test accuracy distribu-
tion for: (a) FASHION MNIST and (b) CIFAR10 datasets.
accuracy as DSGD, it significantly outperforms DSGD in terms of the worst distribution test accuracy. For the gap between both algorithms, the improvement, in terms of the worst distribution test accuracy, is of the order of 7% for FASHION MNIST and 10% for CIFAR10 datasets, respectively. This is mainly due to the fact that while the FRM objective sacrifices the worst-case performance for the average one, DRO aims lower the variance while maintaining good average performance across the different devices. Not only our proposed algorithm achieves better performance than DSGD, but it is also more communication-effiiinn In fact, for the same metric requirement, DR-DSGD requires fewer communication rounds than DSGD. Since our approach exponentially increases the weight of high training loss devices, it converges much faster than DSGD. For instance, in the experiment using the FASHION MNIST dataset, DR-DSGD requires 10x fewer iterations than DSGD to achieve 70% worst distribution test accuracy. Finally, each experiment, we plot the standard deviation (STDEV) of the different devices' test accuracies for both algorithms. We can see from both Figs. [(c] and 3(c) that DR-DSGD has a smaller STDEV compared to DSGD, which reflects that DR-DSGD promotes fairness among the devices.
6.3
Fairness
From this section on, consider K 25. To investigate the fairness of the performance across the devices, we run the experiments on FASHION MNIST and CIFAR10 datasets reporting the final test accuracy on each device in the case when = 9. In Figs. ((a) and 4(b) we plot the worst test accuracy distribution across devices. We note that DR-DSGD results in a more concentrated distribution in both experiments, hence fairer test accuracy distribution with lower variance. For instance, DR-DSGD reduces the variance of accuracies across all devices by 60% on average for the FASHION MNIST experiment while koeping almost the same average accuracy.
6.4 Tradeoff Between Fairness & Average Test Accuracy
In this section, show how a controls the trade-off between fairness and average test accuracy. To this end, we report, in Table [ the average, and worst 10% test accuracy, as well as the STDEV based on five runs for 17=300 and for different values of for both datasets. As expected, higher values of give more weight to the regularization term; hence driving the values of X, closer to the average weight 1/K. Therefore, as p increases, the average test accuracy increases but the worst (10%) test accuracy decreases. Conversoly, the worst test accuracy increases as the value of μ decreases at the cost of drop in the average test accuracy. Furthermore, the STDEV decreases for smaller values of l ensuring fairer performance across devices.
11

---

Published in Transactions on Machine Learning Research (08/2022)
Table 1; Statistics of the accuracy distribution for different values of μ.
Average
Worst 10%
STDEV
Dataset
(%)
(%)
71.5 1.3
49.1 2.4
11.4 0.3
FMNIST
72.3 + 1.1
48.8 3
11.8 + 1.5
1 73.4 1 2.4
44.5 4: 4.4
13.4 +: 2.1
f = Ja 59.83 1.6
57.2 1 2.4
50.9 1.5
10.3 1 0.6
CIFARIO
48.9 + 1.8
10.9 + 0.4
1A 1.4
44.9 4: 1.9
11.2 + 1.3
DSGD DR-0SGD
DSGD
50
Worst Test Accursiy
Word Text Actunry
50-
20
0.3
0.45 Connectivity ratio 1
0.6
0.3
0.45
0.6
Connectivity ratio
(b)
Figure 5: Performance comparison between DR-DSGD and DSGD in terms of worst test accuracy distribu- tion for different values of p for: (a) FASHION MNIST and (b) CIFAR10 datasets.
6.5 Impact of Graph Topology
In this section, start by inspecting the effect of the graph sparsity the performance of DR-DSGD and DSGD in terms of the worst distribution test accuracy by considering different conncetivity ratios E (0.3,0. 0.45,,000.0 0.6] and for = 6. The results are reported in Fig 5 for both datasets for μ 6. We can see that as the graph becomes denser, iee as increases, the performance of both algorithms improves in terms of the worst test distribution. Nonetheless, it clear that DR-DSGD outperforms DSGD for three different values of p for both datasets. Next, we explore the performance both algorithms on several other types of graph-types, specifically geometric (Fig. [(a]), ring (Fig. 6(b) and grid graphs (Fig. [(c).. The first row represents the graph topology, while the second represents the worst distribution test accuracy function of the number of communication rounds for FASHION MNIST. We can see that DR-DSGD outperforms DSGD for the three graphs considered in Fig. G by achieving higher worst distribution test accuracy. Furthermore, we note that both algorithms converge faster as the graph becomes denser. For instance, both algorithms require fewer communication rounds when the graph topology geometric (Fig. 6(a) compared to the ring graph (Fig. 6(b))
6.6 Limitations
In this section, we highlight some of the limitations our approach, while outlining several potential direc- tions for future work.
Solving the unregularized distributionally robust problem: Instcad of solving ( we pro- pose DR-DSGD to solve its regularized form given in ( This mainly motivated by the fact that solving the min-max problem in in decentralized fashion is challenging task. A weakness of
12

---

Published in Transactions on Machine Learning Research (08/2022)
(a)
(b)
(c)
Woyk Dhanngaten Tal MaLinee
0.4
Werre Drarrautio
0.-
Wenet Desroaato
DSGD DR-DSGO
DSGD
DR-DSGD
30
75
300
123
150
375
202
50
75
225
1.0
200
50
100
125
152
375
200
Communtcarrr
Aumber of Comme corrinniaaiionn Kou
Namber
Figure 6: Performance comparison between DR-DSGD and DSGD in terms of worst test accuracy for: (a) geometric graph, (b) ring graph, and (c) grid graph for FASHION MNIST dataset.
the convergence analysis is that the derived convergence rate is obtained only for values of i larger than one. For μ 0, the bound, derived in Theorem ! grows infinity.
Relaxing some of the assumptions: As pointed out in (Khaled et al. 2020), the bounded gradient assumption has been criticised in the FL literature. Adopting more reasonable assumption is left for future work.
7 Conclusion
This paper proposes distributionally robust decentralized algorithm, DR-DSGD, that builds upon the decentralized stochastic gradient descent (DSGD) algorithm. The proposed framework is the first to solve the distributionally robust lcarning problem over graphs. Simulation results indicate that our proposed algorithm more robust across heterogeneous data distributions while being more communication-eficii than non-robust counterpart, DSGD. Furthermore, the proposed approach ensures fairer performance across all devices compared to DSGD.
Broader Impact Statement
This paper proposes distributionalll--oouer decentralized learning algorithm. Our approach minimizes the maximum loss among the worst-case distributions across devices' data. As result, even if the data distribu- tion across devices is significantly heterogencous, DR-DSGD guarantees notion of fairness across devices. More specifically, the proposed algorithm ensures that the trained model has almost similar performance for all devices, rather than just performing well on a few of them while doing poorly on other devices.
Acknowledgments
This work was supported in part by the Academy of Finland 6G Flagship under grant No. 318927, in part by project SMARTER, part by projects EU-ICT IntellloT under grant No. 957218, EUCHISTERA LdarningEdge, CONNECT, Infotech-NOOR, and NEGEIN. We would like also to thank the anonymous reviewers for their insightful comments that led to improving the manuscript.
13

---

Published in Transactions on Machine Learning Research (08/2022)
References
Onur Avei, Osama Abdeljaber, Serkan Kiranyaz, Mohammed Hussein, and Daniel J Inman. Wireless and real-time structural damage detection: A novel decentralized method for wireless sensor networks. Journal of Sound and Vibralion, 424:158 172, 2018.
Chaouki Ben Issaid, Anis Elgabli, Jihong Park, Mehdi Bennis, and Mérouane Debbah. Communication efficient decentralized learning over bipartite graphs. IEEE Transactions Wireless Communications,, pp. 1-1, 2021. doi: 0T010///TWC..2211122688688
Arjum Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. In International Conference on Machine Learning, pp. 634 643. PMLR, 2019.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated aver- aging. In Advonces in Neural Information Processing Systems, volume 33, pp. 15111-15122, 2020.
John Duchi, Peter Glymn, and Hongscok Namkoong. Statistics of robust optimization: A generalized empir- ical likelihood approach. arXie preprial arXiv:1610.03422 2016.
John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Transactions on Automatic control, 57(3))592 606, 2011,
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115 166, 2018
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference, pp. 11 - 15, Pasadena, CA USA, 2008.
Jenny Hamer, Mehryar Mohri, and Ananda Theertha Suresh. FedBoost: A communication-elliien algo- rithm for federated learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 3973-3983, 2020.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advonces in neural information processing systems, 29, 2016.
Samuel Horváth, Maziar Sanjabi, Lin Xiao, Peter Richtárik, and Michael Rabbat. Fedshuffle: Recipes for better use of local work in federated learning, arXiv preprint arXiv:2204.13169 2022.
Fan Hu, Wen Xiong, Renbo Wu, Yongzhao Lao, Yunlong Li, Zhigang Li, and Jinyu Yu. Decentralized distributionally robust dispatch of multi-regional power systems considering the correlated variable wind power In 2021 Power System and Green Energy Conference (PSGEC), pp. 491 496, 2021.
Feihu Huang, Junyi Li, and Heng Huang. Compositional federated learning: Applications in distributionally robust averaging and meta learning. arXie preprint orXiv:2106. 11661 2021.
Gokhan Inalhan, Dusan M Stipanovic, and Claire J Tomlin. Decentralized optimization, with application to multiple aircraft. coordination. In Proceedings of the 41sl IEEE Conference on Decision and Coutrol, 2002., volume 1, pp. 1147 1155. IEEE, 2002.
Björn Johansson. On distributed optimization in networked systems. PhD thesis, KTH, 2008.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and Trendoo in Machine Learning, 14(1 2):1 210, 2021.
Sai Pranccth Karimireddy, Martin Jaggi, Satyen Kale, Mchryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mine: Mimicking centralized stochastic algorithms in federated learning. Xiviv preprint or Xic:2008. 03606, 2020a.
14

---

Published in Transactions on Machine Learning Research (08/2022)
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132 5143. PMLR, 2020b.
Vassilis Kekatos and Georgios B Giannakis. Distributed robust power system state estimation. IEEF Transactions on Power Systems, 28(2):6617-1266, 2012.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogencous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519-4529 PMLR, 2020.
Alex Krizhevsky, GeofTrey Hinton, el al. Learning multiple layers of features from tiny images. Technical report, 2009.
Peng Li and Ming Yang. Decentralized distributionally robust coordinated dispatch of multi-area power systems considering voltage security. In 2020 IEEE/IAS Industrial and Commercial Power System Asia (I CPS Asia), pp. 863 868, 2020.
Tian Li, Anit Kumar Sahu, Amect Talwalkar, and Virginia Smith. Federated learning: Challenges, mothods, and future directions. IEEE Signal Processing Magazine, (7(3):50-60 60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-44 450, 2020b.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Tn Proceedings of Machine Learning ond Systems, volume 2, pp. 429 450, 2020c.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations (ICLR), 2020d.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference on Learning Representations (ICLR), 2021a.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357 6368. PMLR, 2021b.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang, On the convergence of FedAvg on non-lID data. In International Conference on Learning Representations, 2020e.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Xianfeng Liang, Shuhong Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reducod local sgd with lower communication complexity. arXiv preprinl 1912.
2019.
Brendan McMahan, Eider Moore, Danicl Ramage, Seth Hampson, and Blaise Aguera y Arcas. commmmication-ffiiiee.. learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282, 2017.
Mihail Mihaylov, Karl Tuyls, and Ann Nowé. Decentralized learning in wireless sensor networks. In Inter- national Workshop on Adaptive and Learning Agents, pp. 60-73. Springer, 2009.
Aritra Mitra, Rayana Jaafar, George J. Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. In Advances in Newral Information Processing Systems, volume 34, pp. 14606-14611 2021.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 4615-4625 2019.
15

---

Published in Transactions on Machine Learning Research (08/2022)
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with -divergences. Advances in neural information processing systems, 29, 2016.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprint ar Xix: 19445, 2019.
Qi Qian, Shenghuo Zhu, Jiasheng Tang, Rong Jin, Baigui Sun, and Hao Li. Robust optimization over multiple domains. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 4739 4746, 2019.
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. In Advances in Neural Information Processing Systems, volume 33, pp. 21554 21565, 2020.
Wei Ren, Randal W Beard, and Ella M Atkins. Information consensus in multivchicle cooperative control.
IEEE Control systems magazine, 27(2):71-82, 2007.
Wei Shi, Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin. On the linear convergence of the ADMM decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(():1750 1761-1776,11100 2014.
Beatriz Soret, Lam Duc Nguyen, Jan Seeger, Arne Bröring, Chaouki Ben Issaid, Sumudu Samarakoon, Anis El Gabli, Vivek Kulkarni, Mchdi Bennis, and Petar Popovski. Learning, computing, and trustworthiness in intelligent IoT environments: Performance-energy tradeoffs. IEEE Transactions on Green Communi- cations and Networking, 2021.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya kar. MATCHA: Speeding up decentralized sgd via matching docomposition sampling. arXiv preprint arXiv:1905. 105.0490,,,,43,, 2019.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogencous federated optimization. Advances in neural information processing systems, 33: 7611 1621- 2020.
Mengdi Wang, Ji Liu, and Ethan Fang. Accelerating stochastic composition optimization. Advances in Newral Information Processing Systems, 29, 2016.
Mengdi Wang, Ethan Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-var value functions. Mathematical Programming, 161(1):419-444 449, 2017.
Ermin Wei and Asuman Ozdaglar. Distributed alternating direction method of multipliers. In 2012 IEEE 51st IEEE Conference Decision and Control (CDC), pp. 5450. IEEE, 2012.
Yichao Wu and Yufeng Liu. Robust truncated hinge loss support vector machines. Journal of the American Statistical Association, 102(479):974-983) 2007.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.0774 2017.
Linli Xu, Koby Crammer, Dale Schuurmans, et al. Robust support vector machine training via convex outlier ablation. In AAAI, volume 6, pp. 536 542, 2006.
Min Yang, Linli Xu, Martha White, Dale Schurrmans, and Yao-liang Yu. Relaxed clipping: A global training method for robust regression and classification. Advances in neural information processing systems, 23, 2010.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Oplimization, 26(3):1835-1885 1854, 2016.
16

---

Published in Transactions on Machine Learning Research (08/2022)
Jinshan Zeng and Wotao Yin. On nonconvex decentralized gradient descent. IEEE Transactions signal processing, 66(11):2834-28)) 2018.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-llD data. anXiv preprint Stw:1880000588 2018.
A Appendix
A.1 Worst-case Bound on Categorical Cross-entrops
Let's first examine the behavior of a randomly initialized network. With random weights, the many units/ /layers will usually compound to result in the network outputting approximately uniform predictions. In a classification problem with .M classes, we will get probabilities of around 1/M for each category. In fact, the cross-entropy for a single data point defined as
CE = Σ Um log(Um).
(30)
where y are the true probabilities (labels), f are the predictions. With hard labels (i.c. one-hot encoded), only single ym is 1, and all others are 0. Thus, CE reduces to - log(mm), where m is now the correct class. With a randomly initialized network, we have 2m ~ 1/M, therefore, we get - lololl/////// (og( ) = log(M)). Since the
training objective usually to reduce cross-entropy, we can think of log(M) as a worst-case bound.
A.2 Proximity of the Solutions of 66 to
In this appondix, we discuss briefly the Proximity the solutions of (6) to (5) in the convex case. According (Qian et al. 2019)) problem (6) can be re-writien using the duality theory as
min max ( GER AEA
(31)
1=1
s.t. 10,1
(32)
where every μ4 we associate value. From Namkoong & Duchi 2016 Duchi al. 2016 for convex loss functions, have that
1 K Σ (()) + [V..) op, (K (K-
Σ
(e(())
(33)
AEPAN 1=1
where ((0)= = (G)) lx (O)J
R is the vector of losses, Po the empirical probability distribution,
and the ambiguity set Pa, defined as Pp, = {) E R ΣK d 1, X 2 0, Φ(A, 1/K) < <.). Note that problem equivalent
6 when O. Thus, we can link the objective of the problem (6) to as
(f)(() min max GER XEP
min max
xf((()) V=Varp,
(34)
GER XEPo,K
A.3 Basic identities and inequalities
We start by summarizing the main identities and inequalities used in the proof. Let {a, be a sequence of vectors in Rdd by and by two scalars, C₁ and Cz two matrices, and e > O, then we have.
Σ
a
S
|a ?!?
(35)
17

---

Published in Transactions on Machine Learning Research (08/2022)
2 a2) ||a]]|² + ||a2|| - -a2l??.
(36)
2b1b2 S bi ve O.
(37)
(Cauchy-Schwarz))
[Tr(CiCa)ls
|Clle
(38)
A.4 Proof of Lemma
Let of denote the th row vector of matrix A and e, the 1t vector of the canonical basis of R then
can write
E
| (W - -J) [12]
K
W 1
|
at
K
|af ||2
e K
(39)
From
Lian et al. 2017 Lemma 5), we have
1 K
W e;
S p".
(40)
Replacing equation equation we get
E | (W" - J) [|2] S p² 1A
(41)
Hence, the proof is completed.
A.5 Proof of Lemma 2
From Assumption 4, we have that the function + {(0,E) is bounded, then 0 + exp(e(0,g)) is C on a compact, and as a consequence, there exists Le > such that
Bl[exp exp (=1) - exp (22) |] S Te|=1 =2),
(42)
where 2, = E(O,, E). Next, let > 22 and define t; = exp(z;), then we can write
exp (1) - 1)M
exp (1 1)M
El( - t1' E
xx dr <
1811 [2]
E [exp (21) exp (22)]-
1
(43)
Using 42
we get
Elt
tg s exp ( 1),0 LolE
22
(44)
A similar result can be obtained we considered 21 < 22, hence, we can write
E
s exp ) L.E
1)M
(45)
11
Using the definition of Y, we can write
E
[| exp(()) - exp(v2)l - L2(4)111 321-
(46)
18

---

Published in Transactions on Machine Learning Research (08/2022)
where L2(H)= == exp ( 1)M) Le and hence the proof of statement (a).
For statement (b); using Hoeffding's lemma, we can write
E [()))
M 2p²²
M M
E (eex((((0,5)/mm) exp
+
S exp
+
(47)
2p²
By choosing G2( = exp Af M²)
we prove statement (b).
2n²)
Finally, for statement (c), we write
-xtpe(((...))))eeep(pppe exp(fx())m1) 2 (((ee (xp(((2)))))))=+((())))))))))))
(48)
Using Assumption and Hoeffding's lemma, we get
E
(49)
where (dz(m))) : (exp 2M +
M² 1²²
+ cxpp (2M1 ))
A.6 Proof of Lemma 3
Using the update rule 20 and the identity WJ JW J, can write
0' - (J= ( W(I J) 1'~ J)W -U
(50)
Writing
50 recursively, we get
0' - - -) -I- - - U = -
(51)
7=0
where we used the fact that all local models are initiated the same point, i.c. 0 J)W Thus, we can write
T E
Σ
(I-
KT
27 Σ U (w
1-1
Σ
KT
F
Σ ("- VFT) (Wi- J)
E
27²²
27
VF-VF (W
E
F (W
(22)
19

---

Published in Transactions on Machine Learning Research (08/2022)
where we used 35 (for S 2) in the last inequality. Let B,,, W - J. We start by examining the first term of 52 by writing
Σ U VF B
Σ E - VF
B 2
T=0 7'=0,
+'
E
U
V
F 1/
B 1|
Σ
B [ VF B 11u VF Br,((r
r'=0,
r'
B
E
1
-
+
+
1-1
E
[
V
[7]] <p E U
1 (53)
V
2e
2
0=0
7= 0= 7'=0,
+' +'ght
where we have used Lemma and inequalities
(7
and
(38
Setting p - we can further write 533
E
Σ UU- - VFF)
Br
E
| - AF |2
B
2
T=0 0'=0,
+/T
t-1
E |ーー [2
Σ
Σ
E
7=0
7/0
Σ p x
| - V
Σ 2
-
[2
B E -1- VF |/
1
VF
Σ p
Vp L
$
(54)
1 Vp 1=0
where in the last inequality, we used Σ Σ p 2 vp + vp + Vp S vP
I-V0. Now, let's focus
finding an upper bound for the term E -0- F F [ To this end, we start by writing
10 - 1 1
h(0T::))((0)) exp ()((E)) P
V.A(O)))
(55)
2
20

---

Published in Transactions on Machine Learning Research (08/2022)
Next, write the following
)
h(07; ((00;1)):((7)) - exp
= -1(0::)))(((0) - : p: (0)) + :)((())):(00) - [1(())
(f)) + exp [ V.:(0T) exp
[[((5] p
exp
V):(0)))
(56)
Using the decomposition
56
in 55
and taking the expected value while using the incquality 35 (for
S = 4), we get.
E
UT
VF
[1T:;]) (g:(0T) 0010 + 112
Vi((OT) (1100:1)) - exp ((((TT
B
-100
||
|eep Texp
f((O:))
E
1 (VS1())) VS((O))
4(G2(1)) 112
A(G2(1)))
E (0g) (0))
Σ
E (1)
122
4G K
[((OT))
(27
4(G2(1))
K
+
:4) exp
+
[IV)(( [((0))]
112
1²
8G2 P '
K
8G 0 (I2 +1K
E 1110 0,1 +
11
n2BBB
SG L2 122
8G 8G + 1)K
||
[)
+
(57)
122
where we used Assumptions 1-3 and defined the constants 0₂ = -max 02 02, az()),, G₁ = max (G G2(11) and L,- = LL L1, (2))) Going back to 54 and using (57 we can write
T
Σ
U -F-FFF
B
KT
F
L
T 1-1
0 (I - J) + ( +1)
T (-1
t-
Σ Σ p
<
11 vp) KT
12(1 VPTT t=1 r=0
1=1 1=
I S 12
T-t
S 1)
T T-
[|
J
11 vp) KT
1221 VPTT
r=0
SpG2 1.2
1
Sp +1)
< 12(L 3 KT
E
[I
(58)
1P(1 2p)
Now, we focus on the second term of we get
52
Following similar steps as when bounding the first term of
52
E
V F
B
p E
1
(59)
21

---

Published in Transactions on Machine Learning Research (08/2022)
Next, we look for an upper bound for the term E
|VPT
To this end, we start by writing
E
WVFI
||
1
K
f((O
E
exp
Vf((.))
1
(2)
[V
12
G1 2 (G2())))
x
11
G K
(60)
22
Therefore, we get
GhP
E
F B r,
(61)
KT
p² vD)2
Next, using
52
588
and
we can write
KT Σ E 10
1)
16 n²(1 2 KT
1
Σ
T
E [100 -J-J]
2n pG 180
10 (1. +1) + G
(62)
12 vp)²
Let 7/2 = 160² p p=11-pp]= -pj then we obtain
277² pG (00 (8
+ G2]
KT [I
(63)
1² - (111-)111-00 - 2
which concludes the proof of Lemma 3
A.7 Proof of Theorem
Since the objective function F(-) has Lipschitz gradient, can write
L
F(O - 1 F(O)) (VF(0)) 0+ 0t) 0++11 0.113.
(64)
Plugging the update rule 0+ 0¹ - n K, we have
U'1 L
U 2
F( F(O)) < (VF
(65)
K
2
K
Using the identity
36 we can write the first term of the left hand-side of
65
as
U'1, 1 (VF()))
U
U'1
|VF(0))22
F(0*)
(66)
K -
K
K
22

---

Published in Transactions on Machine Learning Research (08/2022)
Next, look for upper bound for the third term of 666. To this end, start by writing
U'
VF(0')
K
1
):(0')
Vi((0') (0:;;)
exp
μk
16
K
1:(0%)
K
Vf((0') ~(0')) ~(O
: (VV
exp
pk
uk
K
1
( h( H1:; +
(67)
uk
Using the inequality
35
we get.
U'1
VF(O')
K
K
1:(0')
- -m(0'u))
4
Σ [l((((': 100:4)) (('))
exp
K.2K
11
12
4
4
|0O0:: μ)) (Vf((0')-9:(00 -
|n(0 1)) (9:(0') - (0))
(68)
n
K
12K
Using assumption and taking the expected value from both sides, we can write
U'
27
E
OF
K
4G
fi(0')
4G
E
exp
-h00:: 12)
+
E
I((0: (M) h(0 [
# K
1
p22k K
T2
2i
4(G2(1))
K
4(G2(11)) K μ²K
Σ
E
(
9.(00))1
E 9 (0') g. (0))
(69)
12K
We start by bounding the term Ti
f((09)
T = E
exp
1(00:11)
15
B
E(0' (5)
f((0))
2 E
B
1
I
E
Σ (8(0', - 1(00))
B2
12 IE B²
Σ
X
13
Σ
R.
X
Σ
B [(xx
(70)
2
23

---

Published in Transactions on Machine Learning Research (08/2022)
where X E(0', - f. Since & and Ej are independent for + then E [(X] xx)] 0. Then, using
25
we can write that
L Ti
1 (B,
12202
E X
(71)
B²
B²
Similarly, we can bound the term T3 as T3 S o/ Next, we bound the term Tg as
1/(0: :1) - h(0 [11111111 m)1
T2 = E
27
E
exp
- Σ
1 13
1(0' ,5)
exp
1
B
E(0),
B
1
B
1
|=1
1=1
16
B
E(0'
1
B
e(0),
L
B j=1
B
1=1
L B²
E
Σ (e(0', .5)) -((O),E)))
L Σ
|le(0-.5) -5) - ((0
By2
/=1
(a) T. G2
||00 -0-1""]
E
(72)
422
where we have used the fact that last inequality. Finally, using 11 terms Ti-Ta, we can write
12 gives that E(0' EJ) is G-Lisschitz continuous in (a) and 24 in the can bound T3 as T4 S LE || 11|13 Using the bounds the
U'1
4G o + x2)
GG + 12)12
K
E
VF(O)
E [10' - 0/.33]
(73)
K
B²B B
μ* K
1=1
Replacing
73
in
66
we obtain
U'1
U'1 27
2G 22 [T3 + 122)
2G (G2 + x12)122
E
O0')
2
E
[IVE
E [1 J)
K
K
11¹
n* K
(74)
Going back to
65
we can write
E -
- - 7 [IVF(O)) + 7 (nL, - 1)
U'1
+
20 o (1 12)
+
4G + 122
[[i0(I []]]]]]
2
2
K
=²B
μ²
(75)
Setting the learning rate such that nLp < 1, and taking the average over E [1,T], we get
F(OT) F(
+ +12)
2n
12 L2 (G + 2²)
T Σ
E ( +
E
0 (J-J]
T
2T
B
μ KT
E
(76)
24

---

Published in Transactions on Machine Learning Research (08/2022)
Re-arranging the terms and using assumption 5, can write
2(F - Fins) 2 + 22)
2G L + 12)
E [IV
Σ
E
||00 (I J)
T
n/T'
4BB
μ*T
(77)
Using Lemma
T we get
3
2(F(0)) Fins)
20 (L2 + p2)
4n 2 L3 pG (G2 + /²) 18, + 1) G
1/T
1 B
1 7) vD)²
(78)
Furthermore, choosing 7 such that nLnn < p(1-v0)
ensures that 7/e < 1
21 then we can write
8GpvP
2(F(0')- Fin))
oL + w²)
L + 18) + 1)+
E
|VF(0') <
1/T
μ B
3p vp)
(79)
which finalizes the proof.
25


Reviews:
[{"review_id": "7peKcO32U4", "reviewer": "Reviewer_Xb1C", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nFirst of all, I want to state that I checked all proofs and I did not find any serious mistake. I think the proofs are correct.  \nI also found the work to be sufficiently well-written. There are some typos, but they are fixable. The only missing piece in terms of writing is a good discussion of the paper's limitations.  \nFinally, I found the topic of the work to be quite meaningful. There is an ongoing effort to make decentralized optimization useful in applications and I think the combination of decentralization and distributional robustness makes sense.\n\nI do not have much to say about the experiments, but it seems they are sufficiently good. For some reason, the authors only compared to DSGD, so there is no comparison to non-decentralized algorithms, but the paper seems to be primarily theoretical, so I will not request any additional experiments.\n\n## Weaknesses\nThe theory in this work is far from satisfying. There are several major issues:\n1. First of all, it is not exactly clear if the authors aim at solving problem (5) or (6). From the text, it appears that the main interest is in having robustness as given in formulation (5). However, there are no guarantees for that problem in this paper. Instead, Theorem 1 states convergence for the gradient norm of the regularized objective. The authors should either explain how these guarantees translate to guarantees for problem (5), or give sufficient motivation to solve (6).  \n2. Secondly, I am quite unhappy about the results. The error in Theorem 1, $O\\left(\\frac{1}{T} + \\frac{1}{\\mu^2} \\right)$, does not go to 0 if we increase the number of iterations, so it does not guarantee convergence. It could be fine if we could also increase $\\mu$, but the issue is that in this case the problem would get closer and closer to the standard empirical risk minimization. So, the more robustness we want the worse is the guarantee, which I find to be a very significant limitation. Resolving this issue is absolutely necessary for the paper to be accepted.\n3. Next, I am a bit unhappy about Assumption 2. The assumption requires almost surely bounded gradient gradients and bounded loss values, which seems to be quite restrictive. This type of assumption has been criticised in the literature on federated learning (see Khaled et al., \"Tighter theory for local SGD on identical and heterogeneous data\"). \n4. I am also concerned about implicit dependence of \"constants\" on $\\mu$. For instance, equation (12) in Assumption 1, equation (14) in Assumption 2, and equation (17) in Assumption 3 all state the bounds in terms of universal constants even though they involve $\\mu$. It seems that the values of $L_2$, $G_2$ and $\\sigma_3$ implicitly depend on $\\mu$, and at least in Corollary 1, the value of $\\mu$ is not assumed to be fixed. The authors should either justify why these constants do not depend on $\\mu$, or they should fix the assumptions and make the necessary corrections in the theoretical results. \n5. Corollary 1 is very strange, if not incorrect. First of all, why can we take $\\eta=\\sqrt{\\frac{K}{T}}$? It is not apparent at all why this value would satisfy the conditions of Theorem 1. Secondly, the value $\\mu = \\left(\\frac{1}{KT}\\right)^\\frac{1}{4}$ does not lead to the upper bound as written in (27). Indeed, $\\mu^2$ is in the denominator in (26), so to obtain the expression in (27), one needs to set $\\mu=\\left(KT\\right)^\\frac{1}{4}$, which to me makes no sense.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This works studies distributionally robust optimization, i.e., the problem of minimizing the worst linear combination of given losses $f_i$, where $f_i$ is the objective of $i$-th device. The authors assume that $f_i$ is given in the form of expectation over random samples, with bounded values, bounded variance of values, and bounded variance of the gradients as well.  \nThe authors formulate this problem and then relax it using Kullback-Leibler regularization from uniform weights. They parameterize the regularization with coefficient $\\mu$, which gives the original problem if $\\mu=0$ and gives standard empirical risk if $\\mu\\to+\\infty$. The last objective can be equivalently rewritten as $\\min_{\\Theta} \\frac{1}{K}\\sum_{i=1}^k F_i(\\Theta)$, where $F_i(\\Theta)=\\frac{\\exp(f_i(\\Theta))}{\\mu}$.  \nThe main contribution is a decentralized algorithm that runs stochastic gradient descent on each device and communicates with neighbors given by a mixing matrix $W$. The authors state its convergence in Theorem 1, which is roughly saying that after $T$ iterations we have $\\mathbb{E}[\\Vert\\nabla F(\\overline \\theta)\\Vert^2] = O\\left(\\frac{1}{T} + \\frac{1}{\\mu^2} \\right)$.  \nThe authors also run experiments to compare their algorithm DR-DSGD with non-decentralized DSGD.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The main change required from the authors is to fix convergence and dependence on $\\mu$ in the constants. There should also be a discussion of the assumptions as they are quite restrictive.\n\n## Minor points\n1. One thing that really confuses me is that superscripts are used both as iteration counters and matrix powers, sometimes within the same equation, for instance in (36).\n2. The authors claim several times that their algorithm is \"robust to data heterogeneity\". I am not sure what this means and where it is shown. Instead, it seems that the algorithm is robust to distribution shift, which is not the same as robust to higher data heterogeneity. Moreover, I suspect that any algorithm that tries to use distributional robustness would be less robust to data heterogeneity, as it may largely overfit to the data on a single client.\n3. Why is DR-DSGD better than DSGD in the experiments in terms of average test accuracy? From what I understand, DR-DSGD is solving a harder problem, so it is natural to expect that it would be better in terms of worst-distribution test accuracy, but the improvement of the average accuracy is quite surprising. For instance, in the work on \"tilte\" risk minimization, Table 7, only an improvement for the worst devices is reported.\n\n## Typos\nPage 2, \"on distributionally robustness\" -> \"on distributional robustness\"  \nPage 2, \"as shown in corollary 1\" -> \"as shown in Corollary 1\"  \nPage 3, \"set of neighbors of device $n$ is defined as $N_i$\" -> \"set of neighbors of device $i$ is defined as $N_i$\"  \nPage 3, \"if only if\" -> \"if and only if\"  \nPage 4, the text writes \"a local stochastic gradient update (Line 3) using the learning rate $\\eta_t$\", but in the algorithm itself $\\eta$ is used without a subscript  \nPage 5, equation (15), it's not vectors, so norms need to be replaced with absolute values  \nAssumption 4 should probably mention that $F_{inf}>-\\infty$  \nPage 7, \"we start by stating a key lemma\". It's a bit strange to write this after stating Lemma 1  \nPage 7, \"Let $\\eta$ satisfies\" -> \"Let $\\eta$ satisfy\"  \nPage 14, equation (38), the last term should be part of the sum rather than be written separately from it  \nPage 15, the step where $\\sum_{\\substack{\\tau'=0 \\\\ \\tau'\\neq \\tau}}^{t-1} \\rho^{\\frac{t-\\tau'}{2}}$ is changed to $\\sum_{\\tau'=0}^{t-1} \\rho^{\\frac{t-\\tau'}{2}} - \\rho^{\\frac{t-\\tau}{2}}$ should be identity rather than inequality  \nPage 16, \"where we used assumptions 1-3\" -> \"where we used Assumptions 1-3\"  \nPage 17, \"$F(\\cdot)$ is Lipschitz smooth\" -> \"$F(\\cdot)$ is $L$-smooth\" or \"$F(\\cdot)$ has Lipschitz gradient\"  \nPage 18, equation (52), the last terms in the right-hand sides are detached from the sums, use () to make them part of the summation  ", "broader_impact_concerns": "I do not think that there might be any ethical concern about this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "frUjDXbaCs", "reviewer": "Reviewer_7oCx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* The paper is generally well-written and pleasant to read\n* Experimental results are promising, showing consistent improvements over plain DSGD\n* The theoretical analysis guaranteeing convergence at the expected $\\mathcal{O}(1/KT)$ rate appears to be correct.\n\n## Weaknesses\nI elaborate on each of the following weaknesses below, when discussing requested changes to address them:\n* Several statements in the introduction are highly debatable. The paper would be strengthened by providing better support for these, or by softening the statements.\n* There are some relevant references on robustness in FL that are missing\n* There are relevant references to related work on decentralized distributionally-robust methods that are missing\n* Several assumptions in the analysis should be more clearly explained, better justified, or possibly even simplified\n* There are ways in which the presentation of theoretical results in Section 5 could be improved\n* The experimental evaluation only compares DR-DSGD with DSGD. In particular, there isn't any comparison to other methods in the literature that aim to address robustness or data heterogeneity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes and analyzes a new method, distributionally-robust decentralized stochastic gradient descent or DR-DSGD, for robust decentralized learning. The target setting is motivated by federated learning, where there is data heterogeneity. Rather than the usual objective, which corresponds to minimizing the empirical risk, the proposed objective is the usual one considered in distributionally robust optimization, where the aim is to minimize the loss wrt the the worst-case mixture over data distributions. Using existing ideas from the literature, this min-max problem is transformed to a minimization problem with a different objective, and the standard DSGD method is applied to the new formulation. A convergence analysis is provided for the smooth non-convex setting, and experiments validate the convergence analysis, highlighting the promising performance of the proposed approach in comparison to standard DSGD applied to the ERM formulation.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The suggested changes here are primarily to address weaknesses mentioned above.\n\n### Accuracy of several statements in the intro\nThere are several statements made in the introduction which are highly debatable and should be better supported by evidence.\n* \"privacy ensured by only exchanging models/gradients with server\" This is not true; see for example, work on gradient inversion attacks such as [Geiping et al. 2003](https://arxiv.org/abs/2003.14053). Additional mechanisms are needed (differential privacy, secure aggregation) to formally ensure privacy.\n* \"Most FL algorithms fail to address the data heterogeneity issue\" There have been several methods proposed in the FL literature that aim to address the data heterogeneity issue, and which ought to be better acknowledged. For example, see FedProx, VRLSGD, Scaffold, Mime, FedNova, FedLin, and FedShuffle.\n* Although I agree that FedAvg-style methods are state-of-the-art, I would not call FedAvg itself state-of-the-art in FL. Again, see the methods mentioned in the previous point, which exhibit superior performance to FedAvg.\n\n### Relationship to other literature on robustness\nSeveral other papers in the literature address robustness in FL in different senses. While the paper does already mention several relevant references, there are a few others I was also expecting to see:\n* [Pillutla et al., 2019](https://arxiv.org/abs/1912.13445) and references therein\n* [Li et al., 2020](https://arxiv.org/abs/2012.04221)\n\n### Relationship to other decentralized algorithms for distributionally-robust optimization\nThere is some prior literature looking at decentralized distributionally-robust optimization specifically in the context of power systems. It would be good to call out this connection and also acknowledge prior work. For example, see\n* https://ieeexplore.ieee.org/abstract/document/9542394\n* https://ieeexplore.ieee.org/document/9208508\n\n### Explaining, justifying, and possibly simplifying assumptions\nPresently, the analysis in Section 5 requires some strong assumptions, and it is not clear whether these are all necessary.\n* Assumption 1, equation (12) essentially follows from assuming that the range of the ($\\mu$-scaled) loss function is bounded. Can you provide examples of loss functions that satisfy this assumption? The only way I can see to ensure this for most commonly-used losses is to impose a clipping. If that's indeed necessary, then it would be better to state it explicitly. Once you assume that the range is bounded, then smoothness of $F_i$ and $F$ follows directly from smoothness of $f_i$. Often one may already know or more easily check properties of $\\ell$, and hence $f_i$, than properties of $F_i$ or $F$.\n* Equation (11) is not well-defined as written, since $g_i$ are stochastic gradients. Is there a missing expectation? Or is the assumption really that $\\| \\nabla \\ell(\\theta_1, \\xi_i^t) - \\nabla \\ell(\\theta_2, \\xi_i^t)\\| \\le L_1 \\|\\theta_1 - \\theta_2\\|$ for all $\\xi_i^t$?\n* The bounded gradient assumption is rather strong. Can you provide examples where this holds?\n\n### More general suggestions about the presentation of the theoretical results\n* The ultimate objective (8) on which the DR-DSGD method is based is the composition of the original loss $f_i$ with the exponential function, which is smooth, convex, and non-decreasing. I appreciate that the analysis focuses on guarantees for non-convex functions. However, to start, it could be worthwhile to point out that if $f_i$ is convex (e.g., if $\\ell$ is convex), then convergence of the proposed method follows directly from existing results in the literature. In particular, since $\\exp(\\cdot)$ is convex and non-decreasing, if $f_i$ is also convex then (8) is convex too.\n* In the non-convex case, as mentioned in Remark 1, gradients aren't unbiased. It could be worth pointing out that this is not necessarily detrimental, and it is well known (e.g., [Bottou et al. (2016)](https://arxiv.org/abs/1606.04838) Theorems 4.8 and 4.9) that stochastic gradient methods can still converge as long as the stochastic gradients are sufficiently well-aligned with the expected gradient.\n* How are $\\sigma$, $L$, and $G$ in Lemma 2 defined? The definitions ought to be included in the main body of the paper for readability. \n\n### Suggestions for the experiments section\n* Please include more details about the ``pathological non-IID way'' in which data is distributed across devices, to enable an interested reader to reproduce your results.\n* Was it expected that DR-DSGD improves Average Test Accuracy, in addition to Worst Distribution Test Accuracy? Or is this a pleasant consequence? Is there some intuition for why this is the case? Would it be the same if data were IID across devices?\n* The empirical comparison only is made between DR-DSGD and DSGD. It would significantly strength the work and increase the interest of the paper if a comparison was included to other methods from the literature on robustness and fairness in FL, such as DITTO, Tilted empirical risk minimization, and DRFA.\n* The `networkx` package provides functions to generate several types of random graphs. It sounds like the ones used in the experiment are Erdos-Renyi. Is that correct? Please clarify. It could be relevant to explore performance on several other types of graphs (e.g., rings, grids, ...) to validate the theoretical dependence on network topology.", "broader_impact_concerns": "I don't have any major concerns about ethical implications of the work. At the same time, given that the paper addresses fairness and robustness, it seems like there is a missed opportunity here to discuss the potential broader impact of this work, since the Broader Impact Statement has been omitted in the initial submission.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "b6hTmXvG5u", "reviewer": "Reviewer_A9Fv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed algorithm has better performance than decentralized SGD\n2. The proposed algorithm has rigorous convergence guarantees since it is essentially decentralized SGD.\n\nWeakness:\n1. The analysis seems to be unnecessary since there are many existing analyses for decentralized SGD.\n2. The experiment is a bit weak and unconvincing for several reasons. 1). The parameter tuning procedure seems to be missing in the paper. 2). The experiments use small datasets, a small neural network, and a small number of devices. It is hard to say how the algorithm will perform in more practical settings.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposed a decentralized optimization algorithm for agnostic federated learning. The proposed algorithm is essentially decentralized SGD applied to a slightly different formulation than empirical risk minimization. Experiments on Fashion MNIST and CIFAR-10 are done to compare the proposed algorithm with decentralized SGD. Empirically, it is shown the proposed algorithm can converge faster and can achieve smaller accuracy variance across nodes.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. If the analyses is just redoing traditional analyses for decentralized SGD, please remove it and cite existing results. If not, please highlight the difference and this could be part of the contribution.\n\n2. Please include parameter tuning procedures like how stepsizes and \\mu are chosen for the experiments.\n", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)