Journal article
RSG: Beating Subgradient Method without Smoothness and Strong Convexity
Journal of machine learning research, Vol.19, pp.1-33
01/01/2018
Abstract
In this paper, we study the efficiency of a Restarted SubGradient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an is an element of -optimal solution with a lower complexity than the SG method. In particular, we first show that RSG can reduce the dependence of SG's iteration complexity on the distance between the initial solution and the optimal set to that between the is an element of -level set and the optimal set multiplied by a logarithmic factor. Moreover, we show the advantages of RSG over SG in solving a broad family of problems that satisfy a local error bound condition, and also demonstrate its advantages for three specific families of convex optimization problems with different power constants in the local error bound condition. (a) For the problems whose epigraph is a polyhedron, RSG is shown to converge linearly. (b) For the problems with local quadratic growth property in the 6-sublevel set, RSG has an O(1/is an element of log(1/is an element of)) iteration complexity. (c) For the problems that admit a local Kurdyka-Lojasiewicz property with a power constant of beta is an element of E[0, 1), RSG has an O(1/is an element of(2 beta) log(1/is an element of)) iteration complexity. The novelty of our analysis lies at exploiting the lower bound of the first-order optimality residual at the 6-level set. It is this novelty that allows us to explore the local properties of functions (e.g., local quadratic growth property, local Kurdyka-Lojasiewicz property, more generally local error bound conditions) to develop the improved convergence of RSG. We also develop a practical variant of RSG enjoying faster convergence than the SG method, which can be run without knowing the involved parameters in the local error bound condition. We demonstrate the effectiveness of the proposed algorithms on several machine learning tasks including regression, classification and matrix completion.
Details
- Title: Subtitle
- RSG: Beating Subgradient Method without Smoothness and Strong Convexity
- Creators
- Tianbao Yang - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USAQihang Lin - Univ Iowa, Dept Management Sci, Iowa City, IA 52242 USA
- Resource Type
- Journal article
- Publication Details
- Journal of machine learning research, Vol.19, pp.1-33
- Publisher
- Microtome Publ
- ISSN
- 1532-4435
- eISSN
- 1533-7928
- Number of pages
- 33
- Grant note
- 1463988; 1545995 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2018
- Academic Unit
- Computer Science; Business Analytics
- Record Identifier
- 9984259411102771
Metrics
8 Record Views