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