PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Optimization with Importance Sampling

Peilin Zhao, Tong Zhang

arXiv:1401.2753v2stat.MLcs.LG

TL;DR

Uniform sampling in prox-SGD and prox-SDCA is unbiased but can have high variance that harms convergence. The paper develops importance-sampling strategies for both methods and theoretically shows significant convergence improvements under suitable conditions, with experiments verifying the analysis.

  • Problem

    Uniform sampling can yield high-variance stochastic estimates in prox-SGD and prox-SDCA, negatively affecting convergence.

  • Method

    The paper uses importance sampling for prox-SGD to minimize gradient-estimator variance and for prox-SDCA to increase expected dual value during coordinate ascent.

  • Results

    Theoretical analyses show that proposed importance-sampling methods can significantly improve convergence rates for both prox-SGD and prox-SDCA under suitable conditions.

  • Takeaways & Limitations

    Sampling distributions based on gradient norms or loss smoothness and Lipschitz constants provide a variance-reduction approach applicable to both proximal stochastic methods.

  • Takeaways & Limitations

    The exact variance-minimizing prox-SGD distribution requires calculating n derivatives at each step, motivating practical upper-bound relaxations; explicit high-probability bounds are not provided.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies importance sampling for prox-SGD and prox-SDCA to reduce stochastic variance and improve convergence rates over uniform sampling under suitable conditions.

  • Uniform sampling can produce high-variance stochastic quantities, negatively affecting optimization convergence.
  • For prox-SGD, the paper proposes importance sampling and an unbiased gradient estimator designed to minimize stochastic-gradient variance.
  • The proposed prox-SGD distribution is roughly proportional to stochastic-gradient norms, with upper-bound relaxations considered for computational simplicity.
  • Theoretical analyses show significant convergence-rate improvements for both methods under suitable conditions, while recovering uniform-sampling results as special cases.
  • For prox-SDCA, importance sampling is designed through the relationship between sampling probabilities and expected dual-objective increase.

2 Related Work

Prior work largely studied uniform sampling, while this paper extends importance-sampling analysis to prox-SGD and prox-SDCA and distinguishes its scope from related methods.

  • Existing prox-SGD research established finite-sample convergence rates, including O(1/T) for convex losses after later averaging strategies.
  • Prior prox-SDCA analyses reported O(1/T) rates for Lipschitz losses and O(exp(−O(T))) linear rates for smooth losses.
  • Most existing work used uniform sampling throughout learning, motivating importance-sampling analysis for stochastic optimization.
  • The paper generalizes related importance-sampling work through stochastic mirror descent and additionally studies prox-SDCA with importance sampling.
  • Its basic stochastic-gradient analysis has worse convergence rates than SAG and SVRG for smooth strongly convex objectives.
  • Existing non-uniform coordinate-descent results cannot be directly applied to proximal SDCA because their analyses and sampling distributions differ.

3 Preliminaries

The preliminaries define convexity, smoothness, Lipschitzness, Bregman divergence, and dual norms used to analyze the optimization methods.

  • Strong convexity is defined relative to a norm through a lower bound on function curvature.
  • Lipschitzness bounds function-value changes relative to distances measured by a norm.
  • Smoothness is defined through differentiability and a Lipschitz gradient, equivalently through a first-order upper bound.
  • Smoothness of a function implies strong convexity of its dual function, and dual norms pair p and q with 1/q + 1/p = 1.
  • The Bregman divergence measures the gap between a function value and its first-order Taylor approximation around a reference point.
  • A σ-strongly convex reference function yields a Bregman-divergence lower bound involving σ and the norm distance.

4 Stochastic Optimization with Importance Sampling

The paper formulates importance sampling for prox-SGD and prox-SDCA to reduce stochastic variance or improve expected dual progress, and derives convergence guarantees under stated smoothness, convexity, and Lipschitz conditions.

  • The optimization problem minimizes a regularized empirical loss, with applications including SVM, ridge regression, and lasso.
  • Uniform prox-SGD uses one randomly selected example per iteration, producing an unbiased gradient estimate but potentially high variance across examples.
  • Importance-sampled prox-SGD selects examples from a probability distribution and applies an unbiased importance-weighted gradient estimator designed to minimize variance.
  • Theoretical results establish convergence bounds for importance-sampled prox-SGD under strongly convex, convex, smooth, and regularized settings, with improvements especially when gradient-related quantities are much smaller than n.
  • For prox-SDCA, the method samples dual coordinates according to probabilities chosen to accelerate convergence, with analyses covering smooth and Lipschitz losses.

5 Applications

The applications section instantiates the proposed methods as stochastic gradient descent by choosing a quadratic regularizer.

  • The applications set ψ(w) = 1/2∥w∥2^2, making stochastic mirror descent equivalent to stochastic gradient descent.

5.1 Hinge Loss Based SVM with ℓ2 Regularization

This section applies importance-sampled proximal methods to hinge-loss SVM with ℓ2 regularization, using bounded iterates and data-dependent gradient information.

  • The application considers a Support Vector Machine formulated with hinge loss.
  • Assuming X = maxi ∥xi∥2 is not too large, the proposed proximal SGD and proximal SDCA importance-sampling methods can solve the problem.The text gives short-document bag-of-words representations as an example setting.
  • The optimal SVM solution satisfies ∥w∗∥2 ≤ 1/λ, enabling projection of iterates onto the Euclidean ball of radius 1/λ.The theoretical analysis remains valid after this projection.
  • For hinge loss, the loss is ∥xi∥2-Lipschitz, and the analysis determines an importance-sampling distribution from the example norms.
  • The dual function is used with θi = αiyixi to obtain a closed-form update for option I.

5.2 Squared Hinge Loss Based SVM with ℓ2 Regularization

This section applies importance-sampled proximal methods to squared hinge-loss SVM with ℓ2 regularization and derives the corresponding sampling and update forms.

  • The application studies squared hinge-loss Support Vector Machine optimization with ℓ2 regularization.
  • The optimal solution obeys ∥w∗∥2 ≤ 1/λ, so iterates can be projected onto the Euclidean ball of radius 1/λ without invalidating the analysis.
  • For squared hinge loss, the analysis specifies an optimal importance-sampling distribution for the proximal SGD setting.
  • The squared hinge loss is (2∥xi∥2)-smooth with respect to the Euclidean norm, yielding an optimal distribution for proximal SDCA with importance sampling.
  • Using R = supu≠0 ∥u∥D′/∥u∥D = 1, the proximal SDCA update admits a closed-form solution for option I.

5.3 Squared Hinge Loss Based SVM with ℓ1 Regularization

This section applies importance-sampled proximal methods to squared hinge-loss SVM with ℓ1 regularization, emphasizing sparsity and deriving projection, sampling, and update properties.

  • The application studies squared hinge-loss Support Vector Machine optimization with ℓ1 regularization.
  • ℓ1 regularization makes the optimal model sparse, which can alleviate the curse of dimensionality and improve interpretability.
  • The optimal solution satisfies ∥w∗∥2 ≤ ∥w∗∥1 ≤ 1/λ, allowing Euclidean projection onto the ball of radius 1/λ while preserving the analysis.
  • The ℓ1 regularizer determines the proximal mapping used by the method.
  • The gradient bound determines the importance-sampling distribution for proximal SGD in this application.The bound is ∇φi(w) ≤ 2(1 + ∥xi∥2/λ)∥xi∥2.
  • An ϵ/2-approximate solution of the auxiliary problem implies an ϵ-approximate solution of the original optimization problem.
  • The analysis also specifies an optimal proximal SDCA importance-sampling distribution and a closed-form option-I update for this setting.

6 Experimental Results

The experiments compare importance-sampled and uniformly sampled prox-SGD and prox-SDCA on several real-world datasets, measuring optimization, generalization, and stochastic-gradient variance. Importance sampling improves SGD most on the last two datasets and accelerates duality-gap minimization across all datasets.

  • Experimental setup: The experiments compare Iprox-SGD with Pegasos and Iprox-SDCA with SDCA on squared-hinge-loss SVMs with ℓ2 regularization.All algorithms use the same experimental setup, including dataset-specific regularization parameters and prescribed step sizes for prox-SGD variants.
  • Theoretical predictions: Importance sampling is predicted to be effective for SGD on kdd2010 and w8a but not very effective for ijcnn1.The same theoretical ratios predict faster duality-gap minimization for importance sampling on all datasets.
  • Evaluation measures: Performance is evaluated using primal objective values, duality gaps, test error rates, and stochastic-gradient variances over learning.Results are averaged over five random seeds for each dataset.
  • Iprox-SGD results: On the last two datasets, Iprox-SGD achieves the fastest primal-objective convergence, significantly lower test error, and much smaller stochastic-gradient variance than SGD.The algorithms use the same learning rates, while the first dataset shows comparable convergence rates.
  • Iprox-SDCA results: Across all datasets, Iprox-SDCA converges much faster in duality gap than standard SDCA, while test error remains comparable.Its stochastic-gradient variance is only slightly smaller, which is not accompanied by a significant test-error reduction.

7 Conclusion

The paper develops importance-sampling strategies for prox-SGD and prox-SDCA to reduce variance and improve convergence under suitable conditions. Its theoretical analysis identifies sampling distributions based on gradient norms or loss-function smoothness or Lipschitz constants, and experiments confirm the analysis.

  • The paper studies importance sampling for Proximal Stochastic Gradient Descent and Proximal Stochastic Dual Coordinate Ascent to reduce stochastic variance.
  • For prox-SGD, variance reduction uses distributions based on loss-gradient norms, or relaxed versions based on smooth or Lipschitz constants.
  • For prox-SDCA, the sampling distribution relies on the smooth or Lipschitz constants of all loss functions.
  • Under suitable conditions, both proposed importance-sampling methods significantly improve optimization convergence rates over uniformly sampled prox-SGD and prox-SDCA.Experiments are reported to confirm the theoretical analysis.

Appendix

The appendix develops a proof using Bregman divergence, optimality conditions, monotonicity of a convex subdifferential, strong convexity, and Cauchy–Schwarz to establish the stated lemma.

  • Lemma 3 assumes a convex function r and a function ψ that is σ-strongly convex with respect to the norm.
  • The proof begins from the definition of Bregman divergence and the optimality of b_u.
  • Convexity of ηλr(w) makes its subdifferential monotone, yielding the key inequality used in the proof.
  • Strong convexity of ψ and the Cauchy–Schwarz inequality are then used to rearrange and bound the inequality.
  • Dividing by σ∥b_u − b_v∥ completes the proof.
Loading 1401.2753v2…