Conference proceeding
Adaptive SVRG Methods under Error Bound Conditions with Unknown Growth Parameter
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 30 (NIPS 2017), Vol.30
Advances in Neural Information Processing Systems
01/01/2017
Abstract
Error bound, an inherent property of an optimization problem, has recently revived in the development of algorithms with improved global convergence without strong convexity. The most studied error bound is the quadratic error bound, which generalizes strong convexity and is satisfied by a large family of machine learning problems. Quadratic error bound have been leveraged to achieve linear convergence in many first-order methods including the stochastic variance reduced gradient (SVRG) method, which is one of the most important stochastic optimization methods in machine learning. However, the studies along this direction face the critical issue that the algorithms must depend on an unknown growth parameter (a generalization of strong convexity modulus) in the error bound. This parameter is difficult to estimate exactly and the algorithms choosing this parameter heuristically do not have theoretical convergence guarantee. To address this issue, we propose novel SVRG methods that automatically search for this unknown parameter on the fly of optimization while still obtain almost the same convergence rate as when this parameter is known. We also analyze the convergence property of SVRG methods under Holderian error bound, which generalizes the quadratic error bound.
Details
- Title: Subtitle
- Adaptive SVRG Methods under Error Bound Conditions with Unknown Growth Parameter
- Creators
- Yi Xu - University of IowaQihang Lin - Univ Iowa, Dept Management Sci, Iowa City, IA 52242 USATianbao Yang - University of Iowa
- Contributors
- I Guyon (Editor)U V Luxburg (Editor)S Bengio (Editor)H Wallach (Editor)R Fergus (Editor)S Vishwanathan (Editor)R Garnett (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 30 (NIPS 2017), Vol.30
- Publisher
- Neural Information Processing Systems (Nips)
- Series
- Advances in Neural Information Processing Systems
- ISSN
- 1049-5258
- Number of pages
- 11
- 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
- 9984380476702771
Metrics
3 Record Views