Communication-Efficient Distributionally Robust Decentralized Learning
Authors: Matteo Zecchin
Marios Kountouris
David Gesbert
Venue: Accepted by TMLR ()

Abstract: Decentralized learning algorithms empower interconnected devices to share data and computational resources to collaboratively train a machine learning model without the aid of a central coordinator. In the case of heterogeneous data distributions at the network nodes, collaboration can yield predictors with unsatisfactory performance for a subset of the devices. For this reason, in this work, we consider the formulation of a distributionally robust decentralized learning task and we propose a decentralized single loop gradient descent/ascent algorithm (AD-GDA) to directly solve the underlying minimax optimization problem. We render our algorithm communication-efficient by employing a compressed consensus scheme and we provide convergence guarantees for smooth convex and non-convex loss functions.  Finally, we corroborate the theoretical findings with empirical results that highlight AD-GDA's ability to provide unbiased predictors and to greatly improve communication efficiency compared to existing distributionally robust algorithms.

Published in Transactions on Machine Learning Research (12/2022)
Communication-Efficieiit y Robust Decentral- ized Learning
Matteo Zecchin Communication Systems Department EURECOM, Sophia Antipolis, France
matteo..ecchinn@ecrrno..
Marios Kountouris
Communication Systems Department EURECOM, Sophia Antipolis, France
David Gesbert
duvidd.gesberttBeeeeeoo
Communication Systems Department EURECOM, Sophia Antipolis, France
Reviewed on OpenReview: /ttps://openreeeee net/ forum? id- tnRRHzZPNg
Abstract
Decentralized learning algorithms empower interconnected devices to share data and computa- tional resources to collaboratively train a machine learning model without the aid a central coordinator. Tn the case of heterogeneous data distributions the netw nodes, collabora- tion can yield predictors with unsatisfactory performance for subset of the devices. For this reason, in this work, we consider the formulation of distributionally robust decentralized learning task and propose decentralized single loop gradient descent/asee /ascent algorithm (AD-GDA) to directly solve the underlying minimax optimization problem. We render our algorithm communicttion-eficaee provide convergence guarantees for smooth convex and non-convex loss functions. Finally, we corroborate the theoretical findings with empirical results that highlight AD-GDA's Ass ability to provide unbiased predictors and to greatly improve communication efficiency compared to existing distributionally robust algorithms.
by employing a compressed consensus scheme and we
1 Introduction
Decentralized learning algorithms have gained an increasing level of attention, mainly due to their ability to harness, in a fault-tolerant and privacy-preserving manner, the large computational power and data availability at the network edge (Chen & Sayed] 2012: Yan et al. 2012). In this framework, set of interconnected nodes (smartphones, IoT devices, health centers, research labs, etc.) collaboratively train a machine learning model alternating between local model updates, based on in situ data, and peer-to-peer type of communication to exchange model-related information. Compared to federated learning in which swarm of devices communicates with central parameter server at each communication round, fully decentralized learning has the benefits of removing the single point of failure and of alleviating the communication bottleneck inherent to the star topology.
The heterogeneity of distributedly generated data entails a major challenge, represented by the notions of al. 2009). In the distributed setup, the
fairness (Dwork et al.) 2012)) and robustness (Quiñonero-Cante customary global loss function the weighted sum of the local empirical losses, with each term weighted by the fraction of samples that the associated node stores. However, in the case of data heterogeneity across participating parties, model minimizing such definition of risk can lead to unsatisfactory and unfair
In the machine learning community, the notion of fairness has many facets. this work, we will accordance with the nation good-intent. faimesss as introduced in Mohri al. 2019).
"fair"

---

Published in Transactions on Machine Learning Research (12/2022)
inference capabiliitis for certain subpopulations. Consider, for example, consortium of hospitals spread across the world sharing medical data to devise a new drug and in which small fraction of hospitals have medical records influenced by geographical confounders, such as local diet, meteorological conditions, etc. In this setting, a model obtained by myopically minimizing the standard notion of risk defined over the aggregated data can be severely biased Lowards some populations at the expense of others. This can lead to a potentially dangerous or unfair medical treatment as shown in Figure
0.-
Awergy
with microscope
CHOCOASGD Minasppe
Node with microscope
1000
5030
2003
2030
Link
Network Topology
(b) Worst-node accuracy
Figure 2: Comparison between standard and distributionally robust decentralized learning procedures. We consider & network of 10 nodes that collaboratively train a mouse cell image classifier based on the Cells Out Of Sample 7-Class (COOS7) data set (Lu et al. 2019). Two nodes store samples obtained using different microscope from the rest of the net work devices (left figure). On the right, report the validation accuracy of the standard decentralized learning (CHOCO-SGD) and the proposed distributionally robust decentralized learning (AD-GDA). We consider three different validation sets: one made of samples from one microscope, another with samples from the other, and one made of a 50/50 mixture of the two. CHOCO-SGD (dashed lines) yields a final model with a 24% accuracy gap between the two types of instruments. On the contrary, AD-GDA (solid lines) reduces the accuracy gap less than 2% and improves fairness among collaborating parties. The average performance is not affected by the distributionally robust procedure.
To tackle this issue, distributionally robust learning aims at maximizing the worst-case performance over set of distributions, termed uncertainty set, which possibly contains the testing distribution of interest. Typical choices of the uncertainty sets are balls centered around the training distribution (Esfahani & Kuhn 2018 whenever the training samples come from a mixture of distributions, the set of potential subpopulations resulting in such mixture (Duchi et al. 2019 Duchi & Namkoong) 2018). Robust distributed learning with heterogeneous data in which different distributions exist at the various devices falls in the latter category, as the natural ambiguity set is the one represented by the convex combination of the local distributions. In that case, minimizing the worst-case risk is equivalent trying to ensure a minimum level of performance for each participating device. Specifically for the federated case, Mohri et al. (Mohri et al., 2019) introduced agnostic federated learning (AFL) as means to ensure fairness and proposed gradient gradient-based algorithm to solve the distributionally robust optimization problem. In (Deng et al. 2021 communcction-effiienn version of AFL, which avoids frequent retransmission of the dual variables, was proposed. More recently, distributionally robust learning has also been studied in the fully decentralized case. In this setting, the underlying minimax optimization problem becomes challenging and distributionally robust learning has been limited a special formulation Kullback-Lcibler (KL) regularization that allows simplifying the problem [Issaid al. 2022..
In virtue of the advantages of the fully decentralized setup and advocating the necessity for robust and fair predictors, in this work we propose AD-GDA, novel distributionally robust algorithm for the decentralized setting. In contrast to previous works, our solution directly lackles the minimax optimization problem in a fully decentralized fashion. Our algorithm is general and encompasses previous solutions as particular choices of the regularization function. Furthermore, we show that is possible perform distributionally robust optimization in a commmication--ffcienn manner by employing a compressed gossip scheme without hampering the rate of convergence of the algorithm.
2

---

Published in Transactions on Machine Learning Research (12/2022)
Table 1: Comparison between the proposed and existing distributionally robust algorithms.
Features
Convergencee rate
Topologies
Compression
Regularizer
Couvex
Non-convex
AD-GDA (ouns) DRFA (Deng et al. 2021
Connected
Strongly-coneave
(TT-1/3)
((T-1/2)
Star
Strongly-concave
((T-1/8)
O(T-1/8)
DR-DSGD Issaid al. 2022
Connected
x
Kullback-Lcibler
x
((T-1/2)
Contributions: The main contributions of the work are the following:
We propose AD-GDA, optimization algorithm to perform distributionally robust. learning in fully docentralized fashion. As detailed in Table previous works have cither been limited to the federated case or particular choices of the regularizer, AD-GDA direclly tackles the distributionally robust minimax optimization problem in fully decentralized fashion. Despite the additional complexity stemming from solving the docentralizod minimax optimization problem, our solution is computation and communication efficient. AD-GDA alternates between local single-loop stochastic gradient descent bescent/ascenn ascent model updates and compressed consensus steps cope with local connectivity in a commuicationn-eficient manner.
We establish convergence guarantees for the proposed algorithm both in the case of smooth convex and smooth non-convex local loss functions that match or outperform the existing ones (see Table 1.. In the former case, the algorithm returns e-optimal solution after O(1/²²) iterations. In the latter, the output is guaranteed to be e-stationary solution after O(1/e²) iterations whenever the stochastic gradient variance is also bounded by otherwise, we can obtain the same guarantee by increasing the number of calls to the stochastic gradient oracle.
We empirically demonstrate AD-GDA capability in finding robust predictors under different com- pression schemes, network topologies, and models. First, we compare the proposed algorithm with compressed decentralized stochastic gradient descent (CHOCO-SGD) and highlight the merits of the distributionally robust procedure. We then consider the existing distributionally robust learning algorithms; namely, Distributionally Robust Federated Averaging (DRFA) (Deng et al. 2021 and Distributionally Robust Decentralized Stochastic Gradient Descent (DR-DSGD) (Issaid et al. 2022). We show that AD-GDA attains the same worst-case distribution accuracy transmitting fraction of the bits and it is up to 4x and 10x times more communication efficient compared to DRFA and DR-DSGD, respectively.
2
Related Work
Communication-efticeen decentralized learning. Initiated in the 80s by the work of Tsitsiklis (Titssiklss
1984
Tsitsiklis et al. 1986), the study of decentralized optimization algorithuss was spurred by their adaptability to various network topologies, reliability to link failures,
capabilities, and potentially superior convergence properties compared the centralized counterpart (Chen Sayed 2012 Yan al. 2012 Olfati-Saber et al. 2007 Ling al.) 2012: Lian et al. 2017). This growing interest and the advent of large-scale machine learning brought forth an abundance of optimization algorithms both in the
deterministic and stochastic settings (Nedic & Ozdaglar 2009 Wei & Ozdaglar 2012 Duchi et al. 2011
Shamir & Srebro 2014 Rabbat 2015). With the intent of extending its applicability, concurrent effort has been made to devise techniques able to reduce the delay due to inter-node communication, Notable results in this direction are the introduction of message compression techniques, such as sparsification and quantization
(Stich et al. 2018 Aji & Heafield| 2017 Alistarh et al., 2018 2017 Bernstein et al. 2018 Koloskova al. 2019bb, and triggerriggeee commmncation allow multiple local updates between communication rounds
(Stich 2018
Yu et al. 2019
3

---

Published in Transactions on Machine Learning Research (12/2022)
Distributional robust learning. Tracing back to the work of Scarf (Scarf 1957). distributional robustness copes with the frequent mismatch between training and testing distributions by posing the training process as game between a learner and an adversary, which has the ability to choose the testing distribution within an uncertainty set. Restraining the decisional power of the adversary is crucial to obtain meaningful and tractable problems and a large body of the literature deals with uncertainly sets, represented by balls centered around the training distribution and whose radii are determined by f-divergences (Namkoong & Duchi Hu & Hong 2013) or Wasserstein distance (Wozabal, 2012] Jiang & Guan 2016 Esfahani & Kuhn 2018 As such, distributional robustness is deeply linked to stochastic game literature. In this context, Lin et al. (2020b) provides last-iterate guarantees in case of coercive games. Refined results are later obtained in (Loizou et al.) 2021), for expected coercive games and by relaxing the bounded gradient assumption. Furthermore, dist ribbutioaaa robustness is deeply linked with the notion of fairness as particular choices of uncertainty sets allow guaranteeing uniform performance across the latent subpopulations in the data (Duchi & &NMakoong 2018): Duchi et al. 2019). In the case of fedcrated learning, robust optimization ideas have been explored to ensure uniform performance across all participating devices (Mohri et. al.] 2019). Distributionally robust learning has also been studied in the fully decentralized scenario in the case of Kullback-Leibler (KL)
2016
regularizers for which exists an exact solution for the inner maximization problem (Issaid et al. 2022
Decentralized minimax optimization. Saddle point optimization algorithms are of great interest given their wide range of applications in different fields of machine learning, including generative adversarial networks [Goodfellow et al.] 2014), robust adversarial training (Sinha et al. 2017 Madry et al. 2017): : and
multi-agent reinforcement learning (Pinto al. 2017: Li et al., 2019). Their convergence properties have also been studied in the decentralized scenario for the convex-concave setting (Koppel et al., 2015 Mateos-Nínez & Cortés 2015). More recently, the assumptions on the convexity and concavity of the objective function have been relaxed. In Tsaknakis et al. (2020) an algorithm for nonconvex strongly-concave objective functions has been proposed; however, the double-loop nature of the solution requires solving the inner maximization problem with an increasing level of accuracy rendcring it potentially slow. On the other hand, our algorithm is based on a single loop optimization scheme with dual and primal variables being updated at each ileration in parallel and, consequently, has a lower computational complexity. For the nonconvex- nonoovee--- case, Liu et al.] (2019b) provides a proximal point algorithm while simpler gradient-based algorithm is provided in Liu et al. (2019a) to train generative adversarial networks in a decentralized fashion. None of these works take into consideration communication efficiency in their algorithms.
3 Preliminaries
Distributed system We consider a network of m devices in which each node i is endowed with a local objective function ft : ud + R given by (0,,,, with P. denoting the local distribution at node i and E Rd being the model parameter to be optimized. Whenever P; is replaced by an empirical measure Pr the local objective function coincides with the empirical risk computed over n, samples. Network nodes are assumed to be interconnected by communication topology specified by connected graph G := (V,E) in which V- = -(l...., ) indexes the devices and (i.j) E & if and only if nodes i and j can communicate. For each node i E V. we define its set of neighbors by (ii) := {j : (i,j) E E} and since we assume self communicatioon we have (i, E (i) for all i in V. At each communication round, the network nodes exchange messages with their neighbors and average the received messages according to a mixing matrix W E mmxm.
Assumption 3.1. The mixing matrix W E gmm is symmetric and doubly-stochastic; we denote its spectral gap- the difference between the moduli of the two largest cigenvalues by p (0, and define B = I W112 E [0.
Compressed communication Being the communication phase the major bottleneck of decentralized training, we assume that nodes transmit only compressed messages instead of sharing uncompressed model updates. To this end, we define a, possibly randomized, compression operator Q R.d + Rd that satisfies the following assumption.
Assumption 3.2. For any I2" and for some 8 E (0, 1],
Ee [11((<)) x²| s (1 0)]|=
(1)
4

---

Published in Transactions on Machine Learning Research (12/2022)
The above definition is quite general as it entails both biased and unbiased compression operators. For instance, random quantization (Alistarh et al. 2017) falls into the former class and satisfies with 8 == 7 For a given vector æ E R= and quantization levels 2", it yields compressed message
2b sign(2)
||>||
|e||
26
+
(2)
2
with 7 = 1 + min {d/22s, vd/2b) and E e~ 400 _jed. A notable representative of the biased category is the
top-K sparsification Stich ct al. 2018). which for a given vector a E IR' returns the K largest magnitude components and satisfies with K. Operators of that type have been previously considered in the context of decentralized learning and the effect of compressed communication decentralized stochastic optimization has been previously investigated (Koloskova al. 2019a b) Stich et al. 2018). The resulting communication cost savings have been showeased in the context of decentralized training of deep neural
networks (Koloskova et al.; 2019a). However, to the best of our knowledge, there are no applications of comprossed communication to distributional robust training in the decentralized sctup.
Algorithm 1: Agnostic Decentralized GDA with Compressed Communication (AD-GDA)
Input :Number of nodes m, number of iterations T, learning rates vi and fJa, mixing matrix W initial values 8" Rd and X E An-1
Output: :0. 1
0¹
A = 1 -
initialize 0. 0 X =0
1o
and = i
for in o,...T do
In parallel at each node i 8. 0t 0 - no Vogi X
// Descent Step
x + PA (Mi 1/ A X E))
// Projected Ascent Step
0t41 - 0 +7 (si 0!)
// Gossip
q + Q (0)-1 1 -0) 0.)
// Compression
send (g), X; 4 $) to E (i) and receive x from j (()
// Msgs exchange
g.+1 qi 0
// Public variables update
a/11 - : Σラ= wigh
x Emn Wi.j X3
++
// Dual variable averaging
end
Distributionally robust network loss In order to obtain final predictor with satisfactory performance for all local distributions {P: the common objective is to learn global model which is distributionally robust with respect to the ambiguity set p == 1>" A.P. d e A where A where denotes the m probability simplex. As shown in Mohri et al. 2019). network objective function that effectively works as proxy for this scope is given by
min max OE XEA m--1
g(0.A) = (A.f((0 + ar()))
3))
m-1
(0.A))
in which r: mm11 + RR is a strongly-concave regularizer and a E R+ For instance, in the empirical risk minimization framework in which each node i endowed with a training set D, ~ ppn; and the overall number of training points n n= Σ, 2 ni, a common choice of r(A) is x²(x) = Σ. (A-nn//n)² or the Kullback-Leibler divergence (A : Σ, A₂ log (A,n/n,) (Issadd et al., 2022 Restricting (3) to the latter regularizer, the
2./n
inner maximization problem can be solved exactly (Issaid et al. 2022 Mohajerin Esfahani & Kuhn 2018).
In what follows, we refer to and X as the primal and dual variables, respectively, and make the following fairly standard assumptions on the local functions 9: and the stochastic oracles available at the network nodes.
5

---

Published in Transactions on Machine Learning Research (12/2022)
Assumption 3.3. Each function g A) is differentiable in R x Am-1, L-smooth and μe- concave in A.
Assumption 3.4. Each node i has access to the stochastic gradient oracles (0 (0, X,) and Vxgi E,), with randomness w.r.t. &s, which satisfy the following assumptions:
Unbiasodness
Es (o9.(0. (o,)(0,)), Eg, [J. = VA
(4)
Bounded variance
Egg (Vg:(0, (0. s sog. Es, (IVA::0,AAEE) -1 soz (5)
Bounded magnitude
Eg, [1.0, S G Es, (IVA):00.A.)))) GR.
(6)
The above assumption implics that cach network node can query stochastic gradients that are unbiased, have finite variance, and have bounded second moment. The bounded magnilude assumption is rather strong and limits the choice of regularization functions, but it is often made in distributed stochastic optimization (Stich
ct al. 2018 Koloskova et al. 2019a; Deng et al. 2021 ).
4 Distributionally Robust Decentralized Learning Algorithm
Problem (3) entails solving a distributed minimax optimization problem in which, at every round, collaborating nodes store a privade value of the model parameters and the dual variable, which are potentially different from node to node. We denote the estimate of the primal and dual variables of node i at time t by 0f and X and the network estimates at time & as 0' = = > of and X 1 >n Xf, respectively. The main challenge resulting from the decentralized implementation of the stochastic gradient descent/ /ascent/asscet /ascent algorithm consists in approaching a minimax solution or a stationary point (depending on the convexity assumption on the loss function) while concurrently ensuring convergence procedure, given in Algorithm [ alternates between local update step and consensus step. At each round, every node queries the local stochastic gradient oracle and, in parallel, updates the model parameter 0, by gradient descent step with learning rate > 0 and the dual variable X; by a projected gradient ascent one with learning rate y > 0 (Euclidean projection). Subsequently, a gossip strategy is used to share and average information between neighbors. In order to alleviate the communication burden of transmitting the vector of model parameters, which is typically high dimensional and contributes to the largest share of the communication load, a compressed gossip step is employed. To implement the compressed communication, we consider the memory-efficient version of CHOCO-GOSSIP (Koloskova al. 2019bb in which each node ncods to store only two additional variables Ô and 8;, each of the same size as 0,. The first one public version of 0, while the second is used track the evolution of the weighted average, according to matrix W, of the public variables at the neighboring nodes. Instead of transmitting 0,, each node first computes averaging step to update the value of the private value using the information about the public variables encoded in 0, and 8,. It then computes q:, a compressed representation of the difference between é; and 0, and shares it with the neighboring nodes to update the value of Ô; and 8; used in the averaging step in the next round. As the number of participating nodes is usually much smaller than the size of the model (m & d), the dual variable A; is updated sending uncompressed messages and then averaged according to matrix W. Note that AD-GDA implicitly assumes that collaborating parties are honest and for this reason, it does not employ any countermeasure against malicious nodes providing false dual variable information in order to steer the distributional robust network objective at their whim.
common global solution. To this end, the proposed
4.1 Comparison with existing algorithms
Before deriving the convergence guarantees for AD-GDA we compare the features of AD-GDA against other distributionally robust algorithms, DRFA and DR-DSGD (see Table [ Firstly, we notice that AD-GDA and

---

Published in Transactions on Machine Learning Research (12/2022)
DR-DSGD are fully decentralized algorithms, and therefore the only requirement for deployment is that the network is connected. In contrast, DRFA is a client-server algorithm and star topologies, which are known to be less fault tolerant and characterized by a communication bottleneck. Furthermore, AD-GDA is the only algorithm that attains communication efficiency by the mcans of message compression that, as we show in Section 5.2.2 allows AD-GDA to attain the same worst-node accuracy at much lower communication cost. compared to DRFA and DR-DSGD. is also important to notice that DR-SGD obtained by restricting the dual regularizer to Kullback-Leibler divergences, this allows sidestepping the minimax problem. On the other hand, AD-GDA directly tackles the distributionally robust problem (3) and therefore can be applied to any strongly concave regularizer that satisfies Assumption 3.4 For example, the chi-squared regularizer, which allows AD-GDA to direclty minimize the distributionally objective of Mohri et al. (2019).. In Section we show AD-GDA recovers the same convergence rate of DR-DSGD in this more general set-up.
(.3)
4.2
Convex Loss Function
We provide now a convergence guarantee for the solution output by Algorithm I for the case the loss function {(-) is convex in the model parameter The result. is given in the form of sub-optimality gap bound for the function
((0) - g (0)) X²(-): == arg mag g(: A)
(7)
A
and it can be promptly derived from a primal-dual gap type of bound provided in the Appendix. In the bound we also refer to (-) E arg max g(0,-).
Theorem 4.1. Under Assumptions 3.3
9.4
we have that for any 0" E aarging ((0) the solution Og returned
by Algorithm with learning rates nh
n J and consensus step size y 16pt +462 +2p82 Spó satisfies
0²8
Do + DA + GB +8+02 G3
IDAGG
<eVT + LDoGA PVT
LGR p2T
LG e
((.(0.) - -0000 0
+
+0
+
(8)
VT
where DA max, E || - ->-(0)ll Dg = max, E 0 - -Xo())) and c= 826 82
The bound establishes O(IvVT) non-asymplotic optimality gap guaranlee for the output solution. Compared to decentralized stochastic gradient descent (SGD) in the convex scenario, we obtain the same rate (without dependency on the number of workers m) but with dependency on the network topology and compression also in the lower order terms. Moreover, whenever O and X are constrained in convex sets, the diameter of the two can be used to explicitly bound Do and Dx.
4.3 Non-convex Loss Function
We now focus on the case where the relation between the model parameters O and the value of the loss function is non-convex. In this setting, carefully tuning the relation between primal and dual learning rates is key to establishing a convergent recursion. From the centralized two-time scale stochastic gradient descent literature, it known that the primal learning rate тI has to be 1/(16(k + 1)) time smaller than the dual learning rate 77 (Lin et al., 2020a). The above relationship ensures that the objective function changes slowly enough in the dual variable X, and it allows to bound the distance between optimal values of X (0') and the current estimate A' However, in the decentrulized setup, the estimates of 0 and X differ al every node and therefore there exists multiple optimal values of the dual variable; namely, A (0)) for i = 1,...,m. Nonetheless, we find that it is sufficient to control the quantity 8, == ||>( - X |] the distance between X A0'),, the optimal dual variable for the averaged primal estimate, and X the current averaged dual estimate. The following lemma, whose proof can be found in Appendix A.3 allows us to characterize the behaviour of 8.
Lemma 4.2. For ne
DA 16(++))z
and πa
2L the sequence of {8 generated by Algorithm I satísfies
T
56 K
T
3E
7E
Σ
E 8
+
Σ 5K
4D
[=
t=l
7

---

Published in Transactions on Machine Learning Research (12/2022)
T
Sx.² ne T 2
|| + 57
2
40 16 16 + 1)
(9)
mp
where Eg and Ex are the primal and dual consensus errors, and = A||-
Lemma provides us with an inequality that controls the "speed" at which the optimization problem changes from network-level perspective. As such, the expression (9) contains consensus error terms that do not appear in the centralized setup. We find that to establish convergent recursion while at the same time controlling the consensus error terms, the primal learning rate тo has to be 1/(16(k + 1)²) time smaller than the dual 77x (therefore 1/(k + 1) smaller compared to the centralized case). Once this condition is met it is possible to provide a bound on the stationarity of the randomized solution, picked uniformly over time, that matches the one known for the centralized case.
Thcorem 4.3. Under Assumptions 3.3 9.4. the iterates of Algorithm with learning rates no 16(x+1)² 926
and 1 and consensus step size p6 2p32 8p8 satisfy
2LVT
E V (0
AØT VT
1,22200
DALGO cVT
o + RO
G3 C
KG p2T
o
00
+
+0
+0
+
2
mvT
m (10)
where AΦ" [0)) [[(((")) and
026 82
We note that the bound decreases at a rate (IIVVT), except the last variance term which is non-vanishing. Nonetheless, whenever the variance of the stochastic gradient oracle for the primal variable is small or the number of participating devices is large, this term becomes negligible. Otherwise, gradient complexity, each device query the oracle O(1/e)) times every round, average the results and make the stochastic gradient variance (11/e). This procedure makes the bound vanish and leads to a gradient complexity matching the one of [haamma et al. (0222 given for the federated learning scenario.
a cost of increased
Table 2: Final worst-case distribution accuracy attained by AD-GDA and CHOCO-SGD under different
compression schemes and compression ratios.
Quantization
Sparsification
16 bit
8 bit
4 bit
50%
25%
10%
Logistic AD-GDA
59.19
2.05
57.43
1.44
55.75 = 2.09
57.05 0.68
54.02 1.14
51.51 + 2.88
Logistic CHOCO-SGD
30.69
30.06
29.46 = 0.05
30.28 0.60
28.56 0.54
26.39 0.67
F.C. AD-GDA
54.99
48.99
2.30
47.08 2.53
43.65
2.97
38.95
3.21
F.C. CHOCO-SGD
30.83 2.22
28.08 2.50
28.01 = 2.59
29.92 2 2.54
27.11 1 2.96
25.91 + 3.20
5
Experiments
In this section, empirically evaluate AD-GDA capabilities in producing robust predictors. We first compare AD-GDA with CHOCO-SGD and showcase the merits of the distributionally robust procedure across different. learning models, communication network lopologies, and message compression schemes. We then consider larger-scale experimental setups in which we study the effect of the regularization on the worst-case distribution accuracy and compare AD-GDA against Distributionally Robust Foderated Averaging (DRFA) Deng et al. 2021 and Distributionally Robust Decentralized Stochastic Gradient Descent (DR-DSGD) Issaid et al.
2022
8

---

Published in Transactions on Machine Learning Research (12/2022)
107
Quaut.
10/-
Sjars.
bit Quaut. 16 bét Quant.
Spars.
73% Spars.
10P
Lose
32 bit Quant.
Loss
100%5 Sqarr
2D-TORUS
MESH
Loo
10:11
1000
2000
3000
1000
2000
3000
Iteration
Iseration
10-1
1000
(a) Quantization
(b) Sparsification
[seratioo
Figure 3: Convergence plots of AD-GDA for different quantization levels and schemes.
Figure 4: Convergence plot of AD- GDA for different topologies.
5.1 Fashion- MNNIST Classification
We perform our experiments using the Fashion-MNIST data set (Xiao et al. 2017 a popular data set. made images
different clothing items, which is commonly used to test distributionally robust learners (Mohri al., 2019 Dong al., 2021). To introduce data hetcrogeneity, samples are partitioned across the network devices using a class wise split. Namely, using a workstation equipped with GTX 1080 Ti, we simulate network of 10 nodes, each storing data points coming from one of the 10 classes. In this setting, train a logistic regression model and two-layer fully connected neural network with 25 hidden units to investigate both the convex and the non-convex cases. In both cases, we use the SGD optimizer and, to ensure consensus at the end of the optimization process, we consider a geometrically decreasing learning rate 1/6 = r with ratio r = 0.995 and initial value v/g = 1. The metrics that we track are the final worst-node distribution accuracy and the average accuracy over the aggregated data samples on the network estimate 0'.
5.1.1 Effect of Compression
We assess the effect of compression with fixed budget in terms of communication rounds by organizing nodes in ring topology and training the logistic model and the fully connected network for T 2000 iterations. As representative of the unbiased compression operators, consider the b-bit random quantization scheme for {16, 8, 4} bit levels, while for the biased category implement the top-K sparsification scheme saving K = (50%. 25%, 10%} of the original message components. For each compression scheme and compression level, we tune the consensus step size y by performing a grid search. We train the different models for different random placements of the data shards across the devices using the distributionally robust and standard learning paradigms. In Table 2 we report the average worst-case accuracy atlained by the final averaged model @", AD-GDA almost doubles the worst-case accuracy compared the not-robust bascline CHOCO-SGD (Koloskova et al. 2019b). This gain holds for both compression schemes and across different compression levels. For increased compression ratios, the worst-case accuracy degrades; however, for comparable saving in communication bandwidth the unbiased quantization scheme results in superior performance than the biased sparsification compression operator. For a fixed optimization horizon compression degrades performance. Nonetheless, compression allows us to obtain the same accuracy level with fewer transmitted bits. In Figure 3 we report. the convergence plot of AD-GDA under the different compression schemes and ratios. For this experiment we track the worst-node loss of a logistic model trained using fixed learning rate N) 0.1. The convergence plots confirm the sub-linear rate of AD-GDA and highlight the effect of the compression level on the slope of convergence.
5.1.2 Effect of Topology
We now turn to investigate the effect of node connectivity. Sparser communication topologies slow down the consensus process and therefore hamper the convergence of the algorithm. In the previous batch of
TThe Wishion-MNIST data released under the MIT License

---

Published in Transactions on Machine Learning Research (12/2022)
Table 3: Worst-node accuracy attained by AD-GDA and CHOCO-SGD for different network topologies.
Top-10% Sparsification
4-bit Quantization
2D Torus
Mesh
Torus
Mesh
Log. AD-GDA
54.00 + 0.61
54.07 + 0.03
56.94 + 0.38
57.11 = 0.03
Log. CHOCO-SGD
26.82 + 0.41
29.00
0.02
30.82 0.24
30.97 + 0.03
F.C. AD-GDA
44.31 + 2.47
45.21 2.22
50.16 1.85
50.80 + 1.83
F.C. CHOCO-SGD
26.02 2:29
26.38 2.65
28.79 2.22
28.96 + 1.87
experiments, we considered a sparse ring topology, in which each node connected to only two other nodes. Here, we explore two other network configurations with a more favorable spectral gap. The communication topology with each node connected to the other 4 nodes and the mesh case, in which all nodes communicate with each other. For these configurations, we consider the 4-bit quantization and top-10% sparsification compression schemes. In Table 3 report the final worst-case performance for the different network configurations. As expected, network configurations with larger node degrees lead to higher worst-case accuracy owing to the faster convergence. In Figure f we provide the convergence plot of AD-GDA for different communication topologies. particular, we track the worst-node loss versus the number of iterations for the logistic model optimized using fixed learning rate тo = 0.1. The predicted sublinear rate of the AD-GDA is confirmed and it is also possible to appreciate the influence of the spectral gap on the convergence rates.
5.2 Larger Scale Experiments
We now study AD-GDA and compared it with existing distributionally robust algorithms. We consider three larger-scale experimental setups:
larger scale version of the Fashion MNIST classification task Section 5.1 this section, we assume larger network comprising a total of 50 devices with nodes storing samples from only one class.
CIFAR-10 image classification task based on 4-layer convolutional neural networks (CNN) KKizhevsky et al. 2009). We consider a network of 20 network nodes and we introduce data heterogeneity by evenly partitioning the training set and changing the contrast of the images stored on the devices. The pixel value contrast E [0, 255] is modified using the following non-linear transformation
fa(P) clip 255 [1128 (12)))
(11)
where clip/o,25s|()) rounds values to the discrete set [0, 255]. For c <<1 the contrast is reduced while for 1 it is enhanced. We consider two network nodes storing images with reduced contrast (c = 0.5), two storing images with increased contrast (c= 1.5), and the rest of the nodes storing images with the original contrast level (c= 1). This setup can be used to model a camera network (e.g. surveillance network) containing devices deployed under different lighting conditions.
A network of 10 nodes collaborating to train 4-layer CNN to classify microscopy images from the biological data set COOS7 (Lu et al. 2019 Data heterogeneity is consequence of the existence of different instruments used to sample the training data. In particular, we consider two of the collaborating nodes using a different microscope from the rest of the collaborating devices. This setup illustrates the risk of training models based on biological data affected by local confounders - this case, the usage of different sensors.
5.2.1 Effect of Regularization
We first evaluate the effect of the regularization parameter a in the distributionally robust formulation B and study how it affects AD-GDA final performance. According to the two-player game interpretation of
10

---

Published in Transactions on Machine Learning Research (12/2022)
Table 4: Testing accuracy attained by AD-DGA for different regularization values a. For the Fashion-MNIST data set we report the worst and best class accuracy, for the CIFAR-10 data set the accuracy for the different contrast images and for the COOS7 data set the accuracy for the different microscopes. The last column in all tables is the the accuracy attained test data set comprising samples from all local data distributions.
(a) Dashion-MNIST
(b) COOST.
Worst Class
Best. Class
Average
Microscope 1
Microscope: 2
Average
10
52.83 + 1.14
90.63 + 0.18
77 + 0.19
a: 10
66.93 = 0.23
86.54 + 0.06
76.73 + 0.13
59.17 + 1.06
89.77 + 0.60
76.77 = 0.04
a
72.27 = 0.31
81.30 + 0.18
76.77 + 0.22
0.01
58.47 1 0.92
89.56 1 0.52
76.67 1 0.09
0.01
75.00 1 0.24
75.63 1 0.40
75.31 1 0.22
(c) CIFAR-10.
Low Contrast
High Contrast
Original Contrast
Average
10
34.66 + 0.47
40.67 + 1.29
44.28 + 0.84
39.87 = 3.96
0.1
37.30 + 0.73
40.93 + 1.54
43.62 + 0.91
40.61 = 2.59
0.01
39.06 + 0.80
41.13 + 1.14
42.96 + 0.91
41.05 + 1.59
Table 5: Worst-case distribution accuracy attained by AD-GDA, DR-DSGD and DRFA.
Fashion- MNIST
CIFAR-10
COOS7
AD-GDA
58.47 0.92
39.06 + 0.80
75.00 0.24
DREA
56.68 # 1.04
37.20 + 1.16
69.16 0.39
DR-DSGD
50.77 = 0.42
38.00 + 0.25
67.09 0.42
the minimax optimization problem (3] the regularizer r(A) reduces the freedom that an adversary has in choosing the weighting vector to maximize the training loss at every iteration t. As a result, the smaller the value of a, the less constrained is the adversary and the larger will be the emphasis on the worst-performing nodes. This intuition is confirmed by the following experiments in which we consider regularizer of the form (d-=m/n)2 and run AD-GDA for a {10, 1, 0.013. In Table 4 we report the average accuracy n:/n
(A) =; Σ, attained in the three simulation setups. For 10, observe large test accuracy gap between the worst data set, 9% for the CIFAR-10 data set and 19% for the COOS7 data set. This large accuracy mismatch showcases how large regularization parameter values, and standard decentralized optimization schemes (obtained for a == oo), are unable to guarantee uniform performance across parlicipating parties. On the other hand, using smaller regularization parameters, the gap between is effectively reduced: 31% for the Pashion-MNISS less than 2% for CIFAR-10 and less than 1% for COOS7. At the same time, the improved fairness brought by AD-GDA docs not significantly hamper the average performance of the final model as reported in the last column of all the tables.
and best nodes in the network: 37% for the
In Table 5 we compare the AD-GDA worst-node accuracy against the one obtained by DREA and DR-DSGD. In particular, we run AD-GDA with regularization parameter a = 0.01 and without message compression. For DR-DSGD we consider the same network setup and we fix the regularization parameter a = 6, which we find to yield the best performance. Finally, for DRFA, we organize the network nodes according to a star topology and we run the federated optimization using half-user participation and with a number of local iterations equal to 10. Across all experiments, accuracy. Compared to DR-DSGD, we attribute the superiority of AD-GDA to the capability of solving the distributionally robust optimization using any strongly-coneave regularizer, in this case, the chi-squared one. On the other hand, the superiority of DREA can be attributed to the fact that DRFA attains distributional robustness by sampling more frequently nodes with unsatisfactory performance. However, whenever the fraction of these users is small compared to the overall number of devices that join the federated round, DRFA is unable prioritize the nodes with the worst performance since they remain under-tepresent within the group of sampled devices.
find that AD-GDA yields the largest worst-node
11

---

Published in Transactions on Machine Learning Research (12/2022)
5.2.2
Communication Efficiency
0.35
0.7
0.90
0.1
0.8-
Acsuacc
0.25
0.5
AD-CDDA 4 tit Quant
ADD CDD 4 lit QuALt.
AD-CDA 4 lM Quast.
012-
DRIDDOD
0.4
DR-D66D
0.15
CHOCO-SGD bit Quent
....
CHOCOOSGD bit Quant
CHOOOOSGD hie Quart.
DRFA
DRFA
DRFA
0.10
0.3
600
800
1000
500
1000
1630
2000
2500
2002
4000
0000
8300
MR
(a) MNNSS
(b) CIFAR-10
(c) COOS7
Figure 5: Comparison between the proposed algorithm (AD-GDA), Distributionally Robust Federated Averaging (DRFA), Distributionally Robust Decentralized Stochastic Gradient Descent (DR-SGD) and standard decentralized learning (CHOCO-SGD). The algorithms are compared in terms of their communication efficiency and worst node accuracy.
In the following, we compare AD-GDA against CHOCO-SGD and other existing distributionally robust learning schemes; in particular, Distributionally Robust Foderated Averaging (DRFA) (Deng et al. 2021 and Distributionally Robust Decentralized Stochastie Gradient Descent (DR-SGD) (Issaid et al.) 2022 CHOCO- SGD represents standard decentralized learning procedure that employs compressed gossip to attain communication efficiency. DRFA is federated distributionally robust learning scheme with network devices connected according to a star topology and the star center represented by a central aggregator. Communication efficiency is obtained allowing network devices to perform multiple local updates of the primal variable between subsequent synchronization rounds at the central aggregator. We run DRFA allowing devices to perform 10 local gradient steps before sending their local models for the distributionally robust averaging steps and we consider half-user participation at each round. DR-DSGD is decentralized distributionally robust learning scheme based on KL regularizers that do not employ compressed communication. For the decentralized learning schemes, consider a 2D torus topology with every node connected to the other four nodes and use Metropolis mixing matrices. For AD-GDA and CHOCO-SGD, which employ compressed communication, we consider a 4-bit quantization scheme. For AD-GDA we consider a chi-squared regularizer with a = 0.01, while for DR-DSGD we set the KL regularizer parameter to a = as in Issaid et al. (2022). ). All algorithums are run for T 5000 iterations using an SGD optimizer and the same exponentially learning rate schedule v/é "1 with decay r 0.998. In order to make the comparison fair, the initial learning rate no is set differently at every node to ensure that the effective learning rate is equal across different algorithms. In fact, DR-DSGD and AD-GDA descent steps are affected by the dual variable. The batch sizes are the same across all algorithms and are set to (50, 50, 32} for the F-MNIST, CIFARIO and COOS7 experiments, respectively. The algorithms are compared in terms of communication efficiency, namely the capability of producing fair predictor commmnccttng the smallest number of bits. To this end, in Figure 3 we compare the worst-case distribution accuracy against. the number of bits transmitted by the busiest. node in the network. The simulation results are reported over the different simulation scenarios. AD-GDA and CHOCO-SGD employ the same compression scheme and converge within the same communication budget. However, AD-GDA greatly increase the worst node accuracy compared to CHOCO-SGD. This showeases the merits of distributionally robust learning compared to standard learning. Compared to the other distributionally robust algorithms, AD-GDA atlains the largest worst-case accuracy by transmilling only fraction of bits. In particular, for the Mashion-MNIS' setup, AD-GDA is 4x and 8x more communication-ffiiiene compared to DRFA and DR-DSGD respoctively. For the CIFAR-10 data sot, AD-GDA reduces by 3x and 5x the number of bits necessary to attain the same final worst-node accuracy of DRFA and DR-DSGD respectively. Finally, in the COOS7 case, AD-GDA is 3x more efficient than DRFA and 10x more efficient than DR-DSGD.
12

---

Published in Transactions on Machine Learning Research (12/2022)
6 Conclusion
We provided a provably convergent decentralized single-loop gradient descent/ascent algorithm to solve the distributionally robust optimization problem over a network of collaborating nodes with heterogeneous local data distributions. Differently from previously proposed solutions, which are either limited to the federated scenario with a central coordinator or to specific regularizers, our algorithm directly tackles the underlying manner. Experiments showed
minimax optimization problem in decentralized and communication-effene that the proposed solution produces distributionally robust predictors and it attains superior communication efficicncy compared to the previously proposed algorithms. A combination of the compressed communication and multiple local updates, combined with acceleration techniques, represents the natural extension of the algorithm to further improve its efficiency.
Acknowledgments
The work of M. Zecchin is funded by the Marie Curie action WINDMILL (Grant agrecment No. 813999). The work of M. Kountouris has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 101003431). The work of David Gesbert was partially supported by the 31A interdisciplinary project ANR-19-P3LA-OO funded from the French National Research Agency (ANR)"
References
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. arXiv preprint arxiv: NKw:1704.0502,, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiteee sgd via gradient quantization and encoding. Advances in Newral Information Processing Systems, 30: 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. arXiv preprint rrXic:1809.10505 2018.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Azizzadenesheli, and Animashrec Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560 569. PMLR, 2018
Jianshu Chen and Ali H Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. JEEE Transactions on Signal Processing, 60(8):4280-43000 2012.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. arXiv preprint arXix:2102. 12660, 2021.
John Duchi and Hongsook Namkoong. Learning models with uniform performance via distributionally robust optimization. arXiv preprint XrXio:1810. 08750, 2018.
John C Duchi, Alckh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3) 0009266666600 2011.
John C Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally robust losses against mixture covariate shifts. Under review, 2019.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
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.
13

---

Published in Transactions on Machine Learning Research (12/2022)
lan J Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley Sherjil Ozair, Aaron Courville, and Yoshua. Bengio. Generative adversarial networks. arXiv preprint arXie:1406 406.6666.66666 2014.
Zhaolin Hu and L Jeff Hong, Kullback-leibbe divergence constrained distributionally robust optimization. Available at Optimization Online, 2013.
Chaouki Ben Issaid, Anis Elgabli, and Mehdi Bennis. DR-DSGD: distributionally robust decentralized
learning algorithm over graphs. Transactions on Machine Learning Research, 2022. URL https://
openreview. http://ww..e/ttoor///ddaaaoaaaaa
Ruiwei Jiang and Yongpei Guan. Data-driven chance constrained stochastic program. Mathematical Programming, 158(1):2 2016.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXto:1977.098: 2019a.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp- 3478 3487. PMLR, 2019b.
Alec Koppel, Felicia Y Jakubiec, and Alejandro Ribeiro. A saddle point algorithm for networked online convex optimization. IEEE Transactions Signal Processing, 63(19):51499 554-55144,9 2015.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Shihui Li, Yi Wn, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4213 4220, 2019.
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. Xiv preprint orxiv:1706 100.009006 2017.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pp. 6083-6093. PMLR, 2020a.
Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael Jordan. Finite-time last-iterate conver- gence for multi-agent learning in games. In International Conference on Machine Learning, pp. 6161 6171
PMLR, 2020b.
Qing Ling, Zaiwen Wen, and Wolao Yin. Decentralized jointly sparse optimization by reweighted b minimization. IEFE Transactions on Signal Processing, (5)5:1116-11170, 2012.
Mingrui Liu, Wei Zhang, Youssef Mroueh, Xiaodong Cui, Jerret Ross, Tianbao Yang, and Payel Das. A docentralizod parallel algorithm for training generative adversarial nets. arXiv preprint arXiv:1910. 12999, 2019a.
Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil, Zebang Shen, and Nenggan Zheng. A decentralized proximal point-type method for saddle point problems. arXiv preprint ar 1910: 14380, 2019b.
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien, Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Newral Information Processing Systems, 34:19095-19108, 2021.
Alex X Lu, Amy X Lu, Wicbke Schormann, Marzych Ghassemi, David W Andrews, and Alan M Moses. The cells out of sample (coos) dataset and benchmarks for measuring out-of-sample generalization of image classifiers. Xrxiv preprint ar S5l::1900072884 2019.
14

---

Published in Transactions on Machine Learning Research (12/2022)
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint
2017.
David Mateos- Ninez and Jorge Cortés. Distributed subgradient methods for saddle-point problems. In 2015 54th TEEE Conference Decision and Control (CDC), pp- 6462-5467. TEFE, 2015.
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.
Mchryar Mohri, Gary Sivck, and Ananda Theertha Suresh. Agnostic federated lcarning. In International Conference on Machine Learning, pp. 4615 4625. PMLR, 2019.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with Edivergences. In NIPS, volume 29, pp. 2208 2216, 2016.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Trunsactions Aulomalic Control, 54(1):48 61, 2009.
Reza Olfati-Saber, Alex Fax, and Richard M Murray, Consensus and cooperation in networked multi-agent systems. Proceedings of the IEFF, (1)21: 233, 2007.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In International Conference on Machine Learning, pp. 2817-2826. PMLR, 2017.
Joaquin Quiñonero- Caaddeer-CCandel, Masashi Sugiyama, Neil D Lawrence, and Anton Schwaighofer. Dataset shift én machine learning. Mit Press, 2009.
Michael Rabbat. Multi-agent mirror descent for decentralized stochastic optimization. In 2015 IEEE 6th International Workshop on Computational Aduances in Multi-Sensor Adaptive Processing (CAMSAP), pp. 517-520. IEEE, 2015.
Herbert E Scarf. A min-max solution of an inventory problem. Technical report, RAND CORP SANTA MONICA CALIF, 1957.
Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. In 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 850-857. IEEE, 2014.
Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod K Varshney. Federated minimax optimization:
Improved convergence analyses and algorithms. arXiv preprint arXiv:2203.0440 04850, 2022.
Aman Sinha, Hongseok Namkoong, Riecardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training, arXiv preprint 1rXi::1110.10511 2017.
Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXii:1805.000 2018.
Sebastian U Stich, Saan-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. arXiv preprinl wrXiu:1809.0755 07099, 2018.
Toannis Tsaknakis, Mingyi Hong, and Sijia Liu. Decentralized min-max optimization: Formulations, algorithms and applications in network poisoning attack. In ICASSP 2020-2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5755 5759. IEEE, 2020.
John Tsitsiklis, Dimitri Bertsckas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on aulomatic control, 31(9):803 812, 1986.
John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
Ermin Wei and Asuman Ozdaglar. Distributed alternating direction method of multipliers. In 2012 IEEE 51st IEFE Conference on Decision and Control (CDC), pp. 5445 5450. IEFE, 2012.
15

---

Published in Transactions on Machine Learning Research (12/2022)
David Wozabal. A framework for optimization under ambiguity. Annals of Operations Research, 193(1): 21 21-47, 2012.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arxiv preprint 1rXiv:1708.071 708.07747, 2017.
Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learning: properties. IEEE Transactions on Knowledge and Data Engineering,
Regrets and intrinsic 25(11)22483 2493, 2012.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-599 5693-5700, 2019.
A Appendix
A.1 Useful inequalities
This section contains collection of ancillary results that are useful for the subsequent proofs. Proposition A.1. differentiable and T-smooth function (ax) satisfies
L || x'1l
(12)
Purthermore, if f(x) is conver
I. 2 1ly x||
f(v) ( f(x) + (Vf(z),
y - x)
(13)
and if xx is a minimizer
[V(x) S ((x)) - s(x)))
(14)
2L
Otherwise, (x) concave
L 2 lly x||
f(y) 2 f(z) (Vf(z). y-))
(15)
and if x² is marimizer
2L IVf(() f(x²)
(16)
Proposition A.2. differentiable and p-strongly conver function f(x) satisfies
f(y) 2 f(x) (VI(x), x))
1 l1y z0l2
(17)
and differentiable and p-strongly concave function g(æ)) sulisfies
# 11 x
g(v) g(x) + (Vg(x), x)
(18)
2
Proposition A.3. Given two vectors a. b Rdd for we have
2 b) 3 ||||| 2 + 3 ||b1|
(19)
and
|la b1| < (1 + 1-1 ||a|| + (1 B) [bb]2
(20)
16

---

Published in Transactions on Machine Learning Research (12/2022)
Proposition A.4. Given two matrices A R B Rix,, we have
||B|| I |||||
|B12
(21)
where ||-|| denotes the Frobenius norm.
Proposition A.5. Given set of vectors {a, [a:)== we have
a;
11 aall
(22)
Consensus incqualities
streamline the notation we define (g 11) = gg X, E and introduce the following matrices
O 0i...., 0f E Rdxm
6' 0i..... ..... 0% E Rddm. A {
X
&R
(23)
VoG(O', = [o9i (1),).i. Xi)...., Vogm @ {in)
E Rdxm
(24)
VAG(O A²) = V (0) Xi),... Vxgm Nma E R
(25)
and for matrix X define X = X 11
m
The local update rule of Algorithm I can be rewritten as
@++ O 1/0 VoG
(26)
A PA (A' nx VAG(O"))))
(27)
where PA is applied column-wise. The compressed gossip algorithm CHOCO-GOSSIP (Koloskova et al.
2019b) used to share model parameters preserves averages and satisfies the following recursive inequality with 2
82
11 11 - +11l:=++1++00000000 - s c) - 10 +100+= -
E
(28)
The uncompressed gossip scheme used to communicate satisfics
< - p)B | | A 1
(29)
Lemma A.6. (Consensus inequality for compressed commmumicatinn (Koloskova et al. 2019a)) For fired
028
> 0 and 7 +45 8pb the iterates of Algorithm satisfy
|
mG
E
[ = E Σ
0
0e
< 12ne
(30)
Lemma A.7. (Consensus Inequality for uncompressed communication JA > O the ilerales of Algorithm
Koloskova et al.
2019b For fixed
salisfy
m
mG2
E
EE
X
X
4n
(31)
Lemma A.6 and A.7 apply the primal and dual iterates obtained of Algorithm and they are obtained
from Lemma A.2 of Koloskova et al. 2019b).
17

---

Published in Transactions on Machine Learning Research (12/2022)
A.2 Proof of Theorem 4.1 Convex case
Define
((:) max AEA"-1
g(, A);
(32)
under assumptions 3.3 3.4 and the local objective functions (fi(0)) are convex, Theorem 4.1 guarantees that the output solution (0o, Ao) satisfies
LG x²
LG
DxLGa + DoLGr
E
((.))
min (()) oEe
+3
+
V12
T
VT
P
Dg + Dx
G
GG
(33)
2
2
The proof starts from the following decomposition of the sub-optimality gap
E
max g(0, A) min max g A)
max g A)
max min g(0, A))
(34)
A
A
max (0.. A) min g Xa)) A
(35)
max ( A) - -g(0, 20)) 2,0
(36)
T-1
max 7,8
Σ
g X) - -00, X'))
(37)
T
<
max
Σ
g A) -6(0, x2)
T
t=
E
max
g(0' X9 2(0, x2)
(38)
Thanks to Lemmas
A.8 and
A.9
proved below, the two summands can be bounded to obtain
Do
D2IGG
T.G 12n
E
(
min (0)) 8E0
G2 V48
Tn
c
c²
Dx
7
G2 +
DoLGx 8
+ 4n
LG P
(39)
2 T
Setting '/0 V the final result is obtained.
Lemma A.8. For T > O and any O, the sequence (0', X X generated by Algoritium satisfies
E
T-1
Σ
g X 2(0,X9)
<
Do
+ To G + 12n
T.G
+ 2nd
Do
(40)
2npT
2
c
where Dg max;=o... 0 A||-
Proof: From the update rule of the primal variable and the assumptions 3.4 on the stochastic gradient we have, that for any 0
Eg |0+1- 0
= Eg:
0' - 0
V Vog.
00' Xt)
(41)
==
0
0
2
Tle
0
0: Eg (00 + Eg
7 m
Vog 0 X()
(42)
m
18

---

Published in Transactions on Machine Learning Research (12/2022)
$100 0 2 -2 116 m
0 0:
Vogi (0); X;)) +n
(43)
Denoting with D |10:
0|| we have that for T2 the following holds
m
m
T2 = -2 7/
Σ 00'
0; Vog. (0 x)) +
Σ 0 0; (egi(0;, Vo9i(0;,
(44)
m
1=1
S 2 7/0 m
00 0 Vogi (0' x1) + Ly
(45)
m i=1
m
3
110
(0' 0: (0;, x²)) + (0)- 0: (0 x1)) + DD
(46)
m i=1
m
80
110
m
9:(0", (1) -0)00000)')
L 00 e.11²) + 2n
3
(47)
m
2
m
710
m
(9.(0', X gi X() +
2n I = 2no LD'
Ex
(48)
m
m
m
Plugging it back in
43
rearranging the terms and taking the expectation over the previous iterate we get
E [o(00 X9 -000
E
9: (: X²
(1)
(49)
17
E
0
012
0
G
EE
L LE
+
[D]]
E E
(50)
21T8
m
m
Telescoping from == 0 to t = T - and plugging the consensus inequalities
30
and
31
we get
R Σ g X9 (0,
<
Do
2 G
12
LG c²
2m
DoLG>
(51)
T
2n T
P
where Dg max T [BD max E O||.
Lemma A.9. For T > O and any X, the sequence (Ø) A. generated by Algorithm i satisfies
E T
Σ
0 A) g(0'
Dx
MA G
AA + 417
LG3
+ V11210
DaLGo
(52)
21pA T
1²
where D max T E X All-
Proof The proof follows similarly as in Lemma (A.)
2
Ee: ||(41 212² -Be:
A X'
xg: (0', x;)
(53)
==1
2
= =||²² ~/12
7
1z ( (;)) + EE
?
xg 0 x
(54)
m
m
i=1
172
-BI
2/1
2
7
X VA (D) &.
(55)
m
Ts
19

---

Published in Transactions on Machine Learning Research (12/2022)
Denoting with D = ||X = we have that for T3 the following holds
m
T3
-2 A
Σ (X (O )
X Vagi(0) -
VADi(0'
(56)
m
7
(() X; (0' (()1 + L
E
(57)
m
m
2
(A 1/: ( 20) + (2 - X V (()1 2MLDDX
(58)
16
-2 A
9.(0', A) 9: X)
I.
| x(Ii))
2TALDS
3
(59)
2
- 7
(0' A) 90 (\) 2 + 2np LDD
3
(60)
m
Plugging it back in
55
rearranging the terms and laking the expectation over the previous iterate we get
1 E
B [(g(O'A)) A) g(0 X1]
Σ 9 A) 3,(00,xy
(61)
m
E X A|R E
2112
71 G3 +
LE
[
[
E
622
2nd
2
m
m
Telescoping from t = 0 to t = T and plugging the consensus inequalities
30 and
31
we get
E
g >) g(0 x1
S
Dx
+ 1A
G
4n
L.G, p²
c vinn
DALGo
(63)
2T2T
2
where DA = max
E = max E X -ll-
A.3 Proof of Theorem 4.3
Non-convex case
In the case of non-convex functions (fimm Theorem the randomized solution of Algorithm
4.3 provides the following e-stationarity guarantee on
T
2L VT
45Lx
V 0
<
256 (E[ E(((0"))
+
2
Go
o
45k0
G
KG
oh
5D, L.
+
+
+
171
+
(64)
VT
2m
4m
T
4
p
m
The proof is inspired from recent results in Lin et al. below, provides descent incquality of the type
2020a
Specifically, Lemma A.10
stated and proved
E[ <E(
LL
110
E (V
m
+ 1,2 1/8 21
[|
+
2
2F(61
(65)
m
m
Setting 7/ inequalities
ni 16(++17
and 7 z
1 expression
can be simplified thanks to the following chain of 65
27.
7ne
1
1 + 21 <
9re 16
<
2) S no 2
(66)
16
2
20

---

Published in Transactions on Machine Learning Research (12/2022)
Telescoping the simplified expression from t 1 to T obtain
[ + T NaxLo
TT
T
E [
((
m
16
9rfe
E BE
2 2
Mhg 1
1.2
E
(67)
16
m
m
8
where 6x := (0') - x represents the squared distance between the optimal value of the dual variable for the current averaged network belief and the current averaged value of the dual variable.
Lemma A.11 reported below, provides bound on E/= 04 that plugged in 67 yields
45LK200
45x n
7 E
E [[)(0") [E) + 170
+ 110
112
16
nok
4 2
450
+ Tna
m
4m
2 16
+ 1 979
T
B|
2 x
30<BE=
70
4)
16
m
m
m
7
+ 1
40xD)-11 1-1
(68)
16
Moreover, the relation between the two step-sizes established above ensures that
45k 1
7
(69)
16
4
4 and therefore rearranging terms, dividing by The and recalling that K 2 1
V (0'
|1
4
(E 1 (0))
- E( )1)
25
noT
27
MonLooz
45KLMA 2
450
+
4
+
m
4m
2. 162m
9L2
T
72E
31<EE;
72E
(70)
4T
m
m
Exploiting consensus inequalities and obtain
(30),
33 and the fact that K 2 1 and T1 16(x+1) S 1/2L we can simplify
T
64(n + 1)2
45Tx260
101
-E
+
T
nxT
2TTx
Lo 2
45kLo²
450
+ 2
8
+ 17
+
2m
162m
9
Go
2 RG
2 RG?
+ 2
40nD 1-1 VI2no
372
+
2887
(71)
4T
1=1
Simplifying and defining Dx = max:=u.....r DĄ
T
64(k + +12
45L
V
(
(E[O()")) -E(00")) 27
T
Tx
21

---

Published in Transactions on Machine Learning Research (12/2022)
Lo
45xLo
4503
+2
a
+ +M
+
m
2m
16
Go
G3
KG
+ L²
[10
+
+11 c
+
684M1
?
(72)
Grouping
1
256 (E|+( - E[((0"))) + 45Lx200 09
B
V
1/7
110D Ga + Loi
45KLO²
L2
LRRG2
og
)
+ 11
684
(73)
m
2m
c²
p²
m
Sctting 77x
we get
2LVT
E
V 0 |||]
<
2L VT
256 -[(000))-(((0"))) B(O(0'))
45Lx200
2
Go
oه
45k0
G2
NG
oh
5D
171
(74)
VT
c
2m
4m
T
4
p²
m
Lemma A.10. For each 1 t= 1,..., T the iterales generaled by Algorithm 7
salisfies
[[)( <E(
n
(T1
21
E
[ (
m
+ 2 (2 + 2
[|
+
2
+ 2
(75)
m
m
Proof: From the 2rL-smoothness of (--) (Lemmma 4.3 of Lin et al. 2020a and the update rule we have:
B [0(0') < + Eg -1 1 ) 0' σ (-1))]
+ KL -1 1 0
|
(76)
< 1) - .ll ( V V (
Ege (o [0
m
nL
m
+ mn EE E1
V oggi 0 .1(-1)
(77)
1
< + ( V
(0
T=Ta
nhL m
m
7/0
0
Eg
Σ Vogi 10!-1111-11 111-11)
(78)
Tb
We now turn bounding term T₃
V 1
T4 = no (V
Vogi ( (Q--1,(--1)
(79)
Vogi ( (66-..1111 1 1'
Vi 2
|0 +
V
(80)
< 7/0
|0')011)
V V (''((''11) 11-00000111 - 1 1,x--1)
(81)
2
22

---

Published in Transactions on Machine Learning Research (12/2022)
m L
L m
7e
||
+
0
0
0:-11
|X- X 1|²
(82)
2
m
m
i=1
V70
|v
+ m
1
2
2T. m
Σ (0
1) X 11
(83)
2
m
m
(84)
and from stochastic gradient assumptions 3.4
can bound T3 as follows
m
T3 -g
(0 (1-1))
(85)
= -
(0 10:-00000000000 1,,,1111 Vogi (f
( xx
(86)
1
2 + mo
Σ
Vogi 1,-00:1111111 1 Veg 1-1 100000'0110000111111 (x'(0(-1))
2 m (
(87)
i=1
S mo 2
12
+2L2m Σ
0 0 0:-11| + 2222 m
m
12-00' 1 - 11 1|- + 2m3² 2 V (1'0
(88)
i=1
<mog +2L'
mL + 4
(0-00 X 11 22m² (0 ||?
(89)
=61
Recombining, grouping, and taking the expectation over the previous iterates we get the desired result.
Lemma A.11. The sequence of ( generated by Algorithm 1
satisfies
Σ
E
50
Σ
5K
4Dx11
V
E
1 m
3E
[=b-]
7E
m
m
t=1
T
8x ne
+ ||
57
22 mu
40 162m + 1)
(90)
R2
1=1
where DJ-1 X 1-1 |||
Proof: From 20 for b >>> 0, we have
1 b
Ee . 1 v 1+
Eg
(0(00-1)) X + (1 (1+b) 1)
|x' X \'1001))1
(91)
T=
T7
Bounding To similarly
To -
11- xx11
(92)
-Be--1
('(0--1) -
77A
(0 11 -1 + V (0.- (.(-11)
(93)
m
V (0 .11-1111 1
Ro
< X 1 x--1
7
(94)
2
2 +
7
V
A ( ( 1.2--11
Te.1
23

---

Published in Transactions on Machine Learning Research (12/2022)
-0 - X 7/
V Vigi (0--)1111)
(95)
m
m
16.2
Estimating T
m
To,1 =2nx
(0 'x + (0 ------ - VA (100-111100--11 (0((0-11))
(96)
x 277
Vxgi -,--,,,,-11 - Vigi 11
i=1
m
+ 2
Ag 00-10'1,0 11 - Vagi 10'1000'000001
(97)
Y!1 i=1
12 2 m
Σ 1,2
12-
x-11 | 1,2 10:
0-11
2
4 L
m
(0 (x'(0'=1)) g:(0' xx(11) }]
m
m
(98)
2z
2
L m m
E
-
>
(0' -x'(0--1)) g.(0'-1, (0111
(99)
m
m
Estimating Te.2
To = - 2 m
(1-(0--1) - X'1, 0 11,
(100)
= 2 7
(X'(0-1)) 1) - X (0 , + (0 (1--11))
(101)
m
m
TA
(X- 1) X ; VA (0-11 .
m
i=1
(1 ))=; (A
Vagi (0'-1,2;-1) 21
(102)
m
(1'(0'-1) - x VAO 1111 + 24 T.DD v تي
-2 M
(103)
7
(A' 1100--1-10 X VAO (0'110 ;;-)) + 1--1- Vagi (0' 1011,,11111
i=1
2m
=
(104)
m
19
(g:(0* 1 ( - ( (00'-11)) + 2
m
m
7
11
(0- 1 + - |ス 1 )
(105)
m
2
(0: (x - 1 1- 11) + 27 2 1D1 V /
7
11
- 2
- L+
1 - xد 11²
(106)
m
4
2
i=1
24

---

Published in Transactions on Machine Learning Research (12/2022)
m Di 0 1000-)1))))) - (0" (11-1)
2 10(0011----- x--11²- -2 7A -
m
2L - _ + 2D 11
-/-1
(107)
where the last inoquality follows from choosing VIA S 1/L)... Substituting the expressions we get
To = (1-AAA) 2 |
1-11
-
3 + D
(108)
m
m
m
m
Being (-) is k-smooth (Temma 4.3 Lin et al.
2020a
we can bound T7 as follows
T7 = -1 (x')
10
(109)
<x² E g1
110
001 |
(110)
K 10
E Egr-1
V eogi 0 (0--1 ..--111111 1
(111)
2
2 1g
mag
V oogi (0 (0:- -1-1) + mV
(112)
2
K x
m + 2 | 10 2L m
0 - 11- + m Σ (0-1) -li''-- (113)
m
1=1
2 %
mo + 2m² V 1)1²= + +222 m= + 21 m
(²((0-1)- - x + X x--11² (114)
m2
i=l
+ + 1| 2 4
20
KT
08
4L2 |A'(0-1)) -x-11²)
(115)
m
m
m
2 8
4L'3-11 + +
=
2
- 2 | 1² +
(116)
m
Recombining and grouping we get
1 + )) (1 - Wm
84-1 + 1+ 1
| =/-
8% 5
+ +411 + b)x2 112 1.2
5) 1 MALD
V
2
m
(1+ + b)
E/1
+ (1+ b) 1) O5 = (1 + b) r2 208 0g
Lnj + 2((1 + +b))22222
m
1+
1
3LTл + 4(1 + b)x no
_
+ 2x 2x (1 + b) / 1 00- 11?
(117)
b)
m
Setting 6 2 2 -1) 1)
> we get the following inequalities
11 + 1) (1
< (1
7x11
(118)
2
4
(1+ b) < Ma11
(119)
1
1 + +,
< 2
(120)
(121)
that allows to simplify 117) as follows
57 S (1- AA
16x² 2
5 +
+
Tmmx +
4
m
7AHk
m
25

---

Published in Transactions on Machine Learning Research (12/2022)
+ 2 1
4m n32
16
=x-
8k21Ø
+
6LMT +
|
(122)
MAM
Fixing
7/A 16
we get that
16
V ==
1
(123)
Taking the expectation over the current iterate and applying recursively the inequality we obtain
Eg-r1
Sv' 8 +
Σ
T2 8x
B
--
220 m7
4x An²ng qa
o
MAH
TA
m
1=0
f-1
+
--1
Ama
0=0
(-1
+
(124)
0
Summing from t= 1 to T and from
123
gel
E gi [0%]
58
+
5
8x 2
E Eee-1
V V 10)))))))
57
2 2
4x² oo
7A
7x/4
axll1
m
Ma m
5
1
+
4n2LD
V
Eg $1
7A
m
T
5
7 Eg
(125)
7AA
m
m
26


Reviews:
[{"review_id": "Os2aAFCEEF", "reviewer": "Reviewer_2qTW", "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 considered problem might be of interest to the community working on distributed optimization as it formulates a clear problem and suggests a solution.\n2. The theory covers both convex and nonconvex problems and the claimed rates look reasonable.\n3. The experiments are done with multiple seeds and confidence intervals are reported. They are quite comprehensive and seem to support the theory.\n\n\n## Weaknesses  \n1. One of the paper's contributions is to extend the decentralized distributionally robust optimization beyond Kullback-Leibler to arbitrary regularizers $r$, but it is not explained why we need any other regularizer. As far as I know, it is standard to consider KL regularization.\n2. Assumption 3.4 states that the gradients remain bounded, but as far as I can see, this is not possible with KL regularization. In particular, when of $\\lambda_i$ approaches 0, the gradient would explode.\n3. Overall, the paper feels like a combination of two existing techniques, without strong practical motivation. It is not very clear where exactly is the novelty, all ideas seem to come from prior work.\n4. The writing suffers from a lot of small issues.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "## Summary of the paper\nThis paper studies the problem of distributionally robust optimization on graph networks with arbitrary connected topologies. Compared to other recent papers on the topic, it considers arbitrary regularizer, such as KL divergence, and covers both convex and non-convex functions. The authors propose an algorithm called AG-GDA that was derived as a method for the minmax problem arising in distributionally robust optimization. The theory is supported by experiments with different topologies, objectives and with different quantization.\n\n## Summary of the review\nThe motivation for this work is a little bit unclear to me. Moreover, some of the assumptions seem to contradict specific choices of functions (KL divergence). On top of that, there do not seem to be novel ideas in this paper. The numerical evaluation, on the other hand, seems quite nice, even though it is mostly meant to support the theory.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Questions\n1. What is exactly novel in terms of ideas in this paper?\n2. Why the assumptions on bounded gradient do not contradict choosing $r$ as the KL divergence?\n3. What would be an interesting example of $r$ that is not KL?\n\n## Writing issues\nSome notation feels unnecesseary, for instance, it is introduced for some reason that $f_i$ is given by $\\mathbb{E}_{\\mathbb{R}z\\sim P_i}\\ell(\\theta, \\mathbb{R}z)$, but as far as I can see, $\\ell$ is not used anywhere  \nAssumption 3.1 should include the definition of eigengap, I do not see where it is explained  \nI think in Assumption 3.2, delta should from the range $(0, 1]$ rather than $[0, 1]$  \n\"gradient based algorithm\" ---> \"gradient-based algorithm\"  \nIn Algorithm 1, the Gossip step uses $s_i^{t+1}$, which is defined only a few lines later, I think it should be $s_i^t$  \nThe projection step of Algorithm 1 is not explained anywhere\nThe text in Theorem 4.3 states that the output point $\\theta_o$ satisfies a certain property, but the mathematical bound is for the average iterates $\\overline \\theta^{t-1}$  \nPage 11, \"CHOCOSGD represent\" ---> \"CHOCOSGD represents\"  \nIn table, please highlight the best number in every column  \nIt is confusing that Lemma A.6 and A.7 refer to the works of Koloskova et al. Their papers do not consider the iterates of Algorithm 1, for which the statements are claimed in Lemma A.6 and A.7. So please make these Lemams more specific and explain which results of Koloskova et al. you refer to  \nSome equations, for instance (27), (31), and (40), lack punctuation", "broader_impact_concerns": "This work is mostly theoretical, so there are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "MNUID3bxMg", "reviewer": "Reviewer_87oT", "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\n* The authors study an interesting problem setup of importance to the community.\n* The proposed technique is intuitive and easy to implement.\n\n**Weaknesses**\n\n* The theoretical contributions appear to be concatenations of existing techniques (analysis of decentralized SGD with dual variable updates, Choco-SGD). As such this is fine since the proofs seem correct, but they are presented without intuition. The authors could perhaps clarify what parts were known before, the technical difficulties in bringing them together, and any insights provided over and above existing results.\n* It is unclear why theory results are provided for convex loss functions when none of the experiments involve convexity. (This might be a broader criticism applicable to papers in this area.)\n* It is unclear why results are reported only on small-ish datasets like FashionMNIST and CIFAR-10. (This might be a broader criticism applicable to papers in this area.) ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "**Summary**\n\nThe authors study the problem of distributionally-robust learning in the fully decentralized setting (i.e., in the absence of a network-wide coordinator), and propose a communication-efficient algorithm to solve this problem.\n\nSolutions to this specific problem have been studied previously in the literature. The key difference in the authors' approach is an added emphasis on reducing the number of bits exchanged between nodes in the network. To achieve this, the authors use the Choco-SGD quantization technique introduced in Koloskova et al  (2019) for compressed communication between neighbors. Another difference between previous works in this area is the use of dual variable updates (as opposed to KL regularization) to address the minimax nature of the optimization problem.\n\nThe authors support their new algorithm (called agnostic decentralized gradient descent-ascent, or AD-GDA) with theoretical analysis under certain assumptions, and empirical demonstrations on FashionMNIST, CIFAR-10, and a microscopy image dataset. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Critical**\n\n* Consider rewriting the theory sections, drawing a sharper line between previously known results and new techniques/insights provided by the authors.\n* It may be helpful to draw a sharper line between two closely related papers (DR-DSGD, DRFA) and how the proposed approach improves upon these works. In particular, DRFA also addresses distributional robustness as well as communication efficiency. Perhaps a table in the Introduction comparing the 3 methods in theory, and what gap is filled by AD-GDA that DRFA did not fill before, would be helpful.\n* In Tables 1 and 2, the comparisons to Choco-SGD is fine but this is obviously not designed for robustness; it may be also helpful to report numbers for DR-DSGD and DRFA.\n\n**Other comments**\n\n* Is there any dependence on the number of workers ($m$) in Eq 11? Might be helpful to clarify.\n\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gG9GHhTQjj", "reviewer": "Reviewer_Btiw", "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* Overall the paper is well-written.\n* The theoretical rates match what one would expect for the non DRO setting order-wise, and they also match the upper bounds for a federated DRO method, Local SGDA, the client-server setting.\n* Experiments illustrate the promise of the approach for applications.\n\n## Weaknesses\n* In terms of theory, the paper appears to make heavy use of existing well-known techniques, like prior analysis of SGDA and analyses incorporating error compensation in the context of compressed decentralized optimization.\n* Although the experiments illustrate the usefulness of AD-GDA, they don't directly validate the theory, in the sense that there aren't direct comparisons to the way that the theory predicts rates should depend on key parameters like the level of compression or topology. Presently the comparison is mainly qualitative.\n* The experiments section doesn't describe how different methods, including the baseline, were tuned.\n* The literature review could be expanded to include additional related work on decentralized min-max optimization.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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, AD-GDA, for decentralized distributionally robust learning. The method incorporates update compression (e.g., via quantization or sparsification) to reduce communication overhead. Theoretical convergence rates are derived for the non-convex setting, and experiments also illustrate the benefits of the proposed approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It would be useful to more clearly explain what are the main challenges, if any, in deriving the theoretical results, or if any new analysis techniques are introduced in this work. (I realize this is not a requirement for publication in TMLR, just asking that the paper more clearly spell out if there is any contribution on this front.)\n2. Consider better aligning the experiments with the theory by comparing empirical performance with that predicted by the theory for the different scenarios used in the paper.\n3. Describe in greater detail how the baselines and AD-GDA were tuned in the experiments, both to enable a reader to reproduce your results and to reassure the reader that the comparison being made is fair.\n4. Please expand the discussion of related work to include other papers on decentralized games and min-max optimization. The DRO problem is a particular instance of a min-max problem. For example, the paper [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://proceedings.neurips.cc/paper/2021/hash/9f96f36b7aae3b1ff847c26ac94c604e-Abstract.html) analyzes a similar method, but without communication compression. Is there particular problem structure that AD-GDA exploits to obtain new convergence guarantees, or is the main difference the inclusion of compression and error feedback?", "broader_impact_concerns": "None noted", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes and analyzes a new method, AD-GDA, for decentralized distributionally robust learning. The main contribution over existing work is to simultaneously enable the fully decentralized setting along with general regularizers beyong KL divergence. The reviewers generally found the paper well written and the claims made in the paper well-supported by the evidence provided in the paper. Some reviewers had some concerns regarding the assumptions and the motivation for extending the previous work beyond KL which were addressed by the authors in the revisions. Overall all the reviewers recommended an accept or a leaning accept with novelty being the only concern area. 
Decision: Accept (poster)