Importance Sampling for Minibatches

Abstract

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.

References in corpus (8)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Proximal Stochastic Dual Coordinate Ascent
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• SDCA without Duality
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation

Cited by in corpus (14)

• Stochastic, Distributed and Federated Optimization for Machine Learning
• Advances in Variational Inference
• Coupling Adaptive Batch Sizes with Learning Rates
• Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
• Determinantal Point Processes for Mini-Batch Diversification
• Stochastic Optimization with Bandit Sampling
• Coordinate Descent Face-Off: Primal or Dual?
• Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches
• Online Variance Reduction for Stochastic Optimization
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• Label and Sample: Efficient Training of Vehicle Object Detector from Sparsely Labeled Data
• IS-ASGD: Accelerating Asynchronous SGD using Importance Sampling
• Safe Adaptive Importance Sampling
• Accelerate RNN-based Training with Importance Sampling