TLDR; is there any results showing that more concentrated (or easier) distributions are easier to learn?

In PAC-learning, the guarantee is given for any underlying distributions. But in reality, we don't need the guarantees for any distribution. For example for image classification, there is a limited underlying distribution. It makes sense to have stronger guarantees for easier distributions. Are there any such results?

  • $\begingroup$ See my answer to this question cstheory.stackexchange.com/questions/40335/other-uniform-bound $\endgroup$ – Aryeh Jul 1 '18 at 19:54
  • $\begingroup$ and in particular, the closing comment: tl;dr it all comes down to covering numbers $\endgroup$ – Aryeh Jul 1 '18 at 19:55
  • $\begingroup$ There has been a lot of work on PAC learning under specific (yet expressive) distributions classes, such as log-concave. See e.g. this, this, references within, etc. Also, of course, learning under the uniform or product distributions, on the hypercube. (Both positive and negative results, see e.g. thiese lecture notes) $\endgroup$ – Clement C. Jul 2 '18 at 3:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.