Run-and-inspect method for nonconvex optimization and global optimality bounds for R-local minimizers
From MaRDI portal
Publication:2425163
DOI10.1007/S10107-019-01397-WzbMATH Open1415.90085arXiv1711.08172OpenAlexW2963085159WikidataQ127963668 ScholiaQ127963668MaRDI QIDQ2425163FDOQ2425163
Wotao Yin, Yuejiao Sun, Yifan Chen
Publication date: 26 June 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers and occasionally stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an "inspect" phase to existing algorithms that helps escape from non-global stationary points. The inspection samples a set of points in a radius around the current point. When a sample point yields a sufficient decrease in the objective, we move there and resume an existing algorithm. If no sufficient decrease is found, the current point is called an approximate -local minimizer. We show that an -local minimizer is globally optimal, up to a specific error depending on , if the objective function can be implicitly decomposed into a smooth convex function plus a restricted function that is possibly nonconvex, nonsmooth. For high-dimensional problems, we introduce blockwise inspections to overcome the curse of dimensionality while still maintaining optimality bounds up to a factor equal to the number of blocks. Our method performs well on a set of artificial and realistic nonconvex problems by coupling with gradient descent, coordinate descent, EM, and prox-linear algorithms.
Full work available at URL: https://arxiv.org/abs/1711.08172
Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)
Cites Work
- Title not available (Why is that?)
- Nearly unbiased variable selection under minimax concave penalty
- Optimization by Simulated Annealing
- A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
- Trust Region Methods
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Introduction to Derivative-Free Optimization
- Nonconvex Sparse Logistic Regression With Weakly Convex Regularization
- Cubic regularization of Newton method and its global performance
- Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization
- Coordinate-friendly structures, algorithms and applications
- GAITA: a Gauss-Seidel iterative thresholding algorithm for \(\ell_q\) regularized least squares regression
- Global convergence of ADMM in nonconvex nonsmooth optimization
- Deep relaxation: partial differential equations for optimizing deep neural networks
- Entropy-SGD: biasing gradient descent into wide valleys
- Stochastic backward Euler: an implicit gradient descent algorithm for \(k\)-means clustering
- Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
Uses Software
Recommendations
- On a local and global search involved in nonconvex optimization problems 👍 👎
- Local minima of nonconvex problems 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- On duality bound methods for nonconvex global optimization 👍 👎
- On a class of nonconvex problems where all local minima are global 👍 👎
- Local convexification of the Lagrangian function for nonlinear nonconvex optimization 👍 👎
- From global to local convergence of interior methods for nonlinear optimization 👍 👎
- Approximate global minimization of nonconvex functions that are close to convex 👍 👎
This page was built for publication: Run-and-inspect method for nonconvex optimization and global optimality bounds for R-local minimizers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425163)
