Condition-Independent Convergence via Scaled Gradient Descent

48 concepts33 papers1 proposal

When optimizing low-rank structures—such as factorizing a matrix, completing a tensor, or training a low-rank adapter for a large language model—standard first-order optimization algorithms frequently stall. The root cause of this slowdown is ill-conditioning.

If the target matrix or tensor contains singular values of widely varying magnitudes, the optimization landscape becomes warped into a steep, narrow valley. Standard Gradient Descent (GD) or Stochastic Gradient Descent (SGD) spends iterations bouncing back and forth across the steep walls of the valley while making negligible progress along its flat floor. The number of iterations required for convergence scales linearly with the condition number ($\kappa = \sigma_{\max}/\sigma_{\min}$), meaning that highly ill-conditioned problems become practically intractable.

A rapidly growing body of research resolves this bottleneck through factor-scaled preconditioning. By multiplying the vanilla gradient by the inverse of a factor matrix's own Gram matrix, this approach reshapes the optimization landscape. Crucially, it achieves condition-number-independent convergence, allowing optimization to proceed at a rate completely decoupled from the underlying data's singular values.


The Geometry of Ill-Conditioning

To understand why standard gradient descent fails and how factor-scaled preconditioning fixes it, consider the classic non-convex matrix factorization problem. We want to find two low-rank matrices, $U$ and $V$, such that their product approximates a target matrix $M$:

$$\min_{U, V} \frac{1}{2} \|UV^T - M\|_F^2$$

The gradient of this objective function with respect to $U$ is given by:

$$\nabla_U f(U,V) = (UV^T - M)V$$

Now, imagine the target matrix $M$ has a tiny singular value $\sigma_{\min}$. To reconstruct this component of the matrix, the corresponding columns of the factor matrices $U$ and $V$ must also shrink to a scale of roughly $\sqrt{\sigma_{\min}}$.

Because $V$ is exceptionally small in this direction, the gradient $\nabla_U f(U,V)$—which is multiplied by $V$—becomes vanishingly small. Standard gradient descent takes a step proportional to this gradient:

$$U_{t+1} = U_t - \eta \nabla_U f(U_t, V_t)$$

As a result, the update to $U$ along the direction of the weak signal is minute. The optimization process enters a state of stagnation, requiring $\mathcal{O}(\kappa)$ iterations to recover the weak components of the signal.


The Core Mechanism: Factor-Scaled Preconditioning

Instead of taking a standard gradient step, factor-scaled preconditioning transforms the update by multiplying the gradient by a local, structure-aware preconditioner. For the factor matrix $U$, the gradient is multiplied by the inverse of the other factor's Gram matrix, $(V^T V)^{-1}$.

The modified update rules for Scaled Gradient Descent (ScaledGD) become:

$$U_{t+1} = U_t - \eta \nabla_U f(U_t, V_t) (V_t^T V_t)^{-1}$$ $$V_{t+1} = V_t - \eta \nabla_V f(U_t, V_t) (U_t^T U_t)^{-1}$$

This simple transformation acts as a highly efficient quasi-Newton step, but it avoids the massive computational burden of calculating and inverting a full Hessian matrix.

Why It Works: The Self-Balancing Act

The intuition behind why ScaledGD eliminates the condition number is a beautiful act of mathematical cancellation:

  1. The Vanishing Gradient: As shown before, when a singular value is tiny, the factor matrix $V$ in that direction is small, which causes the vanilla gradient $\nabla_U f(U,V)$ to shrink proportionally to $\sqrt{\sigma_{\min}}$.
  2. The Exploding Preconditioner: Because $V$ is small in that direction, the Gram matrix $V^T V$ also has a tiny eigenvalue. Crucially, when we take its inverse, $(V^T V)^{-1}$, that tiny eigenvalue flips into a massive eigenvalue proportional to $1/\sigma_{\min}$.
  3. Perfect Cancellation: When we multiply the vanishing gradient by the exploding preconditioner, the small and large terms cancel each other out perfectly.

By normalizing the internal scales of the problem, the step size is automatically amplified in the exact directions where the signal is weakest. Weak signal components are recovered just as efficiently as strong ones. As Xixi Jia demonstrates in Preconditioning Matters: Fast Global Convergence of Non-convex Matrix Factorization via Scaled Gradient Descent, this mechanism ensures that the convergence rate remains completely invariant to the target matrix's condition number, even when starting from random initializations.

This foundational insight spans multiple applications. For instance, Bamdev Mishra et al. apply this scaling to matrix completion in Scaled stochastic gradient descent for low-rank matrix completion, showing that balancing local and global second-order information flattens the optimization landscape for highly sparse or ill-conditioned matrices. Similarly, Jian-Feng Cai et al. leverage Jacobi preconditioning in Fast Spectrally Sparse Signal Reconstruction via Jacobi-Preconditioned Gradient Descent to ensure that weak signal components are recovered at the same rate as dominant ones.


In real-world scenarios, the exact rank of the underlying matrix or tensor is rarely known. Practitioners typically overparameterize the model by choosing a rank $r$ that is larger than the true rank $r^*$.

Overparameterization introduces a severe mathematical complication: the target matrix contains singular values that are exactly zero. For standard gradient descent, this creates a landscape riddled with flat saddle points and singular regions where optimization stalls indefinitely. For preconditioned methods, an unregularized inverse Gram matrix $(U^T U)^{-1}$ would blow up to infinity near these rank-deficient regions, causing numerical divergence.

To preserve condition-independent convergence in overparameterized settings, researchers introduce adaptive damping mechanisms. The preconditioner is regularized by adding a self-adjusting parameter $\lambda \cdot I$:

$$(U^T U + \lambda I)^{-1}$$

Gavin Zhang et al. prove in Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization and Preconditioned Gradient Descent for Overparameterized Nonconvex Burer-Monteiro Factorization with Global Optimality Certification that this adaptive damping allows the optimizer to glide smoothly past mathematical singularities, restoring fast linear convergence.

Further work by Xingyu Xu et al. in The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing confirms that this regularized scaling neutralizes geometric stretching without sacrificing computational simplicity. When data is corrupted by heavy outliers, Paris Giampouras et al. extend this to a subgradient framework in Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery, providing the first linear convergence guarantees for asymmetric matrices of unknown rank under heavy noise.


Generalizing Beyond Matrices

The principle of factor-scaled preconditioning extends far beyond simple two-dimensional matrix factorization. The same core intuition—scaling updates by an inverse representation of the parameter structure—has been successfully generalized to tensors, differential operators, and deep learning architectures.

High-Dimensional Tensors

When recovering multi-dimensional tensors via Tucker or CP decompositions, the optimization landscape becomes even more complex. To combat this, Tian Tong et al. introduce an iteration-varying preconditioner in Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements and Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Completion. By scaling the gradient by the inverse of the Hessian's diagonal blocks, they achieve condition-independent linear convergence for tensor estimation. This framework is adapted to slice-by-slice measurements by Tongle Wu et al. in Non-Convex Tensor Recovery from Local Measurements, bypassing the traditional performance degradation seen in ill-conditioned tensor compressed sensing.

Physics-Informed Neural Networks (PINNs)

Training PINNs is notoriously difficult because the underlying differential equations introduce highly stiff, ill-conditioned loss landscapes. Tim De Ryck et al. address this in An operator preconditioning perspective on training in physics-informed machine learning by multiplying the gradient by the regularized inverse of the training matrix associated with the differential operator, driving the condition number near unity. Similarly, Xianliang Xu et al. demonstrate in Fast Convergence of Natural Gradient Descent for Over-parameterized Physics-Informed Neural Networks that Natural Gradient Descent acts as an implicit Gram-matrix preconditioner, bypassing operator stiffness to achieve convergence rates independent of the system's condition number.

Low-Rank Adaptation (LoRA) for Large Language Models

When fine-tuning large language models on downstream tasks, certain features can be significantly harder to learn than others, creating an ill-conditioned task shift. Yuanhe Zhang addresses this in LoRA-One: One-Step Full Gradient Could Suffice for Fine-Tuning Large Language Models, Provably and Efficiently by integrating preconditioners directly into the low-rank update rules. This ensures stable convergence and prevents training stagnation regardless of the task's underlying condition number. In decentralized settings, Abdulla Jasem Almansoori et al. leverage low-rank preconditioning in Collaborative and Efficient Personalization with Mixtures of Adaptors to stabilize the aggregation of updates from heterogeneous client sources.


Scalable and Stochastic Implementations

While multiplying by an inverse Gram matrix provides excellent convergence properties, doing so at a massive scale requires careful algorithmic design to minimize computational overhead.

Online and Distributed Scaling

For massive-scale matrix completion, Gavin Zhang et al. introduce ScaledSGD in Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion. By right-rescaling stochastic gradient updates with the inverse Gram matrix of the current factor estimates, they achieve condition-independent convergence online without adding significant computational overhead. In the distributed regression domain, Kushal Chakrabarti et al. develop an iteratively preconditioned SGD in Accelerating Distributed SGD for Linear Regression using Iterative Pre-Conditioning to flatten the optimization landscape across distributed nodes.

Structure-Aware Preconditioning

When model parameters are treated as large tensors, maintaining a full covariance matrix is impossible. To bridge this gap, Vineet Gupta et al. design Shampoo in Shampoo: Preconditioned Stochastic Tensor Optimization. Shampoo constructs separate, smaller preconditioners for each dimension of a tensor parameter and applies a $1/2k$ root scaling to maintain stability, providing a computationally cheap alternative to full second-order methods.

Standard SGD:
[Gradient] ───> [Highly Warped Landscape] ───> Slow, Condition-Dependent Steps

Factor-Scaled Preconditioned SGD (e.g., ScaledGD, Shampoo):
[Gradient] ───> [Multiply by Inverse Gram Matrix] ───> [Flattened Landscape] ───> Fast, Uniform Steps

Subspace and Kernel Approximations

For complex convex objectives and kernel methods, computing exact preconditioners remains a bottleneck. Researchers circumvent this using randomized low-rank approximations:

Implicit Preconditioning

Interestingly, preconditioning can sometimes occur implicitly through the choice of optimizer architecture. Ke Liang Xiao demonstrates in Exact risk curves of signSGD in High-Dimensions: quantifying preconditioning and noise-compression effects that taking the sign of the gradient vector implicitly applies a diagonal preconditioner derived from the square root of the data's diagonal covariance, automatically compensating for disparate feature scales.


Summary

The power of factor-scaled preconditioning lies in its geometric elegance. By utilizing the current state of the optimization factors to scale the gradient updates, it creates a self-balancing mechanism. Where the signal is weak, the preconditioner amplifies the step size; where the signal is strong, it tempers it. This simple, elegant feedback loop transforms ill-conditioned optimization landscapes into perfectly balanced spaces, unlocking fast, condition-independent convergence across machine learning.

Key Foundational Work

Least Squares Revisited: Scalable Approaches for Multi-class Prediction (2014) — contributed 2 concept elements to this direction.
Theoretical Analysis of Density Ratio Estimation (2010) — 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_preconditioned_gradient_descent_fda5b85a,
  title = {preconditioned gradient descent},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/preconditioned-gradient-descent/rdr_fda5b85abf604cbd98528f16f516dd5d},
  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_preconditioned_gradient_descent_fda5b85a_v1,
  title = {preconditioned gradient descent},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/preconditioned-gradient-descent/rdr_fda5b85abf604cbd98528f16f516dd5d/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