Federated Optimization: Distributed Machine Learning for On-Device Intelligence

Jakub KonečnýH. Brendan McMahanDaniel RamagePeter Richtárik

article2016arXiv2,260 citations

Introduces the federated optimization framework to train centralized machine learning models across millions of decentralized edge devices holding heterogeneous data while minimizing communication rounds.

Listen

Modern mobile devices generate vast volumes of rich, sensitive data that could power intelligent services, but transferring this raw information to central data centers creates substantial privacy risks and demands high network bandwidth. The article addresses this challenge by formulating federated optimization, a distributed learning framework where user data remains locally on client devices. Under this model, personal phones and tablets act as compute nodes that perform local calculations and send small, ephemeral model updates to a central coordinating server, minimizing data collection and significantly reducing privacy exposure.

The primary objective of the article is to evaluate and demonstrate practical optimization algorithms capable of training a high-quality centralized model across a massive network of decentralized devices while strictly minimizing rounds of communication. In this operational setting, local computation is effectively free, but communication bandwidth is severely restricted, often limited to once-per-day cycles when devices are charging and connected to Wi-Fi.

To evaluate this framework, the authors conducted empirical simulations on a binary text-classification task using public Google+ post data partitioned across 10,000 distinct user nodes, covering more than two million training examples and over 20,000 features. The setup captures three defining constraints of federated environments: massively distributed data across thousands of nodes, highly unbalanced dataset sizes per user (ranging from 75 to 9,000 examples), and non-identically distributed (non-IID) local samples where individual users exhibit highly idiosyncratic patterns. To address these hurdles, the authors developed Federated Stochastic Variance Reduced Gradient (FSVRG), an algorithm incorporating adaptive local step sizes, sample-weighted aggregations, and specialized per-coordinate scaling matrices to accommodate extreme data sparsity.

The experimental findings show that existing distributed optimization methods fail under federated conditions. Popular frameworks like CoCoA+ converged slower than basic distributed gradient descent because their performance degrades as the number of nodes grows. In contrast, the proposed FSVRG algorithm achieved optimal test classification accuracy within just 30 communication rounds. When tested against an idealized baseline where data was randomly reshuffled among nodes to remove user-specific bias, FSVRG exhibited virtually identical convergence speeds. This confirms that its adaptive scaling and aggregation mechanisms successfully insulate the optimization process from non-IID and unbalanced data distortions.

These findings demonstrate that training machine learning models directly on decentralized mobile hardware is technically viable without sacrificing model quality or centralizing private user data. This decouples model training from direct data collection, lowering security liabilities and aligning with data minimization regulations. Next steps supported by the article include developing asynchronous update protocols that accommodate intermittently connected devices, extending the optimization framework to non-convex neural network architectures, and exploring personalized hybrid models that tailor global predictions to individual user behavior.

Decision-makers should note that the current experimental validation is primarily limited to sparse, convex generalized linear models under simulated synchronous conditions. While the conceptual principles are sound, applying this approach to deep learning or unconstrained consumer edge networks will require further pilot testing to establish empirical convergence and operational stability.

Google University of Edinburgh communication data points machine learning Data Optimization Algorithm

arXiv: 1610.02527

Paper: Federated Learning: Strategies for Improving Communication Efficiency, Jakub Konečný et al. (2016). This foundational paper immediately precedes and develops the core communication-reduction strategies for federated learning introduced in the source.

Paper: Federated Learning: Challenges, Methods, and Future Directions, Tian Li et al. (2019). This comprehensive survey extends the source by categorizing subsequent federated learning challenges, methods, and practical open research directions.
Paper: Advances and Open Problems in Federated Learning, P. Kairouz et al. (2019). This extensive collaborative survey builds directly on the source's problem formulation to catalog advanced techniques and open problems across the field.

Cover for Federated Optimization: Distributed Machine Learning for On-Device Intelligence

Abstract

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.

Topics

communication data points machine learning mobile devices optimization optimization problems

Keywords

Data Optimization Algorithm Distributed Algorithms Learning Federated Optimization Stochastic Machine Learning Setting

1 Introduction
1.1 Problem Formulation
1.2 The Setting of Federated Optimization
2 Related Work
2.1 Baseline Algorithms
2.2 A Novel Breed of Randomized Algorithms
2.3 Distributed Setting
2.3.1 A Paradigm for Measuring Distributed Optimization Efficiency
2.3.2 Distributed Algorithms
2.3.3 Communication-Efficient Algorithms
3 Algorithms for Federated Optimization
3.1 Desirable Algorithmic Properties
3.2 SVRG
3.3 Distributed Problem Formulation
3.4 DANE
3.5 SVRG meets DANE
3.6 Federated SVRG
3.6.1 Notation
3.6.2 Intuition Behind FSVRG Updates
3.7 Further Notes
4 Experiments
4.1 Predicting Comments on Public Google+ Posts
5 Conclusions and Future Challenges
References
A Distributed Optimization via Quadratic Perturbations
A.1 New Method
A.2 L2-Regularized Linear Predictors
A.3 A Dual Method: Dual Block Proximal Gradient Ascent
A.4 Proof of Theorem

Knowls

Knowl 1 — Federated Optimization Problem Formulation and Core Characteristics
definition
Federated optimization is a distributed empirical risk minimization framework designed for decentralized, on-device machine learning tasks. The optimization objective is formulated as minimizing a finite-sum loss function:

$\min_{w \in \mathbb{R}^d} f(w) \quad \text{where} \quad f(w) \triangleq \frac{1}{n} \sum_{i=1}^n f_i(w) = \sum_{k=1}^K \frac{n_k}{n} F_k(w)$

where $n$ is the total number of training examples, $K$ is the total number of client devices/nodes, $\mathcal{P}_k \subset \{1, \dots, n\}$ denotes the disjoint partition of indices held locally on node $k$ with $n_k = |\mathcal{P}_k|$ and $\sum_{k=1}^K n_k = n$ , and $F_k(w) \triangleq \frac{1}{n_k} \sum_{i \in \mathcal{P}_k} f_i(w)$ is the local empirical loss on node $k$ .

The setting is governed by four distinct characteristics:
- Massively Distributed: The number of nodes $K$ is extremely large, often much larger than the average number of examples per node ( $K \gg n/K$ ).
- Non-IID: Local data distributions differ across devices; data on any single node is not a representative sample of the global distribution.
- Unbalanced: Different nodes hold drastically different numbers of data points ( $n_k$ can vary by orders of magnitude across $k$ ).
- Extreme Communication Constraints: Communication between devices and the server is intermittent, slow, and expensive, making the total number of communication rounds the primary metric to minimize.
Knowl 2 — Federated Stochastic Variance Reduced Gradient (FSVRG)
algorithm
Federated SVRG (FSVRG) is a communication-efficient distributed optimization algorithm adapted for non-IID, unbalanced, and sparse datasets across $K$ nodes. It scales local step sizes inversely with local sample size, applies diagonal scaling matrices $S_k$ to stochastic gradient corrections, and scales global parameter aggregation with matrix $A$ .
Input: Global stepsize parameter $h > 0$ , data partition $\{\mathcal{P}_k\}_{k=1}^K$ , scaling matrices $A, S_k \in \mathbb{R}^{d \times d}$ for $k \in \{1, \dots, K\}$ , initial model $w^0 \in \mathbb{R}^d$
for $s = 0, 1, 2, \dots$ do
    Compute global gradient $\nabla f(w^s) = \frac{1}{n} \sum_{i=1}^n \nabla f_i(w^s)$ and distribute $\nabla f(w^s)$ and $w^s$ to all nodes
    for $k = 1$ to $K$ in parallel do
        Initialize local model $w_k = w^s$ and local stepsize $h_k = h / n_k$
        Let $\{i_t\}_{t=1}^{n_k}$ be a random permutation of $\mathcal{P}_k$
        for $t = 1, \dots, n_k$ do
             $w_k = w_k - h_k \left( S_k (\nabla f_{i_t}(w_k) - \nabla f_{i_t}(w^s)) + \nabla f(w^s) \right)$
        end for
    end for
    Server aggregates updates: $w^{s+1} = w^s + A \sum_{k=1}^K \frac{n_k}{n} (w_k - w^s)$
end for
Here, $n = \sum_{k=1}^K n_k$ , each worker performs a single full pass ( $n_k$ steps) over its local data per communication round, and the server coordinates synchronous gradient aggregation and iterate updates.
Knowl 3 — Sparsity-Aware Gradient and Aggregation Scaling Matrices in FSVRG
model/method
In high-dimensional sparse linear models where data points $x_i \in \mathbb{R}^d$ have sparse coordinates, FSVRG employs per-coordinate, per-node diagonal scaling matrices to prevent gradient overshoot on skewed partitions and accelerate convergence on disjoint features.

Let $e_j \in \mathbb{R}^d$ be the $j$ -th standard basis vector. The quantities are defined as:
- $n^j = |\{i \in \{1, \dots, n\} : x_i^T e_j \neq 0\}|$ : total number of data points globally with non-zero $j$ -th coordinate.
- $n_k^j = |\{i \in \mathcal{P}_k : x_i^T e_j \neq 0\}|$ : number of data points on node $k$ with non-zero $j$ -th coordinate.
- $\phi^j = n^j / n$ : global frequency of non-zero entries in coordinate $j$ .
- $\phi_k^j = n_k^j / n_k$ : local frequency of non-zero entries in coordinate $j$ on node $k$ .
- $s_k^j = \phi^j / \phi_k^j$ : ratio of global to local appearance frequency for coordinate $j$ on node $k$ , forming the diagonal matrix $S_k = \text{Diag}(s_k^1, \dots, s_k^d)$ . If $\phi_k^j = 0$ , $s_k^j$ can be set to 0.
- $\omega^j = |\{k \in \{1, \dots, K\} : n_k^j \neq 0\}|$ : total number of nodes containing at least one data point with non-zero $j$ -th coordinate.
- $a^j = K / \omega^j$ : coordinate-wise aggregation factor, forming the diagonal matrix $A = \text{Diag}(a^1, \dots, a^d)$ .
The local gradient scaling $S_k$ ensures that stochastic updates do not over-amplify gradient magnitudes for features that are rare globally but locally over-represented on node $k$ . The global aggregation scaling $A$ interpolates between simple averaging ( $a^j = 1$ when a feature appears on all $K$ nodes) and disjoint parameter addition ( $a^j = K$ when a feature appears on only 1 node).
Knowl 4 — Desirable Algorithmic Properties for Federated Optimization
definition
An effective algorithm for non-IID, unbalanced, and massively distributed federated optimization is expected to satisfy four structural properties:
- (A) Fixed Point at Optimality: If the global parameter $w^0$ is initialized at the optimal solution $w^*$ , the algorithm remains at $w^*$ ( $w^t = w^*$ for all $t \ge 0$ ).
- (B) Single-Node Convergence: If all training data resides on a single node ( $K = 1$ ), the algorithm converges to the global minimum in $\mathcal{O}(1)$ (ideally 1) round of communication.
- (C) Decomposable / Disjoint Feature Convergence: If each feature appears on only a single node (so that the objective decomposes into disjoint parameter blocks for generalized linear models), the algorithm converges to the global minimum in $\mathcal{O}(1)$ (ideally 1) round of communication.
- (D) Identical Local Datasets Convergence: If every node holds an identical copy of the full dataset, the algorithm converges in $\mathcal{O}(1)$ (ideally 1) round of communication.
Knowl 5 — Equivalence of Inexact DANE and Naive Federated SVRG
theoretical result
Consider the Distributed Approximate Newton (DANE) algorithm with regularizer $\mu = 0$ and stepsize parameter $\eta = 1$ , where the local optimization subproblem on node $k$ at round $s$ is:

$w_k = \arg\min_{w \in \mathbb{R}^d} \left\{ F_k(w) - (\nabla F_k(w^s) - \nabla f(w^s))^T w \right\}$

If each node solves this subproblem by applying one epoch of Stochastic Variance Reduced Gradient (SVRG) initialized at $w^s$ , the stochastic update direction generated for sampled index $i \in \mathcal{P}_k$ is:

$\left[ \nabla f_i(w) - (\nabla F_k(w^s) - \nabla f(w^s)) \right] - \left[ \nabla f_i(w^s) - (\nabla F_k(w^s) - \nabla f(w^s)) \right] + \nabla f(w^s) = \nabla f_i(w) - \nabla f_i(w^s) + \nabla f(w^s)$

This update is identical to the stochastic update step of naive Federated SVRG (FSVRG). Consequently, under identical initializations $w^s$ and identical stochastic sampling sequences, solving the DANE subproblem with an SVRG local solver produces exactly the same iterate sequence $\{w^s\}$ as naive FSVRG.
Knowl 6 — Naive Federated SVRG (FSVRG)
algorithm
Naive Federated SVRG is a distributed baseline that extends SVRG to multiple parallel nodes without per-coordinate feature scaling or partition-size-adaptive step sizes.
Input: Number of stochastic steps per epoch $m$ , stepsize $h > 0$ , data partition $\{\mathcal{P}_k\}_{k=1}^K$ , initial parameter $w^0 \in \mathbb{R}^d$
for $s = 0, 1, 2, \dots$ do
    Compute global gradient $\nabla f(w^s) = \frac{1}{n} \sum_{i=1}^n \nabla f_i(w^s)$ and distribute it to all $K$ nodes
    for $k = 1$ to $K$ in parallel do
        Initialize $w_k = w^s$
        for $t = 1$ to $m$ do
            Sample $i \in \mathcal{P}_k$ uniformly at random
             $w_k = w_k - h \left( \nabla f_i(w_k) - \nabla f_i(w^s) + \nabla f(w^s) \right)$
        end for
    end for
    Update global model: $w^{s+1} = w^s + \frac{1}{K} \sum_{k=1}^K (w_k - w^s)$
end for
Knowl 7 — Duality Equivalence between Primal Quadratic Perturbation and Dual Block Proximal Gradient Ascent
theoretical result
For $L_2$ -regularized linear prediction problems with quadratic loss $\phi_i(t) = \frac{1}{2}(t - y_i)^2$ , the primal empirical risk minimization problem is:

$\min_{w \in \mathbb{R}^d} f(w) = \frac{1}{2n} \|X^T w - y\|^2 + \frac{\lambda}{2} \|w\|^2$

where $X = [X_1, \dots, X_K] \in \mathbb{R}^{d \times n}$ with $X_k \in \mathbb{R}^{d \times |\mathcal{P}_k|}$ , $y \in \mathbb{R}^n$ , $\lambda > 0$ , and local subproblems are $F_k(w) = \frac{K}{2n} \|X_k^T w - y_k\|^2 + \frac{\lambda}{2}\|w\|^2$ with equal partition sizes $|\mathcal{P}_k| = n/K$ .

Let $\sigma \in [1, K]$ satisfy $X^T X \preceq \sigma \text{Diag}(X_1^T X_1, \dots, X_K^T X_K)$ , $\eta = K/\sigma$ , and $\mu = \lambda(\eta - 1)$ . If dual variables $\alpha^0 \in \mathbb{R}^n$ and primal variables $w^0 \in \mathbb{R}^d$ are initialized such that $w^0 = \frac{1}{\lambda n} X \alpha^0$ , then the sequence of primal iterates $w^t$ produced by the Primal Quadratic Perturbation Method and the sequence of dual iterates $\alpha^t$ produced by Dual Block Proximal Gradient Ascent satisfy:

$w^t = \frac{1}{\lambda n} X \alpha^t \quad \text{for all } t \ge 0$

This proves that primal quadratic perturbation methods (related to DANE) and dual block coordinate ascent frameworks (such as CoCoA+) are dual representations of one another for regularized quadratic objectives.
Knowl 8 — Primal Quadratic Perturbation Method for Distributed Optimization
algorithm
The Primal Quadratic Perturbation Method solves $L_2$ -regularized distributed optimization problems by maintaining local correction vectors $g_k^t$ that satisfy $\sum_{k=1}^K g_k^t = 0$ for all $t \ge 0$ .
Input: Data matrices $X_k \in \mathbb{R}^{d \times |\mathcal{P}_k|}$ , regularization $\lambda > 0$ , parameter $\sigma \in [1, K]$
Choose initial dual vectors $\alpha_k^0 \in \mathbb{R}^{|\mathcal{P}_k|}$ for $k = 1, \dots, K$
Set $\eta = K / \sigma$ and $\mu = \lambda(\eta - 1)$
Set $w^0 = \frac{1}{\lambda n} \sum_{k=1}^K X_k \alpha_k^0$
Set $g_k^0 = \eta \left( \frac{K}{n} X_k \alpha_k^0 - \lambda w^0 \right)$ for $k = 1, \dots, K$
for $t = 0, 1, 2, \dots$ do
    for $k = 1$ to $K$ in parallel do
         $w_k^{t+1} = \arg\min_{w \in \mathbb{R}^d} \left\{ F_k(w) - \left( \nabla F_k(w^t) - (\eta \nabla F_k(w^t) + g_k^t) \right)^T w + \frac{\mu}{2} \|w - w^t\|^2 \right\}$
    end for
     $w^{t+1} = \frac{1}{K} \sum_{k=1}^K w_k^{t+1}$
    for $k = 1$ to $K$ in parallel do
         $g_k^{t+1} = g_k^t + \lambda \eta (w_k^{t+1} - w^{t+1})$
    end for
end for
Knowl 9 — Google+ Comment Prediction Benchmark Setup
experimental setup
To evaluate federated optimization under realistic non-IID, unbalanced, and sparse distributions, a binary classification benchmark is constructed from public Google+ posts to predict whether a post receives at least one comment:
- Client Partitioning: $K = 10,000$ authors (each simulating an independent node) who authored at least 100 public English posts.
- Dataset Scale: $n = 2,166,693$ total training examples partitioned chronologically per user (first 75% for training, remaining 25% for test evaluation).
- Unbalanced Distribution: Local dataset sizes $n_k$ range from 75 to 9,000 examples per user (mean $n_k \approx 216$ ).
- Feature Representation & Sparsity: Bag-of-words dictionary of the 20,000 most frequent words across Google+, plus a bias term and an unknown-word indicator ( $d = 20,002$ ). Over 88% of features appear on fewer than 1,000 nodes.
- Model: $L_2$ -regularized logistic regression with regularization parameter $\lambda = 1/n$ .
Knowl 10 — Convergence and Robustness of FSVRG on Non-IID Federated Data
empirical result
On the 10,000-user Google+ binary classification task, baseline naive predictors achieve a 33.16% test classification error by always predicting -1 (no comment), and 17.14% error using a per-author majority baseline. The optimal global centralized logistic regression model achieves 26.27% test classification error.

When evaluated against alternative distributed optimization algorithms:
- FSVRG converges to the optimal test classification accuracy (26.27% error) and minimal primal suboptimality in approximately 30 rounds of communication.
- Distributed Gradient Descent (GD) exhibits very slow convergence, reaching roughly 30.5% test error after 30 communication rounds.
- CoCoA+ converges even more slowly than distributed GD due to its dependency on the data aggregation parameter $\sigma' \approx K = 10,000$ , achieving approximately 33% test error after 30 rounds.
- FSVRGR (FSVRG applied to an IID-reshuffled version of the same unbalanced dataset) yields convergence curves nearly identical to FSVRG on the non-IID data, demonstrating that the local step size $h_k$ , gradient scaling $S_k$ , and coordinate aggregation matrix $A$ make FSVRG robust against non-IID data skew.

Coverage note — Omitted general background reviews of single-node optimization (GD, SGD, SAG, SAGA, RCD) and generic distributed literature (ADMM, parameter servers) as they are standard prior work.

References

1.Martın Abadi, Andy Chu, Ian Goodfellow, Brendan H McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. arXiv:1607.00133, 2016.
2.Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In Advances in Neural Information Processing Systems, pages 873–881, 2011.
3.Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. arXiv:1603.05953, 2016.
4.Zeyuan Allen-Zhu, Yang Yuan, and Karthik Sridharan. Exploiting the structure: Stochastic gradient methods using raw clusters. arXiv:1602.02151, 2016.
5.Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Advances in Neural Information Processing Systems, pages 1756–1764, 2015.
6.Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
7.Dimitri P Bertsekas. Distributed asynchronous computation of fixed points. Mathematical Programming, 27(1):107–120, 1983.
8.Dimitri P Bertsekas and John N Tsitsiklis. Parallel and distributed computation: numerical methods. Prentice-Hall, Inc., 1989.
9.Antoine Bordes, Leon Bottou, and Patrick Gallinari. Sgd-qn: Careful quasi-Newton stochastic gradient descent. The Journal of Machine Learning Research, 10:1737–1754, 2009.
10.Leon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium on learning and data science, 2009.
11.Leon Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade, pages 421–436. Springer, 2012.
12.Leon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. arXiv:1606.04838, 2016.
13.Olivier Bousquet and Leon Bottou. The tradeoffs of large scale learning. In Advances in Neural Information Processing Systems, pages 161–168, 2008.
14.Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and TrendsR in Machine Learning, 3(1):1–122, 2011.
15.Joseph Bradley, Aapo Kyrola, Daniel Bickson, and Carlos Guestrin. Parallel coordinate descent for l1-regularized loss minimization. In Proceedings of the 28th International Conference on Machine Learning, pages 321–328, 2011.
16.Richard H Byrd, Samantha L Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-Newton method for large-scale optimization. SIAM Journal on Optimization, 26(2):1008–1031, 2016.
17.Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12:1069–1109, 2011.
18.Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pages 571–582, 2014.
19.CNN. Where (and when) do you use your smartphone: Bedroom? Church? News article http://edition.cnn.com/2013/07/13/tech/smartphone-use-survey/, 2013.
20.Dominik Csiba and Peter Richtarik. Primal method for ERM with flexible mini-batching schemes and non-convex losses. arXiv:1506.02227, 2015.
21.Dominik Csiba and Peter Richtarik. Coordinate descent face-off: primal or dual? arXiv:1605.08982, 2016.
22.Christopher M De Sa, Ce Zhang, Kunle Olukotun, and Christopher Re. Taming the wild: A unified analysis of hogwild-style algorithms. In Advances in Neural Information Processing Systems, pages 2656–2664, 2015.
23.Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang, Quoc V Le, et al. Large scale distributed deep networks. In Advances in Neural Information Processing Systems, pages 1223–1231, 2012.
24.Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008.
25.Aaron Defazio. A simple practical accelerated method for finite sums. arXiv preprint arXiv:1602.02442, 2016.
26.Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pages 1646–1654, 2014.
27.Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. The Journal of Machine Learning Research, 13(1):165–202, 2012.
28.Wei Deng and Wotao Yin. On the global and linear convergence of the generalized alternating direction method of multipliers. Journal of Scientific Computing, 66(3):889–916, 2016.
29.John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimization: convergence analysis and network scaling. Automatic control, IEEE Transactions on, 57(3):592–606, 2012.
30.John C Duchi, Sorathan Chaturapruek, and Christopher Re. Asynchronous stochastic convex optimization. arXiv:1508.00882, 2015.
31.John C Duchi, Michael I Jordan, and Brendan H McMahan. Estimation, optimization, and parallelism when data is sparse. In Advances in Neural Information Processing Systems, pages 2832–2840, 2013.
32.John C Duchi, Michael I Jordan, and Martin J Wainwright. Privacy aware learning. Journal of the Association for Computing Machinery, 2014.
33.Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science. Now Publishers, 2014.
34.Olivier Fercoq, Zheng Qu, Peter Richtarik, and Martin Takaɵc. Fast distributed coordinate descent for non-strongly convex losses. In Machine Learning for Signal Processing (MLSP), 2014 IEEE International Workshop on, pages 1–6. IEEE, 2014.
35.Olivier Fercoq and Peter Richtarik. Accelerated, parallel, and proximal coordinate descent. SIAM Journal on Optimization, 25(4):1997–2023, 2015.
36.The MPI Forum. MPI: A message passing interface standard, Version 3.1. Document available at http://www.mpi-forum.org/, 2015.
37.Roy Frostig, Rong Ge, Sham M Kakade, and Aaron Sidford. Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
38.Robert Mansel Gower, Donald Goldfarb, and Peter Richtarik. Stochastic block BFGS: squeezing more curvature out of data. In Proceedings of The 33rd International Conference on Machine Learning, pages 1869–1878, 2016.
39.Robert Mansel Gower and Peter Richtarik. Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms. arXiv:1602.01768, pages 1869–1878, 2016.
40.Mert Gurbuzbalaban, Asu Ozdaglar, and Pablo Parrilo. Why random reshuffling beats stochastic gradient descent. arXiv:1510.08560, 2015.
41.Reza Harikandeh, Mohamed Osama Ahmed, Alim Virani, Mark Schmidt, Jakub Konecny, and Scott Sallinen. Stop wasting my gradients: Practical SVRG. In Advances in Neural Information Processing Systems, pages 2251–2259, 2015.
42.Martin Jaggi, Virginia Smith, Martin Takaɵc, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, and Michael I Jordan. Communication-efficient distributed dual coordinate ascent. In Advances in Neural Information Processing Systems, pages 3068–3076, 2014.
43.Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315–323, 2013.
44.Jakub Konecny, Jie Liu, Peter Richtarik, and Martin Takaɵc. Mini-batch semi-stochastic gradient descent in the proximal setting. IEEE Journal of Selected Topics in Signal Processing, 10(2):242–255, 2016.
45.Jakub Konecny, Brendan H McMahan, and Daniel Ramage. Federated optimization: Distributed optimization beyond the datacenter. arXiv:1511.03575, 2015.
46.Jakub Konecny, Zheng Qu, and Peter Richtarik. Semi-stochastic coordinate descent. arXiv:1412.6293, 2014.
47.Jakub Konecny and Peter Richtarik. Semi-stochastic gradient descent methods. arXiv:1312.1666, 2013.
48.Remi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien. ASAGA: Asynchronous parallel saga. arXiv:1606.04809, 2016.
49.Yann A LeCun, Leon Bottou, Genevieve B Orr, and Klaus-Robert Muller. Efficient backprop. In Neural networks: Tricks of the trade, pages 9–48. Springer, 2012.
50.Jason Lee, Tengyu Ma, and Qihang Lin. Distributed stochastic variance reduced gradient methods. arXiv:1507.07595, 2015.
51.Yin Tat Lee and Aaron Sidford. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 147–156. IEEE, 2013.
52.Chieh-Yen Lin, Cheng-Hao Tsai, Ching-Pei Lee, and Chih-Jen Lin. Large-scale logistic regression and linear support vector machines using spark. In Big Data (Big Data), 2014 IEEE International Conference on, pages 519–528. IEEE, 2014.
53.Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimization. In Advances in Neural Information Processing Systems, pages 3366–3374, 2015.
54.Dong C Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical programming, 45(1-3):503–528, 1989.
55.Ji Liu and Stephen J Wright. Asynchronous stochastic coordinate descent: Parallelism and convergence properties. SIAM Journal on Optimization, 25(1):351–376, 2015.
56.Ji Liu, Stephen J Wright, Christopher Re, Victor Bittorf, and Srikrishna Sridhar. An asynchronous parallel stochastic coordinate descent algorithm. Journal of Machine Learning Research, 16:285–322, 2015.
57.Chenxin Ma, Jakub Konecny, Martin Jaggi, Virginia Smith, Michael I Jordan, Peter Richtarik, and Martin Takaɵc. Distributed optimization with arbitrary local solvers. arXiv:1512.04039, 2015.
58.Chenxin Ma, Virginia Smith, Martin Jaggi, Michael Jordan, Peter Richtarik, and Martin Takaɵc. Adding vs. averaging in distributed primal-dual optimization. In Proceedings of The 32nd International Conference on Machine Learning, pages 1973–1982, 2015.
59.Dhruv Mahajan, Nikunj Agrawal, S Sathiya Keerthi, S Sundararajan, and Leon Bottou. An efficient distributed learning algorithm based on effective local functional approximations. arXiv preprint arXiv:1310.8418, 2013.
60.Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. arXiv:1507.06970, 2015.
61.Jakub Marecek, Peter Richtarik, and Martin Takaɵc. Distributed block coordinate descent for minimizing partially separable functions. In Numerical Analysis and Optimization, pages 261–288. Springer, 2015.
62.Brendan H McMahan, Eider Moore, Daniel Ramage, and Blaise Aguera y Arcas. Federated learning of deep networks using model averaging. arXiv:1602.05629, 2016.
63.Philipp Moritz, Robert Nishihara, and Michael Jordan. A linearly-convergent stochastic l-bfgs algorithm. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 249–258, 2016.
64.Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pages 451–459, 2011.
65.Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances in Neural Information Processing Systems, pages 1017–1025, 2014.
66.Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009.
67.Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341–362, 2012.
68.Yurii Nesterov. A method of solving a convex programming problem with convergence rate o(1/k2). Soviet Mathematics Doklady, 27(2):372–376, 1983.
69.Yurii Nesterov. Introductory Lectures on Convex Optimization. A Basic Course. Kluwer, 2004.
70.Jiquan Ngiam, Adam Coates, Ahbik Lahiri, Bobby Prochnow, Quoc V Le, and Andrew Y Ng. On optimization methods for deep learning. In Proceedings of the 28th International Conference on Machine Learning, pages 265–272, 2011.
71.Feng Niu, Benjamin Recht, Christopher Re, and Stephen Wright. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 693–701, 2011.
72.Zhimin Peng, Yangyang Xu, Ming Yan, and Wotao Yin. Arock: an algorithmic framework for asynchronous parallel coordinate updates. arXiv:1506.02396, 2015.
73.B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964.
74.Zheng Qu, Peter Richtarik, Martin Takaɵc, and Olivier Fercoq. SDNA: Stochastic dual newton ascent for empirical risk minimization. In Proceedings of The 33rd International Conference on Machine Learning, pages 1823–1832, 2016.
75.Zheng Qu, Peter Richtarik, and Tong Zhang. Quartz: Randomized dual coordinate ascent with arbitrary sampling. In Advances in Neural Information Processing Systems, volume 28, pages 865–873, 2015.
76.Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. On variance reduction in stochastic gradient descent and its asynchronous variants. In Advances in Neural Information Processing Systems, pages 2647–2655, 2015.
77.Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. arXiv:1603.06160, 2016.
78.Sashank J Reddi, Jakub Konecny, Peter Richtarik, Barnabas Poczos, and Alex Smola. AIDE: Fast and communication efficient distributed optimization. arXiv:1608.06879, 2016.
79.Peter Richtarik and Martin Takaɵc. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming, 144(1-2):1–38, 2014.
80.Peter Richtarik and Martin Takaɵc. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 156(1):433–484, 2016.
81.Peter Richtarik and Martin Takaɵc. Distributed coordinate descent method for learning with big data. Journal of Machine Learning Research, 17(75):1–25, 2016.
82.Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400–407, 1951.
83.Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In Advances in Neural Information Processing Systems, pages 2663–2671, 2012.
84.Mark Schmidt, Reza Babanezhad, Mohamed Ahmed, Aaron Defazio, Ann Clifton, and Anoop Sarkar. Non-uniform stochastic average gradient method for training conditional random fields. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, pages 819–828, 2015.
85.Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. arXiv:1309.2388, 2013.
86.Shai Shalev-Shwartz. SDCA without duality, regularization, and individual convexity. arXiv:1602.01582, 2016.
87.Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal estimated sub-gradient solver for svm. Mathematical programming, 127(1):3–30, 2011.
88.Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss. The Journal of Machine Learning Research, 14(1):567–599, 2013.
89.John Shalf, Sudip Dosanjh, and John Morrison. Exascale computing technology challenges. In High Performance Computing for Computational Science–VECPAR 2010, pages 1–25. Springer, 2011.
90.Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. In Communication, Control and Computing (Allerton), 2014 52nd Annual Allerton Conference on, pages 850–857. IEEE, 2014.
91.Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-efficient distributed optimization using an approximate newton-type method. In Proceedings of the 31st International Conference on Machine Learning, pages 1000–1008, 2014.
92.Virginia Smith, Simone Forte, Michael I Jordan, and Martin Jaggi. L1-regularized distributed optimization: A communication-efficient primal-dual framework. arXiv:1512.04011, 2015.
93.Martin Takaɵc, Avleen Bijral, Peter Richtarik, and Nathan Srebro. Mini-batch primal and dual methods for SVMs. In Proceedings of the 30th International Conference on Machine Learning, 2013.
94.Martin Takaɵc, Peter Richtarik, and Nathan Srebro. Distributed mini-batch SDCA. arXiv:1507.08322, 2015.
95.John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, DTIC Document, 1984.
96.Vladimir N Vapnik. An overview of statistical learning theory. Neural Networks, IEEE Transactions on, 10(5):988–999, 1999.
97.Huahua Wang and Arindam Banerjee. Randomized block coordinate descent for online and stochastic optimization. arXiv:1407.0107, 2014.
98.White House Report. Consumer data privacy in a networked world: A framework for protecting privacy and promoting innovation in the global digital economy. Journal of Privacy and Confidentiality, 2013.
99.Blake Woodworth and Nathan Srebro. Tight complexity bounds for optimizing composite objectives. arXiv:1605.08003, 2016.
100.Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057–2075, 2014.
101.Tianbao Yang. Trading computation for communication: Distributed stochastic dual coordinate ascent. In Advances in Neural Information Processing Systems, pages 629–637, 2013.
102.Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, and Ion Stoica. Spark: cluster computing with working sets. In Proceedings of the 2nd USENIX conference on Hot topics in cloud computing, volume 10, page 10, 2010.
103.Yuchen Zhang, John Duchi, Michael I Jordan, and Martin J Wainwright. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems, pages 2328–2336, 2013.
104.Yuchen Zhang, John C Duchi, and Martin J Wainwright. Communication-efficient algorithms for statistical optimization. Journal of Machine Learning Research, 14:3321–3363, 2013.
105.Yuchen Zhang and Xiao Lin. DiSCO: Distributed optimization for self-concordant empirical loss. In Proceedings of The 32th International Conference on Machine Learning, pages 362–370, 2015.
106.Yong Zhuang, Wei-Sheng Chin, Yu-Chin Juan, and Chih-Jen Lin. Distributed newton methods for regularized logistic regression. In Advances in Knowledge Discovery and Data Mining, pages 690–703. Springer, 2015.
107.Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J Smola. Parallelized stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 2595–2603, 2010.

Citation

MLA

Konečný, J., et al. “Federated Optimization: Distributed Machine Learning for On-Device Intelligence”. arXiv, 2016, http://arxiv.org/abs/1610.02527v1.

APA

Konečný, J., McMahan, H. B., Ramage, D., & Richtárik, P. (2016). Federated Optimization: Distributed Machine Learning for On-Device Intelligence. arXiv. http://arxiv.org/abs/1610.02527v1

Chicago

Konečný, J., H. B. McMahan, D. Ramage, and P. Richtárik. 2016. “Federated Optimization: Distributed Machine Learning for On-Device Intelligence”. arXiv. http://arxiv.org/abs/1610.02527v1.

Harvard

Konečný, J. et al. (2016) “Federated Optimization: Distributed Machine Learning for On-Device Intelligence”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1610.02527v1.

Vancouver

1. Konečný J, McMahan HB, Ramage D, Richtárik P (2016) Federated Optimization: Distributed Machine Learning for On-Device Intelligence. arXiv

BibTeX

@article{konecny2016federated,
  title = {Federated Optimization: Distributed Machine Learning for On-Device Intelligence},
  author = {Konečný, Jakub and McMahan, H. Brendan and Ramage, Daniel and Richtárik, Peter},
  year = {2016},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1610.02527v1},
  eprint = {1610.02527}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

Federated Optimization: Distributed Machine Learning for On-Device Intelligence

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Federated Optimization Problem Formulation and Core Characteristics

Knowl 2 — Federated Stochastic Variance Reduced Gradient (FSVRG)

Knowl 3 — Sparsity-Aware Gradient and Aggregation Scaling Matrices in FSVRG

Knowl 4 — Desirable Algorithmic Properties for Federated Optimization

Knowl 5 — Equivalence of Inexact DANE and Naive Federated SVRG

Knowl 6 — Naive Federated SVRG (FSVRG)

Knowl 7 — Duality Equivalence between Primal Quadratic Perturbation and Dual Block Proximal Gradient Ascent

Knowl 8 — Primal Quadratic Perturbation Method for Distributed Optimization

Knowl 9 — Google+ Comment Prediction Benchmark Setup

Knowl 10 — Convergence and Robustness of FSVRG on Non-IID Federated Data

References

Citation

BibTeX

Access the Paper