Afshin Rostamizadeh
Rademacher Bounds for Beta-mixing Distributions

This paper presents the first data-dependent generalization bounds,
based on the notion of Rademacher complexity, for non-iid settings. Our
bounds extend existing Rademacher complexity bounds, derived for the iid
setting, to the non-iid case. These bounds provide a generalization of
the ones found in the iid case (modulo constant factors), and can also
be used within the standard iid scenario. They also apply to the natural
scenario of beta-mixing stationary sequences examined in many previous
studies of non-iid settings and benefit form the crucial advantages of
Rademacher complexity over other measures of the complexity of
hypothesis classes. In particular, these bounds are data-dependent and
measure the complexity of a class of hypotheses based on the training
sample.  Thus, the empirical Rademacher complexity can be estimated from
finite samples and lead to tighter bounds.