Source-linked AI summary
Federated Optimization:Distributed Optimization Beyond the Datacenter
Jakub Konečný, Brendan McMahan, Daniel Ramage
TL;DR
The paper introduces federated optimization for learning from massive, non-IID, unbalanced datasets distributed across nodes, where communication efficiency is critical. It proposes a sparsity-aware method motivated by SVRG and DANE, and experiments report rapid convergence and robustness to non-IID data. The paper identifies missing datasets, broader experiments, and theoretical justification as important open limitations.
Problem
Federated optimization addresses centralized-model training when data are massively distributed, non-IID, unbalanced, and communication is severely constrained.
Method
The proposed method combines SVRG-style local optimization with DANE’s distributed structure and sparsity-aware update scaling and aggregation.
Results
DSVRG reaches optimality in very few communication rounds and loses very little performance relative to randomly reshuffled data, while existing communication-efficient methods are inefficient in this setting.
Takeaways & Limitations
Federated optimization is presented as an increasingly important setting for practical learning with mobile-device data, privacy concerns, and limited connectivity.
Takeaways & Limitations
The method lacks proper theoretical justification, and larger experiments and naturally user-clustered public datasets remain needed.
Abstract
from arXiv · showhide
We introduce a new and increasingly relevant setting for distributed optimization in machine learning, where the data defining the optimization are distributed (unevenly) over an extremely large number of \nodes, but the goal remains to train a high-quality centralized model. We refer to this setting as Federated Optimization. In this setting, communication efficiency is of utmost importance. A motivating example for federated optimization arises when we keep the training data locally on users' mobile devices rather than logging it to a data center for training. Instead, the mobile devices are used as nodes performing computation on their local data in order to update a global model. We suppose that we have an extremely large number of devices in our network, each of which has only a tiny fraction of data available totally; 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, we 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. This work also sets a path for future research needed in the context of federated optimization.
1 Introduction and Problem Formulation
Distributed optimization addresses finite-sum machine-learning objectives when growing datasets cannot be stored on one node, but communication becomes the dominant practical bottleneck. Communication-efficient methods therefore shift computation locally between communication rounds.
- Growing datasets make solving the centralized finite-sum objective on one node infeasible because storage becomes a constraint.
- Distributed optimization solves the objective without giving any single node direct access to all data.
- Communication cost is the largest bottleneck, and per-iteration communication can dramatically reduce practical performance.
- Communication-efficient algorithms perform substantial local computation before each communication round to balance computation and communication costs.
- Existing distributed methods establish basic theory and adaptations, but many open questions remain in this relatively new area.
2 Federated Optimization — The Challenge of Learning from Decentralized Data
Federated optimization targets distributed learning where conventional assumptions about node count, representative samples, and balanced data fail. The setting prioritizes communication minimization, especially for privacy-sensitive data retained on mobile devices.
- Federated optimization addresses settings where existing methods assume fewer nodes than local datapoints, IID samples, and typically equal node sizes.
- Its data are massively distributed, non-IID across nodes, and unbalanced in the number of training examples held by each node.
- The paper focuses on sparse data and uses sparsity structure to develop an effective federated-optimization algorithm.
- Mobile-device data may be privacy sensitive and reflect distinct usage patterns, motivating local computation rather than centralized collection.
- Limited connectivity may permit only one communication round per day, making communication rounds the practical objective to minimize.
3 An Algorithm for Federated Optimization
The proposed method connects DANE’s distributed subproblems with SVRG’s local variance-reduced solver, then adapts stepsizes, stochastic updates, and aggregation to federated data sparsity. These modifications target failures of basic distributed SVRG in sparse, heterogeneous settings.
- The algorithm is motivated by a connection between SVRG for single-node variance reduction and DANE for distributed optimization.
- Using SVRG as an approximate DANE local solver yields a distributed version of SVRG.
- Basic distributed SVRG can fail in federated optimization, particularly when data are sparse.
- The modified method uses node-specific stepsizes, sparsity-aware diagonal scaling of stochastic updates, and data-adaptive aggregation.
- The matrices S_k and A correct for feature-frequency differences and take longer steps for features present on fewer nodes.
4 Experiments
The experiments evaluate distributed optimization on a large, unbalanced, non-IID user dataset and compare communication-efficient algorithms by communication rounds, objective value, and test prediction error. The proposed DSVRG method reaches optimality in few rounds and retains nearly the performance of randomly reshuffled data.
- Experimental setup: The experiment uses 10,000 authors as nodes for binary post-comment prediction, with 2,166,693 training examples and a 20,000-word bag-of-words logistic regression model.Each author’s data are split chronologically, using earlier posts for training and later posts for testing.
- Experimental setup: Node data are substantially unbalanced, ranging from 75 to 9,000 examples, and cannot be considered IID samples from the overall distribution.The average node contains approximately 216 data points.
- Algorithm comparison: Figure 1 compares optimization algorithms using rounds of communication against objective function and test prediction error.The figure includes OPT, distributed gradient descent, CoCoA, and the proposed SVRGfo variants.
- Algorithm comparison: DANE and DiSCO diverge in this federated setting, so they are omitted from Figure 1.Their exclusion reflects instability on this experimental problem rather than a plotted performance value.
- Results: DSVRG reaches optimality in very few communication rounds, while CoCoA converges more slowly than distributed gradient descent.The experiments also report very little performance loss for DSVRG when data are randomly reshuffled between nodes, indicating robustness to non-IID data.
- Limitations and future work: The authors identify missing larger-scale and more challenging experiments, absent theoretical justification, and the need to incorporate differential privacy for on-device intelligence.They specifically mention deep learning as a more challenging problem and call for a new public dataset with naturally user-clustered data.