Learning non-smooth sparse additive models from point queries in high dimensions

Hemant Tyagi, Jan Vybiral

Research output: Working paper

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 languageEnglish
PublisherArXiv
Number of pages42
Publication statusPublished - 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.

Cite this