Source-linked AI summary
Variance Reduction in SGD by Distributed Importance Sampling
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, Yoshua Bengio
TL;DR
Distributed deep learning must train a single model across multiple GPUs while addressing communication and synchronization costs. The paper uses distributed workers to find informative examples and importance sampling to update the model, reporting reduced gradient variance and improved training time even with stale weights.
Problem
Training a single model across multiple GPUs requires distributed methods, while ASGD incurs substantial bandwidth costs and may use stale gradients after synchronization barriers are removed.
Method
Workers search for informative examples in parallel, and a model-updating worker uses importance sampling based on gradient information.
Results
The method reduced gradient-estimate variance in distributed settings with stale importance weights and produced significant training-time improvements on permutation invariant SVHN.
Takeaways & Limitations
Importance sampling offers a novel distributed-training approach that can supplement ASGD while focusing learner attention on informative examples.
Takeaways & Limitations
The method’s higher-dimensional variance objective requires choosing what aspect of covariance to minimize, and the implementation receives weights that may be stale.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Distributed deep learning must use multiple GPUs without incurring the bandwidth and theoretical costs associated with asynchronous training. The paper proposes importance sampling as a different distributed-training principle focused on informative examples.
- Multiple GPUs, including GPUs on separate computers, create a central challenge for training a single model.
- ASGD parallelizes gradient computation and removes synchronization barriers so distributed training can run faster.
- ASGD requires substantial bandwidth and can lose theoretical guarantees because synchronization is removed and stale gradients are used.
- The paper presents importance sampling as an alternative distributed-training principle and positions experiments as proof of concept rather than a replacement mandate for ASGD.
- The method focuses learning attention on examples that are most informative from the learner’s perspective.
2 SCALING DEEP LEARNING BY DISTRIBUTING IMPORTANCE SAMPLING
The proposed distributed approach has workers identify useful training samples while reducing communication relative to sending minibatch gradients. It adapts curriculum-learning intuition by using the model to identify currently informative examples.
- The approach selects useful training samples rather than giving equal attention to every training example.
- The method extends curriculum-learning ideas by having the model determine which examples are currently informative for the learner.
- Adaptive Weighted SGD also calibrates sampling coefficients to reduce variance, while this paper presents an exact method for obtaining optimal coefficients.
- Workers communicate one floating-point number per training sample instead of minibatch gradients, potentially reducing network transfers for 100 MB to 1 GB parameter models.
- Parameter communication remains necessary, but its cost can be amortized if sample selection remains robust to older parameters.
3 IMPORTANCE SAMPLING IN THEORY
The paper generalizes importance sampling to vector-valued functions by minimizing the trace of the estimator’s covariance, while preserving unbiasedness. It also gives a gradient-norm computation for fully connected networks, but this formula does not extend to convolutions with parameter sharing.
- 3.1 CLASSIC CASE IN SINGLE DIMENSION: Importance sampling estimates expectations from samples drawn under a proposal q(x), requiring q(x)>0 wherever p(x)>0.The proposal reweights samples from the target distribution while maintaining a valid estimator.
- 3.1 CLASSIC CASE IN SINGLE DIMENSION: The importance-sampling estimator is unbiased, with mean µ = E_p[f(x)], and its variance can then be minimized through the proposal choice.The paper first verifies unbiasedness and then optimizes the estimator’s variance.
- 3.2 EXTENDING BEYOND A SINGLE DIMENSION: For vector-valued functions, the paper minimizes Tr(Σ), the sum of the variances of the gradient-vector components.The Frobenius-norm alternative is noted but does not have a known analytical optimum.
- 3.2 EXTENDING BEYOND A SINGLE DIMENSION: The resulting optimal proposal q* generalizes the classic one-dimensional importance-sampling result and achieves the optimal covariance-trace value.The theorem is stated for a general function f, later interpreted as a model-loss gradient.
- 3.2 EXTENDING BEYOND A SINGLE DIMENSION: With a dataset, importance weights can define q by setting ˜ω_n=h(x_n), normalizing them, and sampling from the resulting multinomial distribution.This enables proposal sampling even when p(x) is not directly known.
- 3.3 DEALING WITH MINIBATCHES: The gradient-norm recipe applies to fully connected MLP layers but fails for convolutions because of sparsity patterns and parameter sharing.In mixed architectures, it still applies to fully connected layers, but the paper does not investigate ignoring convolutional contributions.
4 DISTRIBUTED IMPLEMENTATION OF ISSGD
The distributed ISSGD implementation approximates an oracle by having workers update per-sample probability weights while a master trains on importance-sampled minibatches. Although communication delays make these weights stale, the method retains unbiased gradients, and stale proposals are experimentally compared with the ideal minimum-variance proposal.
- Oracle-based sampling: The oracle assigns each training sample a probability weight proportional to its gradient norm, enabling ideal importance sampling.The ideal proposal is denoted qIDEAL and is contrasted with uniform and stale proposals.
- Oracle-based sampling: Minibatches are sampled with replacement according to the weights, and the loss is scaled as prescribed by importance sampling.Uniform sampling is recovered when all weights are equal.
- Distributed implementation: A master worker updates model parameters, while GPU-equipped workers repeatedly refresh per-sample weights using parameter copies retrieved through a database.The database decouples master and worker communication, allowing parameter and weight updates to be retrieved asynchronously.
- Distributed implementation: Distributed delays make the master’s weights stale because they may reflect parameters from an earlier iteration.The paper distinguishes degrees of staleness and defines qSTALE using weights from the previous iteration as a pessimistic estimator.
- Variance under staleness: Tr(Σ(qIDEAL)) is a lower bound on all proposal variances, and experiments generally observe the corresponding inequality when staleness is not excessive.The paper also notes practical robustness measures including weight filtering, gradient-norm approximation, and smoothing constants.
- Relaxed synchronization: Even after synchronization barriers are removed, ISSGD retains an unbiased gradient estimator, although stale probability weights may increase variance.The implementation uses barriers only for sanity checks or studying the absence of staleness.
5 EXPERIMENTAL RESULTS
Experiments on permutation-invariant SVHN compare ISSGD with regular SGD across training speed, prediction error, and gradient-variance measurements. ISSGD reaches zero training loss faster and can reduce variance, although smoothing and generalization outcomes depend on the setting.
- Dataset and model: The experiments use about 600,000 cropped 32x32 RGB SVHN images, a permutation-invariant task, and a four-hidden-layer MLP with 2048 units per layer.The model uses ReLU activations except for a final softmax; convolutional models were excluded because per-example gradient norms were unavailable.
- Distributed setup: The distributed setup uses one ISSGD master, one database, and multiple GPU workers that evaluate quantities needed for importance sampling.Synchronization barriers can be enforced for an exact method or dropped for faster practical training.
- Training and prediction: Across both hyperparameter settings, ISSGD minimizes training loss faster than regular SGD and reaches 0.0.Results are medians over 50 random initializations, with quartiles shown to indicate variation.
- Training and prediction: Test prediction error does not consistently favor faster ISSGD convergence; the authors suggest regular SGD may benefit from a variance-related regularization effect.The two hyperparameter settings produce opposite generalization comparisons between the methods.
- Training and prediction: Final test prediction errors are very similar for ISSGD and regular SGD when each method uses its best validation-selected hyperparameters.The values average prediction errors over the final 10% of plotted timesteps.
- Variance reduction: ISSGD shows a smaller square root of Tr(Σ(q)) clearly under the smaller learning rate and +1.0 smoothing, but the reduction is less convincing with +10.0 smoothing.Adding constants improves stability while trading away potential variance-reduction gains.
6 FUTURE WORK
Future work is needed to extend the method beyond fully connected networks and to compare or combine it with ASGD. The paper identifies approximate gradient norms and peer-based distributed designs as possible directions.
- Model scope: The theoretical proposition applies only to models with fully connected layers, excluding popular convolutional neural networks.The paper suggests extending the method to parameter-sharing models such as convolutional networks and RNNs.
- Model scope: Approximate gradient norms for convolutional layers could enable importance sampling, but the resulting scheme may be lower quality and difficult to evaluate.Possible approximations include ignoring contributions from sparsely connected layers, though this strategy is not investigated.
- Comparison with ASGD: The paper avoids direct ASGD comparisons because the authors lack a production-quality ASGD implementation.They propose studying whether combining ASGD and ISSGD produces positive interactions or interference.
- Comparison with ASGD: A proposed combination with ASGD removes the master-worker distinction and lets peers obtain and share importance weights when computing gradient contributions.The design could use a parameter server, shared memory, or another synchronization method.
7 CONCLUSION
The paper presents distributed importance sampling as a way to focus training on informative examples. On permutation-invariant SVHN, it reports faster training and reduced gradient-estimate variance despite distributed, stale importance weights.
- Conclusion: The method uses multiple machines to search for the most informative training examples for neural-network training.This is the paper’s proposed approach to distributing training.
- Conclusion: The method produced significant training-time improvements on permutation-invariant SVHN.The reported evaluation used this task as the experimental setting.
- Conclusion: Importance sampling reduced gradient-estimate variance in the distributed setting even when importance weights were not exact.The conclusion identifies stale or imperfect weights as compatible with observed variance reduction.
- Conclusion: Extending the method to parameter-sharing models and comparing or combining it with ASGD remain future-work directions.The paper specifically names convolutional networks, RNNs, and ASGD as targets for further study.
A.1 EXTENDING BEYOND A SINGLE DIMENSION
For vector-valued importance sampling, the unbiased estimator’s covariance trace is minimized by sampling proportionally to the Euclidean norm of the integrand. The paper extends this result to minibatch neural-network gradients and derives a compact way to compute per-example gradient norms.
- The importance-sampling estimator remains unbiased when its proposal distribution satisfies q(x) > 0 whenever p(x) > 0.
- The trace of the estimator covariance is minimized by the optimal proposal q∗, which is proportional to p(x)∥f(x)∥2.
- This proposal achieves the smallest covariance-trace value possible among valid proposal distributions.
- For a proposal proportional to p(x)h(x), the covariance trace can be expressed using h, and dataset samples can implement the proposal through unnormalized weights ˜ωn = h(xn).
- In multilayer perceptrons, the Euclidean norm of each example’s flattened parameter gradient can be computed from Frobenius norms of the corresponding matrix-shaped gradients.
B.1 USING ONLY A SUBSET OF THE WEIGHTS
The distributed method can filter out stale importance weights before sampling, retaining only recently updated candidates. On SVHN, this filtering reduced the active weights substantially without favoring samples a priori, while more workers reduced staleness.
- A staleness threshold filters out candidates whose importance weights have not been updated sufficiently recently.
- 15% of SVHN probability weights were retained with a 4-second threshold and 3 workers, while 85% were filtered out.
- The filtering gives every probability weight an equal chance of being retained based on when it was last recomputed, rather than favoring samples a priori.
- Adding more workers lowers average weight staleness by enabling more frequent updates, although parameter communication remains costly.
B.2 APPROXIMATING ∥gTRUE∥2
The paper approximates the true full-dataset gradient norm because computing it directly would defeat the efficiency goal of ISSGD. Using the same approximation across proposals preserves their covariance-trace ordering, and the approximation becomes accurate near convergence.
- The true gradient gTRUE is defined as the expected gradient over the entire training set but is not directly computed for practical reasons.
- Instead, the method averages per-minibatch parameter-gradient norms, producing an upper bound on ∥gTRUE∥2.
- Using the same approximation for all three proposals does not change the ordering of Tr(Σ(qIDEAL)), Tr(Σ(qSTALE)), and Tr(Σ(qUNIF)).
- Near the end of training, the upper bound becomes insignificant, making the three reported covariance traces very close to their exact values.
B.3 SMOOTHING PROBABILITY WEIGHTS
Rapidly changing gradients can make stale, low-probability weights produce unstable updates. The method adds a smoothing constant to trade potential variance-reduction gains for greater training stability, approaching regular SGD as the constant grows.
- A rapidly changing gradient can make a stale low-probability sample receive an excessively large scaled contribution, threatening long-term training stability without changing unbiasedness.
- Adding a smoothing constant to every unnormalized probability weight makes the sampling behavior more robust to sudden gradient changes.
- Larger smoothing constants make ISSGD resemble regular SGD, with an infinite constant yielding exactly regular SGD.
- The paper did not explore an adaptive procedure for selecting the smoothing constant because many other hyperparameters required study.