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 b
e 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 ($beta$-mixing) processes, of independent probability-theoretic interest.
Concentration bounds for non-product, non-Haar measures are fairly recent: the first such result was obtained for contracting Markov chains by Marton in 1996 via the coupling method. The work that followed, with few exceptions, also used coupling. Al
though this technique is of unquestionable utility as a theoretical tool, it is not always simple to apply. As an alternative to coupling, we use the elementary Markov contraction lemma to obtain simple, useful, and apparently novel concentration results for various Markov-type processes. Our technique consists of expressing probabilities as matrix products and applying Markov contraction to these expressions; thus it is fairly general and holds the potential to yield further results in this vein.
We bound the number of nearly orthogonal vectors with fixed VC-dimension over $setpm^n$. Our bounds are of interest in machine learning and empirical process theory and improve previous bounds by Haussler. The bounds are based on a simple projection
argument and the generalize to other product spaces. Along the way we derive tight bounds on the sum of binomial coefficients in terms of the entropy function.
We investigate the existence of bounded-memory consistent estimators of various statistical functionals. This question is resolved in the negative in a rather strong sense. We propose various bounded-memory approximations, using techniques from autom
ata theory and stochastic processes. Some questions of potential interest are raised for future work.
We give a universal kernel that renders all the regular languages linearly separable. We are not able to compute this kernel efficiently and conjecture that it is intractable, but we do have an efficient $eps$-approximation.
The rate at which dependencies between future and past observations decay in a random process may be quantified in terms of mixing coefficients. The latter in turn appear in strong laws of large numbers and concentration of measure results for depend
ent random variables. Questions regarding what rates are possible for various notions of mixing have been posed since the 1960s, and have important implications for some open problems in the theory of strong mixing conditions. This paper deals with $eta$-mixing, a notion defined in [Kontorovich and Ramanan], which is closely related to $phi$-mixing. We show that there exist measures on finite sequences with essentially arbitrary $eta$-mixing coefficients, as well as processes with arbitrarily slow mixing rates.
