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.
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