What is a uniform convergence counterpart to Bernstein's inequality?
If Pollard's inequality is a uniform convergence counterpart to Hoeffding's inequality, what is a uniform convergence counterpart to Bernstein's inequality?
For completeness, I include all these three concentration inequalities here:
Hoeffding's inequality: If $\{X_i\}_{i=1}^n$ are i.i.d. random variables such that $a_i \leq X_i \leq b_i, \forall i$. Then, for any $\epsilon > 0$, we have$$ P(\frac{1}{n}\sum_{i=1}^X X_i - \mathbb{E}[X_1] > \epsilon) \leq \exp( \frac{-2 n^2 \epsilon^2}{ \sum_{i=1}^n (a_i - b_i)^2 } ) $$
Pollard's:
where $\mathcal{N}$ is the covering number notation (From here ).
- Bernstein's inequality:
From here (probability_theory).
What I am looking for is a uniform convergence counterpart to the Bernstein's inequality, something possibly looks like this:
$$ P(\sup_{f \in \mathcal{F}} | \frac{1}{n} \sum_{i=1}^n f(X_i) - \mathbb{E}[f(X_1)] | > \epsilon) \leq \text{covering_number} \cdot \exp( \frac{-0.5 \epsilon^2}{ \sum_{i=1}^n \mathbb{E}[X_i^2] + 1/3 M \epsilon } ). $$
$\endgroup$1 Answer
$\begingroup$This is exactly Theorem B in :) :
