Second-order guarantees of distributed gradient algorithms
From MaRDI portal
Abstract: 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--implementable also over digraphs--likely converges to exact SoS solutions, thus avoiding (strict) saddle-points. Furthermore, new convergence rate results to first-order critical points is established for the latter class of algorithms.
Recommendations
- Second-order guarantees in centralized, federated and decentralized nonconvex optimization
- Event and Its Application in Algebraic Structures
- Distributed nonconvex constrained optimization over time-varying digraphs
- Distributed coordination for nonsmooth convex optimization via saddle-point dynamics
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Cites work
- A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization
- Accelerated methods for nonconvex optimization
- Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
- An Approximate Dual Subgradient Algorithm for Multi-Agent Non-Convex Optimization
- An Extrinsic Look at the Riemannian Hessian
- Behavior of accelerated gradient methods near critical points of nonconvex functions
- Computing a Trust Region Step
- Constrained Consensus and Optimization in Multi-Agent Networks
- Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Cubic regularization of Newton method and its global performance
- Distributed nonconvex constrained optimization over time-varying digraphs
- Distributed Optimization Over Time-Varying Directed Graphs
- Distributed Subgradient Methods for Multi-Agent Optimization
- Finding approximate local minima faster than gradient descent
- First-order methods almost always avoid strict saddle points
- Gradient descent finds the cubic-regularized nonconvex Newton step
- Harnessing Smoothness to Accelerate Distributed Optimization
- scientific article; zbMATH DE number 1817650 (Why is no real title available?)
- scientific article; zbMATH DE number 3980052 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Non-Convex Distributed Optimization
- Nonconvergence to unstable points in urn models and stochastic approximations
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- On gradients of functions definable in o-minimal structures
- On Nonconvex Decentralized Gradient Descent
- On the convergence of decentralized gradient descent
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
- On the global convergence of trust region algorithms for unconstrained minimization
- Parallel and distributed successive convex approximation methods for big-data optimization
- Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Recursive Stochastic Algorithms for Global Optimization in $\mathbb{R}^d $
Cited in
(8)- Second-order guarantees in centralized, federated and decentralized nonconvex optimization
- Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization
- Second-Order Guarantees of Stochastic Gradient Descent in Nonconvex Optimization
- Decentralized nonconvex optimization with guaranteed privacy and accuracy
- Graph Topology Invariant Gradient and Sampling Complexity for Decentralized and Stochastic Optimization
- Distributed constrained optimization algorithms with linear convergence rate over time-varying unbalanced graphs
- A decentralized proximal gradient tracking algorithm for composite optimization on Riemannian manifolds
- Escaping saddle points in distributed nonconvex optimization via cubic regularization
This page was built for publication: Second-order guarantees of distributed gradient algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5131964)
