PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent

Wei Xu

arXiv:1107.2490v2cs.LG

TL;DR

ASGD can require prohibitively many samples to reach its asymptotic region when its learning rate is chosen arbitrarily. The paper develops non-asymptotic guidance for setting the learning rate and shows that properly tuned ASGD outperforms SGD once enough data are available.

  • Problem

    ASGD’s favorable asymptotic convergence does not specify how much data it needs to reach that regime, and arbitrary learning rates can make this requirement prohibitively large.

  • Method

    The paper provides finite-sample analysis of ASGD and selects learning-rate parameters according to the curvature of the expected cost function.

  • Results

    With the proposed learning-rate recipe, ASGD outperforms SGD when the data size is large enough for SGD to reach its asymptotic region.

  • Takeaways & Limitations

    A simple, curvature-informed learning-rate schedule makes ASGD effective for large-scale learning while retaining its implementation simplicity.

  • Takeaways & Limitations

    The stochastic-linear analysis assumes a positive-definite matrix and martingale-difference noise process.

Abstract

from arXiv · show

For large scale learning problems, it is desirable if we can obtain the optimal model parameters by going through the data in only one pass. Polyak and Juditsky (1992) showed that asymptotically the test performance of the simple average of the parameters obtained by stochastic gradient descent (SGD) is as good as that of the parameters which minimize the empirical cost. However, to our knowledge, despite its optimal asymptotic convergence rate, averaged SGD (ASGD) received little attention in recent research on large scale learning. One possible reason is that it may take a prohibitively large number of training samples for ASGD to reach its asymptotic region for most real problems. In this paper, we present a finite sample analysis for the method of Polyak and Juditsky (1992). Our analysis shows that it indeed usually takes a huge number of samples for ASGD to reach its asymptotic region for improperly chosen learning rate. More importantly, based on our analysis, we propose a simple way to properly set learning rate so that it takes a reasonable amount of data for ASGD to reach its asymptotic region. We compare ASGD using our proposed learning rate with other well known algorithms for training large scale linear classifiers. The experiments clearly show the superiority of ASGD.

1. Introduction

Large-scale learning motivates one-pass methods such as SGD and ASGD, whose asymptotic benefits depend on learning-rate choices and may require substantial data to materialize. The paper develops finite-sample guidance for setting ASGD’s schedule and evaluates it against established large-scale solvers.

  • Motivation: Large-scale optimization is difficult because classical methods repeatedly process millions or billions of training samples, whereas SGD uses stochastic gradients for scalable learning.The empirical objective may require full-data passes even to evaluate once, while SGD updates from individual samples.
  • Limitations of prior analyses: Existing second-order analyses are mostly asymptotic, while approximating the curvature matrix H sacrifices guaranteed optimal convergence and full-matrix maintenance is expensive in high dimensions.The paper emphasizes that asymptotic analyses do not specify how much data is needed to reach the asymptotic region.
  • Averaged SGD: ASGD averages SGD parameters and can asymptotically match the performance of full second-order SGD and the empirical optimum after enough training samples.Its running average is used as the estimator for the optimal parameter, while retaining a simple one-pass implementation.
  • Learning-rate challenge: Arbitrarily chosen learning rates can make ASGD require a prohibitively large amount of data to reach its asymptotic regime.This delayed realization of ASGD’s convergence is identified as a possible reason for its limited attention in large-scale learning.
  • Results: With the proposed learning-rate recipe, ASGD outperforms SGD once the data size is large enough for SGD to reach its asymptotic region, and experiments report an advantage over prominent large-scale solvers.The evaluation covers linear classification and regression models on synthetic, real, and benchmark tasks.

2. Stochastic Linear Equation

The section linearizes stochastic-gradient behavior around the optimum and analyzes averaged iterates under martingale noise. It characterizes when averaged SGD reaches its optimal asymptotic regime and how the learning-rate offset affects that transition.

  • Stochastic approximation: The SGD gradient is decomposed into a linear component, noise at the optimum, state-dependent noise, and linearization error.The analysis then focuses on a stochastic approximation procedure that ignores the state-dependent and linearization-error terms.
  • Stochastic approximation: The stochastic approximation uses a positive definite matrix A, martingale-difference noise ξ_t, and covariance S to find the root θ∗ of Aθ = b.The smallest and largest eigenvalues of A are λ0 and λ1, respectively.
  • Convergence analysis: Under γ0λ1 ≤ 1 and (2c − 1)a < λ0, Theorem 1 provides a convergence bound for the averaged estimator ¯θ_t.The bound yields the best possible asymptotic convergence rate, consistent with Polyak and Juditsky (1992).
  • Convergence analysis: Choosing a = λ0 requires t = O((λ0γ0)^−1) samples for ¯θ_t to reach its asymptotic region, after which it begins to outperform θ_t.Both averaged and non-averaged iterates require this sample scale under the stated comparison.
  • Learning-rate choice: The learning-rate offset a should be limited: a = 0 is appropriate for the linear problem, while the general update requires a constant factor times λ0.An arbitrary value such as 1 can substantially delay asymptotic convergence when λ0 is very small.

3. Regression Problem

The regression analysis identifies when ASGD overtakes standard SGD and derives learning-rate settings for reaching its asymptotic regime with fewer samples. For linear regression, the recommended schedule uses γ0 = 1/M, a = λ0, and c = 2/3.

  • Analysis assumptions: The analysis assumes conditions linking continuity and data distributions with the convergence of standard SGD.Under these assumptions, the paper derives the stated asymptotic convergence result for quadratic loss.
  • Asymptotic behavior: ASGD begins to outperform SGD after t > O((λ0γ0)−1).
  • Scope: The regression conclusion also extends to normally distributed y, independently distributed dimensions of y, and L2 regularization.
  • Learning-rate choice: For linear regression, the proposed learning-rate parameters are γ0 = 1/M, a = λ0, and c = 2/3.These values are proposed specifically for calculating the learning rate in the linear regression setting.

4. Non-quadratic loss

For non-quadratic loss, the analysis adds assumptions for the loss-noise contribution and finds a different optimal averaging exponent. The best convergence rate is obtained with c = 3/4 rather than the quadratic-loss setting’s c = 2/3.

  • Assumptions: For non-quadratic loss, the analysis requires two additional assumptions concerning continuity, data distributions, and standard SGD convergence.The assumptions are motivated by properties of g(θ, d), the distributions of x and y, and asymptotic normality of θt.
  • Convergence rate: The best convergence rate for non-quadratic loss is obtained when c = 3/4.

5. Implementation

The implementation maintains the ASGD running average while exploiting sparse feature updates to reduce per-sample computation. It also discusses initialization and a possible adaptive point for beginning averaging.

  • Running average: The running average is recursively updated, but directly averaging θt can be costly when θt is dense on sparse datasets.The paper therefore develops an alternative averaging procedure that exploits sparse inputs.
  • Running average: The parameter update and running-average update are θt = (1 − λγt)θt−1 − γtgt and ¯θt = (1 − ηt)¯θt−1 + ηtθt.
  • Sparse updates: When xt is sparse, gt is sparse, enabling updates that take advantage of the input sparsity.
  • Sparse updates: The efficient averaging algorithm maintains auxiliary variables and recovers ¯θt from ¯ut at each step.The procedure is presented as an efficient algorithm for updating the averaged parameter.
  • Computational cost: The number of operations per sample is O(Z), where Z is the number of non-zero elements in x.The algorithm avoids operations involving two dense vectors.
  • Averaging start: A moving average can identify when averaging becomes beneficial by comparing its empirical loss with that of θt.The described procedure uses ˆθt = 0.99ˆθt−1 + 0.01θt during the initial period.

6. Experiments

The experiments examine learning-rate scheduling, asymptotic convergence, and benchmark performance. ASGD reaches strong performance quickly and generally outperforms the compared large-scale learning methods.

  • The experiments evaluate learning-rate scheduling, asymptotic convergence, and large-scale linear-model performance.The study uses synthetic problems, regression, and benchmark datasets.
  • 6.1 Effect of learning rate scheduling: A proposed learning-rate schedule reaches the ASGD asymptotic region after only a few thousand examples, compared with hundreds of thousands for an arbitrary schedule.The arbitrary schedule eventually outperforms SGD and approaches the batch method, but converges much later.
  • 6.2 Asymptotic optimal convergence: After about 10^4 examples, ASGD approaches batch-solution accuracy while SGD remains more than 10 times worse.ASGD uses O(N) computation per sample, compared with O(N^2) for the batch method.
  • 6.3 Experiments on benchmark data sets: Across most benchmark datasets, ASGD clearly outperforms the other five algorithms in accuracy and often reaches good performance after one data pass.Its one-pass time is similar to the other methods except oLBFGS, while the beta dataset is an exception because its classes are not linearly separable.
  • 6.3 Experiments on benchmark data sets: ASGD performance is more robust than the other methods and also works well with the non-smooth hinge loss.The paper notes that the current ASGD theory assumes a smooth cost function.

7. Conclusion

ASGD is easy to implement and, with the proposed learning-rate schedule, performs better than more complicated algorithms for large-scale learning. The paper applies it to convex-loss linear models and identifies more complex models as a direction for future work.

  • With the proposed learning-rate schedule, ASGD performs better than more complicated algorithms on synthetic and real datasets.The paper describes ASGD as relatively easy to implement.
  • The paper applies ASGD only to linear models with convex loss and a unique local optimum.Applying ASGD to more complicated models such as conditional random fields is left for future work.

Appendix A. Proofs

The appendix develops lemmas and algebraic bounds used to prove the paper’s main theorem, including conditions controlling averaged iterates and divergence of the error.

  • Supporting lemmas: A key lemma provides a bound for the averaged iterate under conditions on γ0λ1 and (2c −1)a relative to λ0.The stated conditions are γ0λ1 ≤1 and (2c −1)a < λ0.
  • Supporting lemmas: The proof derives intermediate inequalities using induction, mean-value arguments, and bounds on powers such as xc.These steps support the lemma bounds before they are substituted into the final claims.
  • Theorem 1: Theorem 1 is proved by combining the preceding lemma with equations and assumptions introduced earlier in the appendix.The proof explicitly invokes Lemma 11 and then derives the theorem from equations (5), (18), and (19).
  • Divergence condition: The expected squared error is stated to diverge when the learning-rate sequence satisfies γt ≥ 2 as the relevant product tends to zero.This conclusion is presented after taking expectations over the data variables and using Aθ∗ = b.
Loading 1107.2490v2…