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.LGOct 5, 2026

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

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

Organizations: Department of CSE, The Chinese University of Hong Kong, Hong Kong SAR · Department of SEEM, The Chinese University of Hong Kong, Hong Kong SAR · Department of ECE, University of Minnesota, Minnesota, USA

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.

Figures & tables

Fig. 1: Convergence of FedAvg with homogeneous (“homo. device”:

T_{i}=27

for all devices) and heterogeneous (“hete. device”:

T_{i}=4

for device

1

4

T_{i}=50

for device

5

8

) devices. Both configurations share the same average

T_{\text{avg}}=27

with global/local stepsizes: (Left)

\eta_{g}=64,\eta_{l}=1

, (Right)

\eta_{g}=128,\eta_{l}=1

Fig. 2: Effects of the number of local steps

T

. All devices perform the same number of local epochs

T\in\{1,4,16,64\}

, with global stepsizes

\eta_{g}\in\{1,64,128\}

and local stepsize

\eta_{l}=1

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Fig. 3: Effect of hard-sample placement under heterogeneous local step counts. All configurations share the same set of data and the same average local work

T_{\mathrm{avg}}=57

. The hardest samples are assigned to either straggler clients with

T_{i}=13

( hardLowT ), fast clients with

T_{i}=101

( hardHighT ) under the heterogeneous setup, or arbitrarily for the homogeneous setup where all

T_{i}=57

( homo ). We use the global stepsizes

\eta_{g}\in\{32,64\}

, local stepsize

\eta_{l}=1

Fig. 4: Effect of heterogeneous local update steps under minibatch SGD. All devices perform local updates using minibatches of size

b\in\{5,25,125\}

, with global stepsizes

\eta_{g}\in\{32,64\}

and local stepsize

\eta_{l}=1

. Two configurations are compared at a matched average

T_{\mathrm{avg}}=57

: homogeneous (

T_{i}=57

for all devices) and heterogeneous (

T_{i}=13

for devices 1-4,

T_{i}=101

for devices 5-8).

Explore similar work

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
Jun 21, 2026Shengchao Zhao, Yongchao LiuFederated Learning Fedavg
School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China
Convergence Analysis of Sequential Federated Learning on Heterogeneous Data
Nov 6, 2023Yipeng Li, Xinchen LyuFederated Learning Convergence
National Engineering Research Center for Mobile Network Technologies Beijing University of Posts and Telecommunications Beijing, 100876, China
Statistical Limits and Efficient Algorithms for Differentially Private Federated Learning
May 18, 2026Arnab Auddy, Xiangni Peng, Subhadeep PaulFederated Learning Federated Averaging
Department of Statistics · The Ohio State University

Jun 21, 2026, cs.LGJ/K move · Enter open · S save

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

Shengchao Zhao, Yongchao Liu

School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China

Federated Learning Fedavg Stochastic Gradient Descent Variance Reduction Convex Optimization

Open paper AskPDF arXiv

Federated learning (FL) is an emerging distributed machine learning paradigm that enables local devices to jointly train a global model while keeping data decentralized and private. We propose a variance-reduction based algorithm, VRA-FedSGD, for FL in the presence of heavy-tailed gradient noise and communication noise, where these noises are prevalent in large-scale machine learning over wireless networks and Internet of Things deployments. VRA-FedSGD employs a momentum variance reduction technique together with a nonlinear mapping to mitigate heavy-tailed gradient noise, and uses a variance-reduced aggregation mechanism to suppress heavy-tailed communication noise. In the mean sense, VRA-FedSGD achieves a convergence rate of {\small

\mathcal{O}\left(K^{-(p-1)/(2p-1)}\right)

} for nonconvex objective functions, where

p

is the tail index of heavy-tailed noise. In the almost sure sense, VRA-FedSGD achieves a convergence rate of

\tilde{\mathcal{O}}\left(K^{-(1-1/(p-ε))}\right)

for strongly convex objective functions, where

ε

is an arbitrarily small constant. Simulated experiments on a logistic regression problem with real-world data verify the effectiveness of VRA-FedSGD.

Abstract

Explore similar work

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

Convergence Analysis of Sequential Federated Learning on Heterogeneous Data

Statistical Limits and Efficient Algorithms for Differentially Private Federated Learning