Self-Normalized Bernstein Inequalities for Regenerative Processes and Machine Learning Applications

Paper Overview

• Field: Machine Learning
• Authors: Imon Banerjee, Pierre Alquier
• Published: 2026-10-21
• arXiv: 2610.30119

Abstract

We prove a self-normalized Bernstein inequality for bounded functions of a regenerative process with independent, identically distributed marked cycles of finite mean length. The bound uses observed cycle lengths and retains explicit terms for truncation and the cycle ending after the observation horizon.

Selecting a tuning parameter from a finite deterministic collection gives a version of the Bernstein inequality where all terms are empirical but one, related to the tails of the regeneration times. We then study this term in many regimes: it turns out that it is of second-order in many cases of interest.

This is important for applications in machine learning:

• We prove generalization error bounds for classification with non-i.i.d., regenerative data.
• These bounds can be used to define learning objectives: by minimizing only the first-order term of the bound, we define agnostic classifiers that still satisfy oracle inequalities.
• We prove that the mean deviation bounds given by our results are minimax optimal in terms of sample size and expected regeneration time.
• Finally, combining the Bernstein inequality with regenerative strong approximation, we obtain Gaussian approximation results using observable block variance estimators.

*Auto-collected on 2026-10-23.*