Convergence Rates

Optimization · Axiom Academy

LESSON Convergence Rates in Optimization Understanding how fast algorithms approach optimal solutions Convergence rate describes how the error decreases as an optimization algorithm iterates. We classify convergence into three main categories based on how error shrinks at each iteration. The general convergence formula is: ||x k+1 - x*|| ≤ c||x k - x*|| p , where: O-notation (Big-O) provides a formal mathematical framework for describing convergence rates. It characterizes the asymptotic behavior of the error as iterations progress. 3 Why Gradient Descent Has Linear Convergence For strongly convex functions with L-Lipschitz continuous gradients, gradient descent with appropriate step size achieves linear convergence. The convergence rate depends on the condition number of the problem. The constant c = (κ - 1)/(κ + 1) where κ is the condition number. As κ increases, c approaches 1, and convergence slows dramatically. 4 Visual Comparison of Convergence Rates The difference between linear, superlinear, and quadratic convergence becomes dramatic after just a few iterations. Quadratic methods can achieve high accuracy in remarkably few steps. ~20-50 iterations for accuracy 5 Condition Number and Its Effect on Convergence The condition number κ = L/μ (ratio of largest to smallest eigenvalues of the Hessian) profoundly affects convergence. Well-conditioned problems (κ ≈ 1) converge quickly; ill-conditioned problems (κ >> 1) converge slowly.

This is the written version of the interactive lesson above. See the full Optimization course.