Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

arXiv:2603.10485v3 Announce Type: replace-cross Abstract: 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: R^{d imes k} o R is convex and apply nabla K(dot) to train an over-parameterized linear model with a convex loss of the form ell(X W - Y), for weights W in R^{d imes k}, labels Y in R^{n imes k} and data X in R^{n imes 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_{infty} in R^{d imes k} satisfying XW_{infty} = Y. We also study the implicit bias of Dual Space Preconditioned Gradient Descent. First, we demonstrate analytically and empirically that, for general K(dot), W_infty 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, |W_0 - W_{infty}|F le c |W_0 - W{ext{GD}, infty}|F for a constant c>0 and W{ext{GD}, infty} denoting the convergence point of GD initialized at W_0. 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 W{ext{GD}, infty}. Finally, in the experiments, we demonstrate faster convergence on a nonlinear model obtained using the smoothed matrix elastic-net as a preconditioner.

Source: arXiv cs.LG | 2026-08-12