Research map / Optimization / Implicit bias and generalization

Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least Squares

NeurIPS 2025 · Optimization › Implicit bias and generalization · approach: Edge-of-stability dynamics · 0 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.

Gives convergence rates for large-step-size gradient descent (edge of stability) on codimension-1 overparametrised least squares by decomposing GD into Riemannian gradient descent on sharpness along the solution manifold plus a period-doubling bifurcating orthogonal component, yielding subcritical, critical, and supercritical regime results.

Problem

Gradient descent at the edge of stability in overparametrised least squares is non-monotonic and poorly understood theoretically; no convergence rates existed for settings where monotone decrease may never occur.

Approach

Overparametrisation makes the global minimiser set a Riemannian manifold; GD splits into a parallel component performing Riemannian gradient descent on sharpness and an orthogonal component that is a period-doubling (flip) bifurcating system, enabling rates in subcritical, critical and supercritical step-size regimes.

Key results

• In the subcritical regime (eta < 2/lambda_*), transient instability is overcome in finite time and iterates converge linearly to a suboptimally flat global minimum at rate O(beta^t).
• In the critical regime (eta = 2/lambda_*), d_M(theta_t, theta_*) and |theta^perp_t| are both Theta(t^{-1/2}), a power-law convergence to the optimally flat minimum.
• In the supercritical regime (eta > 2/lambda_*), iterates converge at rate O((1-C_3(eta*lambda_*-2))^t) to a stable period-two orbit of amplitude approximately (eta*lambda_*-2)^{1/2} centred on the optimally flat minimum.

Surprising findings

• The sharpness of the loss is geodesically strongly convex on a geodesic ball in the solution manifold for deep scalar factorisation, despite the non-convexity of the landscape.
• The critical regime (power-law convergence to the optimally flat minimum with persistent oscillation) had not previously been identified in the literature.

Limitations

• Analysis restricted to codimension-1 least squares (single output, single datapoint), excluding multi-datapoint or multi-output regression.
• Assumes GD is initialised in a tubular neighbourhood of the solution manifold, which is not guaranteed under standard initialisation.
• Only the 2-periodic supercritical behaviour is analysed; higher-order periodicity and chaos are not covered.

Experimental setup

Metrics: distance to optimum orthogonal iterate magnitude sharpness suboptimality gap convergence rate

Baselines: Cohen et al. edge of stability analysis self-stabilisation analysis (Damian et al.)

Builds on: edge of stability (Cohen et al.) self-stabilisation (Damian et al.) Riemannian gradient descent

Closest papers by meaning

• Beyond the Edge of Stability via Two-step Gradient Updates (ICML 2023 · similarity 0.93)
• Classification at the Edge of Stability: Unifying Self-Stabilization and Convergence Rates (NeurIPS 2026 · similarity 0.92)
• Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability (ICLR 2021 · similarity 0.92)
• On the Unstable Convergence Regime of Gradient Descent (AAAI 2024 · similarity 0.91)
• A Precise Characterization of SGD Stability Using Loss Surface Geometry (ICLR 2024 · similarity 0.89)
• Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters (NeurIPS 2026 · similarity 0.89)