Research map / Optimization / Implicit bias and generalization
SGD vs GD: Rank Deficiency in Linear Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows analytically that gradient flow preserves the determinant of the parameter Gram matrix of a two-layer linear network while label-noise SGD drives it to zero, and derives an SDE for eigenvalues revealing a repulsive force that induces rank deficiency.
Problem
Understanding how stochasticity (label-noise SGD) in gradient methods yields simpler, low-rank solutions compared with deterministic gradient flow in linear networks, and how initialization dependence is removed.
Approach
Tracks the determinant of Θ⊤Θ (a block parameter matrix) as a conserved quantity under gradient flow and as a decaying quantity under stochastic gradient flow, then derives an SDE for the eigenvalues of W1ᵀW1 showing repulsive interactions balanced against geometric Brownian motion pulling singular values to zero.
Key results
- Under gradient flow the determinant of Θ⊤Θ stays constant (Theorem 4.1), whereas under label-noise SGF it decays as det(Θ0⊤Θ0)exp(-2ηδ tr(X⊤X) t) (Theorem 4.2).
- In experiments with width l=10 and label noise δ=2, the smallest singular values of W1 are driven toward zero while the top-k singular values remain at scale under gradient flow.
- For the two-vector large-noise limit, s0^{-α} is a super-martingale and s1^{-α} a sub-martingale with α=(p-3)/2 (Theorem 5.2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add label noise (δ = 2) instead of using gradient flow without label noise | two-layer linear network · synthetic Gaussian regression | determinant of Θ⊤Θ | Helped |
| add label noise instead of using gradient flow | two-layer linear network · synthetic Gaussian regression | smallest singular values of W1 | Helped |
| increase SGD step size from η = 0.005 to η = 0.1 | linear network · synthetic regression with MSE loss | singular values of W1 | Helped |
| use SGD with η = 0.005 rather than a larger step size | linear network · synthetic regression with MSE loss | singular values of W1 | No clear effect |
| use SGD with larger step size η = 0.5 | linear network · synthetic classification with logistic loss | smallest singular value of W1 | Helped |
| use SGD with larger step size η = 0.5 | linear network · synthetic classification with logistic loss | remaining singular values of W1 | No clear effect |
| use a 2-layer ReLU network instead of a linear network | SGD-trained network · synthetic regression with MSE loss | decrease of the last singular value of W1 | Hurt |
| increase SGD step size from η = 0.0001 to η = 0.001 | 2-layer ReLU network · synthetic regression with MSE loss | separation of largest and smallest singular values of W1 | Helped |
Surprising findings
- The determinant evolves deterministically under SGF even though the parameter trajectory is random.
- Larger step sizes in discrete SGD can shrink the determinant and simplify parameters even when the training loss does not converge (catapult/edge-of-stability regimes).
Limitations
- Full characterization of the eigenvalue SDE solution is left open; collision-avoidance is not established.
- Theoretical determinant results give limited insight when the determinant is already zero at initialization (width l < p+k).
- Eigenvalue analysis for general cases restricted to k=1 and isotropic data, with the two-vector result only in the large-noise limit.
Experimental setup
Datasets: synthetic Gaussian regression data (n=1000, p=5, k=2) synthetic two-cluster classification data (n=1000, p=5)
Metrics: determinant of Theta^T Theta over iterations top-5 singular values of W1
Baselines: gradient flow gradient descent
Builds on: Label noise SGD (Blanc et al., 2020) Bru (1989) matrix-valued stochastic process eigenvalues Pillaud-Vivien et al. (2022) diagonal networks Pesme et al. (2021) Varre et al. (2024)
Closest papers by meaning
- Implicit bias of SGD in $L_2$-regularized linear DNNs: One-way jumps from high to low rank (ICLR 2024 · similarity 0.90)
- High-dimensional Limit of SGD for Diagonal Linear Networks (NeurIPS 2026 · similarity 0.89)
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.87)
- A Precise Characterization of SGD Stability Using Loss Surface Geometry (ICLR 2024 · similarity 0.87)
- Does SGD really happen in tiny subspaces? (ICLR 2025 · similarity 0.87)
- Emergence and scaling laws in SGD learning of shallow neural networks (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.