2016/04/18 by Hemant Tyagi, Tyagi, Hemant, Anastasios Kyrillidis +5
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #cs.IT #cs.LG #math.IT #stat.ML
paper · pdf · doi:10.48550/arxiv.1604.05307
23 pages, to appear in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) 2016
arxiv created 2016/04/18 · openalex publication_date 2016/04/18 · arxiv updated 2016/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A function f: ℝd → ℝ is referred to as a Sparse Additive Model (SPAM), if it is of the form f(x) = ∑l ∈ Sϕl(xl), where S ⊂ [d], |S| ≪ 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 ⊂ [d], S2 ⊂ [d] \choose 2, the function f is assumed to be of the form: f(x) = ∑p ∈ S1ϕp (xp) + ∑(l,l′) ∈ S2ϕ(l,l′) (xl,xl′). Assuming ϕp,ϕ(l,l′), 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,l′). 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.