Algorithms for PAC learning of functions with smoothness properties
Nageswara S. V. Rao, V. Protopopescu · University of North Texas Digital Library (University of North Texas) · 1996
We present three computationally efficient algorithms for Probably and Approximately Correct (PAC) learning of an unknown function f: [0, 1]{sup d} {r_arrow} [0,1], based on finite samples. The function f is chosen from the family F {intersection} C([0,1]{sup d}) or F {intersection} L{sup {infinity}} ([0,1]{sup d}), where F has either bounded modulus of smoothness or bounded capacity or both. Three function estimators based on: local averaging; nearest neighbor rule; and Nadaraya-Watson estimator, all computed using the Haar system, are analyzed. With no preprocessing of the sample, estimated function value at a given point can be computed in O(n) time. With preprocessing, the first and third estimators can be computed in O((log n){sup d}) time using a range-tree precomputed in O(dn(log n){sup d}) time.