Projects per year

## Abstract / Description of output

We consider the problem of learning a $d$-variate function $f$ defined on the cube $[-1,1]^d\subset \matR^d$, where the algorithm is assumed to have black box access to samples of $f$ within this domain. Denote $\totsupp_r \subset {[d] \choose r}; r=1,\dots,\order$ 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_{\vecj \in \totsupp_1} \phi_{\vecj} + \sum_{\vecj \in \totsupp_2} \phi_{\vecj} + \dots + \sum_{\vecj \in \totsupp_{\order}} \phi_{\vecj},$$ where each $\phi_{\vecj}$; $\vecj \in \totsupp_r$ is at most $r$-variate for $1 \leq r \leq \order$. We derive randomized algorithms that query $f$ at carefully constructed set of points, and exactly recover each $\totsupp_r$ with high probability. In contrary to the previous work, our analysis does not rely on numerical approximation of derivatives by finite order differences.

Original language | English |
---|---|

Publisher | ArXiv |

Number of pages | 42 |

Publication status | Published - 25 Jan 2018 |

## Fingerprint

Dive into the research topics of 'Learning non-smooth sparse additive models from point queries in high dimensions'. Together they form a unique fingerprint.## Projects

- 1 Finished