  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.
