acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
learning theory
Keywords:
Implicit bias, directional convergence, benign overfitting, spectral gradient descent

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_CJMyOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the implicit bias and generalization of spectral gradient descent, an idealized counterpart of Muon, in overparameterized matrix linear classification with corrupted labels. The data model combines a shared low-rank signal with sample-specific rank-one features used for memorization. The authors show that changing the geometry of these features from collapsed to dispersed can reverse the relative generalization performance of GD and SpecGD in certain parameter regimes. They further establish that weak correlations among random dispersed features preserve a small but statistically relevant signal component, whereas exact orthogonality eliminates the signal from the limiting direction. To characterize the direction selected by SpecGD despite non-uniqueness of spectral max-margin solutions, the paper analyzes the dynamics of normalized loss weights through the max-margin dual. Finally, it identifies conditions under which one SpecGD step interpolates the corrupted training labels and generalizes better than the late-stage solution.

Critical strengths
  1. The paper identifies shortcut geometry as a concrete factor that can reverse the relative generalization of GD and SpecGD. This might be valuable to the community.

  2. The analysis shows that weak random correlations among dispersed shortcuts preserve a small but statistically meaningful signal component, whereas exact orthogonality eliminates the signal from the limiting direction. This is nontrivial and may inspire future optimizer design.

  3. Going beyond the spectral margin maximization, the paper characterizes the direction selected by SpecGD despite the non-uniqueness of the primal max-margin problem. The analysis combines normalized loss-weight dynamics, conditional dual convergence, and a model-specific direction-selection identity to determine the signal component needed for the generalization results.

Critical weaknesses
  1. The data model assumes rank-one sample-specific shortcuts whose row and column spaces are orthogonal to those of the signal. While this structure enables the signal–memorization decomposition central to the analysis, it remains unclear which conclusions survive when these subspaces overlap or shortcuts have higher rank.

  2. The analysis identifies shortcut geometry as a determinant of generalization, but does not provide an observable diagnostic connecting this geometry to practical training problems. Beyond motivating early stopping, it remains unclear how the results could guide optimizer selection or training decisions.

  3. While the paper characterizes the first iterate and limiting direction, it does not establish when test risk deteriorates. Finite-time risk bounds would clarify how long favorable early-stage behavior persists and strengthen the early-stopping implications.

Questions for authors
  1. Given the contrast between the good generalization of the first iterate and the potentially catastrophic overfitting of the limiting direction, is it feasible within the current dual-dynamical framework to estimate a deterioration timescale?

  2. While I appreciate the theoretical focus of the paper, I would be interested in the authors’ perspective on whether these findings suggest any practical diagnostics or training adjustments for Muon users beyond early stopping. I view this as an exploratory question rather than a requirement for the present work.

2 comments

We thank the reviewer for their constructive feedback. We address their comments and questions below.

1. Concern: Does the phenomenon survive overlapping subspaces and higher-rank shortcuts?

Response. Please see the general answer. We have added experiments with overlapping signal–shortcut subspaces (Section I.1). showing that our results persist with overlapping subspaces.

In addition, our experiment below suggests that the same phenomenon persists with shortcuts of relatively small rank RR but with a different magnitude. Under CSM the performance of SpecGD degrades when RR increases, but under DSM it improves. The performances of GD degrade in both cases when RR increases. See Table 1 for the numerical results and below for the formal definition of the extended model:

Rank RRCSM: GDCSM: SpecGDDSM: GDDSM: SpecGD
144.813.70.031.7
448.614.016.718.2
747.821.728.24.9
1550.031.336.77.3

Table 1. Clean test error (%) of GD and SpecGD under collapsed (CSM) and dispersed (DSM) shortcuts with varying shortcut rank RR. Parameter: n=100n=100, D=104D=10^4, ρ=0.45\rho=0.45, λ=50\lambda=50, r=1r=1, σ1=1\sigma_1=1, T=800T=800, and η=10−2\eta=10^{-2}.

Setting: We extend the shortcut model by considering rank-RR perturbations

\qquad U_i^\top U_i=V_i^\top V_i=I_R,$$ where $U_i,V_i\in\mathbb R^{d\times R}$ are sampled independently and uniformly from the Stiefel manifold in the subspace orthogonal to the signal. In the collapsed model (CSM), we impose $V_i=V_0$ for all $i$, whereas in the dispersed model (DSM), the $V_i$ are sampled independently. We conjecture that the improved performance of SpecGD with large $R$ is due to the small correlations amplification. **2. Question: Can the onset of test-error deterioration be estimated?** **Response.** Figure 2 shows that deterioration can occur relatively quickly: under DSM, SpecGD interpolates after the first iteration, but its test error increases substantially within the first few hundred iterations. Our new MNIST experiments (Appendix I.2) also exhibit deterioration following interpolation. While our dual-dynamical framework provides a convergence rate toward the limiting classifier (Remark 2), it does not directly characterize the onset of deterioration. Establishing such a timescale would require additional finite-time analysis of the signal and shortcut components, which we leave for future work. **3. Question: What diagnostics or Muon training adjustments follow beyond early stopping?** **Response.** **One practical implication is that the choice of Newton–Schulz approximation may affect generalization, and closer approximation to the exact polar factor is not necessarily better.** Our additional experiments show that, while accurate polar approximations reproduce SpecGD's behavior, the popular quintic Newton–Schulz iteration avoids the deterioration observed under DSM, with only moderate degradation under CSM. This suggests that the approximation scheme itself may be a useful tuning choice for Muon. Regarding diagnostics, our results identify the organization of sample-specific features across singular directions as a potentially relevant property, although translating this insight into a practical diagnostic remains open.

Thank you for the clarifications and additional experiments. I maintain my weak-accept recommendation.

Reviewer_gLPjOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper compares spectral gradient descent (SpecGD, an idealized form of Muon) with GD for a matrix-valued linear classifier trained with exponential loss on labels with random flips. The shortcuts are arranged in one of three ways: 1. collapsed (CSM): all shortcuts share one right singular direction; 2. dispersed (DSM): shortcuts occupy independent random directions; 3. orthogonal benchmark (DOB): shortcuts are exactly orthogonal. The paper proposes a few convergence results of late-stage SpecGD, SpecGD and GD, as well as one-step, which seems to close a formally defined gap in [1].

[1] Fan, Chen, Mark Schmidt, and Christos Thrampoulidis. "Implicit bias of spectral descent and muon on multiclass separable data." Advances in Neural Information Processing Systems 38 (2026): 39622-39669.

Critical strengths
  1. A well-defined gap is closed. [1] show that SpecGD maximizes the spectral margin but cannot say which of the many max-margin solutions it selects. This paper identifies the selected direction and its signal coefficient with a neat Prop. B.2.

  2. The results are explicit and appear correct. I used Claude Opus 5.5 to help me proofread the Appendix proofs section-by-section and found no critical errors.

  3. Both late-stage and one-step behavior are covered. This gives a concrete case where SpecGD’s implicit bias generalizes worse than early stopping.

[1] Fan, Chen, Mark Schmidt, and Christos Thrampoulidis. "Implicit bias of spectral descent and muon on multiclass separable data." Advances in Neural Information Processing Systems 38 (2026): 39622-39669.

Critical weaknesses
  1. The model is highly stylized, which limits significance: a. Shortcuts are confined to the orthogonal complement of S’s singular subspaces. As a result, the polar factor splits additively into P_S plus the polar factor of the shortcut aggregate. b. Under this assumption, the geometry-dependent reversal follows largely from the definition of the polar factor: a collapsed aggregate receives one unit singular value, while a dispersed one receives n.

  2. Robustness is never examined. It is unclear whether any conclusion survives overlap between the signal and shortcut subspaces, multiclass or nonlinear models, momentum, or the Newton-Schulz approximations used in Muon. Experiments use only the synthetic model too.

  3. Despite correct proofs, the theorems are vacuous at the scales the paper reports. Theorem 1 needs n in the millions, is that practical? Fig. 2 setting (n = 100, ρ = 0.45) satisfies none of the conditions. The DSM risk has an exponent, which is like 6e-4 at ρ=0.45\rho=0.45. late-stage SpecGD therefore sits near 40% error, which can be fine but does not look promising. Figures 3–4 use a constant step size, which is outside Assumption A1.

  4. The technique is only moderately novel. It is known that normalized exponential-loss weights follow multiplicative-weights or mirror-descent dynamics on the margin dual. Theorem B.1 is a standard mirror-descent convergence argument. Prior work showing that the choice of optimizer changes generalization in signal-plus-noise models (e.g., [1]) should be discussed.

  5. The appendix is out of proportion to the insight, and I have to point out that it is too long for human reviewer to verify without AI. About 38 of the 67 appendix pages make Theorem 1 rigorous, yet its leading constant follows from a calculation of about one page, not mentioning re-derivation of standard, cite-able materials (but this helps AI proofread though). This also contains overstatements and presentation: Table 1 and Appendix J state two-sided Θ(⋅)\Theta(\cdot) rates for GD, but Appendix E proves only the upper bounds; Section 4 implies that local relative growth is needed for the dual iterates to converge---uniqueness of the minimizer already suffices; local growth is needed only for the rate; Symbols are heavily overloaded, there are also typos, and Remark 3 contradicts the hypothesis of its own lemma.

[1] Vasudeva, Bhavya, et al. "The rich and the simple: On the implicit bias of adam and sgd." Advances in neural information processing systems 38 (2026): 161725-161761.

Questions for authors

Please refer to the weaknesses. Additionally: 1. Do the conclusions, and the reversal in particular, survive when shortcuts partially overlap the signal’s singular subspaces? 2. How many iterations does SpecGD need to approach W⋆_DSM? Does the reversal appear with constant step sizes, momentum, or Newton–Schulz polar approximations? 3. Do any conclusions carry over to neural networks trained with Muon on data with structured spurious features?

4 comments
AuthorsOpenReview ↗

Response to Reviewer gLPj (Part 1 of 2)

We thank the reviewer for their constructive feedback. We address their comments and questions below. We have divided it into two posts

1. Concern: Are the conclusions robust beyond orthogonal shortcuts and idealized SpecGD?

Response. Please see the general answer. Our new experiments directly address these robustness concerns. Appendix I.1 (Figures 7–9) shows that the geometry-dependent reversal persists under small signal–shortcut overlap. These experiments also demonstrate that Muon can reproduce SpecGD's behavior with sufficiently accurate Newton–Schulz orthogonalization, even with momentum, while the popular quintic approximation can change the generalization behavior qualitatively, and large momentum can substantially delay deterioration.

The reversal also persists with constant stepsizes (Figure 4) and in two-layer ReLU and tanh networks (Appendix I.3, Table 2). Additional MNIST experiments (Appendix I.2) demonstrate the distinction between early- and late-stage generalization on real data.

Exact orthogonality allows us to identify the theoretical mechanism precisely, but the new experiments show that the observed phenomena are not artifacts of this assumption. Theoretical extensions to overlapping subspaces, multiclass classification, and nonlinear models remain interesting directions for future work.

2. Concern: Does the reversal follow simply from the polar factor and shortcut rank?

Response. We would like to emphasize that shortcut rank alone does not determine the generalization behavior of SpecGD. DSM and the deterministic orthogonal benchmark (DOB) both have shortcut rank nn, yet their limiting SpecGD classifiers behave qualitatively differently. Under DSM, small random correlations generate a positive signal component, resulting in benign overfitting. Under DOB, exact orthogonality eliminates this component, and the limiting test error equals 1/21/2.

Thus, the number of unit singular values in the polar factor does not determine generalization. Identifying the second-order effect of shortcut correlations, and proving that it determines the selected classifier, constitutes a central technical contribution of our work.

3. Concern: Are Theorem 1’s assumptions vacuous at realistic sample sizes? Late-stage SpecGD in Fig 2 sits near 40% error does not look promising.

Response. We have substantially improved the sufficient conditions of Theorem 1 from L5≲nL^5\lesssim n, D≳nL4D\gtrsim nL^4 to L3≲nL^3\lesssim n, D≳nL2D\gtrsim nL^2, where L=log⁡(n/δ)L=\log(n/\delta). More fundamentally, requiring large sample sizes does not make an asymptotic benign-overfitting result vacuous. Our main results characterize when interpolating corrupted labels leads to benign or harmful overfitting, and how shortcut geometry determines the generalization behavior as nn grows.

To illustrate benign overfitting directly, we have added Figure 3, showing decreasing limiting test error as nn increases from 100100 to 10001000, with ρ=0.30\rho=0.30.

The relatively high test error at ρ=0.45\rho=0.45 is consistent with our results. Figure 2 deliberately uses this high corruption rate to highlight the geometry-dependent reversal and the deterioration of SpecGD under DSM after interpolation, rather than to demonstrate benign overfitting.

4. Concern: Constant-step experiments lie outside Assumption A1

Response. The constant-stepsize experiments investigate finite-time behavior; we do not use them to establish asymptotic directional convergence under Assumption A1.

5. Concern: Is the dual-dynamical contribution sufficiently novel, given that normalized exponential-loss weights are known to follow multiplicative-weights and Theorem B.1 appears to use a standard mirror-descent convergence argument?

Response. We agree that multiplicative-weights and mirror-descent techniques are well established. Our key technical observation is that the normalized exponential-loss weights evolve exactly as exponentiated-gradient iterates on the spectral max-margin dual objective of SpecGD. This connection is specific to the polar update and does not follow merely from the multiplicative-weights form of the loss weights.

We have already cited Ji and Telgarsky for a related connection in GD. Importantly, directional convergence of GD had previously been established by Soudry et al. without this technique. For SpecGD, however, existing spectral max-margin results do not establish directional convergence, as the primal solution may be nonunique. Our dual-dynamical connection enables us to establish directional convergence and, combined with the second-order analysis of shortcut correlations, identify the selected classifier and its generalization.

AuthorsOpenReview ↗

Response to Reviewer gLPj (Part 2 of 2)

6. Concern: Missing related work on optimizer-dependent generalization

Response. We thank the reviewer for the suggestion. We have added the reference to Section 1.2, alongside our discussion of optimizer-dependent implicit bias.

7. Concern: The lengthy proof of Theorem 1 disproportionate to its insight, given that the leading constant can be derived briefly

Response. The leading constant can indeed be anticipated from a second-order expansion. However, making this calculation rigorous requires uniform concentration of the random fluctuations, control of higher-order remainders, and proof of uniqueness and interiority of the dual optimizer. These are essential for establishing directional convergence and generalization under DSM, rather than merely obtaining a formal approximation. We provide the detailed arguments to make these nontrivial steps verifiable.

8. Concern: Unsupported two-sided GD rates and other technical inconsistencies

Response. We appreciate these specific technical comments. We have substantially strengthened the GD risk bounds in Appendix E, establishing matching exponential upper and lower bounds throughout the benign-overfitting regimes of CSM and in an additional regime of DSM. Table 1 and Appendix J now distinguish these matching rates from regimes where only upper bounds are established. All our original GD–SpecGD generalization comparisons remain valid.

We have also clarified the role of local relative growth and corrected the typographical errors. In particular, the inconsistency in Remark 3 was caused by a typo. We have corrected the inconsistency and moved this remark to the main text to make our intention clearer.

9. Question: How many iterations are needed to approach the SpecGD limit?

Response. Remark 2, equation (3.3), provides a quantitative Frobenius-norm convergence rate for normalized SpecGD iterates. For example, with ηk=(k+1)−1/2\eta_k=(k+1)^{-1/2}, the rate is O(k−1/4)O(k^{-1/4}). Thus, achieving approximation error at most ε\varepsilon requires O(ε−4)O(\varepsilon^{-4}) iterations, up to problem-dependent constants. The precise iteration count depends on the stepsize schedule and these constants.

Thank you for the detailed response. Several of the changes address most of my concerns: the new GD lower bounds, the weaker conditions in Theorem 1, the experiments with overlap, accurate Newton–Schulz and two-layer networks, and the fixes to Remark 3 and to the role of local growth. I also agree that I undersold the near-orthogonality result: the second-order effect that separates the DSM from the DOB is a genuine and non-obvious contribution. With the new conditions, my "n in the millions" estimate no longer applies.

A few points remain, and I would like to see them reflected in the paper. First, the reversal itself does not depend on that effect. Under the DOB, SpecGD is at chance and GD still wins (Proposition 1, Figure 2), so the ordering is set by whether the shortcuts span one direction or n. Second, the exponentiated-gradient identity is not specific to the polar update: it holds for any normalized steepest descent, as your Discussion suggests for SignGD. Third, by the rate in Remark 2 with η_k = (k+1)^{-1/2}, resolving the signal requires the Frobenius error to fall below the signal coefficient. That coefficient is about 3×10⁻³ at the Figure 2 setting, so this takes on the order of 10¹⁰ iterations, up to constants. Together with your finding that quintic Newton–Schulz and large momentum change the behavior, this suggests the late-stage limit may not describe Muon as used in practice. A sentence on this in the limitations would help. Overall, I have raised my score.

We sincerely thank the reviewer for the thoughtful follow-up and for reconsidering our work. We appreciate these additional observations and would be happy to clarify the corresponding points in the manuscript.

We agree that the GD–SpecGD reversal can already be demonstrated by comparing CSM and DOB. However, the second-order effect reveals a stronger phenomenon: as summarized in Figure 1, in certain regimes, the limiting SpecGD risks satisfy RDSM⋆≪RCSM⋆≪RDOB⋆=1/2\mathcal R_{DSM}^\star \ll \mathcal R_{CSM}^\star \ll \mathcal R_{DOB}^\star = 1/2, even though DSM and DOB have the same shortcut rank.

We also appreciate the reviewer's observation that the dual-dynamical connection extends to other "normalized" steepest-descent methods, and would be happy to clarify it in the manuscript. We are not aware of prior work explicitly establishing this, and would be grateful if the reviewer could suggest a reference.

Finally, we will clarify the limitations of extrapolating our results to practical Muon. We note that Remark 2 provides an upper bound on the approximation error, not a lower bound on the number of iterations required to observe the limiting behavior.

We thank the reviewer again for their constructive suggestions.

Reviewer_Gy2KOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper examines how SpecGD’s equalization of gradient singular values interacts with memorization shortcuts in matrix classification with corrupted labels. It shows that shortcut geometry can reverse the generalization ordering of SpecGD and GD, and that continued training can worsen SpecGD’s generalization even after it fits all training labels. The authors explain these effects through an analysis of SpecGD’s limiting direction, supported by theoretical guarantees and synthetic experiments.

Critical strengths
  1. A clear demonstration that shortcut geometry can reverse optimizer generalization. By changing the organization of memorization features while keeping their strength fixed, the paper isolates a consequential interaction between data geometry and spectral updates. This provides a concrete theoretical explanation for why SpecGD need not generalize better than GD.

  2. A characterization of the solution actually selected by SpecGD. The dual-dynamical analysis goes beyond a potentially nonunique spectral max-margin characterization to identify the limiting direction and its generalization properties. This strengthens the paper’s conclusions by connecting optimization dynamics to statistical performance, including deterioration after training-label interpolation.

Critical weaknesses
  1. The scope of the conclusions is limited by the structured data model. The analysis assumes a linear matrix classifier with rank-one shortcuts occupying subspaces orthogonal to the signal. These assumptions enable precise results, but it remains unclear whether the generalization reversal persists when signal and shortcut components overlap or have more realistic structure. This limits the conclusions’ relevance beyond the constructed setting.

  2. The empirical validation does not establish relevance to practical Muon training. The experiments largely illustrate the theoretical model, without testing whether the same mechanism appears in nonlinear networks or practical Muon variants. Such evidence would substantially strengthen the case that shortcut geometry explains meaningful optimizer behavior beyond this idealized setting.

Questions for authors
  1. How essential is exact orthogonality between the signal and shortcut subspaces to the generalization reversal? Do you have theoretical or empirical evidence that the reversal persists under small violations of this assumption?

  2. Do you have evidence beyond the synthetic model that the identified mechanism persists with practical Muon variants or nonlinear predictors? Such evidence would materially strengthen my assessment of the results’ broader relevance; I am asking about existing evidence rather than requesting a new line of work.

2 comments

We thank the reviewer for their constructive feedback. We address their comments and questions below.

1. Concern: How essential is exact orthogonality between the signal and shortcut subspaces to the generalization reversal?

Response. Please see the general answer. We have added experiments with overlapping signal–shortcut subspaces (Appendix I.1), which show that the geometry-dependent reversal persists under small violations of exact orthogonality.

2. Concern: Relevance to practical Muon and nonlinear neural networks

Response. Please see the general answer. We have substantially expanded our experiments. Appendix I.1 investigates Newton–Schulz approximations and momentum, demonstrating when Muon-type updates recover SpecGD's behavior and when they differ. Appendix I.3 shows that the geometry-dependent reversal persists in two-layer ReLU and tanh networks. We additionally include MNIST experiments in Appendix I.2 examining early- and late-stage generalization.

I thank the authors for their response and additional experiments, which substantially address my concerns about the restrictive assumptions and broader relevance of the results. I maintain my score of 3.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Answer

We thank the reviewers for their constructive feedback and their generally positive assessment of the novelty and soundness of our theoretical results. Before addressing the individual comments, we would like to discuss two recurring concerns regarding the simplicity of our statistical model and the broader significance of our findings beyond this theoretical setting.

  • Our theory identifies a key data structure governing generalization. We show that GD and SpecGD can select interpolating classifiers with drastically different generalization properties: changing only the singular organization of non-predictive features can reverse which optimizer generalizes better, even when the predictive signal, shortcut strength, and label corruption are fixed. Our results thus identify shortcut singular geometry as a decisive factor in determining when spectral normalization improves or harms generalization.

  • Our simplified setting isolates the mechanisms governing generalization. Both the structured shortcut model and the idealized SpecGD algorithm serve important methodological purposes. The former allows us to isolate the effect of shortcut geometry while keeping other statistical properties fixed; the latter isolates the effect of spectral normalization without additional complications from momentum or approximate orthogonalization. These simplifications enable us to identify precisely how data geometry and optimizer geometry interact to determine generalization, which would be much harder to disentangle in a more general setting.

  • Additional experiments demonstrate the broader relevance of our findings. We show that practical Muon can reproduce SpecGD's behavior with sufficiently accurate Newton–Schulz orthogonalization, even with momentum, whereas the popular quintic approximation can lead to qualitatively different generalization behavior (Section I.1). Experiments on MNIST show that SpecGD can generalize better at interpolation before deteriorating under continued training (Section I.2). Finally, the geometry-dependent reversal persists in two-layer ReLU and tanh networks with random initialization (Section I.3).

  • A counterintuitive phenomenon requiring nontrivial analysis. Our analysis of DSM reveals a subtle phenomenon: despite having the same number of shortcut singular directions as the exactly orthogonal benchmark, even vanishing correlations between shortcuts can generate a statistically relevant signal component that disappears under exact orthogonality. Thus, despite its simplicity, our model uncovers a second-order mechanism that the exactly orthogonal approximation cannot anticipate.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.