# Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

arXiv: https://arxiv.org/abs/2603.10485 · HTML: https://mlsanity.com/paper/2603.10485/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 48 references that are in the map.
- First posted on arXiv 11 Mar 2026.

## Builds on (most cited first, 30 of 31)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [The Marginal Value of Adaptive Gradient Methods in Machine Learning](https://mlsanity.com/paper/1705.08292/) (2017)
- [Old Optimizer, New Norm: An Anthology](https://mlsanity.com/paper/2409.20325/) (2024)
- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [Implicit Bias of AdamW: ℓ_∞ Norm Constrained Optimization](https://mlsanity.com/paper/2404.04454/) (2024)
- [Lion Secretly Solves Constrained Optimization: As Lyapunov Predicts](https://mlsanity.com/paper/2310.05898/) (2023)
- [Preconditioned Stochastic Gradient Descent](https://mlsanity.com/paper/1512.04202/) (2015)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization](https://mlsanity.com/paper/1906.03830/) (2019)
- [The Implicit Bias of Adam on Separable Data](https://mlsanity.com/paper/2406.10650/) (2024)
- [Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization](https://mlsanity.com/paper/1806.00952/) (2018)
- [Preconditioner on Matrix Lie Group for SGD](https://mlsanity.com/paper/1809.10232/) (2018)
- [The Implicit Bias of AdaGrad on Separable Data](https://mlsanity.com/paper/1906.03559/) (2019)
- [Curvature-Informed SGD via General Purpose Lie-Group Preconditioners](https://mlsanity.com/paper/2402.04553/) (2024)
- [Dual Space Preconditioning for Gradient Descent](https://mlsanity.com/paper/1902.02257/) (2019)
- [Regularized Linear Regression for Binary Classification](https://mlsanity.com/paper/2311.02270/) (2023)
- [Anisotropic Proximal Gradient](https://mlsanity.com/paper/2210.15531/) (2022)
- [Stochastic Hessian Fittings with Lie Groups](https://mlsanity.com/paper/2402.11858/) (2024)
- [Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness](https://mlsanity.com/paper/2502.08532/) (2025)
- [Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning](https://mlsanity.com/paper/2509.15817/) (2025)
- [Dualities for non-Euclidean smoothness and strong convexity under the light of generalized conjugacy](https://mlsanity.com/paper/2112.08886/) (2021)
- [Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis](https://mlsanity.com/paper/2510.11312/) (2025)

## Abstract (arXiv)

In this work, we study the convergence properties of the Dual Space Preconditioned Gradient Descent, encompassing optimizers such as Normalized Gradient Descent and Gradient Clipping. We consider preconditioners of the form nabla K, where K: ℝd × k → ℝ is convex and apply nabla K(·) to train an over-parameterized linear model with a convex loss of the form ℓ(X W - Y), for weights W ∈ ℝd × k, labels Y ∈ ℝn × k and data X ∈ ℝn × d. Under the aforementioned assumptions, we prove that the iterates of the full-batch preconditioned gradient descent converge at an exponential rate to a point W∞ ∈ ℝd × k satisfying XW∞ = Y. We also study the implicit bias of Dual Space Preconditioned Gradient Descent. First, we demonstrate analytically and empirically that, for general K(·), W_∞ depends on the chosen constant step size, hindering a precise characterization of the implicit bias. We also provide an approximate implicit bias property for general preconditioners, namely, |W0 - W∞|F ≤ c |W0 - WGD, ∞|F for a constant c>0 and WGD, ∞ denoting the convergence point of GD initialized at W0. Furthermore, for preconditioners of the form K(G) = h(|G|F), known as it isotropic preconditioners, and for the stochastic variation of the algorithm with arbitrary batch-size, we prove linear convergence to WGD, ∞. Finally, in the experiments, we demonstrate faster convergence on a nonlinear model obtained using the smoothed matrix elastic-net as a preconditioner.