Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence
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 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 the first-order term only in the bound, we define agnostic classifiers that still satisfy oracle inequalities. We also show that the bound on the average deviation provided by our results is minimax-optimal in the sample size and in the expected regeneration time. Finally, we combine the Bernstein inequality with a regenerative strong approximation to obtain a Gaussian approximation using an observable block variance estimator.
Related
- Bernstein’s inequalities for general Markov chains
- Weighted Bernstein-type inequalities on a trapezoidal domain
- Jackson and Bernstein Inequalities with Explicit Weight Dependence for Band-Limited Wavelet Approximation in Weighted Besov Spaces
- Sharp Bernstein--Nikolskii inequalities for polynomials and entire functions of exponential type
- Intrinsic-dimension empirical Bernstein inequalities for bounded self-adjoint operators
BibTeX
@misc{banerjee2026selfnormalized,
title = {{Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence}},
author = {Imon Banerjee and Pierre Alquier},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30119},
eprint = {2610.30119},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30119},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence
AU - Imon Banerjee
AU - Pierre Alquier
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30119
UR - https://arxiv.org/abs/2610.30119
AB - 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 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 the first-order term only in the bound, we define agnostic classifiers that still satisfy oracle inequalities. We also show that the bound on the average deviation provided by our results is minimax-optimal in the sample size and in the expected regeneration time. Finally, we combine the Bernstein inequality with a regenerative strong approximation to obtain a Gaussian approximation using an observable block variance estimator.
ER -