Convergence guarantees for a class of non-convex and non-smooth optimization problems
This work addresses optimization challenges in machine learning and statistics, offering theoretical guarantees and simplified algorithms for practitioners dealing with complex, non-smooth problems.
The paper tackles the problem of finding critical points for non-convex and non-smooth functions by analyzing gradient-based methods, establishing convergence rates and proving faster rates for continuous sub-analytic functions, with applications in areas like best subset selection and robust estimation.
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.