CS Paper Radar

Faster to the Wrong Answer: The Price of Local Updates in Federated Optimization

Molly Wang

cs.LG ·submitted 2026-11-18 08:49 UTC · v1

Abstract

Local computation can improve the conditioning of federated updates but may also introduce bias, causing their fixed point to differ from the global minimizer. We characterize the minimum worst-case bias achievable under a prescribed conditioning bound. We consider strongly convex quadratic client objectives with Hessian eigenvalues in $[μ,L]$ and local updates represented by a shared positive spectral filter. Client heterogeneity is measured by the root-mean-square gradient at the global minimizer. For a uniform surrogate condition number bounded by $χ\in[1,L/μ]$, we establish the exact worst-case bias per unit heterogeneity, $(L-μχ)/(2μL\sqrtχ)$, and show that local gradient descent with sufficiently small step sizes and proximal updates attain this bound. Our analysis reduces populations of arbitrary dimension, including noncommuting Hessians, to distributions over scalar curvatures. This reduction provides optimality certificates and worst-case constructions involving at most three scalar clients. We further extend the sharp proximal bias bound to smooth strongly convex objectives beyond quadratics and quantify the error introduced by inexact local solves.

Comment
18 pages, 1 figure; includes supplementary proofs and reproduction code

Closest papers

Nearest neighbours by meaning across the whole index.

FedMIX-P: Mixing Local and Global Preconditioners for Federated Vision and Language Model Training

cs.LG cs.AI ·2026-10-01 ·Junkang Liu
similarity 0.67
Abstract

Adaptive preconditioners accelerate model training, but heterogeneous client geometries can bias federated updates even when gradients are evaluated at the same model. Round-start synchronization alone cannot prevent this mismatch from reappearing during local training. We propose \texttt{FedMIX-P}, which mixes shared and local preconditioners at every local step, retaining local adaptation while reducing mean-squared operator mismatch by a factor of $λ^2$. For smooth nonconvex objectives with stochastic gradients and partial participation, we establish an $O(R^{-1/2})$ stationarity bound using suitable stepsizes and a horizon-dependent mixing weight, without requiring local preconditioners to converge to one another. A two-client counterexample shows that fixed positive mixing can preserve a nonstationary fixed point. The theory covers bounded linear symmetric positive-definite preconditioners. Experiments with SOAP, Sophia, and Muon variants across vision and language tasks show improvements over corresponding local optimizers, including accuracy gains of up to $19.47$ percentage points and lower validation loss for 60M--350M language models. Full nonlinear and momentum-based updates require separate analysis.

0.30

SCAFFOLD under Hessian Similarity: Sharp Convergence Rates

cs.LG math.OC ·2026-10-26 ·Zhirayr Tovmasyan, Slavomír Hanzely, Egor Shulgin, Peter Richtárik, Sebastian U. Stich
theory similarity 0.67
Abstract

One of the main challenges of federated learning is heterogeneous data split among the clients, leading to biased local updates called client drift. The SCAFFOLD algorithm (Karimireddy et al., 2020) corrects client drift with control variates, but its relation to the similarity of client data is not yet fully understood: the original similarity-based guarantees cover only quadratics with a stronger second-order similarity assumption, and a follow-up weakly convex analysis (Luo et al., 2025) obtains a $\sqrt{Lδ}$ dependence for $L$-smooth losses with averaged Hessian similarity $δ$. We analyze SCAFFOLD with minibatch-based control variates and establish linear dependence on Hessian similarity beyond quadratics, for both convex and nonconvex objectives. In particular, for convex objectives with exact gradients, $R$ SCAFFOLD rounds with $K$ local steps lead to an objective gap of order $(L/K+δ)D_0^2/R$, where $D_0$ is the initial distance to a minimizer. When $K=Θ(L/δ)$, it improves the minibatch SGD rate by a factor $Θ(L/δ)$. For nonconvex objectives, we prove an analogous stationarity guarantee under uniform Hessian similarity for a client-selection variant. In both settings, we extend these guarantees to stochastic gradients and prove matching lower bounds for the analyzed methods with constant local stepsizes. We also show that, under partial participation, even identical clients need not obtain the full communication benefit of additional local steps.

0.15

Personalized Projected Ascent for Federated Stackelberg Optimization

cs.LG ·2026-10-15 ·M Yashwanth, Sharannya Ghosh, Saikiran Bulusu, Anirban Chakraborty
similarity 0.66
Abstract

Federated minimax problems, such as distributionally robust optimization and adversarial training, include an inner maximization variable built from each client's local data. These variables differ in meaning and dimension from one client to the next, so averaging them across clients, as standard federated minimax methods do, is ill-posed. We therefore study a federated minimax problem where the minimization variable $\mathbf{x}$ is shared and aggregated, while each client retains the maximization variable $\mathbf{y}_i$ (personalized). Because these applications constrain $\mathbf{y}_i$ to a compact convex set, we analyze projected ascent directly. We show that, in the nonconvex-concave regime, this projected personalized scheme attains the standard sublinear rate. In the nonconvex-PL regime, however, it hits a stepsize-invariant noise floor due to stochastic $\mathbf{y}_i$ updates. To mitigate this, we propose VR-SGDA, incorporating a variance-reduced ascent step where each client maintains a private variable snapshot. By evaluating current and snapshot gradients on the same sample, the constant variance is replaced by a vanishing drift under a two-timescale regime. VR-SGDA eliminates the noise floor, attaining sublinear leading rates while preserving personalization and projection. Experiments on subpopulation-robustness and NLP adversarial training confirm both the worst-group robustness benefits and the two-timescale tracking mechanism.

0.13

Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds

cs.LG math.OCstat.ML ·2026-09-12 ·Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour
theoryhot direction similarity 0.65
Abstract · 6 pages, 2 figures

This work addresses decentralized online Riemannian optimization on Hadamard manifolds. Prior work under geodesic convexity (g-convexity) may require curvature information in the optimization analysis, typically through a finite lower bound on the sectional curvature. Curvature may also enter the step size or contraction factor of tangent-space Riemannian consensus schemes. In this work, we relax the curvature dependence for a narrower class of horospherical convex (h-convex) functions. We study Distributed Riemannian Online Gradient Descent (D-ROGD), which combines local Riemannian h-subgradient updates with an implicit Fréchet-mean consensus. For h-convex and strongly h-convex local objectives, we establish $O(\sqrt{T})$ and $O(\log T)$ static regret, respectively, matching the corresponding Euclidean rates with respect to $T$, with network dependence governed solely by the spectral gap. To our knowledge, these are the first curvature-independent regret guarantees for decentralized online optimization on Hadamard manifolds. Experiments on hyperbolic embeddings corroborate the predicted rates, with no observable degradation due to curvature.

0.35

Characterizing Client-Independent Stationary Bias for SCAFFOLD and FedAvg in Federated Learning

cs.LG math.ST ·2026-08-27 ·Yi-Ping Tang, Guan-Ju Peng
similarity 0.64
Abstract

Even when all clients optimize the same strongly convex objective, the global model parameters produced by constant-step federated learning may still have a stationary mean that differs from the minimizer. Does increasing the number of clients eliminate this bias, or can some components persist? Answering this question clarifies the limits of client averaging. To this end, we study two federated learning algorithms, \Scaf{} and matched \FedAvg{}, under full participation, a sufficiently smooth objective, and independent bounded additive gradient noise. Analyzing global stationary balance and within-round local fluctuations yields multidimensional expansions with a shared $γ/N$ term and explicit client-independent $γ^2$ coefficients, where $γ$ is the step size and $N$ is the client count. The \Scaf{} coefficient combines the ordinary local-update contribution found in \FedAvg{} with an additional persistent-control contribution. Although zero-sum controls cancel from the direct server increment, they change local second moments, which interact with third-order curvature to shift the stationary mean. For fixed dimension $d$ and local-step count $H$, a remainder of $O_{H,d}(γ^2/N+γ^3)$, uniform in $N$ for sufficiently small $γ$, identifies the second-order coefficients along arbitrary joint small-step, large-client limits after removing the shared leading term. Controlled experiments assess the predicted coefficients. In real-data analyses, finite-tail mean displacement can account for a substantial share of averaged-model parameter error, and a post-hoc comparison shows directional agreement with the derived curvature--noise structure.

0.27

Scalar Communication via Random Direction Refreshing for Distributed Optimization

cs.MA ·2026-10-05 ·Mohammadreza Rostami, Solmaz S. Kia
similarity 0.63
Abstract

Distributed optimization over networks requires agents to repeatedly exchange decision variables with their neighbors. When the decision dimension $d$ is large, these exchanges dominate the communication cost, which is critical for bandwidth-constrained agents. Existing remedies quantize or sparsify the exchanged vectors, yet each message still scales with $d$ and the compression error must be compensated by additional states. To address this limitation, we propose a scalar-communication mechanism in which every neighbor message carries a single real number regardless of $d$. Agents regenerate a common random direction from a shared seed, transmit only the inner product of their state with that direction, and act on the resulting rank-one surrogate of their neighbors' states while retaining full local gradients. We develop and analyze the mechanism for an existing continuous-time distributed optimization algorithm. For strongly convex local costs with Lipschitz gradients, we show that the optimizer remains the unique consensus equilibrium, that a fixed direction admits spurious equilibria, and that refreshing the direction at a sufficiently high rate yields exponential mean-square and almost-sure convergence with constant gains and no residual error. The framework admits any isotropic fixed-norm direction distribution, including Rademacher, scaled-coordinate, and sphere-normalized Gaussian directions; all three attain lower fresh-encoding variance than unnormalized Gaussian directions. The effects of the direction distribution and the refresh interval are illustrated in~simulations.

0.53

Adaptive Federated Optimization Across Smooth and Nonsmooth Regimes

cs.LG math.OC ·2026-10-29 ·Zimeng Wang, Ali Dadras, Alp Yurtsever
similarity 0.63
Abstract

AdaGrad-style methods can simultaneously adapt to both the order and constants of smoothness in centralized optimization. However, existing extensions to federated optimization with heterogeneous client objectives and multiple local steps require the smoothness order to be specified in advance. We address this limitation with AdaFed, a federated method that adapts across several regimes under a single choice of parameters. In the deterministic setting, AdaFed achieves an $O(1/T)$ convergence rate for both smooth nonconvex and smooth convex objectives, and an $O(1/\sqrt{T})$ rate for Lipschitz nonsmooth convex objectives up to logarithmic factors. Under a light-tailed stochastic-gradient noise assumption, these guarantees extend to the stochastic setting with additional logarithmic factors and noise-dependent terms. Experiments across the three problem classes further support our theoretical findings.

0.22

KKT-Perturbation-Aware Communication for Fully Distributed Online Convex Optimization with Nonseparable Coupling

cs.LG ·2026-11-09 ·Zhaoye Pan, Tao Li, Yunjie Guo, Guanpu Chen
similarity 0.63
Abstract

Nonseparable costs and coupled constraints in distributed online convex optimization often arise when system performance and operational constraints depend on the joint configuration of all agents and cannot be decomposed into individual contributions. Such nonseparability leads to fully distributed decision-making with challenging partial local information, where each agent evaluates its local primal-dual update using estimated global information via a local belief of the joint action and the shared Lagrange multiplier to be exchanged with neighbors. While the belief consensus established by prior works ensures no-regret learning, exchanging beliefs comprising full-dimensional primal and dual states at every round imposes a communication overhead that scales with both the joint decision dimension and the network size. Existing event-triggered schemes typically activate communication according to state variation or consensus error. Under nonseparable coupling, however, errors of equal magnitude can produce markedly different perturbations after passing through the KKT operator. We therefore propose a randomized KKT-perturbation-aware communication mechanism, where the triggering of each agent's primal and dual communication channels depends on their impact on the KKT operator. The proposed mechanism transfers the adaptive-sampling principle of coordinate descent from allocating computation across decision blocks to allocating communication across information channels: channels with larger estimated perturbations receive greater priority for refresh. Under standard regularity assumptions, the resulting algorithm achieves $O({T}^{2/3})$ expected static regret and $O({T}^{2/3})$ expected cumulative constraint violation. Numerical experiments demonstrate improved learning and constraint-enforcement performance per transmitted bit over belief consensus baselines.

0.15