Probably Approximate Learning over Classes of Distributions
B. K. Natarajan · SIAM Journal on Computing · 1992
This paper presents algorithms that construct approximations to sets and functions on the reals, from randomly chosen sample points. The model that is analyzed is a generalization of the paradigm of probably approximate learning proposed by Valiant. Previously, necessary and sufficient conditions for learning sets were established for the case when the class of sampling distributions is finite, and for the case when the class of sampling distributions is the set of all possible distributions. Here, sufficient conditions are obtained for learning sets and functions over general classes of sampling distributions. The results for functions are with respect to general metrics for measuring the distance between two functions.