PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.05915v1cs.LGmath.OC

TL;DR

The paper investigates whether large-stepsize FedAvg converges when devices perform different numbers of local updates, and how device heterogeneity affects its convergence bound. The paper analyzes FedAvg for multinomial logistic regression with heterogeneous local updates under linear separability. For FedAvg with large stepsizes and heterogeneous devices, objective values converge to zero at O(1/R); for R ≫1, optimality gap behaves as O(1/(RTavg)).

  • Problem

    The paper investigates whether large-stepsize FedAvg converges when devices perform different numbers of local updates, and how device heterogeneity affects its convergence bound.

    Source: §I · p. 1

  • Method

    The paper analyzes FedAvg for multinomial logistic regression with heterogeneous local updates under linear separability.

    Source: §I · p. 1, §II · p. 2, §V · p. 6

  • Results

    For FedAvg with large stepsizes and heterogeneous devices, objective values converge to zero at O(1/R); for R ≫1, optimality gap behaves as O(1/(RTavg)).

    Source: §I · p. 1

  • Takeaways & Limitations

    For sufficiently many rounds, the convergence rate is governed by the average number of local steps across devices rather than persistent heterogeneity effects.

    Source: §I · p. 1, §V · p. 6

    The analysis is limited to linearly separable data; non-separable data and regularized losses are identified as future work.

    Source: §V · p. 6

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper asks whether FedAvg’s large-stepsize convergence survives heterogeneous local-update counts, and reports stability for any stepsizes with asymptotically vanishing heterogeneity.

  • In federated learning, local updates can create drift from data and computational heterogeneity, while existing approaches typically guarantee convergence only with sufficiently small problem-dependent stepsizes.Source: §I · p. 1
  • Prior work found that gradient descent can converge with arbitrarily large stepsizes on linearly separable logistic-regression data, departing from classical small-stepsize analyses.Source: §I · p. 1
  • The paper investigates whether large-stepsize FedAvg converges when devices perform different numbers of local updates, and how that heterogeneity affects its convergence bound.Source: §I · p. 1
  • For linearly separable logistic regression, FedAvg is stable with any stepsizes and its objective values converge to zero at O(1/R).R is the number of communication rounds.Source: §I · p. 1
  • For R ≫ 1, the optimality-gap bound is O(1/(R T_avg)), with device heterogeneity’s effect on the convergence rate vanishing asymptotically.T_avg is the average number of local update steps per communication round.Source: §I · p. 1
  • Numerical experiments corroborate the asymptotic insensitivity to device heterogeneity, and the analysis extends prior work to multinomial logistic regression.Source: §I · pp. 1–2

II. PROBLEM SETUP AND FEDAVG ALGORITHM

The setup trains a multinomial linear classifier with FedAvg, allowing devices to take different numbers of local updates per communication round. The analysis assumes bounded feature norms and globally linearly separable data.

  • The model is a K-class linear classifier parameterized by a matrix W, trained using multinomial logistic loss over device-local datasets.Source: §II · p. 2
  • FedAvg lets devices compute local updates and sends their accumulated differences to a server for aggregation with a global stepsize.Source: §II · p. 2
  • Devices may perform different numbers of local steps T_i in each round; when every T_i equals 1, FedAvg reduces to centralized gradient descent on the global objective.Source: §II · p. 2
  • Prior large-stepsize FedAvg analysis covered only homogeneous devices and binary classification, while much existing heterogeneous-device analysis focuses on small stepsizes.Source: §II · p. 2
  • The analysis assumes feature norms are bounded and the full training data are globally linearly separable, implying the local and global loss infima are zero.Source: §II · p. 2

III. LARGE STEPSIZE CONVERGENCE ANALYSIS

Under Assumptions 1–2, FedAvg’s average risk converges at O(1/R) for arbitrary positive stepsizes and any distribution of local update counts. After entering a stable phase, the objective decreases monotonically, with its asymptotic rate governed by T_avg rather than device heterogeneity.

III. LARGE STEPSIZE CONVERGENCE ANALYSIS

  • O(1/R): the average risk converges to zero for arbitrary positive global and local stepsizes and any distribution of device update counts.The bounds also show that larger stepsizes can amplify the effect of heterogeneity.Source: §III · p. 3
  • For homogeneous devices with binary classification, the paper reports a tighter bound than [20, Theorem 4.1], attributing the improvement potentially to its proof structure.The comparison is for the special case T_i=T and K=2.Source: §III · p. 3
  • O(1/(rT_avg)): in the stable phase, the last-iterate objective converges at a rate dominated by the average local update count, as heterogeneity effects vanish asymptotically.The stable phase follows once the objective falls below a threshold; the theorem imposes a sufficient but conservative heterogeneity condition.Source: §III · p. 3
  • Stable-phase convergence is observed in practice even without the stated heterogeneity condition.The bound is described as sufficient but conservative.Source: §III · p. 3

A. Proof of Theorem 3

The proof of Theorem 3 constructs a reference point and bounds progress using properties of the local losses and the server update. Its proof structure yields a tighter bound than [20, Theorem 4.1] while also handling heterogeneous devices.

A. Proof of Theorem 3

  • The proof measures the iterate’s distance from a constructed reference point U=U1+U2+U3 and represents the server update as the round-to-round change in W.The analysis uses the decomposition of the server update to control progress.Source: A. Proof of Theorem 3 · pp. 3–4
  • Convexity, smoothness, and a separability-based lemma bound the local loss at U1 and contribute to the bound on A1.The proof uses the lemma with a chosen α to obtain a bound on Li(U1) for every device.Source: A. Proof of Theorem 3 · p. 4
  • The proof bounds the residual term E(r), combines the resulting inequalities, and iterates the recurrence to obtain the average-risk bound.It then applies a square-root step and triangle inequality to derive the companion bound.Source: A. Proof of Theorem 3 · p. 4
  • A different reference point and a round-by-round progress recursion yield a tighter bound than [20, Theorem 4.1] that also covers heterogeneous devices.The authors identify these proof modifications as enabling both properties.Source: A. Proof of Theorem 3 · p. 4

B. Proof of Theorem 4

Theorem 4’s proof establishes stable-phase monotonicity by induction, using one-step progress to keep the objective from increasing after the required threshold is reached.

B. Proof of Theorem 4

  • The argument uses Gi(W)≤Li(W) to maintain the conditions needed for the induction across rounds.This inequality is stated as the starting point for proving the induction claim.Source: B. Proof of Theorem 4 · pp. 4–5
  • The proof establishes its induction base from the theorem’s initial loss condition and bounds one-step progress using a descent-lemma argument on log L(W(r)).The server-side update is used to analyze the transition from W(r) to W(r+1).Source: B. Proof of Theorem 4 · pp. 4–5
  • When the loss is below the stated threshold, the proof bounds log-loss curvature and applies Cauchy–Schwarz to show the next objective value does not increase.The induction then carries this monotonicity forward to subsequent rounds.Source: B. Proof of Theorem 4 · p. 5

C. Proof of Corollary 6

The proof of Corollary 6 uses monotonicity and a telescoping argument to establish the stated bound.

C. Proof of Corollary 6

  • Monotonicity of L(W(r)) lets the proof apply a telescoping argument to establish the corollary’s bound.The derivation first divides by the product of consecutive objective values.Source: C. Proof of Corollary 6 · p. 5

IV. NUMERICAL EXPERIMENTS

The experiments use a synthetic, linearly separable five-class dataset with label-imbalanced client partitions.

IV. NUMERICAL EXPERIMENTS

  • The synthetic task uses 12-dimensional inputs, five classes, and 5,000 samples, with a label-imbalanced split assigning each client samples from at most two classes.The data are constructed so the classifier satisfies Assumptions 1 and 2 with γ = 0.001.Source: §IV · p. 5

A. Effect of Heterogeneous Local Epochs

The experiment compares heterogeneous and homogeneous local-update schedules with the same average of 27 updates per round. Heterogeneity lengthens the transient, but the two cases become indistinguishable asymptotically.

A. Effect of Heterogeneous Local Epochs

  • Eight clients each receive 625 samples; four perform 4 local updates and four perform 50, averaging 27 updates per round, while the homogeneous comparison uses 27 each.The local stepsize is 1, and global stepsizes 64 and 128 are tested.Source: A. Effect of Heterogeneous Local Epochs · p. 5
  • After the transient, heterogeneous and homogeneous schedules become indistinguishable, consistent with an asymptotic O(1/(TavgR)) rate independent of device heterogeneity.Both global stepsize configurations show this pattern.Source: A. Effect of Heterogeneous Local Epochs · p. 6
  • The heterogeneous schedule has a longer transient with larger fluctuations before entering a stable monotonic regime.The passage says this behavior is consistent with Theorem 3, which predicts slower convergence for heterogeneous devices.Source: A. Effect of Heterogeneous Local Epochs · p. 6

B. Effect of Large Local Steps under Label Imbalance

The experiment varies the common number of local steps under label imbalance and compares global stepsizes. Larger local-step counts and global stepsizes 64 or 128 are associated with faster convergence in the reported settings.

B. Effect of Large Local Steps under Label Imbalance

  • The comparison uses a common local-step count T ∈ {1, 4, 16, 64} for all clients and runs FedAvg for 50,000 communication rounds.The tested global stepsizes are 1, 64, and 128, with local stepsize 1.Source: B. Effect of Large Local Steps under… · p. 6
  • At sufficiently large R, all configurations have convergence rates close to O(1/(TR)); increasing T leads to faster convergence, with FedAvg evaluated over R = 50,000 communication rounds.Source: B. Effect of Large Local Steps under… · p. 6
  • Global stepsizes 64 and 128 significantly accelerate convergence compared with the significantly slower baseline global stepsize of 1.The local stepsize is 1 in all configurations.Source: B. Effect of Large Local Steps under… · p. 6

V. CONCLUSION

Under linear separability, the paper extends large-stepsize FedAvg analysis to heterogeneous devices and concludes that heterogeneity vanishes asymptotically, with the rate dominated by average local steps.

V. CONCLUSION

  • The analysis extends large-stepsize FedAvg to heterogeneous devices under a linear separability condition.The conclusion identifies non-separable data and regularized losses as directions for future work.Source: §V · p. 6
  • The conclusion states that device heterogeneity vanishes asymptotically and that convergence is dominated by the average number of local steps across devices.The paper says numerical experiments validate these findings.Source: §V · p. 6

APPENDIX III MISSING PROOFS OF THEOREM 4

APPENDIX V AUXILIARY LEMMAS

  • Under Assumptions 1 and 2, the loss function L(W) is 1/2-smooth.Source: Appendix V · p. 9

A. Hard Sample Placement on Heterogeneous Devices

With average local work matched, hard-sample placement changes convergence speed according to gradient alignment, while minibatch local SGD becomes asymptotically indistinguishable across homogeneous and heterogeneous update counts. Larger minibatches shorten the transient in most cases but do not change the asymptotic rate.

A. Hard Sample Placement on Heterogeneous Devices

  • hardHighT converges fastest, homo is intermediate, and hardLowT is significantly slower as step-count weights align with or oppose gradient deviations.The comparison uses the same data and Tavg = 57; alignment, rather than Tavg alone, governs the observed rate ordering.Source: Figure 3 · p. 10, A. Hard Sample Placement on… · p. 10

B. Effect of Large Stepsize under Minibatch SGD Local Updates

Loading 2610.05915v1…