Answers.Body: <p>You actually need to substitute <span class="math-container">$\delta=6/7$</span> to account for the extra &quot;<span class="math-container">$6$</span>&quot;, since in COROLLARY 2.3 to arrive at the minimum training sample size <span class="math-container">$m$</span> required for another ERM learner <span class="math-container">$E$</span> with a finite hypothesis class <span class="math-container">$H$</span> that contains <span class="math-container">$f$</span> to successfully learn the failed task which is tried by an arbitrary classification learner <span class="math-container">$A$</span> whose failure when samples are i.i.d. generated from a <em>specific</em> joint-distribution <span class="math-container">$D$</span> is proved by the No-Free-Lunch theorem 5.1, in the sense that with probability <em>at least</em> <span class="math-container">$1-\delta$</span> the successful ERM learner <span class="math-container">$E$</span>'s true risk is below <span class="math-container">$\epsilon$</span>.</p>
  <p>We can arrive at <span class="math-container">$\delta=6/7$</span> from the hint of exercise 1 of the same chapter of the book as follows. First we need Lemma B.1 which basically says that, <span class="math-container">$\forall a \in (0, 1), \forall r.v. Z.(Z \in [0,1] \land \mathbb{E}[Z]=\mu) \to \mathbb{P}[Z&gt;1-a] \ge \frac{\mu-(1-a)}{a} \land \mathbb{P}[z&gt;a] \ge \mu-a$</span></p>
  <p>Then from the critical result (5.2) as <span class="math-container">$\mathbb{E}[L_D(A(S))] \ge 1/4$</span>, we can substitute <span class="math-container">$Z=L_D(A(S)), \mu \ge 1/4$</span> along with <span class="math-container">$a=7/8, a=1/8$</span> to Lemma B.1, then we can easily obtain both <span class="math-container">$\mathbb{P}[Z&gt;1/8] \ge 1/7$</span> and <span class="math-container">$\mathbb{P}[Z&gt;1/8] \ge 1/8$</span>, so finally we merge them and get a single result for the failed arbitrary learner <span class="math-container">$A$</span> as <span class="math-container">$\mathbb{P}[L_D(A(S))&gt;1/8] \ge 1/7$</span>, which implies on the contrary the successful ERM learner <span class="math-container">$E$</span>'s true risk must be bounded by <span class="math-container">$\mathbb{P}[L_D(E(S)) \le 1/8] \ge 1/7$</span> since  for each case of sample <span class="math-container">$S$</span> with size <span class="math-container">$m$</span> drawn i.i.d. from <span class="math-container">$D$</span> where <span class="math-container">$A$</span> fails (<span class="math-container">$L_D(A(S))&gt;1/8$</span>) <span class="math-container">$E$</span> succeeds (<span class="math-container">$L_D(E(S)) \le 1/8$</span>), so <span class="math-container">$\delta=6/7$</span> in the sense that with probability <em>at least</em> <span class="math-container">$1/7$</span> the successful ERM learner <span class="math-container">$E$</span>'s true risk is below <span class="math-container">$1/8$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-29T02:06:13.833Z
Answers.Text: Not sure I follow your reasoning. If we substitute δ = 6/7, that means that the probability of failure (in this case having a generalization error more than 1/8) is 6/7. However, it is stated that P(L_D(A(S)) >= 1/8) is at least 1/7. This means that P(failure) >= 1/7 which implies that  δ = 1/7
Answers.UserDisplayName: fsafe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-29T03:06:30.500Z
Answers.Text: Your interpretation of failure is relative, as explained in my answer's last paragraph that the unavoidable failure of the free-lunch learner A corresponds to the success of a ERM learner E after learning from at least $m$ training samples in your quotation expressed as $P[L_D(E(S))≤1/8]≥1/7$ which is in the form of the usual 'success' version of PAC learning you can count on to match the $δ$ term.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-29T15:02:17.833Z
Answers.Text: A simpler way to think about this is that we are calculating an "at least one" probability. This is done by calculating the converse probability (6/7) and then using 1-p() to find what we really needed. That's where the 6/7 comes from.
Answers.UserDisplayName: David Hoelzer
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-28T00:52:24.467Z
Answers.LastActivityDate: 2024-12-28T01:52:56.960Z
Answers.LastEditDate: 2024-12-28T01:52:56.960Z
Answers.UserDisplayName: cinch
Body: <p>Section 5.1 of Understanding Machine Learning: From Theory to Algorithms 2014 by Shai Shalev-Shwartz and Shai Ben-David states:</p>
  <blockquote>
  <ol start="2">
  <li>With probability of at least <span class="math-container">$\frac{1}{7}$</span> over the choice of <span class="math-container">$S ∼ D^m$</span> we have that <span class="math-container">$L_D(A(S)) ≥ \frac{1}{8}$</span>. This theorem states that for every learner, there exists a task on which it fails, even though that task can be successfully learned by another learner. Indeed, a trivial successful learner in this case would be an ERM learner with the hypothesis class <span class="math-container">$H = \{f\}$</span>, or more generally, ERM with respect to any finite hypothesis class that contains f and whose size satisfies the equation <span class="math-container">$m ≥ 8log(\frac{7|H|}{6}$</span>) (see Corollary 2.3).</li>
  </ol>
  </blockquote>
  <p>Also according to the book:</p>
  <blockquote>
  <p>COROLLARY 2.3 Let H be a finite hypothesis class. Let <span class="math-container">$\delta \in (0, 1)$</span> and <span class="math-container">$\epsilon &gt; 0$</span> and let <span class="math-container">$m$</span> be an integer that satisfies
  <span class="math-container">$m ≥ \frac{log(\frac{|H|}{\delta})}{\epsilon}$</span>. Then, for any labeling function, <span class="math-container">$f$</span>, and for any distribution, <span class="math-container">$D$</span>, for which the
  realizability assumption holds (that is, for some <span class="math-container">$h \in H, L_{(D,f)}(h) = 0$</span>), with probability of at least <span class="math-container">$1 − \delta$</span> over the choice of an i.i.d. sample <span class="math-container">$S$</span> of size <span class="math-container">$m$</span>, we have that for every ERM hypothesis, <span class="math-container">$h_S$</span>, it holds that
  <span class="math-container">$L_{(D,f)}(h_S) ≤ \epsilon$</span>.</p>
  </blockquote>
  <p>I am trying to understand how <span class="math-container">$m ≥ 8log(\frac{7|H|}{6})$</span> was derived.</p>
  <p><span class="math-container">$\delta$</span> is the probability of failure which is when the generalization error, <span class="math-container">$L_D(A(S))$</span>, is greater than or equal to <span class="math-container">$\epsilon$</span>. Therefore <span class="math-container">$\delta = \frac{1}{7}$</span> and <span class="math-container">$\epsilon = \frac{1}{8}$</span>. Substituting this into COROLLARY 2.3 one gets:</p>
  <p><span class="math-container">$m ≥ \frac{log(\frac{|H|}{\frac{1}{7}})}{\frac{1}{8}} = 8log(7|H|)$</span>.</p>
  <p>Where is the 6 coming from in this case?</p>
  <p>I understand that if <span class="math-container">$\delta = \frac{6}{7}$</span> we would get <span class="math-container">$8log(\frac{7|H|}{6})$</span> but <span class="math-container">$\frac{6}{7}$</span> is <span class="math-container">$1 - \delta$</span> which is the probability of success and not the probability of failure.</p>
  
Tags: <computational-learning-theory><sample-complexity><hypothesis-class><no-free-lunch-theorems>
Title: How was $m ≥ 8log(\frac{7|H|}{6})$ derived here?
UserDisplayName: fsafe
ThreadText: # How was $m ≥ 8log(\frac{7|H|}{6})$ derived here?
  
  (Asked by: username_0 on 2024-12-26)
  
  Section 5.1 of Understanding Machine Learning: From Theory to Algorithms 2014 by Shai Shalev-Shwartz and Shai Ben-David states:
  
  > 2. With probability of at least $\frac{1}{7}$ over the choice of $S ∼ D^m$ we have that $L\_D(A(S)) ≥ \frac{1}{8}$. This theorem states that for every learner, there exists a task on which it fails, even though that task can be successfully learned by another learner. Indeed, a trivial successful learner in this case would be an ERM learner with the hypothesis class $H = \{f\}$, or more generally, ERM with respect to any finite hypothesis class that contains f and whose size satisfies the equation $m ≥ 8log(\frac{7|H|}{6}$) (see Corollary 2.3).
  
  Also according to the book:
  
  > COROLLARY 2.3 Let H be a finite hypothesis class. Let $\delta \in (0, 1)$ and $\epsilon > 0$ and let $m$ be an integer that satisfies
  > $m ≥ \frac{log(\frac{|H|}{\delta})}{\epsilon}$. Then, for any labeling function, $f$, and for any distribution, $D$, for which the
  > realizability assumption holds (that is, for some $h \in H, L\_{(D,f)}(h) = 0$), with probability of at least $1 − \delta$ over the choice of an i.i.d. sample $S$ of size $m$, we have that for every ERM hypothesis, $h\_S$, it holds that
  > $L\_{(D,f)}(h\_S) ≤ \epsilon$.
  
  I am trying to understand how $m ≥ 8log(\frac{7|H|}{6})$ was derived.
  
  $\delta$ is the probability of failure which is when the generalization error, $L\_D(A(S))$, is greater than or equal to $\epsilon$. Therefore $\delta = \frac{1}{7}$ and $\epsilon = \frac{1}{8}$. Substituting this into COROLLARY 2.3 one gets:
  
  $m ≥ \frac{log(\frac{|H|}{\frac{1}{7}})}{\frac{1}{8}} = 8log(7|H|)$.
  
  Where is the 6 coming from in this case?
  
  I understand that if $\delta = \frac{6}{7}$ we would get $8log(\frac{7|H|}{6})$ but $\frac{6}{7}$ is $1 - \delta$ which is the probability of success and not the probability of failure.
  
  **Tags:** computational-learning-theory, sample-complexity, hypothesis-class, no-free-lunch-theorems
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-12-28. Score: 0
  
  You actually need to substitute $\delta=6/7$ to account for the extra "$6$", since in COROLLARY 2.3 to arrive at the minimum training sample size $m$ required for another ERM learner $E$ with a finite hypothesis class $H$ that contains $f$ to successfully learn the failed task which is tried by an arbitrary classification learner $A$ whose failure when samples are i.i.d. generated from a *specific* joint-distribution $D$ is proved by the No-Free-Lunch theorem 5.1, in the sense that with probability *at least* $1-\delta$ the successful ERM learner $E$'s true risk is below $\epsilon$.
  
  We can arrive at $\delta=6/7$ from the hint of exercise 1 of the same chapter of the book as follows. First we need Lemma B.1 which basically says that, $\forall a \in (0, 1), \forall r.v. Z.(Z \in [0,1] \land \mathbb{E}[Z]=\mu) \to \mathbb{P}[Z>1-a] \ge \frac{\mu-(1-a)}{a} \land \mathbb{P}[z>a] \ge \mu-a$
  
  Then from the critical result (5.2) as $\mathbb{E}[L\_D(A(S))] \ge 1/4$, we can substitute $Z=L\_D(A(S)), \mu \ge 1/4$ along with $a=7/8, a=1/8$ to Lemma B.1, then we can easily obtain both $\mathbb{P}[Z>1/8] \ge 1/7$ and $\mathbb{P}[Z>1/8] \ge 1/8$, so finally we merge them and get a single result for the failed arbitrary learner $A$ as $\mathbb{P}[L\_D(A(S))>1/8] \ge 1/7$, which implies on the contrary the successful ERM learner $E$'s true risk must be bounded by $\mathbb{P}[L\_D(E(S)) \le 1/8] \ge 1/7$ since for each case of sample $S$ with size $m$ drawn i.i.d. from $D$ where $A$ fails ($L\_D(A(S))>1/8$) $E$ succeeds ($L\_D(E(S)) \le 1/8$), so $\delta=6/7$ in the sense that with probability *at least* $1/7$ the successful ERM learner $E$'s true risk is below $1/8$.
  
  > **Comments:**
  > **username_0**: Not sure I follow your reasoning. If we substitute δ = 6/7, that means that the probability of failure (in this case having a generalization error more than 1/8) is 6/7. However, it is stated that P(L_D(A(S)) >= 1/8) is at least 1/7. This means that P(failure) >= 1/7 which implies that  δ = 1/7  
  > **username_1**: Your interpretation of failure is relative, as explained in my answer's last paragraph that the unavoidable failure of the free-lunch learner A corresponds to the success of a ERM learner E after learning from at least $m$ training samples in your quotation expressed as $P[L_D(E(S))≤1/8]≥1/7$ which is in the form of the usual 'success' version of PAC learning you can count on to match the $δ$ term.  
  > **username_2**: A simpler way to think about this is that we are calculating an "at least one" probability. This is done by calculating the converse probability (6/7) and then using 1-p() to find what we really needed. That's where the 6/7 comes from.  
  
  ---
  
  