Algorithms for learning sparse additive models with interactions in high dimensions

DOI10.1093/IMAIAI/IAX008MaRDI QIDQ5242847zbMATH OpenOpenAlexFDO

Authors Hemant Tyagi, Anastasios Kyrillidis, Andreas Krause, B. Gärtner

Publication date 7 November 2019

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.00609

zbMATH Keywords

compressed sensinghigh-dimensional functionsnon-parametric function estimationsparse additive modelssparse Hessian estimation

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: A function $f:mathbb{R}^{d}ightarrowmathbbR$ is a Sparse Additive Model (SPAM), if it is of the form $f(mathbfx)=su{m}_{linmathcalS}ph{i}_l(x_l)$ where $mathcalSsubset[d]$, $|mathcalS|lld$. Assuming $phi$'s, $mathcalS$ 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 $mathcal{S}_{1}subset[d],mathcal{S}_{2}subset[d]choose2$, with $|mathcal{S}_1|lld,|mathcal{S}_2|ll{d}^2$, the function $f$ is now assumed to be of the form: $su{m}_{pinmathcal{S}_1}ph{i}_p(x_p)+su{m}_{(l,l^{prime})inmathcal{S}_2}ph{i}_{(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 $mathcal{S}_1,mathcal{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 $mathcal{S}_2$ essentially rely on estimation of sparse Hessian matrices, for which we provide two novel compressed sensing based schemes. Once $mathcal{S}_1,mathcal{S}_2$ are known, we show how the individual components $ph{i}_p$, $ph{i}_{(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.

Recommendations

• Learning general sparse additive models from point queries in high dimensions
• Modal additive models with data-driven structure identification
• Sparse additive models
• Minimax-optimal rates for sparse additive models over kernel classes via convex programming
• Statistical inference in sparse high-dimensional additive models

Cited in

(6)

• Learning general sparse additive models from point queries in high dimensions
• Information based complexity for high dimensional sparse functions
• Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
• HARFE: hard-ridge random feature expansion
• A new large-scale learning algorithm for generalized additive models
• Statistical inference in sparse high-dimensional additive models

This page was built for publication: Algorithms for learning sparse additive models with interactions in high dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5242847)