Efficient Sampling for Learning Sparse Additive Models in High Dimensions
We consider the problem of learning sparse additive models, i.e., functions of the form: $f(\vecx) = \sum_{l \in S} \phi_{l}(x_l)$, $\vecx \in \matR^d$ from point queries of $f$. Here $S$ is an unknown subset of coordinate variables with $\abs{S} = k \ll d$. Assuming $\phi_l$'s to be smooth, we propose a set of points at which to sample $f$ and an efficient randomized algorithm that recovers a \textit{uniform approximation} to each unknown $\phi_l$. We provide a rigorous theoretical analysis of our scheme along with sample complexity bounds. Our algorithm utilizes recent results from compressive sensing theory along with a novel convex quadratic program for recovering robust uniform approximations to univariate functions, from point queries corrupted with arbitrary bounded noise. Lastly we theoretically analyze the impact of noise -- either arbitrary but bounded, or stochastic -- on the performance of our algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
Additive modelsCompressive SensingVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noise
This paper investigates theoretical properties of subsampling and hashing as tools for approximate Euclidean norm-preserving embeddings for vectors with (unknown) additive Gaussian noises. Such embeddings are sometimes c…
Dimensionality ReductionLEMMAEstimation and Uniform Inference in Sparse High-Dimensional Additive Models
We develop a novel method to construct uniformly valid confidence bands for a nonparametric component $f_1$ in the sparse additive model $Y=f_1(X_1)+\ldots + f_p(X_p) + \varepsilon$ in a high-dimensional setting. Our met…
Additive modelsvalidVocal Bursts Intensity PredictionOn Thompson Sampling and Bilateral Uncertainty in Additive Bayesian Optimization
In Bayesian Optimization (BO), additive assumptions can mitigate the twin difficulties of modeling and searching a complex function in high dimension. However, common acquisition functions, like the Additive Lower Confid…
Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner
Gaussian processes (GPs) are widely used in non-parametric Bayesian modeling, and play an important role in various statistical and machine learning applications. In a variety tasks of uncertainty quantification, generat…
Sparse additive Gaussian process with soft interactions
Additive nonparametric regression models provide an attractive tool for variable selection in high dimensions when the relationship between the response and predictors is complex. They offer greater flexibility compared …
regressionVariable Selection