Source-linked AI summary
Importance Sampling for Minibatches
Dominik Csiba, Peter Richtárik
TL;DR
Importance sampling for minibatches had not previously been proposed or analyzed, despite the potential value of combining it with minibatching. The paper introduces bucket samplings and analyzes the new approach; experiments report substantial speedups on synthetic and real datasets.
Problem
Importance sampling for minibatches had not been proposed or analyzed, with subset selection, probability design, and efficient sampling posing challenges.
Source: §2 · p. 3Method
Results
Importance minibatching yields one or more orders of magnitude speedup over standard uniform minibatching on synthetic data, and up to an order of magnitude on real datasets.
Source: §2 · p. 3Takeaways & Limitations
The authors expect favorable speedups when real data have particular shapes and distributions of example sizes.
Source: §2 · p. 3The alternating-optimization procedure for computing (v*, p*) is costly because each iteration requires a pass over all data.
Source: §6.1 · p. 9
Abstract
from arXiv · showhide
Minibatching is a very well studied and highly popular technique in supervised learning, used by practitioners due to its ability to accelerate training through better utilization of parallel processing power and reduction of stochastic variance. Another popular technique is importance sampling -- a strategy for preferential sampling of more important examples also capable of accelerating the training process. However, despite considerable effort by the community in these areas, and due to the inherent technical difficulty of the problem, there is no existing work combining the power of importance sampling with the strength of minibatching. In this paper we propose the first {\em importance sampling for minibatches} and give simple and rigorous complexity analysis of its performance. We illustrate on synthetic problems that for training data of certain properties, our sampling can lead to several orders of magnitude improvement in training time. We then test the new sampling on several popular datasets, and show that the improvement can reach an order of magnitude.
1 Introduction
Large ERM problems make batch methods impractical, while stochastic methods trade cheap iterations for noise. Minibatching, importance sampling, and variance-reducing shifts offer complementary strategies for managing that noise and accelerating training.
1 Introduction
- Increasing training-data volumes make ERM computationally intensive, and batch methods that inspect all data before each update are described as prohibitively impractical.SGD instead updates from one random example, but its stochastic noise can halt progress after one or a few data passes.Source: §1 · pp. 1–2
1.1 Strategies for dealing with stochastic noise
- Decreasing stepsizes can ensure SGD converges to the ERM optimum, but slow iteration and yield sublinear convergence even for strongly convex objectives.The slowdown is the trade-off for directly scaling down the noise.Source: §1.1 · p. 2
- Minibatching reduces gradient-estimate variance, but increases computation; parallel processing can yield speedup without improving the convergence rate at fixed batch sizes.For sparse data, the leading-constant improvement can produce almost linear speedup.Source: §1.1 · p. 2
- Importance sampling uses data-driven selection probabilities to reduce stochastic-gradient variance, typically improving the complexity estimate's leading constant with negligible sampling overhead.The analysis often replaces a maximum of data-dependent quantities with their average.Source: §1.1 · p. 2
- Variance-reducing shifts modify the search direction through a cheaply maintained control variate; for strongly convex losses, these methods can achieve a fast linear rate.The paper distinguishes primal-space and dual-space approaches.Source: §1.1 · p. 2
1.2 Combining strategies
- Minibatching, importance sampling, and variance-reducing shifts are presented as orthogonal strategies that can be combined for an amplification effect.The paper cites minibatch and importance-sampling combinations with variance-reduced methods.Source: §1.2 · p. 3
2 Contributions
The paper addresses the unstudied combination of importance sampling and minibatches, whose design poses sampling and computational challenges. It introduces bucket samplings, analyzes them, and reports speedups on synthetic and real datasets.
2 Contributions
- No importance sampling for minibatches had been proposed or analyzed, in part because choosing subsets, assigning data-dependent probabilities, and sampling efficiently are difficult.The space of possible minibatches is large, making both subset selection and computationally practical sampling challenging.Source: §2 · p. 3
- The authors introduce bucket samplings and a particular member, importance sampling for minibatches, enabled by recent analysis of arbitrary sampling.They illustrate it with dfSDCA, while noting it can also combine with other stochastic ERM methods and extend beyond ERM.Source: §2 · p. 3
- Synthetic datasets show speedups of one or more orders of magnitude over standard uniform minibatching, while real-dataset speedups reach up to an order of magnitude.The authors predict larger-than-one-order speedups for real data with particular shapes and example-size distributions.Source: §2 · p. 3
3 The Problem
The paper formulates L2-regularized empirical risk minimization for linear prediction from example-label data. Its stated analysis assumes convex, smooth losses, while the sampling can be adapted to some nonsmooth settings.
3 The Problem
- The setup represents features as rows and examples as columns of a data matrix, and seeks a linear predictor for the example-label pairs.The labels form a vector corresponding to the examples.Source: §3 · p. 4
- The stated objective is L2-regularized empirical risk minimization with a loss function for each example-label pair and regularization parameter λ > 0.Square loss is given as one example of a loss function.Source: §3 · p. 4
- The analysis assumes convex, 1/γ-smooth loss functions, though the results are not limited to L2 regularization and allow an arbitrary strongly convex regularizer.The paper also says the sampling can be adapted to nonsmooth losses such as hinge loss.Source: §3 · p. 4
4 The Algorithm
The paper illustrates its sampling with dfSDCA, which samples example subsets and updates dual variables and the predictor using variance-reduction shifts. Its complexity analysis relates convergence to the sampling and allowable stepsize.
4 The Algorithm
- dfSDCA is illustrated with the proposed sampling and updates selected examples' α variables before updating the predictor.Its sampling is a random subset of examples, and the α variables act as variance-reduction shifts.Source: §4 · pp. 4–5
- The sampling requires each example to have positive selection probability, and the stepsize must not exceed a theoretically allowable maximum or the method could diverge.That maximum depends on the data matrix and sampling.Source: §4 · pp. 4–5
- For single-example updates, the shifted stochastic gradient's variance progressively vanishes as α_i converges, so additional variance-control strategies are unnecessary in that case.The passage conditions this behavior on using a proper stepsize.Source: §4 · p. 5
4.1 Complexity of dfSDCA
- The complexity analysis assumes ESO parameters; for minibatches of size at most τ, one stated conservative choice is v_i = τ∥X:i∥².Under the theorem's smoothness and stepsize conditions, the potential decays exponentially to zero.Source: §4.1 · p. 5
5 Bucket Sampling
The section moves from standard importance sampling to bucket-based minibatches, defining a sampling family and deriving bucket-specific parameters. It also compares uniform bucket sampling with τ-nice sampling.
5.1 Standard importance sampling
- 10× faster at σ = 10, dfSDCA with importance sampling versus uniform sampling; the sampling probabilities are chosen to minimize complexity.The probabilities are proportional to v_i+nλγ.Source: §5.1 · p. 6
5.2 Uniform minibatch sampling
- Importance minibatching aims to replace a single-example maximum complexity term with an average; τ-nice sampling uniformly selects a τ-element subset of [n].For τ-nice sampling, the selection is uniform over all subsets of cardinality τ.Source: §5.2 · p. 6
5.3 Bucket sampling: definition
- Bucket sampling partitions the examples into τ nonempty sets and selects one example from each, forming a minibatch of size τ.Given the partition, the inclusion probabilities determine the sampling.Source: §5.3 · p. 7
5.4 Optimal bucket sampling
- The bucket-sampling parameters are difficult to optimize because the ESO parameters depend on inclusion probabilities; Theorem 3 provides parameters for this setting.The difficulty arises from the complicated dependence of the parameters on the probability vector.Source: §5.4 · p. 7
5.5 Uniform bucket sampling
- Uniform bucket sampling yields a dfSDCA complexity formula similar to τ-nice sampling; when τ = 1 or each feature occurs in one example, v_i = ||X:i||² for both.The comparison assumes equal-sized buckets and uniform within-bucket probabilities.Source: §5.5 · p. 8
6 Importance Minibatch Sampling
Importance minibatch sampling is formulated as an approximate solution to an optimization problem for bucket sampling, with uniform minibatch sampling as a feasible baseline. The section compares alternating optimization with a practical formula and describes when the latter can improve complexity over uniform sampling.
6 Importance Minibatch Sampling
- Importance minibatch sampling approximates the bucket-sampling optimization problem, for which uniform minibatch sampling is a feasible solution.The authors therefore expect the optimized sampling to improve on uniform sampling.Source: §6 · p. 8
6.1 Approach 1: alternating optimization
- The alternating strategy often converges experimentally to a pair (p*, v*) satisfying (13), and its complexity replaces a maximum over all elements with a maximum over group averages.The group-average maximum leads to speedup, other things equal; the complexity also depends on a v* different from v(τ-nice). Each iteration is costly because it requires a pass over all data, motivating a closed-form alternative found empirically to offer nearly optimal convergence rate.Source: §6.1 · pp. 8–9
6.2 Approach 2: practical formula
- The practical formula improves on uniform minibatch complexity when β_l is approximately 1 for all groups, because the maximum of group averages is better than the maximum over all elements.The authors say the difference can be very large, but provide no magnitude in these passages.Source: §6.2 · p. 9
7 Experiments
The experiments compare importance minibatch sampling with τ-nice sampling on artificial and real data. Importance sampling performs significantly better, with theory closely estimating observed speedups and larger gains on denser or extreme data.
7 Experiments
- The comparison measures optimality gap against effective data passes divided by τ, and evaluates τ-nice and τ-importance for τ values from 1 to 32.Empirical speedup is the ratio of horizontal-axis values when each method reaches precision 10^-10.Source: §7 · pp. 9–10
7.1 Artificial data
- Artificial experiments vary feature sparsity and example-norm distributions, using 10% or 80% nonzeros and dimensions of 1,000 or 10,000.The data use n = 50,000 examples; the norm distributions are summarized in Table 1 and shown as histograms in Figure 1.Source: §7.1 · p. 10, Table 1 · p. 10, Figure 1 · p. 11
7.3 Conclusion
- Across experiments, τ-importance significantly outperformed τ-nice; theory closely predicted observed speedup, which was higher on denser data and could reach several orders on extreme artificial datasets.The authors suggest practical speedup will likely be dramatic for data with large σ.Source: Table 2 · p. 10, Table 3 · p. 11, §7.3 · pp. 11–12
7.2 Real data
- Real-data experiments use several publicly available datasets, summarized in Table 4, and report theoretical and empirical speedup ratios in Table 5.The passage also points to experimental results in Figure 7.3.Source: §7.2 · p. 11, Table 4 · p. 12, Table 5 · p. 12
8 Proof of Theorem 3
The proof develops lemmas for bucket sampling before applying them to Theorem 3. Its argument uses probability-matrix properties and a prior result involving a largest normalized eigenvalue.
8.1 Three lemmas
- Lemma 4 characterizes bucket sampling through a probability matrix, with B marking pairs of examples that belong to the same bucket.The passage gives the matrix entries for equal indices, examples in different buckets, and the remaining case.Source: §8.1 · p. 15
8.2 Proof of Theorem 3
- Theorem 3's proof invokes Theorem 5.2 in [22] and uses the largest normalized eigenvalue of a symmetric matrix.The passage states that this supplies parameters for inequality (2).Source: §8.2 · p. 16