Variance Reduction in Training Forecasting Models with Subgroup Sampling

Yucheng Lu, Youngsuk Park, Lifan Chen, Yuyang Wang, Christopher De Sa, Dean P. Foster

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.

Visualizing the relationship between time series patterns, gradient distribution, and stratification.

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.

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

Training and test loss curves comparing standard optimizers with their stratified counterparts (S-Adam, S-Adagrad) across different datasets and models.

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

BibTeX
@inproceedings{lu2021variance,
  author = {Yucheng Lu and Youngsuk Park and Lifan Chen and Yuyang Wang and Christopher De Sa and Dean P. Foster},
  title = {{Variance Reduction in Training Forecasting Models with Subgroup Sampling}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=GZMIdZ4rPo6},
}
Figure