Randomized Subspace Methods for High Dimensional Optimization

30 concepts25 papers2 proposals

When optimizing functions in high-dimensional spaces, we inevitably run into the curse of dimensionality. Whether we are trying to compute a second-order Hessian matrix, maximize an acquisition function in Bayesian optimization, or update the weights of a large language model, the computational and memory costs scale poorly with the number of dimensions $d$.

The core intuition behind randomized subspace optimization is that we do not need to solve the entire high-dimensional problem all at once. Instead, we can project the problem onto a sequence of much smaller, low-dimensional subspaces ($k \ll d$) at each iteration. By solving these smaller subproblems and dynamically changing the subspace over time, we can navigate the full high-dimensional landscape efficiently while drastically reducing per-iteration costs.


The Core Intuition: Why Subspaces Work

To understand why subspace optimization works, imagine trying to find the lowest point in a massive, multi-dimensional valley. Instead of looking in every possible direction simultaneously, you choose a small, random slice of directions (a subspace), find the best step within that slice, and then pick a new random slice for your next step.

As long as the sequence of random subspaces eventually covers the entire parameter space, this iterative process will converge to the global optimum. Kozak et al. demonstrated that projecting gradients onto low-dimensional random subspaces preserves enough directional information to guarantee linear convergence for strongly convex functions.

Subspaces can be constructed in several ways:

  1. Axis-Aligned Subspaces (Coordinate Blocks): Selecting a random subset of the original coordinates. This is often called "dropout" or block coordinate descent.
  2. Random Projections: Multiplying the gradient or parameter space by a random matrix (e.g., a Gaussian matrix) to map it to a lower-dimensional space.
  3. Data-Dependent Subspaces: Using techniques like sketching or Singular Value Decomposition (SVD) to find the most informative directions based on recent gradients or curvature.

To avoid sampling bias and ensure convergence in non-separable problems, the gradient steps must be carefully scaled. For instance, Grishchenko et al. showed that scaling the gradient step by the inverse square root of the expected projection matrix corrects for the distortion introduced by subspace sampling.


Taming Second-Order Curvature

Second-order optimization methods, like Newton's method or cubic regularization, are highly desirable because they use curvature information to navigate ill-conditioned landscapes in fewer iterations. However, computing and inverting a full Hessian matrix costs $O(d^3)$ time and $O(d^2)$ memory—making it completely impractical for high-dimensional problems.

Subspace methods solve this by restricting the second-order calculations to a small subspace of dimension $k$. This drops the cost of Hessian inversion from $O(d^3)$ to $O(k^3)$.

Full Space Newton:    [   Hessian Matrix (d x d)   ] -> Inversion: O(d³)
Subspace Newton:      [ H (k x k) ]                  -> Inversion: O(k³)

Several variations of this idea have been developed:

  • Coordinate Subspaces: Lu introduced a randomized block proximal damped Newton method that solves subproblems using curvature restricted to a chosen block of coordinates. Similarly, Hanzely et al. and Zhao et al. applied cubic regularization to random coordinate subspaces, achieving fast convergence with a fraction of the full-space overhead.
  • Random Projections: Instead of aligning with coordinates, Hanzely developed a "sketch-and-project" Newton method that projects updates onto a lower-dimensional random subspace while maintaining robust global convergence rates. Higuchi et al. extended this to non-convex optimization using a random Gaussian matrix within a trust-region framework.
  • Hybrid Updates: Rather than ignoring the rest of the space, Jahani et al. proposed concentrating second-order curvature information within a low-dimensional subspace while simultaneously applying cheap, first-order gradient updates to the orthogonal complement.
  • Krylov Subspaces: Gratton et al. demonstrated that optimization can be restricted to Krylov subspaces using only Hessian-vector products, allowing algorithms to escape saddle points without ever explicitly evaluating the full Hessian or objective function.

Scaling Bayesian and Zeroth-Order Optimization

The benefits of subspace restriction extend beyond gradient-based optimization to derivative-free regimes like Bayesian Optimization (BO) and Zeroth-Order (ZO) optimization.

In Bayesian Optimization, we construct a probabilistic surrogate model of a black-box function and maximize an acquisition function to choose the next evaluation point. However, maximizing this acquisition function in a high-dimensional space is itself a difficult, non-convex optimization problem.

To bypass this bottleneck, researchers restrict the acquisition search space:

  • Dropout-inspired Selection: Li et al. proposed optimizing the acquisition function over a small, randomly selected subset of dimensions at each iteration, ensuring all variables are eventually explored over time.
  • Discrete Subspaces: Tran-The et al. simplified the problem by restricting the search to a discrete set of randomly sampled low-dimensional subspaces, allowing users to explicitly trade off their computational budget for convergence speed.
  • One-Dimensional Lines: Taking this to the extreme, Mutný introduced an algorithm that iteratively solves one-dimensional sub-problems, completely sidestepping the curse of dimensionality during the acquisition step.

For zeroth-order settings where gradients are unavailable and must be estimated via finite differences, exploring every direction is prohibitively expensive. Cheng et al. and Berglund et al. showed that estimating gradients and Hessians exclusively within a lower-dimensional sketched or random subspace makes zeroth-order optimization scalable to massive systems.


Breaking the Memory Wall in LLM Training

As Large Language Models (LLMs) grow, the memory required to store optimizer states (like the moving averages in Adam) becomes a major bottleneck. Subspace optimization has emerged as a powerful strategy to compress these states.

Early low-rank adaptation methods relied on Singular Value Decomposition (SVD) to find the most important directions for gradient projection. However, computing SVD frequently is computationally expensive. Recent work shows that pure randomness can substitute for SVD without sacrificing performance.

Liu et al. demonstrated that randomly generated Gaussian matrices are sufficient to map high-dimensional gradients into a lower-dimensional subspace, preserving the optimization benefits of the original system while bypassing expensive SVD computations. Similarly, Chen et al. introduced a framework that decomposes high-dimensional training into smaller, random subproblems, slashing optimizer states, activation memory, and communication overhead simultaneously.

When structured subspace information is desired, it can be done efficiently. Refael et al. utilized randomized SVD to dynamically adapt a low-rank subspace for gradient projection, capturing the dominant directions of the loss landscape with minimal computational cost.

By shifting the optimization burden from the full, high-dimensional space to a rotating sequence of low-dimensional subspaces, these methods allow us to train larger models and solve harder optimization problems using a fraction of the memory and time.

Key Foundational Work

High Dimensional Bayesian Optimization Using Dropout (2017) — contributed 2 concept elements to this direction.
Randomized block proximal damped Newton method for composite self-concordant minimization (2016) — contributed 1 concept elements to this direction.
Feature-distributed sparse regression: a screen-and-clean approach (2016) — 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_subspace_constrained_acquisition_optimiz_b797975e,
  title = {subspace-constrained acquisition optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subspace-constrained-acquisition-optimization/rdr_b797975e160647f29cfcc4789f296db6},
  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_subspace_constrained_acquisition_optimiz_b797975e_v1,
  title = {subspace-constrained acquisition optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subspace-constrained-acquisition-optimization/rdr_b797975e160647f29cfcc4789f296db6/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