Solving Concentration Bounds for Sample Size

From a Tail Bound to a Sample Size

A concentration inequality is often presented as a statement about deviation probability at a given sample size. In planning a study or assessing a learning guarantee, the question is usually reversed: how many observations are sufficient to make a specified error tolerance hold with a specified probability? This is an algebraic inversion of the tail bound, but the details matter: the logarithm depends on whether the bound is one-sided or two-sided, and the final sample size must be an integer.

Here, $\varepsilon>0$ is the allowed absolute deviation and $\delta\in(0,1)$ is the allowed failure probability. A guarantee with failure probability at most $\delta$ is also called a confidence guarantee of at least $1-\delta$. The answer obtained by inverting an inequality is a sufficient sample size under that inequality; it is not generally the exact smallest sample size for the true distribution.

Definition: A bound-based sample-size requirement for tolerance $\varepsilon$ and failure probability $\delta$ is an integer $n$ for which the chosen concentration inequality guarantees $P(|\hat{\theta}-\theta|>\varepsilon)\leq\delta$, or the corresponding one-sided guarantee. The event, assumptions, and form of the inequality must be stated along with the resulting $n$.

Inverting Hoeffding’s Inequality

Let $X_1,\ldots,X_n$ be independent random variables with $X_i\in[a,b]$ almost surely for every $i$, and write $\bar X=n^{-1}\sum_{i=1}^n X_i$. Hoeffding’s inequality gives the two-sided deviation bound

P\left(\left|\bar X-\frac{1}{n}\sum_{i=1}^n E[X_i]\right|\geq\varepsilon\right) \leq 2\exp\left(-\frac{2n\varepsilon^2}{(b-a)^2}\right).

To make the right-hand side no larger than $\delta$, take logarithms and solve for $n$. Since the logarithm is increasing, and the exponential is decreasing in $n$, the required inequality is equivalent to

2\exp\left(-\frac{2n\varepsilon^2}{(b-a)^2}\right)\leq\delta \quad\Longleftrightarrow\quad n\geq \frac{(b-a)^2}{2\varepsilon^2}\log\left(\frac{2}{\delta}\right).

The sample size must be an integer, so round the right-hand side up. Rounding down can leave the concentration bound above the desired failure probability. The same expression applies to independent, identically distributed observations when $\bar X$ estimates their common mean; for a bounded loss in $[0,1]$, its range width $b-a$ is one.

Result: Under the boundedness and independence assumptions above, the two-sided Hoeffding bound is at most $\delta$ whenever $$ n\geq \left\lceil\frac{(b-a)^2}{2\varepsilon^2}\log\left(\frac{2}{\delta}\right)\right\rceil. $$

Worked Hoeffding Sample Sizes

Worked Example: Accuracy of a Bounded Risk Estimate

Suppose a fixed predictor has independent losses $X_i\in[0,1]$, and its empirical risk is $\bar X$. Find a sufficient sample size for absolute error at most $0.05$ with failure probability at most $0.05$.

Here $b-a=1$, $\varepsilon=0.05$, and $\delta=0.05$. The unrounded threshold is

\frac{1}{2(0.05)^2}\log\left(\frac{2}{0.05}\right) =\frac{1}{0.005}\log(40) =200(3.688879\ldots) =737.7759\ldots.

Thus the bound-based integer sample size is $n=738$. Checking the bound at this integer gives

2\exp\bigl(-2(738)(0.05)^2\bigr) =2\exp(-3.69) \approx 0.04994<0.05.

At $n=737$, the exponent is $2(737)(0.05)^2=3.685$, which is less than $\log(40)=3.688879\ldots$. Therefore the Hoeffding upper bound is greater than $0.05$ at 737. This verifies that 738 is the smallest integer meeting this particular bound criterion.

Worked Example: A Tighter Failure Probability

For losses in $[0,1]$, find the Hoeffding sample size for tolerance $\varepsilon=0.10$ and failure probability $\delta=0.01$.

Substitution gives

n\geq \frac{1}{2(0.10)^2}\log\left(\frac{2}{0.01}\right) =50\log(200) =50(5.298317\ldots) =264.9159\ldots.

Rounding up gives $n=265$. At that sample size, the two-sided bound is

2\exp\bigl(-2(265)(0.10)^2\bigr) =2\exp(-5.3) \approx 0.0099832<0.01.

The displayed value is below $0.01$, as required. The calculation uses $\log(2/\delta)$, not $\log(1/\delta)$, because the stated inequality controls both tails together.

Inverting Bernstein’s Inequality

When the observations have a useful variance bound, Bernstein’s inequality can yield a smaller sample-size requirement than Hoeffding’s range-based bound. One standard form is as follows. Let $X_1,\ldots,X_n$ be independent and identically distributed, suppose $|X_i-E[X_i]|\leq M$ almost surely, and suppose $\operatorname{Var}(X_i)\leq v$. Then

P\left(\left|\bar X-E[X_1]\right|\geq\varepsilon\right) \leq 2\exp\left(-\frac{n\varepsilon^2}{2v+(2/3)M\varepsilon}\right).

The denominator is positive when $\varepsilon>0$ and either $v>0$ or $M>0$. In the non-degenerate bounded setting, making this bound at most $\delta$ is equivalent to

n\geq \frac{2v+(2/3)M\varepsilon}{\varepsilon^2} \log\left(\frac{2}{\delta}\right).

The variance and centered-magnitude assumptions are part of the guarantee. They cannot be omitted simply because a sample variance or an observed maximum looks small; those are data-dependent quantities and require a bound that justifies their use.

Result: Under the stated iid Bernstein assumptions, a sufficient integer sample size for the two-sided deviation probability to be at most $\delta$ is $$ n\geq \left\lceil \frac{2v+(2/3)M\varepsilon}{\varepsilon^2} \log\left(\frac{2}{\delta}\right) \right\rceil. $$

Worked Example: Using a Variance Bound

Suppose an iid loss $X_i$ satisfies $|X_i-E[X_i]|\leq1$ almost surely and $\operatorname{Var}(X_i)\leq0.04$. Find the Bernstein sample size for $\varepsilon=0.05$ and $\delta=0.05$.

The denominator factor in the Bernstein exponent is

2v+\frac{2}{3}M\varepsilon =2(0.04)+\frac{2}{3}(1)(0.05) =0.08+0.033333\ldots =0.113333\ldots.

Consequently, the unrounded threshold is

\frac{0.113333\ldots}{(0.05)^2}\log(40) =45.333333\ldots(3.688879\ldots) =167.2292\ldots.

The sufficient integer is $n=168$. A direct check is useful:

\frac{168(0.05)^2}{0.113333\ldots} =\frac{63}{17} =3.705882\ldots>\log(40),

so the bound is $2\exp(-3.705882\ldots)<0.05$. At $n=167$, the exponent is $501/136=3.683824\ldots<\log(40)$, so the bound is greater than $0.05$. Thus 168 is the smallest integer satisfying this Bernstein bound.

Why the Inversion Works

Both calculations are instances of the same monotone inversion. Suppose an inequality has the form $P(A_n)\leq C\exp(-cn)$, where $C>0$, $c>0$, and the desired failure probability is $\delta$. Taking logarithms yields

C\exp(-cn)\leq\delta \quad\Longleftrightarrow\quad \log(C)-cn\leq\log(\delta) \quad\Longleftrightarrow\quad n\geq\frac{1}{c}\log\left(\frac{C}{\delta}\right).

The equivalences hold because logarithms preserve order on positive numbers and division by $c$ preserves order. The exponential bound decreases as $n$ increases, so every larger sample size also satisfies the same probability requirement.

For a real threshold $r$, the smallest integer $n$ with $n\geq r$ is $\lceil r\rceil$. Indeed, by definition $\lceil r\rceil\geq r$, while every integer strictly smaller than $\lceil r\rceil$ is less than $r$. Applying this fact to the inverted Hoeffding and Bernstein thresholds proves the ceiling formulas and the minimality claims with respect to their respective upper bounds. It does not prove that smaller sample sizes fail the true probability requirement: a concentration upper bound may be conservative.

One-Sided Guarantees and Risk Interpretation

If the goal is only to control an upper deviation, a one-sided inequality can avoid the factor of two. For example, the one-sided Hoeffding bound for independent $X_i\in[a,b]$ is

P\left(\bar X-\frac{1}{n}\sum_{i=1}^n E[X_i]\geq\varepsilon\right) \leq \exp\left(-\frac{2n\varepsilon^2}{(b-a)^2}\right).

Inverting it replaces $\log(2/\delta)$ by $\log(1/\delta)$. This change is valid only if the desired event is genuinely one-sided; it does not provide the two-sided absolute-error guarantee. In learning, if $X_i$ are losses for a fixed predictor, then $\bar X$ is empirical risk and $E[X_i]$ is its population risk under iid sampling. The guarantee concerns that fixed predictor. Choosing a predictor after examining the same data is a different problem and is not made valid merely by inserting the selected predictor into this pointwise calculation.

Common Mistakes

Rounding down. A real threshold of $264.9159$ requires 265 observations, not 264. The ceiling is part of the calculation.
Dropping the factor of two without changing the event. The two-sided absolute-deviation bound uses $\log(2/\delta)$; $\log(1/\delta)$ corresponds to a one-sided form.
Calling a sufficient bound exact. The inverted inequality identifies a sample size that the bound certifies, not necessarily the true minimum for the underlying distribution.
Using Bernstein without its assumptions. The variance and centered-magnitude bounds must hold for the observations being analyzed.
Confusing pointwise and data-selected guarantees. A bound for one fixed predictor does not automatically control a predictor selected using the same sample.

Key takeaway: Identify the event and its assumptions, set the concentration upper bound no larger than $\delta$, solve for $n$, and round up. Report the result as a bound-based sufficient sample size, not as an exact description of the data-generating distribution.

Check Your Understanding

Use the stated assumptions and the correct one- or two-sided form when answering.

For $X_i\in[0,1]$, write the two-sided Hoeffding sample-size threshold for tolerance $\varepsilon$ and failure probability $\delta$.
Why must a real-valued sample-size threshold be rounded up rather than to the nearest integer?
Which logarithmic term belongs to a two-sided Hoeffding guarantee: $\log(1/\delta)$ or $\log(2/\delta)$? Explain.
Under Bernstein’s inequality, which assumptions are needed in addition to independence to use the sample-size formula?
Does satisfying an inverted concentration bound prove that the selected sample size is the exact minimum for the true distribution? Why or why not?