1
$\begingroup$

I've got a question to the Hoeffding Inequality which states, that for data points $X_1, \dots, X_n \in X$, which are i.i.d. according to a probability measure $P$ on $X$, we find an upper bound for:

$$P\left(\left|{\sum_{I=1}^n}X_i - \int_XX_1dP(x)\right| \ge \varepsilon\right) \le \alpha.$$

In machine learning proofs, this is often used for bounding functions, hence we get for a function $f: X \rightarrow \mathbb{R}$ a bound:

$$P\left(\left|{\sum_{I=1}^n}f(X_i) - \int_Xf(X_1)dP(x)\right| \ge \varepsilon\right) \le \alpha.$$

I don't understand, why we are able to obtain this bound with the same probability measure $P$. Why don't we need to look at a different / transformed probability measure $P_f$?

$\endgroup$
3
  • $\begingroup$ Applying a function preserves independence. That's a question for MSE imo. $\endgroup$ Jul 14, 2022 at 7:55
  • $\begingroup$ That's only a matter of notation. Call $f(X_i)$ $X_i'$. $\endgroup$ Jul 14, 2022 at 8:47
  • $\begingroup$ Ah, thanks! That means, I can use this bound also for different functions uniformly, using the same probability space on the Random variables X_i: $P(|\sum f(X_i)-\int_Xf(X_1)dP(x)| \ge \epsilon \cap |\sum g(X_i)-\int_Xg(X_1)dP(x)| \ge \epsilon) \le 2\alpha$ ? $\endgroup$ Jul 14, 2022 at 9:36

1 Answer 1

2
$\begingroup$

I think this question is more on the definition side. Often times people don't distinguish $\mathbb{P}$ the probability measure in the underlying probability space, and $P$ the distribution or the probability measure induced by a random variable. Also people tend to use $P$ directly, without making any explicit reference to the original probability space. This can cause confusion.

The first inequality may be restated more precisely as follows. Let $X_i: \Omega \to \mathcal{X}$ be a real-valued Borel measurable map from the probability space $(\Omega, \mathcal{F}, \mathbb{P})$, for each $i=1,...,n$. Let $X_i$'s have a common distribution $P$. Then the first inequality should be $$ \mathbb{P}\Big\{ \omega \in \Omega : \Big| \sum_{i=1}^n X_i(\omega) - \int_{\mathcal{X}} x P(dx) \Big| > \varepsilon \Big\} \leq \alpha, $$ which can be written as $$ \mathbb{P}\Big\{ \Big| \sum_{i=1}^n X_i - \int_{\mathcal{X}} x P(dx) \Big| > \varepsilon \Big\} \leq \alpha. $$ Notice $\mathbb{P}$ should be used instead of the distribution $P$. In fact, the first inequality in your post doesn't really make sense when you read it rigorously: Since $P$ is a probability measure on $\mathcal{X}$, the argument of function $P$ should be a subset of $\mathcal{X}$.

The second inequality should be of the form $$ \mathbb{P}\Big\{ \omega \in \Omega : \Big| \sum_{i=1}^n f(X_i(\omega)) - \int_{\mathcal{X}} f(x) P(dx) \Big| > \varepsilon \Big\} \leq \alpha'. $$ Notice you're essentially taking probability of some collection of outcomes in $\Omega$, which has nothing to do with the function $f$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.