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

<p>In <a href="https://en.wikipedia.org/wiki/Probably_approximately_correct_learning" rel="nofollow noreferrer">PAC-learning</a>, the guarantee is given for any underlying distributions. But in reality, we don't need the guarantees for <em>any</em> 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? </p>

CC BY-SA 4.0
2018-07-01T19:54:40.187Z
See my answer to this question https://cstheory.stackexchange.com/questions/40335/other-uniform-bound
Aryeh
CC BY-SA 4.0
2018-07-01T19:55:00.577Z
and in particular, the closing comment: tl;dr it all comes down to covering numbers
Aryeh
CC BY-SA 4.0
2018-07-02T03:58:33.537Z
There has been a lot of work on PAC learning under specific (yet expressive) distributions classes, such as log-concave. See e.g. [this](https://arxiv.org/abs/1211.1082), [this](http://proceedings.mlr.press/v30/Kane13.pdf), 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](https://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture8.pdf))
Clement C.
<machine-learning><lg.learning><pac-learning>
Learnability of under some characteristics of the distribution
Daniel
# Learnability of under some characteristics of the distribution

(Asked by: username_0 on 2018-07-01)

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

In [PAC-learning](https://en.wikipedia.org/wiki/Probably_approximately_correct_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?

**Tags:** machine-learning, lg.learning, pac-learning

> **Comments:**
> **username_1**: See my answer to this question https://cstheory.stackexchange.com/questions/40335/other-uniform-bound  
> **username_1**: and in particular, the closing comment: tl;dr it all comes down to covering numbers  
> **username_2**: There has been a lot of work on PAC learning under specific (yet expressive) distributions classes, such as log-concave. See e.g. [this](https://arxiv.org/abs/1211.1082), [this](http://proceedings.mlr.press/v30/Kane13.pdf), 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](https://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture8.pdf))  

---

## 0 answers

