PaperlayerView exact revision on arXiv

Source-linked AI summary

Group Distributionally Robust Optimization over Decentralized Networks

Haomin Bai, Junyan Sun, Quan Cheng, Yuanyu Wan, Lijun Zhang

arXiv:2610.29261v1math.OCcs.LG

TL;DR

Average-risk training can leave some workers poorly served when their data distributions differ, while existing decentralized GDRO methods do not guarantee local models for the original objective. This paper develops error decompositions and modular decentralized methods for SemiDec and Dec, establishing per-worker guarantees and reporting improved worst-worker performance over baselines.

  • Problem

    Heterogeneous worker distributions can make average-risk training unfair, while existing decentralized GDRO methods lack guarantees for locally maintained models under the original objective.

    Source: §1 · pp. 1–2

  • Method

    The paper decomposes decentralized GDRO into D-OCO and prediction-with-expert-advice in SemiDec, or two coupled D-OCO problems in Dec, while isolating consensus errors.

    Source: §1 · p. 2

  • Results

    The paper establishes the first per-worker convergence guarantees for the original decentralized GDRO objective and reports improved worst-worker performance over prior methods.

    Source: §6 · p. 8, §8 · p. 10

  • Takeaways & Limitations

    The guarantees apply to each worker’s local model, avoiding reliance on a globally averaged model that requires additional communication.

    Source: §1 · p. 2

    The analysis assumes a nonempty compact convex model space, convex risks with unbiased stochastic gradients, and a connected communication graph with a symmetric mixing matrix.

    Source: §3 · p. 3

Abstract

from arXiv · show

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 \emph{first} per-worker convergence guarantees for optimizing the original GDRO objective over decentralized networks. Instantiations with accelerated gossip and Choco-gossip achieve an $O(\sqrt{(\log m)/T})$ convergence rate over $T$ update rounds, while experiments demonstrate improved worst-worker performance over baselines.

1 INTRODUCTION

GDRO targets the highest-risk worker, addressing the limits of average-risk training when local data distributions are heterogeneous. This paper directly optimizes the original GDRO objective over decentralized networks and develops per-worker guarantees.

Motivation

  • Heterogeneous worker data can make average-risk optimization unfair to some workers and less robust to distribution shift.GDRO instead minimizes the maximum risk across workers.Source: §1 · p. 1

Gap

  • Prior decentralized GDRO methods optimize dual-regularized variants and guarantee a globally averaged model, not optimality for the original objective or locally maintained models.Approximating the global average requires additional communication.Source: §1 · p. 2

Approach

  • A new error decomposition makes decentralized GDRO tractable despite worker-dependent losses that require unavailable cross-worker information.It separates shared global objectives from discrepancies caused by inconsistent local decisions.Source: §1 · p. 2
  • SemiDec reduces to D-OCO for primal updates and prediction with expert advice for dual updates; Dec reduces to two coupled D-OCO problems.Both formulations include discrepancy terms for inconsistencies among local decisions.Source: §1 · p. 2

Contributions

  • Modular frameworks isolate consensus effects and establish per-worker convergence guarantees; accelerated gossip and Choco-gossip yield the stated O( p (log m)/T) rate.The paper also reports improved worst-worker performance over prior methods.Source: §1 · p. 2

2 RELATED WORK

Related work covers decentralized minimax optimization, GDRO across centralized and distributed settings, and decentralized online convex optimization methods.

Decentralized minimax optimization

  • Decentralized minimax research spans several convexity regimes, while Koppel et al. (2015) use dual variables for consensus constraints rather than distributional weights.Applications include energy systems, wireless sensor networks, and autonomous vehicles.Source: §2 · pp. 2–3

Group distributionally robust optimization

  • GDRO has been studied centrally and in server-based federated learning, while decentralized methods use strongly concave dual regularization; the original objective remains unexplored there.DR-DSGD and AD-GDA simplify decentralized design through regularized dual formulations.Source: §2 · p. 3

Decentralized online convex optimization

  • D-OCO combines decentralized decision updates with consensus, using methods including gradient descent, FTRL, gossip, accelerated gossip, and compressed communication.Recent work targets improved regret bounds and communication efficiency.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries define the optimization error and assumptions on risks, model space, and the worker communication network, then introduce consensus as a modular information-exchange routine.

Optimization setup

  • Optimization error is the worst-worker risk of a candidate model minus the minimum achievable worst-worker risk.The setup assumes a nonempty compact convex model space and convex risks with unbiased stochastic gradients.Source: §3 · p. 3

Communication network

  • The communication graph is undirected and connected, and its symmetric mixing matrix has positive entries only on worker links.The framework also assumes self-links and a matrix satisfying P · 1m = 1m.Source: §3 · p. 3

Consensus routine

  • Information exchange is modeled as a black-box consensus routine, instantiated with accelerated gossip for fast mixing or Choco-gossip for compressed communication.The corresponding procedures and consensus-error bounds are provided in the appendix.Source: §3 · pp. 3–4

4 SEMI-DECENTRALIZED GDRO

SemiDec assigns the shared dual vector to a lightweight server while workers exchange high-dimensional model information. Its analysis decomposes each worker’s error into online-learning regrets and disagreement terms, then isolates consensus effects in a modular framework.

4 SEMI-DECENTRALIZED GDRO

  • SemiDec combines high-bandwidth worker-to-worker communication with a low-bandwidth server link; the server maintains the shared dual vector while workers communicate model updates.The paper motivates this architecture with wireless systems that have fast device-to-device links and bandwidth-limited base-station links.Source: §4 · p. 4

4.1 ERROR DECOMPOSITION

  • Unavailable cross-worker risks prevent direct construction of worker-specific dual sequences, so the decomposition separates shared global objectives from local-decision discrepancies.The resulting error is controlled by shared dual regret via PEA, primal regret via D-OCO, and model discrepancy.Source: §4.1 · pp. 4–5

4.2 FRAMEWORK DESIGN AND INSTANTIATION

  • GDRO-SEMIDEC treats consensus as a black box and bounds each worker’s time-averaged local-model error through consensus error, allowing different routines and communication schedules.The framework is instantiated with accelerated gossip and Choco-gossip; their corollaries specify communication-round choices.Source: §4.2 · p. 6

5 DECENTRALIZED GDRO

In Dec, every worker maintains its own model and dual vector, creating both model and dual inconsistency. The analysis decomposes each worker’s error into coupled online-optimization regrets and discrepancy terms, then uses consensus-based FTRL to obtain a modular framework.

5 DECENTRALIZED GDRO

  • Dec removes the server, leaving each worker to maintain both a local model and a local dual vector, so dual inconsistency joins model inconsistency.This differs from SemiDec, where the dual vector is shared.Source: §5 · p. 6

5.1 ERROR DECOMPOSITION

  • A virtual simplex reference sequence lets dual deviations be controlled through dual consensus error, avoiding an additional factor of m.The reference sequence is driven by the averaged dual gradient.Source: §5.1 · p. 7
  • Each worker’s output error is bounded by two D-OCO regret terms over shared global objectives and two discrepancy terms.The discrepancies capture disagreement among local decisions.Source: §5.1 · p. 7

5.2 FRAMEWORK DESIGN AND INSTANTIATION

  • GDRO-DEC uses consensus-based FTRL updates and isolates communication effects through consensus errors, allowing the two consensus routines to be instantiated independently.Under exact consensus, C1 = 1 and C2 = C3 = 0 in the stated bound.Source: §5.2 · pp. 7–8

6 DISCUSSION OF THEORETICAL GUARANTEES

The theoretical guarantees apply to each worker’s local model and separate optimization error from communication-induced consensus errors. Under exact consensus, the optimization rate is O(sqrt((log m)/T)), with sample complexity matching centralized GDRO up to logarithmic factors.

6 DISCUSSION OF THEORETICAL GUARANTEES

  • Theorems 1 and 2 provide the first per-worker convergence guarantees for the original GDRO objective over decentralized networks.Each worker’s bound separates an intrinsic optimization term from communication-induced consensus errors.Source: §6 · p. 8
  • Under exact consensus, the error is O(sqrt((log m)/T)), and an ε-optimal solution requires O((log m)/ε^2) updates and O((m log m)/ε^2) samples.The sample complexity matches the best-known centralized GDRO results and the information-theoretic lower bound up to a factor of O(log m).Source: §6 · p. 8
  • The stated AG and CG communication-round choices preserve the O(sqrt((log m)/T)) rate, but are sufficient rather than necessary.The main theorems remain valid for different numbers of consensus rounds.Source: §6 · p. 8

7 EXPERIMENTS

Experiments on Adult, MNIST, and CIFAR-10 report worst-worker accuracy for SemiDec and Dec. In Dec, the proposed variants generally converge faster and attain higher accuracy than the baselines; additional consensus rounds generally improve convergence speed in both settings.

Experimental setup

  • The evaluation uses Adult, MNIST, and CIFAR-10, reporting worst-worker accuracy on an undirected ring network.Adult and MNIST use linear classifiers; CIFAR-10 uses a frozen pretrained ResNet-20 backbone with a randomly initialized linear head.Source: §7 · p. 9

Results

  • In Dec, the proposed variants generally converge faster and attain higher worst-worker accuracy than the baselines.The comparison is against DR-DSGD and AD-GDA; Figure 1 reports results across Adult, MNIST, and CIFAR-10.Source: §7 · p. 9
  • Across SemiDec and Dec, L = 3 variants generally improve faster than their L = 1 counterparts, while AG and CG show stable convergence across datasets.The authors relate the speed pattern to reduced consensus errors with additional consensus rounds.Source: §7 · p. 9

8 CONCLUSION

The paper concludes with per-worker guarantees for the original GDRO objective, using modular frameworks that accommodate different consensus routines. Its appendix presents accelerated gossip and Choco-gossip as representative consensus instantiations.

8 CONCLUSION

  • The conclusion bounds each worker’s time-averaged local model for the original GDRO objective and reports improved worst-worker performance over baselines.The analysis separates global regret terms from disagreement-induced discrepancies.Source: §8 · pp. 9–10

A CONSENSUS ROUTINE INSTANTIATIONS

  • The appendix presents accelerated gossip and Choco-gossip as two instantiations of the black-box consensus routine, with procedures and contraction guarantees.The frameworks are designed to support different consensus routines.Source: §8 · p. 9, A CONSENSUS ROUTINE INSTANTIATIONS · p. 13

A.1 ACCELERATED GOSSIP

  • Accelerated gossip is an accelerated linear consensus scheme, and its instantiation assumes the communication matrix P is positive semidefinite.Source: §A.1 · p. 13

A.2 CHOCO-GOSSIP

  • Choco-gossip reduces communication bandwidth by exchanging compressed messages using an approximate compressor.Source: §A.2 · p. 13

B.1 EXPERIMENTAL DETAILS

Experiments evaluate worst-worker loss on Adult, MNIST, and CIFAR-10, while the discussion compares communication costs and the consensus required by the proposed methods. The appendix details the experiment setup and supporting regret analysis.

B.1 EXPERIMENTAL DETAILS

  • Adult uses six workers split by race and sex; MNIST and CIFAR-10 use ten workers, with 80% of each class assigned to its matching worker.The remaining 20% is distributed approximately uniformly among other workers.Source: §B.1 · p. 14

B.2 WORST-WORKER LOSS

  • In Dec, the proposed variants generally finish below AD-GDA and DR-DSGD in worst-worker loss, with the clearest separation on CIFAR-10 and smaller differences on Adult and MNIST.In SemiDec, loss decreases for all variants; AG is faster than CG on MNIST, while L = 3 variants generally improve earlier, particularly on CIFAR-10.Source: Figure 2 · p. 15, §B.2 · p. 15

B.1 EXPERIMENTAL DETAILS

  • The experiments use linear classifiers for Adult and MNIST, and a frozen pretrained ResNet-20 feature extractor with a trained linear head for CIFAR-10.Batch sizes are 128 for Adult and MNIST and 32 for CIFAR-10; the proposed methods use original batch loss for primal updates and clipped, normalized dual feedback.Source: §B.1 · p. 15

C FURTHER DISCUSSION OF THEORETICAL GUARANTEES

  • For target expected error ε, AG has communication complexity O(|Ens|(log m)^2/(ε^2√ρ)), while CG has O(|Ens|(log m)^2/(ε^2δρ^2)).These bounds use the stated gossip-round orders for each method.Source: C FURTHER DISCUSSION OF THEORETICAL… · pp. 15–16
  • The multiple consensus rounds are inherited from the D-OCO subproblems; the cited analysis associates a single AG step per round with a worse regret bound.The blocking-based method cited for comparison uses O((log m)/√ρ) rounds between decision updates and achieves a near-optimal regret bound up to a logarithmic factor.Source: C FURTHER DISCUSSION OF THEORETICAL… · p. 16
  • SemiDec and Dec require the same order of peer-to-peer consensus rounds for primal information, but Dec also communicates m-dimensional dual information among workers.SemiDec maintains its shared dual vector through scalar server–worker communication.Source: C FURTHER DISCUSSION OF THEORETICAL… · p. 16

D.1 USEFUL LEMMAS

  • The appendix states FTRL regret bounds and a simplex, negative-entropy instantiation for analyzing the updates.Source: §D.1 · p. 16

D.2 THE PROOF OF THEOREM 1

  • In SemiDec, the server handles the dual regret as a prediction-with-expert-advice problem using Hedge, alongside the primal regret analysis.The analysis uses a virtual decision sequence to characterize deviations from workers’ local decisions.Source: §D.2.1 · p. 18, §D.2.2 · p. 19

D.2.3 DISCREPANCY ERROR TERM AND RESULTS

The appendix derives bounds by combining regret terms with discrepancies caused by decentralized decisions. It applies this analysis to the SemiDec and Dec settings and to accelerated and compressed gossip guarantees.

D.2.3 DISCREPANCY ERROR TERM AND RESULTS

  • The SemiDec result assumes per-round communication error at most ε_c and bounds each worker’s optimization error using regret and discrepancy terms.Source: §D.2.3 · pp. 20–21

D.3 THE PROOF OF COROLLARY 1

  • The accelerated-gossip corollary proof applies its per-round communication-error bound to the general optimization bound.Source: §D.3 · p. 21

D.4 THE PROOF OF COROLLARY 2

  • The Choco-gossip corollary proof applies the corresponding communication-error bound and Jensen’s inequality to obtain its guarantee.Source: §D.4 · p. 22

D.5 THE PROOF OF THEOREM 2

  • In Dec, the optimization error decomposition uses each worker’s local dual iterates because there is no central server to compute a shared dual sequence.The analysis introduces discrepancy measures for disagreement in primal and dual iterates around virtual sequences.Source: §D.5 · pp. 22–23

D.5.1 REGRET Reg(i)

  • The Dec primal-regret analysis follows the SemiDec approach but uses locally maintained dual weights rather than shared server weights.Source: §D.5.1 · pp. 23–24

D.5.2 REGRET Reg(i)

  • The analysis treats term(q2) via Lemma 4 and update rule (47), and treats term(q3) by applying the argument for (32) to the data-dependent index j(i).Source: §D.5.2 · p. 25

D.5.3 DISCREPANCY ERROR TERM AND RESULTS

The Dec analysis bounds each worker’s optimization error by combining regret bounds with an estimate of disagreement among local decisions. The resulting guarantee incorporates consensus errors through primal and dual discrepancy bounds.

D.5.3 DISCREPANCY ERROR TERM AND RESULTS

  • Combining the Dec regret bounds with the discrepancy estimate yields an optimization-error bound for every worker.The discrepancy estimate captures disagreement among local models and between local dual vectors and the proxy vector.Source: §D.5.3 · p. 25
  • The final bound substitutes consensus-error bounds for primal and dual discrepancies, and Equation (62) yields the Theorem 2 bound.Source: §D.5.3 · p. 26

D.6 THE PROOF OF COROLLARY 3

The appendix derives corollary bounds using accelerated gossip and Choco-gossip, with average preservation supporting the analyses. It also proves lemmas concerning disagreement and consensus calls.

D.6 THE PROOF OF COROLLARY 3

  • Substituting into the general optimization bound (62) yields a bound for every worker in the accelerated-gossip analysis.The proof also treats the shorter-horizon case separately.Source: §D.6 · pp. 26–27

D.7 THE PROOF OF COROLLARY 4

  • The Choco-gossip analysis applies Lemma 9 and the general optimization bound (62), with a separate argument for the shorter-horizon case.Average-preservation conditions are stated to hold automatically.Source: §D.7 · p. 27

D.8 THE PROOF OF LEMMA 8

  • Lemma 8 bounds the disagreement measure e_t = ∥X_t − X̄_t1⊤∥_F.The proof also states that accelerated gossip preserves the average.Source: §D.6 · p. 26, §D.8 · p. 28

D.9 THE PROOF OF LEMMA 9

  • The Lemma 9 proof conditions on consensus-call inputs, applies Lemma 2, and then takes total expectations.It introduces the number of communication rounds as L.Source: §D.9 · p. 28

Related papers

Loading 2610.29261v1…