Pseudospectral Bounds for Transient Amplification in Coupled Gradient Descent

Coupled gradient descent—where the update of one parameter depends on another—arises naturally in bilevel optimization, two-time-scale stochastic approximation, and generative adversarial networks. When the coupled Jacobian is block-triangular, asymptotic stability is determined by the spectral radii of the diagonal blocks, yet transient amplification before convergence can be arbitrarily large due to non-normality. We develop a sharp pseudospectral theory for block-triangular Jacobians $J = \begin{bmatrix} A & 0 \\ C & D \end{bmatrix}$, proving Kreiss-constant bounds of the form $K(J) \le 2/(1-\gamma) + \|C\|/(4(1-\gamma))$ when $\rho(A),\rho(D) \le \gamma < 1$ and $A, D$ are symmetric, and establishing matching minimax lower bounds. We characterize the critical coupling threshold for spectral instability and extend the theory to nearly self-referential systems via a Neumann-series perturbation framework. As a consequence, we obtain a finite-horizon $O(K(J)^2 \log(1/\delta))$ iteration-complexity bound. Framed as scaling laws for stochastic two-time-scale optimization, our results expose a non-asymptotic, instance-dependent regime of high-dimensional learning dynamics that is invisible to spectral-radius analysis. Experiments on linear-quadratic problems, IQC-based comparisons, and neural-network training confirm the theory.