PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Accelerated Stochastic Gradient Descent

Honglin Yuan, Tengyu Ma

arXiv:2006.08950v4cs.LGcs.DCmath.OCstat.ML

TL;DR

Distributed optimization needs faster convergence with less communication, but acceleration can conflict with the stability required by federated algorithms. FedAc addresses this tradeoff by accelerating FedAvg, achieving improved convergence and communication guarantees, including linear speedup with fewer synchronizations.

  • Problem

    Communication bottlenecks limit distributed machine learning, motivating whether FedAvg can achieve improved convergence speed and communication efficiency despite acceleration–stability conflicts.

  • Method

    FedAc parallelizes generalized Accelerated SGD and balances acceleration with stability using a principled distributed optimization design.

  • Results

    FedAc provably improves FedAvg’s convergence and communication efficiency, requiring O~(M^1/3) synchronizations rather than O~(M) for linear speedup under strongly convex objectives.

  • Takeaways & Limitations

    FedAc saves runtime and reduces communication overhead, especially with abundant workers and infrequent communication, while providing stronger guarantees for third-order smooth objectives.

  • Takeaways & Limitations

    FedAc is not designed or proved for the distributed ERM setting.

Abstract

from arXiv · show

We propose Federated Accelerated Stochastic Gradient Descent (FedAc), a principled acceleration of Federated Averaging (FedAvg, also known as Local SGD) for distributed optimization. FedAc is the first provable acceleration of FedAvg that improves convergence speed and communication efficiency on various types of convex functions. For example, for strongly convex and smooth functions, when using $M$ workers, the previous state-of-the-art FedAvg analysis can achieve a linear speedup in $M$ if given $M$ rounds of synchronization, whereas FedAc only requires $M^{\frac{1}{3}}$ rounds. Moreover, we prove stronger guarantees for FedAc when the objectives are third-order smooth. Our technique is based on a potential-based perturbed iterate analysis, a novel stability analysis of generalized accelerated SGD, and a strategic tradeoff between acceleration and stability.

1 Introduction

The paper introduces FedAc to accelerate FedAvg while addressing the tension between acceleration and stability in distributed optimization. Its theory and experiments report improved convergence and communication efficiency, especially with many workers or infrequent synchronization.

  • Motivation: Communication is a major bottleneck in distributed and federated machine learning, motivating methods that reduce synchronization overhead.The paper studies stochastic optimization with M workers, limited synchronization rounds R, and parallel runtime T.
  • Problem: FedAvg periodically averages local SGD iterates, but acceleration is challenging because momentum can amplify instability and worker discrepancies.The paper reports that standard accelerated gradient descent may be initial-value unstable even for smooth strongly convex functions.
  • Approach: FedAc is a principled acceleration of FedAvg that parallelizes generalized Accelerated SGD and balances acceleration with stability.Its analysis uses a perturbed-iterate framework and controls the acceleration-stability tradeoff under smoothness, bounded variance, and strong convexity assumptions.
  • Theoretical results: R = ˜O(M^1/3) synchronization rounds suffice for linear speedup in M for strongly convex smooth objectives, compared with ˜O(M) for FedAvg.The corresponding FedAc rate is ˜O(1/(MT) + 1/(TR^3)), while the cited FedAvg rate is ˜O(1/(MT) + 1/(TR)).
  • Theoretical results: For third-order-smooth objectives, FedAc has stronger guarantees, including the strongly convex rate ˜O(1/(MT) + 1/(T^2R^6)).Third-order smoothness is described as being intuitively close to quadratic, and the paper compares FedAc with FedAvg in this setting.
  • Empirical results: Experiments suggest considerable improvement over FedAvg, distributed Minibatch-SGD, and distributed Accelerated Minibatch-SGD, especially with abundant workers and highly infrequent communication.The paper also reports that FedAc outperforms the other baselines when K ≥ 128 because accelerated minibatch methods have too few gradient steps.

2 Preliminaries

The paper analyzes FedAc under standard convexity, smoothness, variance, and higher-order moment assumptions, with notation for workers, synchronization, runtime, and iterates. It also records a limitation concerning the scope of its stability counterexample.

  • Assumptions: Assumption 1 combines convexity, smoothness, and uniformly bounded stochastic-gradient variance for the optimization analysis.
  • Scope: The initial-value stability counterexample is constructed for simplicity and clarity, while extension to other stability notions is conjectured rather than established.
  • Assumptions: The analysis considers both strongly convex objectives with µ > 0 and general convex objectives with µ = 0, assuming a finite optimum.
  • Assumptions: Assumption 2 adds third-order smoothness and a uniformly bounded fourth central moment to Assumption 1.
  • Notation: The framework uses M for parallel workers, R for synchronization rounds, K for local steps per round, and T = KR for parallel runtime.
  • Notation: The analysis hides multiplicative polylogarithmic factors with ˜O and ˜Θ and uses superscripts to distinguish workers and FedAc iterate modifiers.

3 Main results

FedAc parallelizes generalized accelerated SGD with three intertwined iterate sequences and synchronized averaging. Its main results provide convergence guarantees for strongly convex and general convex objectives, including improved communication behavior and stronger rates under third-order smoothness.

  • Algorithm: FedAc maintains an aggregate sequence, auxiliary middle points for gradient queries, and a main iterate sequence on each worker.
  • Algorithm: At unsynchronized steps, workers retain local candidate iterates; at synchronization steps, candidates are averaged and broadcast to all workers.
  • Algorithm: FedAc uses a flexible generalized accelerated-SGD parameterization because distributed acceleration requires balancing acceleration against stability.
  • Strongly convex results: Under standard assumptions, FedAc-I asymptotically outperforms FedAvg, while FedAc-II improves communication efficiency through an infrequent-communication term decaying as R^-3.
  • Third-order-smooth results: Under third-order smoothness, the paper establishes stronger FedAc guarantees and separately proves a FedAvg convergence rate for comparison.
  • General convex results: For general convex objectives, the analysis uses quadratic regularization to reuse the strongly convex analysis and conjectures direct FedAc constructions with the same rates.

4 Proof sketch

The proof combines perturbed-iterate potentials with stability bounds for accelerated dynamics, then tunes the acceleration to control synchronization discrepancies. A key technical result shows that standard accelerated gradient descent can be unstable with respect to initialization.

  • Proof framework: The proof begins by comparing FedAc with its fully synchronized idealization using a potential-based perturbed-iterate analysis.
  • Proof framework: The resulting potential includes a discrepancy-overhead term that measures worker dissimilarity caused by infrequent synchronization.
  • Stability analysis: For FedAvg, convexity reduces discrepancy through gradients, while stochasticity contributes O(η^2σ^2) variance per local step.
  • Stability analysis: Acceleration complicates discrepancy control because momentum can amplify errors accumulated during previous local steps.
  • Stability analysis: Standard deterministic accelerated gradient descent may exhibit exponential initial-value instability even for smooth strongly convex objectives.
  • Parameter tradeoff: FedAc chooses a less aggressive acceleration parameter as a function of local-step count K, keeping discrepancy growth at most linear in K.
  • Parameter tradeoff: The proof then selects η to optimize the resulting bound, with increasing and decreasing terms controlled separately before substituting K = T/R.
  • Third-order-smooth analysis: For FedAc-II, a centralized potential and third-order smoothness enable the alternative analysis, followed by fourth-order stability bounds.

5 Numerical experiments

Experiments evaluate FedAc against FedAvg, Mb-Sgd, and Mb-Ac-Sgd on regularized logistic regression, including tests of synchronization intervals and worker counts. FedAc is reported as more robust to infrequent synchronization, while vanilla FedAc can be less robust than FedAc-I.

  • Experimental setup: Experiments test FedAc against FedAvg, Mb-Sgd, and Mb-Ac-Sgd on ℓ2-regularized logistic regression using the UCI a9a dataset.The regularization strength is set to 10^-3, with worker counts ranging from M = 2^2 to 2^13.
  • Additional analysis: The experiments include additional datasets and more detailed analysis in the appendix.The paper identifies Figure 1 as the main observed-linear-speedup result and points to Section A for further experiments.
  • Experimental setup: Figure 1 measures observed linear speedup versus workers M under varied synchronization intervals K.All four algorithms attain linear speedup when K = 1.
  • Results: FedAc is most robust to infrequent synchronization and outperforms the baselines by a margin for K ≥64.FedAvg and Mb-Sgd lose linear speedup for K as low as 8, while Mb-Ac-Sgd deteriorates significantly for K ≥64.
  • Results: Vanilla FedAc is less robust to infrequent synchronization and performs worse than the stable FedAc-I on the a9a dataset.Figure 2 compares vanilla FedAc, FedAc-I, and Mb-Ac-Sgd at λ = 10^-4.

6 Conclusions

The conclusion presents FedAc as an acceleration of FedAvg that improves convergence speed and communication efficiency, especially with many workers and infrequent communication. It also identifies stronger guarantees for third-order-smooth objectives and broader potential extensions.

  • Conclusions: FedAc is proposed as a principled acceleration of FedAvg that improves convergence speed and communication efficiency.The conclusion states that both theory and experiments support these improvements.
  • Conclusions: The theory and experiments suggest runtime savings and reduced communication overhead, especially with abundant workers and infrequent communication.The paper also establishes stronger guarantees for third-order-smooth objectives.
  • Conclusions: Non-convex objectives and heterogeneous workers are identified as settings to which FedAc could be generalized.These are presented as expected extensions rather than established results in the conclusion.

Appendices

The appendices contain supplementary experiments and complete proofs for the paper’s convergence and stability results. They also cover corresponding FedAvg and general-convex analyses.

  • Section A: Section A contains additional experiments and descriptions of experimental setup details.
  • Sections B–C: Sections B and C prove complete versions of Theorems 3.1 and 3.3 on FedAc convergence under Assumption 1 or Assumption 2.
  • Sections D–E: Sections D and E cover FedAvg convergence under Assumption 2 and FedAc and FedAvg convergence for general convex objectives.
  • Section F: Section F proves Theorem 4.2 on the initial-value instability of accelerated gradient descent.

List of appendices

The listed appendix materials describe experimental baselines and datasets, evaluation procedures, and hyperparameter selection. The experiments use regularized logistic regression on two binary classification datasets.

  • Baselines: FedAc is compared with FedAvg, Mb-Sgd, and Mb-Ac-Sgd at fixed parallel runtime T = 4096 across synchronization intervals K and worker counts M.The minibatch baselines run SGD or accelerated SGD for T/K steps with batch size MK.
  • Datasets: The datasets are ℓ2-regularized logistic-regression tasks from LibSVM.They are binary classification datasets.
  • Datasets: The a9a dataset contains 123 features and 32,561 training samples.It is identified as the “adult” dataset from the UCI Machine Learning Repository.
  • Datasets: The epsilon dataset contains 2,000 features and 400,000 training samples.It comes from the PASCAL Challenge 2008.
  • Evaluation: Evaluation records the best suboptimality attained over measurements taken every 512 parallel timesteps.Suboptimality is the regularized population loss relative to a pre-computed optimum F*.
  • Hyperparameter choice: Only the learning-rate hyperparameter η is tuned for all four algorithms.For FedAc and Mb-Ac-Sgd, the strong-convexity estimate μ is set to the ℓ2-regularization strength λ.

A.2 Results on dataset a9a

Across the a9a experiments, FedAc is more communication-efficient and more robust to infrequent synchronization than the baselines. This pattern persists across regularization strengths and also appears on the epsilon dataset.

  • Synchronization robustness: For K ≤64, FedAc and Mb-Ac-Sgd perform similarly and both outperform FedAvg and Mb-Sgd at regularization 10^-2.For K ≥128, Mb-Ac-Sgd worsens drastically and FedAc outperforms the other baselines by a margin.
  • Synchronization robustness: FedAc is more robust to infrequent synchronization than FedAvg, Mb-Sgd, and Mb-Ac-Sgd on a9a with regularization 10^-3.FedAvg and Mb-Sgd deteriorate beyond K=2, while Mb-Ac-Sgd deteriorates around K=32 because sparse communication leaves too few gradient steps.
  • Cross-dataset consistency: On epsilon with regularization 10^-4, FedAc is more communication-efficient than the baselines.The results are qualitatively similar to the preceding a9a experiments.

B.1 Main theorem and lemmas: Complete version of Theorem 3.1(a)

The complete analysis establishes convergence and stability guarantees for FedAc-I under strong convexity and standard smoothness, variance, and parameter assumptions. The proof combines a potential-based perturbed-iterate argument with discrepancy-overhead bounds and transformed-norm stability analysis.

  • Main theorem: The complete theorem analyzes FedAc-I for strongly convex objectives under Assumption 1 and derives its convergence guarantee.The theorem is stated using synchronization gap K, with K=T/R relating local steps, runtime, and synchronization rounds.
  • Proof structure: The proof decomposes the analysis into convergence and stability lemmas, then combines their bounds through an appropriate stepsize choice.The decreasing and increasing terms are balanced to complete the theorem.
  • Scope of theorem: The bound also applies to irregular synchronization provided the maximum synchronization interval is at most K.The formal appendix states the result in terms of K rather than synchronization rounds R.
  • Potential-based analysis: FedAc-I tracks progress with a decentralized potential that combines optimization error and worker disagreement.The proof separately analyzes the potential's distance and disagreement-related quantities before coupling them.
  • Proof ingredients: The one-step potential analysis uses strong convexity, smoothness, bounded variance, independence, conditional expectation, and Jensen's inequality.These ingredients establish the component inequalities that are telescoped over time.
  • Stability analysis: The discrepancy-overhead analysis controls products of varying update matrices using a transformed norm rather than the ordinary matrix operator norm.The transformed norm supplies the uniform bound needed for stability across local updates.

C.1 Main theorem and lemmas: Complete version of Theorem 3.3

This section establishes FedAc-II convergence for strongly convex objectives through a potential-based perturbed-iterate analysis coupled with stability bounds. Under Assumption 2, the analysis uses fourth-order stability to control discrepancy overhead and derives the complete convergence theorem.

  • Main theorem: Theorem C.1 gives the complete convergence guarantee for FedAc-II on strongly convex objectives under Assumption 2.The theorem is obtained by combining potential-based convergence and discrepancy-overhead bounds, then selecting an appropriate step size.
  • Potential analysis: FedAc-II is analyzed using a decentralized potential that tracks convergence progress and combines distance and objective-related terms.The potential-based perturbed-iterate analysis is stated under Assumption 1 and uses specific choices of α, β, and γ.
  • Parameter choice: The convergence proof separates a decreasing term from an increasing term and balances them through the choice of η.This tradeoff is used to obtain the main theorem from the general-η convergence lemma.
  • Stability analysis: The discrepancy overhead is controlled through fourth-order stability, with the key bounds requiring Assumption 2 and third-order smoothness.The proof analyzes worker differences through matrix transformations and uniform norm bounds before relating them to the discrepancy overhead.
  • Assumption 1: Theorem C.13 extends the FedAc-II convergence result to strongly convex objectives under the weaker Assumption 1.Lemma C.2 requires only Assumption 1, allowing the potential analysis to be reused in this setting.

D.1 Main theorem and lemma: Complete version of Theorem 3.4

This section develops the complete FedAvg convergence theorem under Assumption 2 for strongly convex objectives. The proof combines perturbed-iterate convergence with fourth-order discrepancy stability.

  • Main theorem: Theorem D.1 states the complete convergence guarantee for FedAvg when the objective is strongly convex and satisfies Assumption 2.The theorem follows by selecting an appropriate η in the general-η convergence lemma.
  • Convergence analysis: FedAvg convergence is established through a perturbed-iterate analysis that is telescoped over time.The analysis uses a convergence lemma with a synchronization-dependent discrepancy term.
  • Stability analysis: FedAvg’s discrepancy overhead is bounded using fourth-order stability of differences between distinct workers.The proof derives a one-step stability inequality and telescopes it from the latest synchronization point, where worker differences are zero.
  • One-step bound: The stability argument applies convexity and smoothness to control worker disagreement during nonsynchronized steps.At synchronized steps the result is immediate; otherwise, the worker-difference recursion is bounded before taking square roots.

E.1 Main theorems

For general convex objectives, the paper applies FedAc or FedAvg to an ℓ2-augmented objective that introduces strong convexity. It then derives convergence results for FedAc-I, FedAc-II, and FedAvg under the stated assumptions.

  • Augmentation: The general-convex analysis applies the algorithms to the augmented objective ˜Fλ, which has smoothness L + λ and strong convexity λ.The variance is unchanged, and under Assumption 2 the Q-3rd-order-smoothness is also unchanged.
  • Communication parameterization: The bounds in Table 2 are obtained by substituting K = T/R into the general-convex theorems.This connects the synchronization-gap parameter K to the number of communication rounds R.
  • FedAc-I: Theorem E.1 gives a convergence guarantee for FedAc-I on general convex objectives under Assumption 1.The theorem applies FedAc-I to ˜Fλ with parameters selected as functions of T, K, L, and the initial distance.
  • FedAvg comparison: Theorem E.4 provides a corresponding general-convex convergence guarantee for FedAvg under Assumption 2.The paper includes this result for comparison with the FedAc guarantees.

F.1 Main theorem and lemmas

This section proves that standard deterministic accelerated gradient descent can be initial-value unstable even on one-dimensional smooth strongly convex objectives. The construction produces exponentially growing differences between nearby trajectories while preserving the stated curvature conditions.

  • Interpretation: The instability construction does not contradict Agd convergence because it changes curvature locally to separate trajectories, whereas convergence depends on global curvature.The paper presents this as evidence for an acceleration-stability tradeoff rather than a failure of convergence.
  • Main theorem: Theorem F.1 shows initial-value instability of deterministic standard Agd when L/µ ≥25.For arbitrarily small positive initial separation, the constructed trajectories can diverge exponentially over K blocks.
  • Construction: The instability result constructs a one-dimensional L-smooth, µ-strongly convex objective with locally alternating curvature patterns.Curvature equals L at selected steps and µ otherwise, within neighborhoods around the trajectory.
  • Difference dynamics: The difference between two Agd instances is analyzed through a one-step recursion involving an intermediate curvature value.Lemma F.3 supplies the trajectory-difference growth relation used in the instability proof.
  • Growth result: After K three-step blocks, the constructed trajectories satisfy exponential separation bounds proportional to (1.02)^K times the initial perturbation.The displayed bound applies to both accelerated and auxiliary trajectory components.
Loading 2006.08950v4…