From the book "Understanding Machine Learning: From Theory to Algorithms", The Realizability Assumption is defined as follows:

There exists $h^{\star}\in \mathcal{H}$ s.t. $L_{(D,f)}(h^{\star})=0$. Note that this assumption implies that with probability 1 over random samples, $S$, where the instances of $S$ are are sampled according to $\mathcal{D}$ and labeled by $f$, we have $L_{S}(h^{\star})=0$. The realizability assumption implies that for every ERM hypothesis we have that $L_{S}(h_S)=0$. However, we are interested in the true risk of $h_S$, $L_{(D,f)}(h_S)$, rather than its empirical risk.

Isn't the true risk $\big{(} L_{(D,f)}(h_S) \big{)}$ already ZERO by the definition of the realizability assumption?, I mean isn't $L_{S}(h_S)=0$ because $L_{(D,f)}(h_S)=0$? and if it isn't, why then the realizability assumption implies that $L_{S}(h_S)=0$?

  • $\begingroup$ Does $h_S = h^*$ for all $S$? $\endgroup$
    – jbowman
    Commented Feb 21, 2023 at 21:15
  • $\begingroup$ @jbowman Why not? $\endgroup$
    – ammar
    Commented Feb 22, 2023 at 22:35
  • $\begingroup$ @jbowman what are you implying by that? if we assume they're not equal the why would the realizability assumption imply $L_S(h_S)=0$? $\endgroup$
    – ammar
    Commented Feb 23, 2023 at 21:25
  • $\begingroup$ Just because $L_S(h_S)=0$ doesn't mean that $L_{(D,f)}(h_S) = 0$. For the latter to be true, $h_S$ must equal $h^*$, because it's $h^*$ for which $L_{(D,f)}(h) = 0$ ,but $h_S$ is associated with a particular sample, not the population, so there's no reason why that would be so. $\endgroup$
    – jbowman
    Commented Feb 23, 2023 at 21:30
  • $\begingroup$ Does this link help: stats.stackexchange.com/questions/304991/… $\endgroup$
    – jbowman
    Commented Feb 23, 2023 at 21:35


Your Answer

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

Browse other questions tagged or ask your own question.