Are we there yet? Manifold identification of gradientrelated proximal methods
[edit]
Proceedings of Machine Learning Research, PMLR 89:11101119, 2019.
Abstract
In machine learning, models that generalize better often generate outputs that lie on a lowdimensional manifold. Recently, several works have separately shown finitetime 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 finiteiteration 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 problemdependent 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.
Related Material


