Research map / Optimization / Optimizers
Understanding the Curse of Unrolling
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.
Provides a non-asymptotic analysis of the "curse of unrolling" (transient growth of derivative error in algorithm unrolling), shows explicit truncation of early iterations and warm-starting in bilevel optimization mitigate it.
Problem
Algorithm unrolling computes Jacobians of fixed-point solution maps by differentiating through iterations, but the derivative iterates can initially diverge from the true Jacobian before converging; the non-asymptotic behavior of this transient is not well understood.
Approach
Derives non-asymptotic error bounds for forward and reverse mode derivative iterates of contractive fixed-point iterations, identifying the k*rho^k term as the source of the curse, and shows that late-starting the derivative recursion (truncation) multiplies this term by rho^T, while warm-starting in bilevel optimization induces this truncation implicitly.
Key results
- Forward- and reverse-mode derivative errors can initially increase before decaying on gradient descent for least-squares problems, with the curse more pronounced for larger N (slower convergence) and optimal step size.
- Increasing the truncation index progressively suppresses the curse, with truncation evaluated under a fixed computational budget using omega=3.
- Using a suboptimal step size (1/(3L)) reduces the curse severity, and truncation is then largely ineffective.
Surprising findings
- Truncation is ineffective when the step size is suboptimal, since the derivative error does not increase substantially even without truncation.
Limitations
- Bounds rely on global contraction and global Lipschitz smoothness assumptions that may not hold in practice.
- Optimal truncation index requires unknown constants (rate, Lipschitz constants), and static autodiff graphs prevent adaptive truncation with stopping criteria.
- Experiments limited to quadratic least-squares problems; the bilevel warm-start benefit is described but not empirically evaluated in the main text.
Experimental setup
Benchmarks: quadratic least-squares with gradient descent (synthetic)
Metrics: derivative error norm to exact Jacobian iterate error
Baselines: vanilla unrolling (no truncation)
Builds on: Scieur et al. curse of unrolling implicit differentiation Banach fixed-point theorem
Closest papers by meaning
- Ascent Fails to Forget (NeurIPS 2025 · similarity 0.85)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.84)
- Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness (ICML 2025 · similarity 0.84)
- Unrolled denoising networks provably learn to perform optimal Bayesian inference (NeurIPS 2024 · similarity 0.84)
- How Memory in Optimization Algorithms Implicitly Modifies the Loss (NeurIPS 2025 · similarity 0.84)
- Loss Landscape Characterization of Neural Networks without Over-Parametrization (NeurIPS 2024 · similarity 0.83)
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.