Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling

Abstract

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.

References in corpus (3)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Stochastic Optimization with Importance Sampling

Cited by in corpus (25)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Predictive Collective Variable Discovery with Deep Bayesian Models
• Advances in Variational Inference
• A Study of Gradient Variance in Deep Learning
• Determinantal Point Processes for Mini-Batch Diversification
• Stochastic Optimization with Bandit Sampling
• Stochastic Gradient Descent for Semilinear Elliptic Equations with Uncertainties
• Active Mini-Batch Sampling using Repulsive Point Processes
• Faster Learning by Reduction of Data Access Time
• Accelerating Minibatch Stochastic Gradient Descent using Typicality Sampling
• A Novel Stochastic Stratified Average Gradient Method: Convergence Rate and Its Complexity
• Distributed Computation for Marginal Likelihood based Model Choice
• On Sampling Strategies for Neural Network-based Collaborative Filtering
• Lsh-sampling Breaks the Computation Chicken-and-egg Loop in Adaptive Stochastic Gradient Estimation
• Reweighting Augmented Samples by Minimizing the Maximal Expected Loss
• Drill the Cork of Information Bottleneck by Inputting the Most Important Data
• Stochastic Gradient Made Stable: A Manifold Propagation Approach for Large-Scale Optimization
• Efficient posterior sampling for high-dimensional imbalanced logistic regression
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• Near Optimal Stratified Sampling
• Submodular Batch Selection for Training Deep Neural Networks
• Accelerating Stochastic Gradient Descent Using Antithetic Sampling
• Training Efficiency and Robustness in Deep Learning
• Uniform Sampling over Episode Difficulty
• Approximate Inference via Clustering