2015

Stop Wasting My Gradients: Practical SVRG

Babanezhad, Reza, Ahmed, Mohamed Osama, Virani, Alim et al.

Understand

We present and analyze several strategies for improving the performance of stochastic variance-reduced gradient (SVRG) methods.

We first show that the convergence rate of these methods can be preserved under a decreasing sequence of errors in the control variate, and use this to derive variants of SVRG that use growing-batch strategies to reduce the number of gradient calculations required in the early iterations.
We further (i) show how to exploit support vectors to reduce the number of gradient computations in the later iterations, (ii) prove that the commonly-used regularized SVRG iteration is justified and improves the convergence rate, (iii) consider alternate mini-batch selection strategies, and (iv) consider the generalization error of the method.

Built on

T. Joachims, “Making large-scale SVM learning practical,” in Advances in Kernel Methods - Support Vector Learning
1999
Earlier work this paper cites.
Springer, 2004
Y. Nesterov, Introductory lectures on convex optimization: A basic course · 2004
Earlier work this paper cites.
R. Caruana, T. Joachims, and L. Backstrom, “KDD-cup 2004: results and analysis,” ACM SIGKDD Newsletter
2004
Earlier work this paper cites.
D. Lewis, Y. Yang, T. Rose, and F. Li, “RCV1: A new benchmark collection for text categorization research,” Journal of Machine Learning Research
2004
Earlier work this paper cites.
S. Keerthi and D. DeCoste, “A modified finite newton method for fast solution of large scale linear svms,” Journal of Machine Learning Research
2005
Earlier work this paper cites.
http://plg.uwaterloo.ca/~gvcormac/treccorpus/
G. V. Cormack and T. R. Lynam, “Spam corpus creation for TREC,” in Proc. 2nd Conference on Email and Anti-Spam · 2005
Earlier work this paper cites.
S. Rosset and J. Zhu, “Piecewise linear regularized solution paths,” The Annals of Statistics
2007
Earlier work this paper cites.
L. Bottou and O. Bousquet, “The tradeoffs of large scale learning,” Advances in neural information processing systems (NIPS)
2007
Earlier work this paper cites.
I. Guyon, “Sido: A phamacology dataset,” 2008
2008
Earlier work this paper cites.
C. Hu, J. Kwok, and W. Pan, “Accelerated gradient methods for stochastic optimization and online learning,” Advances in neural information processing systems (NIPS)
2009
Earlier work this paper cites.

Similar

Cengage Learning, 2009
S. Lohr, Sampling: design and analysis · 2009
Cited alongside, same era.
PhD thesis, Univ. of British Columbia, May 2009
Original
P. Carbonetto, New probabilistic inference algorithms that harness the strengths of variational and Monte Carlo methods · 2009
Cited alongside, same era.
N. Usunier, A. Bordes, and L. Bottou, “Guarantees for approximate incremental svms,” International Conference on Artificial Intelligence and Statistics (AISTATS)
2010
Cited alongside, same era.
L. Bottou, “Large-scale machine learning with stochastic gradient descent,” in Proceedings of COMPSTAT’2010
2010
Cited alongside, same era.
A. Frank and A. Asuncion, “UCI machine learning repository,” 2010
2010
Cited alongside, same era.
M. Schmidt, N. Le Roux, and F. Bach, “Convergence rates of inexact proximal-gradient methods for convex optimization,” Advances in neural information processing systems (NIPS)
2011
Cited alongside, same era.
N. Le Roux, M. Schmidt, and F. Bach, “A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets,” Advances in neural information processing systems (NIPS)
2012
Cited alongside, same era.
M. P. Friedlander and M. Schmidt, “Hybrid deterministic-stochastic methods for data fitting,” SIAM Journal of Scientific Computing
2012
Cited alongside, same era.
A. Aravkin, M. P. Friedlander, F. J. Herrmann, and T. Van Leeuwen, “Robust inversion, dimensionality reduction, and randomized sampling,” Mathematical Programming
2012
Cited alongside, same era.
R. H. Byrd, G. M. Chin, J. Nocedal, and Y. Wu, “Sample size selection in optimization methods for machine learning,” Mathematical programming
2012
Cited alongside, same era.

Then

K. van den Doel and U. Ascher, “Adaptive and stochastic algorithms for EIT and DC resistivity problems with piecewise constant solutions and many measurements,” SIAM J. Scient. Comput
2012
Later among the works it cites.
S. Shalev-Schwartz and T. Zhang, “Stochastic dual coordinate ascent methods for regularized loss minimization,” Journal of Machine Learning Research
2013
Later among the works it cites.
J. Mairal, “Optimization with first-order surrogate functions,” International Conference on Machine Learning (ICML)
2013
Later among the works it cites.
M. Mahdavi, L. Zhang, and R. Jin, “Mixed optimization for smooth functions,” Advances in neural information processing systems (NIPS)
2013
Later among the works it cites.
R. Johnson and T. Zhang, “Accelerating stochastic gradient descent using predictive variance reduction,” Advances in neural information processing systems (NIPS)
2013
Later among the works it cites.
L. Zhang, M. Mahdavi, and R. Jin, “Linear convergence with condition number independent access of full gradients,” Advances in neural information processing systems (NIPS)
2013
Later among the works it cites.
J. Konečný and P. Richtárik, “Semi-stochastic gradient descent methods,” arXiv preprint
2013
Later among the works it cites.
A. Defazio, F. Bach, and S. Lacoste-Julien, “Saga: A fast incremental gradient method with support for non-strongly convex composite objectives,” Advances in neural information processing systems (NIPS)
2014
Later among the works it cites.
L. Xiao and T. Zhang, “A proximal stochastic gradient method with progressive variance reduction,” SIAM Journal on Optimization
2014
Later among the works it cites.
J. Konečný, J. Liu, P. Richtárik, and M. Takáč, “ms2gd: Mini-batch semi-stochastic gradient descent in the proximal setting,” arXiv preprint
2014
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…