Inequalities and Convergence

TL;DR

1. Markov: $P(X\ge t)\le \frac{E(X)}{t}$ for $X\ge 0$. Chebyshev: $P(|X-EX|\ge t)\le \frac{\mathrm{Var}(X)}{t^2}$.
2. Hoeffding (bounded i.i.d. variables in $[0,1]$): $P(|{\bar{X}}_n-\mu |\ge \epsilon )\le 2e^{-2n{\epsilon }^2}$: exponentially small in $n$.
3. Three ways to read one bound: fix $n,\epsilon$ → probability; fix $n,\delta$ → accuracy $\epsilon =\sqrt{\log (2/\delta )/(2n)}$; fix $\epsilon ,\delta$ → sample size $n\ge \log (2/\delta )/(2{\epsilon }^2)$.
4. “With probability at least $1-\delta$” = the bad event has probability at most $\delta$.
5. Law of large numbers: ${\bar{X}}_n\to \mu$. Convergence in probability: $P(|Z_n-Z|>\epsilon )\to 0$ for every $\epsilon >0$. Consistency is defined this way.

Markov and Chebyshev

Markov's inequality

For a non-negative random variable $X$ and $t>0$: $P(X\ge t)\le \frac{E(X)}{t}$.

Example: average waiting time 5 minutes. Then at most $5/20=25\%$ of the people wait 20 minutes or longer, whatever the distribution.

Chebyshev's inequality

$P(|X-E(X)|\ge t)\le \frac{\mathrm{Var}(X)}{t^2}$ (Markov applied to $(X-EX{)}^2$).

Applied to the mean of $n$ i.i.d. variables ($\mathrm{Var}={\sigma }^2/n$): $P(|{\bar{X}}_n-\mu |\ge \epsilon )\le \frac{{\sigma }^2}{n{\epsilon }^2}$. It goes to 0 like $1/n$: this proves the (weak) law of large numbers.

Hoeffding’s inequality

Hoeffding

$Z_1,\dots ,Z_n$ independent with values in $[0,1]$, ${\bar{Z}}_n=\frac{1}{n}{\sum }_i{Z}_i$, $\mu =E{\bar{Z}}_n$:

$$P(|{\bar{Z}}_n-\mu |\ge \epsilon )\le 2\exp (-2n{\epsilon }^2).$$

One-sided (only ${\bar{Z}}_n-\mu \ge \epsilon$): without the factor 2.

Why it matters: the loss of a fixed classifier on $n$ test points is exactly such an average, so the test error is within $\epsilon$ of the true risk with high probability (L3).

Solving a bound for the sample size, the accuracy or the confidence

Set the right-hand side equal to $\delta$ and solve:

wanted	given	formula (two-sided)
probability of a bad event	$n$, $\epsilon$	$2e^{-2n{\epsilon }^2}$
accuracy $\epsilon$	$n$, $\delta$	$\epsilon =\sqrt{\frac{\ln (2/\delta )}{2n}}$
sample size $n$	$\epsilon$, $\delta$	$n\ge \frac{\ln (2/\delta )}{2{\epsilon }^2}$

Mini example

How many test points guarantee the test error to be within $\epsilon =0.05$ of the true error with probability $95\%$ ($\delta =0.05$)? $n\ge \frac{\ln 40}{2\cdot 0.0025}=\frac{3.69}{0.005}\approx 738$. For $\epsilon =0.01$: 25 times as many, about $18,445$.

Memory aid

Half the error needs four times the data ($n\sim 1/{\epsilon }^2$), but ten times more confidence (δ divided by 10) only costs $+\ln 10\approx 2.3$ in the numerator. Confidence is cheap, accuracy is expensive.

Finite class of $m$ functions: the union bound (Probability Basics) multiplies the bad probability by $m$, so $\ln (2/\delta )$ becomes $\ln (2m/\delta )$: $\epsilon =\sqrt{(\ln 2m+\ln (1/\delta ))/(2n)}$ (L3).

Reading “with probability at least 1 − δ”

A statement like “with probability at least $1-\delta$, $R(f)\le R_n(f)+\epsilon (n,\delta )$” means: over the random draw of the training set, the event where the inequality fails has probability at most $\delta$. Smaller $\delta$ (more confidence) makes $\epsilon$ larger, but only through $\log (1/\delta )$.

Memory aid

$\delta$ is the “risk of bad luck with the sample”. It always appears as $\log (1/\delta )$ or $-\log \delta$ (the same thing, since $-\log \delta =\log (1/\delta )>0$ for $\delta <1$).

Law of large numbers and convergence

Convergence in probability

$Z_n\to Z$ in probability if for every $\epsilon >0$: $P(|Z_n-Z|>\epsilon )\to 0$ as $n\to \infty$. Other modes (almost surely, in $L_1$) are in L1.2.

Law of large numbers

For i.i.d. $X_i$ with mean $\mu$: ${\bar{X}}_n\to \mu$ (in probability; also almost surely). In the course: $R_n(f)\to R(f)$ for every fixed $f$ (L1.2).

Why the LLN is not enough for ERM

The ERM solution $f_n$ is chosen using the data, so the $\ell (X_i,Y_i,f_n(X_i))$ are not independent of $f_n$; the LLN does not apply to $R_n(f_n)$. The fix is uniform convergence over the whole class (L3), paid for with $\log m$ or the VC dimension.

Consistency of a learning algorithm is convergence in probability of the risk: $P(R(f_n)-R^{\ast }>\epsilon )\to 0$ (L1.2).

Self-check

Question cards (4)

A classifier makes 30 errors on 1000 independent test points. Give a 95% two-sided Hoeffding interval for its true error.

Answer

$\epsilon =\sqrt{\ln 40/2000}\approx 0.043$: true error in $[0,0.073]$ (the lower end cut at 0).

What changes in the Hoeffding sample size if $\epsilon$ is divided by 3?

Answer

$n$ is multiplied by 9, because $n\sim 1/{\epsilon }^2$.

Why does the finite-class bound contain $\log m$?

Answer

Union bound over $m$ functions multiplies the failure probability by $m$; solving $2m{e}^{-2n{\epsilon }^2}=\delta$ for $\epsilon$ puts $m$ inside the logarithm.

What does "consistent" mean in terms of convergence?

Answer

The risk of the learned function converges in probability to the Bayes risk: $P(R(f_n)-R^{\ast }>\epsilon )\to 0$ for every $\epsilon >0$.

Related

• Math overview · Random Variables and Expectation · Combinatorics and Asymptotics