Discriminative State-Space Models
We introduce and analyze Discriminative State-Space Models for forecasting nonstationary time series. We provide data-dependent generalization guarantees for learning these models based on the recently introduced notion of discrepancy. We provide an in-depth analysis of the complexity of such models. We also study the generalization guarantees for several structural risk minimization approaches to this problem and provide an efficient implementation for one of them which is based on a convex objective.
Synopsis -------------------
* This paper follows in a line of work from Kuznetsov and Mohri on developing agnostic learning guarantees for time series prediction using sequential complexity measures. Ostensibly, the setup in past works and the present work is that one will fit a hypothesis to observations (x_t,y_t) from time 1 through T, then use this hypothesis to predict y_{T+1} from x_{T+1} (the generalization guarantees provided are slightly more general than this). Where previous works (e.g. "Learning Theory and Algorithms for Forecasting Non-Stationary Time Series", NIPS 2015) considered the case where the hypothesis class is a fixed mapping from context space to outcome space, the present work extends this setup to the case where the setting where one learns a "state space" model. Here, the each hypothesis is a pair (h,g), where g generates an internal "state" variable and h predicts using both a context and state variable (see the paper for more detail). This captures, for example, HMMs. The authors give basic generalization guarantees for this setup, generalization for the setup under structural risk minimization, and an algorithm for learning a restricted class of state space models.
Review  -------------------
* I found the concept for the paper exciting and believe it is well-written but I feel it has two major shortcomings:
I) Technical novelty
* The main results Theorem 1 and 2 should be compared with Theorem 1/Corollary 2 of the NIPS 2015 paper mentioned above (call it KM15 for short). The authors mention that the main advantage of the present work is that the discrepancy term in Theorem 2 does not include a sup over the class G, which one would get by applying Theorem 1 from KM15 naively. Yet, if we look at the proof of Theorem 1 Theorem 2 of the present work, we see that this is achieved by being careful with where one takes the sup over G (line 418), then immediately applying to Lemma 1, whose proof is essentially identical to that of KM15 Theorem 1. To give some more examples: Appendix B largely consists of standard facts about sequential rademacher complexity. It is unclear to me whether the structural risk minimization results represent a substantive improvement on the basic generalization bounds. While I admit that others may find these results practically useful, I feel that the applications and experiments should have been fleshed out further if this was the goal.
 II) General setting is not instantiated sufficiently.
* I was not satisfied with the depth to which the general bounds (eg Theorem 2) were instantiated. I do not feel that the basic promise of the paper (learning state space models) has been fully explored. Namely
** The algorithms section (5) only applies in the setting where the state space mapping class G is a singleton, and so there is no real "learning" of the state space dynamics going on. While I acknowledge that developing efficient algorithms for learning G may be challenging, this bothers me from a conceptual perspective because Theorem 2 bears no improvement over the KM15 results mentioned above when G only contains a single element.
** In line with this comment, the discrepancy term never seems to be instantiated.
** While Theorem 2 depends on the expected sequential cover of the class H x G, which one expects should exhibit some rich dependence on the dynamics G and the distribution over (X,Y), Appendix B seems to handle this term by immediately bounding it by the *worst case* sequential rademacher complexity, which includes a sup over all state space paths, not just those that could be induced by G.
Conclusion -------------------
* In summary, I found the basic concept fairly interesting and think that the tools introduced (eg sequential covering for state space models) will be useful, but I don't think they were explored to enough depth. I also found Assumption 1 and the concrete cases where the discrepancy can be removed in the SRM setting to form a nice set of observations.
* One last comment: While you allude that some notion of discrepancy is necessary for learning based on some results of Long, it would be nice to see a formal lower bound whose functional form depends on this quantity in the general case.
Misc comments:
* Line 123: Definition of \mathcal{R}_{s} doesn't exactly match the formal specification for the class \mathcal{R} used in the definition of the sequential covering number.