TL;DR
Training large-scale forecasting models is often slowed down by the massive diversity (heterogeneity) of time series data, which creates "noisy" gradients for standard optimizers. This paper introduces SCott (Stochastic Stratified Control Variate Gradient Descent), an optimizer that uses stratified sampling and control variates to drastically reduce gradient variance. This approach leads to faster convergence and better performance on both synthetic and real-world datasets.
What Problem Does This Paper Address?
In modern forecasting, we often train a single global model (like a deep neural network) on thousands of different time series simultaneously. However, these series are rarely "well-behaved." They exhibit heterogeneity: a retail sales series looks nothing like a temperature series, and even a single series can change its behavior over time (a phenomenon called concept drift).
When we use standard stochastic optimizers like SGD or Adam, we pick a random "mini-batch" of data to estimate the direction (gradient) to update the model. Because the data is so diverse, these random samples often provide wildly different estimates. The authors provably show that for even a simple AutoRegressive (AR) model, this variance can become arbitrarily large, forcing the model to train much longer or use tiny, inefficient steps to avoid "getting lost" in the noise.
Methods
The authors propose a two-pronged approach to tackle this variance:
- Stratification: Instead of sampling uniformly from the entire dataset, they group similar data segments into "strata." For time series, they use a clever, low-cost trick: temporal hashing. They group data by timestamps (e.g., "Mondays at 8 AM" or "Winter months"). Since time series often have recurring patterns, segments in the same temporal stratum are much more homogeneous, leading to more stable gradient estimates.
- SCott Algorithm: Stratified sampling is accurate but computationally expensive if done at every step. SCott balances this by using a control variate framework (inspired by SVRG and SCSG).
- Outer Loop: Periodically performs a full stratified sample to create a "snapshot" gradient (an anchor).
- Inner Loop: Performs standard, fast mini-batch updates but "corrects" them using the difference between the current noisy gradient and the high-quality anchor.
This allows the optimizer to enjoy the variance-reduction benefits of stratification without the massive overhead of sampling every stratum in every iteration.
Datasets
The researchers evaluated SCott across several benchmarks:
- Synthetic Datasets: Data generated from Vector AutoRegressive (VAR) and LSTM processes where the "ground truth" for stratification was known.
- Real-World Datasets:
- Traffic: Hourly road occupancy rates from San Francisco bay area freeways.
- Exchange-Rate: Daily exchange rates for eight foreign countries.
- Electricity: Hourly electricity consumption for 321 clients.
- Models: They tested SCott on standard Multi-Layer Perceptrons (MLP) and the state-of-the-art N-BEATS architecture.
Key Insights and Ideas
- The "Zero-Respecting" Proof: The authors provide a theoretical lower bound proving that for any "zero-respecting" optimizer (a category including SGD, Adam, and Adagrad), the number of iterations needed to converge is directly tied to the gradient variance—which, in forecasting, is often massive.
- Simple Hashing is Powerful: You don't need complex, high-dimensional clustering to find "similar" data. Simple temporal features (day of week, season) are highly effective proxies for gradient similarity in time series.
- Compatibility: SCott isn't just for SGD. The authors successfully created "S-Adam" and "S-Adagrad" variants, showing that the stratified control variate principle can enhance the most popular adaptive optimizers used in deep learning today.
Key Results
- Faster Convergence: SCott consistently converged faster than SGD, Adam, and Adagrad in terms of both the number of iterations and actual "wall-clock" time.
- Better Generalization: On the Electricity dataset using N-BEATS, SCott achieved significantly lower test error (MAPE) compared to standard Adam within the same time budget.
- Stability with Large Learning Rates: Because SCott reduces noise, it allows practitioners to use larger learning rates that would normally cause standard SGD to diverge or become unstable.
- Variance Reduction: Empirical plots show that the "Subgroup Sampling" used in SCott produces a much tighter distribution of gradients compared to standard random sampling.
Limitations and Future Work
- Stepsize Selection: While SCott is faster, it still requires tuning the learning rate. The authors suggest that developing automated, practical stepsize selection for SCott is a key next step.
- Stratification Heuristics: The current work relies on manual temporal hashing. Future work could explore automated ways to learn the optimal strata during the training process itself.
- Beyond Forecasting: While the focus here is time series, the authors note that the principle of stratified control variates could potentially be applied to other heterogeneous data domains, such as multi-task learning or recommendation systems.
Summary updated