Learning general sparse additive models from point queries in high\n dimensions

2018/01/25 by Hemant Tyagi, Tyagi, Hemant, Jan Vybíral +1
Computer Science · Mathematics · #41A25 #41A63 #65D15 #Domain Adaptation and Few-Shot Learning #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Machine Learning and Algorithms #Numerical Analysis (math.NA) #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1801.08499

openalex publication_date 2018/01/25 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

We consider the problem of learning a d-variate function f defined on the\ncube [-1,1]^d\⊂ mathbb R^d, where the algorithm is assumed to have\nblack box access to samples of f within this domain. Denote mathcal S_r\n\⊂ [d] choose r; r=1,\…,r₀ to be sets consisting of unknown\nr-wise interactions amongst the coordinate variables. We then focus on the\nsetting where f has an additive structure, i.e., it can be represented as f\n=
sum_
mathbf j
in
mathcal S₁
phi_
mathbf j +
sum_
mathbf j\n
in
mathcal S₂
phi_
mathbf j +
dots +
sum_
mathbf j
in\n
mathcal S_r0
phi_
mathbf j, where each \φ_ mathbf j;\n mathbf j \∈ cal S_r is at most r-variate for 1 \≤ r \≤ r₀. We\nderive randomized algorithms that query f at carefully constructed set of\npoints, and exactly recover each mathcal S_r with high probability. In\ncontrary to the previous work, our analysis does not rely on numerical\napproximation of derivatives by finite order differences.\n

Citations

• Statistical inference in compound functional models
• Variable selection in high-dimensional additive models based on norms of projections
• Iterative hard thresholding for compressed sensing

Related

• Learning Sparse Additive Models with Interactions in High Dimensions
• Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions
• Learning Functions of Few Arbitrary Linear Parameters in High Dimensions
• Learning Non-Parametric Basis Independent Models from Point Queries via\n Low-Rank Methods
• High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups