Generalization for slowly mixing processes
This work addresses generalization theory for non-i.i.d. data, providing improved bounds for slowly mixing stochastic processes, which is incremental but relevant for applications in time-series analysis and dependent data settings.
The paper tackles the problem of deriving generalization bounds for data generated by stationary and phi-mixing processes, showing that the mixing time enters sample complexity additively rather than multiplicatively, which offers advantages for slowly mixing processes. The result applies to loss classes with Lipschitz or smoothness constraints and can be extended to unconstrained classes using local properties.
A bound uniform over various loss-classes is given for data generated by stationary and phi-mixing processes, where the mixing time (the time needed to obtain approximate independence) enters the sample complexity only in an additive way. For slowly mixing processes this can be a considerable advantage over results with multiplicative dependence on the mixing time. The admissible loss-classes include functions with prescribed Lipschitz norms or smoothness parameters. The bound can also be applied to be uniform over unconstrained loss-classes, where it depends on local Lipschitz properties of the function on the sample path.