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
Inria Lille - Nord Europe, LPP - Laboratoire Paul Painlevé - UMR 8524, METRICS - Evaluation des technologies de santé et des pratiques médicales - ULR 2694, Polytech Lille - École polytechnique universitaire de Lille, Université de Lille, Sciences et Technologies
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

https://hal.inria.fr/hal-02379404
Contributor : Hemant Tyagi <>
Submitted on : Monday, November 25, 2019 - 4:27:05 PM
Last modification on : Tuesday, January 19, 2021 - 10:16:03 AM

File

SPAMgen_main.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

75

Files downloads

464