Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks

By Kevin Scaman, Francis R. Bach, Sébastien Bubeck, Yin Tat Lee, Laurent Massoulié. 2017

372 citations recorded by the source corpus.

In this paper, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized and decentralized communications over a network. For centralized (i.e. master/slave) algorithms, we show that distributing Nesterov's accelerated gradient descent is optimal and achieves a precision e > 0 in time O(√kg(1 + Δτ) ln(l/e)), where kg is the condition number of the (global) function to optimize, Δ is the diameter of the network, and τ (resp. l) is the time needed to communicate values between two neighbors (resp. perform local computations). For decentralized algorithms based on gossip, we provide the first optimal algorithm, called the multi-step dual accelerated (MSDA) method, that achieves a precision e e 0 in time O(√kl(1 + τ/√γ)ln(1/e)), where kl is the condition number of the local functions and γ is the (normalized) eigengap of the gossip matrix used for communication between nodes. We then verify the efficiency of MSDA against state-of-the-art methods for two problems: least-squares regression and classification by logistic regression.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Optimization & Training, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “This term could potentially be improved to 1 / 2 with acceleration techniques, such as in (Scaman et al., 2017).”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “, 2012), and several dual based strategies (Seaman et al., 2017; Scaman et al., 2018; Uribe et al., 2018).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, neutral): “Similar results have been observed very recently for related schemes (Scaman et al., 2017; 2018; Koloskova et al., 2019; Yu et al., 2019).”
Distributed Learning over Unreliable Networks (2018, methodology): “5 of the Microsoft Cognitive Toolkit Seide and Agarwal [2016]. We implement the RPS algorithm using MPI.”
COLA: Decentralized Linear Learning (2018, background): “Specifically, [Scaman et al., 2017] assumes each Fi(x) is smooth and strongly convex, and [Scaman et al.”
Collaborative Deep Learning in Fixed Topology Networks (2017, methodology): “Moreover, a decentralized algorithm based on gossip protocol called the multi-step dual accelerated (MSDA) [17] was developed for solving deterministically smooth and strongly convex distributed optimization problems in networks with a provable optimal linear convergence rate.”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, methodology): “Method Convergence Rate Per-iteration Cost Communication Cost EXTRA (Shi et al., 2015a) O((κ2 + κg) log 1ǫ ) O(ρqd +∆(G)d) O(∆(G)d) DLM (Ling et al., 2015) O((κ2 + κgκ) log 1ǫ ) O(ρqd +∆(G)d) O(∆(G)d) SSDA (Scaman et al., 2017) O(√κκg log 1ǫ ) O(ρqd+ qτ +∆(G)d) O(∆(G)d) DSA (Mokhtari & Ribeiro, 2016”
Distributed Proximal Splitting Algorithms with Rates and Acceleration (2020, background): “If K is a gossip matrix like the minus graph Laplacian, decentralized optimization over a network can be tackled [29,30].”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, methodology): “By using Nesterov’s acceleration technique, reference [4] shows that the scalability of a new average consensus protocol can be improved to O(n); when the nonsmooth terms ri’s are absent, reference [53] shows that the scalability of a new dual based accelerated distributed gradient method can be imp”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, neutral): “In order to ensure the efficiency of this communication scheme, we impose standard assumptions on the matrix W ∈ Rn×n, called the gossip matrix (Boyd et al., 2006; Scaman et al., 2017):”
Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, background): “On the other hand, “multi-step” methods that alternate multiple communication rounds per local gradient computation, such as the ones considered in [37, 51, 42, 43], display a runtime that scales with a factor of the form m+ τ+Deg(P ) 1−σ2 in our setting.”
Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters (2018, background): “Moreover, accelerated gradient methods have natural extensions for the decentralized distributed setting [40, 45, 28].”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, methodology): “First, a more connected topology leads to faster convergence in terms of iterations or communication rounds, as quantified by classic worst-case convergence bounds in terms of the spectral properties of the topology [75, 24, 89, 90, 103, 40].”
Push–Pull Gradient Methods for Distributed Optimization in Networks (2018, background): “More recently, for a class of so-termed dual friendly functions, papers [6], [24] have obtained an optimal decentralized consensus optimization algorithm whose dependency on the condition number1 of the system’s objective function achieves the best known scaling in the order of”
Accelerated Distributed Nesterov Gradient Descent (2017, background): “3If dual-gradients are available, the dependence on μ can be better [8].”
The Role of Network Topology for Distributed Machine Learning (2019, methodology): “Our analysis can be easily adapted to extend the results in [6], [7] to take into account the variability of the computation and communication times.”