To understand why an optimization algorithm converges—and how to make it go faster—it is incredibly powerful to view the algorithm through the lens of a discrete linear dynamical system.
Consider a generic iterative algorithm trying to find an optimal solution $x^*$. At each step $k$, we can define an error vector $e_k = x_k - x^*$. For many classic algorithms, especially when optimizing quadratic functions or analyzing behavior locally near an equilibrium point, the update rule can be written as a linear transformation of the previous error:
$$e_{k+1} = T e_k$$
where $T$ is the transition matrix (or iteration matrix) of the algorithm. Unrolling this recurrence over $k$ steps yields:
$$e_k = T^k e_0$$
This simple equation reveals why the entire trajectory of the algorithm is dictated by the spectral properties of $T$. As $k$ grows large, the matrix power $T^k$ is dominated by its largest eigenvalue in absolute value. This value is known as the spectral radius, denoted as $\rho(T)$.
If $\rho(T) < 1$, the error shrinks to zero, guaranteeing convergence. The smaller the spectral radius, the faster the error decays. Consequently, $\rho(T)$ directly determines the asymptotic rate of linear convergence.
Tuning Parameters by Shifting Eigenvalues
Algorithm designers often have hyperparameters they can tune, such as the step size (learning rate), momentum parameters, or relaxation factors. Changing these parameters alters the entries of the transition matrix $T$, which in turn shifts its eigenvalues. Therefore, the quest for the "optimal" hyperparameters can be mathematically framed as an optimization problem: minimize $\rho(T)$ over the parameter space.
For instance, in the context of the Alternating Direction Method of Multipliers (ADMM), André M. H. Teixeira et al. used this exact approach in Optimal scaling of the ADMM algorithm for distributed quadratic programming to derive closed-form expressions for jointly optimal step-size and relaxation parameters by analyzing the roots of the characteristic polynomials of the iteration. Similarly, Euhanna Ghadimi et al. demonstrated in Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems that the optimal penalty parameter for constrained quadratic problems is determined by the geometric mean of the extreme eigenvalues of the system matrix. This selection minimizes the spectral radius of the transition operator, ensuring the fastest possible linear convergence.
This perspective also illuminates the behavior of momentum methods. Mahmoud Assran et al. in On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings modeled Nesterov's Accelerated Gradient (NAG) method as a linear dynamical system where the state vector tracks both error and momentum, showing how its convergence is dictated by the spectral radius of the resulting transition matrices. When studying the Heavy Ball method, Xiaoge Deng et al. in Exploring the Inefficiency of Heavy Ball as Momentum Parameter Approaches 1 examined how the error bounds scale with the momentum parameter $\beta$, showing that as $\beta \to 1$, the spectral properties of the transition matrix can cause instability and inefficiency.
Geometric Trajectories and Complex Eigenvalues
The spectrum of $T$ does more than just predict the speed of convergence; it also dictates the geometric path the algorithm takes. If the dominant eigenvalues of $T$ are purely real and positive, the error decays smoothly and monotonically. However, if the eigenvalues are complex, the error vector rotates as it shrinks.
This phenomenon explains the spiraling or oscillatory trajectories frequently observed in certain optimization settings. For example, Jingwei Liang et al. showed in Local Linear Convergence Analysis of Primal-Dual Splitting Methods that in primal-dual splitting methods, the non-linear proximal iterations can be linearized around the active manifold, and the resulting complex eigenvalues in the iteration matrix are precisely what cause the iterates to spiral toward the optimum.
Real Eigenvalues (Smooth Decay) Complex Eigenvalues (Spiraling Decay)
e_0 e_0
│ ╲
▼ ▼
e_1 e_2 ──► e_1
│ ▲ │
▼ │ ▼
e_2 └─── e_3
This geometric understanding becomes crucial when moving from single-objective minimization to multi-player games, such as Generative Adversarial Networks (GANs) or bilinear zero-sum games. In these settings, the interaction between competing agents introduces non-symmetric Jacobian matrices, which naturally possess complex eigenvalues.
Guojun Zhang et al. leveraged this in Convergence of Gradient Methods on Bilinear Zero-Sum Games by modeling gradient-based min-max solvers as discrete linear dynamical systems, using the spectral radius to prove why alternating updates provide larger stability regions and faster convergence than simultaneous updates. To find the fundamental "speed limits" of such games, Adam Ibrahim et al. in Linear Lower Bounds and Conditioning of Differentiable Games focused on the spectral modulus of these non-symmetric Jacobians to establish linear lower bounds for stationary linear iterations. Furthermore, Evan Becker et al. in Local Convergence of Gradient Descent-Ascent for Training Generative Adversarial Networks linearized the local dynamics of GANs near equilibrium to show how the spectral radius of the Jacobian matrix predicts phase transitions between convergence, oscillation, and divergence.
Spectral Radius as a Learning Objective
Because the spectral radius is the true arbiter of convergence speed, researchers have begun using it directly as an objective function to design better algorithms. Traditionally, machine learning models or numerical solvers might minimize a proxy metric like the Frobenius norm of the error matrix because it is computationally easier to handle.
However, Ali Taghibakhshi et al. demonstrated in Learning Interface Conditions in Domain Decomposition Solvers that the Frobenius norm often fails to reflect the actual convergence rate. A matrix can have a large Frobenius norm but a small spectral radius, meaning it might look bad in the first step but converges extremely quickly over time. To exploit this, the authors proposed using an unsupervised loss function that directly minimizes the spectral radius of the error-propagation operator, approximating the largest eigenvalue via Gelfand's formula to train highly accelerated domain decomposition solvers.
Analytical Tools for Spectral Mapping
To compute or bound the spectral radius of complex iterative systems, researchers rely on several specialized mathematical frameworks:
- Local Fourier Analysis (LFA): Used extensively in numerical analysis to study error propagation on grids. For instance, Yunhui He et al. adapted LFA in Local Fourier Analysis of Balancing Domain Decomposition By Constraints Algorithms to analytically determine optimal relaxation parameters that minimize the spectral radius of domain decomposition operators.
- Perron-Frobenius Theory: Applies to matrices with non-negative entries. Mert Gurbuzbalaban et al. utilized this theory in Randomness and permutations in coordinate descent methods to establish tight bounds on the rate of convergence for coordinate descent methods, helping explain why cyclic updates can asymptotically outperform randomized ones (When Cyclic Coordinate Descent Outperforms Randomized Coordinate Descent).
- Control Theory and Reinforcement Learning: The connection between spectral radius and stability is a cornerstone of control theory. Amir Massoud Farahmand et al. applied classic PID control techniques to Value Iteration in reinforcement learning in PID Accelerated Value Iteration Algorithm, explicitly accelerating convergence by shifting the eigenvalues of the value-function transition matrix further inside the unit circle.