## Run-and-Inspect Method for Nonconvex Optimization and Global Optimality Bounds for R-Local MinimizersYifan Chen, Yuejiao Sun, Wotao Yin Accepted by Mathematical Programming, Ser. B ## OverviewMany optimization algorithms provably converge to stationary points. When the underlying problem is nonconvex, those algorithms 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 local minimizers and stationary
points that are not globally optimal.
The inspection samples a set of points in a radius For high-dimensional nonconvex 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. ## Citation
« Back |