Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

Abstract

The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. It arises in various application domains, including distributed tracking and localization, multi-agent co-ordination, estimation in sensor networks, and large-scale optimization in machine learning. We develop and analyze distributed algorithms based on dual averaging of subgradients, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our method of analysis allows for a clear separation between the convergence of the optimization algorithm itself and the effects of communication constraints arising from the network structure. In particular, we show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network. The sharpness of this prediction is confirmed both by theoretical lower bounds and simulations for various networks. Our approach includes both the cases of deterministic optimization and communication, as well as problems with stochastic optimization and/or communication.

40 pages, 4 figures

Cited by in corpus (55)

• Speeding Up Distributed Machine Learning Using Codes
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Harnessing Smoothness to Accelerate Distributed Optimization
• Distributed Random Projection Algorithm for Convex Optimization
• Accelerated Distributed Nesterov Gradient Descent
• Distributed Maximum Likelihood Sensor Network Localization
• Online Distributed Optimization on Dynamic Networks
• An Exact Quantized Decentralized Gradient Descent Algorithm
• Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
• Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems
• ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning
• Distributed Algorithms for Computation of Centrality Measures in Complex Networks
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Privacy-preserving Distributed Machine Learning via Local Randomization and ADMM Perturbation
• A Distributed Nash Equilibrium Seeking in Networked Graphical Games
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• Quantized Consensus ADMM for Multi-Agent Distributed Optimization
• Hop: Heterogeneity-Aware Decentralized Training
• A unitary distributed subgradient method for multi-agent optimization with different coupling sources
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Dynamic Power Distribution System Management With a Locally Connected Communication Network
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• FedHybrid: A Hybrid Primal-Dual Algorithm Framework for Federated Optimization
• Coordinate Dual Averaging for Decentralized Online Optimization with Nonseparable Global Objectives
• Dynamic and Distributed Online Convex Optimization for Demand Response of Commercial Buildings
• Continuous-time Discounted Mirror-Descent Dynamics in Monotone Concave Games
• Distributed Gradient Methods with Variable Number of Working Nodes
• Corrigendum to "Balance of Communication and Convergence: Predefined-time Distributed Optimization Based on Zero-Gradient-Sum"
• Toward Resource-Optimal Consensus over the Wireless Medium
• Accelerated Distributed Dual Averaging over Evolving Networks of Growing Connectivity
• Learning, Computing, and Trustworthiness in Intelligent IoT Environments: Performance-Energy Tradeoffs
• Private Weighted Random Walk Stochastic Gradient Descent
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• Privacy-Preserving Distributed Learning for Residential Short-Term Load Forecasting
• Distributed Online Private Learning of Convex Nondecomposable Objectives
• (Corrected Version) Push-LSVRG-UP: Distributed Stochastic Optimization over Unbalanced Directed Networks with Uncoordinated Triggered Probabilities
• Distributed Adaptive Gradient Algorithm with Gradient Tracking for Stochastic Non-Convex Optimization
• Stochastic Optimization from Distributed, Streaming Data in Rate-limited Networks
• Delay-Tolerant Constrained OCO with Application to Network Resource Allocation
• Asynchronous Distributed Learning from Constraints
• Distributed Safe Control Design and Probabilistic Safety Verification for Multi-Agent Systems
• Efficient Distributed Estimation of Inverse Covariance Matrices
• Extensions of Fast-Lipschitz Optimization
• Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
• On stochastic mirror descent with interacting particles: convergence properties and variance reduction
• Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
• Automatic Performance Estimation for Decentralized Optimization
• Scalable Distributed Optimization of Multi-Dimensional Functions Despite Byzantine Adversaries
• Randomized Block Proximal Methods for Distributed Stochastic Big-Data Optimization
• On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps
• Asynchronous Message-Passing and Zeroth-Order Optimization Based Distributed Learning with a Use-Case in Resource Allocation in Communication Networks
• The Minimizer of the Sum of Two Strongly Convex Functions
• A Communication-efficient Local Differentially Private Algorithm in Federated Optimization
• Anytime Minibatch with Delayed Gradients