Minimax Time Series Prediction
We consider an adversarial formulation of the problem of predicting a time series with square loss. The aim is to predict an arbitrary sequence of vectors almost as well as the best smooth comparator sequence in retrospect. Our approach allows natural measures of smoothness such as the squared norm of increments. More generally, we consider a linear time series model and penalize the comparator sequence through the energy of the implied driving noise terms. We derive the minimax strategy for all problems of this type and show that it can be implemented efficiently. The optimal predictions are linear in the previous observations. We obtain an explicit expression for the regret in terms of the parameters defining the problem. For typical, simple definitions of smoothness, the computation of the optimal predictions involves only sparse matrices. In the case of norm-constrained data, where the smoothness is defined in terms of the squared norm of the comparator's increments, we show that the regret grows as T / √ λ T , where T is the length of the game and λ T is an increasing limit on comparator smoothness.
The paper is very well-written, both syntactically and logically: the ideas were easy to follow and the contribution is quite clear. The idea to analyze arbitrarily generated time series using the regret criteria is interesting in my opinion, yet it is not the first time such analysis is made (despite the fact that the authors do not cover the relevant literature in their related work section). I expect the authors to do a better literature review if the paper is accepted.One issue that bothers me the most is the non-standard definition of the regret: why should the comparator class be penalized on its smoothness complexity? In particular, many time series are not smooth and yet are simply predicted (for example, AR type time series). In my opinion, the logical thing to do is to restrict the model and not the predictions. For example, if we consider an AR model, the restriction should be on the smoothness of the AR coefficients and not on the smoothness of the predictions. The current regularization might hold as well, but needs to be better motivated by the authors.The authors mention that their setting can handle with ARMA models, which seems misleading to me. I am not sure what the authors mean here - if the time series is allowed to be arbitrarily generated (as the authors assume) then ARMA models are not well-defined (see the work of Anava et al (2013)). If the time series is stochastically generated (and is in fact an ARMA process), then a regret result is meaningful, but I expect the authors to clarify this point. In particular, such results should be better contrasted with existing results (both theoretically and empirically).I find the experimental section very poor (even though it appears only in the appendix). In particular, the authors do not compare their result to any baseline, error plots are not presented, the setting and the generation mechanism of the time series are not specified, and more. I suggest the authors to remove it completely or follow the standard requirements in this field.Despite the weaknesses I spot, I vote for acceptance and willing to upgrade my score according to the authors response (mainly motivating the regret definition).minor comments: (1) line 282 - sill -> still. (2) I would use similar notations in section 3 and 4 - \alpha should be c, \beta should be w, and c should be u. It will be easier to follow this way. (3) please use the word "intriguing" less than you do.UPDATE: The authors response did not allay my concerns regarding the regret formulation, and thus I chose not to upgrade my score. However, since the authors suggest a new approach for time series prediction, I think the paper should be accepted despite its weak theory and experiments. In fact, I am quite sure that this approach will be far behind existing approaches in practice, but might open the door for interesting future work. Missing literature: I would start with the standard textbooks (Hamilton, Box&Jenkins, Brockwell&Davis), and advance to newer papers that combine learning techniques for time series prediction (some even use the regret criterion). Some pointers: Generalization Bounds for Time Series Prediction with Non-stationary Processes, Nonparametric Time Series Prediction Through Adaptive Model Selection, Online Prediction of Time Series Data With Kernels, Online Learning for Time Series Prediction.