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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.