The following theorem is stated in these lecture notes of MIT on the mathematics of machine learning, right before section 2.3:

Let $\chi$ be a set. For any function $\hat h: \chi \to \{0,1\}$ built from $(x_1,y_1),...,(x_n,y_n) \in \chi \times \{0,1\}$ and for any sequence $a_n \to 0$ there exists a distribution $p_{X,Y}$ of $(X,Y)$ such that the indicator random variable $h^* = I(\mathbb{E}[Y|X]>\frac12)$ satisfies $\mathbb P[h^*(X) \neq Y]=0$ and yet $\forall n \geq 1:\mathbb E[\Bbb P[\hat h_n(X)\neq Y]] \geq a_n$.

I don't understand the statement of the theorem, and would like a more rigorous reformulation of it.

The logical order of quantifiers in this statement looks unclear: Are we given two random variables $X,Y$ and claim that there exists a mutual distribution $p_X,Y$ of them (with correct marginal distributions) with these properties? Or are we only specifying the random variables $X,Y$ after we fix $\epsilon$? What do we mean by "built from"? What is exactly the definition of $\hat h_n$, which indicates that we don't have a single $\hat h$, but rather a sequence of functions?

Moreover, I'd like to know the exact assumptions: Do we need $y_1,...,y_n$ to be distinct? Do we need $\chi$ to be an infinite set?

It seems to me like the claim on $h^*$ is equivalent to saying that $Y$ is a function of $X$ a.e. Is that true?

(If I will understand the content of the theorem, I plan to ask for a proof in a separate post.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.