Source-linked AI summary
Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling
Peilin Zhao, Tong Zhang
TL;DR
Uniform minibatch SGD is unbiased but can have high variance, which can slow convergence. The paper clusters the dataset and uses stratified sampling to reduce variance; its analysis and experiments report improved convergence and effectiveness.
Problem
Uniformly sampled minibatch gradients are unbiased but may have high variance, which can negatively affect convergence.
Source: §1 · p. 1Method
The method clusters the dataset and uses stratified sampling to construct unbiased stochastic gradient estimators that minimize an upper bound on variance.
Source: §1 · p. 1, §3.3 · p. 4Results
Under certain conditions, the proposed method can significantly improve convergence, and experiments verify its effectiveness.
Source: §1 · p. 1Takeaways & Limitations
The sampling objective is tied to roughly minimizing the sum of weighted standard deviations of gradients across subdatasets.
Source: §1 · p. 1The variance-minimizing approach is impractical directly because it requires n derivative calculations and reclustering at every iteration.
Source: §3.3 · p. 5
Abstract
from arXiv · showhide
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.
1 Introduction
Uniform minibatch sampling is unbiased but can have high variance, motivating stratified sampling for SGD. The paper analyzes variance-minimizing sampling and reports improved convergence under certain conditions.
1 Introduction
- Uniformly sampled minibatches are unbiased gradient estimates, but their potentially high variance can negatively affect convergence.The proposed alternative partitions the dataset into clusters and samples across them.Source: §1 · p. 1
- Stratified sampling constructs unbiased stochastic gradient estimators by minimizing an upper bound on variance, with an optimal strategy targeting weighted subdataset gradient standard deviations.The analysis shows improved convergence under certain conditions, and experiments verify the result.Source: §1 · p. 1
- The paper proceeds from related work to stratified minibatch SGD, empirical evaluations, and a conclusion.Source: §1 · p. 2
2 Related Work
Related work includes finite-sample convergence analyses and variance-reduction approaches for SGD. This paper distinguishes stratified sampling from those approaches and describes it as complementary to them.
2 Related Work
- For convex loss, SGD has an O(1/T) convergence rate, while strongly convex loss has an O(log T/T) rate, improved to O(1/T) with suffix or polynomial-decay averaging.The cited discussion contrasts these finite-sample results with earlier asymptotic analyses.Source: §2 · p. 2
- SVRG produces an unbiased estimator whose variance approaches zero asymptotically for finite training data, while a control-variate method uses low-order moments but retains uniform sampling.Source: §2 · p. 2
- Stratified sampling is presented as a distinct minibatch variance-reduction method, complementary to SVRG and importance sampling, and combinable with them.Source: §2 · p. 2
3 Minibatch SGD with Stratified Sampling
The section motivates minibatching as a parallel SGD strategy whose variance can be reduced further by stratifying examples into clusters. It develops cluster-based sampling and gives convergence bounds, including gradient-descent-matching rates when estimator variance is zero.
3.2 Problem Setting
- Uniform minibatching reduces estimator variance by 1/b versus single-example SGD, but costs b times more computation and supports parallel training.Source: §3.2 · p. 4
3.3 Algorithm
- SGD-ss partitions indices into clusters and samples uniformly within each cluster, combining cluster minibatches into an update that equals the full-gradient update in expectation.Source: §3.3 · p. 4
- The variance-minimizing design is a dynamically weighted k-means problem, but exact per-iteration clustering is impractical; per-class standard k-means is a simpler alternative.Exact variance minimization requires calculating n derivatives and running clustering every iteration.Source: §3.3 · pp. 5–6
3.4 Analysis
- O(1/T) for convex smooth objectives and O(alpha(eta)^T) for strongly convex smooth objectives are obtained when Vt=0, matching gradient descent's respective bounds.Source: §3.4 · pp. 8–9
4 Experiments
The experiments compare stratified-sampling SGD with uniform-sampling SGD on multiclass logistic-regression benchmarks, measuring training objectives, test errors, and gradient-estimator variance. The reported results favor SGD-ss on covtype.binary and across additional datasets.
4.1 Experimental Setup
- The experiments use L2-regularized multiclass logistic regression on benchmark datasets selected to cover various dataset sizes.The setup uses a common step-size schedule and matching minibatch sizes for SGD and SGD-ss; a simpler k-means clustering alternative is reported to cause no performance degradation.Source: §4.1 · p. 10
- Performance is assessed using training primal objective, test error rate, and stochastic-gradient-estimator variance, averaged over five random-seed runs per dataset.The experiments compare the proposed algorithm with uniform-sampling SGD.Source: §4.1 · p. 10, §4 · p. 10
4.2 Performance Evaluation
- On covtype.binary, SGD-ss converges faster and more stably, with smaller test error rates and stochastic-gradient variance than uniform-sampling SGD.The comparison used the same minibatch size and learning rates for both algorithms.Source: §4.2 · pp. 10–11, Figure 1 · p. 11
- Across letter, mnist, pendigits, and usps, SGD-ss is reported as clearly superior to uniform-sampling SGD on logistic-regression results.The reported measures are primal objective value, test error rate, and stochastic-gradient variance.Source: §4.2 · p. 11
5 Conclusion
The paper concludes that dynamic and fixed stratified-sampling strategies reduce SGD training convergence time. Experiments report promising effectiveness against uniform sampling.
5 Conclusion
- The proposed stratified-sampling approach includes both dynamic and fixed strategies for SGD.The conclusion describes the approach as targeting variance reduction.Source: §5 · p. 11
- The authors report that the proposed strategies can significantly reduce the convergence rate for the training process.Source: §5 · p. 11
- Experiments compare the method with uniform sampling and report promising empirical validation across objective, test-error, and gradient-variance measures.Figure 2 covers letter, mnist, pendigits, and usps.Source: §5 · p. 11, Figure 2 · p. 12