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.

本文提出一种介于非加性模型和一阶加性模型之间的中间阶加性模型 SALSA，使模型可以同时考虑变量间的交互和模型容量控制，并将此模型用于高维非参数回归中，具有良好的性能表现。