Harnessing Smoothness to Accelerate Distributed Optimization

Abstract

There has been a growing effort in studying the distributed optimization problem over a network. The objective is to optimize a global function formed by a sum of local functions, using only local computation and communication. Literature has developed consensus-based distributed (sub)gradient descent (DGD) methods and has shown that they have the same convergence rate $O(\frac{\log t}{\sqrt{t}})$ as the centralized (sub)gradient methods (CGD) when the function is convex but possibly nonsmooth. However, when the function is convex and smooth, under the framework of DGD, it is unclear how to harness the smoothness to obtain a faster convergence rate comparable to CGD's convergence rate. In this paper, we propose a distributed algorithm that, despite using the same amount of communication per iteration as DGD, can effectively harnesses the function smoothness and converge to the optimum with a rate of $O(\frac{1}{t})$. If the objective function is further strongly convex, our algorithm has a linear convergence rate. Both rates match the convergence rate of CGD. The key step in our algorithm is a novel gradient estimation scheme that uses history information to achieve fast and accurate estimation of the average gradient. To motivate the necessity of history information, we also show that it is impossible for a class of distributed algorithms like DGD to achieve a linear convergence rate without using history information even if the objective function is strongly convex and smooth.

30 pages, 4 figures

References in corpus (1)

• Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs

Cited by in corpus (39)

• Accelerated Distributed Nesterov Gradient Descent
• ADD-OPT: Accelerated Distributed Directed Optimization
• Optimal Distributed Feedback Voltage Control under Limited Reactive Power
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Optimization for Reinforcement Learning: From Single Agent to Cooperative Agents
• FROST -- Fast row-stochastic optimization with uncoordinated step-sizes
• Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
• On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
• AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs
• Distributed Nesterov gradient methods over arbitrary graphs
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Initialization-free Privacy-guaranteed Distributed Algorithm for Economic Dispatch Problem
• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• A unitary distributed subgradient method for multi-agent optimization with different coupling sources
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• A Linearly Convergent Algorithm for Distributed Principal Component Analysis
• Recent theoretical advances in decentralized distributed convex optimization
• A System Theoretical Perspective to Gradient-Tracking Algorithms for Distributed Quadratic Optimization
• Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function
• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization
• Accelerated Distributed Dual Averaging over Evolving Networks of Growing Connectivity
• FAST-PCA: A Fast and Exact Algorithm for Distributed Principal Component Analysis
• Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
• Privacy-Preserving Push-Pull Method for Decentralized Optimization via State Decomposition
• Distributed Online Private Learning of Convex Nondecomposable Objectives
• Implicit Tracking-Based Distributed Constraint-Coupled Optimization
• A Distributed Optimization Algorithm over Time-Varying Graphs with Efficient Gradient Evaluations
• Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
• Self-Healing First-Order Distributed Optimization
• On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps
• Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution
• DISH: A Distributed Hybrid Primal-Dual Optimization Framework to Utilize System Heterogeneity
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• NPGA: A Unified Algorithmic Framework for Decentralized Constraint-Coupled Optimization
• Fully First-Order Methods for Decentralized Bilevel Optimization
• A Distributed Methodology for Approximate Uniform Global Minimum Sharing