Additive Approximations in High Dimensional Nonparametric Regression via the SALSA

By Kirthevasan Kandasamy, Yaoliang Yu. 2016

47 citations recorded by the source corpus.

High dimensional nonparametric regression is an inherently difficult problem with known lower bounds depending exponentially in dimension. A popular strategy to alleviate this curse of dimensionality has been to use additive models of \emph{first order}, which model the regression function as a sum of independent functions on each dimension. Though useful in controlling the variance of the estimate, such models are often too restrictive in practical settings. Between non-additive models which often have large variance and first order additive models which have large bias, there has been little work to exploit the trade-off in the middle via additive models of intermediate order. In this work, we propose SALSA, which bridges this gap by allowing interactions between variables, but controls model capacity by limiting the order of interactions. SALSA minimises the residual sum of squares with squared RKHS norm penalties. Algorithmically, it can be viewed as Kernel Ridge Regression with an additive kernel. When the regression function is additive, the excess risk is only polynomial in dimension. Using the Girard-Newton formulae, we efficiently sum over a combinatorial number of terms in the additive expansion. Via a comparison on $15$ real datasets, we show that our method is competitive against $21$ other alternatives.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Convex-constrained Sparse Additive Modeling and Its Extensions (2017, background): “Previous works have also studied additive models where some interactions among covariates are allowed [HT90, TKGK16, KY16].”
Multi-fidelity Gaussian Process Bandit Optimisation (2016, methodology): “Regression using additive kernels (SALSA): We used the SALSA method for additive kernel ridge regression (Kandasamy and Yu, 2016) on the 4-dimensional coal power plant dataset.”
Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations (2016, methodology): “Regression using Additive Kernels (SALSA): We used the regression method from [14] on the 4-dimensional coal power plant dataset.”