| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
07 February 2025 |
|
| | | |
|
Article overview
| |
|
A unified convergence bound for conjugate gradient and accelerated gradient | Sahar Karimi
; Stephen A. Vavasis
; | Date: |
2 May 2016 | Abstract: | 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
$epsin(0,1)$ after $kge 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. | Source: | arXiv, 1605.0320 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|