When optimizing a complex function, knowing the direction of steepest descent (the gradient) is rarely enough. High-dimensional optimization landscapes are often plagued by ill-conditioning—narrow, winding valleys where standard gradient steps bounce violently between walls rather than moving along the floor.
To navigate these landscapes efficiently, algorithms must learn the underlying geometry of the space. They do this by tracking how variables move together, capturing this information in a second-moment or covariance matrix. This matrix acts as a coordinate transformer, stretching and rotating the search space so that the algorithm can treat a highly correlated, poorly scaled landscape as if it were a perfectly symmetric bowl.
This geometric awareness is the secret weapon behind powerful optimization paradigms, including Covariance Matrix Adaptation Evolution Strategies (CMA-ES), Natural Evolution Strategies (NES), and adaptive subgradient methods. However, as optimization problems scale to thousands or millions of variables, this secret weapon encounters a severe mathematical wall: the full-covariance bottleneck.
The Geometry of the Bottleneck
To understand why full-covariance methods break down, we must look at the computational tax imposed by maintaining an explicit $n \times n$ matrix, where $n$ is the number of dimensions.
Standard Full-Covariance Step:
[Sample/Gradient] ──> [Update Matrix: O(n²)] ──> [Decompose/Invert: O(n³)] ──> [Transform Step]
This tax is levied in three distinct currencies:
- Space Complexity ($O(n^2)$): Storing a full covariance matrix requires memory that scales quadratically with the number of parameters. For modern machine learning models with millions of parameters, simply holding this matrix in memory is impossible.
- Time Complexity ($O(n^3)$): It is not enough to simply store the matrix; the algorithm must actively use it to generate new search points or condition gradients. As noted by Daan Wierstra et al. in their foundational work on Natural Evolution Strategies, modeling full dependencies typically requires matrix operations—such as inversion or eigendecomposition—that scale cubically.
- Sample Complexity ($O(n^2)$): To reliably estimate a full covariance matrix without it becoming singular or noisy, an algorithm needs a quadratic number of function evaluations relative to the dimensionality. As Youhei Akimoto et al. point out in their work on Diagonal Acceleration, this sample overhead makes standard evolution strategies impractical for high-dimensional spaces where evaluating the objective function is expensive.
When $n$ is small, the benefits of affine invariance outweigh these costs. But as $n$ scales into the thousands, the internal matrix algebra begins to dominate the total execution time, rendering the algorithms prohibitively slow.
To scale optimization to truly high-dimensional problems, researchers have developed several distinct strategies to bypass or break this bottleneck.
Strategy 1: Direct Factorization Updates
The most direct way to attack the cubic time bottleneck is to avoid full matrix decompositions altogether. In standard CMA-ES, the covariance matrix is updated, and then an explicit eigendecomposition ($O(n^3)$) is performed to find the matrix square root needed to sample next-generation candidates.
To bypass this, Oswin Krause et al. introduced Cholesky-CMA-ES. Instead of maintaining and decomposing the covariance matrix $\Sigma$, the algorithm directly maintains and updates its lower triangular Cholesky factor $A$, where $\Sigma = AA^T$.
By applying rank-one updates directly to the Cholesky factor, the authors reduced the per-iteration time complexity from cubic $O(n^3)$ to an optimal quadratic $O(n^2)$. A similar insight was leveraged by Thorsten Suttorp et al. to achieve efficient covariance updates for variable metric evolution strategies.
While direct factorization drops the time complexity by a full factor of $n$, it still leaves the quadratic $O(n^2)$ space and sample complexity intact. For problems involving millions of parameters, further approximations are required.
Strategy 2: Matrix Sketching and Low-Rank Approximations
In many high-dimensional problems, variables do not interact uniformly. Instead, the significant correlations are often confined to a small, low-dimensional subspace, while the rest of the landscape behaves like a simple coordinate-aligned space. Matrix sketching exploits this property by tracking only the dominant directions of variance.
In the context of adaptive subgradient methods (which face identical bottlenecks when tracking full second-moment matrices for deep networks), Sifan Yang et al. proposed using a streaming data sketching technique called "Frequent Directions" in Dimension-Free Adaptive Subgradient Methods with Frequent Directions.
Full Second-Moment Matrix (n x n) ──> Frequent Directions Sketch (k x n)
[ O(n²) Space ] [ O(kn) Space ]
Instead of maintaining the full $n \times n$ matrix, their framework maintains a compact sketch of size $k \times n$, where $k \ll n$ represents the number of frequent directions. By performing a spectral compensation trick on this low-rank sketch, the authors slashed the per-round time complexity from quadratic to linear with respect to the sketch size, achieving regret bounds that are entirely independent of the ambient dimensionality.
Strategy 3: Hybrid Scaling and Diagonal Acceleration
Another powerful approach is to separate the problem into two parts: coordinate-wise scaling (the diagonal elements of the covariance matrix) and structural correlations (the off-diagonal elements). Coordinate-wise scaling can be learned rapidly with linear complexity, while full correlations take much longer to resolve.
This is the core intuition behind dd-CMA-ES, introduced by Youhei Akimoto et al. in Diagonal Acceleration for Covariance Matrix Adaptation Evolution Strategies. The algorithm adaptively injects a diagonal matrix acceleration step alongside the full covariance adaptation.
Early in the optimization process, or when the landscape is roughly coordinate-separable, the diagonal acceleration drives progress at a fraction of the computational cost. As the algorithm converges on highly correlated sub-regions, the full covariance adaptation takes over. This hybrid approach drastically reduces the sample complexity penalty, allowing the algorithm to converge quickly on simple landscapes without sacrificing its robustness on highly correlated ones.
Strategy 4: Replacing Matrices with Generative Models
Perhaps the most radical departure from traditional covariance tracking is to abandon explicit matrices altogether. If the purpose of a covariance matrix in an evolution strategy is merely to define a Gaussian distribution from which to sample the next generation of solutions, can we replace the matrix with a model that implicitly captures these dependencies?
In Neural Evolution Strategy for Black-box Pareto Set Learning, Chengyu Lu et al. tackle multi-objective optimization problems where traditional evolution strategies scale poorly due to explicit matrix tracking. The authors substitute the explicit covariance matrix with a deep neural network trained to model the distribution of high-performing candidates.
Because neural networks can learn non-linear, low-dimensional representations of high-dimensional dependencies through their internal layers, they bypass the explicit $O(n^2)$ storage and $O(n^3)$ inversion constraints entirely. This allowed the authors to scale black-box Pareto set learning to problems exceeding 1,000 dimensions.
Summary of Trade-offs
The research direction is a continuous spectrum of trade-offs between geometric precision and computational scalability:
| Approach | Representative Work | Time Complexity | Space Complexity | Primary Benefit |
|---|---|---|---|---|
| Full Covariance (Standard) | Wierstra et al. | $O(n^3)$ | $O(n^2)$ | Perfect affine invariance; handles arbitrary correlations. |
| Direct Factorization | Krause et al. | $O(n^2)$ | $O(n^2)$ | Eliminates the cubic decomposition bottleneck entirely. |
| Matrix Sketching | Yang et al. | $O(k^2 n)$ | $O(kn)$ | Reduces memory and time to linear in the dimension $n$. |
| Diagonal Acceleration | Akimoto et al. | Hybrid | Hybrid | Drastically reduces sample complexity on separable landscapes. |
| Neural Parameterization | Lu et al. | Varies | Varies | Captures non-linear, complex dependencies without explicit matrices. |
By transitioning from explicit, dense matrix representations to structured factorizations, sketches, and implicit models, recent optimization frameworks successfully break the quadratic and cubic walls. The reader should take away that the full covariance matrix is not an irreplaceable requirement for geometric optimization; rather, it is a luxury that can be sketched, factored, or parameterized away to unlock scalability in high-dimensional spaces.
Key Foundational Work
Real-coded GA for High-dimensional k-tablet Structures: Proposal and Evaluation of Latent Variable Crossover LUNDX-m (2004) — contributed 1 concept elements to this direction.
Efficient covariance matrix update for variable metric evolution strategies (2009) — contributed 1 concept elements to this direction.