Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling

By Peilin Zhao, T. Zhang. 2014

98 citations recorded by the source corpus.

Stochastic Gradient Descent (SGD) is a popular optimization method which has been applied to many important machine learning tasks such as Support Vector Machines and Deep Neural Networks. In order to parallelize SGD, minibatch training is often employed. The standard approach is to uniformly sample a minibatch at each step, which often leads to high variance. In this paper we propose a stratified sampling strategy, which divides the whole dataset into clusters with low within-cluster variance; we then take examples from these clusters using a stratified sampling technique. It is shown that the convergence rate can be significantly improved by the algorithm. Encouraging experimental results confirm the effectiveness of the proposed method.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “In ord e to enable parallelism, the idea of mini-batching—using estim a ing the gradient using multiple random i in each iteration—is often employed [21], [22], [23], [24], [18], [25].”
Gradient Diversity: a Key Ingredient for Scalable Distributed Learning (2017, methodology): “De et al. (2016) propose an optimization algorithm for choosing the batch-size, and weighted sampling techniques have also been developed (Needell and Ward, 2016, Zhang et al., 2017, Zhao and Zhang, 2014).”
Stochastic Gradient Made Stable: A Manifold Propagation Approach for Large-Scale Optimization (2015, background): “The regularization term R(w) is mostly assumed to be non-differentiable and thus has no Lipschitz parameter.”
Advances in Variational Inference (2017, methodology): “These methods include stratiﬁed sampling [225], where one samples data from pre-deﬁned subgroups based on meta-data or labels, clustering-based sampling [47], which amounts to clustering the data using k-means and then sampling data from every cluster with adjusted probabilities, and diversiﬁed…”
Adaptive Sampling for SGD by Exploiting Side Information (2016, methodology): “As such, all the typical convergence guarantees of vanilla SGD (Robbins & Monro, 1951) follow even when using any arbitrary sampling distribution P (i), as long as the gradient estimates are unbiased and P (i) is a strictly positive distribution (Zhao & Zhang, 2014b).”
Stochastic Learning on Imbalanced Data: Determinantal Point Processes for Mini-batch Diversification (2017, methodology): “A second class of methods relies on non-uniform sampling of minibatches [8, 11, 32, 38, 47, 48].”