Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence
Overview & Synopsis
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.
arxiv.org)
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence |
|---|---|
| Author / Organization | Imon Banerjee, Pierre Alquier |
| Subject & Discipline | cs.LG |
| Categories | Science & Mathematics |
| Publication Year | 2026 |
| License / Rights | arXiv Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
arXiv
(arxiv.org)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-266164 |
| Original Source Link | Visit Source Page on arxiv.org » |