A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks

By César A. Uribe, Soomin Lee, Alexander V. Gasnikov, Angelia Nedić. 2018

149 citations recorded by the source corpus.

We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum $\sum\nolimits_{i = 1}^m {{f_i}\left( z \right)} $ of functions over in a network. We provide complexity bounds for four different cases, namely: each function fi is strongly convex and smooth, each function is either strongly convex or smooth, and when it is convex but neither strongly convex nor smooth. Our approach is based on the dual of an appropriately formulated primal problem, which includes a graph that models the communication restrictions. We propose distributed algorithms that achieve the same optimal rates as their centralized counterparts (up to constant and logarithmic factors), with an additional optimal cost related to the spectral properties of the network. Initially, we focus on functions for which we can explicitly minimize its Legendre–Fenchel conjugate, i.e., admissible or dual friendly functions. Then, we study distributed optimization algorithms for non-dual friendly functions, as well as a method to improve the dependency on the parameters of the functions involved. Numerical analysis of the proposed algorithms is also provided.

How researchers see this paper

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

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ć et al., 2014; Scaman et al., 2017; 2018; Uribe et al., 2018; Fallah et al., 2019).”
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 Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “For the deterministic (non-stochastic) convex version of (1) 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).”
Push–Pull Gradient Methods for Distributed Optimization in Networks (2018, background): “More recently, for a class of so-termed dual friendly functions, the research works in [6] and [24] have obtained an optimal decentralized consensus optimization algorithm whose dependence on the condition number1 of the system’s objective function achieves the best known scaling in the order of O( ”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, unknown): “Mokhtari and Ribeiro, 2016) to more recent improvements (Qu and Li, 2016; Jiang et al., 2017; He et al., 2018; Pu et al., 2018; Uribe et al., 2018; Koloskova et al., 2019; Xin et al., 2019; Jakovetić, 2019).”
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks (2019, background): “To our best knowledge, achieving the non-distributed O(exp(−k/Θ( √ κ))) 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 s”
Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters (2018, background): “On the other hand, recent studies [34, 40, 37, 46, 31] on accelerated distributed convex optimization algorithms demonstrated their efficiency for convex optimization problems over arbitrary networks with inherently distributed data, i.”