Additive Decomposition for High-Dimensional Modeling

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 280 papers112 conceptsfrozen 2026-10-04

In high-dimensional machine learning, researchers often encounter the "curse of dimensionality": as the number of input features increases, the volume of the search space grows exponentially, making data points sparse and optimization computationally prohibitive. To combat this, a recurring strategy across Gaussian Processes (GPs), Bayesian Optimization (BO), and symbolic regression is additive decomposition.

By assuming a function can be represented as a sum of lower-dimensional components, researchers can transform a single, intractable high-dimensional problem into a collection of manageable sub-problems.

The Additive Inductive Bias

The core idea, as formalized by David Ginsbourger, Nicolas Durrande, and Olivier Roustant in Additive Kernels for Gaussian Process Modeling, is to structure the covariance kernel of a GP as a sum of univariate kernels: $$K(x, x') = \sum_{d=1}^D k_d(x_d, x'_d)$$ This structural choice forces the resulting model to decompose into independent functions for each dimension. While this restricts the model from capturing every possible high-order interaction, it provides a powerful inductive bias that prevents overfitting and enables the model to learn from sparse data in high-dimensional regimes.

Scaling Bayesian Optimization

In Bayesian Optimization, the "scaling wall" typically occurs around 10–20 dimensions. Kirthevasan Kandasamy, Jeff Schneider, and Barnabás Póczos demonstrated in High Dimensional Bayesian Optimisation and Bandits via Additive Models that if the objective function is additive, the cumulative regret scales linearly with the number of dimensions rather than exponentially.

The intuition is "divide and conquer": instead of searching a $D$-dimensional space for the next point to sample, the algorithm maximizes each low-dimensional component of the acquisition function independently. Zi Wang and Stefanie Jegelka further refined this in Max-value Entropy Search for Efficient Bayesian Optimization, showing that combining additive decomposition with entropy-based search allows BO to scale to hundreds of variables by treating the global search as a combination of simpler sub-searches.

Bypassing the Search Space Explosion

The benefits of additivity extend to symbolic regression—the task of finding a mathematical expression that fits a dataset. Standard symbolic regression fails in high dimensions because the number of possible equation combinations explodes.

Bahador Bahmani and colleagues have applied this to physics-informed modeling, such as in Physics-constrained symbolic model discovery for polyconvex incompressible hyperelastic materials. By decomposing complex energy functionals into univariate functions, they isolate the influence of individual variables. This modularity allows for the discovery of interpretable mathematical expressions by transforming a single difficult search into multiple manageable one-dimensional tasks. Similarly, Hongjue Zhao showed that breaking down multi-variable equations into single-variable problems can improve recovery rates of complex formulas by over 70%.

Computational Acceleration via Fourier Transforms

Beyond statistical efficiency, additive structures unlock significant computational speedups. Standard kernel methods require $O(N^3)$ time for training, which is prohibitive for large datasets.

Theresa Wagner, Martin Stoll, and Franziska Nestler have developed frameworks like those in Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication that use the Non-equispaced Fast Fourier Transform (NFFT) to accelerate matrix-vector products. Because the kernels are additive, the high-dimensional problem is decomposed into low-dimensional "feature windows." This allows the application of efficient low-dimensional transforms to each dimension independently, reducing complexity to near-linear $O(N \log N)$ and enabling kernel-based learning on hundreds of thousands of points.

Relaxing the Assumption

While pure additivity (summing 1D functions) is powerful, it can be too restrictive for functions with complex interactions. Recent work has focused on relaxing these constraints:

Papers in this version

Showing 60 of 80 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 79 papers
  2. Version 1 · 2026-10-04 · 80 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_additive_function_decomposition_c6bd02b1,
  title = {additive function decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/additive-function-decomposition/rdr_c6bd02b10a1547b5b58f26046b9d5931},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_additive_decomposition_for_high_dimensio_c6bd02b1_v1,
  title = {Additive Decomposition for High-Dimensional Modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/additive-decomposition-for-high-dimensional-modeling/rdr_c6bd02b10a1547b5b58f26046b9d5931/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}