PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients

Aritra Mitra, Rayana Jaafar, George J. Pappas, Hamed Hassani

arXiv:2102.07053v2cs.LGcs.DCeess.SYmath.OC

TL;DR

Federated learning must handle systems heterogeneity, intermittent and compressed communication, and differing local objectives while retaining reliable convergence. The paper proposes and analyzes FedLin, showing linear convergence to the global minimum under arbitrary objective and systems heterogeneity, with tight rate analysis and sparsification results, while client-side compression leaves a non-vanishing error.

  • Problem

    The paper examines how systems heterogeneity and infrequent or imprecise communication affect convergence rates in federated learning.

  • Method

    The paper proposes and systematically analyzes FedLin, considering heterogeneous local objectives, differing client computing speeds, intermittent communication, and gradient compression.

  • Results

    FedLin guarantees linear convergence to the global minimum under arbitrary objective and systems heterogeneity, preserves linear convergence under aggressive sparsification, and has a matching lower-bound analysis.

  • Takeaways & Limitations

    FedLin provides tight linear convergence guarantees for federated learning with heterogeneous clients and communication constraints, while compression effects depend on where sparsification is applied.

  • Takeaways & Limitations

    With gradient compression at each client, FedLin is established to converge linearly only to a neighborhood of the global minimum.

Abstract

from arXiv · show

We consider a standard federated learning (FL) architecture where a group of clients periodically coordinate with a central server to train a statistical model. We develop a general algorithmic framework called FedLin to tackle some of the key challenges intrinsic to FL, namely objective heterogeneity, systems heterogeneity, and infrequent and imprecise communication. Our framework is motivated by the observation that under these challenges, various existing FL algorithms suffer from a fundamental speed-accuracy conflict: they either guarantee linear convergence but to an incorrect point, or convergence to the global minimum but at a sub-linear rate, i.e., fast convergence comes at the expense of accuracy. In contrast, when the clients' local loss functions are smooth and strongly convex, we show that FedLin guarantees linear convergence to the global minimum, despite arbitrary objective and systems heterogeneity. We then establish matching upper and lower bounds on the convergence rate of FedLin that highlight the effects of intermittent communication. Finally, we show that FedLin preserves linear convergence rates under aggressive gradient sparsification, and quantify the effect of the compression level on the convergence rate. Our work is the first to provide tight linear convergence rate guarantees, and constitutes the first comprehensive analysis of gradient sparsification in FL.

1 Introduction

Federated learning must address objective heterogeneity, systems heterogeneity, and communication constraints while seeking accurate global optimization. FedLin is proposed to resolve these challenges with linear convergence guarantees, tight rate analysis, and gradient-sparsification results.

  • Challenges: Clients’ private datasets can produce non-identical local objectives with different minima, creating objective or statistical heterogeneity.The global objective aggregates client-specific losses in an empirical risk minimization formulation.
  • Challenges: Hardware and power variability creates systems heterogeneity, including differing computation speeds, stragglers, and possible unexpected dropouts.Communication efficiency also motivates reducing both communication rounds and transmitted message sizes.
  • Challenges: FedAvg can suffer client drift under objective heterogeneity because isolated local iterates move toward clients’ own local-loss minima.This drift leads to slow convergence rates.
  • FedLin: FedLin combines gradient correction using memory, client-specific learning rates, and error-feedback mechanisms to address objective and systems heterogeneity and gradient sparsification.The framework is designed to account simultaneously for these sources of federated-learning difficulty.
  • Guarantees: For smooth and strongly convex losses, FedLin guarantees linear convergence to the global minimum under arbitrary objective and systems heterogeneity.The paper also reports matching centralized guarantees in broader smooth, convex, non-convex, and stochastic settings.
  • Guarantees: FedLin’s matching lower bound quantifies the price of intermittent communication, while gradient-sparsification analysis distinguishes server-side and client-side compression.Server compression can retain convergence to the true minimum, whereas client compression yields convergence only to a neighborhood even with error feedback.

2 Motivation

The motivation section shows that objective and systems heterogeneity can make existing methods converge quickly to incorrect surrogate minimizers or require diminishing step sizes for accuracy. FedLin is introduced to eliminate this speed-accuracy trade-off.

  • Surrogate optimization problem: FedProx and FedNova can minimize surrogate objectives whose minimizers differ from the true global minimum under client heterogeneity.FedProx exhibits this issue even when clients perform the same number of local updates; FedNova extends it to systems heterogeneity.
  • Speed-accuracy trade-off: FedNova’s normalized aggregation of accumulated local gradients is insufficient by itself to resolve the speed-accuracy trade-off.The analysis attributes the mismatch to heterogeneity in client objectives rather than only differences in computing speeds.
  • Speed-accuracy trade-off: A fixed positive learning rate cannot generally eliminate FedProx or FedNova convergence error, while diminishing rates slow convergence.For FedProx, lower η reduces error but sacrifices convergence speed; analogous behavior occurs for FedNova.
  • Numerical illustration: FedLin converges rapidly to the true minimum despite heterogeneity in clients’ loss functions and operating speeds.The simulations contrast this behavior with the incorrect minimizers and speed-accuracy trade-offs observed for FedProx and FedNova.

3 Proposed Algorithm: FedLin

FedLin uses remembered global-gradient information, client-specific learning rates, and error feedback to coordinate heterogeneous local updates. Its design targets objective and systems heterogeneity while supporting gradient sparsification.

  • Exploiting memory: FedLin guides each client’s local updates with a remembered global gradient and corrects it using local gradients.The correction subtracts the stale local gradient at the round’s starting model and adds the client gradient at the current local iterate.
  • Client-specific learning rates: Client-specific learning rates scale inversely with local-step counts to compensate for heterogeneous client drift.The drift bound scales linearly with τi, and ηi ∝ 1/τi is also necessary according to the cited theorem.
  • Error feedback: Error feedback at clients and the server compensates for gradient coordinates omitted by sparsification.Clients add accumulated compression error to subsequent gradients before compressing them again.
  • Overall workflow: Each round averages client models, broadcasts the new global model, and exchanges compressed gradient information for the next local updates.The compression levels δc and δs control client-side and server-side sparsification, respectively.
  • Fixed-point property: FedLin preserves the global optimum as a fixed point, unlike SCAFFOLD in general because stale control variates can move clients away from that optimum.Without sparsification, FedLin’s client iterates stop evolving once the global model reaches x∗.

4 Matching Centralized Rates under Objective and Systems Heterogeneity

FedLin is analyzed under objective and systems heterogeneity, with results covering deterministic, stochastic, convex, non-convex, and intermittent-communication settings. For smooth strongly convex losses, it achieves linear convergence to the global minimum, while local computation creates a quantified communication–rate trade-off.

  • FedLin matches centralized convergence guarantees, up to constants, across strongly convex, convex, and non-convex settings despite arbitrary objective and device heterogeneity.
  • FedLin guarantees linear convergence to the global minimum for smooth strongly convex objectives, resolving the speed-accuracy conflict.
  • O(1/T) is obtained in the noisy strongly convex case under unbiased gradients with bounded variance, matching centralized SGD up to constants.
  • The Price of Intermittent Communication: H local steps reduce communication by a factor of H relative to centralized training, while the convergence exponent is slower by a factor of H.
  • The Price of Intermittent Communication: More local steps accelerate convergence in homogeneous settings, but objective heterogeneity requires η ∝1/H, washing out that advantage.
  • The Price of Intermittent Communication: Theorem 6 supplies a matching lower bound, showing tight linear convergence analysis and instances where η ∝1/H is necessary for convergence to x∗.

5 Impact of Gradient Sparsification at Server

The paper studies server-side gradient sparsification separately from client-side compression. For smooth strongly convex objectives, FedLin retains linear convergence to the true minimum under server sparsification, with error-feedback improving the rate’s dependence on compression.

  • The server-side analysis isolates compression at the server by assuming client gradients are not sparsified, δc = 1.
  • Server sparsification can preserve linear convergence to the global minimum without error-feedback, even when the server transmits a single gradient component.
  • δs = 1 recovers Theorem 1, while stronger server compression produces a convergence-rate trade-off inversely proportional to δs.
  • Error-feedback improves the convergence rate by improving its dependence on the server compression parameter δs.

6 Impact of Gradient Sparsification at Clients

The client-side analysis assumes unsparsified server communication and introduces bounded gradient dissimilarity. With error-feedback, FedLin generally converges linearly only to a neighborhood whose size depends on objective heterogeneity, whereas D = 0 yields exact convergence.

  • Client-side sparsification is analyzed with δs = 1 and a bounded gradient dissimilarity assumption.
  • With error-feedback, FedLin guarantees linear convergence to a neighborhood of the global minimum under client sparsification.
  • The neighborhood size scales linearly with D, the measure of objective heterogeneity.
  • When D = 0, the iterates converge exactly to the global minimum, which is also the minimum of every local objective.
  • Unlike server-side sparsification, client-side compression injects more errors and requires both error-feedback and the bounded gradient dissimilarity assumption for the stated guarantee.
  • The sparsification results are limited to the strongly convex and smooth setting, with combined server-and-client compression identified as an extension.

7 Experimental Results

FedLin is evaluated on synthetic least-squares problems with controlled objective and systems heterogeneity. Server-side sparsification preserves exact linear convergence, whereas client-side sparsification introduces an error that worsens with compression and heterogeneity.

  • Experimental setup: The experiments use 20-client synthetic least-squares regression with heterogeneous local objectives and varying numbers of local iterations.Each client has A_i ∈ R^500×100, b_i ∈ R^500, and local steps sampled uniformly from [2, 100].
  • Server-side sparsification: Increasing server-side sparsification slows convergence at α = 10 while preserving convergence accuracy.The comparison includes unsparsified server communication, TOP-50, and TOP-25 operators.
  • Server-side sparsification: At α = 50, server-side sparsification leaves both convergence speed and accuracy unchanged across the tested sparsification levels.This contrasts with the slower rates observed at α = 10.
  • Server-side sparsification: Server-side TOP-50 and TOP-25 sparsification preserve linear convergence to the global minimum under objective and systems heterogeneity.The server-side experiments use δ_s ∈ {2, 4}, with no client-side sparsification or error-feedback.
  • Client-side sparsification: Client-side TOP-75 and TOP-50 sparsification yield linear convergence with a non-vanishing error that increases with compression and objective heterogeneity.The client-side tests compare δ_c ∈ {4/3, 2} at α = 1 and α = 10.

8 Conclusions and Open Problems

The paper presents FedLin as a framework for linear convergence under objective, systems, and communication heterogeneity, while identifying unresolved questions about local computation and client-side compression. Its conclusions also highlight open directions involving stochastic optimization and privacy.

  • Conclusions: FedLin guarantees linear convergence to the global minimum under arbitrary objective and systems heterogeneity, including with aggressive gradient sparsification.The paper also establishes a matching lower bound and describes the resulting convergence analysis as tight.
  • Open problems: The benefits of local computation under objective heterogeneity remain unresolved, and the paper calls for algorithm-independent lower bounds.The authors state that their finite-sum results do not quantify benefits from local steps.
  • Open problems: The paper does not determine whether faster machines help or hurt when client objectives have different minima.A fast client may drift toward its own local minimum, which can be far from the global minimum.
  • Open problems: With client-side gradient compression, the analysis guarantees linear convergence only to a neighborhood of the global minimum.The paper leaves open whether alternative communication schemes can guarantee exact convergence.
  • Future directions: Future work includes extending FedLin to finite-sum stochastic optimization and combining it with differential-privacy techniques.These directions are presented as open research questions rather than established results.
  • Compression analysis: The compression analysis addresses gradient sparsification in federated learning with local steps and both objective and systems heterogeneity.The authors characterize this as the first analysis covering these factors together.

D Analysis under Objective Heterogeneity: FedLin resolves the Speed-Accuracy Conflict

The analysis shows that FedLin removes the speed-accuracy conflict under objective heterogeneity by correcting local updates toward the global gradient. With smooth strongly convex losses, it reduces to centralized gradient descent in the homogeneous case and converges linearly in the heterogeneous case.

  • Update structure: FedLin local updates use the local gradient corrected by the difference between the global gradient and its local evaluation.The analysis studies this mechanism first without systems heterogeneity or sparsification.
  • Heterogeneous setting: For smooth strongly convex objectives with equal local-step counts, FedLin guarantees linear convergence under objective heterogeneity.The theorem uses η = 1/(6LH) and assumes δ_c = δ_s = 1.
  • Homogeneous setting: In the homogeneous setting, FedLin becomes m parallel implementations of gradient descent on the global loss function.Each client performs TH iterations over T communication rounds.
  • Proof strategy: The proof bounds local client drift from the common model and then combines that bound with smoothness-based objective decrease.The drift is controlled using the gradient at the beginning of each communication round.

E Proof of Theorem 6: Lower bound for FedLin

The lower-bound proof constructs a two-client quadratic example and analyzes FedLin as a linear dynamical system. Stability forces a step size inversely related to the number of local iterations, yielding an H-independent lower bound on convergence.

  • Construction: The proof constructs two strongly convex, L-smooth quadratic client objectives and studies the resulting global recursion.The example uses a diagonal structure and allows L ≥ 14 and H ≥ 2.
  • Dynamical-system analysis: FedLin’s round-to-round dynamics can be represented as an LTI system with transition matrix M.Convergence from any initial condition requires M to be Schur stable.
  • Step-size constraint: Stability requires the step size to scale inversely with H, the number of local iterations per communication round.The argument derives this requirement from a necessary eigenvalue condition.
  • Lower bound: The constructed instance yields f(x̄_T+1) − f(x*) ≥ exp(−4T)(f(x̄_1) − f(x*)) for all T ≥ 1.This lower bound holds for any L ≥ 14 and H ≥ 2.
  • Lower-bound scope: The lower bound still holds when the client local objectives share the same minimizer.Thus, differing local minimizers are not necessary for this lower-bound construction.
  • Parameter effects: Larger L simultaneously increases objective heterogeneity, reduces smoothness, and necessitates a smaller step size.The proof connects these effects through the stability condition on the recursion.

F.3 Proof of Theorem 3: Analysis for Non-convex loss functions

The non-convex analysis bounds client drift using smoothness rather than convexity, under stricter step-size conditions. The proof then derives the stated convergence guarantee through recursive inequalities and stochastic-oracle bounds.

  • Non-convex drift analysis: Smoothness alone supports the initial bound, but controlling client drift requires a separate argument because the convex-case drift bound no longer applies.The non-convex analysis replaces the convexity-dependent drift bound with Lemma 11.
  • Non-convex drift analysis: η_i ≤ 1/(Lτ_i) is required for the non-convex drift bound, which is more stringent than the corresponding convex-setting condition.The non-convex drift bound is also worse by a factor of 3 than the bound in Lemma 9.
  • Proof completion: The proof obtains the theorem by substituting the drift bound into the descent inequality and summing over communication rounds.The argument explicitly uses η_iτ_i = ¯η and ¯ηL ≤ 1.
  • Stochastic extension: The stochastic proof combines the derived bounds with L-smoothness and µ-strong convexity to complete Theorem 5.The supplied proof passage identifies these properties as the basis for the final steps.
  • Sparsification analysis: TOP-k sparsification is analyzed through operator properties and recursive bounds, yielding the stated FedLin guarantee under the corresponding step-size requirements.The proof uses η_i ≤ 1/L, η_iτ_i = ¯η, and ¯ηL ≤ 1 in its recursion.

H Proof of Theorem 9: Gradient Sparsification at Clients

The client-side sparsification proof introduces a virtual sequence and a Lyapunov function that jointly track optimization progress and compression error. Recursive bounds then establish convergence under smoothness, strong convexity, and step-size restrictions.

  • Proof strategy: The proof uses a virtual sequence to separate convergence of the compressed iterate from convergence of the idealized iterate.The virtual sequence is designed to resemble the unsparsified FedLin recursion.
  • Proof strategy: The Lyapunov function accounts simultaneously for systems heterogeneity and gradient sparsification.Its components include distance from the virtual iterate to the optimum and a sparsification-error term.
  • Virtual-iterate bound: The virtual-iterate recursion includes optimization descent, gradient-norm terms, accumulated sparsification error, and a residual term.The displayed bound is derived under L-smoothness, µ-strong convexity, and server-side sparsification being absent.
  • Compression-error control: Client-side compression errors are controlled through a separate recursion based on TOP-k operator properties and the drift bound between client and virtual iterates.The analysis bounds both local-update deviation and the error sequence before combining them in the Lyapunov recursion.
  • Convergence recursion: Choosing ¯η ≤ 1/(72Lδ_cC) satisfies the lemma conditions and enables recursive contraction of the Lyapunov function.The proof uses smoothness and strong convexity to simplify the resulting inequality.
  • Convergence recursion: The initial compression errors vanish, so the initial Lyapunov value equals the squared distance between the initial global iterate and the optimum.The recursion then yields the desired conclusion.

J Simulation Results for FedSplit

The FedSplit simulation implements its proximal solver with a fixed number of gradient-descent steps per communication round. In the tested range, the implementation diverged for odd step counts but converged for some even counts.

  • Simulation setup: FedSplit is implemented by approximating each proximal solve with e gradient-descent steps using a suitably chosen step size.The simulation evaluates e from 1 through 41 local gradient-descent steps per communication round.
  • Simulation setup: e ∈ {1, …, 41} determines the number of gradient-descent rounds used by FedSplit within each communication round.The proximal and gradient-descent step sizes are selected according to Corollary 1 in the referenced FedSplit work.
  • Simulation outcome: The local FedSplit implementation diverged for every odd e between 1 and 41, while it converged for some even values.The authors note that the implementation code for FedSplit was not publicly available.

K Additional Experimental Results on Logistic Regression

Additional logistic-regression experiments evaluate FedLin under heterogeneous local iteration counts and gradient sparsification. Server-side sparsification still reaches the true minimizer, whereas client-side sparsification leaves an error that grows with compression.

  • Experimental setup: The logistic-regression experiment uses 10 clients, parameter dimension 100, 500 features per client, and heterogeneous local iterations τ_i ∈ [2, 50].Client objectives are smooth and convex, and the synthetic design-matrix entries are sampled independently from N(0, 1).
  • Server-side sparsification: δ_s ∈ {2, 4} corresponds to TOP-50 and TOP-25 server compression, while δ_s = 1 denotes no server sparsification.The server-side experiments fix ¯η at 0.15 across clients.
  • Server-side sparsification: Regardless of server-side gradient sparsification, FedLin converges to the true minimizer.This conclusion is reported for the tested server compression levels and the no-sparsification comparison.
  • Client-side sparsification: δ_c ∈ {1.25, 1.67} corresponds to TOP-80 and TOP-60 client compression, respectively.The client-side experiments fix ¯η at 0.1 across clients.
  • Client-side sparsification: Client-side sparsification produces a non-vanishing convergence error that increases as δ_c increases.This contrasts with the reported server-side sparsification behavior.

L Simulation Results for FedLin with Noisy Gradients

FedLin is evaluated on a least-squares problem with simulated noisy client gradients. The experiments show a noise-dependent non-vanishing error floor, corroborating Theorem 5.

  • FedLin is tested on the least-squares problem with δs = δc = 1 and α = 10.The remaining parameters are kept unchanged from the corresponding setup.
  • Zero-mean Gaussian gradient noise is added with variances σ2 ∈ {10−5, 10−3, 10−1}.
  • FedLin converges with a non-vanishing error floor under noisy gradients, and the floor increases with noise variance.This behavior corroborates the theoretical result in Theorem 5.
Loading 2102.07053v2…