Additive Approximations in High Dimensional Nonparametric Regression via the SALSA

Kirthevasan Kandasamy, Yaoliang Yu

The Curse of Dimensionality in Regression

In high-dimensional nonparametric regression, the goal is to estimate a function $f(x)$ without assuming a rigid parametric form, such as a simple straight line. However, these flexible methods usually hit a mathematical wall known as the curse of dimensionality: the amount of data needed to maintain predictive accuracy grows exponentially as the number of dimensions $D$ increases.

To fight this, researchers often rely on "first-order additive models." These models assume the target function is merely a sum of independent 1D functions (i.e., $f(x) = f_1(x_1) + f_2(x_2) \dots$). While mathematically convenient and easy to estimate, they are often too simplistic for real-world data because they ignore how variables interact—for example, how the combination of humidity and temperature jointly affects crop yield.

This research addresses a critical middle ground: how can we model complex interactions between $d$ variables (where $d > 1$ but $d \ll D$) without the computational complexity blowing up?

Introducing SALSA

The authors introduce SALSA (Shrunk Additive Least Squares Approximation), a method that treats the problem as Kernel Ridge Regression (KRR) using a specialized additive kernel to bridge the gap between overly simple additive models and complex, dimension-prone non-parametric methods.

  1. The $d$-th Order Model: Instead of looking at single variables in isolation, SALSA considers all possible combinations of $d$ variables. For a 100-dimensional problem, a 2nd-order model evaluates all $\binom{100}{2} = 4,950$ pairs.
  2. The ESP Kernel: Manually calculating every single interaction becomes combinatorially impossible as $d$ increases. To bypass this, SALSA employs an Elementary Symmetric Polynomial (ESP) kernel.
  3. The Computational Trick: The "secret sauce" of SALSA is its use of Girard-Newton formulae. This mathematical identity allows the sum of all $\binom{D}{d}$ interaction terms to be computed in $O(Dd^2)$ time. This transforms a problem that would normally take geological timescales into one that runs in seconds on a standard laptop.
  4. Shrinkage: The model applies a squared RKHS (Reproducing Kernel Hilbert Space) norm penalty to prevent overfitting. This effectively "shrinks" the influence of complex interactions unless the data strongly supports them.

Key Insights and Results

SALSA was rigorously evaluated against 21 other regression methods—including Gaussian Processes, Random Forests, and Support Vector Regression—across synthetic benchmarks and 15 real-world datasets from physical, biological, and social domains.

SALSA performance vs. sample size across dimensions
  • Breaking the Curse: Theoretical analysis proves that if the true underlying function is additive, the "excess risk" (error) only grows polynomially with dimension $D$, a massive improvement over standard exponential growth.
  • Order as a Regularizer: Traditionally, model complexity is controlled using a smoothing parameter. SALSA demonstrates that the order of interaction ($d$) is itself a powerful tool for managing the bias-variance tradeoff. Small $d$ works best for small datasets (low variance), while larger $d$ captures more nuance as more data becomes available (low bias).
  • Interaction Matters: In many real-world tests, cross-validation chose an interaction order $d > 1$. This confirms the hypothesis that first-order models are often too restrictive for real data.
Benchmark results across 15 real-world datasets
  • Superior Consistency: Across the 15 real datasets, SALSA was either the top performer or in the top 5 in almost every case. It proved significantly more consistent than specialized methods like SpAM (Sparse Additive Models) or MARS.
  • Robustness to Noise: In experiments where "junk" dimensions were artificially added (marked with * in the results), SALSA remained highly competitive, effectively ignoring irrelevant features while focusing on meaningful interactions.

Limitations and Future Work

While highly effective, SALSA does have limitations. Like most kernel methods, it requires inverting an $n \times n$ matrix, which carries a computational complexity of $O(n^3)$. This currently limits the method to "moderate" dataset sizes of a few thousand points. Additionally, the current implementation uses a fixed heuristic for the base kernel bandwidth, leaving room for improvement via more sophisticated kernel learning.

Future directions proposed by the authors include combining SALSA with scalable kernel techniques—such as random Fourier features or Nyström approximations—to extend its powerful interaction modeling to datasets with millions of samples.

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 dimensionali...
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