Imagine hiking to a mountain peak. A map that guarantees "you will eventually reach the summit" is reassuring, but it leaves out a critical piece of information: will the journey take two hours or two weeks?
In mathematical optimization and machine learning, a similar gap often exists. Proving asymptotic convergence establishes that an iterative algorithm will eventually find the optimal solution as the number of steps approaches infinity. However, to build practical, scalable software, engineers and researchers need to know the convergence rate—the iteration complexity that quantifies exactly how much closer to the solution an algorithm gets with each step.
Many foundational algorithms have historically lacked these explicit rate guarantees. For instance, in multi-task network structure learning, Jean Honorio et al. demonstrated in Multi-Task Learning of Gaussian Graphical Models that a complex structural optimization problem could be solved efficiently by reduction to quadratic knapsack problems, yet the theoretical rate of convergence remained unquantified. Similarly, for minimizing convex functions split into smooth and non-smooth components, Hugo Raguet et al. introduced a powerful framework in A Generalized Forward-Backward Splitting, but left its exact sublinear or linear decay rate as an open question.
Characterizing these rates is the key to transforming qualitative algorithmic ideas into predictable, high-performance computational tools.
The Spectrum of Algorithmic Speed
To understand why convergence rates matter, it helps to look at the mathematical regimes that define algorithmic progress. Optimization speeds typically fall into three primary categories: sublinear, linear, and quadratic.
Sublinear: Error ≈ 1 / k (Slow, progress decays)
Linear: Error ≈ c^k (Steady, constant % reduction)
Quadratic: Error ≈ c^(2^k) (Explosive, doubles correct digits)
- Sublinear Convergence ($O(1/k)$): Progress slows down significantly the closer the algorithm gets to the optimum. It is common in non-smooth or poorly conditioned problems.
- Linear Convergence ($O(c^k)$ where $0 < c < 1$): The error shrinks by a fixed percentage at every single step. In matrix and tensor factorization, Jianze Li et al. established local linear convergence for Jacobi-type algorithms using a gradient-based selection rule in Approximate matrix and tensor diagonalization by unitary transformations: convergence of Jacobi-type algorithms. Similarly, Song Ping Zhou et al. proved the first known linear convergence rate for a limited-memory variant of Kelley's Method in Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives, providing a predictable runtime bound where classic simplicial methods lacked guarantees.
- Quadratic Convergence ($O(c^{2^k})$): The gold standard of optimization. The number of correct digits in the solution roughly doubles with each iteration. In Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression, Zhankun Luo et al. provided a major geometric breakthrough by proving that the Expectation-Maximization (EM) algorithm for two-component mixed linear regression achieves a consistent quadratic convergence rate in noiseless settings, bypassing the slower rates typically expected of statistical mixture solvers.
Mathematical Tools for Unlocking Rates
How do theoreticians move from an asymptotic proof to an exact iteration complexity bound? They generally rely on three core strategies: mapping geometric trajectories, exploiting structural smoothness, or establishing error bounds.
1. Geometric Trajectories
Sometimes, an algorithm's path through the parameter space follows a hidden, highly structured geometric curve. By identifying this curve, researchers can calculate exact step-by-step progress. For example, the aforementioned work by Zhankun Luo et al. mapped the exact trajectory of EM updates to a mathematical curve known as a cycloid. This geometric insight allowed them to prove the transition from general super-linear behavior to an explicit quadratic rate.
2. Structural Smoothness
When optimization problems involve non-smooth constraints (like absolute values or sparsity-inducing norms), standard calculus breaks down. However, functions often exhibit "partial smoothness"—meaning they are smooth along certain active manifolds or constraints. In Convergence Rates of Forward-Douglas-Rachford Splitting Method, Cesare Molinari et al. leveraged this partly smooth geometry to derive new global sublinear and local linear convergence rates for operator splitting methods, explaining why these algorithms perform exceptionally well on structured machine learning problems.
3. Error Bounds
An error bound is an inequality that bounds the distance from a current point to the optimal solution set using a measurable quantity, such as the size of a projected gradient step. If an algorithm satisfies a strong error bound, it cannot stall far away from the optimum. In Convergence rate of a gradient projection method for solving variational inequalities, Pham Duy Khanh et al. utilized a projection-type error bound to prove the linear convergence rate of the Gradient Projection Method for co-coercive mappings, providing a unified framework for evaluating numerical efficiency.
The Frontier: Non-Convexity and Over-Parameterization
The boundary of convergence rate analysis continues to expand as machine learning models grow more complex. In non-convex landscapes or over-parameterized regimes (like deep neural networks), finding any global optimum is challenging, let alone proving how fast you will get there.
In over-parameterized models, Lénaïc Chizat et al. utilized Wasserstein gradient flows in On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport to show that gradient descent converges to a global minimizer in the many-particle limit. Yet, as the authors noted, establishing a quantitative convergence rate for this regime remains an open challenge.
Conversely, progress is accelerating in non-convex block coordinate frameworks. In Complexity of Block Coordinate Descent with Proximal Regularization and Applications to Wasserstein CP-dictionary Learning, Dohyun Kwon et al. provided the first global worst-case complexity analysis for Block Coordinate Descent with Proximal Regularization (BCD-PR) on general nonconvex smooth objectives. They proved that the method reaches an $\epsilon$-stationary point within exactly $O(\epsilon^{-1}(\log \epsilon^{-1})^2)$ iterations.
By replacing empirical guesswork with rigorous iteration complexity bounds, convergence rate analysis allows the field to transition from simply knowing that an algorithm can find a solution, to knowing exactly when it will finish.