PAC learning over continuous functions

Question

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

Answer 1

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.