Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/6823

Accelerated gradient methods for stochastic optimization and online learning

Authors Hu, Chonghai
Kwok, James T Y
Pan, Weike
Issue Date 2009
Source Proceedings of the 23rd Annual Conference on Neural Information Processing Systems , Vancouver, B. C., Canada, 7-9 December 2009,
Summary Regularized risk minimization often involves non-smooth optimization, either because of the loss function (e.g., hinge loss) or the regularizer (e.g., ℓ1-regularizer). Gradient methods, though highly scalable and easy to implement, are known to converge slowly. In this paper, we develop a novel accelerated gradient method for stochastic optimization while still preserving their computational simplicity and scalability. The proposed algorithm, called SAGE (Stochastic Accelerated GradiEnt), exhibits fast convergence rates on stochastic composite optimization with convex or strongly convex objectives. Experimental results show that SAGE is faster than recent (sub)gradient methods including FOLOS, SMIDAS and SCD. Moreover, SAGE can also be extended for online learning, resulting in a simple algorithm but with the best regret bounds currently known for these problems.
Subjects
Rights © 2009 NIPS Foundation.
Language English
Format Conference paper
Access
Files in this item:
File Description Size Format
nips09.pdf 195108 B Adobe PDF