We study group distributionally robust optimization (GDRO) over decentralized networks, where workers collaborate to learn robust models by minimizing the maximum local risk. Existing methods optimize only dual-regularized surrogates and establish guarantees for a globally averaged model that is not available to workers. In this paper, we directly optimize the original GDRO objective and establish guarantees for local models in semi-decentralized (SemiDec) and fully decentralized (Dec) settings. A key difficulty is that applying the primal-dual decomposition from centralized GDRO yields worker-dependent losses whose evaluation requires unavailable cross-worker information. To address this challenge, we develop a novel error decomposition that recasts decentralized GDRO as (i) a decentralized online convex optimization (D-OCO) problem and a prediction-with-expert-advice problem in SemiDec, and as (ii) two coupled D-OCO problems in Dec, with discrepancy terms capturing inconsistencies among local decisions. By isolating consensus errors in analysis, we develop modular frameworks that support different consensus routines. We then establish the *first* per-worker convergence guarantees for optimizing the original GDRO objective over decentralized networks. Instantiations with accelerated gossip and Choco-gossip achieve an O((logm)/T) convergence rate over T update rounds, while experiments demonstrate improved worst-worker performance over baselines.
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.Reviewer_z4BwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary
The paper studies unregularized group distributionally robust optimization over semi-decentralized and fully decentralized networks. It decomposes each worker’s optimization error into online regret and disagreement terms, and develops FTRL frameworks with accelerated or compressed gossip. The resulting guarantees apply to each worker’s time-averaged local model.
Critical strengths
The guarantees concern the original GDRO objective and locally available models. This makes the results more relevant to decentralized deployment than guarantees for a globally averaged model.
The decomposition separates optimization and consensus errors, allowing different communication routines within the same framework.
Critical weaknesses
The experimental implementation differs from the analyzed algorithm. Appendix B.1 uses clipped cross-entropy for dual updates but unclipped cross-entropy for primal updates. These updates generally do not correspond to the same GDRO objective, weakening the experimental support for the paper’s central claim.
Comparisons are reported against update rounds despite different communication costs. The proposed methods use multiple consensus rounds and, in Dec, communicate both primal and dual states. Without matched communication budgets, the reported convergence advantage is difficult to assess.
Questions for authors
How often is clipping activated, and do the results hold when primal and dual updates use the same loss as required by the analysis?
Do the proposed methods retain their advantage when compared at equal transmitted-byte budgets and with tuned baseline regularization strengths?
We thank the reviewer for the careful and constructive review. We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.
Q1. Clipping frequency and objective consistency.
We thank the reviewer for raising this concern. We use clipping to keep the dual feedback bounded, as required by Assumption 2. In practice, clipping was never activated on Adult or CIFAR-10 and occurred in only 0.0126% of evaluations on MNIST in Dec. We also repeated the experiments without clipping while keeping the normalization and other settings. On MNIST, the mean accuracy decreased by only 0.04, 0.19, and 0.25 percentage points for AG(3), AG(1), and CG(1), respectively, while CG(3) remained unchanged. These results suggest that clipping has little empirical impact in practice.
Q2. Matched transmitted bytes and regularization tuning.
We thank the reviewer for this important suggestion. We added worst-worker accuracy versus cumulative communication in Figures 3-4 and cross-entropy in Figure 6. For Dec at the same budgets, reported worst-worker accuracy (%, mean ± SD) is:
Method
MNIST (1300 MB)
CIFAR-10 (100 MB)
AG(1)
80.84 ± 0.58
70.22 ± 1.30
AG(3)
80.67 ± 0.63
73.21 ± 0.63
CG(1)
79.51 ± 1.60
68.15 ± 0.82
CG(3)
78.23 ± 0.49
71.35 ± 1.20
AD-GDA
69.00 ± 0.66
60.76 ± 0.87
DR-DSGD
70.85 ± 0.45
58.89 ± 1.17
We also evaluated sensitivity to baseline regularization on CIFAR-10 over α{AD-GDA}∈0.01,0.05,0.1,0.5,1,3 and μDR-DSGD∈1,3,6,10,20,30. At each communication budget, the baseline entry reports the highest mean accuracy and the lowest mean cross-entropy across all configurations, reported as Accuracy (%) / CE:
Communication cost (MB)
AD-GDA
DR-DSGD
Dec AG(1)
Dec CG(1)
25.61
49.186 / 1.1604
50.279 / 1.2478
62.499 / 1.1181
60.977 / 1.0474
51.21
56.756 / 1.0455
61.132 / 1.0649
67.785 / 0.8907
66.026 / 0.8932
76.82
60.013 / 1.0038
64.780 / 0.9850
69.727 / 0.8024
67.648 / 0.8397
102.42
61.668 / 0.9854
66.557 / 0.9452
70.766 / 0.7628
68.529 / 0.8154
The results show higher accuracy and lower cross-entropy for AG(1) and CG(1).
Please feel free to let us know if you have any additional concerns or questions.
This paper studies convex group distributionally robust optimization (GDRO) in semi-decentralized and fully decentralized networks, aiming to minimize the maximum risk across workers. Its main contribution is an error decomposition that separates optimization errors from disagreements among workers’ models and group weights, leading to frameworks supporting different consensus routines. The accelerated-gossip and Choco-gossip variants achieve an expected optimization error of O(logm/T) for each worker's time-averaged local model under the original GDRO objective, with the prescribed number of consensus rounds per update. Here, m is the number of workers and T is the number of updates.
Experiments on Adult, MNIST, and CIFAR-10 evaluate worst-worker accuracy and loss using linear classifiers or frozen features with a linear head. The fully decentralized variants generally outperform AD-GDA and DR-DSGD in the reported experiments. The evaluation also compares consensus routines and examines the effect of additional communication rounds per update.
Critical strengths
1.The paper establishes convergence guarantees for each worker’s time-averaged local model under the original GDRO objective, rather than only for a model averaged across the network. This is meaningful because the guarantee concerns the worst-group risk of an output that each worker can maintain locally, without an additional final model-averaging step. The results cover both semi-decentralized and fully decentralized settings and avoid modifying the objective with a fixed dual penalty. Together, these features make the theoretical guarantees relevant to decentralized deployment.
2.The error decomposition explains how disagreements between workers’ models and group weights affect convergence. In the fully decentralized setting, weights taken from different workers do not need to form a valid probability distribution. The paper uses a virtual reference probability distribution to control the resulting error through consensus accuracy. By separating communication effects from the optimization analysis, the framework supports both accelerated gossip and Choco-gossip. This makes the analysis useful beyond a single communication routine and clarifies the role of imperfect information exchange.
Critical weaknesses
Appendix B.1 clips the loss used to update group weights but not the loss used to train the model. When clipping is active, these updates do not directly match the objective analyzed in the theory. Its effect on the results is not evaluated. The experiments also compare update rounds rather than equal communication costs. These issues weaken the claim that the gains come from optimizing the original GDRO objective.
The paper emphasizes the unregularized objective and local-model guarantees, but does not directly compare its assumptions and convergence bounds with those of AD-GDA. In particular, differences in the dependence on the number of workers and the required communication are not clearly presented. This makes the extent of the theoretical improvement difficult to assess, which is important because the paper’s main contribution is theoretical.
Questions for authors
1.Do the main results hold without clipping the loss in the dual update? Please provide an ablation with and without clipping, keeping the normalization unchanged.
2.Does the performance advantage remain at the same communication cost? Please compare performance against the total amount of data transmitted.
We thank the reviewer for the constructive review and positive assessment of our paper. We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.
Q1. Clipping and the original objective.
We thank the reviewer for raising this concern. We use clipping to keep the dual feedback bounded, as required by Assumption 2. In practice, clipping was never activated on Adult or CIFAR-10 and occurred in only 0.0126% of evaluations on MNIST in Dec. We also repeated the experiments without clipping while keeping the normalization and other settings. On MNIST, the mean accuracy decreased by only 0.04, 0.19, and 0.25 percentage points for AG(3), AG(1), and CG(1), respectively, while CG(3) remained unchanged. These results suggest that clipping has little empirical impact in practice.
Q2. Equal-communication comparisons.
We thank the reviewer for this important suggestion. We added worst-worker accuracy versus cumulative communication in Figures 3-4 and cross-entropy in Figure 6. For Dec at the same budgets, reported worst-worker accuracy (%, mean ± SD) is:
Method
MNIST (1300 MB)
CIFAR-10 (100 MB)
AG(1)
80.84 ± 0.58
70.22 ± 1.30
AG(3)
80.67 ± 0.63
73.21 ± 0.63
CG(1)
79.51 ± 1.60
68.15 ± 0.82
CG(3)
78.23 ± 0.49
71.35 ± 1.20
AD-GDA
69.00 ± 0.66
60.76 ± 0.87
DR-DSGD
70.85 ± 0.45
58.89 ± 1.17
Our four variants achieve higher mean accuracy than both baselines.
Q3. Comparison of theoretical guarantees with AD-GDA.
Thank you for this suggestion. AD-GDA (Zecchin et al., 2023, Theorem 4.1) analyzes a smooth, strongly concave-in-dual, regularized objective gα(w,q)=ϕ(w,q)/m+αr(q). For the negative chi-square regularizer with a uniform reference, r(q)=−m∣q−1/m∣22∈[−(m−1),0]. Writing Ψ(w)=maxiRi(w) and Φα(w)=maxq∈Δmgα(w,q) gives Ψ(w)−minuΨ(u)≤m[Φα(w)−minuΦα(u)]+αm(m−1).Thus, for fixed α>0, AD-GDA's guarantee does not eliminate the additive regularization bias. More explicitly, letting Aα=1+αm, Theorem 4.1 yields the following bound for the original GDRO objective:
\le O\left(
\frac{mA_\alpha^2}{\rho^2\delta\sqrt T}
+\frac{mA_\alpha^3}{\rho^4\delta^2T}
\right)+\alpha m(m-1).$$
In contrast, our Proposition 2 establishes a per-worker convergence guarantee $O\left(\frac{m^{3/4}\sqrt{\log m}}{\sqrt{\delta}\rho\sqrt T}\right),$ with a single gossip step per consensus call. Even in this single-round setting, our Dec-CG(1) bound exhibits strictly milder dependence on $m$, $\rho$, and $\delta$ than the leading term of AD-GDA's converted bound, while avoiding regularization bias and smoothness assumptions.
The paper studies group distributionally robust optimization (GDRO), minw∈Wmaxq∈Δm∑i=1mqiRi(w), over decentralized networks in the convex setting. Two architectures are considered:
SemiDec: a lightweight server maintains the shared dual vector using scalar loss reports, while model information is exchanged by gossip among workers.
Dec: each worker maintains both a local model and a local dual vector.
The main technical tool is an error decomposition. Following the centralized GDRO analysis, it bounds each worker's optimization error by primal and dual regrets. It then rewrites the worker-dependent dual objective as a shared global term, ∑jqjRj(wt(j)), plus a Lipschitz discrepancy term. This reduces the problem to a D-OCO problem plus a prediction-with-expert-advice problem in SemiDec, and to two coupled D-OCO problems in Dec. In Dec, a virtual simplex reference sequence is introduced to avoid an extra factor of m.
Algorithmically, both frameworks run FTRL (dual averaging) on gossip-tracked cumulative gradients, with the consensus routine treated as a black box. Instantiations with accelerated gossip (AG) and Choco-gossip (CG) achieve an O(logm/T) per-worker rate on the original GDRO objective, using O(logm/ρ) or O(logm/(δρ2)) gossip rounds per update. Experiments train linear models on Adult, MNIST, and CIFAR-10 (frozen ResNet-20 features) over a ring graph, and compare worst-worker accuracy against DR-DSGD and AD-GDA.
Critical strengths
Relevant problem. Worst-group robustness under heterogeneous decentralized data is practically relevant. Targeting the unregularized GDRO objective, rather than a dual-regularized surrogate, avoids the regularization bias of DR-DSGD and AD-GDA.
Per-worker guarantees. Guarantees are stated for each worker's local time-averaged model rather than for a network average that is unavailable in practice.
Modular analysis. Isolating consensus error as a black-box quantity makes the framework compatible with different gossip schemes, including compressed ones. The proofs are detailed, with explicit constants.
Good dependence on m. The use of entropic FTRL together with the simplex structure yields logm dependence, matching centralized GDRO up to logarithmic factors in sample complexity.
Sensible SemiDec design. The server only handles scalars and the m-dimensional dual, while high-dimensional traffic stays on peer-to-peer links.
Critical weaknesses
1. Limited technical novelty. The main ingredients are standard:
the primal/dual regret decomposition comes from centralized GDRO (Zhang et al., 2023; Soma et al.);
per-node analysis of distributed dual averaging around a virtual centralized iterate follows Duchi et al. (2012);
multiple gossip rounds per update follow the blocking idea of Wan et al. (2025) and Yang et al. (2026).
The "novel error decomposition" amounts to adding and subtracting Rj(wt(j)) and bounding the difference by Lipschitzness, which is a routine step in consensus-based analyses. The virtual reference sequence q~t in Dec is the most non-trivial component, but it is also a fairly standard device. Moreover, because O(logm) gossip rounds per update drive consensus error to a negligible level (e.g., εc,q≤1/m2 in Corollaries 3-4), the algorithm effectively emulates centralized GDRO, and the analysis largely inherits from it. The paper does not analyze what happens with a constant number of gossip rounds (e.g., L=1), which is the regime that would require genuinely new decentralized arguments and is also what the experiments use.
2. Incomplete positioning against decentralized convex-concave minimax literature. The related-work section states that most decentralized minimax methods target regimes other than convex-concave, and dismisses Koppel et al. (2015). This overlooks a substantial body of work on decentralized convex-concave saddle-point problems and monotone VIs, including:
Mateos-Nunez & Cortes (IEEE TAC 2017): subgradient methods with Laplacian averaging and per-node 1/t guarantees for general convex-concave problems;
Rogozin et al. (arXiv 2021; Optim. Methods Softw. 2025): decentralized mirror-prox with non-Euclidean, including entropic, setups and guarantees in both duality gap and consensus;
Beznosikov et al. (NeurIPS 2022): decentralized stochastic extragradient for monotone VIs;
Kovalev et al. (NeurIPS 2022): optimal decentralized stochastic VIs.
GDRO fits directly into this framework by writing ϕ(w,q)=m1∑i=1mfi(w,q) with fi(w,q)=mqiRi(w), where each worker can compute stochastic gradients of fi in both arguments. The paper should explain what applying these generic methods to GDRO would yield (e.g., the dependence on m under Euclidean versus entropic geometry, and smoothness requirements) and precisely what the proposed approach improves. Without this comparison, the claim of "the first per-worker convergence guarantees for the original GDRO objective" is not well substantiated.
3. The convergence measure is not stronger than existing ones. The paper bounds the primal suboptimality εϕ(wˉ)=maxqϕ(wˉ,q)−minwmaxqϕ(w,q) evaluated at each local output wˉ=wˉT(i). By weak duality, for any qˉ∈Δm we have εϕ(wˉ)≤maxqϕ(wˉ,q)−minwϕ(w,qˉ)=Gap(wˉ,qˉ), so this is a weaker criterion than the duality-gap guarantees provided by generic decentralized saddle-point methods. Per-worker guarantees also follow almost immediately from guarantees on an averaged point plus a consensus bound: since maxjRj is G-Lipschitz, εϕ(wˉ(i))≤εϕ(wˉavg)+G∥wˉ(i)−wˉavg∥2. The emphasis on per-worker guarantees as a distinguishing contribution should therefore be toned down or better justified.
4. Weak experimental evaluation.
No baselines for SemiDec. At minimum, a centralized GDRO baseline and a naive adaptation of existing methods should be included.
No communication-normalized comparison. AG(3)/CG(3) use three gossip rounds per update, and in Dec the method communicates both primal and dual quantities (Lw+Lq rounds). The plots use update rounds on the x-axis, which may favor the proposed methods. Results should also be shown against the number of communicated bits or neighbor exchanges.
Limited scale and diversity. All experiments use linear models (CIFAR-10 uses only a trainable linear head), small m (6 or 10), and a single ring topology. There is no study of how performance scales with m or with the spectral gap ρ, even though these are central to the theory.
5. Presentation and notation. The paper is difficult to follow because of heavy notation overloading and inconsistencies. The reader will get overwhelmed by the heavy notations and lose the patient to dive deeper.
Questions for authors
Comparison to generic methods. If GDRO is cast as minwmaxqm1∑i=1mfi(w,q) with fi(w,q)=mqiRi(w) and solved by an existing decentralized convex-concave method (e.g., Mateos-Nunez & Cortes 2017 with an entropic mirror map, Rogozin et al. 2025, or Beznosikov et al. 2022), what rate and dependence on m and ρ would result? What precisely does your decomposition enable that these approaches cannot?
Duality gap. Since the FTRL regret bound holds for any comparator u∈W, can your analysis directly bound the duality gap at (wˉT(i),qˉT) (SemiDec) or (wˉT(i),qˉT(i)) (Dec)? If so, why report only primal suboptimality?
Constant gossip rounds. What guarantee does your framework give with L=1 (or any constant L) per update? Does the rate remain O(1/T) with a worse dependence on m/ρ, or does the analysis break down? This is the regime used in your experiments.
Communication-normalized experiments. Can you provide plots of worst-worker accuracy against total communication (bits or neighbor exchanges), comparing AG(1), AG(3), CG(1), CG(3), AD-GDA, and DR-DSGD on equal footing?
Constants in Dec. In Corollaries 3-4, the dual consensus error must be driven to 1/m2 (with kq∼m5). Although the number of rounds remains logarithmic, what are the hidden constants for realistic m and ρ? How many gossip rounds would the theory prescribe for your experimental settings?
Step-size dependence on m. Theorem 2 uses ηq=m2lnm/T. Can you comment on the role of this scaling and whether it causes instability for larger m?
Nonconvex models. Although the theory is convex, the motivation includes deep models. Have you evaluated the method end-to-end on a nonconvex model (e.g., full ResNet training), even without theoretical guarantees?
We thank the reviewer for the careful reading and detailed assessment. We have carefully considered your comments and uploaded our revised paper, with the changes highlighted in blue for ease of reference.
Q1. Limited technical novelty.
Technical novelty. We respectfully disagree that our contributions amount to applying standard tools.
Directly applying centralized GDRO analysis requires cross-worker risks that workers cannot evaluate locally (Sections 4.1 and 5.1). Our technical contribution is a new decomposition of these inaccessible worker-specific objectives. The key choice of Rj(wt(j)) is guided by each worker's local information and yields a shared global objective, bridging the inaccessible worker-specific risks Rj(wt(i)) and implementable decentralized updates.
Duchi et al. (2012) study single-level convex minimization, whereas GDRO couples primal optimization with adaptive dual weights. Even after the D-OCO reduction in Dec, w and q still require joint analysis, since each bound involves the other variable's consensus error.
Multiple gossip rounds reduce disagreement, but do not provide an analysis of the coupled minimax updates. Exploiting these rounds relies on our decomposition, which separates optimization and consensus errors in Theorems 1–2.
Constant gossip rounds. Our framework still converges with one communication step per consensus routine. Propositions 1–2 (Appendix D.10) give the following per-worker bounds:
Setting
AG(1)
CG(1)
SemiDec
O(Tm/ρ+logm)
O(Tm/(δρ2)+logm)
Dec
O(T(1+m/ρ)logm)
O(δρ2Tm3/2logm)
Thus all four settings retain O(T−1/2) convergence for fixed network parameters. Multi-round communication improves the sample and communication complexities, as summarized in Tables 1–2 (Appendix C).
Q2. Positioning against decentralized convex-concave minimax literature.
We appreciate these references. However, their guarantees differ from ours in assumptions or convergence criteria. Rogozin et al. (2025) and Beznosikov et al. (2022) require Lipschitz-continuous operators, corresponding to stronger smoothness requirements for GDRO. Kovalev et al. (2022) also require strong monotonicity, which the original GDRO objective lacks. Mateos-Núñez and Cortés (2017, Theorem IV.6) bound saddle-point evaluation error, which does not bound primal suboptimality. Koppel et al. (2015), already cited in Section 2, study network regret with dual variables enforcing consensus constraints rather than GDRO's distributional weights.
Q3. Per-worker guarantees and duality gap.
We agree that the duality gap is a stronger optimality certificate, and our current analysis does not achieve a guarantee on it. However, we want to emphasize that inherited from GDRO, our learning target is minw∈Wmaxj∈[m]Rj(w), and thus the natural performance measure is ϵϕ(wˉ)=maxjRj(wˉ)−minwmaxjRj(w) studied in both our paper and previous studies (Sagawa et al., 2020; Mohri et al., 2019; Zhang et al., 2023; Zecchin et al., 2023).
Moreover, although the inequality εϕ(wˉ(i))≤εϕ(wˉavg)+G∥wˉ(i)−wˉavg∥2 is valid, the existing study (Rogozin et al., 2025) only achieves these two bounds under stronger smoothness assumption and with exact gradients. As mentioned above, this is not directly comparable with ours.
SemiDec baselines. We have added SGD-AG(1), SGD-CG(1), and a centralized GDRO reference for SemiDec (please see Figures 1, 3, 5, and 6). At the final updates, both AG(1) and CG(1) achieve lower mean worst-worker loss than their corresponding SGD baselines on all three datasets.
Communication cost comparisons. Figures 3–4 report worst-worker accuracy against cumulative communication cost, and Figure 6 reports cross-entropy. At matched Dec communication budgets, we obtain the following reported worst-worker accuracies (%, mean ± SD):
Method
MNIST (1300 MB)
CIFAR-10 (100 MB)
AG(1)
80.84 ± 0.58
70.22 ± 1.30
AG(3)
80.67 ± 0.63
73.21 ± 0.63
CG(1)
79.51 ± 1.60
68.15 ± 0.82
CG(3)
78.23 ± 0.49
71.35 ± 1.20
AD-GDA
69.00 ± 0.66
60.76 ± 0.87
DR-DSGD
70.85 ± 0.45
58.89 ± 1.17
Network topology. We additionally evaluated five connected m=10 networks on MNIST after 3,000 updates. Ring-4, Regular-4 Low, and Regular-4 each have 20 edges, allowing equal-edge-count comparisons. Their results show decreasing cross-entropy with increasing spectral gap.
Topology
Edges
Spectral gap (ρ)
AG(1) Acc ↑ (%)
AG(1) CE ↓
CG(1) Acc ↑ (%)
CG(1) CE ↓
Ring
10
0.0955
82.34 ± 0.33
0.642 ± 0.009
75.00 ± 0.47
0.783 ± 0.008
Regular-4 Low
20
0.1402
84.15 ± 0.51
0.581 ± 0.013
76.43 ± 0.78
0.6620 ± 0.013
Ring-4
20
0.2205
85.37 ± 0.26
0.551 ± 0.008
78.22 ± 0.63
0.647 ± 0.004
Regular-4
20
0.3167
85.85 ± 0.38
0.4475 ± 0.005
83.57 ± 0.51
0.5031 ± 0.012
Complete
45
0.5556
88.19 ± 0.11
0.3923 ± 0.011
87.80 ± 0.43
0.4187 ± 0.012
Worker scalability. We further evaluated m∈{10,20,30} on MNIST, using Ring and Regular-4 networks for 3,000 updates. AG(1) has higher accuracy and lower CE than CG(1) in all settings. The Regular-4 results degrade less with increasing m in these experiments.
Topology
m
AG Acc (%) ↑
AG CE ↓
CG Acc (%) ↑
CG CE ↓
Ring
10
82.34 ± 0.33
0.6418 ± 0.0092
75.00 ± 0.47
0.7831 ± 0.0079
Ring
20
66.80 ± 0.50
0.8765 ± 0.0113
63.08 ± 0.80
0.9247 ± 0.0097
Ring
30
65.92 ± 1.32
0.9304 ± 0.0416
58.66 ± 0.95
1.0216 ± 0.0095
Regular-4
10
85.85 ± 0.38
0.4475 ± 0.0045
83.57 ± 0.51
0.5031 ± 0.0121
Regular-4
20
84.48 ± 0.48
0.5341 ± 0.0097
83.45 ± 0.49
0.5411 ± 0.0118
Regular-4
30
84.15 ± 0.23
0.5927 ± 0.0104
80.57 ± 0.58
0.6847 ± 0.0103
Nonconvex experiments. We additionally fine-tuned the full ResNet-20 on CIFAR-10, including its convolutional layers and classification head. The table reports final worst-worker results after 3,000 optimization updates. Both proposed variants exceed these baselines.
Methods
Worst-worker accuracy ↑
Worst-worker CE ↓
AG(1)
52.61%
1.0761
CG(1)
50.10%
1.1278
DR-DSGD
47.70%
1.2657
AD-GDA
24.75%
2.7217
Overall, these experiments demonstrate the applicability of our methods across different network topologies and workers.
Q5. Constants in Dec.
The multi-round choices in Corollaries 1–4 are sufficient worst-case conditions for the O(log(m)/T) rate and can be conservative. Propositions 1–2 establish convergence for the relevant L=1 regime. Using the lazy-ring mixing matrices of our experiments and δ=0.5, the prescribed counts are:
Network
SemiDec AG L
SemiDec CG L
Dec AG (Lw,Lq)
Dec CG (Lw,Lq)
m=6 (Adult)
21
1,499
(21,40)
(1499,5008)
m=10 (MNIST/CIFAR-10)
38
8,950
(38,79)
(8950,30250)
Q6. Step-size dependence on m.
For entropy-regularized FTRL, ηq=O(log(m)/(GqT)). In Dec, consensus tracks gradients of m1∑iqist,i, with st,i∈[0,1], giving the ℓ∞ bound Gq=1/m. Hence ηq=O(mlog(m)/T).
Although ηq increases with m, the norm of the consensus term decreases accordingly, thereby maintaining the stability of the optimization process.
Q7. Presentation and notation.
We thank the reviewer for this suggestion and have clarified the index conventions in Section 3, summarized the notation in Table 3, and explained the consensus-state conventions in Appendix A.
We will continue to refine the exposition and would appreciate any specific examples of notation or passages that you found difficult to follow.
Please feel free to let us know if you have any additional concerns or questions.
Thank you again for your time and careful consideration of our work.
We would like to kindly follow up on our response. If you have any remaining questions or concerns, we are happy to provide further clarification before the discussion period concludes. We would appreciate your updated assessment in light of our response and revisions.
Best regards,
Authors
From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.
To Reviewer z4Bw
We thank the reviewer for the careful and constructive review. We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.
Q1. Clipping frequency and objective consistency.
We thank the reviewer for raising this concern. We use clipping to keep the dual feedback bounded, as required by Assumption 2. In practice, clipping was never activated on Adult or CIFAR-10 and occurred in only 0.0126% of evaluations on MNIST in Dec. We also repeated the experiments without clipping while keeping the normalization and other settings. On MNIST, the mean accuracy decreased by only 0.04, 0.19, and 0.25 percentage points for AG(3), AG(1), and CG(1), respectively, while CG(3) remained unchanged. These results suggest that clipping has little empirical impact in practice.
Q2. Matched transmitted bytes and regularization tuning.
We thank the reviewer for this important suggestion. We added worst-worker accuracy versus cumulative communication in Figures 3-4 and cross-entropy in Figure 6. For Dec at the same budgets, reported worst-worker accuracy (%, mean ± SD) is:
We also evaluated sensitivity to baseline regularization on CIFAR-10 over α{AD-GDA}∈0.01,0.05,0.1,0.5,1,3 and μDR-DSGD∈1,3,6,10,20,30. At each communication budget, the baseline entry reports the highest mean accuracy and the lowest mean cross-entropy across all configurations, reported as Accuracy (%) / CE:
The results show higher accuracy and lower cross-entropy for AG(1) and CG(1).
Please feel free to let us know if you have any additional concerns or questions.