Research map / Optimization / Implicit bias and generalization
Learning Provably Improves the Convergence of Gradient Descent
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.
Proves linear training convergence for a Math-L2O model (a recurrent NN that learns GD step sizes) using NTK theory with a wide layer, and proposes a deterministic initialization that mitigates gradient explosion.
Problem
Learn-to-Optimize (L2O) unrolled solvers lack rigorous guarantees for their own training convergence, and the link between training convergence (over epochs) and solver convergence (over optimization steps) is unclear; existing analyses rely on unrealistic assumptions and suffer gradient explosion u
Approach
Treat the Math-L2O NN (which outputs per-coordinate GD step sizes) as an over-parameterized network analyzed via NTK theory, prove a linear training-loss rate that is at least as fast as GD's rate, and use a deterministic initialization (zero last layer, QR-orthogonalized Gaussian inner layers, expansion coefficient e) to satisfy the required singular-value conditions and control gradients.
Key results
- Math-L2O training loss converges linearly, matching the theoretical rate, on synthetic quadratic problems with T=100 steps.
- The method achieves over 50% better optimality than standard GD after training (abstract claim, relative improvement on synthetic data).
- Ablation shows that LR 1e-3 causes instability or divergence at expansion coefficient e=50, while 1e-4 and smaller converge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train Math-L2O to learn adaptive GD step sizes | Gradient Descent · Synthetic quadratic optimization problems | solution optimality: over 50% better optimality | Helped |
| Use a learning rate of 10^{-3} instead of 10^{-4} or smaller (ablation) | Math-L2O (e=50) · Synthetic optimization, T=20 | relative objective improvement | Hurt |
| Reduce the learning rate below the stability threshold (ablation) | Math-L2O (e=50) · Synthetic optimization, T=20 | convergence rate | Hurt |
| Increase the initialization expansion coefficient e (ablation) | Math-L2O (η=10^{-7}) · Synthetic optimization, T=20 | relative objective improvement | Helped |
| Use the proposed Math-L2O method rather than standard GD | Math-L2O · Synthetic optimization problems | solution optimality: up to a 50\% improvement | Helped |
| Use the proposed Math-L2O method rather than state-of-the-art L2O methods or Adam | Math-L2O · Synthetic datasets | robustness | Helped |
Surprising findings
- Prior Math-L2O and LISTA-CPSS training is unstable: gradients overflow at high learning rates and training converges poorly at low learning rates.
- Measured LISTA-CPSS convergence conditions are frequently violated during inference, particularly in early steps.
Limitations
- Theoretical bounds require very small learning rates that shrink with depth L and steps T, and an expansion coefficient e that grows with T.
- Experiments are limited to synthetic Gaussian quadratic problems with small numbers of training problems.
- Assumes X_0 = 0 and a width-O(Nd) over-parameterized network, with detached input-feature gradients in the implementation.
Experimental setup
Datasets: synthetic Gaussian quadratic problems
Benchmarks: synthetic quadratic programming instances
Metrics: training loss relative objective improvement over GD
Baselines: Gradient Descent Math-L2O LISTA-CPSS Adam
Builds on: Math-L2O LISTA-CPSS Neural Tangent Kernel Back-Propagation-Through-Time
Closest papers by meaning
- Training Stronger Baselines for Learning to Optimize (NeurIPS 2020 · similarity 0.90)
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks (ICLR 2019 · similarity 0.89)
- LPGD: A General Framework for Backpropagation through Embedded Optimization Layers (ICML 2024 · similarity 0.87)
- Optimization for Neural Operators can Benefit from Width (ICML 2025 · similarity 0.87)
- On the Parameterization of Second-Order Optimization Effective towards the Infinite Width (ICLR 2024 · similarity 0.87)
- Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regression (NeurIPS 2024 · similarity 0.86)
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.