Answers.Body: <p>What I was missing is the condition in the definition: &quot;S is labeled by a function <span class="math-container">$f$</span>&quot;.</p>
  <p>Since <span class="math-container">$(\mathcal{},f)(ℎ^{\star})=0$</span> and <span class="math-container">$h^{\star}\in\mathcal{H}$</span>, then for every ERM hypothesis <span class="math-container">$h_{\mathcal{S}}=ERM_{\mathcal{H}}(\mathcal{S})\in \underset{h\in{\mathcal{H}}}{argmin} L_{\mathcal{S}}(h)$</span> learned from <span class="math-container">$S$</span> that minimizes the loss defined by:</p>
  <p><span class="math-container">$$
  \begin{align}
  L_{S}(h):=\frac{|\{i \in [m]: h(x_{i}) \ne f(x_{i}) = y_{i}\}|}{m},
  \end{align}
  $$</span></p>
  <p>we simply have that <span class="math-container">$L_{\mathcal{S}}(h_{\mathcal{S}}))=0$</span> otherwise choose <span class="math-container">$h^{\star}$</span> for <span class="math-container">$h_{\mathcal{S}}$</span>.</p>
  <p>This is different from, say, the agnostic ERM learner where this condition is relaxed by replacing the labeling function <span class="math-container">$f$</span> by a data generating distribution instead.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-10T06:14:03.663Z
Answers.LastActivityDate: 2023-10-10T06:14:03.663Z
Answers.UserDisplayName: Tran Khanh
Body: <p>I'm quoting <em>Understanding Machine Learning: From Theory to Algorithms</em>, Cambridge University Press, 2014:</p>
  <blockquote>
  <p>Definition 2.1 (The Realizability Assumption). There exists <span class="math-container">$h^{\star} \in \mathcal{H}$</span> s.t. <span class="math-container">$L(D, f )(h^{\star}) = 0$</span>. Note that this assumption implies that with probability 1 over random samples, S, where the instances of S are sampled according to D and are labeled by f, we have <span class="math-container">$L_{S}(h^{\star})=0$</span>.</p>
  </blockquote>
  <p>My understanding of the second sentence in this definition is that because <span class="math-container">$h^{\star}$</span> satisfies the equation <span class="math-container">$L(D, f )(h^{\star}) = 0$</span>, so every prediction made by <span class="math-container">$h^{\star}$</span> on every example <span class="math-container">$x$</span> sampled from the domain set <span class="math-container">$\mathcal{X}$</span> is correct (otherwise the loss <span class="math-container">$L(D, f )(h^{\star})$</span> will not equal 0). Equivalently, every prediction made by <span class="math-container">$h^{\star}$</span> is correct. Therefore, for any sample <span class="math-container">$S$</span> sampled from <span class="math-container">$\mathcal{X}$</span> we have <span class="math-container">$L_{S}(h^{\star})=0$</span>.</p>
  <p>However what I'm stumble upon is when the author further collaborates on this def.:</p>
  <blockquote>
  <p>The realizability assumption implies that for every ERM hypothesis we have that <span class="math-container">$L_{S}(h_{S})=0$</span>.</p>
  </blockquote>
  <p>I don't quite get what the author means here since every ERM hypothesis <span class="math-container">$h_{S}$</span> is found based on some subjective minimization algorithm, which in turn, depends on a number of other factors, such as the choice of the loss function, the sample size, the algorithm complexity and thus may not always converge to <span class="math-container">$h^{\star}$</span>?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-09T11:02:49.480Z
Comments.Text: one thing is knowing that there is a solution, another one is to find it... we know that there is a solution to any sudoku, but it's hard to find
Comments.UserDisplayName: Alberto
Tags: <machine-learning><ai-basics><hypothesis-class>
Title: Realizability Assumption: Why is that for every ERM hypothesis $L_{S}(h_{S})=0$
UserDisplayName: Tran Khanh
ThreadText: # Realizability Assumption: Why is that for every ERM hypothesis $L_{S}(h_{S})=0$
  
  (Asked by: username_0 on 2023-10-08)
  
  I'm quoting *Understanding Machine Learning: From Theory to Algorithms*, Cambridge University Press, 2014:
  
  > Definition 2.1 (The Realizability Assumption). 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 sampled according to D and are labeled by f, we have $L\_{S}(h^{\star})=0$.
  
  My understanding of the second sentence in this definition is that because $h^{\star}$ satisfies the equation $L(D, f )(h^{\star}) = 0$, so every prediction made by $h^{\star}$ on every example $x$ sampled from the domain set $\mathcal{X}$ is correct (otherwise the loss $L(D, f )(h^{\star})$ will not equal 0). Equivalently, every prediction made by $h^{\star}$ is correct. Therefore, for any sample $S$ sampled from $\mathcal{X}$ we have $L\_{S}(h^{\star})=0$.
  
  However what I'm stumble upon is when the author further collaborates on this def.:
  
  > The realizability assumption implies that for every ERM hypothesis we have that $L\_{S}(h\_{S})=0$.
  
  I don't quite get what the author means here since every ERM hypothesis $h\_{S}$ is found based on some subjective minimization algorithm, which in turn, depends on a number of other factors, such as the choice of the loss function, the sample size, the algorithm complexity and thus may not always converge to $h^{\star}$?
  
  **Tags:** machine-learning, ai-basics, hypothesis-class
  > **Comments:**
  > **username_1**: one thing is knowing that there is a solution, another one is to find it... we know that there is a solution to any sudoku, but it's hard to find  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2023-10-10. Score: 1 | Accepted answer
  
  What I was missing is the condition in the definition: "S is labeled by a function $f$".
  
  Since $(\mathcal{},f)(ℎ^{\star})=0$ and $h^{\star}\in\mathcal{H}$, then for every ERM hypothesis $h\_{\mathcal{S}}=ERM\_{\mathcal{H}}(\mathcal{S})\in \underset{h\in{\mathcal{H}}}{argmin} L\_{\mathcal{S}}(h)$ learned from $S$ that minimizes the loss defined by:
  
  $$
  \begin{align}
  L\_{S}(h):=\frac{|\{i \in [m]: h(x\_{i}) \ne f(x\_{i}) = y\_{i}\}|}{m},
  \end{align}
  $$
  
  we simply have that $L\_{\mathcal{S}}(h\_{\mathcal{S}}))=0$ otherwise choose $h^{\star}$ for $h\_{\mathcal{S}}$.
  
  This is different from, say, the agnostic ERM learner where this condition is relaxed by replacing the labeling function $f$ by a data generating distribution instead.
  
  
  ---
  
  