Convergence guarantees for a class of non-convex and non-smooth optimization problems
From MaRDI portal
(Redirected from Publication:5214248)
Abstract: We consider the problem of finding critical points of functions that are non-convex and non-smooth. Studying a fairly broad class of such problems, we analyze the behavior of three gradient-based methods (gradient descent, proximal update, and Frank-Wolfe update). For each of these methods, we establish rates of convergence for general problems, and also prove faster rates for continuous sub-analytic functions. We also show that our algorithms can escape strict saddle points for a class of non-smooth functions, thereby generalizing known results for smooth functions. Our analysis leads to a simplification of the popular CCCP algorithm, used for optimizing functions that can be written as a difference of two convex functions. Our simplified algorithm retains all the convergence properties of CCCP, along with a significantly lower cost per iteration. We illustrate our methods and theory via applications to the problems of best subset selection, robust estimation, mixture density estimation, and shape-from-shading reconstruction.
Recommendations
- Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
- Convergence analysis of a proximal point algorithm for minimizing differences of functions
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- On the convergence of a linesearch based proximal-gradient method for nonconvex optimization
- Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
Cites work
- A complete characterization of the gap between convexity and sos-convexity
- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- A proximal difference-of-convex algorithm with extrapolation
- Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
- Convergence analysis of a proximal point algorithm for minimizing differences of functions
- Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
- Convex optimization: algorithms and complexity
- Cubic regularization of Newton method and its global performance
- DC formulations and algorithms for sparse optimization problems
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Gradient descent only converges to minimizers: non-isolated critical points and invariant regions
- High-dimensional statistics. A non-asymptotic viewpoint
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 757676 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- Introduction to global optimization.
- Lower bounds for finding stationary points I
- NP-hardness of deciding convexity of quartic polynomials and related problems
- On functions representable as a difference of convex functions
- On gradients of functions definable in o-minimal structures
- On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
- 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
- The Concave-Convex Procedure
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
- Variations and extension of the convex-concave procedure
Cited in
(17)- Data clustering based on the modified relaxation Cheeger cut model
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- Behavior of accelerated gradient methods near critical points of nonconvex functions
- Convergence of a non-interior smoothing method for variational inequality problems
- Relaxing Kink Qualifications and Proving Convergence Rates in Piecewise Smooth Optimization
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- Non-convex optimization via strongly convex majorization-minimization
- On the Convergence of an Optimization Algorithm Based on Nonlinear Operators
- On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods
- Sharp global convergence guarantees for iterative nonconvex optimization with random data
- Stochastic approximation with discontinuous dynamics, differential inclusions, and applications
- scientific article; zbMATH DE number 7705675 (Why is no real title available?)
- Convergence of a Class of Nonmonotone Descent Methods for Kurdyka–Łojasiewicz Optimization Problems
- A boosted DC algorithm for non-differentiable DC components with non-monotone line search
- A generalized formulation for group selection via ADMM
- A unified Bregman alternating minimization algorithm for generalized DC programs with application to imaging
- An inexact boosted difference of convex algorithm for nondifferentiable functions
This page was built for publication: Convergence guarantees for a class of non-convex and non-smooth optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5214248)
