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

Wei Xu, Wei Xu 0017arXiv 2011 · arXiv

Introduction

In the era of "Big Data," the ideal learning algorithm is one that can achieve optimal model parameters by processing each data point exactly once—a paradigm known as one-pass learning. Standard Stochastic Gradient Descent (SGD) is the primary tool for this task, yet its performance is highly sensitive to the choice of learning rate.

Averaged SGD (ASGD), which maintains a running average of the parameters visited during training, is theoretically superior. It is known to converge asymptotically at rates comparable to complex second-order methods. However, practitioners often find that ASGD requires a prohibitively large number of samples to reach this optimal performance region. This paper investigates the causes of this "warm-up" lag and proposes a specific learning rate schedule that allows ASGD to become a practical, high-performance tool for large-scale linear classification and regression.

Finite Sample Analysis and Learning Rate Scheduling

The core contribution of this work is a finite-sample analysis of ASGD, moving beyond asymptotic behavior to understand performance after a specific number of steps. The analysis reveals that the choice of learning rate significantly impacts the duration of the initial noisy period before averaging benefits take hold.

The authors propose a new learning rate schedule: $$\gamma_t = \gamma_0(1 + a\gamma_0t)^{-c}$$ Where:

  • $\gamma_0$ is the initial learning rate.
  • $a$ and $c$ are constants.

For quadratic losses (like linear regression), the optimal power is found to be $c = 2/3$, while for non-quadratic losses (like logistic regression), $c = 3/4$ is recommended. Crucially, the parameter $a$ should be set based on the curvature (the smallest eigenvalue of the Hessian) of the cost function to minimize the warm-up period.

Sparse ASGD Implementation

Updating a running average typically requires modifying every parameter at every step, which is inefficient for high-dimensional sparse data. The paper introduces Sparse ASGD, which uses a variable transformation to update the average only for non-zero features present in a given sample. This ensures that ASGD maintains the $O(d)$ per-iteration efficiency of standard SGD.

Experimental Evaluation and Key Results

The proposed approach was evaluated on synthetic data and several large-scale public benchmarks, including RCV1, MNIST, and the Pascal Large Scale Challenge suite.

Comparison of excess risk across different algorithms. ASGD with a proper schedule (ASGD) significantly outperforms SGD and reaches the optimal region much faster than ASGD with a poor schedule (ASGD_BAD).

As illustrated in Figure 1, the choice of schedule is critical. While an improperly tuned ASGD (ASGD_BAD) can take hundreds of thousands of samples to reach the optimal region, the proposed schedule allows ASGD to converge in just a few thousand samples. On real-world datasets, ASGD achieved lower test error in a single pass than popular alternatives like LIBLINEAR, Pegasos, and SGDQN.

Key Insights and Robustness

  • Curvature Matters: The parameter $a$ in the learning rate is not just a tuning knob; it should reflect the cost function's curvature ($\lambda_0$).
  • Delayed Averaging: Performance can be further improved by discarding the initial noisy training period and only starting the ASGD averaging once the model has stabilized.
  • Stability: Unlike volatile methods like oLBFGS, ASGD’s averaging mechanism provides significant robustness to noise, leading to smoother convergence and more reliable test performance.

Conclusion

ASGD, when paired with an appropriate learning rate schedule, offers a robust and efficient solution for one-pass large-scale learning. While this work focuses on smooth linear models, extending these principles to non-smooth losses and non-convex architectures like deep neural networks remains a promising direction for future research.

Summary updated

Abstract

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.
BibTeX
@misc{xu2011towards,
  author = {Wei Xu and Wei Xu},
  title = {{Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent}},
  year = {2011},
  eprint = {1107.2490},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1107.2490},
}
Figure