2015

Online Learning to Sample

Bouchard, Guillaume, Trouillon, Théo, Perez, Julien et al.

Understand

Stochastic Gradient Descent (SGD) is one of the most widely used techniques for online optimization in machine learning.

In this work, we accelerate SGD by adaptively learning how to sample the most useful training examples at each time step.
First, we show that SGD can be used to learn the best possible sampling distribution of an importance sampling estimator.
Second, we show that the sampling distribution of an SGD algorithm can be estimated online by incrementally minimizing the variance of the gradient.

A stochastic approximation method
H. Robbins and S. Monro · 1951
Earlier work this paper cites.
Acceleration of stochastic approximation by averaging
B. T. Polyak and A. B. Juditsky · 1992
Earlier work this paper cites.
Reinforcement Learning
Richard S. Sutton, editor · 1992
Earlier work this paper cites.
Global arrays: A nonuniform memory access programming model for high-performance computers
Jaroslaw Nieplocha, Robert J Harrison, and Richard J Littlefield · 1996
Earlier work this paper cites.
Simulation academic press
SM Ross · 1997
Earlier work this paper cites.
Online algorithms and stochastic approximations
L. Bottou · 1998
Earlier work this paper cites.
Gradient-based learning applied to document recognition
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner · 1998
Earlier work this paper cites.
Adaptive importance sampling to accelerate training of a neural probabilistic language model
J-S Senecal and Y Bengio · 2003
Earlier work this paper cites.
Histograms of oriented gradients for human detection
N Dalal and W Triggs · 2005
Earlier work this paper cites.
Policy gradient in continuous time, May 2006
Rémi Munos · 2006
Earlier work this paper cites.

Adaptive importance sampling to accelerate training of a neural probabilistic language model
Yoshua Bengio and J-S Senecal · 2008
Cited alongside, same era.
On the quantitative analysis of deep belief networks
R Salakhutdinov and I Murray · 2008
Cited alongside, same era.
Curriculum learning
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston · 2009
Cited alongside, same era.
The Pascal Visual Object Classes (VOC) Challenge
M Everingham, L Van Gool, C K I Williams, J Winn, and A Zisserman · 2010
Cited alongside, same era.
Algorithms for Reinforcement Learning
C. Szepesvari · 2010
Cited alongside, same era.
The tradeoffs of large scale learning
L Bottou and O Bousquet · 2011
Cited alongside, same era.
Non-asymptotic analysis of stochastic approximation algorithms for machine learning
F Bach and E Moulines · 2011
Cited alongside, same era.
Adaptive subgradient methods for online learning and stochastic optimization
J Duchi, E Hazan, and Y Singer · 2011
Cited alongside, same era.
Beating sgd: Learning svms in sublinear time
Elad Hazan, Tomer Koren, and Nati Srebro · 2011
Cited alongside, same era.
Non-negative matrix factorization as a feature selection tool for maximum margin classifiers
Mithun Das Gupta and Jing Xiao · 2011
Cited alongside, same era.
Software Engineering Advice from Building Large-Scale Distributed Systems
J Dean
Cited in the paper.

Hybrid deterministic-stochastic methods for data fitting
M Friedlander and M Schmidt · 2012
Later among the works it cites.
Variational bayesian inference with stochastic search
J Paisley, D Blei, and M Jordan · 2012
Later among the works it cites.
Towards Good Practice in Large-Scale Learning for Image Classification
F Perronnin, Z Akata, Z Harchaoui, and C Schmid · 2012
Later among the works it cites.
ImageNet Classification with Deep Convolutional Neural Networks
A Krizhevsky, GE Hinton, and I Sutskever · 2012
Later among the works it cites.
Loss-proportional subsampling for subsequent erm
P Mineiro and N Karampatziakis · 2013
Later among the works it cites.
Stochastic variational inference
M Hoffman, D Blei, C Wang, and J Paisley · 2013
Later among the works it cites.
DeCAF : A Deep Convolutional Activation Feature for Generic Visual Recognition
J Donahue, Y Jia, O Vinyals, J Hoffman, N Zhang, E Tzeng, and T Darrell · 2014
Later among the works it cites.
Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks
M Oquab, L Bottou, I Laptev, and J Sivic · 2014
Later among the works it cites.
Rich feature hierarchies for accurate object detection and semantic segmentation
R Girshick, J Donahue, T Darrell, and J Malik · 2014
Later among the works it cites.
Deterministic policy gradient algorithms
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller · 2014
Later among the works it cites.

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

alphaXiv is searching for related work…

Reading the bibliography…