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

Yifan Sun(yifan.0.sungmail.com)
Halyun Jeong(hajeongmath.ubc.ca)
Julie Nutini(julie.nutinigmail.com)
Mark Schmidt(schmidtmcs.ubc.ca)

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.

Keywords: proximal methods; active set identification; manifold identification

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: AISTATS 2019

Download: [PDF]

Entry Submitted: 03/07/2019
Entry Accepted: 03/08/2019
Entry Last Modified: 03/07/2019

Modify/Update this entry