Convergence guarantees for a class of non-convex and non-smooth optimization problems

Koulik Khamaru, Martin Wainwright
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2601-2610, 2018.

Abstract

Non-convex 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 non-convex problems with non-smooth components. We analyze the behavior of two gradient-based methods—namely a sub-gradient method, and a proximal method. Our main results are to establish rates of convergence for general problems, and also exhibit faster rates for sub-analytic 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-khamaru18a, title = {Convergence guarantees for a class of non-convex and non-smooth optimization problems}, author = {Khamaru, Koulik and Wainwright, Martin}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2601--2610}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/khamaru18a/khamaru18a.pdf}, url = {https://proceedings.mlr.press/v80/khamaru18a.html}, abstract = {Non-convex 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 non-convex problems with non-smooth components. We analyze the behavior of two gradient-based methods—namely a sub-gradient method, and a proximal method. Our main results are to establish rates of convergence for general problems, and also exhibit faster rates for sub-analytic 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.} }
Endnote
%0 Conference Paper %T Convergence guarantees for a class of non-convex and non-smooth optimization problems %A Koulik Khamaru %A Martin Wainwright %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-khamaru18a %I PMLR %P 2601--2610 %U https://proceedings.mlr.press/v80/khamaru18a.html %V 80 %X Non-convex 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 non-convex problems with non-smooth components. We analyze the behavior of two gradient-based methods—namely a sub-gradient method, and a proximal method. Our main results are to establish rates of convergence for general problems, and also exhibit faster rates for sub-analytic 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.
APA
Khamaru, K. & Wainwright, M.. (2018). Convergence guarantees for a class of non-convex and non-smooth optimization problems. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2601-2610 Available from https://proceedings.mlr.press/v80/khamaru18a.html.

Related Material