Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

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.