Improved Convergence Factor of Windowed Anderson Acceleration for Symmetric Fixed-Point Iterations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911084930138112 |
|---|---|
| author | Garner, Casey Lerman, Gilad Zhang, Teng |
| author_facet | Garner, Casey Lerman, Gilad Zhang, Teng |
| contents | This paper studies the commonly utilized windowed Anderson acceleration (AA) algorithm for fixed-point methods, $x^{(k+1)}=q(x^{(k)})$. It provides the first proof that when the operator $q$ is linear and symmetric the windowed AA, which uses a sliding window of prior iterates, improves the root-linear convergence factor over the fixed-point iterations. When $q$ is nonlinear, yet has a symmetric Jacobian at a fixed point, a slightly modified AA algorithm is proved to have an analogous root-linear convergence factor improvement over fixed-point iterations. Simulations verify our observations. Furthermore, experiments with different data models demonstrate AA is significantly superior to the standard fixed-point methods for Tyler's M-estimation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_02490 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved Convergence Factor of Windowed Anderson Acceleration for Symmetric Fixed-Point Iterations Garner, Casey Lerman, Gilad Zhang, Teng Numerical Analysis Optimization and Control Machine Learning 65F10, 65H10, 68W40 This paper studies the commonly utilized windowed Anderson acceleration (AA) algorithm for fixed-point methods, $x^{(k+1)}=q(x^{(k)})$. It provides the first proof that when the operator $q$ is linear and symmetric the windowed AA, which uses a sliding window of prior iterates, improves the root-linear convergence factor over the fixed-point iterations. When $q$ is nonlinear, yet has a symmetric Jacobian at a fixed point, a slightly modified AA algorithm is proved to have an analogous root-linear convergence factor improvement over fixed-point iterations. Simulations verify our observations. Furthermore, experiments with different data models demonstrate AA is significantly superior to the standard fixed-point methods for Tyler's M-estimation. |
| title | Improved Convergence Factor of Windowed Anderson Acceleration for Symmetric Fixed-Point Iterations |
| topic | Numerical Analysis Optimization and Control Machine Learning 65F10, 65H10, 68W40 |
| url | https://arxiv.org/abs/2311.02490 |