In classical optimization theory, the dimension $d$ of a parameter space is often treated as a fundamental tax on performance. Traditional worst-case bounds suggest that as the number of variables grows, optimization algorithms should slow down polynomially or exponentially. Yet, modern machine learning routinely defies this "curse of dimensionality." Models with billions of parameters, such as large language models, converge efficiently, and algorithms operating on infinite-dimensional functional spaces remain remarkably stable.
This discrepancy has driven a major research direction focused on dimension-free (or dimension-independent) convergence. The core insight is that the difficulty of an optimization problem is not dictated by its ambient parameter count, but rather by its intrinsic geometry, structural constraints, or the adaptive nature of the optimizer itself. When these properties are properly aligned, the iteration complexity required to reach a solution remains completely invariant—or scales only logarithmically—with the dimension of the space.
Reshaping Geometry via Adaptive Step Sizes
Standard gradient descent treats every direction in a parameter space uniformly, which causes updates to oscillate wildly in high-dimensional, poorly conditioned landscapes. Adaptive optimizers circumvent this by dynamically adjusting step sizes based on the local geometry of the objective function.
The theoretical foundation for why adaptive methods scale so gracefully is deeply tied to how they model noise and curvature. For instance, Shuo Xie et al. in A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent demonstrate that by modeling noise through adaptive gradient variance rather than standard variance, optimization methods can achieve convergence rates that do not degrade as model dimensionality increases. This explains the immense scalability of normalized steepest descent methods. Similarly, Haochuan Li et al. in Convergence of Adam Under Relaxed Assumptions prove that the convergence rate of adaptive momentum optimizers like Adam is fundamentally dimension-free under realistic conditions, ensuring stable iteration complexity even as architectures scale to billions of parameters.
This geometric flattening can also be achieved through scalar step-size rules or matrix operations:
- Local Geometry Alignment: Antonio Orvieto et al. show in Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution that utilizing a scalar step size based on local function geometry yields dimension-independent convergence, providing a distinct theoretical advantage over coordinate-wise methods.
- Matrix Orthogonalization: In On the Convergence of Muon and Beyond, Da Chang et al. establish that matrix-orthogonalizing optimizers possess dimension-independent convergence bounds, explaining their empirical success in training massive weight matrices.
- Implicit Gradient Transport: Ashok Cutkosky et al. demonstrate in Momentum Improves Normalized SGD. that adding momentum to normalized SGD eliminates the need for massive batch sizes on non-convex objectives, securing dimension-free convergence rates.
However, explaining the exact magnitude of this advantage remains an active area of research. As noted by Elad Hazan et al. in Open Problem: Black-Box Reductions and Adaptive Gradient Methods for Nonconvex Optimization, standard theoretical models still struggle to fully explain why adaptive optimizers outperform standard stochastic gradient descent by factors related to the square root of the problem dimension in practical high-dimensional settings.
Exploiting Effective Dimension and Sparsity
Another reason why dimension-free convergence is achievable is that high-dimensional data and models often live on much lower-dimensional manifolds. Algorithms can exploit this by targeting the effective dimension or intrinsic sparsity of the problem.
This principle is particularly vital in zeroth-order (gradient-free) optimization, which traditionally suffers from a severe curse of dimensionality because it relies on random isotropic perturbations. Congliang Chen in Unlocking Black-Box Prompt Tuning Efficiency via Zeroth-Order Optimization proves that when a loss function satisfies specific geometric properties, the convergence rate of zeroth-order optimization becomes nearly independent of the large ambient dimension, allowing black-box prompt tuning to scale efficiently.
Ambient Parameter Space (Dimension d)
┌────────────────────────────────────────────────────────┐
│ .
* .
* .
* .
* │
│ ┌──────────────────────────────────────────┐ │
│ │ Effective Subspace (Intrinsic Dimension) │ │
│ │ ───► Optimization Path │ │
│ └──────────────────────────────────────────┘ │
│ * .
* .
* .
* . │
└────────────────────────────────────────────────────────┘
By confining updates or perturbations to the effective dimension,
the algorithm's convergence rate becomes independent of the ambient space.
Several distinct strategies leverage this low-dimensional behavior:
- Jacobian-Targeted Updates: Pengyun Yue et al. in PseuZO: Pseudo-Zeroth-Order Algorithm for Training Deep Neural Networks focus on the Jacobian of the model output rather than the entire parameter space, ensuring the convergence rate is less sensitive to massive parameter scaling.
- Sparse Perturbations: In Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization, Mayumi Ohta et al. show that restricting perturbations to a sparse subset of parameters bounds the convergence rate by the number of perturbed parameters rather than the total dimensionality.
- Logarithmic Ambient Scaling: When explicit sparsity assumptions are met, Yining Wang et al. demonstrate in Stochastic Zeroth-order Optimization in High Dimensions. that zeroth-order algorithms can achieve convergence rates that depend only logarithmically on the ambient dimension.
- Weak Dimension Dependency: Pengyun Yue et al. further establish in Zeroth-order Optimization with Weak Dimension Dependency that tasks like linear regression with normalized data can achieve completely dimension-free convergence in zeroth-order settings.
This structural independence extends to first-order coordinate methods and statistical estimation. The authors of Efficient Greedy Coordinate Descent for Composite Problems. prove that greedy coordinate descent can achieve convergence rates for non-smooth composite problems that are independent of the total number of features, overturning previous theoretical assumptions that favored random selection. In high-dimensional M-estimation, Tianqi Qiao et al. introduce the Sparse Polyak step-size rule, which achieves "rate invariance"—meaning the number of iterations required to reach a solution depends solely on the sample size and intrinsic sparsity rather than the ambient feature dimension.
Convergence in Infinite-Dimensional Spaces
The ultimate proof of dimension-free optimization occurs when algorithms are applied directly to infinite-dimensional spaces, such as Reproducing Kernel Hilbert Spaces (RKHS) or functional spaces governed by partial differential equations (PDEs). If an algorithm's convergence rate remains stable in an infinite-dimensional space, it is inherently dimension-free.
In Dimension-free convergence rates for gradient Langevin dynamics in RKHS, Boris Muzellec et al. show that Gradient Langevin Dynamics (GLD) can achieve non-asymptotic, dimension-free convergence rates when optimization occurs in a space characterized by structured spectral decay. Instead of counting dimensions, the complexity is governed by how fast the eigenvalues of the space decay, bypassing the curse of dimensionality entirely.
This functional perspective alters how we analyze neural networks and statistical models:
- Mean-Field Neural Networks: Naoki Nishikawa et al. study training on infinite-dimensional data in Two-layer neural network on infinite dimensional data: global optimization guarantee in the mean-field regime. By utilizing Gaussian measures and Radon-Nikodym derivatives, they prove that the difficulty of training does not scale with data dimensionality, enabling the processing of bottomless input spaces.
- PDE Regularization: Neil K. Chada et al. demonstrate in Consistency analysis of bilevel data-driven learning in inverse problems that learning regularization parameters in PDE models exhibits dimension independence, meaning convergence depends on the underlying physics rather than the grid resolution.
- Gradient Boosting as Kernel Inference: Aleksei Ustimenko et al. establish in Gradient Boosting Performs Gaussian Process Inference that regularized gradient boosting with symmetric trees is equivalent to solving a Kernel Ridge Regression problem, resulting in convergence rates independent of input dimensionality.
Bypassing Geometric Bottlenecks: Saddles, Constraints, and Subspaces
High-dimensional landscapes are notorious for geometric traps, such as an exponential proliferation of saddle points and highly complex constraint sets. Dimension-free convergence works here by leveraging inherent stochasticity or confining the optimization path to informed subspaces.
In non-convex optimization, escaping saddle points typically slows down as the dimension increases because the algorithm must find a specific direction of negative curvature. However, the authors of Escaping Saddles with Stochastic Gradients demonstrate that the natural noise inherent in Stochastic Gradient Descent (SGD) is uniquely structured to escape saddle points at a rate completely independent of the parameter space's dimensionality. When optimizing over smooth manifolds, Yue Sun et al. prove in Escaping from saddle points on Riemannian manifolds that the convergence rate scales polylogarithmically with the manifold's dimension, preserving high efficiency in extreme dimensions.
Saddle Point Landscape
▼ (Stochastic Gradient Descent)
┌───────────┐
│ ░ ░ ░ ░ ░ │ ◄── Inherent "natural" noise explores all directions simultaneously
└─────┬─────┘
▼
Escapes along negative curvature at a dimension-independent rate.
When constraints are introduced, standard methods often require expensive global projections that scale poorly. To avoid this, algorithms can restrict their operations to low-dimensional subspaces or exploit dual structures:
- Krylov Subspaces: The authors of Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate introduce a second-order method that computes updates exclusively within an informed Krylov subspace, achieving a dimension-free convergence rate while maintaining manageable per-iteration costs.
- Strongly Convex Sets: Dan Garber demonstrates in Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets that the vanilla Frank-Wolfe algorithm achieves an accelerated $O(1/t^2)$ convergence rate that is completely independent of the problem's dimension when operating over strongly convex sets.
- Nonlinear and Bilevel Constraints: Michael Muehlebach et al. show in Accelerated first-order optimization under nonlinear constraints that accelerated first-order methods can achieve optimal convergence rates independently of dimensionality under nonlinear constraints. For bilevel optimization, Guy Kornowski et al. prove in First-Order Methods for Linearly Constrained Bilevel Optimization that access to optimal dual variables isolates the convergence rate from the problem's ambient dimension.
Particle Dynamics and Alternative Learning Paradigms
The paradigm of dimension-free convergence manifests across several other specialized optimization frameworks, including particle-based global optimization, federated learning, and robust estimation.
In derivative-free global optimization, methods like Consensus-Based Optimization (CBO) replace gradients with a swarm of interacting particles. Massimo Fornasier et al. demonstrate in Convergence of Anisotropic Consensus-Based Optimization in Mean-Field Law that incorporating anisotropic noise scaling allows CBO to converge globally at a rate independent of the problem's dimensionality. This mathematical framework effectively "convexifies" difficult landscapes, a property further extended to spherical domains by Massimo Fornasier et al. in Consensus-based Optimization on the Sphere II: Convergence to Global Minimizers and Machine Learning.
This independence from ambient dimensionality is also a recurring theme across diverse machine learning settings:
- Vertical Federated Learning (VFL): Ganyu Wang et al. show in A Unified Solution for Privacy and Communication Efficiency in Vertical Federated Learning and Secure and fast asynchronous Vertical Federated Learning via cascaded hybrid optimization that restricting zeroth-order optimization to a client's output layer forces the convergence rate to depend on the low-dimensional embedding size or client-side feature extractor rather than the massive server-side parameter space.
- Asynchronous Parallelism: Cong Fang et al. prove in Parallel Asynchronous Stochastic Variance Reduction for Nonconvex Optimization that the convergence of asynchronous variance-reduced gradient methods (ASVRG) is independent of dimensionality, ensuring consistent parallel speedups on high-dimensional deep networks.
- Robust Online Estimation: In Online robust non-stationary estimation, Abishek Sankararaman designs update rules based on the intrinsic geometry of the parameter space, ensuring that error bounds do not scale with the number of input features even under heavy-tailed noise and non-stationarity.
- Strategic Classification: The authors of One-Shot Strategic Classification Under Unknown Costs show that under standard cost structures, utilizing dual norm regularization yields a convergence rate to a minimax optimal solution that is completely independent of the number of input features.
- Structured Prediction and Conditional Gradients: Artem Sokolov et al. demonstrate in Stochastic Structured Prediction under Bandit Feedback that stochastic first-order methods can achieve convergence rates independent of feature space dimensionality. Similarly, Kazuma Tsuji et al. show in Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding that a blending rule prioritizing local progress eliminates inefficient swap steps, yielding dimension-independent convergence in conditional gradient methods.
Fundamental Limits
While dimension-free convergence highlights the optimistic structures present in practical problems, it operates within strict theoretical boundaries. In On the Iteration Complexity of Oblivious First-Order Optimization Algorithms, Yossi Arjevani et al. establish dimension-independent lower bounds for algorithms that pre-schedule step sizes based solely on smoothness and convexity. Their work confirms that the convergence limits of standard gradient methods are fundamental to the algorithm's internal logic rather than an artifact of high-dimensional spaces.
Ultimately, dimension-free convergence works because it shifts the mathematical burden of optimization from the size of the container (the ambient dimension) to the shape of the content (the intrinsic geometry, sparsity, and spectral decay). Whether through adaptive step sizes that flatten the landscape, or noise that naturally navigates high-dimensional traps, understanding these mechanisms explains why modern, massive models remain so remarkably trainable.
Key Foundational Work
Convex Optimization: Algorithms and Complexity (2015) — contributed 2 concept elements to this direction.