Predictive PAC Learning and Process Decompositions
We informally call a stochastic process learnable if it admits a generalization error approaching zero in probability for any concept class with finite VC-dimension (IID processes are the simplest example). A mixture of learnable processes need not be learnable itself, and certainly its generalization error need not decay at the same rate. In this paper, we argue that it is natural in predictive PAC to condition not on the past observations but on the mixture component of the sample path. This definition not only matches what a realistic learner might demand, but also allows us to sidestep several otherwise grave problems in learning from dependent data. In particular, we give a novel PAC generalization bound for mixtures of learnable processes with a generalization error that is not worse than that of each mixture component. We also provide a characterization of mixtures of absolutely regular (β-mixing) processes, of independent probability-theoretic interest.
This paper focuses on learning with dependent 
      observations. Under various assumptions, it is possible to upper-bound the 
      deviations of the empirical mean with respect to the expectation, thus 
      allowing to study empirical risk minimization. These assumptions ranges 
      from various mixing assumptions to so-called weak-dependence condition. 
      The authors remark that when P and Q are two probability 
      distributions for the stochastic process X, when X is mixing under P and 
      under Q, it is generally not mixing under aP + (1-a)Q. However, if E is a 
      deviation undersirable event, and if P(E)\leq e and Q(E)\leq e, then 
      (aP+(1-a)Q)(E)\leq e. So, it is possible to extend deviation inequalities 
      to a wider class of probability distribution (that is, mixture of mixing 
      disitributions). This remark might seem trivial, however, it allows some 
      interesting generalization. For example, as exchangeable probability 
      distributions can be written as mixtures of iid distributions, this remark 
      extends results from iid setting to exhangeable distribution at no cost. 
      However: 1) to my opinion, this is a small increment to 
      learning with dependent observations. 2) the paper is not well 
      written. Unnecessary discussions hide the main message of the paper. On 
      the other hand, Definition 1 is non standard and should be explained in 
      more details. The bibliography is incomplete. A lot has been done on 
      learning with dependent observations in Modha and Masry (IEEE Trans. Info. 
      Theory, 1998), Meir (JMLR, 2000), a series of papers by Steinwart, e.g. 
      Steinwart, Hush and Scovel (Journal of Multivariate Analysis, 2009), 
      Alquier and Wintenberger (Bernoulli, 2012) among 
      others.