Convergence Rates and Acceleration in Numerical Optimization
Convergence rates, acceleration, and the Nemirovski-Yudin lower bound
Goal of this page
Quantitatively evaluate the convergence rates of basic algorithms such as the gradient method and Newton's method using a function's smoothness ($L$) and strong convexity ($\mu$). Then understand that Nesterov's accelerated gradient method attains $O(1/k^2)$, and that this is the optimal rate for first-order methods, via the Nemirovski-Yudin lower bound. A bridge to the nonsmooth composite case (proximal gradient, FISTA) is also given.
Prerequisites
- Gradient Descent — Intermediate, Ch. 1
- Newton's Method — Intermediate, Ch. 2
- Quasi-Newton Methods — basics of BFGS
- Linear algebra (eigenvalues, positive definiteness), analysis (Taylor expansion, Lipschitz continuity)
§1. Convergence Rates and Optimality: The Viewpoint
Steepest descent, Newton's method, and quasi-Newton methods are algorithms that "move" the iterate toward the optimum. This chapter evaluates "how fast" they approach the optimum quantitatively, and further asks "can we go faster?" The key lies in two questions:
- Convergence-rate analysis: how to quantify a function's smoothness and curvature, and how that links to the number of iterations.
- Optimality: for a given class of functions, what is the fastest convergence rate achievable by a method that uses only first-order information (the gradient)?
The answer to the latter is surprising: the naive gradient method is not optimal, and Nesterov acceleration is asymptotically optimal. Since Nesterov's 1983 paper, this has become standard across many application areas.
§2. Smoothness, Strong Convexity, and the Condition Number
Definition 2.1 ($L$-smoothness)
A differentiable convex function $f: \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth if its gradient $\nabla f$ is $L$-Lipschitz continuous, that is, for all $x, y$,
$$\|\nabla f(x) - \nabla f(y)\| \le L\,\|x - y\|.$$If $f \in C^2$, this is equivalent to the largest eigenvalue of the Hessian being at most $L$ everywhere ($\nabla^2 f(x) \preceq L I$).
Definition 2.2 ($\mu$-strong convexity)
$f$ is $\mu$-strongly convex ($\mu > 0$) if, for all $x, y$,
$$f(y) \ge f(x) + \langle \nabla f(x), y - x\rangle + \dfrac{\mu}{2}\|y - x\|^2.$$If $f \in C^2$, this is equivalent to $\nabla^2 f(x) \succeq \mu I$. Intuitively, the function "curves at least as much as the quadratic $\dfrac{\mu}{2}\|x\|^2$ everywhere."
Definition 2.3 (condition number)
If $f$ is $L$-smooth and $\mu$-strongly convex, the condition number is defined by
$$\kappa := \dfrac{L}{\mu} \ge 1.$$$\kappa = 1$ corresponds to a "perfectly spherical" case such as the quadratic $\dfrac{\mu}{2}\|x\|^2$, whereas $\kappa \gg 1$ corresponds to a "long, narrow valley." The larger the condition number, the harder the optimization.
Example 2.1 (quadratic function)
For $f(x) = \dfrac{1}{2} x^\top A x$ ($A \succ 0$), we have $L = \lambda_{\max}(A)$, $\mu = \lambda_{\min}(A)$, and $\kappa = \lambda_{\max}/\lambda_{\min} = \mathrm{cond}(A)$, which coincides with the condition number from linear algebra.
§3. Convergence Rates of First-Order Methods
3.1 Smooth convex functions: the gradient method is $O(1/k)$
When $f$ is $L$-smooth convex (not strongly convex), the gradient method with step size $\eta = 1/L$,
$$x_{k+1} = x_k - \dfrac{1}{L} \nabla f(x_k),$$satisfies the following bound on the function-value gap:
Theorem 3.1 (gradient method, smooth convex)
$$f(x_k) - f(x^*) \le \dfrac{L\,\|x_0 - x^*\|^2}{2k}$$That is, $O(1/k)$ convergence. Obtaining an $\varepsilon$-optimal solution requires $k \sim L \|x_0 - x^*\|^2 / \varepsilon$ iterations.
3.2 Strongly convex case: linear convergence $O((1 - 1/\kappa)^k)$
If $f$ is additionally $\mu$-strongly convex, the same step size gives linear convergence:
Theorem 3.2 (gradient method, strongly convex)
$$\|x_k - x^*\|^2 \le \left(1 - \dfrac{1}{\kappa}\right)^k \|x_0 - x^*\|^2$$An $\varepsilon$-optimal solution needs $k \sim \kappa \log(1/\varepsilon)$ iterations. The bottleneck is the iteration count proportional to the condition number $\kappa$.
This is the limit of the classical gradient method. The next section treats the acceleration that improves upon it.
§4. Nesterov's Accelerated Gradient Method
4.1 Motivation: the heavy-ball method
Polyak (1964) introduced the heavy-ball method:
$$x_{k+1} = x_k - \eta \nabla f(x_k) + \beta (x_k - x_{k-1}).$$The second term represents "momentum." On quadratics, choosing $\eta, \beta$ appropriately improves the iteration count with respect to the condition number $\kappa$ to $\sqrt{\kappa}$, but for general strongly convex functions it has the drawback that global convergence is not guaranteed.
4.2 Nesterov's accelerated gradient method (NAG)
Nesterov (1983) modified the heavy-ball method to evaluate the gradient not at $x_k$ but at an extrapolated point $y_k$. For an $L$-smooth convex function:
Algorithm 4.1 (Nesterov accelerated gradient, convex case)
Initialize $x_0 = y_0$, $t_0 = 1$. For $k = 0, 1, \ldots$:
- $x_{k+1} = y_k - \dfrac{1}{L} \nabla f(y_k)$ (gradient step)
- $t_{k+1} = \dfrac{1 + \sqrt{1 + 4 t_k^2}}{2}$
- $y_{k+1} = x_{k+1} + \dfrac{t_k - 1}{t_{k+1}} (x_{k+1} - x_k)$ (extrapolation)
Theorem 4.1 (NAG convergence, convex case)
$$f(x_k) - f(x^*) \le \dfrac{2 L\,\|x_0 - x^*\|^2}{(k+1)^2}$$That is, $O(1/k^2)$, one order faster than the gradient method's $O(1/k)$.
4.3 Acceleration in the strongly convex case
If $f$ is $L$-smooth and $\mu$-strongly convex, the accelerated method with fixed extrapolation coefficient $\beta = (\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)$ gives:
Theorem 4.2 (NAG convergence, strongly convex case)
$$f(x_k) - f(x^*) \le L\,\|x_0 - x^*\|^2 \left(1 - \dfrac{1}{\sqrt{\kappa}}\right)^k$$An $\varepsilon$-optimal solution needs $k \sim \sqrt{\kappa} \log(1/\varepsilon)$ iterations. Compared with the classical gradient method's $\kappa \log(1/\varepsilon)$, the decisive point is the dependence on the square root of the condition number.
§5. Convergence Rates of Second-Order Methods — Newton and Quasi-Newton
5.1 Local Q-quadratic convergence of Newton's method
If $f \in C^2$ and the Hessian is Lipschitz continuous and nonsingular near the solution, the Newton iteration $x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$ satisfies, from a sufficiently good initial point,
$$\|x_{k+1} - x^*\| \le C\,\|x_k - x^*\|^2$$(Q-quadratic convergence). In practice it reaches machine precision in 5–10 iterations.
The flip side of local convergence — globalization and cost
Newton's convergence rate is the strongest locally, but only when started near the solution; from a far initial point it may diverge. Hence in practice it is globalized with trust-region methods, Newton's method with line search, cubic regularization, and the like.
Moreover, each iteration is costly, $O(n^3)$, because it solves a linear system involving the Hessian. For large problems, therefore, Hessian-free Newton (CG-based), which does not form the Hessian explicitly, is used.
5.2 Superlinear convergence of BFGS
Quasi-Newton methods such as BFGS do not compute the Hessian directly; they approximate it by low-rank updates from the gradient history. If $f$ is $L$-smooth and $\mu$-strongly convex and the initial Hessian approximation is good, then near the solution
$$\lim_{k \to \infty} \dfrac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|} = 0,$$that is, Q-superlinear convergence (weaker than Q-quadratic but stronger than linear). Each iteration costs $O(n^2)$, lighter than Newton's method. L-BFGS is lighter still at $O(mn)$ ($m$ the memory length).
§6. The Optimal-Rate Lower Bound — Nemirovski-Yudin
How fast can first-order methods possibly be? In 1983 Nemirovski and Yudin gave a rigorous lower bound:
Theorem 6.1 (Nemirovski-Yudin lower bound, convex case)
For any first-order method (using only the gradient at each iteration, with $x_k$ in the subspace spanned by $\{x_0, \nabla f(x_0), \ldots, \nabla f(x_{k-1})\}$), there exists an $L$-smooth convex function $f$ and an initial point $x_0$ such that
$$f(x_k) - f(x^*) \ge \dfrac{3 L\,\|x_0 - x^*\|^2}{32(k+1)^2}.$$That is, an $\Omega(1/k^2)$ lower bound holds. It is attainable in dimension $n \ge 2k$.
Combining Theorem 4.1 (NAG's $O(1/k^2)$) with Theorem 6.1 (the $\Omega(1/k^2)$ lower bound):
Conclusion: Nesterov acceleration is optimal (up to constants)
Within the class of smooth convex functions, the fastest convergence rate achievable by a first-order method is $\Theta(1/k^2)$, and Nesterov's accelerated gradient method attains it (up to a constant factor).
The bound concerns "first-order" methods
This lower bound is a statement about first-order methods that use only the gradient; it does not apply to Newton's method (§5), which uses second-order (Hessian) information. Newton's local Q-quadratic convergence—far faster than $O(1/k^2)$—lies outside this bound.
Similarly, in the strongly convex case the lower bound is $\Omega((1 - 1/\sqrt{\kappa})^k)$, and the strongly convex version of Nesterov acceleration attains this rate.
§7. Bridge to the Nonsmooth Extension
When the objective is a sum of a smooth and a nonsmooth term, $F(x)=f(x)+g(x)$ ($f$ an $L$-smooth convex function, $g$ a nonsmooth convex function such as $\|x\|_1$ or an indicator function)—a composite problem—the gradient method cannot be applied directly because $g$ is nondifferentiable. Yet through the proximal map of $g$, the acceleration ideas of this chapter carry over unchanged. Alternating a gradient step on $f$ with the proximal map of $g$ gives the proximal gradient method (ISTA) with rate $O(1/k)$, and adding the same extrapolation as in §4 gives FISTA with $O(1/k^2)$—the same optimal order as the smooth case.
The derivation via forward-backward splitting, the convergence proofs, the implementation (backtracking, restart), and applications to Lasso, total variation, and compressed sensing are collected in the dedicated article Proximal Gradient Method and FISTA. For the proximal map itself—its definition, properties, and closed forms—see the Proximal Operator.
Summary
Key points of this chapter
- A function's properties are measured by $L$-smoothness and $\mu$-strong convexity; the ratio $\kappa = L/\mu$ is the condition number.
- Classical gradient method: $O(1/k)$ for smooth convex, $O((1 - 1/\kappa)^k)$ for strongly convex.
- Nesterov accelerated gradient (NAG): $O(1/k^2)$ for convex, $O((1 - 1/\sqrt{\kappa})^k)$ for strongly convex.
- By the Nemirovski-Yudin lower bound, NAG is asymptotically optimal among first-order methods.
- Newton's method is locally Q-quadratic; BFGS is locally Q-superlinear.
- The nonsmooth extension (proximal gradient ISTA, accelerated FISTA) and its implementation (restart, backtracking) are collected in Proximal Gradient Method and FISTA.
This convergence-rate analysis is a basic tool in the following chapters as well (stochastic optimization, variational problems, optimization on Riemannian manifolds, and more).
References
- Nesterov, Y. (1983). "A method of solving a convex programming problem with convergence rate $O(1/k^2)$". Soviet Math. Dokl. 27 (2): 372-376.
- Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Kluwer.
- Beck, A., Teboulle, M. (2009). "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems". SIAM J. Imaging Sciences 2 (1): 183-202.
- Nemirovski, A. S., Yudin, D. B. (1983). Problem Complexity and Method Efficiency in Optimization. Wiley.
- Bubeck, S. (2015). "Convex Optimization: Algorithms and Complexity". Foundations and Trends in Machine Learning 8 (3-4): 231-357. arXiv:1405.4980
Frequently Asked Questions
Why is Nesterov acceleration faster than the ordinary gradient method?
Because the extrapolation term reuses the past direction of motion. The dependence on the condition number improves from $\kappa$ to $\sqrt{\kappa}$, giving a dramatic speedup especially when $\kappa$ is large (a long, narrow valley). By the Nemirovski-Yudin lower bound, this is optimal among first-order methods.
What is the condition number of a quadratic function?
For $f(x) = \dfrac{1}{2}x^\top A x$ ($A \succ 0$), $\kappa = \lambda_{\max}(A)/\lambda_{\min}(A) = \mathrm{cond}(A)$, which coincides with the condition number from linear algebra. Geometrically, the ratio of the Hessian's eigenvalues measures the "elongation of the level sets."
What is FISTA used for?
It is used to solve nonsmooth regularized minimization such as Lasso, image restoration, and compressed sensing. When the objective has the form $f(x) + g(x)$ ($f$ a smooth convex function, $g$ a nonsmooth convex function whose proximal map is computable), it is the standard method converging at $O(1/k^2)$.
When should one use Newton's method versus BFGS?
Newton's method has the strongest local rate (Q-quadratic) but each iteration's Hessian solve, $O(n^3)$, is costly. For medium-to-large problems, BFGS (locally Q-superlinear, $O(n^2)$) or L-BFGS ($O(mn)$, $m$ the memory length) is chosen. For $n \gtrsim 10^3$ use L-BFGS; for $n \gtrsim 10^6$, stochastic, accelerated, or distributed optimization is realistic.