Algorithms for learning sparse additive models with interactions in high dimensions*. (24th August 2017)

• Record Type: Journal Article
• Authors: Tyagi, Hemant; Kyrillidis, Anastasios; Gärtner, Bernd; Krause, Andreas
• Is Part Of: Information and inference. Volume 7:Number 2(2018)
• Page Start: 183
• Page End: 249
• Publication Date: 2017-08-24
• Subjects: sparse additive models -- non-parametric function estimation -- compressed sensing -- sparse Hessian estimation -- high-dimensional functions; Mathematical models -- Periodicals; 519.605
• DOI: 10.1093/imaiai/iax008
• Languages: English
• ISSNs: 2049-8764

Abstract

Abstract: A function $f:{\mathbb{R}}^d \rightarrow {\mathbb{R}}$ is a sparse additive model (SPAM), if it is of the form $f(\mathbf x) = \sum_{l \in \mathscr{S}}\phi_{l}(x_l)$, where $\mathscr{S} \subset [{d}]$, ${|{{\mathscr{S}}}|} \ll {d}$ . Assuming $\phi$ 's, $\mathscr{S}$ to be unknown, there exists extensive work for estimating $f$ from its samples. In this work, we consider a generalized version of SPAMs that also allows for the presence of a sparse number of second-order interaction terms . For some ${\mathscr{S}_1} \subset [{d}], {\mathscr{S}_2} \subset {[d] \choose 2}$, with ${|{{{\mathscr{S}_1}}}|} \ll {d}, {|{{{\mathscr{S}_2}}}|} \ll d^2$, the function $f$ is now assumed to be of the form: $\sum_{p \in {\mathscr{S}_1}}\phi_{p} (x_p) + \sum_{(l, l^{\prime}) \in {\mathscr{S}_2}}\phi_{(l, l^{\prime})} (x_{l}, x_{l^{\prime}})$ . Assuming we have the freedom to query $f$ anywhere in its domain, we derive efficient algorithms that provably recover ${\mathscr{S}_1}, {\mathscr{S}_2}$ with finite sample bounds . Our analysis covers the noiseless setting where exact samples of $f$ are obtained and also extends to the noisy setting where the queries are corrupted with noise. For the noisy setting in particular, we consider two noise models namely: i.i.d. Gaussian noise and arbitrary but bounded noise. Our main methods for identification of ${\mathscr{S}_2}$ essentially rely on estimation of sparse Hessian matrices, for which we provide two novel compressed sensing-based schemes. Once ${\mathscr{S}_1}, {\mathscr{S}_2}$ are known, we show how the individual components $\phi_p$, $\phi_{(l, l^{\prime})}$ can be estimated via additional queries of $f$, with uniform error bounds. Lastly, we provide simulation results on synthetic data that validate our theoretical findings.