Answers.Body: <p>Indeed by lemma 4.2, once the training set <span class="math-container">$S$</span> is <span class="math-container">$(\epsilon/2)$</span>-representative the ERM learning rule is guaranteed to be APAC learnable <span class="math-container">$L_D(h_s)\leq \min_{h}L_D(h)+\epsilon$</span>. However, it's not clear based on what theorem you arrived at <span class="math-container">$\min_{h}L_D(h) \leq \min_{h}L_S(h)+\epsilon$</span>. Since the <span class="math-container">$h$</span> on both sides may not be the same hypothesis in the hypothesis class under min operator, uniform convergence property doesn't ensure this step at all.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-15T06:21:49.203Z
Answers.LastActivityDate: 2024-03-15T06:21:49.203Z
Answers.UserDisplayName: cinch
Body: <p>I am currently studying &quot;Understanding Machine Learning from Theory to Practice&quot; written by Shai Shalev-Shwartz and Shai Ben-David. I want to understand how i can use the Definitions and Results of the Theory he describes in Practice.</p>
  <p>Consider the problem of fitting a one dimensional polynomial to data; namely,
  our goal is to learn a function, <span class="math-container">$h : R → R$</span> , and as prior knowledge we consider
  the hypothesis class of polynomials up to degree 10. Our class <span class="math-container">$H$</span> has VCdim(<span class="math-container">$H$</span>)=11 so with the fundamental theorem of statistical learning it is APAC learnable with ERM. If i fix my <span class="math-container">$\epsilon,\delta \in (0,1)$</span>, then if my sample size is equal to
  <span class="math-container">$ C_2\frac{11+\log(1/\delta)}{\epsilon^2}$</span> i can be sure that with probability of atleast <span class="math-container">$1-\delta$</span>, ERM will output a hypothesis with
  <span class="math-container">\begin{equation}
  L_D(h_s)\leq \min_{h}L_D(h)+\epsilon.
  \end{equation}</span>
  <span class="math-container">$C_2$</span> is a constant and <span class="math-container">$h_S$</span> is the hypotheis of the ERM algorithm. Now in practical Terms, this doesnt tell me anything about the quality of my Model. Because we dont know the underlying Distribution <span class="math-container">$D$</span> we can't compute <span class="math-container">$L_D(h)$</span> for any <span class="math-container">$h\in H$</span>. But i can compute <span class="math-container">$L_S(h)$</span> for every <span class="math-container">$h\in H$</span> in particular <span class="math-container">$L_S(h_S)$</span>. My intuition is then that we could use the uniform-convergence property of our class <span class="math-container">$H$</span> (VCdim(H) is finite) to get a bound for how much <span class="math-container">$L_D(h_S)-L_S(h_S)$</span> differ. With probability of atleast <span class="math-container">$1-\delta$</span>
  <span class="math-container">\begin{equation}
  L_D(h_S)\leq \min_{h}L_D(h)+\epsilon \leq \min_{h}{L_S(h)+\epsilon}+\epsilon=L_S(h_S)+2\epsilon
  \end{equation}</span>
  I know my the value of <span class="math-container">$\epsilon$</span> so i can calculate the above expression. For example with <span class="math-container">$\epsilon=0.01$</span> and <span class="math-container">$L_S(h_S)=0.01$</span> i can gurantee that the true error of my hypotheis <span class="math-container">$h_S$</span> is at most <span class="math-container">$\leq 0.03$</span> with probability <span class="math-container">$1-\delta$</span>.</p>
  
Tags: <machine-learning><pac-learning>
Title: Using the definition of APAC learning and uniform convergence in practice
UserDisplayName: MathAccount12
ThreadText: # Using the definition of APAC learning and uniform convergence in practice
  
  (Asked by: username_0 on 2024-03-07)
  
  I am currently studying "Understanding Machine Learning from Theory to Practice" written by Shai Shalev-Shwartz and Shai Ben-David. I want to understand how i can use the Definitions and Results of the Theory he describes in Practice.
  
  Consider the problem of fitting a one dimensional polynomial to data; namely,
  our goal is to learn a function, $h : R → R$ , and as prior knowledge we consider
  the hypothesis class of polynomials up to degree 10. Our class $H$ has VCdim($H$)=11 so with the fundamental theorem of statistical learning it is APAC learnable with ERM. If i fix my $\epsilon,\delta \in (0,1)$, then if my sample size is equal to
  $ C\_2\frac{11+\log(1/\delta)}{\epsilon^2}$ i can be sure that with probability of atleast $1-\delta$, ERM will output a hypothesis with
  \begin{equation}
  L\_D(h\_s)\leq \min\_{h}L\_D(h)+\epsilon.
  \end{equation}
  $C\_2$ is a constant and $h\_S$ is the hypotheis of the ERM algorithm. Now in practical Terms, this doesnt tell me anything about the quality of my Model. Because we dont know the underlying Distribution $D$ we can't compute $L\_D(h)$ for any $h\in H$. But i can compute $L\_S(h)$ for every $h\in H$ in particular $L\_S(h\_S)$. My intuition is then that we could use the uniform-convergence property of our class $H$ (VCdim(H) is finite) to get a bound for how much $L\_D(h\_S)-L\_S(h\_S)$ differ. With probability of atleast $1-\delta$
  \begin{equation}
  L\_D(h\_S)\leq \min\_{h}L\_D(h)+\epsilon \leq \min\_{h}{L\_S(h)+\epsilon}+\epsilon=L\_S(h\_S)+2\epsilon
  \end{equation}
  I know my the value of $\epsilon$ so i can calculate the above expression. For example with $\epsilon=0.01$ and $L\_S(h\_S)=0.01$ i can gurantee that the true error of my hypotheis $h\_S$ is at most $\leq 0.03$ with probability $1-\delta$.
  
  **Tags:** machine-learning, pac-learning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-03-15. Score: 0
  
  Indeed by lemma 4.2, once the training set $S$ is $(\epsilon/2)$-representative the ERM learning rule is guaranteed to be APAC learnable $L\_D(h\_s)\leq \min\_{h}L\_D(h)+\epsilon$. However, it's not clear based on what theorem you arrived at $\min\_{h}L\_D(h) \leq \min\_{h}L\_S(h)+\epsilon$. Since the $h$ on both sides may not be the same hypothesis in the hypothesis class under min operator, uniform convergence property doesn't ensure this step at all.
  
  
  ---
  
  