Learning general sparse additive models from point queries in high dimensions

Tyagi, Hemant; Vybiral, Jan

Document type :

Article dans une revue scientifique: Article original

DOI :

10.1007/s00365-019-09461-6

Title :

Learning general sparse additive models from point queries in high dimensions

Author(s) :

Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]
Vybiral, Jan [Auteur]
Czech Technical University in Prague [CTU]

Journal title :

Constructive Approximation

Pages :

403–455

Publisher :

Springer Verlag

Publication date :

2019-05-03

ISSN :

0176-4276

English keyword(s) :

sparse recovery Mathematics
hash functions
sampling
Sparse additive models

HAL domain(s) :

Mathématiques [math]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL

Files

document
Open access
Access the document

SPAMgen_main.pdf
Open access
Access the document

1801.08499
Open access
Access the document

Learning general sparse additive models ... BibTeX CSV Excel RIS

Files

Learning general sparse additive models ...

BibTeX

CSV

Excel

RIS