<p>In PAC learning, you specify the function class a priori. Thus, there might not <em>be</em> a function in your class that fits the sample perfectly. You'll typically minimize some empirical risk, such as <span class="math-container">$L_1$</span> or <span class="math-container">$L_2$</span>. The classical papers are</p>
<p>Scale-sensitive dimensions, uniform convergence, and learnability
Alon, Ben-David, Cesa-Bianchi, Haussler
<a href="https://dl.acm.org/doi/10.1145/263867.263927" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/263867.263927</a></p>
<p>and</p>
<p>Fat-Shattering and the Learnability of Real-Valued Functions
Bartlett, Long, Williamson
<a href="https://www.sciencedirect.com/science/article/pii/S0022000096900331" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0022000096900331</a></p>
<p>These are somewhat technical, and I suggest the book
Anthony, Bartlett
Neural Network Learning
<a href="https://www.cambridge.org/core/books/neural-network-learning/665C8C7EB5E2ABC5367A55ADB04E2866" rel="nofollow noreferrer">https://www.cambridge.org/core/books/neural-network-learning/665C8C7EB5E2ABC5367A55ADB04E2866</a></p>
<p>which provides a comprehensive and readable introduction and proves the relevant results.</p>

CC BY-SA 4.0
2022-11-01T15:21:55.617Z
2022-11-01T15:21:55.617Z
Aryeh
<p>I'm wondering if it's possible to use PAC learning to learn a continuous function. For example, if we wanted to learn a probability distribution or a CDF, is it valid to train on some set of <em>m</em> examples and basically then find some hypothesis function <em>h</em> that fits those examples? Basically then we can find the sample complexity as with learning boolean functions, finding what is the minimum sample size we need <em>m</em> that will make the algorithm output an <em>h</em> that will correctly estimate the probability of any input within <span class="math-container">$\pm$$\epsilon$</span> for some error parameter <span class="math-container">$\epsilon$</span></p>
<p>I've seen some papers on using PAC for continuous functions, but they go a bit over my head, and I'm wondering if there's a simpler explanation</p>

CC BY-SA 4.0
2022-11-01T06:26:25.787Z
May be of interest to you: https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality (learning a density function in Kolmogorov distance, i.e., learning the CDF to pointwise $\varepsilon$ error)
Clement C.
<cc.complexity-theory><machine-learning><lg.learning><pac-learning>
PAC learning over continuous functions
qc6518
# PAC learning over continuous functions

(Asked by: username_0 on 2022-11-01)

I'm wondering if it's possible to use PAC learning to learn a continuous function. For example, if we wanted to learn a probability distribution or a CDF, is it valid to train on some set of *m* examples and basically then find some hypothesis function *h* that fits those examples? Basically then we can find the sample complexity as with learning boolean functions, finding what is the minimum sample size we need *m* that will make the algorithm output an *h* that will correctly estimate the probability of any input within $\pm$$\epsilon$ for some error parameter $\epsilon$

I've seen some papers on using PAC for continuous functions, but they go a bit over my head, and I'm wondering if there's a simpler explanation

**Tags:** cc.complexity-theory, machine-learning, lg.learning, pac-learning
> **Comments:**
> **username_1**: May be of interest to you: https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality (learning a density function in Kolmogorov distance, i.e., learning the CDF to pointwise $\varepsilon$ error)  

---

## 1 answers

### Answer by username_2 on 2022-11-01. Score: 2

In PAC learning, you specify the function class a priori. Thus, there might not *be* a function in your class that fits the sample perfectly. You'll typically minimize some empirical risk, such as $L\_1$ or $L\_2$. The classical papers are

Scale-sensitive dimensions, uniform convergence, and learnability
Alon, Ben-David, Cesa-Bianchi, Haussler
<https://dl.acm.org/doi/10.1145/263867.263927>

and

Fat-Shattering and the Learnability of Real-Valued Functions
Bartlett, Long, Williamson
<https://www.sciencedirect.com/science/article/pii/S0022000096900331>

These are somewhat technical, and I suggest the book
Anthony, Bartlett
Neural Network Learning
<https://www.cambridge.org/core/books/neural-network-learning/665C8C7EB5E2ABC5367A55ADB04E2866>

which provides a comprehensive and readable introduction and proves the relevant results.


---

