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.
Furthermore, an online approach that relies on regret minimization techniques was never considered for ARMA prediction, and hence regret bounds of the type we are interested simply do not exist. Yet, results on the convergence rate of the coefficient vectors do exist, and regret bounds can be derived from these results. E.g., in @cite_2 such results are presented, and a regret bound of @math can be derived for the squared loss. We are not familiar of these kind of results for general convex loss functions.
@cite_2
2160220160
We introduce the general and powerful scheme of predicting information re-use in optimization algorithms. This allows us to devise a computationally efficient algorithm for bandit convex optimization with new state-of-the-art guarantees for both Lipschitz loss functions and loss functions with Lipschitz gradients. This is the first algorithm admitting both a polynomial time complexity and a regret that is polynomial in the dimension of the action space that improves upon the original regret bound for Lipschitz loss functions, achieving a regret of @math . Our algorithm further improves upon the best existing polynomial-in-dimension bound (both computationally and in terms of regret) for loss functions with Lipschitz gradients, achieving a regret of @math .