Anderson Acceleration Without Restart: A Novel Method with $n$-Step Super Quadratic Convergence Rate
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909149425565696 |
|---|---|
| author | Ye, Haishan Lin, Dachao Chang, Xiangyu Zhang, Zhihua |
| author_facet | Ye, Haishan Lin, Dachao Chang, Xiangyu Zhang, Zhihua |
| contents | In this paper, we propose a novel Anderson's acceleration method to solve nonlinear equations, which does \emph{not} require a restart strategy to achieve numerical stability. We propose the greedy and random versions of our algorithm. Specifically, the greedy version selects the direction to maximize a certain measure of progress for approximating the current Jacobian matrix. In contrast, the random version chooses the random Gaussian vector as the direction to update the approximate Jacobian. Furthermore, our algorithm, including both greedy and random versions, has an $n$-step super quadratic convergence rate, where $n$ is the dimension of the objective problem. For example, the explicit convergence rate of the random version can be presented as $ \norm{\vx_{k+n+1} - \vx_*} / \norm{\vx_k- \vx_*}^2 = \cO\left(\left(1-\frac{1}{n}\right)^{kn}\right)$ for any $k\geq 0$ where $\vx_*$ is the optimum of the objective problem. This kind of convergence rate is new to Anderson's acceleration and quasi-Newton methods. The experiments also validate the fast convergence rate of our algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_16734 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Anderson Acceleration Without Restart: A Novel Method with $n$-Step Super Quadratic Convergence Rate Ye, Haishan Lin, Dachao Chang, Xiangyu Zhang, Zhihua Optimization and Control In this paper, we propose a novel Anderson's acceleration method to solve nonlinear equations, which does \emph{not} require a restart strategy to achieve numerical stability. We propose the greedy and random versions of our algorithm. Specifically, the greedy version selects the direction to maximize a certain measure of progress for approximating the current Jacobian matrix. In contrast, the random version chooses the random Gaussian vector as the direction to update the approximate Jacobian. Furthermore, our algorithm, including both greedy and random versions, has an $n$-step super quadratic convergence rate, where $n$ is the dimension of the objective problem. For example, the explicit convergence rate of the random version can be presented as $ \norm{\vx_{k+n+1} - \vx_*} / \norm{\vx_k- \vx_*}^2 = \cO\left(\left(1-\frac{1}{n}\right)^{kn}\right)$ for any $k\geq 0$ where $\vx_*$ is the optimum of the objective problem. This kind of convergence rate is new to Anderson's acceleration and quasi-Newton methods. The experiments also validate the fast convergence rate of our algorithm. |
| title | Anderson Acceleration Without Restart: A Novel Method with $n$-Step Super Quadratic Convergence Rate |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2403.16734 |