Stochastic Optimization with Importance Sampling

Abstract

Uniform sampling of training data has been commonly used in traditional stochastic optimization algorithms such as Proximal Stochastic Gradient Descent (prox-SGD) and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA). Although uniform sampling can guarantee that the sampled stochastic quantity is an unbiased estimate of the corresponding true quantity, the resulting estimator may have a rather high variance, which negatively affects the convergence of the underlying optimization procedure. In this paper we study stochastic optimization with importance sampling, which improves the convergence rate by reducing the stochastic variance. Specifically, we study prox-SGD (actually, stochastic mirror descent) with importance sampling and prox-SDCA with importance sampling. For prox-SGD, instead of adopting uniform sampling throughout the training process, the proposed algorithm employs importance sampling to minimize the variance of the stochastic gradient. For prox-SDCA, the proposed importance sampling scheme aims to achieve higher expected dual value at each dual coordinate ascent step. We provide extensive theoretical analysis to show that the convergence rates with the proposed importance sampling methods can be significantly improved under suitable conditions both for prox-SGD and for prox-SDCA. Experiments are provided to verify the theoretical analysis.

29 pages

References in corpus (4)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Proximal Stochastic Dual Coordinate Ascent
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction

Cited by in corpus (29)

• Online Batch Selection for Faster Training of Neural Networks
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling
• Stochastic Dual Ascent for Solving Linear Systems
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Minimizing the Maximal Loss: How and Why?
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Efficient Per-Example Gradient Computations
• Importance Sampling for Minibatches
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
• Block-proximal methods with spatially adapted acceleration
• Distributed ADMM with Synergetic Communication and Computation
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Stochastic Optimization with Bandit Sampling
• Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions
• Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization
• Accelerating Optimization via Adaptive Prediction
• Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport
• SAGA with Arbitrary Sampling
• Reducing Runtime by Recycling Samples
• Stochastic Gradient Made Stable: A Manifold Propagation Approach for Large-Scale Optimization
• Dual Free Adaptive Mini-batch SDCA for Empirical Risk Minimization
• Greedy methods, randomization approaches and multi-arm bandit algorithms for efficient sparsity-constrained optimization
• A Fast Sampling Gradient Tree Boosting Framework
• Which Samples Should be Learned First: Easy or Hard?