Efficient Interpolation of Density Estimators
Paxton Turner, Jingbo Liu, Philippe Rigollet
Abstract
We study the problem of space and time efficient evaluation of a nonparametric estimator that approximates an unknown density. In the regime where consistent estimation is possible, we use a piecewise multivariate polynomial interpolation scheme to give a computationally efficient construction that converts the original estimator to a new estimator that can be queried efficiently and has low space requirements, all without adversely deteriorating the original approximation quality. Our result gives a new statistical perspective on the problem of fast evaluation of kernel density estimators in the presence of underlying smoothness. As a corollary, we give a succinct derivation of a classical result of Kolmogorov—Tikhomirov on the metric entropy of Holder classes of smooth functions.
BibTeX
@InProceedings{pmlr-v130-turner21a,
title = { Efficient Interpolation of Density Estimators },
author = {Turner, Paxton and Liu, Jingbo and Rigollet, Philippe},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {2503--2511},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/turner21a/turner21a.pdf},
url = {https://proceedings.mlr.press/v130/turner21a.html},
abstract = { We study the problem of space and time efficient evaluation of a nonparametric estimator that approximates an unknown density. In the regime where consistent estimation is possible, we use a piecewise multivariate polynomial interpolation scheme to give a computationally efficient construction that converts the original estimator to a new estimator that can be queried efficiently and has low space requirements, all without adversely deteriorating the original approximation quality. Our result gives a new statistical perspective on the problem of fast evaluation of kernel density estimators in the presence of underlying smoothness. As a corollary, we give a succinct derivation of a classical result of Kolmogorov—Tikhomirov on the metric entropy of Holder classes of smooth functions. }
}