Fetching the paper…

Reading the bibliography…

2015

Variance Reduced Stochastic Gradient Descent with Neighbors

Hofmann, Thomas, Lucchi, Aurelien, Lacoste-Julien, Simon et al.

Original
PDF
Post on X

Understand

Stochastic Gradient Descent (SGD) is a workhorse in machine learning, yet its slow convergence can be a computational bottleneck.

Variance reduction techniques such as SAG, SVRG and SAGA have been proposed to overcome this weakness, achieving linear convergence.
However, these methods are either based on computations of full gradients at pivot points, or on keeping per data point corrections in memory.
Therefore speed-ups relative to SGD may need a minimal number of epochs in order to materialize.

Variance Reduced Stochastic Gradient Descent with Neighbors · Around

Built on

A stochastic approximation method
H. Robbins and S. Monro · 1951
Earlier work this paper cites.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
A. Andoni and P. Indyk · 2008
Earlier work this paper cites.
Large-scale machine learning with stochastic gradient descent
L. Bottou · 2010
Earlier work this paper cites.
Pegasos: Primal estimated sub-gradient solver for SVM
S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter · 2011
Earlier work this paper cites.

Similar

Accelerating stochastic gradient descent using predictive variance reduction
R. Johnson and T. Zhang · 2013
Cited alongside, same era.
Semi-stochastic gradient descent methods
Original
J. Konečnỳ and P. Richtárik · 2013
Cited alongside, same era.
Minimizing finite sums with the stochastic average gradient
Original
M. Schmidt, N. L. Roux, and F. Bach · 2013
Cited alongside, same era.
Stochastic dual coordinate ascent methods for regularized loss
S. Shalev-Shwartz and T. Zhang · 2013
Cited alongside, same era.

Then

SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives
A. Defazio, F. Bach, and S. Lacoste-Julien · 2014
Later among the works it cites.
Convergence rate of stochastic gradient with constant step size
M. Schmidt · 2014
Later among the works it cites.
Randomized partition trees for nearest neighbor search
S. Dasgupta and K. Sinha · 2015
Closest in time.

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…