Learning general sparse additive models from point queries in high dimensions
For statisticians and machine learning researchers, this provides a theoretically rigorous method for exact recovery of additive model structure in high dimensions, though it is incremental over existing work.
The paper addresses learning high-dimensional functions with unknown sparse additive structure, proposing randomized algorithms that exactly recover interaction sets with high probability using point queries, without relying on derivative approximations.
We consider the problem of learning a $d$-variate function $f$ defined on the cube $[-1,1]^d\subset {\mathbb R}^d$, where the algorithm is assumed to have black box access to samples of $f$ within this domain. Denote ${\mathcal S}_r \subset {[d] \choose r}; r=1,\dots,r_0$ to be sets consisting of unknown $r$-wise interactions amongst the coordinate variables. We then focus on the setting where $f$ has an additive structure, i.e., it can be represented as $$f = \sum_{{\mathbf j} \in {\mathcal S}_1} ϕ_{\mathbf j} + \sum_{{\mathbf j} \in {\mathcal S}_2} ϕ_{\mathbf j} + \dots + \sum_{{\mathbf j} \in {\mathcal S}_{r_0}} ϕ_{\mathbf j},$$ where each $ϕ_{\mathbf j}$; ${\mathbf j} \in {\cal S}_r$ is at most $r$-variate for $1 \leq r \leq r_0$. We derive randomized algorithms that query $f$ at carefully constructed set of points, and exactly recover each ${\mathcal S}_r$ with high probability. In contrary to the previous work, our analysis does not rely on numerical approximation of derivatives by finite order differences.