Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms

Abstract

We consider a class of popular distributed non-convex optimization problems, in which agents connected by a network $\mathcal{G}$ collectively optimize a sum of smooth (possibly non-convex) local objective functions. We address the following question: if the agents can only access the gradients of local functions, what are the fastest rates that any distributed algorithms can achieve, and how to achieve those rates. First, we show that there exist difficult problem instances, such that it takes a class of distributed first-order methods at least $\mathcal{O}(1/\sqrt{\xi (\mathcal{G})}\times \bar{L}/\epsilon )$ communication rounds to achieve certain $\epsilon$-solution [where $\xi (\mathcal{G})$ denotes the spectral gap of the graph Laplacian matrix, and $\bar{L}$ is some Lipschitz constant]. Second, we propose (near) optimal methods whose rates match the developed lower rate bound (up to a polylog factor). The key in the algorithm design is to properly embed the classical polynomial filtering techniques into modern first-order algorithms. To the best of our knowledge, this is the first time that lower rate bounds and optimal methods have been developed for distributed non-convex optimization problems.

arXiv commentAccepted by TSP

References in corpus (13)

• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Optimal Algorithms for Distributed Optimization
• Chebyshev and Conjugate Gradient Filters for Graph Image Denoising
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization
• A Distributed Second-Order Algorithm You Can Trust
• Newton-ADMM: A Distributed GPU-Accelerated Optimizer for Multiclass Classification Problems

Cited by in corpus (24)

• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Consensus Control for Decentralized Deep Learning
• Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
• Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
• The Barzilai-Borwein Method for Distributed Optimization over Unbalanced Directed Networks
• Robust and Communication-Efficient Collaborative Learning
• A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization
• Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent
• Linear Convergence of First- and Zeroth-Order Primal-Dual Algorithms for Distributed Nonconvex Optimization
• Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution
• GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning
• Optimal Complexity in Decentralized Training
• A general framework for decentralized optimization with first-order methods
• Distributed proximal gradient algorithm for non-smooth non-convex optimization over time-varying networks
• On the Convergence of NEAR-DGD for Nonconvex Optimization with Second Order Guarantees
• Decentralized Learning with Lazy and Approximate Dual Gradients