View PDF HTML (experimental)

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: \mathbb{R}^{d \times k} \to \mathbb{R}$ is convex and apply $\nabla K(\cdot)$ to train an over-parameterized linear model with a convex loss of the form $\ell(X W - Y)$, for weights $W \in \mathbb{R}^{d \times k}$, labels $Y \in \mathbb{R}^{n \times k}$ and data $X \in \mathbb{R}^{n \times 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 \mathbb{R}^{d \times 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(\cdot)$, $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_{\text{GD}, \infty}\|_F$ for a constant $c>0$ and $W_{\text{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_{\text{GD}, \infty}$. Finally, in the experiments, we demonstrate faster convergence on a nonlinear model obtained using the smoothed matrix elastic-net as a preconditioner.

Submission history

From: Reza Ghane [view email]
[v1] Wed, 11 Mar 2026 07:19:52 UTC (217 KB)
[v2] Tue, 17 Mar 2026 21:55:00 UTC (217 KB)
[v3] Mon, 10 Aug 2026 19:23:31 UTC (381 KB)