Answers.Body: <p>Here's a rough proof sketch that might be clearer, but is probably less precise, than the solution you already have.</p>
  
  <ol>
  <li><p>We have a sequence of hypotheses classes, but the problem actually only asks us to consider a single class. A hypothesis class is a set of possible models for classification that differ only in a set of parameter values.</p></li>
  <li><p>We are told that the algorithm for selecting a hypothesis from <span class="math-container">$H_n$</span> uses only <span class="math-container">$O(n)$</span> samples from the training set, and that using those samples, it takes the algorithm <span class="math-container">$O(n)$</span> to find the hypothesis that minimizes the empirical risk for the class, provided that the ERM minimizing hypothesis has an empirical risk of 0 (i.e. it is realizable). </p></li>
  <li><p>Further, if we pick some hypothesis at random from the class, we are told that the cost of determining its exact empirical risk is <span class="math-container">$O(nm)$</span>, where <span class="math-container">$m$</span> is the total size of the training set, and <span class="math-container">$n$</span> is just a parameter associated with this particular hypothesis class <span class="math-container">$H_n$</span>.</p></li>
  <li><p>Observer that, in the unrealizable case, we cannot use the algorithm to find the risk minimizing hypothesis (which, by 2, runs in O(n)). No other algorithm is mentioned, but we are also told (in 2) that the algorithm can construct a hypothesis from <span class="math-container">$O(n)$</span> datapoints in <span class="math-container">$O(n)$</span> time, even if no feasible hypothesis can be found for those <span class="math-container">$O(n)$</span> points.</p></li>
  <li><p>Suppose we wanted to find the hypothesis with minimal risk via brute force. We could compute every subset of the training dataset that is of the size <span class="math-container">$O(n)$</span> that the algorithm may be able to use to construct a hypothesis in <span class="math-container">$O(n)$</span> time. There are <span class="math-container">$O(m^{O(n)})$</span> such subsets (e.g. <span class="math-container">$m*(m-1)/2$</span> possible pairs, <span class="math-container">$m*(m-1)*(m-2)/6$</span> possible triplets, etc.). </p></li>
  <li><p>Since there are <span class="math-container">$O(m^{O(n)})$</span> possible subsets of size <span class="math-container">$O(n)$</span>, and our algorithm can compute a candidate hypothesis in <span class="math-container">$O(n)$</span> time, it costs us <span class="math-container">$O(nm^{O(n)})$</span> to find all possible hypotheses that our algorithm can produce for this dataset.</p></li>
  <li><p>Since it costs us <span class="math-container">$O(nm)$</span> time to compute the emperical risk of a hypothesis generated by this algorithm, we can minimize risk by computing risk for each of the <span class="math-container">$O(m^{O(n)})$</span> hypotheses we made in step 6, and then selecting the one with lowest empirical risk. This costs us <span class="math-container">$O(mnm^{O(n)})$</span> time total. Our total runtime is then the sum of the cost to generate the models in step 6, and the cost to evaluate them here in step 7: <span class="math-container">$O(mnm^{O(n)})+O(nm^{O(n)})$</span>.</p></li>
  <li><p>Since <span class="math-container">$O(mnm^{O(n)})+O(nm^{O(n)}) \in O(mnm^{O(n)})$</span>, we have proven the desired bound on runtime.</p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-11T03:09:49.190Z
Answers.LastActivityDate: 2019-10-11T03:09:49.190Z
Answers.UserDisplayName: John Doucette
Body: <p>Let <span class="math-container">$H_1$</span> , <span class="math-container">$H_2$</span> ,... be a sequence of hypothesis classes for binary classiﬁcation. </p>
  
  <p>Assume that there is a learning algorithm that implements the ERM rule in the realizable case such that the output hypothesis of the algorithm for each class <span class="math-container">$H_n$</span> only depends on <span class="math-container">$O(n)$</span> examples out of the training set. Furthermore, assume that such a hypothesis can be calculated given these <span class="math-container">$O(n)$</span> examples in time <span class="math-container">$O(n)$</span>, and that the empirical risk of each such hypothesis can be evaluated in time <span class="math-container">$O(mn)$</span>. </p>
  
  <p>For example, if <span class="math-container">$H_n$</span> is the class of axis aligned rectangles in <span class="math-container">$R^n$</span> , we saw that it is possible to ﬁnd an ERM hypothesis in the realizable case that is deﬁned by at most <span class="math-container">$2n$</span> examples. </p>
  
  <p>Prove that in such cases, it is possible to ﬁnd an ERM hypothesis for <span class="math-container">$H_n$</span> in the unrealizable case in time <span class="math-container">$O(mnm^{O(n)})$</span>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-11T02:13:18.270Z
Comments.Text: I've added the "homework" tag to this problem because it looks like it is a homework problem from the book "Understanding Machine Learning" by Shalev-Shwartz & Ben-David. I'm guessing you would like a hint for this problem, rather than a fully worked answer?
Comments.UserDisplayName: John Doucette
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-11T02:20:32.257Z
Comments.Text: @JohnDoucette Not absolutely. I'm just reading the book. I came across the exercise, and I also have the solution to the exercise, but I cannot understand the solution. Hope you can help me!
Comments.UserDisplayName: Ben
Tags: <machine-learning><time-complexity><pac-learning><homework>
Title: Prove that in such cases, it is possible to ﬁnd an ERM hypothesis for $H_n$ in the unrealizable case in time $O(mnm^{O(n)})$
UserDisplayName: Ben
ThreadText: # Prove that in such cases, it is possible to ﬁnd an ERM hypothesis for $H_n$ in the unrealizable case in time $O(mnm^{O(n)})$
  
  (Asked by: username_0 on 2019-10-11)
  
  Let $H\_1$ , $H\_2$ ,... be a sequence of hypothesis classes for binary classiﬁcation.
  
  Assume that there is a learning algorithm that implements the ERM rule in the realizable case such that the output hypothesis of the algorithm for each class $H\_n$ only depends on $O(n)$ examples out of the training set. Furthermore, assume that such a hypothesis can be calculated given these $O(n)$ examples in time $O(n)$, and that the empirical risk of each such hypothesis can be evaluated in time $O(mn)$.
  
  For example, if $H\_n$ is the class of axis aligned rectangles in $R^n$ , we saw that it is possible to ﬁnd an ERM hypothesis in the realizable case that is deﬁned by at most $2n$ examples.
  
  Prove that in such cases, it is possible to ﬁnd an ERM hypothesis for $H\_n$ in the unrealizable case in time $O(mnm^{O(n)})$.
  
  **Tags:** machine-learning, time-complexity, pac-learning, homework
  
  > **Comments:**
  > **username_1**: I've added the "homework" tag to this problem because it looks like it is a homework problem from the book "Understanding Machine Learning" by Shalev-Shwartz & Ben-David. I'm guessing you would like a hint for this problem, rather than a fully worked answer?  
  > **username_0**: @username_1 Not absolutely. I'm just reading the book. I came across the exercise, and I also have the solution to the exercise, but I cannot understand the solution. Hope you can help me!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-10-11. Score: 1
  
  Here's a rough proof sketch that might be clearer, but is probably less precise, than the solution you already have.
  
  1. We have a sequence of hypotheses classes, but the problem actually only asks us to consider a single class. A hypothesis class is a set of possible models for classification that differ only in a set of parameter values.
  2. We are told that the algorithm for selecting a hypothesis from $H\_n$ uses only $O(n)$ samples from the training set, and that using those samples, it takes the algorithm $O(n)$ to find the hypothesis that minimizes the empirical risk for the class, provided that the ERM minimizing hypothesis has an empirical risk of 0 (i.e. it is realizable).
  3. Further, if we pick some hypothesis at random from the class, we are told that the cost of determining its exact empirical risk is $O(nm)$, where $m$ is the total size of the training set, and $n$ is just a parameter associated with this particular hypothesis class $H\_n$.
  4. Observer that, in the unrealizable case, we cannot use the algorithm to find the risk minimizing hypothesis (which, by 2, runs in O(n)). No other algorithm is mentioned, but we are also told (in 2) that the algorithm can construct a hypothesis from $O(n)$ datapoints in $O(n)$ time, even if no feasible hypothesis can be found for those $O(n)$ points.
  5. Suppose we wanted to find the hypothesis with minimal risk via brute force. We could compute every subset of the training dataset that is of the size $O(n)$ that the algorithm may be able to use to construct a hypothesis in $O(n)$ time. There are $O(m^{O(n)})$ such subsets (e.g. $m\*(m-1)/2$ possible pairs, $m\*(m-1)\*(m-2)/6$ possible triplets, etc.).
  6. Since there are $O(m^{O(n)})$ possible subsets of size $O(n)$, and our algorithm can compute a candidate hypothesis in $O(n)$ time, it costs us $O(nm^{O(n)})$ to find all possible hypotheses that our algorithm can produce for this dataset.
  7. Since it costs us $O(nm)$ time to compute the emperical risk of a hypothesis generated by this algorithm, we can minimize risk by computing risk for each of the $O(m^{O(n)})$ hypotheses we made in step 6, and then selecting the one with lowest empirical risk. This costs us $O(mnm^{O(n)})$ time total. Our total runtime is then the sum of the cost to generate the models in step 6, and the cost to evaluate them here in step 7: $O(mnm^{O(n)})+O(nm^{O(n)})$.
  8. Since $O(mnm^{O(n)})+O(nm^{O(n)}) \in O(mnm^{O(n)})$, we have proven the desired bound on runtime.
  
  
  ---
  
  