Multivariate Online Linear Regression for Hierarchical Forecasting

Massil Hihat, Guillaume Garrigos, Adeline Fermanian, Simon BussyarXiv 2024 · DOI · arXiv

Introduction

In time series analysis, predictions are rarely isolated. Most real-world data is organized into hierarchies, where granular predictions (e.g., sales of specific product items) must aggregate to match higher-level totals (e.g., total category sales). This paper introduces MultiVAW, a multivariate extension of the Vovk-Azoury-Warmuth algorithm, designed to provide optimal theoretical guarantees and practical coherence for sequential hierarchical forecasting.

The Hierarchical Forecasting Problem

Standard approaches to Online Hierarchical Forecasting (OHF) often struggle with "incoherence," where the sum of leaf-node forecasts does not equal the parent-node forecast. Traditional methods either fit separate univariate models—ignoring the structure—or apply a post-hoc reconciliation step to fix the totals.

Hierarchical structure and summing constraints.

As shown in the figure above, a hierarchy imposes strict summing constraints (e.g., $y_{t,1} = y_{t,2} + y_{t,3}$). The authors propose baking these constraints directly into the learning process by representing the hierarchy through a summing matrix $S$, ensuring that every prediction is coherent by design.

Methodology: The MultiVAW Algorithm

The core contribution, MultiVAW (Multivariate Vovk-Azoury-Warmuth), updates its parameters $\theta_t$ by minimizing a loss function composed of three critical elements:

  1. Past Losses: Performance on historical data.
  2. Predictive Loss: A "look-ahead" term using current features $X_t$ before the label $y_t$ is revealed. This is the defining feature of VAW-style algorithms.
  3. Time-Varying Regularization: A penalty term $\Lambda_t$ that allows the model to adapt as the hierarchy structure changes.

By incorporating the predictive term $\|X_t\theta\|^2$, MultiVAW achieves a logarithmic regret bound of $O(d \log T)$. This is a significant improvement over standard Online Convex Optimization (OCO) methods like Online Gradient Descent (OGD), which typically offer only sublinear regret ($O(\sqrt{T})$) in similar settings.

Experimental Results

The researchers evaluated MultiVAW-OHF on two benchmark datasets: the M5 Dataset (Walmart sales) and the Labour Dataset (Australian employment data).

Comparative performance across M5 and Labour datasets.

As illustrated in the performance plots, MultiVAW-OHF and its specialized variant, MetaVAW, consistently outperform OGD and FTRL. Key observations include:

  • Regret Optimality: MultiVAW-OHF achieves the theoretical gold standard of logarithmic regret, visible in the average regret plots where the error decays rapidly over time.
  • Forecast Tracking: Qualitative analysis shows that MultiVAW-OHF tracks the "True signal" and the "Optimal Linear Regression" much more efficiently than OGD, which often exhibits a significant lag in "catching up" to the data signal.
  • Robustness: While FTRL showed instability in early learning stages, MultiVAW-OHF remained robust from the first few iterations.

Key Insights and Future Work

A major theoretical contribution of this work is the generalization of MetaVAW. The authors demonstrate that MetaVAW is a special case of MultiVAW, allowing them to relax previous restrictive assumptions regarding data coherence. Furthermore, the algorithm is computationally efficient; by utilizing the Woodbury matrix identity, the authors provide recursive updates that make MultiVAW feasible for real-time applications.

Future research directions include scaling the algorithm to hierarchies with millions of nodes and extending these logarithmic regret guarantees to non-linear or kernelized multivariate settings. Currently, the model assumes a linear relationship, which provides a strong foundation for structured online learning.

Summary updated

BibTeX
@misc{hihat2024multivariate,
  author = {Massil Hihat and Guillaume Garrigos and Adeline Fermanian and Simon Bussy},
  title = {{Multivariate Online Linear Regression for Hierarchical Forecasting}},
  year = {2024},
  eprint = {2402.14578},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.14578},
}
Figure