On the Statistical Efficiency of Compositional Nonparametric Prediction
This work addresses sample efficiency for compositional nonparametric models, which is incremental as it builds on existing theory with specific bounds.
The paper tackles the problem of recovering a labeled binary tree model from data, showing that the sufficient sample complexity is O(k log(pq) + log(k!)) and the necessary sample complexity is Ω(k log(pq) - log(k!)), with validation through synthetic experiments using a greedy algorithm.
In this paper, we propose a compositional nonparametric method in which a model is expressed as a labeled binary tree of $2k+1$ nodes, where each node is either a summation, a multiplication, or the application of one of the $q$ basis functions to one of the $p$ covariates. We show that in order to recover a labeled binary tree from a given dataset, the sufficient number of samples is $O(k\log(pq)+\log(k!))$, and the necessary number of samples is $Ω(k\log (pq)-\log(k!))$. We further propose a greedy algorithm for regression in order to validate our theoretical findings through synthetic experiments.