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:
- Variable Grouping: Yuhao Su introduced GBART in Variable Grouping Based Bayesian Additive Regression Tree, which automatically identifies which variables interact and groups them into "weak learners," balancing flexibility with the additive bias.
- Random Projections: David Bindel proposed RPA-GP in Randomly Projected Additive Gaussian Processes for Regression, which sums kernels applied to random 1D projections. This allows the model to capture interactions across dimensions without explicitly learning a complex high-dimensional kernel.
- Deep Additive Kernels: Wenyuan Zhao and Rui Tuo bridge the gap between kernels and neural networks in From Deep Additive Kernel Learning to Last-Layer Bayesian Neural Networks via Induced Prior Approximation, using additive GP structures to provide interpretability and uncertainty quantification within deep learning architectures.