0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ May be of interest to you: en.wikipedia.org/wiki/… (learning a density function in Kolmogorov distance, i.e., learning the CDF to pointwise $\varepsilon$ error) $\endgroup$
    – Clement C.
    Nov 1, 2022 at 6:26

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.