Bernstein bounds for regenerative data yield non-i.i.d. generalization guarantees
Original title: Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence
The bounds support agnostic classifiers from a first-order term and are minimax-optimal in sample size and expected regeneration time.
The paper proves a self-normalized Bernstein inequality for bounded functions of a regenerative process with i.i.d. marked cycles of finite mean length. The bound uses observed cycle lengths and keeps explicit truncation and leftover-cycle terms. It yields generalization error bounds for classification on non-i.i.d. regenerative data, plus a Gaussian approximation via a regenerative strong approximation and an observable block variance estimator.
- Tuning comes from a finite deterministic collection, leaving one regeneration-tail term.
- That remaining term is second-order in many regimes of interest.
- Minimizing only the first-order term still gives oracle inequalities for agnostic classifiers.
- The average-deviation bound is minimax-optimal in sample size and expected regeneration time.
From the original article
1 min read at arxiv.orgWe 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.
By Imon Banerjee · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.