Research map / Optimization / Implicit bias and generalization

Implicit bias of SGD in $L_2$-regularized linear DNNs: One-way jumps from high to low rank

ICLR 2024 · Optimization › Implicit bias and generalization · approach: Explicit and implicit regularization interplay · 1 citations (OpenAlex)

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 that SGD with L2 regularization in deep linear networks performs one-way jumps from higher-rank to lower-rank minima on matrix completion, via absorbing sets B_r, and verifies this with small experiments.

Problem

In deep linear networks with L2 regularization, the loss has multiple local minima of different ranks; GD can get stuck at rank-overestimating minima in matrix completion, so the question is which minimum SGD converges to.

Approach

Defines nested absorbing regions B_1 ⊂ ... ⊂ B_R of approximately rank-r parameters; proves SGD can never leave B_r once inside but has non-zero probability of entering it from anywhere, so SGD performs one-way jumps from high to low rank, without relying on SDE/Langevin approximations.

Key results

• SGD with annealed large-then-small learning rate and ridge jumps from rank-2 to rank-1 minimum around step 2000 on a 2x2 MC problem (L=3, w=100).
• Depth L=4 networks all jump within 5000 steps while all five L=3 networks fail to jump under the same schedule (epsilon=0.1).
• Theoretical jump probability lower bound is (r/min{d_in,d_out})^T, with T of order tilde-Omega(1/(lambda eta)), and explicit bounds require extremely small learning rates.

Measured effects reported in the paper

Surprising findings

• Theoretical bounds suggest extremely small learning rates, yet empirically larger depth makes jumps more likely, which the authors note as a contradiction with their bounds.
• Stationary distributions of Langevin-type SDE approximations are misleading, since any stationary distribution has support in the rank-1 region, and jumps occur before the limiting distribution is reached.

Limitations

• Second part of the theorem relies on sampling with replacement; with epoch-wise shuffling, jumps would need to happen within an epoch.
• Average time to observe a jump can be impractically large without large learning rates, which makes the dynamics noisy.
• Theoretical learning-rate and ridge bounds are very loose and do not reflect the observed depth dependence.

Experimental setup

Datasets: synthetic 2x2 matrix completion problem

Benchmarks: synthetic 2x2 matrix completion

Metrics: test loss singular value ratio rank of learned matrix

Baselines: gradient descent Langevin dynamics approximation of SGD

Builds on: Schatten norm representation cost of deep linear networks balancedness of critical points Langevin approximation of SGD

Closest papers by meaning

• Implicit Bias of (Stochastic) Gradient Descent for Rank-1 Linear Neural Network (NeurIPS 2023 · similarity 0.91)
• SGD vs GD: Rank Deficiency in Linear Networks (NeurIPS 2024 · similarity 0.90)
• On the Global Convergence of Training Deep Linear ResNets (ICLR 2020 · similarity 0.89)
• (S)GD over Diagonal Linear Networks: Implicit bias, Large Stepsizes and Edge of Stability (NeurIPS 2023 · similarity 0.89)
• Implicit Bias of Gradient Descent for Non-Homogeneous Deep Networks (ICML 2025 · similarity 0.88)
• Block Coordinate Descent for Neural Networks Provably Finds Global Minima (NeurIPS 2025 · similarity 0.88)