In machine learning and black-box optimization, the "curse of dimensionality" is a fundamental barrier. As the number of input dimensions $D$ grows, the volume of the search space explodes exponentially. Standard non-parametric models, such as Gaussian Processes (GPs), quickly become intractable because the data points required to reliably map the space scale exponentially ($O(c^D)$). This bottleneck severely limits applications like hyperparameter tuning, scientific simulation, and experimental design in high-dimensional settings.
To bypass this exponential trap, a powerful structural assumption has emerged: additive function decomposition. The core intuition is simple yet transformative. Instead of treating a high-dimensional objective function $f(x_1, x_2, \dots, x_D)$ as an inseparable $D$-dimensional landscape, we assume it can be decomposed into a sum of lower-dimensional component functions:
$$f(x) = \sum_{m=1}^M f_m(x_{I_m})$$
where each $x_{I_m}$ represents a small, disjoint, or partially overlapping subset of the input variables. By breaking a monolithic high-dimensional problem into independent or loosely coupled sub-problems, we can fundamentally alter the statistical and computational complexity of learning and optimization.
Why Additivity Beats the Curse of Dimensionality
To understand why this works, consider the task of maximizing an acquisition function in Bayesian Optimization (BO). In a standard $D$-dimensional GP, finding the next point to sample requires globally optimizing a complex, non-convex surrogate model over a $D$-dimensional space—a task that itself suffers from exponential complexity.
When we apply an additive structure, the optimization decomposes beautifully. Because the maximum of a sum of independent functions is equal to the sum of their individual maxima ($\max \sum f_m = \sum \max f_m$), the global search space collapses. As shown by Kirthevasan Kandasamy et al. in their work on Add-GP-UCB, this structural shift reduces the computational cost of point selection from exponential to linear relative to the number of dimension groups. Furthermore, they proved that the cumulative regret scales linearly with $D$ rather than exponentially, providing a massive leap in statistical efficiency.
This reduction from multivariate to univariate or low-dimensional operations manifests across different optimization paradigms:
- Thompson Sampling: Taiwo Adebiyi et al. exploit separable kernels in TS-roots to decompose high-dimensional posterior samples into products of independent 1D functions. This allows complex multi-dimensional rootfinding to be solved via simple univariate sub-problems.
- Trend Filtering: In non-parametric regression, Zhi Zhang et al. utilize an additive structure in Quantile Additive Trend Filtering to ensure that models remain interpretable and computationally feasible via backfitting algorithms as the number of predictors increases.
Decoupling Smoothness from Dimensionality
Statistically, the additive assumption changes how noise and bias accumulate. In general high-dimensional estimation, achieving asymptotic normality requires the underlying function to be incredibly smooth—a requirement that becomes stricter as dimensions increase.
By exploiting additivity, bias-reduction techniques can be applied to each component independently. As demonstrated by Fan Zhou et al. in Optimal Estimation of High Dimensional Smooth Additive Function Based on Noisy Observations, the smoothness requirement for accurate estimation becomes entirely decoupled from the total dimensionality of the parameter space. Work by Ping Li et al. on Universal Bias Reduction confirms that this decoupling prevents the cumulative variance explosion typical of high-dimensional regimes, even when the number of parameters matches or exceeds the sample size.
Unlocking Hidden Additivity via Transformations
What happens if the function is not naturally additive in its original coordinate system? Real-world data often contains complex coordinate cross-correlations that obscure simple structures.
To address this, researchers look for latent coordinate systems where additivity emerges. Johannes Kirschner et al. proposed using Orthogonal Projection Pursuit Models, which decouple the estimation of an unknown orthogonal transformation from the optimization of the underlying additive components. Similarly, Fatima Antarou Ba et al. show in Sparse additive function decompositions facing basis transforms that applying the correct orthogonal basis transform can reveal "hidden" sparsity, simplifying seemingly intractable modeling problems into low-dimensional ANOVA or anchored decompositions.
[High-Dimensional Input] ──► [Basis Transform / Projection] ──► [Independent 1D Components] ──► [Summation]
Instead of learning a single, dense kernel over a high-dimensional space, models like the Deep Additive Kernel introduced by Wenyuan Zhao et al. in From Deep Additive Kernel Learning to Last-Layer Bayesian Neural Networks via Induced Prior Approximation decompose the kernel space into a sum of independent 1D Gaussian Processes. This prevents feature over-correlation and forces independent contributions from each feature dimension.
Relaxing Constraints: Overlapping Groups
While strictly disjoint variable partitions offer the cleanest computational gains, they fail when variables interact strongly. The field has therefore evolved to allow for more flexible additive structures.
Jonathan Scarlett et al. extended the additive framework to handle overlapping groups, allowing individual variables to participate in multiple sub-functions simultaneously. This enables the model to capture complex, localized interactions while preserving the core computational benefits of decomposition via message passing and Gibbs sampling.
Furthermore, Anthony Bardou demonstrated in DuMBO that allowing sub-functions to contain multiple variables—rather than restricting them to strictly univariate factors—strikes a powerful balance. It provides the flexibility needed to model intricate real-world dependencies (such as network power control or trajectory planning) while still avoiding the exponential sample requirements of fully multivariate models.
When the exact decomposition structure is unknown a priori, it can be learned dynamically. Chuan Guo et al. developed a Metropolis-Hastings strategy to discover and exploit additive structures on the fly, allowing optimization algorithms to automatically adapt to the underlying dependency graph of the objective function.
Broad Applications
The strategy of additive decomposition extends far beyond standard global optimization:
- Enforcing Physical Constraints: Andrés F López-Lopera demonstrated in High-dimensional Additive Gaussian Processes under Monotonicity Constraints that decomposing a function into univariate components makes it significantly easier to enforce global constraints (like monotonicity) across spaces with up to 1,000 dimensions.
- Symbolic Regression: In engineering and mechanics, discovering interpretable equations from data is notoriously difficult. By breaking down high-dimensional energy functionals or partial differential equations into additive univariate components, frameworks can isolate individual variables, transforming an intractable combinatorial search space into manageable one-dimensional tasks.
By trading off the ability to represent arbitrary, fully-coupled high-dimensional interactions for structured, additive representations, these methods provide a practical and theoretically sound bridge across the curse of dimensionality.