Source-linked AI summary
Online Learning for Time Series Prediction
Oren Anava, Elad Hazan, Shie Mannor, Ohad Shamir
TL;DR
The paper asks how to predict ARMA time series without strong assumptions on the noise or access to the underlying noise terms. It develops online learning algorithms using regret minimization, showing performance as good as the best ARMA model under weak noise assumptions while also analyzing adversarial noise settings.
Problem
Unknown noise terms make ARMA prediction and direct optimization over coefficient vectors difficult in the online setting.
Method
The paper develops two online algorithms, using improper learning and regret minimization, for general convex and exp-concave loss functions.
Results
The algorithms achieve sublinear regret against the best ARMA prediction in hindsight under weak noise assumptions, with an empirical study verifying the theoretical results.
Takeaways & Limitations
Online learning provides a general, simple, and efficient approach to ARMA prediction when noise terms are unknown and may be broadly generated.
Takeaways & Limitations
Under adversarial noise, the comparison is to the expected loss of ARMA coefficients that generated the signal rather than to the best ARMA prediction in hindsight.
Abstract
from arXiv · showhide
In this paper we address the problem of predicting a time series using the ARMA (autoregressive moving average) model, under minimal assumptions on the noise terms. Using regret minimization techniques, we develop effective online learning algorithms for the prediction problem, without assuming that the noise terms are Gaussian, identically distributed or even independent. Furthermore, we show that our algorithm's performances asymptotically approaches the performance of the best ARMA model in hindsight.
1 Introduction
The paper challenges strong noise assumptions in traditional ARMA prediction by introducing online learning algorithms that support broader noise processes and loss functions. It establishes sublinear regret against the best ARMA prediction in hindsight and empirically studies the approach.
- Motivation: Traditional ARMA prediction commonly relies on independent, identically distributed Gaussian noise assumptions.These assumptions support established parameter-identification and prediction methods but are described as strict for real-world data.
- Contribution: The paper relaxes these assumptions through online learning that permits arbitrarily or partly adversarially generated noise.The approach is intended to handle a wider range of time series and loss functions than squared loss alone.
- Results: Two online algorithms target general convex and exp-concave loss functions, respectively, with sublinear regret against the best ARMA prediction in hindsight.The paper applies the results to squared loss and reports an empirical study verifying the theoretical results.
- Related work: The work addresses a gap in regret-minimization approaches for ARMA prediction, especially for general convex loss functions.Earlier work provided related squared-loss regret results, while comparable results for general convex losses were not known to the authors.
2 Preliminaries and model
The paper models signals with AR and ARMA processes and formulates prediction as an online game against a best-ARMA benchmark. The learner predicts before observing each signal while operating under boundedness, coefficient, noise, and loss assumptions.
- Time-series models: An ARMA(k, q) model represents each signal using autoregressive and moving-average components with coefficient vectors α and β.The AR(k) model is the special case where all β_i coefficients are zero.
- Online setting: In the online setting, an adversary fixes coefficients, chooses noise, generates each signal, and reveals the signal after the learner predicts.The learner then incurs the loss ℓ_t for its prediction.
- Online setting: The objective is to minimize cumulative loss while keeping regret sublinear in T relative to the best possible ARMA model.Sublinear regret corresponds to average per-round regret tending to zero as T increases.
- Online setting: Unknown noise terms prevent direct use of online convex optimization over ARMA coefficients and make generating ARMA predictions or identifying the hindsight optimum difficult.This lack of information is a central challenge in the online formulation.
- Assumptions: The main assumptions include zero-mean independent noise with bounded expectations, Lipschitz loss, bounded α coefficients, contractive β coefficients, and bounded signals.The paper later discusses relaxing the independent-noise assumption to adversarial noise.
3 Online time series prediction
The paper replaces unavailable ARMA-coefficient optimization with online learning over an improper AR(m+k) predictor, then derives regret guarantees using ONS or OGD. The analysis relates this finite-history predictor to ARMA(k,q) performance under stated noise and loss assumptions.
- Prediction reduction: Because noise terms are unknown, the learner predicts with an (m+k)-dimensional AR coefficient vector rather than directly optimizing ARMA coefficients.The predictor uses the last m+k signals, making the loss available to full-information online optimization.
- Algorithm parameters: The candidate set K contains bounded (m+k)-dimensional coefficient vectors, with diameter D controlling the online optimization analysis.The coefficient constraints are inherited from assumptions on the ARMA parameters.
- ARMA-ONS: ARMA-ONS uses Online Newton Step updates for the exp-concave setting, with A0 initialized as ǫI_{m+k} and projections onto K.The algorithm input includes the ARMA order, learning rate, and initial matrix; inverse updates can use Sherman-Morrison efficiently.
- Regret analysis: The AR(m+k) analysis bounds regret through online convex optimization and a separate approximation gap between the finite-history AR loss and the ARMA loss.The approximation argument uses recursive predictions and inequalities; under the stated condition ρ^qL = O(1), the added term does not alter the asymptotic result.
- Assumptions and guarantees: The guarantees rely on independent zero-mean noise for comparison with the generating coefficients, while adversarial noise changes the benchmark to the expected loss of those generating coefficients.The expected-loss formulation is necessary because the noise is unknown; high-probability regret requires boundedness or light-tail assumptions.
- ARMA-OGD: ARMA-OGD provides a computationally simpler alternative for general convex and exp-concave losses, but with somewhat worse theoretical and empirical performance for exp-concave losses.Its update uses Euclidean projection, and its proof substitutes Online Gradient Descent for Online Newton Step.
4 Additional results
The paper extends its online ARMA analysis to adversarial noise and squared loss, with separate guarantees for exp-concave and convex losses. Under the stated assumptions, Algorithm 1's average squared loss converges asymptotically to that of the best ARMA predictor in hindsight.
- Adversarial noise: The theorem's guarantees rely on independent, zero-mean noise for the setting where generating coefficients are optimal in hindsight.With unrestricted adversarial noise, the best hindsight coefficients need not be those that generated the signal.
- Adversarial noise: The adversarial-noise analysis considers exp-concave and convex loss functions using separate online algorithms.Algorithm 1 handles exp-concave losses, while Algorithm 2 handles convex losses.
- Adversarial noise: The adversarial-noise theorem compares algorithmic loss with ARMA prediction using the coefficient vectors that generated the signal.This comparison is not against the best ARMA prediction in hindsight.
- Squared loss: For squared loss, the prediction loss is the squared difference between the observed signal and the AR-based prediction.The paper applies its general result to the commonly used squared-loss setting.
- Squared loss: The average loss of Algorithm 1 converges asymptotically to the average loss of the best ARMA prediction in hindsight.The convergence holds under the assumptions from Section 2.3 and is later tested empirically.
5 Experiments
Experiments on artificial and real data evaluate the online algorithms against ARMA-RLS across stationary, changing, correlated-noise, weather, and financial settings. The online methods are reported as effective in changing and correlated environments, while ARMA modeling performs poorly for S&P 500 returns.
- Experimental design: The experiments compare the proposed online algorithms with the proper-learning ARMA-RLS algorithm across multiple settings.Results are averaged over 20 runs, and the AR prediction order is fixed at m + k = 10.
- Artificial data: In the Gaussian-noise sanity check, ARMA-ONS outperforms the other online algorithms under exp-concave loss.The setting uses uncorrelated Gaussian noise with variance 0.09.
- Artificial data: In the slowly changing-coefficient setting, the online algorithms show a clear advantage, with ARMA-ONS superior despite being less adaptive.The coefficients change slowly and the noise is uniform on [−0.5, 0.5].
- Artificial data: In the abruptly changing-coefficient setting, online algorithms remain effective when the generating coefficients switch between two sets.The experiment uses uncorrelated uniform noise and reports a minimum perfect-predictor error rate of 0.0833.
- Artificial data: Under positively correlated noise, ARMA-ONS achieves an average error rate converging approximately to the noise variance, 0.09.This setting is presented as evidence of robustness to correlated noise.
- Real data: For weather data, all four algorithms learn the pattern, but the results indicate that online algorithms are superior.The series contains monthly average sea-surface temperatures from the GCOS website.
- Real data: For S&P 500 daily returns, the results indicate that ARMA is probably not a good predictive model.The paper suggests the model may be insufficiently rich because return history alone is not enough for good prediction.
6 Conclusion and discussion
The paper’s online approach predicts time series as well as the best ARMA model under weak zero-mean noise assumptions, including unknown noise terms. The conclusion identifies coefficient restrictions, noise identifiability, and ARMA’s limited compatibility with some time series as areas for further research.
- The approach predicts time series as well as the best ARMA model under weak zero-mean noise assumptions, despite unknown noise terms.The paper uses improper learning to address the fact that the underlying noise terms are unknown.
- The analysis assumes Σ_i=1^q |β_i| < 1 − ε for some ε > 0, restricting the freedom of the β coefficients.The authors believe this condition follows from their proof techniques and may not be necessary for the results.
- Competing with the best ARMA predictor under adversarial noise is impossible because of identifiability issues.The authors propose studying intermediate settings such as correlated or partially adversarial noise.
- ARMA models are not compatible with every time series, including the finance-related series considered in Section 5.2.The authors suggest extending the approach to other time-series models, noting ARCH models as a relevant direction.