On Nonconvex Decentralized Gradient Descent

By Jinshan Zeng, Wotao Yin. 2016

225 citations recorded by the source corpus.

Consensus optimization has received considerable attention in recent years. A number of decentralized algorithms have been proposed for convex consensus optimization. However, to the behaviors or consensus <italic>nonconvex</italic> optimization, our understanding is more limited. When we lose convexity, we cannot hope that our algorithms always return global solutions though they sometimes still do. Somewhat surprisingly, the decentralized consensus algorithms, DGD and Prox-DGD, retain most other properties that are known in the convex setting. In particular, when diminishing (or constant) step sizes are used, we can prove convergence to a (or a neighborhood of) consensus stationary solution under some regular assumptions. It is worth noting that Prox-DGD can handle nonconvex nonsmooth functions if their proximal operators can be computed. Such functions include SCAD, MCP, and <inline-formula><tex-math notation="LaTeX"> $\ell _q$</tex-math></inline-formula> quasi-norms, <inline-formula><tex-math notation="LaTeX">$q\in [0,1)$</tex-math> </inline-formula>. Similarly, Prox-DGD can take the constraint to a nonconvex set with an easy projection. To establish these properties, we have to introduce a completely different line of analysis, as well as modify existing proofs that were used in the convex setting.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Optimization & Training

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

In Computational Mechanics

In Computer Networks and Communications

In Optimization & Training

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).”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “:[ n ] , edges: E ), and is a doubly stochastic matrix [Wu et al., 2018, Zeng and Yin, 2018, Yuan et al., 2016], but may be not symmetric.”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, methodology): “Decentralized averaging has a long history in the distributed and consensus optimization community (Tsitsik-lis et al., 1986; Nedic & Ozdaglar, 2009; Duchi et al., 2012; Tsianos et al., 2012; Zeng & Yin, 2016; Yuan et al., 2016; Sirb & Ye, 2018).”
Collaborative Deep Learning in Fixed Topology Networks (2017, methodology): “Our proof techniques are different from those in [20, 21] with the choice of Lyapunov function, as well as the notion of stochastic Lyapunov gradient.”
Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks (2018, background): “In their followup work [17], the convergence behavior of DGD was further analyzed for non-convex problems.”
Decentralized Federated Averaging (2021, background): “In DGD, the convexity assumption is unnecessary [30], which makes DGD useful for nonconvex optimization.”
Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, methodology): “The work [25] summarizes a number of recent progress in extending the DSG-based methods for non-convex problems.”
A survey of distributed optimization (2019, unknown): “…and machine learning (see, e.g., Chatzipanagiotis & Za-vlanos, 2017; Hong, Hajinezhad, & Zhao, 2017; Lorenzo & Scu-tari, 2016; Matei & Baras, 2017; Tatarenko & Touri, 2017; Tian, Sun, Du, & Scutari, 2018; Wai, Lafond, Scaglione, & Moulines, 2017; Zeng & Yin, 2018; Zhu & Martínez, 2013 ).”