The necessary and sufficient conditions for learning to occur in the task of binary classification are among the fundamental results in learning theory.

In the sources I'm familiar with, this theorem is stated for hypothesis class of functions from the instance domain $\mathcal X$ to $\{0,1\}$, w.r.t. the 0-1 loss (see e.g. page 72 here).

From following the canonical proofs, my question arise: If $\mathcal H$ is a class of real valued functions, but the loss is a 0-1 function, i.e. $\mathcal X \times \mathbb R \rightarrow \{0,1\}$, it seems that all remains the same: the bounds and the conditions of learnability still hold.

Here it seems that indeed this result hold for any hypothesis class, as long as the loss is 0-1 (Bernoulli random variable).

In order to make this less abstract, consider the following example:

for $\mathcal Z = \mathbb R \times \mathbb R$, let $\mathcal H$ to the class of linear functions with one variable, $\mathcal H=\{ax+b:(a,b)\in \mathbb R^2 \}$, and let the loss function be : $$l(z,h)=\begin{cases} 1 & |h(x)-y|<1 \\ 0 & |h(x)-y|\geq 1 \end{cases} $$

where $z=(x,y)$. Can the "fundamental" theorem be applied for this case as well? Does the classification framework can be applied here? Does it hold that UC $\Leftrightarrow$ finite VC $\Leftrightarrow$ ERM minimization? are the bounds the same?


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.