Convergence guarantees for a class of nonconvex and nonsmooth optimization problems
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:26012610, 2018.
Abstract
Nonconvex optimization problems arise frequently in machine learning, including feature selection, structured matrix learning, mixture modeling, and neural network training. We consider the problem of finding critical points of a broad class of nonconvex problems with nonsmooth components. We analyze the behavior of two gradientbased methods—namely a subgradient method, and a proximal method. Our main results are to establish rates of convergence for general problems, and also exhibit faster rates for subanalytic functions. As an application of our theory, we obtain a simplification of the popular CCCP algorithm, which retains all the desirable convergence properties of the original method, along with a significantly lower cost per iteration. We illustrate our methods and theory via application to the problems of best subset selection, robust estimation, and shape from shading reconstruction.
Related Material


