# Does Hoeffding's bound give tighter bound than Central Limit Theorem does on sample dependency?

From Central Limit Theorem, we know that $$\mu - \bar{x}$$ has a variance of $$\frac{\sigma^2}{n}$$ where $$\sigma^2$$ is the population variance. We can roughly interpret it is as $$P(|\mu - \bar{x}|\ge\epsilon)$$ is inversely proportional to sample size $$n$$. On the other hand, the version of the Hoeffding' inequality that is used in PAC bound derivation states that $$P[|\mu - \bar{x}| \geq \varepsilon] \leq 2e^{-2n\varepsilon^2}$$. Here the probability of $$\bar{x}$$ deviating from $$\mu$$ decays exponentially w.r.t. sample size $$n$$. So apparently the Hoeffding inequality gives a tighter bound than CTL does. Is it because there are more assumptions made for Hoeffding inequality's derivation?

• Hoeffding holds for subgaussians, a special type of random variable which have concentration around their mean at least as tight as some Gaussian. I’m also not convinced by your derivation for the central limit theorem, as if you treat your sample mean as Gaussian, then you will get the same bound as from Hoeffding. However, this bound is completely wrong and this heuristic should not be used. Commented Jul 7, 2023 at 16:41
• yes your view is valid, I shouldn't have explained it this way. My actual derivation involves finding the PDF corresponding to the Hoeffding' inequality I stated above which is $4n|\bar{x}-\mu|e^{-2n(\bar{x}-\mu)^2}$ by differentiating the CDF corresponding to the Hoeffding' inequality stated above. then I wrote out the variance of this PDF by definition (i.e., $VAR(X) = E[X^2]-E[X]^2$) and found out the $E[X^2]$ term has an exponential decaying term w.r.t. $n$. And from CLT we know the variance of $|\bar{x}-\mu|$ is proportional to the $\frac{1}{n}$ which is a slower than exponential decay.
– Sam
Commented Jul 7, 2023 at 17:00
• “From CLT we know the variance…” this is irrelevant of CLT and is also not the conclusion of CLT. The sample mean has variance $1/n$ from a simple computation. Also, the sample mean also has variance $1/n$ in Hoeffding’s lemma, so this argument cannot be plausible. It is true that for a random variable with only the assumption of finite variance, you cannot deduce tight concentration around the mean. However, your arguments are not the correct way to go about it. Commented Jul 7, 2023 at 17:18
• @AndrewZhang 'Also, the sample mean also has variance 1/n in Hoeffding’s lemma, so this argument cannot be plausible.' could you elaborate on how to see this is the case? Thank you
– Sam
Commented Jul 8, 2023 at 2:15
• 'this is irrelevant of CLT and is also not the conclusion of CLT. The sample mean has variance 1/n from a simple computation' not sure about the 'simple computation' part but from the following two sources it is indeed part of CLT: cs.toronto.edu/~yuvalf/CLT.pdf (p.1) en.wikipedia.org/wiki/Central_limit_theorem#Classical_CLT
– Sam
Commented Jul 8, 2023 at 2:19

To understand the conclusion of the central limit theorem, it is necessary to understand weak convergence. We say a sequence of random variables $$X_n$$ converges weakly to $$X$$, denoted $$X_n\Rightarrow X$$, if $$P(X_n\leq t) \to P(X\leq t)$$ as $$n\to\infty$$ for all $$t$$ such that $$t\mapsto P(X\leq t)$$ is continuous. Two equivalent definitions of weak convergence are

1. $$E[f(X_n)]\to E[f(X)]$$ as $$n\to\infty$$ for all continuous and bounded $$f$$.
2. $$P(X_n \in B) \to P(X\in B)$$ as $$n\to\infty$$ for all continuity sets $$B$$, that is, $$P(X\in \partial B) = 0$$, where $$\partial B = \bar B - \overset{\circ}{B}$$ denotes the boundary.

It turns out that if $$t\mapsto P(X\leq t)$$ is continuous, then weak convergence can be upgraded to $$\sup_{t\in \mathbb R}|P(X\leq t)-P(X_n\leq t)| \underset{n\to\infty}{\longrightarrow}0$$ This brings us to the (classical) central limit theorem, which asserts that for any sequence of i.i.d random variables with mean $$\mu$$ and variance $$\sigma^2<\infty$$ that $$\sqrt n(\hat \mu - \mu)\Rightarrow \mathcal N(0,\sigma^2)$$ At this point, it is tempting to use the normal approximation to do computations, which leads to the question of when this is justified. The obvious answer is that anything which relates to weak convergence is justified, though still only at a very heuristic level. Indeed, it would seem that it is OK to approximate $$P(\sqrt n|\hat \mu-\mu| \leq \epsilon) \approx P(|Z|\leq \epsilon),\quad Z\sim\mathcal N(0,1)$$ What is not justified is to use this to make qualitative statements about the rate of convergence of the sample mean $$\hat \mu$$ to $$\mu$$. Indeed, gaussians have extremely tight concentration around their mean: $$P(Z\geq t) \leq \frac{1}{t}\frac{1}{\sqrt{2\pi}}e^{-t^2/2},\quad t>0$$ There is no chance at all for random variable $$X$$ with only finite variance to achieve such concentration. In fact, such tight concentration would imply the moment generating function of $$X^2$$ exists. The point is that one cannot and should not make qualitative statements using the approximation provided by the central limit theorem.

In fact, even the use of such an approximation is not formally justified by the classical central limit theorem, but it is standard practice in statistics. It is possible to do so using the Berry-Esseen central limit theorem, but then you also do need finite third moment.

More generally, one can use the central limit theorem to do approximations of continuous functionals. (Again, this is heuristic and not at all precise, but this is standard practice.) It turns out that many quantities of interest are functions of the distribution function $$F$$. For example, $$F \mapsto \int g(x)\,dF(x),\quad F\mapsto \|F-F_0\|_\infty$$ Using the central limit theorem to approximate functionals therefore boils down to whether $$(X,d)\ni F \mapsto \gamma(F) \in \mathbb R$$ is continuous, where $$X$$ is the space of distribution functions and $$d(F,G) = \|F-G\|_\infty$$. It is well known that the functional $$F\mapsto \int x^p\,dF(x), p \in \mathbb N$$ is not continuous. (It is easy to construct a counterexample if you know about dominated convergence. There are special conditions where it is continuous, but not in general.) In other words, the central limit theorem does not assert that $$\mathrm{Var}(\hat \mu) = \frac{\sigma^2}{n},\quad \hat \mu \equiv \hat \mu(n)$$, nor is the approximation $$\mathrm{Var}(\hat \mu) \approx \frac{1}{n}$$ justified, not even heuristically. Rather, this conclusion follows from $$\mathrm{Var}\left(\frac{S_n}{n}\right) = \frac{1}{n^2}\mathrm{Var}(S_n) = \frac{1}{n^2} \sum_{i=1}^n \mathrm{Var}(X_n) = \frac{1}{n}$$

As for Hoeffding's inequality, it is necessary to introduce the notion of subgaussian random variables. Call $$X$$ $$\sigma^2$$ subgaussian if $$E[e^{\lambda (X-E[X])}]\leq e^{\lambda^2\sigma^2/2},\quad \forall\,\lambda \in \mathbb R$$ For convenience, and really with no loss of generality, I'll take $$X$$ to be centered from now on. If $$X$$ is $$\sigma^2$$ subgaussian and $$t>0$$, then $$P(X\geq t) = P(e^{\lambda X} \geq e^{\lambda t}) \leq \inf_{\lambda>0}e^{-\lambda t}E[e^{\lambda X}] \leq e^{-t^2/(2\sigma^2)}$$ Symmetry yields $$P(|X|\geq t) \leq 2e^{-t^2/(2\sigma^2)},\quad t>0$$ It is easy to see that the sum of independent subgaussians is also subgaussian with parameter given by the sum of the respective parameters. In particular, if $$X_1,\dots,X_n$$ are i.i.d $$\sigma^2$$ subgaussian, then $$P(|S_n|\geq t)\leq 2e^{-t^2/(2n\sigma^2)} \implies P(|n^{-1}S_n|\geq t)\leq 2e^{-nt^2/(2\sigma^2)}$$ This of course begs the question of which random variables are subgaussian. It is a standard exercise (e.g. see Wainwright High Dimensional Statistics Chapter 2) to show that if $$X\in [a,b]$$ almost surely, then $$X$$ is $$\left(\frac{b-a}{2}\right)^2$$ subgaussian. This yields Hoeffding's inequality: If $$X_1,\dots,X_n$$ are independent with $$X_i\in[a_i,b_i]$$ almost surely, then $$P\left(\left \lvert \frac{1}{n}\sum_{i=1}^n X_i - E[X_i]\right\rvert \geq t\right) \leq 2\exp\left(\frac{-2n^2t^2}{\sum_{i=1}^n (b_i-a_i)^2} \right),\quad t>0$$ Finally, if $$X$$ is $$\sigma^2$$ subgaussian, then it is easy to show $$\mathrm{Var}(X) \leq \sigma^2$$. Note that this method of obtaining concentration is "blind" to the details of the underlying distribution, and that it is of course possible to obtain even tighter concentration results given more concrete details about the distribution. Indeed, if you look at how Hoeffding's inequality is derived, it follows from showing $$X\in [a,b]$$ almost surely is $$(b-a)^2/4$$ subgaussian. In fact, we have $$\mathrm{Var}(X)\leq (b-a)^2/4$$, so in some heuristic sense, because Hoeffding's inequality deals with the most general case, it necessarily also assumes the worst possible concentration of measure for the random variables in question.

(There is an alternate standard argument for Hoeffding's, but I prefer the presentation here as it is more "probabilistic," whereas the other is strictly analytic).

• hey, thank you so much for this detailed discussion regarding CLT and standard error. just wondering if you can shed some light on the variance in Hoeffding’s lemma as well :)
– Sam
Commented Jul 8, 2023 at 14:27
• Not sure what you mean by variance in Hoeffding's lemma? Commented Jul 8, 2023 at 14:57
• oh it is from your comment 'Also, the sample mean also has variance 1/n in Hoeffding’s lemma, so this argument cannot be plausible.' My understanding of what you meant is given Hoeffding's inequality, we can find the corresponding PDF and then somehow get a close-form expression of its variance. I tried but my expression derived from $E[X^2] - (E[X])^2$ is hard to simplify.
– Sam
Commented Jul 11, 2023 at 14:10
• I interpreted your argument as you tried to deduce a concentration inequality for the sample mean by using the variance. My comment was referring to how this attempt doesn't work. Admittedly, what I wrote wasn't really clear, and it would probably be best to ignore what I wrote. I'll edit my answer to include a bit more detail on Hoeffding's. Commented Jul 11, 2023 at 16:57
• thanks for your very detailed explanation on Hoeffding’s inequality! However, there is still something I find baffling: I think it is reasonable to view it as a tail probability (i.e., a form of CDF) for the R.V. $X$. But if I take the derivative w.r.t. t (i.e., the deviation of $X_i$ from $E[X_i]$), there will be a $t$ appearing in front of the exponential term. Now if we do a change of variable to express $t$ in terms of $X_i$ and $E[X_i]$, $X_i$ will appear in front of the exponential term. Clearly this is not a sub-Gaussian. I wonder what have gone wrong in my sanity check.
– Sam
Commented Jul 12, 2023 at 14:02