When optimizing complex, real-world systems—such as tuning hyper-parameters, designing airfoils, or controlling robotic systems—we often face a severe mathematical bottleneck: the curse of dimensionality. As the number of input variables ($D$) grows into the thousands or billions, the volume of the search space grows exponentially. Standard black-box optimization methods, like Bayesian Optimization (BO) or Derivative-Free Optimization (DFO), quickly choke because they cannot sample the space densely enough to construct an accurate surrogate model.
To bypass this wall, a dominant paradigm has emerged: the low effective dimensionality assumption. The core intuition is that while a problem may be framed in a massive $D$-dimensional space, the objective function actually varies along only a tiny, hidden $d$-dimensional subspace ($d \ll D$). The remaining $D-d$ dimensions are redundant or have negligible impact.
By exploiting this assumption, algorithms can project a high-dimensional problem into a manageable latent space, optimize it efficiently, and map the solution back. However, this shortcut comes with a major catch: if the assumption is wrong, or if the latent space is mis-specified, the optimization process breaks down entirely.
The Intuition of Subspace Projections
Why does projecting a high-dimensional space into a random low-dimensional slice actually work? Imagine a three-dimensional room where the temperature only changes as you move from north to south; moving east-west or up-down changes nothing. The "effective dimension" of this temperature function is one, even though it exists in a three-dimensional room. If you drop a random two-dimensional sheet (a plane) through the room, that sheet will almost certainly intersect the north-south axis. By searching only along the surface of that sheet, you can still find the absolute hottest and coldest points in the room.
In high-dimensional optimization, algorithms leverage this geometric property via random linear embeddings or hashing matrices. For instance, REMBO, developed by Hutter et al., scales Bayesian Optimization to billions of dimensions by confining the search to a random low-dimensional subspace. Similarly, HeSBO by Nayebi et al. uses a sketching matrix based on hashing to embed the search space, providing tighter error bounds and lower computational overhead than pure random projections.
This mechanism is widely applied across different optimization paradigms:
- Global Search: Algorithms like RESOO (Qian et al.) and EMBEDDEDHUNTER (Al-Dujaili et al.) combine random embeddings with optimistic tree searches or partitioning strategies to scale global optimization.
- Multi-Objective Optimization: Qian et al. demonstrated that the same effective dimensionality framework can scale multi-objective problems to thousands of variables.
- Manifold Constraints: When the underlying space is non-Euclidean, frameworks like HD-GaBO (Rozo) map the problem onto nested Riemannian manifolds to preserve geometric constraints during the reduction process.
The Intrinsic Dimensionality Mismatch
The low effective dimensionality assumption is incredibly powerful, but it introduces a fragile dependency: the algorithm's success hinges entirely on the accuracy of the initial structural guess. When a mismatch occurs between the assumed dimensionality and the true function behavior, optimization fails in predictable ways.
Underestimating the Latent Space
If an algorithm restricts its search to a $d$-dimensional subspace, but the true function requires $d+1$ dimensions to express its optimum, the global optimum is physically excluded from the search space. As noted by Ginsbourger et al., choosing a subspace that is too restrictive permanently blinds the optimizer to influential coordinates. Rozo and Guo et al. describe this as a fundamental trade-off: lower-dimensional latent spaces converge rapidly but lack the expressive power to represent complex, high-performing designs.
The Failure of Dense Interactions
When a function is non-separable—meaning many variables interact densely and uniformly—the low effective dimensionality assumption is fundamentally violated. If every dimension exerts an equal impact on the output, projecting the problem into a lower-dimensional subspace acts like a lossy, blurry filter. Qian et al. and Hu et al. observe that random embedding methods struggle or fail completely when applied to these truly high-rank functions. In such cases, the reduced search space simply cannot capture the necessary complexity (Kandasamy et al.; Hoang et al.; Tran-The et al.).
The Burden of Pre-Specification
In practice, practitioners rarely know the intrinsic dimensionality of a black-box function beforehand. They are forced to manually guess the target dimension $d$ (Shen et al.). Guessing too low causes convergence to a suboptimal solution; guessing too high re-introduces the curse of dimensionality, making the optimization computationally intractable.
Evolving Beyond Fixed Subspaces
To resolve this tension, recent research focuses on making subspace optimization adaptive, or challenging the necessity of hard-coded projections altogether.
Adaptive and Nested Subspaces
Instead of picking a fixed subspace and hoping for the best, modern algorithms dynamically adjust their scope. For example, BAXUS, introduced by Papenmeier, starts optimizing within a very small, manageable target space. As it gathers data, it dynamically "splits" dimensions, growing the search space embedding as needed. This eliminates the need to guess the dimensionality upfront. Similarly, CobBO (Tan) utilizes a two-stage kernel approach to adaptively select promising low-dimensional coordinates, while Sunkara et al. use neural networks to learn the underlying subspace geometry and adaptively partition the search space.
Variable Selection vs. Random Projection
An alternative to random projection is explicit variable selection. Rather than searching along a tilted, blended linear combination of all variables, frameworks like VS-BO (Shen et al.) automatically identify the exact coordinate axes that matter, focusing optimization resources on those active variables while efficiently sampling the rest.
Rethinking the Need for Subspaces
Perhaps the most surprising development comes from Hvarfner et al., who demonstrated that "vanilla" Bayesian Optimization—without any explicit subspace projections or additive structural assumptions—can perform exceptionally well in high dimensions. By simply scaling the lengthscale priors of the Gaussian Process, standard BO can naturally learn to ignore irrelevant dimensions. This suggests that rigid subspace constraints can sometimes do more harm than good when the objective function deviates from a perfect low-dimensional structure.
Fixed Subspace (REMBO/HeSBO) ──► Hard boundary; blind to outside dimensions.
Adaptive Subspace (BAXUS) ──► Starts small; splits and expands dynamically.
Vanilla BO (Lengthscale Prior) ──► Soft boundary; naturally filters out noise.
Parallel Insights in Representation and Learning Theory
The mathematical tension between high-dimensional reality and low-dimensional simplification is not unique to black-box optimization; it reflects a fundamental geometric property encountered across machine learning.
In Self-Supervised Learning (SSL), models often suffer from a phenomenon known as dimensional collapse. As shown by Fang et al., standard metrics fail to detect when neural network features accidentally collapse into a low-dimensional subspace instead of utilizing the full expressivity of the embedding space. This demonstrates that models naturally gravitate toward low-dimensional representations, requiring explicit algorithmic intervention to maintain high-rank diversity.
In Machine Learning Theory, this limitation manifests as a structural barrier to sample compression. A long-standing goal has been to prove the Sample Compression Conjecture by embedding complex concept classes into highly structured, well-behaved "maximum" or "extremal" classes (Rubinstein et al.; Rubinstein et al.).
However, Chase et al. proved that attempting to force an arbitrary concept class into a structured extremal family causes an exponential explosion in VC dimension if the original class possesses high dual complexity.
Just as in optimization, this theoretical result delivers a profound geometric truth: you cannot compress a genuinely complex, high-dimensional structure into a simplified, low-dimensional envelope without fundamentally altering its properties or losing critical information. Whether navigating an optimization landscape or compressing a dataset, the low effective dimensionality assumption remains a powerful but delicate illusion.
Key Foundational Work
Limitations of Learning Via Embeddings in Euclidean Half Spaces (2002) — contributed 6 concept elements to this direction.
Geometric & Topological Representations of Maximum Classes with Applications to Sample Compression (2008) — contributed 2 concept elements to this direction.