Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence

Concentration inequalities for dependent data usually involve mixing coefficients that cannot be observed. Banerjee and Alquier work instead with regenerative processes, whose path splits into independent, identically distributed cycles of finite mean length, and prove a self-normalised Bernstein inequality for bounded functions that uses the observed cycle lengths and keeps explicit terms for truncation and for the cycle still running at the horizon.

Choosing a tuning parameter from a finite deterministic grid yields a version in which all terms are empirical except one, tied to the tails of the regeneration times, which they show is of second order in many regimes. The result gives generalisation bounds for classification with regenerative data, learning objectives whose minimisers satisfy oracle inequalities, and a bound on the average deviation that is minimax-optimal in the sample size \(n\) and the expected regeneration time.