Federated Learning of a Mixture of Global and Local Models

Filip Hanzely; Peter Richtárik

Source-linked AI summary

Federated Learning of a Mixture of Global and Local Models

Filip Hanzely, Peter Richtárik

arXiv:2002.05516v3Feb 10, 2020cs.LGcs.DCmath.OCstat.ML

TL;DR

Federated learning must train across private, heterogeneous device data, while local methods lack strong communication guarantees for the traditional global objective. The paper introduces a global-local mixture objective and develops local SGD variants with convergence guarantees. It shows that personalization and local steps can reduce communication complexity, including without data-similarity assumptions.

Problem
The traditional federated objective seeks one global model, while local methods lack theoretical communication improvements over non-local methods under heterogeneous data.
Method
The paper optimizes a penalized mixture of personalized local models and their mean using L2GD and variance-reduced local SGD variants.
Results
Local SGD variants can outperform synchronous minibatch SGD in communication complexity without assuming data similarity, while communication tends to 0 as λ → 0.
Takeaways & Limitations
Local steps are better interpreted as methods for solving the proposed personalized federated objective rather than only the traditional global objective.
Takeaways & Limitations
The analysis does not explore smooth convex or non-convex losses, and the algorithms’ privacy is not considered in their statements.

Abstract

from arXiv · show

We propose a new optimization formulation for training federated learning models. The standard formulation has the form of an empirical risk minimization problem constructed to find a single global model trained from the private data stored across all participating devices. In contrast, our formulation seeks an explicit trade-off between this traditional global model and the local models, which can be learned by each device from its own private data without any communication. Further, we develop several efficient variants of SGD (with and without partial participation and with and without variance reduction) for solving the new formulation and prove communication complexity guarantees. Notably, our methods are similar but not identical to federated averaging / local SGD, thus shedding some light on the role of local steps in federated learning. In particular, we are the first to i) show that local steps can improve communication for problems with heterogeneous data, and ii) point out that personalization yields reduced communication complexity.

1 Introduction

Federated learning keeps data on edge devices but must handle heterogeneous distributions and privacy constraints. The paper frames a tension between the practical success of local methods and their limited theoretical communication guarantees for the traditional global objective.

Motivation: Federated learning trains models on edge devices to address privacy and the inefficiency of transferring data to centralized locations.Device data may remain private while avoiding the energy and time costs of centralization.
Heterogeneous data: Device distributions can differ substantially, so federated learning methods must operate under heterogeneous data.The local distributions D_i may possess very different properties across devices.
Current approaches: FedAvg and its simple non-participating form, Local Gradient Descent, use multiple local gradient steps before aggregation.FedAvg is the prevalent method for solving the standard global empirical-risk objective in federated learning.
Current approaches: FedAvg works well empirically, particularly for non-convex problems, but has poor convergence guarantees relative to non-local methods under heterogeneous data.This creates a gap between empirical performance and theoretical guarantees.
Personalization: Personalization is motivated by the possibility that a global model may be poorly matched to an individual user’s data and usage patterns.Prior work addressed this issue through approaches including multi-task learning, meta-learning, variational inference, transfer learning, and explicit model mixing.
Research question: The paper asks whether Local Gradient Descent should be understood as solving a problem other than the traditional single-global-model objective.Answering this question may clarify the role of local steps in Local SGD and FedAvg.

2 Contributions

The paper introduces a personalized federated objective that mixes global and local models, then develops local SGD methods with convergence and communication guarantees. It argues that local methods can be communication-efficient because they solve this personalized objective, including under fully heterogeneous data.

New formulation of FL: The new formulation learns personalized models from device-local data while encouraging them to remain close to their mean through a quadratic penalty.The formulation lifts optimization from R^d to R^{nd} and interpolates between local and global models through λ.
Loopless LGD: L2GD applies non-uniform SGD to the mixture objective, combining stochastic updates for the average loss and the similarity penalty.Its algorithmic difference from LGD is minor, while the objective being solved and the resulting communication complexity differ.
Convergence theory: As λ → 0, the communication complexity tends to 0, while as λ → ∞ the formulation approaches the optimal global model and matches GD efficiency.The communication result interpolates between pure local models and the global-model regime.
Personalization, local steps and communication complexity: Local SGD variants can outperform synchronous minibatch SGD in communication complexity without assuming data similarity, when interpreted as methods for the personalized objective.The paper also states that personalized federated learning can be easier to solve communicationally than the traditional objective.
Generalizations: The methods extend to stochastic partial participation, local subsampling, and variance reduction, with a broader total-variance-reduction method described in the appendix.These mechanisms address variance from non-uniform locality, partial participation, and local subsampling.
Heterogeneous data: The proposed methods and convergence results allow fully heterogeneous data without assumptions about similarity across devices.Experiments are reported as supporting the theoretical predictions empirically.

3 New Formulation of FL

The formulation interpolates between independently learned local models and a shared global model through a penalty parameter λ. Its optimal solutions become more similar as λ grows, while retaining loss no worse than the standard global formulation and converging to it at rate O(1/λ).

3 New Formulation of FL: At λ = 0, each device computes its local model from Di alone without communication; incorporating other clients’ data requires communication.The paper notes that individual Di may be insufficiently rich for a useful local model.
3 New Formulation of FL: For λ ∈ (0, ∞), increasing λ strengthens the similarity penalty, requiring communication to prevent the local models from becoming too dissimilar.The intermediate regime produces mixed models between the local and global extremes.
3 New Formulation of FL: The λ → ∞ limit forces local models to coincide and is equivalent to the standard global formulation’s optimal solution.The paper defines xi(∞) as the optimal global solution replicated across devices.
3.1 Technical preliminaries: Under L-smoothness and µ-strong convexity of each fi, the aggregate objective is strongly convex and has a unique solution.The formulation uses separable local losses and a convex, smooth penalty.
3.2 Characterization of optimal solutions: The penalty ψ(x(λ)) is non-increasing, whereas the loss f(x(λ)) is non-decreasing but never exceeds the optimal global loss f(x(∞)).Thus larger λ yields increasingly similar local models while remaining bounded by the standard global objective.
3.2 Characterization of optimal solutions: For λ > 0, each optimal local model equals the average model minus a multiple of its local gradient, and the local gradients sum to zero.The characterization connects local personalization to gradient deviations around the average model.
3.2 Characterization of optimal solutions: The optimal local models converge to the traditional federated-learning solution at rate O(1/λ).Figure 1 examines distances to the pure local and global solutions as λ varies on logistic regression over a1a.

4 L2GD: Loopless Local GD

L2GD applies non-uniform SGD to a personalized objective that balances local losses with a penalty encouraging similarity among device models. Random local and aggregation steps yield communication guarantees interpolating between global and purely local training.

Algorithm: L2GD optimizes the personalized formulation by sampling either the average loss or the similarity penalty to form an unbiased stochastic gradient.The resulting method alternates local gradient steps with movements of local models toward their average.
Algorithm: Each iteration tosses a coin: 0 triggers one local gradient step on every device, while 1 triggers a master-side step toward averaging.The averaging update is a convex combination rather than full averaging.
Communication: The parameter p controls the expected balance between local-gradient and averaging steps, with more local steps moving models toward pure local solutions.Repeated averaging steps instead move local models closer to their average.
Communication: Communication occurs when consecutive coin tosses differ, producing an expected p(1 −p)k communication rounds over k iterations.A 0→1 transition communicates device models to the master; a 1→0 transition communicates updated models back to devices.
Convergence theory: The optimal probability p⋆= λ/(L+λ) minimizes both iteration and expected communication complexity.The corresponding optimal iteration count is 2(L+λ)/ε, while the optimal expected communications are 2λ/(λ+L).
Convergence theory: As λ→∞, L2GD recovers GD communication efficiency, whereas its communication complexity decreases to zero as λ→0.Thus the guarantee interpolates between finding a global model and computing pure local models.

5 Loopless Local SGD with Variance Reduction

L2SGD+ adds variance reduction to loopless local SGD for finite-sum local objectives, addressing L2GD’s convergence to a neighborhood. Its extensions support broader client, sampling, and participation settings.

Method: L2SGD+ incorporates control variates into local stochastic gradient steps while maintaining a global linear convergence rate.It is presented as the first local SGD method with linear convergence under the stated finite-sum assumptions.
Communication: L2SGD+ communicates when consecutive coin tosses differ, averaging p(1 −p)k times over k iterations, but control-variate communication makes each round three times more expensive.An appendix implementation avoids communicating the control variates.
Convergence theory: Theorem 5.1 provides the iteration-complexity guarantee for L2SGD+ under finite-sum local objectives and its stated smoothness and strong-convexity assumptions.The theorem uses a prescribed stepsize choice based on the problem parameters.
Convergence theory: Both communication and iteration complexity are minimized by the probability specified in Corollary 5.2.The supplied passage identifies this probability as the optimizer for both criteria.
Convergence theory: In the pure local setting λ=0, communication complexity becomes log(1/ε), because estimating local-model distances still requires communication.At the global extreme, the comparison matches minibatch SAGA’s communication complexity for finding the globally optimal model.
Extensions: L2SGD++ extends the approach to arbitrary local dataset sizes, local subsampling, partial client participation, and SVRG-like control-variate updates.It also exploits the local objectives’ smoothness structure to obtain tighter rates.

6 Experiments

The experiments numerically verify the paper’s theoretical claims about convergence, communication frequency, and parameter choices for L2SGD+.

Experimental design: The experiments study convergence under different methods, data splits, aggregation probabilities, and values of λ.Additional experiments examine p and λ, with details provided in the Appendix.
Experimental setup: The experiments use logistic regression on LibSVM datasets, with normalized data and stepsizes selected according to Theorem 5.1.Different client counts were used across datasets.
Method comparison: Variance reduction enables fast global convergence for L2SGD+, while L2SGD and L2SGD2 converge to neighborhoods.The neighborhood is slightly smaller for L2SGD2 than for L2SGD.

7 Possible Extensions

The paper identifies extensions of its L2GD analysis and algorithms to broader loss classes, decentralized networks, and accelerated optimization.

Extensions: The L2GD analysis can be extended to smooth convex and non-convex loss functions, although these directions are not explored.The paper also identifies decentralized and accelerated extensions as possible future work.
Extensions: A decentralized version could restrict communication to edges of a connected device network by adding randomization over the penalty ψ.This extension is described as achievable within the proposed approach.
Extensions: Adapting a Katyusha variant could provide Nesterov-style acceleration and further reduce communication rounds.The proposed acceleration is presented as a possible extension rather than an evaluated result.

A Experimental Setup and Further Experiments

The experiments use logistic regression on LibSVM data split across clients, with normalized features, strongly convex local objectives, stochastic local updates, and theorem-based stepsizes.

Experimental model: Each experiment uses binary logistic regression, with device i holding a data matrix Ai and labels bi.The local objective is defined from each device’s data.
Data and assumptions: The data rows are normalized so each component objective is 1-smooth, while every local objective is 10^-4-strongly convex.The datasets come from LibSVM.
Implementation: Each dataset is evenly split among clients, and the local stochastic method samples one data point per iteration.The number of clients varies by dataset.
Implementation: The experiment configurations, including dataset sizes and client counts, are summarized in Table 1.Stepsizes are selected according to Theorem 5.1.

A.1 Comparison of the methods

The experiments compare variance-reduced and local methods under homogeneous and heterogeneous splits, and test how communication probability and λ affect convergence.

Comparison of the methods: Full variance reduction converges to the global optimum, whereas partial variance reduction methods converge only to a neighborhood.This comparison is made among variance-reduced local SGD, shifted local SGD, and local SGD.
Comparison of the methods: Partial variance reduction performs better than using no control variates, although the improvement is rather negligible.The comparison concerns shifted local SGD versus local SGD.
Comparison of the methods: Data heterogeneity does not affect the convergence speed of the proposed methods in the reported homogeneous and heterogeneous splits.The paper contrasts this with standard local SGD.
Effect of p: The aggregation probability p controls communication frequency, with clients taking on average p^-1−1 local steps between communication rounds.The experiments compare p with p⋆, predicted to optimize convergence rate.
Effect of p: Communication probabilities below p⋆ slow convergence as expected, while probabilities above p⋆ can also slow convergence because of the problem’s structure.The latter effect disappears when λ=∞ enforces identical local models.
Effect of λ: Values λ<λ⋆ have comparable convergence speed to λ=λ⋆, whereas λ>λ⋆ yields a noticeably worse rate.Figure 6 compares relative suboptimality across problem instances with different λ.

B.1 Local GD with variance reduction

This section introduces variance-reduced local gradient descent methods that use control variates to preserve unbiasedness and improve convergence, including a communication-efficient implementation.

Variance-reduced local gradient descent: Algorithm 3 incorporates control variates into local gradient descent and can be viewed as a special case of Algorithm 2 with m = 1.It is also a special case of SAGA with importance sampling.
Variance-reduced local gradient descent: The gradient estimator remains unbiased for any control variates Jk and Ψk, which are updated to track recently observed local and aggregation gradients.The control variates are intended to correlate with n∇f(xk) and nλ∇ψ(xk).
Communication pattern: Communication in Algorithm 3 occurs only when the average model is computed, with probability p, paralleling standard local SGD.Between aggregation events, devices perform local updates without communication.
Convergence and communication: The optimal choice p = (4λ+µ)/(4λ+4L+2µ) minimizes both iterations and communication rounds for reaching an ε-solution.The communication complexity is minimized for any p no larger than this value.
Communication-efficient implementation: Algorithm 4 implements L2SGD+ without communicating control variates, requiring on average p(1−p)^k communications over k iterations.Each communication sends only local models to the master and back.

B.3 Local SGD with variance reduction – general method

The general method extends variance-reduced local SGD to heterogeneous local objectives, arbitrary client participation and sampling, and optional proximal regularization.

General method: The method handles local objectives with possibly nonsmooth convex regularizers through a proximal formulation.The regularizer is assumed to admit a cheap proximal-operator evaluation.
General method: Algorithm 5, L2SGD++, supports arbitrary aggregation probability, client sampling, local dataset sizes, objective smoothness structures, and subsampling strategies.It also permits SVRG-like local control-variate updates with reduced storage requirements.
Sampling and analysis: Local sampling distributions and Expected Separable Overapproximation parameters provide smoothness bounds adapted to each sampling strategy.The ESO framework supplies smoothness parameters that account for the chosen sampling scheme.
Convergence guarantees: Algorithm 5 has SAGA and SVRG variants, with Theorems B.4 and B.5 giving their respective convergence rates.The SAGA option and LSVRG option are analyzed separately under the stated smoothness and convexity assumptions.
Relationship among methods: The general construction represents a hierarchy in which Algorithm 3 is a special case of Algorithm 2, which is a special case of Algorithm 5.The corresponding convergence theorems inherit the same specialization relationship.
Additional variants: Algorithm 6 uses no control variates, whereas Algorithm 7 constructs control variates only for the aggregation term and has no convergence rates presented here.The latter produces a locally drifted SGD method with constant drift between communication rounds.

C.2 Proof of Theorem 3.1

The proof framework derives convergence and communication guarantees by casting the proposed algorithms as instances of generalized variance-reduced sketching methods.

Communication analysis: For the simpler setting, minimizing iterations and communications gives p⋆ = λ/(λ+L), with the optimal expected communication expression stated in the proof.The proof chooses α = 1/(2L) when targeting an ε-solution.
Communication analysis: For the analyzed local methods, the aggregation probability is optimized by balancing communication and local-update terms, yielding p = (4λ+µ)/(4L′+4λ+(m+1)µ).The same choice minimizes the expected communication expression in the cited derivation.
Proof strategy: Algorithm 5 is cast as a special case of Generalized JacSketch, allowing Theorem B.4 to follow from an existing GJS convergence theorem.Theorem 5.1 follows immediately because Algorithm 2 is a special case of Algorithm 5.
Proof strategy: GJS uses randomized sketches of the gradient matrix and constructs a variance-reduced estimator before taking a proximal step.The sketch operators include a random projection and an operator that is unbiased in expectation.
Convergence analysis: The analysis assumes a unique minimizer and quasi-strong convexity, then establishes an expected convergence bound for the randomized iterates.The relevant theorem is stated under Assumption C.1 and operator conditions.
Specialization: The proof specializes the general theorem to the SAGA and LSVRG cases by selecting sampling and smoothness parameters for the local objectives.These substitutions recover the stated theorem-specific iteration complexities.