Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems

Abstract

While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual approach, this paper presents a new (stochastic) distributed algorithm with Nesterov momentum for accelerated optimization of non-convex and non-smooth problems. Theoretically, we show that the proposed algorithm can achieve an $\epsilon$-stationary solution under a constant step size with $\mathcal{O}(1/{\epsilon }^2)$ computation complexity and $\mathcal{O}(1/\epsilon )$ communication complexity. When compared to the existing gradient tracking based methods, the proposed algorithm has the same order of computation complexity but lower order of communication complexity. To the best of our knowledge, the presented result is the first stochastic algorithm with the $\mathcal{O}(1/\epsilon )$ communication complexity for non-convex and non-smooth problems. Numerical experiments for a distributed non-convex regression problem and a deep neural network based classification problem are presented to illustrate the effectiveness of the proposed algorithms.

References in corpus (15)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Mobile Edge Computing: A Survey on Architecture and Computation Offloading
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Federated Optimization in Heterogeneous Networks
• D${}^2$: Decentralized Training over Decentralized Data
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• Learning with Non-Convex Truncated Losses by SGD
• A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• Scheduled Restart Momentum for Accelerated Stochastic Gradient Descent

Cited by in corpus (3)

• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency