Conference proceeding
Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence
INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 70, Vol.70
Proceedings of Machine Learning Research
01/01/2017
Abstract
In this paper, a new theory is developed for first-order stochastic convex optimization, showing that the global convergence rate is sufficiently quantified by a local growth rate of the objective function in a neighborhood of the optimal solutions. In particular, if the objective function F(w) in the epsilon-sublevel set grows as fast as vertical bar vertical bar w-w(*)vertical bar vertical bar(1/theta)(2), where w, represents the closest optimal solution to w and theta ( )is an element of (0, 1] quantifies the local growth rate, the iteration complexity of first-order stochastic optimization for achieving an epsilon-optimal solution can be (O) over tilde (1/epsilon(2(1-theta)) ), which is optimal at most up to a logarithmic factor. To achieve the faster global convergence, we develop two different accelerated stochastic subgradient methods by iteratively solving the original problem approximately in a local region around a historical solution with the size of the local region gradually decreasing as the solution approaches the optimal set. Besides the theoretical improvements, this work also include new contributions towards making the proposed algorithms practical: (i) we present practical variants of accelerated stochastic subgradient methods that can run without the knowledge of multiplicative growth constant and even the growth rate theta; (ii) we consider a broad family of problems in machine learning to demonstrate that the proposed algorithms enjoy faster convergence than traditional stochastic subgradient method. For example, when applied to the l(1) regularized empirical polyhedral loss minimization (e.g., hinge loss, absolute loss), the proposed stochastic methods have a logarithmic iteration complexity.
Details
- Title: Subtitle
- Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence
- Creators
- Yi Xu - University of IowaQihang Lin - University of IowaTianbao Yang - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA
- Contributors
- D Precup (Editor)Y W Teh (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 70, Vol.70
- Publisher
- JMLR-JOURNAL MACHINE LEARNING RESEARCH
- Series
- Proceedings of Machine Learning Research
- ISSN
- 2640-3498
- Number of pages
- 10
- Grant note
- IIS-1463988; IIS-1545995 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2017
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984380411102771
Metrics
15 Record Views