Source-linked AI summary
A unified convergence bound for conjugate gradient and accelerated gradient
Sahar Karimi, Stephen A. Vavasis
TL;DR
The paper addresses the lack of a unified convergence analysis for accelerated gradient and linear conjugate gradients, which share an asymptotic bound in their respective settings. It develops a shared potential-based bound and a direct CG analysis; the potential’s prescribed decrease can also help monitor proposed CG implementations. The discussion notes that the potential cannot be evaluated by an algorithm using only quantities available in practice.
Problem
Accelerated gradient and linear conjugate gradients have similar asymptotic bounds in their respective settings, but their conventional analyses differ, and no direct CG analysis is identified.
Source: §1 · p. 2Method
The paper establishes a common one-step convergence bound for both methods using a potential-based analysis.
Source: §1 · p. 2, §8 · p. 13Results
The proposed CG potential should decrease by at least a fixed constant factor each iteration, offering a way to monitor proposed implementations for failures such as roundoff error.
Source: §8 · p. 14Takeaways & Limitations
The analysis may support new analyses of perturbed CG methods that lack Krylov-space optimality, including methods with noisy matrix-vector products or changing preconditioners.
Source: §8 · p. 14The proposed potential cannot be evaluated by an algorithm to measure progress because it uses the objective residual and distance to the optimizer.
Source: §8 · p. 14
Abstract
from arXiv · showhide
Nesterov's accelerated gradient method for minimizing a smooth strongly convex function $f$ is known to reduce $f(\x_k)-f(\x^*)$ by a factor of $\eps\in(0,1)$ after $k\ge O(\sqrt{L/\ell}\log(1/\eps))$ iterations, where $\ell,L$ are the two parameters of smooth strong convexity. Furthermore, it is known that this is the best possible complexity in the function-gradient oracle model of computation. The method of linear conjugate gradients (CG) also satisfies the same complexity bound in the special case of strongly convex quadratic functions, but in this special case it is faster than the accelerated gradient method. Despite similarities in the algorithms and their asymptotic convergence rates, the conventional analyses of the two methods are nearly disjoint. The purpose of this note is provide a single quantity that decreases on every step at the correct rate for both algorithms. Our unified bound is based on a potential similar to the potential in Nesterov's original analysis. As a side benefit of this analysis, we provide a direct proof that conjugate gradient converges in $O(\sqrt{L/\ell}\log(1/\eps))$ iterations. In contrast, the traditional indirect proof first establishes this result for the Chebyshev algorithm, and then relies on optimality of conjugate gradient to show that its iterates are at least as good as Chebyshev iterates. To the best of our knowledge, ours is the first direct proof of the convergence rate of linear conjugate gradient in the literature.
1 Conjugate gradient
The paper addresses the lack of a direct convergence analysis for linear conjugate gradients and seeks a bound shared with accelerated gradient. It introduces a potential whose decrease yields the stated convergence bound for accelerated gradient on smooth strongly convex functions and for conjugate gradients on strongly convex quadratics.
1 Conjugate gradient
- Linear CG minimizes strongly convex quadratic functions of the form f(x) = x^T A x/2 − b^T x, with A symmetric positive definite.The paper distinguishes this quadratic setting from the more general smooth strongly convex functions handled by accelerated gradient.Source: §1 · pp. 1–2
- The paper situates its unified analysis alongside prior accelerated-gradient analyses and notes that CG can be substantially faster in quadratic-function tests.Both methods have the same asymptotic bound in this setting, but the paper describes their conventional analyses as different.Source: §1 · p. 2
- The paper’s direct CG analysis uses the algorithm’s recurrence rather than relying on another method’s convergence and CG’s Krylov-space optimality.Earlier analyses first established the bound for methods such as Chebyshev iteration, then used CG’s optimality in the generated affine space.Source: §1 · p. 2
- A common potential yields a one-step decrease bound for both accelerated gradient and conjugate gradients, despite the irregular stepwise behavior of their individual error measures.The potential combines a perturbed distance to the optimizer with the objective residual.Source: §1 · pp. 2–3
- The resulting theorem gives the accelerated-gradient bound for smooth strongly convex functions and the same bound for conjugate gradients on quadratic functions.The bound’s exponent is k − 1 because the initial step establishes Ψ1 ≤ Ψ0 rather than the recurring contraction.Source: §1 · p. 3
2 Accelerated gradient method
The paper introduces accelerated gradient by referring to Nesterov’s treatment. The supplied passage does not provide further details of the method.
2 Accelerated gradient method
- The paper presents accelerated gradient following Nesterov’s treatment in his book.The method is introduced for a strongly convex function with parameters L and ℓ.Source: §2 · p. 3
Accelerated gradient method
The accelerated-gradient recurrence updates an extrapolated point, takes a gradient step, and records the resulting displacement. The initial extrapolation is specially defined because the initial displacement is unavailable.
Accelerated gradient method
- The recurrence forms y_k+1 from x_k and the previous displacement, takes a gradient step from y_k+1 to obtain x_k+1, then records x_k+1 − x_k.At k = 0, the method sets y_1 = x_0 and θ_0 = 0 because s_0 is undefined; for later steps, the analysis uses a specified choice of θ_k.Source: Accelerated gradient method · pp. 3–4
3 Conjugate gradient method
The section presents linear conjugate gradients for a quadratic with a symmetric positive definite matrix and reviews its established convergence analysis. The paper’s direct analysis avoids the traditional argument from Chebyshev convergence and Krylov-space optimality.
3 Conjugate gradient method
- Linear conjugate gradients is presented for minimizing f(x) = x^T A x/2 − b^T x, where A is symmetric positive definite.The recurrence initializes the residual as b − Ax_0 and updates the iterate and residual using the search direction.Source: §3 · p. 4
- The established Daniel convergence argument transfers Chebyshev’s bound to CG through CG’s optimality over the affine Krylov space.The paper’s analysis does not rely on that optimality argument.Source: §3 · p. 5
- Daniel’s bound is tight up to constant factors for some matrix and starting vector choices, while particular matrices may yield much faster CG behavior.The cited result also identifies the bound as best possible for algorithms using the function-gradient oracle model.Source: §3 · p. 5
4 Unified algorithm
The section presents a parameterized iterative framework that includes accelerated gradient and linear conjugate gradient as special cases.
4 Unified algorithm
- The framework updates y_k, x_k, and s_k using three sequences of scalar parameters, θ_k, ν_k, and π_k.The displayed updates set y_{k+1}=x_k+θ_ks_k, x_{k+1}=x_k+ν_ks_k−π_k∇f(y_{k+1}), and s_{k+1}=x_{k+1}−x_k.Source: §4 · p. 5
- At initialization, y_1=x_0 and x_1=x_0−π_0∇f(y_1), corresponding to ν_0=θ_0=0.The framework leaves s_0 undefined.Source: §4 · p. 5
- Accelerated gradient is a special case of the unified framework under the parameter identification introduced in the section.The supplied passage does not include the full identification.Source: §4 · p. 5
- Linear conjugate gradient is recovered by setting θ_k=0, so y_{k+1}=x_k, and matching the framework recurrence to the CG recurrence.The section derives the corresponding parameter choice through the recurrences.Source: §4 · pp. 5–6
5 A potential for both algorithms
The section proposes a common potential for accelerated gradient and conjugate gradient and states it as the basis of their unified bound.
5 A potential for both algorithms
- A common potential Ψ_k is proposed for both algorithms, with a bound stated as the main result.The supplied passages identify Ψ_k as the potential at step k but do not provide the bound's full expression.Source: §5 · p. 6
- The potential uses an additional scalar sequence ρ_k, alongside the lower strong-convexity parameter ℓ, upper parameter L, and minimizer x*.The section sets w_0=x_0−x* and hence ρ_0=0.Source: §5 · p. 6
- The approach is described as a variant of Nesterov’s technique, whose potential updates only its second term by a scalar between iterations.The passage says the earlier potential involving these two terms was proposed in.Source: §5 · p. 6
6 Analysis of accelerated gradient
The accelerated-gradient analysis establishes the potential bound by expanding its change, choosing a scalar to cancel a difficult term, and treating the first iteration separately.
6 Analysis of accelerated gradient
- Expanding the potential change yields nine terms, which the proof groups and analyzes using the framework recurrences.The expansion uses the identity (a−b)(c+d)+(a+b)(c−d)=2ac−2bd.Source: §6 · pp. 7–8
- The analysis chooses ξ to cancel a cross term involving (y_{k+1}−x*)^T s_k, which is difficult to bound for accelerated gradient.The choice is ξ²=C.Source: §6 · p. 8
- The proof bounds the gradient-step decrease using smoothness, applying the bound to d=∇f(y_{k+1})/L.It represents the function difference as a line integral and applies the Lipschitz condition.Source: §6 · p. 9
- The initial step is handled separately: Ψ_1≤Ψ_0, and the stronger one-step inequality need not hold there for any C>1.The proof notes that several terms vanish when k=0 and uses convexity for the remaining bound.Source: §6 · p. 10
7 Convergence of conjugate gradient
The section proves a potential bound for conjugate gradient directly from CG identities and establishes a weaker initial-step inequality separately.
7 Convergence of conjugate gradient
- The sequence ρ_k has an optimizer property for the distance from x_k+ρs_k to x*, but the analysis does not use that property directly.The property is attributed to.Source: §7 · p. 11
- The CG proof combines identities for the residual, direction, and step length to derive a bound on the potential change.It substitutes α_{k+1}=∥r_k∥²/(p_{k+1}^T A p_{k+1}) while combining terms.Source: §7 · p. 12
- To establish (21), the proof takes C equal to the right-hand side of the preceding inequality, which includes α_{k+1}∥r_k∥²/ℓ and quantities involving w_{k+1} and F_{k+1}.Source: §7 · p. 13
- For the first iteration, the proof uses Ψ_1≤Ψ_0, bounding the distance and objective terms separately.The distance bound follows from the displayed CG inequalities, and F_1≤F_0.Source: §7 · p. 13
8 Discussion
The paper uses one convergence bound to analyze accelerated gradient and conjugate gradient, while identifying nonlinear and modified CG methods as directions where the analysis may be useful. It also notes that the proposed potential is not directly measurable in practical use.
8 Discussion
- The paper proves the accelerated-gradient convergence result using the same convergence bound for conjugate gradient.The shared analysis is motivated by nonlinear conjugate gradient.Source: §8 · p. 13
- Traditional nonlinear CG lacks a known global complexity bound for strongly convex functions and may perform worse than steepest descent.The authors suggest that a unified analysis could guide a nonlinear CG method that reduces to linear CG on quadratics and retains accelerated gradient’s global bound.Source: §8 · pp. 13–14
- The analysis may apply to modified quadratic CG methods that lose Krylov-space optimality, including methods with noisy matrix-vector products or changing preconditioners.The authors leave this possibility for future work.Source: §8 · p. 14
- A fixed-factor decrease in the potential can help test proposed CG methods for inexactness, but monitoring it requires ℓ, L, and the exact solution.The authors contrast this with other convergence measures that may stagnate for consecutive iterations.Source: §8 · p. 14
- The proposed potential is not directly measurable during practical optimization because it uses the objective gap or distance to the optimizer.The authors identify a potential involving the gradient norm as a useful future development.Source: §8 · p. 14