Skip to Main content Skip to Navigation
Journal articles

Learning general sparse additive models from point queries in high dimensions

Hemant Tyagi 1 Jan Vybiral 2 
1 MODAL - MOdel for Data Analysis and Learning
LPP - Laboratoire Paul Painlevé - UMR 8524, Université de Lille, Sciences et Technologies, Inria Lille - Nord Europe, METRICS - Evaluation des technologies de santé et des pratiques médicales - ULR 2694, Polytech Lille - École polytechnique universitaire de Lille
Abstract : We consider the problem of learning a $d$-variate function $f$ defined on the cube $[−1, 1]^d ⊂ R^d$ , where the algorithm is assumed to have black box access to samples of f within this domain. Denote $S_r ⊂ {[d] \choose r} ; r = 1,. .. , r_0$ to be sets consisting of unknown $r$-wise interactions amongst the coordinate variables. We then focus on the setting where f has an additive structure, i.e., it can be represented as $f = \sum_{j∈S1} φ_j + \sum_{j∈S2} φ_j + · · · + \sum_{j∈S_{r_0}} φ_j$, where each $φ_j ; j ∈ S_r$ is at most r-variate for $1 ≤ r ≤ r_0$. We derive randomized algorithms that query f at carefully constructed set of points, and exactly recover each $S_r$ with high probability. In contrary to the previous work, our analysis does not rely on numerical approximation of derivatives by finite order differences.
Document type :
Journal articles
Complete list of metadata

Cited literature [51 references]  Display  Hide  Download
Contributor : Hemant Tyagi Connect in order to contact the contributor
Submitted on : Monday, November 25, 2019 - 4:27:05 PM
Last modification on : Friday, July 8, 2022 - 10:09:26 AM


Files produced by the author(s)




Hemant Tyagi, Jan Vybiral. Learning general sparse additive models from point queries in high dimensions. Constructive Approximation, Springer Verlag, 2019, 50, pp.403-455. ⟨10.1007/s00365-019-09461-6⟩. ⟨hal-02379404⟩



Record views


Files downloads