Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Region

2025/09/29 by Liang, Shuang, Montúfar, Guido · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2509.25351

Abstract

We examine gradient descent in matrix factorization and show that under large step sizes the parameter space develops a fractal structure. We derive the exact critical step size for convergence in scalar-vector factorization and show that near criticality the selected minimizer depends sensitively on the initialization. Moreover, we show that adding regularization amplifies this sensitivity, generating a fractal boundary between initializations that converge and those that diverge. The analysis extends to general matrix factorization with orthogonal initialization. Our findings reveal that near-critical step sizes induce a chaotic regime of gradient descent where the long-term dynamics are unpredictable and there are no simple implicit biases, such as towards balancedness, minimum norm, or flatness.

Citations

• Low Rank Gradients and Where to Find Them
• A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorization
• Leveraging chaotic transients in the training of artificial neural networks
• The geometry of the deep linear network
• Where Do Large Learning Rates Lead Us?
• Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization
• Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes
• Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
• Deep linear networks for regression are implicitly regularized towards flat minima
• Dynamical stability and chaos in artificial neural network trajectories along training
• Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency
• On the Convergence of Gradient Descent for Large Learning Rates
• The boundary of neural network trainability is fractal
• Universal Sharpness Dynamics in Neural Network Training: Fixed Point Analysis, Edge of Stability, and Route to Chaos
• Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult
• A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks
• From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression
• Trajectory Alignment: Understanding the Edge of Stability Phenomenon via Bifurcation Theory
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks
• Catapults in SGD: spikes in the training loss and their impact on generalization through feature learning
• Gradient descent in matrix factorization: Understanding large initialization
• How Two-Layer Neural Networks Learn, One (Giant) Step at a Time
• The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descent
• Gradient Descent Monotonically Decreases the Sharpness of Gradient Flow Solutions in Scalar Networks and Beyond
• Phase diagram of early training dynamics in deep neural networks: effect of the learning rate, depth, and width
• Catapult Dynamics and Phase Transitions in Quadratic Nets
• Learning threshold neurons via the "edge of stability"
• SGD with Large Step Sizes Learns Sparse Features
• Second-order regression models exhibit progressive sharpening to the edge of stability
• Understanding Edge-of-Stability Training Dynamics with a Minimalist Example
• Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability
• Beyond the Edge of Stability via Two-step Gradient Updates
• Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs
• Quadratic models for understanding catapult dynamics of neural networks
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation
• Understanding the unstable convergence of gradient descent
• On the Optimization Landscape of Neural Collapse under MSE Loss: Global\n Optimality with Unconstrained Features
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Gradient Descent on Neural Networks Typically Occurs at the Edge of\n Stability
• Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
• Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank
• A Unifying View on Implicit Bias in Training Linear Neural Networks
• The large learning rate phase of deep learning: the catapult mechanism
• The Break-Even Point on Optimization Trajectories of Deep Neural Networks
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Global Convergence of Gradient Descent for Deep Linear Residual Networks
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers\n are Automatically Balanced
• Step Size Matters in Deep Learning
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Gradient descent with identity initialization efficiently learns\n positive definite linear transformations by deep residual networks
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified\n Geometric Analysis
• Identity Matters in Deep Learning
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• Fractal Geometry: Mathematical Foundations and Applications.
• Beyond the Quadratic Approximation: the Multiscale Structure of Neural Network Loss Landscapes

Cited by

• Sharpness of Minima in Deep Matrix Factorization: Exact Expressions

Related

• Gradient descent in matrix factorization: Understanding large initialization
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
• Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth