Overfitting of Spectral Gradient Descent: How Matrix Geometry shapes Generalization and Implicit Bias

Guillaume Braun; Ichiro Hashimoto; Masaaki Imaizumi

stat.MLSep 26, 2026

Overfitting of Spectral Gradient Descent: How Matrix Geometry shapes Generalization and Implicit Bias

Authors: Guillaume Braun, Ichiro Hashimoto, Masaaki Imaizumi

Organizations: University of Toronto · University of Tokyo, RIKEN AIP, Kyoto University

Abstract

We study the generalization of spectral gradient descent (SpecGD) in overparameterized matrix classification with corrupted labels. Each input combines a shared low-rank signal with a rank-one sample-specific perturbation, referred to as a shortcut, that enables memorization but does not generalize. We contrast collapsed shortcuts, which share a singular direction, with dispersed shortcuts, which occupy distinct singular directions. Changing only this geometry can reverse the relative generalization of GD and SpecGD: collapsed shortcuts can favor SpecGD, while dispersed shortcuts can favor GD. In the dispersed regime, exact shortcut orthogonality eliminates the signal from the late-stage SpecGD direction, while vanishing random correlations collectively generate a small but generalization-relevant signal through a second-order effect. To identify the direction selected by SpecGD, which the spectral max-margin problem alone does not determine, we combine a refined analysis of its dual with the exponentiated-gradient dynamics of normalized loss weights. Finally, we show that a single SpecGD step can already interpolate and generalize well, while continued training converges to a direction with substantially worse generalization.

Figures & tables

Figure 1: Late-stage test risk across shortcut geometries (CSM/DSM). Orange indicates $R_{\rm SpecGD}^{\star}\ll R_{\rm GD}^{\star}$ , while blue indicates $R_{\rm GD}^{\star}\ll R_{\rm SpecGD}^{\star}$ . Here $n,D,r,\lambda$ denote sample size, shortcut dimension, signal rank, and shortcut strength, respectively.

Figure 2: SpecGD generalizes for collapsed shortcuts; GD for dispersed shortcuts. Parameters:

n=100

r=1

D=10^{5}

\rho=0.45

\lambda=125

\sigma_{1}=1

T=3D

and

\eta_{k}=0.005(1+k)^{-0.1}

	Parameter regime	GD (late)	SpecGD (late)	SpecGD (one step)
CSM	$\displaystyle n\ll\lambda^{2}\ll r\wedge\sqrt{nD}$	$\displaystyle e^{-\Theta(Dn/\lambda^{4})}$	$\displaystyle e^{-\Theta(D/n)}$	$\displaystyle e^{-\Omega(cD)}$
	$\displaystyle n\vee r\ll\lambda^{2}\ll rn\wedge\sqrt{nD}$	$\displaystyle e^{-\Theta(Dn/\lambda^{4})}$	$\displaystyle e^{-\Theta(D/n)}$	$\displaystyle e^{-\Omega(rD/\lambda^{2})}$
	$\displaystyle r\vee\sqrt{nD}\ll\lambda^{2}\ll rn$	$\displaystyle\frac{1}{2}$	$\displaystyle e^{-\Theta(D/n)}$	$\displaystyle e^{-\Omega(rD/\lambda^{2})}$
DSM †	$\displaystyle n\ll\lambda^{2}\ll D$	$\displaystyle e^{-\Theta(Dn/\lambda^{2})}$	$\displaystyle e^{-\Theta(n)}$	$\displaystyle e^{-\Omega(\sqrt{r}\,D/\lambda)}$
	$\displaystyle D\ll\lambda^{2}\ll D\sqrt{n}$	$\displaystyle e^{-\Theta(D^{2}n/\lambda^{4})}$	$\displaystyle e^{-\Theta(n)}$	$\displaystyle e^{-\Omega(\sqrt{r}\,D/\lambda)}$
	$\displaystyle D\sqrt{n}\ll\lambda^{2}$	$\displaystyle\frac{1}{2}$	$\displaystyle e^{-\Theta(n)}$	$\displaystyle e^{-\Omega(\sqrt{r}\,D/\lambda)}$

Table 1: Representataive test risks of GD and SpecGD. We set

\|S\|_{F}=1

and

\|S\|_{1}=\sqrt{r}

. The displayed regimes are chosen so that one-step SpecGD improves over late-stage SpecGD.

Figure 3: Test error vs. shortcut dimension $K$ and strength $\lambda$ for GD and SpecGD. Parameters: $n=100$ , $r=1$ , $D=10^{5}$ , $\rho=0.45$ , $||S||_{F}=||S||_{1}=1$ , $T=10^{4}$ , $\eta=10^{-2}$ .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Test error as a function of shortcut dimension $K$ and cumulative optimization time $\tau:=\sum_{\ell=0}^{T}\eta_{\ell}$ for GD and SpecGD. Parameters: $n=100$ , $r=1$ , $D=d-r=10^{5}$ , $\rho=0.45$ , $\lambda=125$ , $\eta=10^{-2}$ , and $T=10^{4}$

Figure 5: Test error as a function of the sample size $n$ and ambient dimension $d$ for GD and SpecGD in the random dispersed model, with $r=1$ and $K=D=d-r$ . Parameters: $\rho=0.45$ , $\lambda=125$ , and $\eta=10^{-2}$ . We compare all configurations at fixed normalized optimization time $n\tau/D=1.5$ . Results are averaged over $10$ independent runs.

	Parameter regime	$R(W_{\rm GD}^{\star})$		$R(W^{\star})$
CSM	$\lambda^{2}\ll n\\|S\\|_{F}^{2}$	$\displaystyle e^{-\Theta\!\left(\frac{D}{n}\right)}$		$\displaystyle e^{-\Theta\!\left(\frac{D}{n}\right)}$
	$n\\|S\\|_{F}^{2}\ll\lambda^{2}\ll\sqrt{nD}\\|S\\|_{F}^{2}\wedge n\\|S\\|_{1}^{2}$	$\displaystyle e^{-\Theta\!\left(\frac{Dn\\|S\\|_{F}^{4}}{\lambda^{4}}\right)}$	$\gg$	$\displaystyle e^{-\Theta\!\left(\frac{D}{n}\right)}$
	$n\\|S\\|_{1}^{2}\ll\lambda^{2}\ll\sqrt{nD}\\|S\\|_{F}^{2}$	$\displaystyle e^{-\Theta\!\left(\frac{Dn\\|S\\|_{F}^{4}}{\lambda^{4}}\right)}$	$\gg$	$\displaystyle e^{-\Theta\!\left(\frac{D\\|S\\|_{1}^{2}}{\lambda^{2}}\right)}$
	$\sqrt{nD}\\|S\\|_{F}^{2}\ll\lambda^{2}\ll D\\|S\\|_{1}^{2}$	$\frac{1}{2}$	$\gg$	$\displaystyle e^{-\Theta\!\left(\frac{D}{n}\wedge\frac{D\\|S\\|_{1}^{2}}{\lambda^{2}}\right)}$
	$\lambda^{2}\gg D\\|S\\|_{1}^{2}$	$\frac{1}{2}$		$\frac{1}{2}$
DSM 1	$\displaystyle\lambda^{2}\ll n\\|S\\|_{F}^{2}\wedge\frac{D^{2}\\|S\\|_{1}^{2}}{n^{2}}$	$\displaystyle e^{-\Theta(D)}$	$\ll$	$\displaystyle e^{-\Theta(n)}$

Appendix

Table 2: Comparison of the late-stage generalization of GD and SpecGD.

Gradient Descent

Gradient descent iteratively updates model parameters to reduce a loss using its slope, with variants for speed, scale, and constraints.

See all 118 papers

Exact information accounting for SGD methods
Sep 30, 2026Akshay BalsubramaniNeural Network Generalization Stochastic Optimization Convergence
Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minima
Jul 9, 2026Lachlan Ewen MacDonald, René VidalGradient Descent Flat Minima
Innovation in Data Engineering and Science (IDEAS) · University of Pennsylvania Pennsylvania, PA 19104
Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamics
Aug 5, 2026Han BaoLogistic Regression Implicit Bias
The Institute of Statistical Mathematics · Tohoku University · RIKEN AIP

Sep 30, 2026J/K move · Enter open · S save

Exact information accounting for SGD methods

Akshay Balsubramani

Neural Network Generalization Stochastic Optimization Convergence Adaptive Gradient Methods Stochastic Gradient Descent

Open paper AskPDF arXiv

As an alternative to the standard geometric analyses, we give an exact, information-theoretic analysis of stochastic gradient descent (SGD) and its variants. We show that a preconditioned SGD step is the posterior-mean update of a Gaussian Bayes model, and that its one-step regret splits into an intrinsic-time cost and a change in comparator information. The split extends to an identity for the objective itself. Convex convergence, strict-saddle-point escape, the link between flatness and generalization, the standard learning-rate schedules, adaptive optimizers, and the noisy, momentum, heavy-tailed, and gradient-free variants of SGD each correspond to a term or a special case of this identity. We measure its terms on synthetic and real training runs. On real networks it attributes the slack of classical convergence bounds to the terms their derivations drop and separates optimizers that reach the same training loss. That separation follows the number and consistency of their steps. Its relation to which of them generalizes better differs between networks. For gradient-free SGD the identity determines how a curvature preconditioner should enter the update. The sharpness-based generalization certificate it yields, with a data-independent isotropic prior, is vacuous at network scale unless the curvature spectrum is nearly flat across all parameters.

Abstract

Gradient Descent

Explore similar work

Exact information accounting for SGD methods

Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minima

Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamics