Concentration Inequalities
Markov, Chebyshev, Hoeffding — generalisation bounds
You need to estimate the mean click-through rate from 100 samples. Your estimate is 0.043. How confident should you be that the true mean is within 0.01 of this estimate? This is a concentration question: how tightly does a sample statistic concentrate around its true value as the sample size grows? Without formal bounds, you are reporting confidence based on intuition rather than proof.
Markov's inequality: P(X ≥ a) ≤ E[X]/a for non-negative X. Weak but requires only a finite mean — it applies even when variance is infinite. Chebyshev's inequality: P(|X - μ| ≥ kσ) ≤ 1/k². Requires both mean and variance to be finite. Better than Markov but still loose — the bound decays only polynomially in k. Hoeffding's inequality: for bounded independent random variables X_i ∈ [a_i, b_i], the sample mean X̄ satisfies P(|X̄ - E[X̄]| ≥ t) ≤ 2 exp(-2n²t² / Σ(b_i - a_i)²). Exponentially tighter than Chebyshev for bounded variables — the bound shrinks exponentially in t² as t increases.
Union bound (Bonferroni): P(A₁ ∪ A₂ ∪ ... ∪ A_k) ≤ Σ P(A_i). This is used in ML theory to get uniform convergence bounds — proving that the model holds simultaneously over all test examples, not just on average. Combined with Hoeffding, it gives bounds on the generalization gap of a model class.
VC dimension and generalization: the generalization error is bounded by O(√(d_VC log(n/d_VC) / n)) where d_VC is the VC dimension of the hypothesis class and n is training size. More data always helps. More complex models need more data to generalize. For modern overparameterized networks with VC dimension far exceeding training size, these classical bounds are vacuous — the implicit regularization from gradient descent produces tighter practical guarantees.
NOT this. Concentration inequalities are not only relevant in theory. These bounds are exactly why you can trust a sample size calculation. Hoeffding's inequality tells you that for click-through rates bounded in [0,1], you need n ≥ log(2/δ) / (2ε²) samples to guarantee P(|X̄ - μ| ≥ ε) ≤ δ with no distributional assumption. Every power calculation in data science is a concentration inequality with a distributional assumption substituted in. The normal approximation underlying t-tests and z-tests is just a special case with a Gaussian assumption; Hoeffding works without any distributional assumption at all.
Key points
- Use Hoeffding's inequality for sample size estimation when your data is bounded. For click-through rates in [0,1], n ≥ log(2/δ) / (2ε²) samples guarantees P(|X̄ - μ| ≥ ε) ≤ δ. This requires no distributional assumption beyond boundedness — it works whether the true distribution is Bernoulli, Beta, or anything else. For ε = 0.01 and δ = 0.05, that is n ≥ log(40) / 0.0002 ≈ 18,444 samples.
- Trap: applying CLT-based confidence intervals when n is small or the distribution is heavy-tailed. The CLT requires finite variance and sufficiently large n. Hoeffding's bound is distribution-free and valid for any n as long as the variable is bounded. For small-sample A/B tests or metrics with extreme outliers, use Hoeffding or bootstrap confidence intervals instead of assuming normality.
- Diagnostic: if your model selection gives inconsistent results across runs with the same data, compute the generalization bound for your model complexity versus training size. If the bound is loose (greater than 0.5), you do not have enough data to reliably distinguish between models — differences in validation performance are within the noise band of the bound, not real differences in generalization.
Concentration inequalities are the mathematical foundation of every sample size calculation and every generalization bound. Hoeffding's inequality gives distribution-free guarantees for bounded variables — understanding it is what separates a rigorous sample size justification from an intuitive one.
Recap
- Concentration = how tightly a sample statistic hugs its true value as n grows — turns intuition into proof.
- Markov: P(X ≥ a) ≤ E[X]/a — weakest, needs only a finite mean.
- Chebyshev: P(|X−μ| ≥ kσ) ≤ 1/k² — needs finite variance, decays only polynomially.
- Hoeffding (bounded vars): P(|X̄−E[X̄]| ≥ t) ≤ 2exp(−2n²t²/Σ(bᵢ−aᵢ)²) — exponentially tighter, distribution-free.
- Sample size from Hoeffding: n ≥ log(2/δ)/(2ε²); for ε=0.01, δ=0.05 → n ≈ 18,444.
- Union bound P(∪Aᵢ) ≤ ΣP(Aᵢ) + Hoeffding → uniform convergence / generalisation-gap bounds.
- VC bound: gen error ≤ O(√(d_VC log(n/d_VC)/n)); classical bounds go vacuous for overparam nets.
Check your understanding
Q1. You sample 1000 values from a distribution with mean 5 and variance 4. Using Chebyshev's inequality, bound P(|X̄ − 5| ≥ 0.5).
- A) Apply Chebyshev to the raw variable X rather than the sample mean: P(|X−5| ≥ 0.5) ≤ Var(X)/0.5² = 4/0.25 = 16, which exceeds 1 and is therefore trivially satisfied and uninformative. The sample mean X̄ is not the right quantity to bound here — Chebyshev applies only to single observations, not to averages, so n=1000 provides no benefit unless the exact distribution family is also known in advance.
- B) Chebyshev applied to X̄: P(|X̄ − μ| ≥ ε) ≤ Var(X̄)/ε² = (σ²/n)/ε². With σ²=4, n=1000, ε=0.5: Var(X̄) = 4/1000 = 0.004, giving a raw bound of 0.004/0.25 = 0.016. But Chebyshev additionally requires the underlying distribution to be symmetric around its mean, so for general asymmetric distributions the correct bound must be doubled: P(|X̄ − 5| ≥ 0.5) ≤ 0.032 = 3.2%.
- C) X̄ is the sample mean of n=1000 i.i.d. samples, so E[X̄] = μ = 5 and Var(X̄) = σ²/n = 4/1000 = 0.004. Chebyshev applied to X̄: P(|X̄ − μ| ≥ ε) ≤ Var(X̄)/ε² = 0.004/0.25 = 0.016, so P(|X̄ − 5| ≥ 0.5) ≤ 1.6%. Chebyshev needs no distributional assumption beyond finite variance — a distribution-free bound. Averaging reduces variance by 1/n, so the bound scales as σ²/(n·ε²): to halve it, quadruple n or halve ε.
- D) P(|X̄ − 5| ≥ 0.5) ≤ 2·exp(−2nε²/range²) is the relevant bound here. We first need the range of X, which is not given. Without knowing the range, we cannot apply Chebyshev to this problem at all — only Hoeffding's inequality, which specifically requires bounded support. Chebyshev only ever applies to individual observations X, never to sample means X̄; for sample means, Hoeffding's inequality is the correct and only valid tool.
Q2. Hoeffding's inequality gives a tighter bound than Chebyshev for bounded random variables. Why? What is the bound on P(|X̄ − E[X̄]| ≥ ε) for n i.i.d. Xᵢ ∈ [0,1]?
- A) Hoeffding's bound for n i.i.d. Xᵢ ∈ [0,1]: P(|X̄ − E[X̄]| ≥ ε) ≤ 2exp(−2nε²). Chebyshev gives P ≤ Var(X̄)/ε² = σ²/(nε²) ≤ 1/(4nε²) for bounded [0,1] variables — Hoeffding is exponential in n while Chebyshev is only polynomial. For n=1000, ε=0.1: Hoeffding ≤ 2exp(−20)≈4×10⁻⁹ versus Chebyshev's 2.5×10⁻² — the exponential dominates for large n. Hoeffding is tighter because it uses the boundedness condition directly via the MGF, which is more constrained than variance alone.
- B) Hoeffding's bound for Xᵢ ∈ [0,1]: P(|X̄ − E[X̄]| ≥ ε) ≤ exp(−nε²/2). Chebyshev's bound is 1/(4nε²). For n=1000, ε=0.1: Hoeffding ≤ exp(−5) ≈ 0.0067 while Chebyshev ≤ 0.0025 — Chebyshev is actually tighter in this regime, because it directly uses variance information (σ² ≤ 1/4 exactly), whereas Hoeffding uses only the coarser range information (width = 1). Hoeffding's advantage only appears for very large n or very small ε, not universally.
- C) Hoeffding's bound: P(|X̄ − E[X̄]| ≥ ε) ≤ 2exp(−nε²). This is tighter than Chebyshev's P ≤ σ²/(nε²) ≤ 1/(4nε²) for all n. At n=50, ε=0.1: Hoeffding ≤ 2exp(−0.5)≈1.21, which exceeds 1 and is vacuous, while Chebyshev ≤ 0.5 is actually tighter here. Hoeffding only beats Chebyshev once 2exp(−nε²) < 1/(4nε²), roughly n > 100 for ε=0.1 — the missing factor of 2 in the exponent is the key difference from the correct formula.
- D) Hoeffding's bound equals Chebyshev's bound for variables in [0,1]: both simply give P ≤ 1/(4nε²). The only real difference is that Hoeffding's bound happens to be exact — an equality rather than an inequality — while Chebyshev's remains a loose upper bound throughout. Hoeffding is 'tighter' only in the sense of being achievable by Bernoulli(0.5) variables, while Chebyshev's bound can never actually be achieved — the Paley-Zygmund inequality supplies the true achievable lower bound on P.
Q3. Which two of the following statements about the VC dimension of linear classifiers in ℝ² (which is 3) are correct?
- A) There exist 3 non-collinear points in ℝ² that can be shattered — labeled in all 2³=8 possible ways by some linear classifier — but no set of 4 points can ever be shattered, since some 4-point labelings require an XOR-style boundary that no linear classifier can implement.
- B) The VC generalisation bound states that, with probability ≥1−δ over the training sample, test error ≤ train error + √(d·log(2n/d) + log(4/δ))/√n, where d is the VC dimension — so a larger, more expressive hypothesis class needs proportionally more training data n to keep the generalisation gap small.
- C) VC dimension 3 means linear classifiers require at least 3 training examples to be fully specified as a decision boundary; with exactly 3 non-collinear points the linear boundary becomes uniquely determined up to an overall scale factor on the weight vector, and generalisation follows automatically once the boundary is fixed.
- D) VC dimension 3 means the growth function m_H(n) is bounded by O(n³) for every n including n ≤ 3, and this same polynomial bound is what directly produces the O(1/√n) generalisation rate — VC dimension is therefore just another name for the polynomial order of the model.
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →