Learning general sparse additive models from point queries in high dimensions

Tyagi, Hemant; Vybiral, Jan

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1007/s00365-019-09461-6

Titre :

Learning general sparse additive models from point queries in high dimensions

Auteur(s) :

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

Titre de la revue :

Constructive Approximation

Pagination :

403–455

Éditeur :

Springer Verlag

Date de publication :

2019-05-03

ISSN :

0176-4276

Mot(s)-clé(s) en anglais :

Sparse additive models
sampling
hash functions
sparse recovery Mathematics

Discipline(s) HAL :

Mathématiques [math]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL

Fichiers

document
Accès libre
Accéder au document

SPAMgen_main.pdf
Accès libre
Accéder au document

1801.08499
Accès libre
Accéder au document

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

Fichiers

Learning general sparse additive models ...

BibTeX

CSV

Excel

RIS