PAC Learning Using Nadaraya-Watson Estimator Based on Orthonormal Systems
Abstract
Regression or function classes of Euclidean type with compact support and certain smoothness properties are shown to be PAC learnable by the Nadaraya-Watson estimator based on complete orthonormal systems. While requiring more smoothness properties than typical PAC formulations, this estimator is computationally efficient, easy to implement, and known to perform well in a number of practical applications. The sample sizes necessary for PAC learning of regressions or functions under sup norm cost are derived for a general orthonormal system. The result covers the widely used estimators based on Haar wavelets, trignometric functions, and Daubechies wavelets.
Cite
Text
Qiao et al. "PAC Learning Using Nadaraya-Watson Estimator Based on Orthonormal Systems." International Conference on Algorithmic Learning Theory, 1997. doi:10.1007/3-540-63577-7_41Markdown
[Qiao et al. "PAC Learning Using Nadaraya-Watson Estimator Based on Orthonormal Systems." International Conference on Algorithmic Learning Theory, 1997.](https://mlanthology.org/alt/1997/qiao1997alt-pac/) doi:10.1007/3-540-63577-7_41BibTeX
@inproceedings{qiao1997alt-pac,
title = {{PAC Learning Using Nadaraya-Watson Estimator Based on Orthonormal Systems}},
author = {Qiao, Hongzhu and Rao, Nageswara S. V. and Protopopescu, Vladimir A.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1997},
pages = {146-160},
doi = {10.1007/3-540-63577-7_41},
url = {https://mlanthology.org/alt/1997/qiao1997alt-pac/}
}