Are we there yet? Manifold identification of gradient-related proximal methods

Yifan Sun, Halyun Jeong, Julie Nutini, Mark Schmidt
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1110-1119, 2019.

Abstract

In machine learning, models that generalize better often generate outputs that lie on a low-dimensional manifold. Recently, several works have separately shown finite-time manifold identification by some proximal methods. In this work we provide a unified view by giving a simple condition under which any proximal method using a constant step size can achieve finite-iteration manifold detection. For several key methods (FISTA, DRS, ADMM, SVRG, SAGA, and RDA) we give an iteration bound, characterized in terms of their variable convergence rate and a problem-dependent constant that indicates problem degeneracy. For popular models, this constant is related to certain data assumptions, which gives intuition as to when lower active set complexity may be expected in practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-sun19a, title = {Are we there yet? Manifold identification of gradient-related proximal methods}, author = {Sun, Yifan and Jeong, Halyun and Nutini, Julie and Schmidt, Mark}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1110--1119}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/sun19a/sun19a.pdf}, url = {https://proceedings.mlr.press/v89/sun19a.html}, abstract = {In machine learning, models that generalize better often generate outputs that lie on a low-dimensional manifold. Recently, several works have separately shown finite-time manifold identification by some proximal methods. In this work we provide a unified view by giving a simple condition under which any proximal method using a constant step size can achieve finite-iteration manifold detection. For several key methods (FISTA, DRS, ADMM, SVRG, SAGA, and RDA) we give an iteration bound, characterized in terms of their variable convergence rate and a problem-dependent constant that indicates problem degeneracy. For popular models, this constant is related to certain data assumptions, which gives intuition as to when lower active set complexity may be expected in practice.} }
Endnote
%0 Conference Paper %T Are we there yet? Manifold identification of gradient-related proximal methods %A Yifan Sun %A Halyun Jeong %A Julie Nutini %A Mark Schmidt %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-sun19a %I PMLR %P 1110--1119 %U https://proceedings.mlr.press/v89/sun19a.html %V 89 %X In machine learning, models that generalize better often generate outputs that lie on a low-dimensional manifold. Recently, several works have separately shown finite-time manifold identification by some proximal methods. In this work we provide a unified view by giving a simple condition under which any proximal method using a constant step size can achieve finite-iteration manifold detection. For several key methods (FISTA, DRS, ADMM, SVRG, SAGA, and RDA) we give an iteration bound, characterized in terms of their variable convergence rate and a problem-dependent constant that indicates problem degeneracy. For popular models, this constant is related to certain data assumptions, which gives intuition as to when lower active set complexity may be expected in practice.
APA
Sun, Y., Jeong, H., Nutini, J. & Schmidt, M.. (2019). Are we there yet? Manifold identification of gradient-related proximal methods. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1110-1119 Available from https://proceedings.mlr.press/v89/sun19a.html.

Related Material