The various PAC lower bounds (realizable, agnostic, bounded noise) construct distributions supported on $d$ points, where $d$ is the VC-dimension of the hypothesis class in question.

Does anyone know of any adversarial distributions with support of size greater than $d$ that achieve sharper (i.e., larger) lower bounds than the support-$d$ distributions? We're only talking about constants here, since for agnostic PAC, the excess risk rate is known up to constants (i.e., $\Theta(\sqrt{d/n})$).


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.