Characterizing the Convergence Rates of Iterative Algorithms

136 concepts136 papers2 proposals

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)

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.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_convergence_rate_analysis_convergence_ra_bbfb5036,
  title = {convergence rate analysis (convergence rate characterization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convergence-rate-analysis-convergence-rate-characterization/rdr_bbfb5036b6e94cada4232771f0cfcc59},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_convergence_rate_analysis_convergence_ra_bbfb5036_v1,
  title = {convergence rate analysis (convergence rate characterization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convergence-rate-analysis-convergence-rate-characterization/rdr_bbfb5036b6e94cada4232771f0cfcc59/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake