Learning general sparse additive models from point queries in high dimensions

Abstract

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 \left(\genfrac{}{}{0ex}{}{[d]}{r}\right);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}{\varphi }_{\mathbf{j}}+\sum _{\mathbf{j}\in {\mathcal{S}}_2}{\varphi }_{\mathbf{j}}+\cdots +\sum _{\mathbf{j}\in {\mathcal{S}}_{r_0}}{\varphi }_{\mathbf{j}},$$ where each ${\varphi }_{\mathbf{j}}$; $\mathbf{j}\in {\mathcal{S}}_r$ is at most $r$-variate for $1\le r\le 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.

References in corpus (6)

• Big Data of Materials Science - Critical Role of the Descriptor
• Component selection and smoothing in multivariate nonparametric regression
• Moments and Absolute Moments of the Normal Distribution
• Tight conditions for consistent variable selection in high dimensional nonparametric regression
• Learning Sparse Additive Models with Interactions in High Dimensions
• Variable selection in high-dimensional additive models based on norms of projections