High Dimensional Optimization via Random Linear Embeddings

66 concepts39 papers1 proposal

When optimizing a complex system—whether tuning the hyperparameters of a database, finding the optimal shape of an airfoil, or prompting a billion-parameter language model—we are often forced to operate in a "black-box" setting. We can evaluate how well a choice performs, but we do not have access to gradients.

In these scenarios, derivative-free optimization algorithms (like Bayesian Optimization or evolutionary strategies) are the gold standard. However, these methods invariably hit a wall known as the curse of dimensionality. As the number of parameters $D$ grows into the thousands or millions, the volume of the search space expands exponentially. Searching for an optimal solution becomes like looking for a needle in a high-dimensional desert; the algorithm stalls, completely overwhelmed by the vastness of the space.

Yet, a remarkable empirical truth has emerged across machine learning: most high-dimensional problems do not actually exploit all their dimensions. Instead, the true behavior of the system is governed by a much smaller, hidden set of parameters. This property is known as a low intrinsic dimensionality or effective dimension.

If the true solution space is small, can we bypass the high-dimensional desert entirely? The answer is yes, and the mechanism is surprisingly simple: random linear embeddings.

The Core Intuition: Slicing the Desert

Imagine you are looking for a specific point hidden inside a massive, 1,000-dimensional room. Finding it by randomly searching the volume is impossible. However, suppose you are told that the point actually lies somewhere on a flat, 2-dimensional sheet of paper slicing through that room.

If you knew the exact orientation of that sheet, you could simply step onto it and conduct a highly efficient 2D search. But what if you don't know its orientation?

The mathematical magic of high-dimensional spaces is that if you drop a random low-dimensional slice (a subspace) through the room, that slice has an incredibly high probability of capturing the essential structure of the target space. Because the important variations are confined to a low-dimensional manifold, a random linear projection acts as a net that catches those variations without needing to know which specific ambient dimensions matter.

Mathematically, instead of optimizing a function $f(x)$ over a high-dimensional space $x \in \mathbb{R}^D$, we define a much smaller search space $y \in \mathbb{R}^d$ (where $d \ll D$). We map this low-dimensional vector back up to the high-dimensional space using a fixed, randomly generated matrix $A \in \mathbb{R}^{D \times d}$:

$$x = Ay$$

The optimization algorithm now searches entirely within the low-dimensional space $\mathbb{R}^d$. Every time it wants to evaluate a point $y$, we multiply it by $A$ to get the high-dimensional parameters $x$, and feed $x$ into the black-box function. The optimizer never has to navigate the daunting ambient dimension $D$.

Scaling Classical Black-Box Optimization

This strategy was famously brought to Bayesian Optimization (BO) via the REMBO framework by Frank Hutter et al. in Bayesian Optimization in a Billion Dimensions via Random Embeddings. Standard BO typically fails when $D > 20$. By utilizing a random linear embedding, the authors demonstrated that BO could effectively optimize functions with up to a billion ambient variables, provided the function's effective dimension $d$ was small. Because a random subspace intersects the important dimensions with high probability, the optimizer can find global optima without prior knowledge of parameter importance.

This concept generalizes across diverse optimization paradigms:

Unlocking Language-Model-as-a-Service (LMaaS)

The rise of massive pre-trained foundation models has given random linear embeddings a powerful second life. Suppose you want to tune a 175-billion parameter language model for a specific downstream task, but the model is hosted behind a commercial API. You cannot access its weights, and you cannot compute gradients; you can only feed it inputs (prompts) and observe the outputs.

To adapt the model, you might try to optimize a sequence of continuous "soft prompt" embeddings. However, the prompt embedding space is highly dimensional, making standard gradient-free optimization stall.

To solve this, Tianxiang Sun et al. introduced Black-Box Tuning (BBT) in Black-Box Tuning for Language-Model-as-a-Service. Instead of optimizing the high-dimensional prompt tokens directly, BBT generates a fixed random projection matrix to map a small, low-dimensional vector (e.g., $d=500$) into the full prompt space.

Low-Dim Vector (y) ∈ ℝᵈ  ───► [ Fixed Random Matrix A ] ───► High-Dim Prompt (x) ∈ ℝᴰ ───► [ Black-Box LLM ]

This works because large pre-trained models already possess a low intrinsic dimensionality for specific downstream tasks. As the authors observe in their follow-up work on BBTv2, as a model's total parameter count increases, the number of dimensions required to effectively tune it for a specific task does not grow proportionally. The effective search space remains small, making derivative-free optimization uniquely viable for massive models.

Subsequent research has rapidly expanded this paradigm across vision and language domains:

Why Does a Random Matrix Suffice?

The intuition for why a completely random matrix works so well lies in the geometry of high-dimensional spaces. When the ambient dimension $D$ is massive, any two randomly chosen vectors are almost perfectly orthogonal to one another. This means a random matrix $A \in \mathbb{R}^{D \times d}$ acts as a collection of nearly orthogonal basis vectors that span a diverse, unbiased slice of the full space.

If the true solution manifold is a low-dimensional subspace of dimension $d_{true}$, a random subspace of dimension $d \ge d_{true}$ will intersect or align closely with that true manifold with a probability approaching 1. You do not need to spend expensive computational cycles figuring out which dimensions are important; the random projection naturally distributes your low-dimensional search coordinates across all ambient dimensions simultaneously.

This structural property is so potent that it exists even in completely untrained networks. Ziqian Zhong and Jacob Andreas demonstrated in Algorithmic Capabilities of Random Transformers that randomly initialized, frozen Transformers can perform complex algorithmic tasks. By training only the input and output embedding layers, the model learns to steer data into pre-existing, low-dimensional functional circuits that naturally occur within the high-dimensional random noise at initialization.

Conclusion

Intrinsic subspace optimization via random linear embeddings turns the curse of dimensionality on its head. By accepting that the ambient parameter space is an illusion, and that the true control levers of a system live on a much smaller manifold, we can compress daunting optimization tasks into manageable ones. Whether applied to classical black-box optimization or modern foundation model adaptation, random embeddings provide a mathematically elegant, highly efficient bridge between high-dimensional complexity and low-dimensional tractability.

Key Foundational Work

A Warped Kernel Improving Robustness in Bayesian Optimization Via Random Embeddings (2015) — contributed 1 concept elements to this direction.
Alternating Minimization for Mixed Linear Regression (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_random_linear_embedding_fa20ed94,
  title = {random linear embedding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-linear-embedding/rdr_fa20ed946f3e4d2dbfe66bc625af74b7},
  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_random_linear_embedding_fa20ed94_v1,
  title = {random linear embedding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-linear-embedding/rdr_fa20ed946f3e4d2dbfe66bc625af74b7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake