Generalization for slowly mixing processes

For samples generated by stationary and φ-mixing processes we give generalization guarantees uniform over Lipschitz, smooth or unconstrained loss classes. The result depends on an empirical estimator of the distance of data drawn from the invariant distribution to the sample path. The mixing time (the time needed to obtain approximate independence) enters these results explicitely only in an additive way. For slowly mixing processes this can be a considerable advantage over results with multiplicative dependence on the mixing time. Because of the applicability to unconstrained loss classes, where the bound depends only on local Lipschitz properties at the sample points, it may be interesting also for iid processes, whenever the data distribution is a sufficiently simple object.