Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization

Abstract

In this work, we study two first-order primal-dual based algorithms, the Gradient Primal-Dual Algorithm (GPDA) and the Gradient Alternating Direction Method of Multipliers (GADMM), for solving a class of linearly constrained non-convex optimization problems. We show that with random initialization of the primal and dual variables, both algorithms are able to compute second-order stationary solutions (ss2) with probability one. This is the first result showing that primal-dual algorithm is capable of finding ss2 when only using first-order information, it also extends the existing results for first-order, but primal-only algorithms. An important implication of our result is that it also gives rise to the first global convergence result to the ss2, for two classes of unconstrained distributed non-convex learning problems over multi-agent networks.

References in corpus (9)

• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• Gradient Descent Converges to Minimizers
• First-order Methods Almost Always Avoid Saddle Points
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• A Generic Approach for Escaping Saddle points
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• NEXT: In-Network Nonconvex Optimization

Cited by in corpus (8)

• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Robust and Communication-Efficient Collaborative Learning
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications