Variance Reduction in SGD by Distributed Importance Sampling

By Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron C. Courville, Yoshua Bengio. 2015

227 citations recorded by the source corpus.

Humans are able to accelerate their learning by selecting training materials that are the most informative and at the appropriate level of difficulty. We propose a framework for distributing deep learning in which one set of workers search for the most informative examples in parallel while a single worker updates the model on examples selected by importance sampling. This leads the model to update using an unbiased estimate of the gradient which also has minimum variance when the sampling proposal is proportional to the L2-norm of the gradient. We show experimentally that this method reduces gradient variance even in a context where the cost of synchronization across machines cannot be ignored, and where the factors for importance sampling are not updated instantly across the training set.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Distributed Prioritized Experience Replay (2018, neutral): “In supervised learning, this approach has been successfully extended to the distributed setting (Alain et al., 2015).”
Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples (2017, methodology): “On the other hand, focusing on harder samples may accelerate and stabilize SGD in cleaner data by minimizing the variance of gradients [1, 12].”
Online Batch Selection for Faster Training of Neural Networks (2015, methodology): “The authors of (Alain et al., 2015) note that their importance sampling approach is limited to fully connected networks (at least so far), whereas our approach directly works for any kind of network structure.”
Not All Samples Are Created Equal: Deep Learning with Importance Sampling (2018, background): “This results in reduced computational requirements of more than an order of magnitude compared to Alain et al. (2015).”
Toward an Integration of Deep Learning and Neuroscience (2016, background): “Interestingly, however, stochastic gradient descent can be used to generate a system that samples adaptively (Alain et al., 2015; Bouchard et al., 2015).”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, background): “Importance sampling [1, 12, 30], uses only a subset of the dataset in each epoch to save on computation.”
Asynchronous Byzantine Machine Learning (2018, background): “Other approaches consider variance minimization by importance sampling (Alain et al., 2015).”
A Survey on Curriculum Learning (2021, background): “Other works [118], [144] [69], [101] or the gradient magnitude [1], [28].”
Safe Adaptive Importance Sampling (2017, background): “Therefore one has to rely on approximations based on upper bounds [36, 37], or stale values [22, 1].”
Variance-reduced Language Pretraining via a Mask Proposal Network (2020, unknown): “Theorem 2 [1] Denote z1, · · · , zT are i.”
Training Deep Models Faster with Robust, Approximate Importance Sampling (2018, methodology): “This result contrasts starkly with [3], for example, in which case generalization performance differs significantly for the importance sampling and standard algorithms.”
Think Locally, Act Globally: Federated Learning with Local and Global Representations (2020, background): “We also found that weighting the updates by the norm of the global gradient ( i.e. sped up convergence [3].”
FairBatch: Batch Selection for Model Fairness (2020, background): “More recently, importance sampling techniques have been proposed for faster convergence (Loshchilov and Hutter, 2016; Alain et al., 2016; Stich et al., 2017; Csiba and Richt ´ arik, 2018; Katharopoulos and Fleuret, 2018; Johnson and Guestrin, 2018).”
Adaptive Sampling for SGD by Exploiting Side Information (2016, background): “During the publication of this work, a very similar idea was pursued in (Alain et al., 2015), where the sampling weights are proportional to the L2 norm of the gradient (similar to our work) but the distribution is maintained at an instance level (thereby requiring multiple machines to update/search”
Meta Learning on a Sequence of Imbalanced Domains with Difficulty Awareness (2021, unknown): “Following [29, 1], it can be expressed as:”
Efficient training of physics‐informed neural networks via importance sampling (2021, methodology): “…an unbiased estimate of the gradient ∇ θ J ( θ ), following Equations 8, 11, the mini-batch gradient descent update rule will then be given by [32, 34] This derivation provides a theoretical evidence that training of PINNs can be accelerated using an importance sampling approach where training…”