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 RSpecGD⋆≪RGD⋆ , while blue indicates RGD⋆≪RSpecGD⋆ . Here n,D,r,λ 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=105 , ρ=0.45 , λ=125 , σ1=1 , T=3D and ηk=0.005(1+k)−0.1 .
Parameter regime
GD (late)
SpecGD (late)
SpecGD (one step)
CSM
n≪λ2≪r∧nD
e−Θ(Dn/λ4)
e−Θ(D/n)
e−Ω(cD)
n∨r≪λ2≪rn∧nD
e−Θ(Dn/λ4)
e−Θ(D/n)
e−Ω(rD/λ2)
r∨nD≪λ2≪rn
21
e−Θ(D/n)
e−Ω(rD/λ2)
DSM †
n≪λ2≪D
e−Θ(Dn/λ2)
e−Θ(n)
e−Ω(rD/λ)
D≪λ2≪Dn
e−Θ(D2n/λ4)
e−Θ(n)
e−Ω(rD/λ)
Dn≪λ2
21
e−Θ(n)
e−Ω(rD/λ)
Table 1: Representataive test risks of GD and SpecGD. We set ∥S∥F=1 and ∥S∥1=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 λ for GD and SpecGD. Parameters: n=100 , r=1 , D=105 , ρ=0.45 , ∣∣S∣∣F=∣∣S∣∣1=1 , T=104 , η=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 τ:=∑ℓ=0Tηℓ for GD and SpecGD. Parameters: n=100 , r=1 , D=d−r=105 , ρ=0.45 , λ=125 , η=10−2 , and T=104
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: ρ=0.45 , λ=125 , and η=10−2 . We compare all configurations at fixed normalized optimization time nτ/D=1.5 . Results are averaged over 10 independent runs.
Parameter regime
R(WGD⋆)
R(W⋆)
CSM
λ2≪n∥S∥F2
e−Θ(nD)
e−Θ(nD)
n∥S∥F2≪λ2≪nD∥S∥F2∧n∥S∥12
e−Θ(λ4Dn∥S∥F4)
≫
e−Θ(nD)
n∥S∥12≪λ2≪nD∥S∥F2
e−Θ(λ4Dn∥S∥F4)
≫
e−Θ(λ2D∥S∥12)
nD∥S∥F2≪λ2≪D∥S∥12
21
≫
e−Θ(nD∧λ2D∥S∥12)
λ2≫D∥S∥12
21
21
DSM 1
λ2≪n∥S∥F2∧n2D2∥S∥12
e−Θ(D)
≪
e−Θ(n)
Appendix
Table 2: Comparison of the late-stage generalization of GD and SpecGD.
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.
An important quantity in the theory of gradient descent (GD) is the sharpness, defined as the largest eigenvalue of the objective Hessian. Classical analyses typically require the step size to be uniformly smaller than twice the reciprocal of the sharpness, but this condition is frequently violated in the training of deep neural networks. Recent work bridges this gap in the setting of overparametrised least-squares with a single scalar output, providing a normal form for large-step GD in a neighbourhood of an isolated flat minimum and establishing three corresponding convergence results. In this paper, we extend this theory in two directions: (1) to overparametrised least-squares with vector-valued outputs (including regression with arbitrarily many observations), and (2) to a neighbourhood of a manifold of flat minima (which we show is essential for applications such as matrix factorisation). We generalise both the normal form and all three convergence theorems of \cite{macdonaldeos} to this broader setting, overcoming several technical challenges, including the solution of a singular partial differential equation via a novel method that may be of independent interest. We further show that our framework applies to deep matrix factorisation under mild assumptions, yielding several new structural results. In particular, we prove that the set of flat minima forms a fibre bundle over a product of spheres, and that the sharpness is Morse-Bott along this manifold.
Lachlan Ewen MacDonald, René Vidal
Innovation in Data Engineering and Science (IDEAS) · University of Pennsylvania Pennsylvania, PA 19104
Gradient descent has been of particular interest in modern machine learning beyond sole focus on optimization. Implicit bias emerging from optimization, though not being encoded by the learning objective, often prevents from overfitting to spurious patterns. A typical instance is the max-margin implicit bias of a linear classifier, widely established for exponentially tailed loss functions. Even after having a given dataset separated, the parameter vector continues to evolve towards the max-margin direction asymptotically along the gradient descent dynamics. This phenomenon corroborates a frequent empirical observation of "train longer, generalize better." However, the max-margin convergence is an asymptotic phenomenon, and what is worse, this asymptotic convergence rate is significantly slower than pure convex optimization. Even so, the parameter vector along gradient descent dynamics commonly correlates with the max-margin direction positively (though not exactly) within considerably fewer iterations than the asymptotic rate. By shedding another light on this classical problem, this work aims to understand the mechanism of this early-stage alignment phenomenon. Our theoretical results demonstrate that the parameter vector weakly aligns with the max-margin direction within O(exp(exp(−δ))) iterations, where δ>0 is the permissible alignment error, which is shown to be tight. By tracking the radial and tangential flows, our proof operates on the alignment dynamics directly with dataset geometry and gets rid of the asymptotic expansion, which is a key insight to establishing faster weak alignment.
Han Bao
The Institute of Statistical Mathematics · Tohoku University · RIKEN AIP