# Learning Sparse Additive Models with Interactions in High Dimensions

arXiv: https://arxiv.org/abs/1604.05307 · HTML: https://mlsanity.com/paper/1604.05307/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2016.

## Built on by (most cited first, 2 of 2)

- [Sparse Interaction Additive Networks via Feature Interaction Detection and Sparse Selection](https://mlsanity.com/paper/2209.09326/) (2022)
- [HARFE: Hard-Ridge Random Feature Expansion](https://mlsanity.com/paper/2202.02877/) (2022)

## Abstract (arXiv)

A function f: ℝd rightarrow ℝ is referred to as a Sparse Additive Model (SPAM), if it is of the form f(x) = suml ∈ Sφl(xl), where S subset [d], |S| ll d. Assuming φl's and S to be unknown, the problem of estimating f from its samples has been studied extensively. In this work, we consider a generalized SPAM, allowing for second order interaction terms. For some S1 subset [d], S2 subset [d] choose 2, the function f is assumed to be of the form: f(x) = sump ∈ S1φp (xp) + sum_(l,lprime) ∈ S2φ_(l,lprime) (xl,x_lprime). Assuming φp,φ_(l,lprime), S1 and, S2 to be unknown, we provide a randomized algorithm that queries f and exactly recovers S1,S2. Consequently, this also enables us to estimate the underlying φp, φ_(l,lprime). We derive sample complexity bounds for our scheme and also extend our analysis to include the situation where the queries are corrupted with noise -- either stochastic, or arbitrary but bounded. Lastly, we provide simulation results on synthetic data, that validate our theoretical findings.