CS Paper Radar

Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices

Hok Fong Wong, Hoi-To Wai, Chung-Yiu Yau

cs.LG math.OC ·submitted 2026-10-05 07:31 UTC · v1
published

Abstract

This paper revisits the distributed learning problem for training a multinomial logistic regression model with the Federated Averaging ($\texttt{FedAvg}$) algorithm. We concentrate on a scenario with arbitrarily large stepsizes and heterogeneous update rules where the devices may perform a different number of local updates in each round. We show that, with linearly separable data, $\texttt{FedAvg}$ is stable with any stepsizes and the objective values converge to zero at the rate of ${\cal O}(1/R)$, where $R$ is the number of communication rounds. Our result also demonstrates that the effects of device heterogeneity vanish asymptotically. For sufficiently large $R$, the objective values decrease monotonically and is bounded by ${\cal O}( 1 / (R T_{\rm avg}))$, where $T_{\rm avg}$ is the average number of local update steps per communication round across devices. Numerical experiments support our findings.

Comment
11 pages, 4 figures, accepted to the 65th IEEE Conference on Decision and Control

Closest papers

Nearest neighbours by meaning across the whole index.

CTP-FL: Common-Trajectory Gradient Prediction for Federated Learning

cs.LG cs.AI ·2026-09-28 ·Junkang Liu
similarity 0.66
Abstract

Communication-efficient federated optimization commonly spends several gradient evaluations between server updates. Existing local-update methods use this computation to advance an independent model on each client. Under heterogeneous data, however, these models evaluate gradients at different locations, making the aggregated update difficult to interpret as a gradient of the global objective. We study an alternative use of the same computation budget: \emph{evaluate the global objective along a shared, predicted path}. We propose Common-Trajectory Predictive Federated Learning (\texttt{CTP-FL}). At each round, all clients construct the same sequence of query points from the current global model and the previous aggregated direction, evaluate $K$ stochastic gradients along this sequence, and upload their average. The server then performs a single global update. Thus, \texttt{CTP-FL} uses $K$ mini-batch gradients per client and one model-sized vector in each communication direction, matching the per-round computation and communication of full-participation FedAvg-M. Shared query points make the aggregated direction an unbiased estimator of the average \emph{global} gradient along the predicted path. The remaining discrepancy from the gradient at the current model is controlled by the path length, without assuming bounded client-gradient dissimilarity or bounded gradients. For smooth non-convex objectives, we establish an $\mathcal{O}\!\left( \sqrt{LΔσ^2/(NKR)}+LΔ/R \right)$ average-stationarity bound under full participation. The analysis isolates a testable trade-off: extending the prediction path provides more forward-looking gradient information but increases its displacement bias.

0.18

Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression

cs.LG ·2026-09-29 ·Haomin Bai, Junyan Sun, Sifan Yang, Bo Xue, Lijun Zhang
similarity 0.65
Abstract · 30 pages, 3 figures

Agnostic federated learning (AFL) seeks a model that performs reliably across $m$ heterogeneous workers, but communication remains a bottleneck. We improve communication efficiency by reducing the number of synchronization rounds via faster convergence and the communication cost per round via compression. We first propose AFL-BR, which updates the dual weights over workers using online mirror ascent with KL divergence and blockwise restarts. It achieves an $O((\log m)^{1/4}T^{-1/8})$ stationarity rate after $T$ update rounds, reducing the $m$-dependence of the synchronization rounds required for convergence from polynomial to logarithmic order. Building on AFL-BR, we develop AFL-Com by applying bidirectional compression with error feedback (EF). Instead of compressing local gradients, workers apply EF to their dual-weighted gradients, enabling direct control of the aggregated compression error under time-varying weights. We then establish an $O((δ^{-1}+(\log m)^{1/4})T^{-1/8})$ stationarity rate for AFL-Com under general $δ$-approximate compressors and improve the $δ$-dependence from $δ^{-1}$ to $δ^{-1/2}$ for additive-and-idempotent compressors with shared randomness (SR). With suitable compression levels, AFL-Com retains the same convergence rate as AFL-BR at a lower per-round communication cost, yielding reductions in total communication complexity by factors of $(\log m)^{1/4}$ with Top-$k$ and $(\log m)^{1/2}$ with Rand-$k$ and SR. Experiments validate the improved synchronization and communication efficiency of our methods.

0.51

Cordial Learning: Distributed Training with Correlated Data

cs.LG cs.AI ·2026-10-02 ·Sarah Shitrit, Ilai Bistritz
theory similarity 0.64
Abstract

We consider a distributed learning task with agents that have correlated data. Specifically, the label of an agent depends on the input of other agents for the same sample, and these inputs are also correlated. Correlated data is the reality when agents share the same environment. Existing decentralized methods, such as federated learning, ignore the structure of the problem and perform poorly on correlated data. On the other hand, centralized approaches are infeasible due to privacy and communication constraints. We introduce cordial (correlated and distributed) learning to address this gap by sharing only low-dimensional outputs between the agents while training local models to extract informative signals from peers. This distributed learning induces a game in which the loss function of each agent depends on the models of others. Assuming a linear model, we prove that cordial learning converges with probability one to a globally optimal solution, despite the nonconvex global objective. Experiments on structured multi-digit MNIST tasks demonstrate that cordial learning remains highly effective even in highly nonlinear settings.

0.18

A Multi-Step Inertial ADMM Algorithm for Federated Learning

cs.LG ·2026-10-17 ·Hao Li, Qingsong Wang, Xihong Yan, Chengcheng Yan, Deren Han
similarity 0.63
Abstract

Federated learning has recently emerged as an important paradigm for large-scale distributed model training, which can be naturally formulated as a class of distributed learning problems. The alternating direction method of multipliers (ADMM) is a widely used approach for solving such problems. However, its practical performance is often hindered by significant communication overhead and system heterogeneity. In this paper, we propose a multi-step inertial ADMM algorithm, called MiFedADMM, for federated learning. The proposed method leverages multiple historical iterates on the server side to construct a higher-order extrapolation after each aggregation to accelerate the convergence behavior. Under mild assumptions, we establish convergence results for the single-step variant of the proposed method and derive an O(1/K) convergence rate. Numerical experiments on both synthetic and real-world datasets demonstrate the effectiveness and improved performance of the proposed method compared with existing approaches.

0.14

Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Always

cs.LG ·2026-10-08 ·Safwan Labbi, Paul Mangold, Eric Moulines
theory similarity 0.63
Abstract

We study personalized federated linear stochastic approximation (LSA), a framework which notably encompass personalized temporal difference learning. In this setting, heterogeneous agents collaborate to solve distinct linear fixed-point equations, each corresponding to an agent-specific learning problem. A central open question in personalized learning is whether a single method can adapt to an unknown level of heterogeneity by converging to each agent's personalized solution in all regimes while achieving a linear speedup in the number of agents when their learning problems are sufficiently similar. We answer this question affirmatively by introducing PF-LSA, a minimalist algorithm that mixes each agent's local stochastic update with the average update across agents, at no additional computational cost relative to standard federated methods. We prove that PF-LSA, achieves best-of-both-worlds guarantees without any prior knowledge on the level of heterogeneity. Our analysis is based on a sharp decomposition of the error into consensus and disagreement components. The consensus error decays rapidly, whereas the disagreement error decays more slowly but becomes negligible in low-heterogeneity regimes.

0.24

NBCLT: Parameter-Agnostic Norm-Ball Clipped Local Training

cs.LG ·2026-10-13 ·Linxuan Pan, Shucheng Yang, Junchi Yang
similarity 0.63
Abstract

Distributed learning with multiple local steps reduces communication but aggravates drift, and its practical performance often depends on carefully tuned hyperparameters under heterogeneous data and communication constraints. At the same time, recent Muon-type optimizers suggest that constraining updates within suitable norm balls provides a simple way to encode geometric priors into optimization. In this work, we propose NBCLT (Norm-Ball Clipped Local Training), a unified local-training framework for both federated learning (FL) and decentralized learning (DL). NBCLT combines a predict-and-correct local update rule with Euclidean projections onto flexible norm balls, thereby performing norm-ball clipping under flexible update geometries while retaining a simple implementation. In FL, its problem-parameter-free regime achieves $\mathcal{O}(ε^{-2})$ communication complexity and $\mathcal{O}(ε^{-4})$ total stochastic-gradient complexity without assuming bounded heterogeneity, when the per-round local-computation budget is scaled appropriately with the horizon. In DL, NBCLT is compatible with both static and time-varying mixing and preserves these accuracy exponents under the analogous computation scaling, up to fixed network constants and an additive initialization cost.

0.20

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.62
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

Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning

cs.LG math.OC ·2026-10-11 ·Yuriy Dorn, Dmitrii Vishovan, Kirill Novoselov, Ilya Kuruzov, Darina Dvinskikh +1 more
theory similarity 0.62
Abstract

We study federated learning from continuously arriving data: each client samples from its own distribution, these distributions drift over time, and the server must track the minimizer of the clients' weighted average loss. Clients are not alike as they collect data at different rates, with different noise, and change at different speeds. The main question is how much history should each one keep? A single shared window must serve every client at once, and so makes a fast-changing client carry the sampling noise of a slow, nearly stationary one. We give each client a memory of its own, sized to that client's noise, arrival rate, and drift, and refresh it by restarted accelerated method that starts from a common point. The tracking error is then bounded by \[ R\left(\sum_m w_m^{3/2}\,σ_m\sqrt{γ_m/λ_m}\right)^{2/3}, \] for clients with weight $w_m$, noise $σ_m$, arrival rate $λ_m$, and drift rate $γ_m$ on a domain of diameter $R$. This is never worse than what any common window can achieve, and strictly better whenever noise and drift are spread unevenly across clients. A lower bound that puts different groups of clients on different drift clocks shows this quantity is the right one. The two bounds agree up to a constant whenever the clients occupy boundedly many refresh scales, and in general differ only by the sixth root of the number of scales. Experiments show the gain comes from the memory rather than from the solver: it persists across accelerated, stochastic-gradient, and one-step methods, and against a separately tuned common-memory baseline.

0.19