Minimax Time Series Prediction

Wouter M. Koolen, Alan Malek, Peter L. Bartlett, Yasin Abbasi-YadkoriNeurIPS 2015 · OpenReview

Introduction

Traditional time series analysis often relies heavily on stochastic assumptions, presuming that data follows a specific probabilistic process like an Auto-Regressive Moving Average (ARMA) model or Brownian motion. However, in many real-world scenarios, data can be adversarial or simply fail to fit a clean probabilistic model.

To address this, this paper introduces an exact minimax strategy for online time series prediction under square loss. By competing against the best "smooth" sequence in hindsight, the authors demonstrate that the optimal adversarial predictor is a simple linear filter. This filter can be updated in constant time, offering a robust, theoretically grounded alternative to traditional stochastic models without relying on empirical datasets for validation.

The Adversarial Regret Framework

Instead of probabilistic modeling, the authors tackle time series prediction using the regret framework. In this setup, a learner attempts to minimize the difference between their cumulative loss and the loss of the best possible sequence of predictions chosen after the fact (the "comparator").

To make this game competitive and meaningful, the comparator is restricted to be "smooth"—meaning it cannot jump around erratically to perfectly match noisy data. The ultimate goal is to find the minimax strategy: the specific algorithm that minimizes the worst-case regret an adversary could possibly inflict on the learner.

Methodology: Solving the Minimax Game

The researchers employ several key mathematical techniques to solve this adversarial game:

  • Minimax Formulation: The problem is structured as a $T$-round game where the learner chooses a prediction and an adversary chooses a data point. The objective function evaluates the learner's square loss minus the comparator's loss, while adding a penalty for the comparator's complexity (e.g., the sum of squared differences between consecutive steps).
  • Backward Induction: To discover the optimal strategy, the authors work backward from the final time step $T$ to the beginning. They prove that the "value-to-go" (the remaining regret) remains a quadratic function of the past data at every step.
  • Convex-Concave Analysis: A significant technical hurdle in this induction is that the sub-problems can flip between being convex and concave. The authors provide a method to solve both cases and show that the active case can be determined beforehand based solely on the regularization parameters.
  • Linear Filtering: They prove that the optimal prediction is always a linear combination of previous observations. For common smoothness measures, the resulting matrices are sparse (specifically tridiagonal), which allows for highly efficient computation.

Key Insights and Theoretical Results

This purely theoretical work yields several powerful insights into adversarial time series prediction:

  • A Priori Curvature: Typically, minimax problems where the objective changes from convex to concave are notoriously difficult to solve. The breakthrough here is showing that the direction of curvature depends only on the problem's parameters (the regularization matrix and data constraints), not on the actual data observed. This allows the optimal strategy to be pre-computed.
  • Exact Minimax Strategy and Efficiency: The paper provides an explicit expression for the optimal predictions and the exact minimax regret for a wide range of smoothness penalties. For the most common smoothness definitions, the algorithm runs in $O(d)$ time per round (where $d$ is the dimension of the data), making it highly practical for real-time applications.
  • Regret Bounds: The authors prove that the minimax regret grows as $O(T / \sqrt{\lambda_T})$, where $T$ is the time horizon and $\lambda_T$ is the smoothness parameter. This confirms that the learner can successfully "track" a smooth comparator with sub-linear regret.
  • Exponential Decay: For the standard case of penalizing increments to enforce smoothness, the optimal predictor acts as a filter where the weights of past observations decay exponentially. This provides a formal, minimax justification for the widespread use of exponential smoothing in time series analysis.
  • Robustness to Constraints: While the minimax strategy is derived assuming certain bounds on the data, it remains highly robust. If the data violates these bounds, the algorithm still provides an adaptive regret bound that scales naturally with the actual energy of the realized data.

Limitations and Future Work

While the framework is robust, the authors note a few limitations and open challenges:

  • Stability of Recursion: The stability of the coefficients used in the recursive updates is not yet fully understood for all possible types of regularization matrices.
  • Higher-Order Smoothness: The framework theoretically supports higher-order penalties (such as penalizing the "acceleration" or second derivative of the series). However, in practice, the behavior of the coefficients becomes much more complex, sometimes oscillating or becoming negative.
  • Loss Functions: The entire derivation relies heavily on the mathematical properties of the squared Euclidean loss ($L_2$). Extending these exact minimax results to other loss functions, like absolute error or $L_1$ loss, remains an open and difficult challenge.

Summary updated

Abstract

We consider an adversarial formulation of the problem ofpredicting a time series with square loss. The aim is to predictan arbitrary sequence of vectors almost as well as the bestsmooth comparator sequence in retrospect. Our approach allowsnatural measures of smoothness such as the squared norm ofincrements. More generally, we consider a linear time seriesmodel and penalize the comparator sequence through the energy ofthe implied driving noise terms. We derive the minimax strategyfor all problems of this type and show that it can be implementedefficiently. The optimal predictions are linear in the previousobservations. We obtain an explicit expression for the regret interms of the parameters defining the problem. For typical,simple definitions of smoothness, the computation of the optimalpredictions involves only sparse matrices. In the case ofnorm-constrained data, where the smoothness is defined in termsof the squared norm of the comparator's increments, we show thatthe regret grows as $T/\sqrt{\lambda_T}$, where $T$ is the lengthof the game and $\lambda_T$ is an increasing limit on comparatorsmoothness.
BibTeX
@inproceedings{koolen2015minimax,
  author = {Wouter M. Koolen and Alan Malek and Peter L. Bartlett and Yasin Abbasi-Yadkori},
  title = {{Minimax Time Series Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=Sy-x4v-ObB},
}

Loading related content...

Figure