Spectral Convergence Analysis of Iterative Optimization

238 concepts170 papers1 proposal

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:

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_spectral_convergence_analysis_65d8c3ad,
  title = {spectral convergence analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spectral-convergence-analysis/rdr_65d8c3add7eb4f41ba385edeaf36dbe1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_spectral_convergence_analysis_65d8c3ad_v1,
  title = {spectral convergence analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spectral-convergence-analysis/rdr_65d8c3add7eb4f41ba385edeaf36dbe1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake