Training deep learning models for large-scale time series forecasting is a computationally intensive task. Whether predicting urban traffic flow or household electricity demand, the underlying data is often "heterogeneous"—patterns vary significantly across different locations and evolve over time. Researchers from Amazon and Cornell University have identified that this heterogeneity leads to high gradient estimation variance, which significantly slows down training. To address this, they introduced SCott, a novel optimizer that leverages stratified sampling to accelerate convergence.
The Challenge of Heterogeneity
Standard stochastic optimizers like SGD and Adam rely on random mini-batches to estimate the gradient of the entire dataset. In forecasting, however, data often suffers from concept drift and local effects. These diverse patterns mean that a small, random sample is frequently a poor representation of the global dataset, leading to noisy gradient estimates.
As shown in the figure above, the complex patterns in a time series (a) result in a wide, high-variance distribution of gradients (b). This noise forces the use of smaller learning rates and results in longer training times. The proposed solution is to group the data into "strata" (c) that are internally more homogeneous, allowing for more accurate gradient estimation.
The SCott Optimizer
The core of the proposed solution is SCott (Stochastic Stratified Control Variate Gradient Descent). SCott combines stratified sampling with a control variate approach to reduce variance without the prohibitive cost of full-dataset stratification at every step.
- Efficient Stratification: Instead of complex clustering, the authors use simple "hashing" based on timestamps (e.g., grouping by hour of day or day of week). This captures recurring temporal patterns at almost zero computational cost.
- Control Variate Framework: SCott operates with an outer and inner loop. Periodically, the outer loop computes a high-quality "anchor" gradient using a full stratified sample. The inner loop then uses cheap mini-batch gradients but adjusts them using the anchor to maintain accuracy and low variance.
This framework is flexible and can be integrated into existing popular optimizers, resulting in variants like S-Adam and S-Adagrad.
Key Results
The researchers evaluated SCott across several real-world scenarios, including traffic occupancy rates and electricity consumption. The experimental results demonstrate that stratified sampling consistently leads to faster convergence and better model performance under fixed time budgets.
As illustrated in the loss curves, the stratified versions (S-Adam and S-Adagrad) reach lower loss levels significantly faster than their standard counterparts. For instance, on the Traffic dataset using an MLP and the Electricity dataset using N-BEATS, the stratified optimizers show a clear advantage in both training and test loss over time. This "plug-and-play" benefit suggests that stratified variance reduction is a robust technique applicable across various model architectures and optimizer families.
Conclusion
By identifying gradient variance as a primary bottleneck in training forecasting models, the authors provide a principled way to speed up deep learning for time series. SCott demonstrates that simple, metadata-driven stratification can drastically reduce noise and accelerate training, making large-scale forecasting more efficient and accessible.
Summary updated