Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
By Mingyi Hong, Jason D. Lee, Meisam Razaviyayn. 2018
34 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Aryan Mokhtari
- Hamed Hassani
- Zhihua Zhang
- Xiang Li
- Wenhao Yang
- Amirhossein Reisizadeh
- Ramtin Pedarsani
- Yuejie Chi
In Computational Mechanics
- Zhihua Zhang
- Xiang Li
- Wenhao Yang
- Haoran Sun
- Hamed Hassani
- Ramtin Pedarsani
- Amirhossein Reisizadeh
- Yuxin Chen
In Computer Networks and Communications
- Amirhossein Reisizadeh
- Hamed Hassani
- Ramtin Pedarsani
- Aryan Mokhtari
- Hossein Taheri
- Haoran Sun
- Yuejie Chi
- Yuxin Chen
Citations in the corpus
- Robust and Communication-Efficient Collaborative Learning (2019, background): “Recently, there have been some works which study non-convex decentralized consensus optimization and establish convergence to a stationary point (Zeng and Yin, 2018; Hong et al., 2017, 2018; Sun and Hong, 2018; Scutari et al., 2017; Scutari and Sun, 2018; Jiang et al., 2017; Lian et al., 2017a).”
- On the Convergence of FedAvg on Non-IID Data (2019, background): “The primal-dual algorithms (Hong et al., 2018; Smith et al., 2016; 2017) are more generally applicable and more relevant to FL.”
- Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, background): “Only recently, the authors of [24] developed first-order distributed algorithms that are capable of computing second-order stationary solutions (which under suitable conditions become local optimal solutions).”
- Communication-Efficient Local Decentralized SGD Methods (2019, methodology): “, one-shot aggregation [47, 48, 14, 19, 41], primal-dual algorithms [32, 33, 6] and distributed Newton methods [29, 46, 26, 30, 23].”
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “The above theory has been extended to accommodate other optimization methods like coordinate descent, mirror descent, and the gradient primal-dual algorithm [159, 160].”