Conference proceeding
O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
Proceedings of Machine Learning Research, Vol.28, pp.1121-1129
International Conference on Machine Learning, 30th
04/02/2013
Abstract
Traditional algorithms for stochastic optimization require projecting the solution at each iteration into a given domain to ensure its feasibility. When facing complex domains, such as the positive semidefinite cone, the projection operation can be expensive, leading to a high computational cost per iteration. In this paper, we present a novel algorithm that aims to reduce the number of projections for stochastic optimization. The proposed algorithm combines the strength of several recent developments in stochastic optimization, including mini-batches, extra-gradient, and epoch gradient descent, in order to effectively explore the smoothness and strong convexity. We show, both in expectation and with a high probability, that when the objective function is both smooth and strongly convex, the proposed algorithm achieves the optimal O(1/T) rate of convergence with only O(logT) projections. Our empirical study verifies the theoretical result.
Details
- Title: Subtitle
- O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
- Creators
- Lijun ZhangTianbao YangRong JinXiaofei He
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of Machine Learning Research, Vol.28, pp.1121-1129
- Conference
- International Conference on Machine Learning, 30th
- Language
- English
- Date published
- 04/02/2013
- Academic Unit
- Computer Science
- Record Identifier
- 9984259486102771
Metrics
24 Record Views