Second-order Guarantees of Gradient Algorithms over Networks

We consider distributed smooth nonconvex unconstrained optimization over networks, modeled as a connected graph. We examine the behavior of distributed gradient-based algorithms near strict saddle points. Specifically, we establish that (i) the renowned Distributed Gradient Descent (DGD) algorithm likely converges to a neighborhood of a Second-order Stationary (SoS) solution; and (ii) the more recent class of distributed algorithms, based on gradient tracking (termed SONATA), likely converges to exact SoS solutions, thus avoiding (strict) saddle points.

• Publication year

  2018

• Venue

  Allerton Conference on Communication, Control, and Computing

• Publication date

  2018-10-01

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1109/ALLERTON.2018.8636044
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• First-order methods almost always avoid saddle points: The case of vanishing step-sizes

  2019cited by this paper
• Distributed nonconvex constrained optimization over time-varying digraphs

  2018cited by this paper
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization

  2018influential reference
• Second-order Guarantees of Distributed Gradient Algorithms

  2018cited by this paper
• Parallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization

  2018cited by this paper
• Behavior of accelerated gradient methods near critical points of nonconvex functions

  2017cited by this paper
• Behavior of Accelerated Gradient Methods Near Critical Points of Nonconvex Problems

  2017cited by this paper
• How to Escape Saddle Points Efficiently

  2017cited by this paper
• Distributed nonconvex multiagent optimization over time-varying networks

  2016cited by this paper
• On Nonconvex Decentralized Gradient Descent

  2016influential reference
• Gradient Descent Only Converges to Minimizers

  2016cited by this paper
• NEXT: In-Network Nonconvex Optimization

  2016cited by this paper
• Matrix Completion has No Spurious Local Minimum

  2016cited by this paper
• Deep Learning without Poor Local Minima

  2016cited by this paper
• Distributed nonconvex optimization over networks

  2015cited by this paper
• Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition

  2015cited by this paper
• Non-Convex Distributed Optimization

  2015cited by this paper
• Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes

  2015cited by this paper
• An Extrinsic Look at the Riemannian Hessian

  2013cited by this paper
• Distributed Subgradient Methods for Multi-Agent Optimization

  2009cited by this paper
• Optimization algorithms on matrix manifolds

  2009cited by this paper
• Constrained Consensus and Optimization in Multi-Agent Networks

  2008cited by this paper
• On gradients of functions definable in o-minimal structures

  1998cited by this paper
• Nonconvergence to Unstable Points in Urn Models and Stochastic Approximations

  1990cited by this paper
• Global Stability of Dynamical Systems

  1986cited by this paper

• A Communication-Efficient Stochastic Gradient Descent Algorithm for Distributed Nonconvex Optimization

  2024cites this paper
• Distributed Data Minimization for Decentralized Collaborative Filtering Systems

  2023cites this paper
• Communication Compression for Distributed Nonconvex Optimization

  2022cites this paper
• Communication Compression for Decentralized Nonconvex Optimization

  2022cites this paper
• Second-Order Optimality in Non-Convex Decentralized Optimization via Perturbed Gradient Tracking

  2020cites this paper
• Distributed Gradient Flow: Nonsmoothness, Nonconvexity, and Saddle Point Evasion

  2020cites this paper
• Distributed Learning in the Non-Convex World: From Batch to Streaming Data, and Beyond

  2020cites this paper
• Distributed Stochastic Gradient Descent and Convergence to Local Minima

  2020cites this paper
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima

  2020cites this paper
• Linear Convergence of First- and Zeroth-Order Primal–Dual Algorithms for Distributed Nonconvex Optimization

  2019influential citation
• Distributed Global Optimization by Annealing

  2019cites this paper
• Machine Learning Algorithms

  2018cites this paper
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms

  2018influential citation