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

Imon Banerjee; Pierre Alquier

cs.LGOct 21, 2026

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

Authors: Imon Banerjee, Pierre Alquier

Organizations: University of Chicago, Booth School of Business · ESSEC Business School, Asia-Pacific campus, Singapore

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.

Figures & tables

Notation	Definition	Notation	Definition
$Z_{t}$	Observation at time $t$ .	$\mathcal{G}_{t}$	Filtration including observations and regeneration marks.
$\tau_{j}$	The $j$ -th regeneration time.	$\mathbb{P}_{A},\mathbb{E}_{A}$	Common post-regeneration law and expectation.
$\Delta_{j}$	Block length $\tau_{j+1}-\tau_{j}$ .	$B_{j}$	Block $(Z_{\tau_{j}+1},\ldots,Z_{\tau_{j+1}})$ .
$\Theta,\mathcal{P}(\Theta)$	Parameter space and its probability measures.	$\mu,\rho$	Prior and generic posterior on $\Theta$ .
$\ell_{\theta}$	Loss associated with $\theta$ , taking values in $[0,1]$ .	$\bar{\pi}$	Equilibrium occupation measure.
$R(\theta)$	Long-run risk $\int\ell_{\theta}(z)\,\bar{\pi}(dz)$ .	$L_{j,\theta}$	Cumulative loss in block $j$ .

Table 1: Notation used throughout the paper.

Generalization Bounds

Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.

See all 163 papers

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
May 2, 2026Fan Chen, Jian Qian, Alexander Rakhlin +1Linear Regression
MIT · University of Hong Kong · UC Berkeley
Sequential operator learning under dependent data
Aug 25, 2026Rafael OliveiraOperator Learning Statistical Learning Theory
CSIRO Technology Sydney, Australia
Comparing Corrupted Constrained Learning Problems
Aug 26, 2026Laura Iacovissi, Rabanus Derr, Robert C. WilliamsonStatistical Learning Theory
Tübingen AI Center, University of Tübingen, Germany

May 2, 2026J/K move · Enter open · S save

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression

Fan Chen, Jian Qian, Alexander Rakhlin, Nikita Zhivotovskiy

MIT · University of Hong Kong · UC Berkeley

Linear Regression

Open paper AskPDF arXiv

Self-normalized martingale inequalities lie at the heart of confidence ellipsoids for online least squares and, more broadly, many bandit and reinforcement-learning results. Yet existing vector and scalar results typically rely on bounded covariates and an explicit regularization matrix, producing bounds that are not scale-invariant: although the self-normalized quantity is scale-invariant by definition, its standard upper bounds are not. We characterize when scale-invariant upper bounds on self-normalized martingales are possible. Without further assumptions, we prove that nontrivial scale-invariant bounds exist only in dimension

d=1

; moreover, in

d=1

we obtain

O(\log T)

scale-invariant self-normalized bounds without any assumptions on the covariates. In contrast, for

d>1

we show that no nontrivial scale-invariant bound can hold in full generality. We then connect this dichotomy to doubly-uniform regret in online linear regression (i.e., regret bounds that are simultaneously independent of the covariate scale and the comparator norm) and use it to resolve the open question of Gaillard, Gerchinovitz, Huard, and Stoltz, \emph{``Uniform regret bounds over

\mathbb{R}^d

for the sequential linear regression problem with the square loss''} (ALT 2019): in

d=1

we give an explicit algorithm with

O(\log T)

doubly-uniform regret, whereas for

d>1

sublinear doubly-uniform regret is impossible. Finally, under a natural smoothness condition (bounded Radon--Nikodym derivatives of the conditional covariate laws with respect to a fixed base measure), we recover sublinear regret for

d>1

without bounded covariates and derive a self-normalized concentration inequality free of the usual regularization penalties, yielding arguably a first natural scale-invariant bound for adaptive, non-i.i.d. vector martingales.

Abstract

Generalization Bounds

Explore similar work

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression

Sequential operator learning under dependent data

Comparing Corrupted Constrained Learning Problems