Suppose $X=[0,1]$ and $Y=[0,1]$, and we use the squared loss

Let's define the hypothesis class $H = {h(x) = (x-a)^2 : a \in [0,1]}$.

Question: How can covering numbers be used to show that this class is agnostically PAC-learnable, and prove an upper bound on $|L_S(h) - L_D(h)|$, which holds simultaneously for all $h\in H$ with probability at least $1 - \delta$.

I'm not sure how covering numbers can be used here, any ideas are appreciated.

Looks like this can be used to prove the upper bound: https://en.wikipedia.org/wiki/Covering_number#Application_to_machine_learning


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.