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} \phi_{ { \mathbf j}} + \sum_{ { \mathbf j} \in { \mathcal S}_2} \phi_{ { \mathbf j}} + \dots + \sum_{ { \mathbf j} \in { \mathcal S}_{ r_0}} \phi_{ { \mathbf j}},$$ where each $\phi_{ { \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.
Categories: math.NA