PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Optimization: Distributed Machine Learning for On-Device Intelligence

Jakub Konečný, H. Brendan McMahan, Daniel Ramage, Peter Richtárik

arXiv:1610.02527v1cs.LG

TL;DR

The paper studies distributed optimization when data is unevenly distributed across extremely many devices and communication rounds are costly. It proposes federated optimization, which keeps data local and aggregates device-computed updates, and reports that suitable algorithms can work efficiently in this challenging setting. The approach uses per-coordinate stochastic-gradient scaling and sparsity-based aggregation of updates.

  • Problem

    Federated optimization must train a centralized model despite massively distributed, non-IID data and a need to minimize communication rounds.

  • Method

    The paper keeps training data on devices and trains a shared model by aggregating locally computed updates, including per-coordinate scaling and sparsity-based update aggregation.

  • Results

    Suitable optimization algorithms can work efficiently and achieve convergence in relatively few communication rounds despite a large number of nodes.

  • Takeaways & Limitations

    Federated optimization makes the vision of training models on distributed device data conceptually feasible and establishes a setting for further research.

  • Takeaways & Limitations

    Additional privacy protections may be needed because updates can still contain private information, and protection from a malicious coordinating server requires further techniques beyond this work.

Abstract

from arXiv · show

We introduce a new and increasingly relevant setting for distributed optimization in machine learning, where the data defining the optimization are unevenly distributed over an extremely large number of nodes. The goal is to train a high-quality centralized model. We refer to this setting as Federated Optimization. In this setting, communication efficiency is of the utmost importance and minimizing the number of rounds of communication is the principal goal. A motivating example arises when we keep the training data locally on users' mobile devices instead of logging it to a data center for training. In federated optimziation, the devices are used as compute nodes performing computation on their local data in order to update a global model. We suppose that we have extremely large number of devices in the network --- as many as the number of users of a given service, each of which has only a tiny fraction of the total data available. In particular, we expect the number of data points available locally to be much smaller than the number of devices. Additionally, since different users generate data with different patterns, it is reasonable to assume that no device has a representative sample of the overall distribution. We show that existing algorithms are not suitable for this setting, and propose a new algorithm which shows encouraging experimental results for sparse convex problems. This work also sets a path for future research needed in the context of \federated optimization.

1 Introduction

The paper introduces federated optimization for training models when data remains distributed across many non-IID devices, making communication efficiency and minimizing communication rounds central concerns. It motivates keeping privacy-sensitive training data on users’ devices while using their computation to update a shared model.

  • Federated learning keeps training data on mobile devices and aggregates locally computed updates through a central coordinating server.
  • This device-based approach can reduce network bandwidth and privacy risks by avoiding centralized raw-data collection, although server trust and update privacy remain concerns.
  • Communication is costly relative to local computation, so the practical objective is to minimize communication rounds.
  • Existing distributed optimization methods often assume evenly distributed, representative local data, assumptions that federated optimization does not satisfy.
  • Federated optimization addresses distributed optimization when data is massively distributed, non-IID, unbalanced, and sparse.
  • The paper initiates federated optimization research and reports that suitable algorithms can converge in relatively few communication rounds despite many nodes and non-IID data.

2 Related Work

The related work surveys centralized and distributed optimization methods, emphasizing that communication efficiency and realistic federated assumptions remain unresolved challenges. Existing approaches face scalability, synchronization, data-partitioning, or modeling limitations in the target setting.

  • Centralized baselines: Gradient descent and accelerated variants require processing the entire dataset in each iteration, making them impractical when n is very large.Gradient descent evaluates a full gradient, while acceleration improves convergence rate without removing the full-data pass.
  • Centralized baselines: SGD reduces per-iteration computation through unbiased sampled gradients, but sampling noise slows convergence and requires diminishing stepsizes.Random reshuffling can improve practical performance, although its theoretical behavior was historically less understood.
  • Randomized algorithms: SVRG avoids SAG/SAGA memory costs but periodically processes the whole dataset, and its performance in the target setting lacks systematic assessment.The cited discussion notes that meaningful conclusions require extensive comparisons with state-of-the-art methods and heuristics.
  • Distributed algorithms: Distributed methods must address synchronous idle time and asynchronous stale updates, while realistic delay assumptions and analyses remain difficult.Synchronous updates wait for the slowest nodes; asynchronous analyses may also suffer from incorrect iterate labeling under realistic delays.
  • Distributed algorithms: Distributed coordinate-descent methods commonly assume feature-based data partitioning, which can be restrictive when data are distributed by examples.Dual variants support data-point partitioning but require explicit strongly convex regularization, limiting the problem class.
  • Communication-efficient algorithms: CoCoA appears applicable to federated optimization, but its communication-round bound for ill-conditioned problems scales with K and it converges slowly on real data.The paper therefore proposes local subproblems formulated without duality as an alternative direction.

3 Algorithms for Federated Optimization

This section motivates algorithms for federated optimization by contrasting its non-IID, unbalanced, massively distributed setting with conventional distributed optimization. It introduces desired convergence properties and reviews SVRG as a variance-reduced baseline.

  • Federated optimization requires algorithms for non-IID, unbalanced, and massively distributed data.The desired setting differs from classic distributed optimization, where machines often hold large IID datasets.
  • An ideal algorithm remains at the optimum and converges in O(1) communication rounds in several extreme data-distribution cases.These cases include single-node data, disjoint feature blocks, and identical datasets across nodes.
  • Property (D), immediate convergence with identical local datasets, is least important for federated optimization because it represents a classic IID setting.Properties (B) and (C) instead represent extreme federated cases.
  • SVRG: SVRG alternates a full-gradient computation with stochastic inner updates to reduce gradient-estimation variance.The full gradient is expensive, while the inner loop performs fast stochastic updates.
  • SVRG: For λ-strongly convex f and L-smooth functions fi, SVRG has theoretically characterized convergence results and parameter-dependent evaluation requirements.The supplied passages state the assumptions and refer to convergence forms and evaluation bounds without displaying their complete formulas.

3.3 Distributed Problem Formulation

The distributed formulation partitions the finite-sum objective across nodes and examines DANE as a communication-efficient method. The discussion identifies its favorable properties, assumptions, and limitations for federated optimization.

  • Distributed Problem Formulation: The data indices are partitioned into disjoint sets Pk across K nodes, with nk data points on node k and local objectives Fk.The global empirical loss is expressed as a convex combination of local empirical losses.
  • DANE: The naive strategy of minimizing each local function and averaging the solutions effectively performs one communication round but generally cannot recover the global solution.A weighted average is not generally the solution unless local functions are identical.
  • DANE: Quadratic regularization around the current iterate modifies local subproblems while preserving much of each local function's curvature information.The resulting subproblem Hessian is ∇^2Fk + µI, and µ may be set to zero.
  • DANE: DANE forms local subproblems using local data and the global gradient, solves them, and averages node updates.The global gradient can be computed in one communication round, while local subproblems may use arbitrary solvers.
  • DANE: The DANE algorithm was originally analyzed with equal local dataset sizes, although the formulation can run with more general nk.The paper presents this as a broader setting than the original analysis.
  • DANE: DANE achieves property (A) for any µ and η, and property (D) in its default setting µ = 0 and η = 1.Identical local datasets make each local objective equal to the global objective in the default setting.
  • DANE: DANE's convergence analysis assumes twice-differentiable functions and IID samples, implying similar local Hessians; its practical regularization choice remains unresolved.For linear regression under the stated strong-convexity condition, the iteration count is O(K log(1/ϵ)).

3.5 SVRG meets DANE

The paper connects DANE with SVRG by using SVRG as an approximate local solver, yielding Federated SVRG. The two procedures generate identical iterates under specified settings.

  • DANE can perform poorly in some settings, and exact minimization of its local subproblem may be infeasible or very expensive.The paper replaces exact optimization with an approximate solution achieving relative Θ accuracy.
  • Using SVRG as a local solver lets DANE skip the initial full-gradient computation because each node already has the shared derivative at wt.Local optimization starts from wt and proceeds with stochastic updates.
  • The modified DANE method is equivalent to a distributed version of SVRG called Federated SVRG.The equivalence is stated for DANE with η = 1 and µ = 0, using one SVRG iteration initialized at wt.
  • The two algorithms generate identical sequences of iterates when initialized at the same point.The proof matches a single SVRG step on each local DANE subproblem to Algorithm 3's update.

3.6 Federated SVRG

Federated SVRG modifies distributed SVRG for unequal local data sizes and sparse, uneven feature distributions. Its update scaling interpolates between averaging dense variables and trusting variables present on fewer nodes.

  • Federated SVRG addresses unequal local data sizes, sparse features, and differing local-versus-global sparsity patterns.The algorithm introduces aggregation and gradient-scaling modifications to handle these federated conditions.
  • 3.6.1 Notation: For sparse generalized linear prediction, gradients are multiples of sparse data vectors, creating both complications and opportunities for faster algorithms.The notation tracks global and local feature frequencies, sparsity ratios, and node participation.
  • Diagonal scaling by Sk adjusts stochastic gradients using the distribution of each feature's sparsity across nodes.The stated motivation is to enforce gradient estimates of the correct magnitude given the known sparsity structure.
  • FSVRG runs parallel local update loops from the shared iterate, using diagonal matrices A and Sk and a local permutation of Pk.The supplied algorithm description includes h, the data partition, local initialization, and nk stochastic updates.
  • The algorithm aggregates local updates proportional to nk/n and uses local stepsizes hk = h/nk.This weighting reflects local data availability while equalizing the approximate progress made across nodes.
  • 3.6.2 Intuition Behind FSVRG Updates: When variables occur on every node, FSVRG averages their updates; when they occur on fewer nodes, it gives those nodes greater influence.This is described as a per-variable interpolation between dense and decomposable settings.
  • 3.6.2 Intuition Behind FSVRG Updates: If data depend on disjoint variable groups and are distributed accordingly, local solutions can be added to solve the resulting disjoint problems in one iteration.This corresponds to desired property (C).

3.7 Further Notes

The authors considered adapting an equivalent algorithm by changing only its local optimization objective, but exact local solutions were impractical and the resulting performance was inferior.

  • Modifying the first equivalent algorithm through only its local objective was investigated as a possible federated-optimization approach.
  • Exact solutions to the local subproblem were often impractical, and relaxing this requirement moved the method toward the approach developed earlier.
  • The modified approach produced results significantly inferior to those reported later for the proposed method.

4 Experiments

The experiments simulate federated optimization using user-clustered Google+ posts, revealing highly unbalanced, sparse, and non-IID data and showing that FSVRG reaches optimal test accuracy in 30 iterations.

  • 4.1 Predicting Comments on Public Google+ Posts: The experiment uses 10,000 Google+ authors as nodes to predict whether posts receive comments, with earlier posts for training and later posts for testing.The dataset contains 2,166,693 training examples and a 20,002-dimensional bag-of-words logistic-regression problem.
  • 4.1 Predicting Comments on Public Google+ Posts: Node data are substantially unbalanced and non-IID: each node averages roughly 216 examples, but node sizes range from 75 to 9,000.Users exhibit different data patterns, while the bag-of-words representation is highly sparse.
  • 4.1 Predicting Comments on Public Google+ Posts: Over 88% of features appear on fewer than 1,000 nodes, although some features, such as the bias term, occur everywhere.
  • 4.1 Predicting Comments on Public Google+ Posts: 17.14% test error comes from predicting each author’s majority label, compared with 26.27% for globally optimal logistic regression and 33.16% for always predicting no comment.
  • 4.1 Predicting Comments on Public Google+ Posts: The authors identify per-author personalization as a natural next step because per-author majority prediction improves substantially over a fixed global model.Personalized models are outside this work’s scope, and the authors note that local adaptation can indicate how far data are from IID.
  • 4.1 Predicting Comments on Public Google+ Posts: FSVRG converges to optimal test classification accuracy in just 30 iterations, while CoCoA+ performs worse than distributed gradient descent in this sparse problem.The comparison evaluates OPT, distributed gradient descent, CoCoA+, FSVRG, and a reshuffled-data variant, FSVRGR.
  • 4.1 Predicting Comments on Public Google+ Posts: The reshuffled-data experiment shows only a subtle convergence difference, supporting the robustness of the proposed techniques to federated-optimization challenges.

5 Conclusions and Future Challenges

The paper defines federated optimization as a massively distributed, non-IID, unbalanced, and sparse setting, and presents algorithms designed to work efficiently under these conditions.

  • Federated optimization keeps users’ generated data local while using their computational power to solve optimization problems, creating a distinct distributed-optimization setting.
  • The setting’s central challenges are massive distribution, non-IID data, imbalance across nodes, and sparse data representations.
  • The authors argue that existing methods are not applicable or effective, while suitable algorithms can converge efficiently despite the setting’s challenges.
  • The proposed method scales stochastic gradients per coordinate and per node, and aggregates updates per coordinate according to sparsity patterns.
  • Future work includes fully asynchronous algorithms, stronger convergence theory, non-convex objectives, and personalized models for non-IID data.

A Distributed Optimization via Quadratic Perturbations

The appendix uses a quadratic-perturbation template to propose a method related to DANE and CoCoA that converges under arbitrary data partitions.

  • The appendix applies a general algorithmic perturbation template to λ-strongly convex objectives to derive a new distributed optimization method.
  • Unlike DANE, the proposed method converges under arbitrary data partitions {P_k}_{k=1}^K.
  • The appendix highlights the method’s relationship to the dual CoCoA algorithm for distributed optimization.
  • For simpler notation, the appendix assumes equal n_k across nodes, while stating that the arguments extend to unequal node sizes.

A.1 New Method

Algorithm 5 is a new quadratic-perturbation method whose averaged perturbations involve the current global gradient. Its maintained quantities satisfy a lemma-based invariant, and it converges for ridge regression under arbitrary data partitions.

  • Algorithm 5 introduces a new method in the family of quadratic perturbation methods.Its perturbation vectors differ from those used by DANE.
  • The method maintains vectors whose updates satisfy an invariant for every iteration t.The invariant follows from the update rule, induction, and the definition of the next iterate.
  • Both DANE and Algorithm 5 use a linear perturbation whose node average involves ∇f(wt), the gradient at the latest iterate.This gives the methods a shared property beyond their common quadratic-perturbation form.
  • Algorithm 5 converges for any ridge regression problem and any data partitioning, unlike DANE's more restricted convergence guarantee.The passage states that DANE may fail on arbitrary problems and is known to converge only under a similarity assumption on node data.
  • Algorithm 5 is presented as the Primal Method in the paper's algorithmic development.

A.2 L2-Regularized Linear Predictors

This section specializes the framework to L2-regularized linear predictors, yielding a regularized empirical-risk minimization problem over data partitioned across K nodes. The loss functions are assumed convex and smooth, with quadratic loss as an example.

  • The section studies L2-regularized linear predictors as a specialization of problem (1).
  • The resulting objective is an L2-regularized empirical risk minimization problem.
  • The data pairs (xi, yi) are partitioned across K nodes, with node k storing the local matrix Xk and label vector yk.The global matrix X is formed by concatenating the node-specific submatrices.

A.3 A Dual Method: Dual Block Proximal Gradient Ascent

The paper constructs a dual block proximal-gradient ascent method for the regularized problem and shows that, under quadratic loss, it is equivalent to the primal Algorithm 5. This dual view yields linear convergence and connects DANE with CoCoA+.

  • The dual problem is optimized using a block-separable proximal-gradient ascent construction.A node-separable quadratic lower bound is maximized blockwise using the local gradients ∇kξ(αt).
  • The dual method is based on ξ(α) = 1/2∥Xα∥2 and a block-diagonal matrix B built from the node matrices Xk.The matrix relation XT X ⪯ σB supplies the smoothness comparison used in the construction.
  • The method maintains block variables αk and combines their updates as αt+1 = αt + ht.
  • Theorem 5 establishes that the primal and dual iterates are related for all t ≥ 0 under quadratic loss and matched initialization.
  • Because the dual method converges linearly, the equivalent primal method also converges linearly.The same dual interpretation identifies CoCoA+ as arising from an inexact Step 5 and relates CoCoA+ to DANE.

A.4 Proof of Theorem 5

The proof specializes the primal-dual framework to ridge regression, writes the corresponding dual objective and distributed decomposition, and verifies the iterate relationship by induction. This establishes Theorem 5 for every t ≥ 0.

  • For quadratic loss, the primal problem becomes ridge regression, with a dual expressed in terms of X, y, λ, and α.The dual objective is given explicitly as a quadratic function of α.
  • The distributed primal objective is decomposed into node-specific functions Fk(w).This uses the partitioned data representation from the distributed setup.
  • The dual method exploits the quadratic structure of D and upper-bounds it with a node-separable quadratic approximation.The resulting block updates can then be written in a primal form.
  • The primal version of the dual method is rewritten through algebraic transformations to connect it with Algorithm 5.The derivation uses the relation between ∥w∥2 and ∥w − wt∥2 and identifies the corresponding perturbation term.
  • The iterate relationship is proved by induction, with the base case following from the initialization and the induction step from the algorithmic update definitions.The proof concludes that the relationship holds for all t ≥ 0.
  • The proof finishes Theorem 5 by establishing the claimed relationship for all t ≥ 0.
Loading 1610.02527v1…