Additive Approximations in High Dimensional Nonparametric Regression via the SALSA

Kirthevasan Kandasamy, Yaoliang Yu

TL;DR

This paper introduces SALSA, a novel method for high-dimensional nonparametric regression that extends beyond simple first-order additive models. By allowing for a controlled order of interactions between variables, SALSA effectively balances bias and variance, achieving competitive performance across numerous real-world datasets.

What Problem Does This Paper Address?

High-dimensional regression, where the number of features (D) is large, is notoriously challenging for nonparametric methods. Standard nonparametric approaches often suffer from an "exponential curse of dimensionality," meaning their performance degrades drastically as D increases. A common workaround is to assume a "first-order additive model," where the target variable is a sum of functions, each depending on only one feature. While this reduces variance, it can lead to high bias by ignoring potentially important interactions between features. Conversely, models that capture all interactions can have very high variance. This paper addresses the gap between these two extremes by proposing a method that can model interactions of intermediate orders, offering a more flexible and effective approach to high-dimensional regression.

Methods

The core of SALSA lies in its use of Shrunk Additive Least Squares Approximation (SALSA), which frames the problem as a Kernel Ridge Regression (KRR) with a specially constructed additive kernel. This additive kernel is designed to capture interactions up to a specified order, d. The key innovation is how they efficiently compute this kernel, which would otherwise be combinatorially expensive. They leverage Girard-Newton formulae and the concept of Elementary Symmetric Polynomial (ESP) kernels to manage this computational complexity. Algorithmically, SALSA can be seen as KRR but with a kernel that explicitly encodes the additive structure. The method's capacity is controlled by the chosen interaction order d, allowing for a tunable trade-off between bias and variance.

Datasets

The authors evaluated SALSA on a comprehensive set of 15 real-world datasets and several synthetic datasets. The real datasets span various domains, including:

  • Housing
  • Galaxy
  • fMRI
  • Insulin
  • Skillcraft
  • School
  • CCPP
  • Bleeding
  • Speech
  • Music
  • Telemonit
  • Propulsion
  • Airfoil
  • Forestfires
  • Brain

The paper also mentions using synthetic datasets to demonstrate the bias-variance trade-off with different interaction orders and to compare performance on low-order additive functions.

Key Insights and Ideas

  • The "Middle Ground" is Crucial: The paper highlights that the strict dichotomy between first-order additive models (low variance, high bias) and fully non-additive models (high variance, low bias) leaves a critical space for improvement. SALSA carves out this space by allowing controlled interactions.
  • Order d as a Tunable Parameter: The interaction order d acts as a powerful knob to balance bias and variance. For small datasets or when interactions are weak, a low d is beneficial. As data size increases, a higher d can be used to capture more complex relationships without succumbing to excessive variance.
  • Efficient Kernel Computation is Key: The combinatorial explosion of terms in higher-order additive kernels is a major hurdle. SALSA's use of ESP kernels and Girard-Newton formulae provides an elegant solution, making these models computationally tractable.
  • Theoretical Guarantees for Additive Functions: When the true underlying function is additive, SALSA offers theoretical guarantees of polynomial dependence on dimension D, a significant improvement over the exponential dependence of standard KRR.

Key Results

  • Competitive Performance: SALSA was compared against 21 other methods on 15 real datasets and performed competitively, often outperforming or being among the top performers. It was particularly strong on datasets where interactions were present but not overly complex.
  • Bias-Variance Trade-off Demonstrated: Experiments with synthetic data clearly showed how increasing the interaction order d in SALSA improved performance as the sample size n increased, illustrating the effective management of the bias-variance trade-off.
  • Reduced Dependence on Dimension: For additive functions, SALSA's theoretical analysis shows that the excess risk depends polynomially on the dimension D, a significant improvement over the exponential dependence of traditional KRR.
  • Practical Applicability: The method was shown to be effective on a diverse range of real-world problems, suggesting its practical utility.

Limitations and Future Work

  • Computational Cost for Large n: While SALSA addresses the combinatorial cost of higher-order kernels, its computational complexity still scales quadratically with the number of samples n (due to kernel matrix storage and inversion). The authors suggest exploring scalable kernel methods (e.g., random features, stochastic gradients) to address this.
  • Choosing d and λ: While cross-validation can be used to select d and λ, the authors note that cross-validation for hyperparameter tuning can be computationally intensive.
  • Agnostic Setting Analysis: The theoretical analysis for non-additive functions in the agnostic setting provides intuition about the bias-variance trade-off but is not as precise as for additive functions.
  • Future Work: The authors express interest in developing methods to learn the optimal kernel structure and in further theoretical work to establish optimal rates for additive models where the order d grows with sample size n. They also aim to extend SALSA to handle larger datasets.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kandasamy2016additive,
  author = {Kirthevasan Kandasamy and Yaoliang Yu},
  title = {{Additive Approximations in High Dimensional Nonparametric Regression via the SALSA}},
  booktitle = {International Conference on Machine Learning},
  year = {2016},
  url = {https://openreview.net/forum?id=H1E4NibOWS},
}
Figure