On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
From MaRDI portal
Publication:6158001
Abstract: In this work, we analyze the global convergence property of coordinate gradient descent with random choice of coordinates and stepsizes for non-convex optimization problems. Under generic assumptions, we prove that the algorithm iterate will almost surely escape strict saddle points of the objective function. As a result, the algorithm is guaranteed to converge to local minima if all saddle points are strict. Our proof is based on viewing coordinate descent algorithm as a nonlinear random dynamical system and a quantitative finite block analysis of its linearization around saddle points.
Recommendations
- Random Coordinate Descent Methods for <inline-formula> <tex-math notation="TeX">$\ell_{0}$</tex-math></inline-formula> Regularized Convex Optimization
- Linear Convergence of Random Dual Coordinate Descent on Nonpolyhedral Convex Problems
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- On the convergence of the coordinate descent method for convex differentiable minimization
- Sharp global convergence guarantees for iterative nonconvex optimization with random data
- Random Coordinate Descent Methods for Nonseparable Composite Optimization
- A coordinate gradient descent method for nonsmooth nonseparable minimization
- On Global Linear Convergence in Stochastic Nonconvex Optimization for Semidefinite Programming
- Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems
- Convergence rates for the stochastic gradient descent method for non-convex objective functions
Cites work
- A coordinate gradient descent method for nonsmooth separable minimization
- A Dynamical Proof of the Multiplicative Ergodic Theorem
- A geometric analysis of phase retrieval
- A proof of Oseledec's multiplicative ergodic theorem
- A Siegel theorem for dynamical systems under random perturbations
- A stochastic version of center manifold theory
- Accelerated block-coordinate relaxation for regularized optimization
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Analyzing random permutations for cyclic coordinate descent
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Behavior of accelerated gradient methods near critical points of nonconvex functions
- Characteristic exponents and invariant manifolds in Hilbert space
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Coordinate descent algorithms
- Coordinatewise descent methods for leading eigenvalue problem
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Ergodic theory of differentiable dynamical systems
- First-order methods almost always avoid strict saddle points
- scientific article; zbMATH DE number 3980052 (Why is no real title available?)
- scientific article; zbMATH DE number 1201579 (Why is no real title available?)
- scientific article; zbMATH DE number 744037 (Why is no real title available?)
- scientific article; zbMATH DE number 3375319 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Lyapunov exponents and invariant manifolds for random dynamical systems in a Banach space
- Normally hyperbolic invariant manifolds for random dynamical systems. I: Persistence
- On Nonconvex Optimization for Machine Learning
- On the convergence of block coordinate descent type methods
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- Parallel coordinate descent methods for big data optimization
- Poincaré theorems for random dynamical systems
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Random permutations fix a worst case for cyclic coordinate descent
- Random reordering in SOR-type methods
- Randomness and permutations in coordinate descent methods
- Smooth center manifolds for random dynamical systems
- Stability of Lyapunov exponents
- Sternberg theorems for random dynamical systems
- Stochastic stability of Lyapunov exponents and Oseledets splittings for semi-invertible matrix cocycles
- Takens theorem for random dynamical systems
Cited in
(20)- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- Random gradient-free minimization of convex functions
- Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
- First-order methods almost always avoid strict saddle points
- Behavior of accelerated gradient methods near critical points of nonconvex functions
- Global convergence analysis of sparse regular nonconvex optimization problems
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- Dual randomized coordinate descent method for solving a class of nonconvex problems
- Analysis of asymptotic escape of strict saddle sets in manifold optimization
- Global rates of convergence for nonconvex optimization on manifolds
- Convergence guarantees for a class of non-convex and non-smooth optimization problems
- Uniform rank gradient, cost, and local-global convergence
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- scientific article; zbMATH DE number 5051694 (Why is no real title available?)
- Sharp global convergence guarantees for iterative nonconvex optimization with random data
- Switched diffusion processes for non-convex optimization and saddle points search
- Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds
- On convergence of a \(q\)-random coordinate constrained algorithm for non-convex problems
- Convergence error analysis of reflected gradient Langevin dynamics for non-convex constrained optimization
- Smoothing proximal gradient block-coordinate algorithms for group sparse _0 regularized nonsmooth convex regression problem
This page was built for publication: On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6158001)
