Batched Stochastic Gradient Descent with Weighted Sampling

By Deanna Needell, Rachel A. Ward. 2016

38 citations recorded by the source corpus.

We analyze a batched variant of Stochastic Gradient Descent (SGD) with weighted sampling distribution for smooth and non-smooth objective functions. We show that by distributing the batches computationally, a significant speedup in the convergence rate is provably possible compared to either batched sampling or weighted sampling alone. We propose several computationally efficient schemes to approximate the optimal weights, and compute proposed sampling distributions explicitly for the least squares and hinge loss problems. We show both analytically and experimentally that substantial gains can be obtained.

Subfields: 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 Optimization & Training

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “[14], Moulines and Bach [35], Needell and Ward [36], Needell et al.”
SGD: General Analysis and Improved Rates (2019, methodology): “The analysis of Needell et al. (2016) was later extended to a mini-batch variant where the mini-batches are formed by partitioning the data (Needell & Ward, 2017).”
Better Theory for SGD in the Nonconvex World (2020, background): “In this setting, data access is expensive, and g ( x ) is typically constructed via subsampling techniques such as minibatching (Dekel et al., 2012) and importance sampling (Needell et al., 2016).”
Gradient Diversity Empowers Distributed Learning (2017, methodology): “Besides batch-size selection, weighted sampling techniques have also been developed for mini-batch SGD [32, 48].”
One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods (2019, background): “This situation does not change even when tricks such as mini-batching or importance sampling (or a combination of both) are applied [24, 23, 5].”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “There are several choices that one can use including constant step-size (Moulines and Bach, 2011; Needell et al., 2016; Gower et al., 2019; Needell and Ward, 2017; Nguyen et al., 2018), decreasing step-size (Robbins and Monro, 1951; Ghadimi and Lan, 2013; Gower et al.”
AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods (2017, methodology): “Our proof technique is based on a variation from the one introduced by [21].”
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).”