Low-Complexity Nonparametric Bayesian Online Prediction with Universal Guarantees
This work addresses the need for efficient online prediction in machine learning, offering a novel method with universal guarantees, though it is incremental in improving nonparametric approaches.
The paper tackles the problem of online prediction for discrete labels from continuous features by introducing a nonparametric Bayesian predictor that uses a k-d tree for discretization and achieves asymptotic performance matching the true conditional entropy. Experiments demonstrate its computational efficiency with O(log n) time complexity per sample and statistical effectiveness compared to existing methods.
We propose a novel nonparametric online predictor for discrete labels conditioned on multivariate continuous features. The predictor is based on a feature space discretization induced by a full-fledged k-d tree with randomly picked directions and a recursive Bayesian distribution, which allows to automatically learn the most relevant feature scales characterizing the conditional distribution. We prove its pointwise universality, i.e., it achieves a normalized log loss performance asymptotically as good as the true conditional entropy of the labels given the features. The time complexity to process the $n$-th sample point is $O(\log n)$ in probability with respect to the distribution generating the data points, whereas other exact nonparametric methods require to process all past observations. Experiments on challenging datasets show the computational and statistical efficiency of our algorithm in comparison to standard and state-of-the-art methods.