Optimal Algorithms for Non-Smooth Distributed Optimization in Networks

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

177 citations recorded by the source corpus.

In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptions: (1) the Lipschitz continuity of the global objective function, and (2) the Lipschitz continuity of local individual functions. Under the local regularity assumption, we provide the first optimal first-order decentralized algorithm called multi-step primal-dual (MSPD) and its corresponding optimal convergence rate. A notable aspect of this result is that, for non-smooth functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly-convex objective functions. Under the global regularity assumption, we provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function, and show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.

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): “For the deterministic (non-stochastic) descentralized optimization a recent line of work developed optimal algorithms based on acceleration (Jakoveti´c et al., 2014; Scaman et al., 2017; 2018; Uribe et al., 2018).”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “(Duchi et al., 2011; Scaman et al., 2018) proposed decentralized algorithms to solve the problem for time-invariant topology at a convergence rate of O(1/ √ k).”
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, background): “Similar results have been observed very recently for schemes with momentum (Yu et al., 2019) and previously also for decentralized optimization in the convex setting (Scaman et al., 2017, 2018; Koloskova et al., 2019).”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “, 2017), adaptive distributed SGD (Cutkosky & Busa-Fekete, 2018), Non-smooth distributed optimization (Scaman et al., 2018), distributed proximal primal-dual algorithm (Hong et al.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “For the case of deterministic (full-gradient) optimization, recent seminal theoretical advances show that the network topology only aﬀects higher-order terms of the convergence rate of decentralized optimization algorithms on convex problems (Scaman et al., 2017, 2018).”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “) The recent research shows a lower bound Ω ( � √ � ) in [29], which shows that the dynamic regret deined by Eq.”
COLA: Decentralized Linear Learning (2018, background): “P Additionally [Scaman et al., 2018] needs a boundedness constraint for the input problem.”
Asynchronous Decentralized Accelerated Stochastic Gradient Descent (2018, methodology): “, [36], [37] has utilized the same communication sliding scheme to develop communication-efficient decentralized algorithms.”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, background): “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].”
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, background): “Recently in [76], the authors extended the optimality lower bounds from [75] to the non-smooth case using the randomized regularization approach [21].”
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.”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, unknown): “A preliminary version of this work with only the analysis for the Lipschitz-continuous case (first line in Table 1) is available as a conference paper (Scaman et al., 2018).”
Lower Bounds and Optimal Algorithms for Personalized Federated Learning (2020, background): “1 is rahter standard in the literature of distributed optimization [44, 21]; it informally means that the iterates of A lie in the span of explored directions only.”
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, methodology): “1), such as, the accelerated primal-dual methods [26, 27], the alternating direction method of multipliers (ADMM) [28–32], and the distributed dual methods (mirror descent/dual averaging) [33–35].”
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks (2019, background): “…√ κ))) linear rate with √ κ dependence via a distributed algorithm is an open problem (unless additional assumptions are made such as explicit characterization of Fenchel dual of the local objective functions, referred to as dualable setting as in Scaman et al. (2018); Uribe et al. (2018)).”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “itectures, decentralized gradient descent (DGD) has been investigated in [45]. Beyond the gradient descent based approach, several communication-efﬁcient decentralized algorithms were proposed. [46], [47] proposed decentralized algorithms with the convergence rate O(1= p k). On the other hand, [48] ”