Suppose we want a model trained across many clients (hospitals, phones, labs) to hold up when test data shifts. We also want to pay a single, fixed amount of shift for the whole system, rather than one amount per client. Wasserstein distributionally robust optimization (training against the worst data distribution within a fixed "transport distance" of the observed data) expresses this directly. The pooled data gets a single ball, and an adversary may spend that shift budget wherever the model is weakest, including concentrating it on one fragile client. The difficulty is computational. After the problem is rewritten as a single optimization (dualized), it gains one extra variable per training sample. That kind of growth made exact robust training slow even on one machine. It looks even worse when clients can talk only occasionally.
This note argues that the growth is harmless in the distributed setting because every new variable is local except one. Under a shared ball, clients are coupled only through the model weights and a single scalar $\lambda$: the price per unit of transport the adversary must pay. Each client can compute its own worst-case perturbations for a given price with no communication at all. The price itself can be set by a one-dimensional search on the server, from one number per client per round (the average transport cost that client's adversary spent). The central claim is that $\lambda$ must be held fixed during local training and updated only at synchronization. Letting clients update the price locally, as one would for an ordinary parameter, pulls the solution toward per-client robustness balls as the number of local steps grows. That is a different and weaker guarantee. The proposal builds this scheme, analyzes it, and tests whether a frozen, server-set price keeps the shared-budget guarantee intact for any number of local steps. Robustness would then cost one extra float per round.
Core Claim
Let client $k$ hold empirical distribution $\hat P_k$ with weight $w_k$. Let $c$ be the transport cost between two samples, $\ell$ the loss, and $\varepsilon$ the global radius. The standard Wasserstein duality, the tool surveyed by Blanchet et al. and Shafiee et al., gives
$$\min_\theta \sup_{Q:\,W(Q,\sum_k w_k \hat P_k)\le\varepsilon} \mathbb{E}_Q[\ell(\theta;\xi)] \;=\; \min_{\theta,\;\lambda\ge 0}\; \lambda\varepsilon + \sum_k w_k\, \mathbb{E}_{\zeta\sim \hat P_k}\Big[\sup_{\xi}\big(\ell(\theta;\xi)-\lambda\, c(\xi,\zeta)\big)\Big].$$
For fixed $\lambda$, the inner suprema split across samples and therefore across clients. The only cross-client quantities are $\theta$ (ordinary model consensus) and the scalar $\lambda$. The derivative in $\lambda$ is $\varepsilon - \sum_k w_k \bar c_k(\theta,\lambda)$, where $\bar c_k$ is the mean transport cost spent by client $k$'s best-response adversary. This is a resource-allocation constraint in the sense of dual decomposition: one shared budget, priced by one multiplier.
Two properties make the price easy to find. First, $\bar c_k$ is nonincreasing in $\lambda$, so the server can locate the $\lambda$ that exactly spends $\varepsilon$ by monotone root-finding. This needs no knowledge of smoothness or condition numbers, echoing the golden-section search on a dual scalar in Li et al.. Second, if a client updated $\lambda$ from its own gradient $\varepsilon-\bar c_k$ over many local steps, its local price would drift toward the value at which that client alone spends $\varepsilon$. That is exactly the per-client-ball formulation of Bai et al.. Client drift in the price is therefore not just noise. It changes which problem is being solved.
Relation to Prior Work
Four papers motivate or constrain this proposal.
Bai et al. is the closest existing work. It gives each client its own Wasserstein ball and solves the dualized problem with a linearized ADMM. It synchronizes at every iteration, runs only on a star topology, and was tested on small tabular data. We change the ambiguity set to a single shared ball, which moves all per-sample dual variables local. We then add local steps, which that paper lacks.
Group-level robust federated methods reweight whole clients rather than perturbing samples. DRFA updates simplex weights at a server from randomized snapshots and gets slow rates. FGDRO avoids dual variables altogether by composition. Its authors report that moving-average gradient tracking is unproven for non-smooth objectives such as CVaR. AD-GDA gossips compressed models in a peer-to-peer network but communicates every iteration. None of the three models within-client feature shift, and FGDRO's composition cannot express a continuous Wasserstein ball. Our dual variable is a single scalar, so the high-dimensional dual synchronization that FGDRO's authors argue against does not arise.
Two lines of work supply the method.
Local ADA reads $K$ local primal steps as an inexact dual gradient and proves convergence for any $K$ under smooth strong convexity. We reuse this reading, with the inexactness now coming from both local drift and an approximate inner supremum. Our dual objective is non-smooth, so we swap accelerated ascent for monotone scalar root-finding.
Local SGDA runs local steps on both players of a minimax game. That file lists rotational drift of both players as open. Freezing the only global adversarial variable removes it: local rounds become pure minimization against a locally computed best response.
For the decentralized extension, the budget is a coupled affine constraint of dimension one. Decentralized Optimization with Coupled Constraints proves such constraints are at least $\sqrt{n}$ harder in communication than plain consensus. We will test whether that penalty is negligible when the coupling is a single scalar.
Research Program
We will build one algorithm in three forms.
The server form works in rounds. The server broadcasts $(\theta,\lambda)$. Each client runs $K$ local steps on its penalized robust loss at the frozen $\lambda$, projecting onto $\|\theta\|_*\le\lambda$ where the linear-model dual requires it. Each client returns its model and its average transport cost $\bar c_k$. The server averages the models and advances a safeguarded secant or bisection step on $\lambda$.
The linear form applies to logistic regression with a feature-norm cost and finite label-flip cost $\kappa$. Here the inner supremum is closed-form, $\max(\ell(\theta;x,y),\ \ell(\theta;x,-y)-\lambda\kappa)$, so the robust objective is exactly computable. We deliberately avoid $\kappa=\infty$. There the problem collapses to norm-regularized logistic regression with $\lambda=\|\theta\|_*$, and every method should coincide. We keep it as a sanity check.
The deep form approximates the inner supremum with a few input-space ascent steps. The decentralized form gossips both $\theta$ and $\lambda$.
The analysis targets two results for regularized convex losses. The first is convergence to the shared-ball solution for every $K\ge1$, with the error from the inexact $\bar c_k$ entering additively, as in Local ADA. The second is a characterization showing that the local-$\lambda$ variant converges to a $K$-dependent interpolation between the shared-ball and per-client-ball solutions.
Baselines
The naive reference is FedAvg on empirical risk with the same $K$, communication rounds and tuning budget. It shows how much robustness costs in average accuracy and buys in worst-case accuracy.
The strongest exact Wasserstein competitor is AD-LPMM from Bai et al.. We run it on the same UCI Heart, Breast Cancer and Abalone splits and the same noise model. Its per-client radii are chosen so that their weighted sum equals our $\varepsilon$, which matches the total adversarial budget. We compare at equal numbers of communicated floats. No reported result was found on Lacuna for AD-LPMM's numeric accuracy or MSE, so we will reproduce it. Beating it means lower certified shared-budget worst-case loss at equal or fewer communicated floats.
The pooled quality ceiling is centralized LP-ADMM from Li et al. on pooled data. That paper reports running up to 852 times faster than YALMIP on synthetic data ($N=10^4$, $d=10^2$) and over 400 times faster on a9a. It is an upper bound on quality, not a competitor.
The minimax competitor is Local SGDA from Federated Minimax Optimization, run on the same joint saddle problem with both players updated locally and a tuned step-size ratio.
The group-reweighting competitors are DRFA, FGDRO and AD-GDA in the deep settings. On iWildCam, FGDRO reports macro F1 of 0.5201, against 0.4964 for FedAvg and 0.4200 for DRFA (FGDRO). On COOS7, AD-GDA reports shrinking the cross-microscope accuracy gap from 24% under CHOCO-SGD to under 2% (AD-GDA). For these methods we do not expect to beat them on group-shift metrics. The bar is to stay within noise of them there while beating them clearly under shared-budget feature perturbation.
Two ablations isolate the key ingredient. The first treats $\lambda$ as an ordinary parameter updated locally in FedAvg. The second fixes $\lambda$ at a grid-searched value. The grid search gets the same total compute as our single run, so a five-point grid means five times shorter runs, or our method trained for five times fewer rounds.
Why not just…?
Why not just run FedAvg with local adversarial training at a hand-tuned fixed $\lambda$? This is the real threat. At the optimal price, the penalty form and the constrained shared-ball form share a solution, so a well-tuned fixed $\lambda$ recovers our answer. What our method adds is hitting a specified radius $\varepsilon$ in one run and tracking it as $\theta$ changes. The fixed-$\lambda$ ablation at matched compute settles whether that matters. If the grid matches us on certified worst-case loss at equal total compute across all benchmarks, the contribution reduces to convenience plus the drift analysis, and we will report it that way.
Why not just treat $\lambda$ as one more trainable parameter? Local gradients in $\lambda$ push each client toward its own budget, which silently turns the shared ball into per-client balls. The local-$\lambda$ ablation tests this directly. We predict its shared-budget worst-case loss degrades as $K$ grows while ours stays flat. If no such degradation appears, the freezing argument is wrong and we will say so.
Why not just use group reweighting such as DRFA or FGDRO? Reweighting only moves mass between existing clients. It cannot protect against perturbations of the features within a client. The WILDS paper found that many domain-generalization heuristics fail to beat ERM on 8 of 10 benchmarks (WILDS), which warns against assuming any one robustness notion transfers. On natural group shifts like iWildCam, reweighting may well win, and we expect to report that.
Why not just compress messages instead of adding local steps? Compression shrinks message size but not the number of synchronization rounds. AD-GDA still gossips every iteration. Our scheme is compatible with compression, and we will stack the two in one run rather than choose between them.
Proposed Experiments
Linear, exactly certifiable. We use a9a, w8a, synthetic DRLR at $N=10^4$, $d=10^2$, and the three UCI noise benchmarks from Bai et al.. Clients have Dirichlet feature skew and differing attribute-noise levels, so that fragility is uneven across clients. The primary metric is the exact shared-budget worst-case loss, computed from the dual at the returned $\theta$ with $\lambda$ re-optimized. We also report gap to the pooled LP-ADMM optimum and communicated floats.
The decisive check sweeps $K\in\{1,4,16,64,256\}$ and compares the frozen-price and local-price variants. The shared-ball property holds only if our worst-case loss stays flat in $K$ while the local-price variant drifts toward AD-LPMM's solution. A second check verifies that the realized spent budget $\sum_k w_k\bar c_k$ lands within 5% of $\varepsilon$ in every run.
Deep. We use CIFAR-10 under Dirichlet splits with per-client input corruption, plus COOS7 and Camelyon17. We evaluate with a shared-budget attack that runs its own price search across the pooled test set, alongside per-client-budget attacks and the standard group metrics. Communication rounds are counted to a target worst-case accuracy against Local SGDA.
Decentralized. We gossip $(\theta,\lambda)$ on ring and random graphs and measure round overhead relative to plain decentralized consensus. This tests whether the $\sqrt{n}$ coupled-constraint penalty from Decentralized Optimization with Coupled Constraints is visible for one-dimensional coupling.
References
- Data-Driven Optimal Transport Cost Selection For Distributionally Robust Optimization
- Distributionally Robust Logistic Regression
- A First-Order Algorithmic Framework for Distributionally Robust Logistic Regression
- Distributionally Robust Federated Learning: An ADMM Algorithm
- Distributionally Robust Federated Averaging
- Communication-Efficient Federated Group Distributionally Robust Optimization
- Communication-Efficient Distributionally Robust Decentralized Learning
- Accelerated Dual Method for Distributed Optimization: An Inexact-Gradient View of Local Updates
- Federated Minimax Optimization: Improved Convergence Analyses and Algorithms
- Decentralized Optimization with Coupled Constraints
- WILDS: A Benchmark of in-the-Wild Distribution Shifts