TL;DR
This paper introduces the first practical method for combining importance sampling with minibatching for faster training of supervised learning models. By intelligently selecting which minibatches to process, their approach can achieve speedups of several orders of magnitude on synthetic data and up to an order of magnitude on real-world datasets, particularly when data exhibits certain properties.
What Problem Does This Paper Address?
Training modern supervised learning models, especially deep neural networks, often involves massive datasets. Empirical Risk Minimization (ERM) is the standard approach, but it can be computationally prohibitive for large datasets. Two common strategies to accelerate ERM are:
- Minibatching: Using small random subsets of data (minibatches) to estimate gradients, which improves computational efficiency by better utilizing parallel hardware and reducing variance.
- Importance Sampling: Strategically selecting data points with higher probability based on their "importance" to reduce variance and accelerate convergence.
Despite the individual success of these techniques, combining them has been a significant challenge due to the inherent technical difficulties in selecting important minibatches. This paper aims to bridge this gap by proposing and analyzing a practical method for importance sampling specifically designed for minibatches.
Methods
The core contribution is a novel family of sampling strategies called bucket samplings. The key idea is to partition the dataset into several "buckets" and then, in each iteration, select exactly one data point from each bucket to form a minibatch. This approach allows for non-uniform sampling within each bucket, enabling the focus on more "important" examples.
The paper then proposes two practical approaches for determining these sampling probabilities:
- Alternating Optimization: An iterative method that alternates between optimizing the sampling probabilities and the importance weights, converging to a good solution.
- Practical Formula (Approach 2): A closed-form solution derived from the alternating optimization, which is computationally efficient and provides near-optimal results. This approach involves re-weighting probabilities based on pre-computed importance values, with a computational cost of at most one pass over the data.
The proposed sampling is demonstrated in conjunction with the dfSDCA (dual first-order Stochastic Dual Coordinate Ascent) algorithm, a variance-reduced method for ERM.
Datasets
The paper evaluates its proposed method on:
- Synthetic datasets: These datasets are generated with controlled sparsity patterns and distributions of example norms (||X:i||²). This allows for a precise analysis of how different data characteristics affect the performance of the sampling strategies.
- Real-world datasets: The paper uses several publicly available datasets, including:
- ijcnn1
- protein
- w8a
- url
- aloi
These datasets are split into training (80%) and testing (20%) sets.
Key Insights and Ideas
- The Synergy of Minibatching and Importance Sampling: The paper demonstrates that combining these two techniques is not only possible but can lead to substantial speedups, overcoming the limitations of using either method in isolation.
- Bucket Sampling as a Practical Solution: The proposed bucket sampling framework provides a structured and computationally feasible way to implement importance sampling for minibatches. It elegantly balances the need to sample from subsets with the desire to focus on important examples.
- Data Distribution Matters: The effectiveness of importance sampling for minibatches is highly dependent on the distribution of example "importance" (related to their norms ||X:i||²). Datasets with a few examples having significantly larger norms (e.g., "extreme" distributions) benefit the most, leading to dramatic speedups.
- Theoretical Predictions Align with Empirical Results: The theoretical analysis of the proposed sampling method provides a good estimate of the actual speedup observed in experiments, validating the underlying theory.
Key Results
- Synthetic Data: Importance sampling for minibatches can achieve several orders of magnitude improvement in training time on synthetic datasets with specific data distributions (e.g., "extreme" norm distributions).
- Real-world Data: The proposed method consistently outperforms standard uniform minibatching, achieving speedups of up to an order of magnitude on various real-world datasets.
- Denser Data Benefits More: The speedup is generally higher on denser datasets compared to sparse ones, aligning with theoretical predictions.
- Theoretical Speedup is a Good Predictor: The theoretical speedup factor calculated by the paper accurately predicts the empirical speedup observed.
Limitations and Future Work
- Partitioning Strategy: While random partitions are used in experiments and are shown to be effective, the paper notes that the optimal choice of partitions is a complex optimization problem. Finding the truly optimal partition could further enhance performance.
- Generalization Beyond ERM: The paper focuses on ERM but mentions that the proposed sampling can be adapted to general convex optimization problems. Exploring these extensions would be a natural next step.
- Non-smooth Losses: The current analysis assumes convex and smooth loss functions. Adapting the method to non-smooth losses (like the hinge loss) could broaden its applicability.
Summary updated