Decentralized machine learning is a promising emerging paradigm in view of global challenges of data ownership and privacy. We consider learning of linear classification and regression models, in the setting where the training data is decentralized over many user devices, and the learning algorithm must run ondevice, on an arbitrary communication network, without a central coordinator. We propose COLA, a new decentralized training algorithm with strong theoretical guarantees and superior practical performance. Our framework overcomes many limitations of existing methods, and achieves communication efficiency, scalability, elasticity as well as resilience to changes in data and allows for unreliable and heterogeneous participating devices. * These two authors contributed equally 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada. Contributions. In this paper, our main contribution is to propose COLA, a new decentralized framework for training generalized linear models with convergence guarantees. Our scheme resolves both described issues in existing approaches, using techniques from primal-dual optimization, and can be seen as a generalization of COCOA [Smith et al., 2018] to the decentralized setting. More specifically, the proposed algorithm offers -Convergence Guarantees: Linear and sublinear convergence rates are guaranteed for strongly convex and general convex objectives respectively. Our results are free of the restrictive assumptions made by stochastic methods , Wang et al., 2017 , which requires i.i.d. data distribution over all devices. -Communication Efficiency and Usability: Employing a data-local subproblem between each communication round, COLA not only achieves communication efficiency but also allows the re-use of existing efficient single-machine solvers for on-device learning. We provide practical decentralized primal-dual certificates to diagnose the learning progress. -Elasticity and Fault Tolerance: Unlike sum-structured approaches such as SGD, COLA is provably resilient to changes in the data, in the network topology, and participating devices disappearing, straggling or re-appearing in the network. Our implementation is publicly available under github.com/epfml/cola . + . More precisely, W ij ∈ [0, 1] denotes the connection strength between nodes i and j, with a non-zero weight indicating the existence of a pairwise communication link. We assume W to be symmetric and doubly stochastic, which means each row and column of W sums to one. The spectral properties of W used in this paper are that the eigenvalues of W are real, and 1 = λ 1 (W) ≥ · · · ≥ λ n (W) ≥ −1. Let the second largest magnitude of the eigenvalues of W be β := max{|λ 2 (W)|, |λ n (W)|}. 1 − β is called the spectral gap, a quantity well-studied in graph theory and network analysis. The spectral gap measures the level of connectivity among nodes. In the extreme case when W is diagonal, and thus an identity matrix, the spectral gap is 0 and there is no communication among nodes. To ensure convergence of decentralized algorithms, we impose
REF address the more specific problem class of generalized linear models.
COLA: Decentralized Linear Learning
NeurIPS
Computer Science Mathematics