Stochastic Optimization with Importance Sampling for Regularized Loss Minimization

By Peilin Zhao, T. Zhang. 2014

390 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

On Sampling Strategies for Neural Network-based Collaborative Filtering (2017, background): “Several sampling techniques, such as stratified sampling [35] and importance sampling [36] are proposed to achieve the variance reduction.”
Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “This is the approach proposed by Zhao and Zhang (2015) (Importance Sampling, left term below) and generalized by Csiba et al. (2015) (Residual sampling, a.k.a. AdaSDCA for binary classiﬁcation, right term): These sampling schemes somehow allow to maximize the second term of (22).”
Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “The non-uniform sampling techniques used in the work of Nesterov (2012); Needell et al. (2014); Zhao & Zhang (2015) use Lipschitz constants of partial derivatives to obtain the sampling probabilities.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “…upper bound is composed of a “bias” term that depends on the initial condition, and a “variance” term that involves either an upper bound on the norm of the noisy gradient (in the non-smooth case), or an upper bound on the variance of the noisy gradient in the smooth case (Zhao and Zhang, 2015).”
Local SGD Converges Fast and Communicates Little (2018, background): “For carefully chosen stepsizes ηt, SGD converges at rate O ( σ(2) T ) 5 on strongly convex and smooth functions f , where σ(2) ≥ E‖∇fikt (x k t )−∇f(xt )‖(2) for t > 0, k ∈ [K] is an upper bound on the variance, see for instance [50].”
Sparsified SGD with Memory (2018, methodology): “For carefully chosen stepsizes ηt this algorithm converges at rate O ( σ(2) t ) on strongly convex and smooth functions f , where σ(2) is an upper bound on the variance, see for instance [46].”
An Empirical Study of Example Forgetting during Deep Neural Network Learning (2018, background): “Zhao & Zhang (2015); Katharopoulos & Fleuret (2018) relate sample importance to the norm of its loss gradient with respect to the parameters of the network.”
Sampling Matters in Deep Embedding Learning (2017, background): “Sampling has been studied for stochastic optimization [43] with the goal of accelerating convergence to the same global loss function.”
Coupling Adaptive Batch Sizes with Learning Rates (2016, background): “We note that another recent line of work on non-uniform sampling of training samples with the goal of variance reduction (including, but not limited to, [18, 27, 24, 4]) is orthogonal to our work, since it is concerned with the composition of batches rather than their size.”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “This method is, in fact, a non-standard application of SGD to our problem, and can be seen as an instance of SGD with non-uniform sampling applied to the problem of minimizing the sum of two convex functions (Zhao & Zhang, 2015; Gower et al., 2019): the average loss, and the penalty.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “[127] SGD O(Cgrad/ ) [196, 162] CD O(nκCpd log(1/ )) [129, 148] SDCA O((n+ κ)Cgrad log(1/ )) [163, 201, 143] SVRG/S2GD O ((nCgrad + κCgrad) log (1/ )) [80, 187, 89] S2CD O ((nCgrad + κ̂Cpd) log (1/ )) this work [84]”
ActiveClean: Interactive Data Cleaning While Learning Convex Loss Models (2016, background): “The convergence rates of SGD are also well analyzed [11, 8, 39].”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, background): “importance sampling (Zhao and Zhang, 2015; Needell et al., 2015), and mini-batching (Konečný et al.”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, methodology): “As each component function fi(·) may have different degrees of smoothness, to select the random index ik from a non-uniform distribution is a much better choice than simple uniform random sampling [4], as well as without-replacement sampling vs.”
Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization (2014, methodology): “Non-uniform sampling schemes similar to the one used in Algorithm 3 have been studied for both stochastic gradient and dual coordinate ascent methods (e.g., Needell et al., 2016; Xiao and Zhang, 2014; Zhao and Zhang, 2015; Qu et al., 2015).”
Data-Dependent Stability of Stochastic Gradient Descent (2017, methodology): “So far we have presented bounds that have data-dependent components, however the step size cannot be adjusted depending on the data, e.g. as in (Zhao and Zhang, 2015).”
Training Deep Models Faster with Robust, Approximate Importance Sampling (2018, methodology): “This first change is not new—see [1], for example.”