Algorithms for learning sparse additive models with interactions in high dimensions*. (24th August 2017) - Tyagi, Hemant; Kyrillidis, Anastasios; Gärtner, Bernd; Krause, Andreas
Abstract: A function $f:{\mathbb{R}}^d → {\mathbb{R}}$ is a sparse additive model (SPAM), if it is of the form $f(\mathbf x) = \sum_{l \in \mathscr{S}}φ_{l}(x_l)$, where $\mathscr{S} \subset [{d}]$, ${|{{\mathscr{S}}}|} \ll {d}$ . Assuming $φ$ '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}}φ_{p} (x_p) + \sum_{(l, l^{′}) \in {\mathscr{S}_2}}φ_{(l, l^{′})} (x_{l}, x_{l^{′}})$ . 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 $φ_p$, $φ_{(l, l^{′})}$ 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.