Transient Amplification in Cascaded Gradient Methods: Exact Minimax Laws and Tracking without Resonance
Abstract
Leader-follower gradient iterations, including bilevel and two-time-scale methods, can exhibit large finite-time excursions despite asymptotic stability. For cascaded iterations with block matrix J = [[A,0],[C,D]], symmetric diagonal blocks of norm at most gamma < 1, and coupling norm at most c, we prove an exact, dimension-free minimax formula: at every horizon t, the worst-case amplification equals the spectral norm of [[gamma^t,0],[c t gamma^(t-1),gamma^t]], attained by an aligned two-dimensional quadratic. Consequently, the worst transient is on the order of 1 + c/(1-gamma), and eigenvalues alone cannot predict finite-time gain. Under martingale noise, the aligned system has stationary follower variance sigma^2 c^2 (1+gamma^2)/(1-gamma^2)^3, establishing cubic inverse-gap scaling. For quadratic followers, the coupling is linked to follower sensitivity R by C = (I-D)R. When the leader is isotropic and the follower map is positive semidefinite, amplification is at most 1 plus the operator norm of R, independently of the spectral gaps. A look-ahead Newton update eliminates follower memory and is minimax-optimal among linear updates that track the leader exactly. Experiments validate the bounds and show that accelerated or inexact follower solvers can exceed the sensitivity bound when their effective maps have negative eigenvalues. Code and experiment scripts: https://github.com/Axym-Labs/transient-amplification
Related
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- Optimal Design of Distributed Inexact Gradient Tracking: Exact Worst-case Convergence Rate and Explicit Parameters
- Topology-aware HVT MTCMOS power gating for power–delay optimization of cascaded transmission-gate MUX and DEMUX
- A cascaded U-nets model based on hybrid attention for video anomaly detection
- Factorisation and matrix amplification of real rank zero inclusions
BibTeX
@misc{ariq2026transient,
title = {{Transient Amplification in Cascaded Gradient Methods: Exact Minimax Laws and Tracking without Resonance}},
author = {Ahanaf Hasan Ariq and Davide Wiest},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.04031},
eprint = {2606.04031},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.04031},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Transient Amplification in Cascaded Gradient Methods: Exact Minimax Laws and Tracking without Resonance
AU - Ahanaf Hasan Ariq
AU - Davide Wiest
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2606.04031
UR - https://arxiv.org/abs/2606.04031
AB - Leader-follower gradient iterations, including bilevel and two-time-scale methods, can exhibit large finite-time excursions despite asymptotic stability. For cascaded iterations with block matrix J = [[A,0],[C,D]], symmetric diagonal blocks of norm at most gamma < 1, and coupling norm at most c, we prove an exact, dimension-free minimax formula: at every horizon t, the worst-case amplification equals the spectral norm of [[gamma^t,0],[c t gamma^(t-1),gamma^t]], attained by an aligned two-dimensional quadratic. Consequently, the worst transient is on the order of 1 + c/(1-gamma), and eigenvalues alone cannot predict finite-time gain. Under martingale noise, the aligned system has stationary follower variance sigma^2 c^2 (1+gamma^2)/(1-gamma^2)^3, establishing cubic inverse-gap scaling. For quadratic followers, the coupling is linked to follower sensitivity R by C = (I-D)R. When the leader is isotropic and the follower map is positive semidefinite, amplification is at most 1 plus the operator norm of R, independently of the spectral gaps. A look-ahead Newton update eliminates follower memory and is minimax-optimal among linear updates that track the leader exactly. Experiments validate the bounds and show that accelerated or inexact follower solvers can exceed the sensitivity bound when their effective maps have negative eigenvalues. Code and experiment scripts: https://github.com/Axym-Labs/transient-amplification
ER -