Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912073151152128 |
|---|---|
| author | Li, Kexin Bai, Luwei Wang, Xiao Wang, Hao |
| author_facet | Li, Kexin Bai, Luwei Wang, Xiao Wang, Hao |
| contents | Anderson acceleration is an effective technique for enhancing the efficiency of fixed-point iterations; however, analyzing its convergence in nonsmooth settings presents significant challenges. In this paper, we investigate a class of nonsmooth optimization algorithms characterized by the active manifold identification property. This class includes a diverse array of methods such as the proximal point method, proximal gradient method, proximal linear method, proximal coordinate descent method, Douglas-Rachford splitting (or the alternating direction method of multipliers), and the iteratively reweighted $\ell_1$ method, among others. Under the assumption that the optimization problem possesses an active manifold at a stationary point, we establish a local R-linear convergence rate for the Anderson-accelerated algorithm. Our extensive numerical experiments further highlight the robust performance of the proposed Anderson-accelerated methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09420 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification Li, Kexin Bai, Luwei Wang, Xiao Wang, Hao Optimization and Control Machine Learning Numerical Analysis Anderson acceleration is an effective technique for enhancing the efficiency of fixed-point iterations; however, analyzing its convergence in nonsmooth settings presents significant challenges. In this paper, we investigate a class of nonsmooth optimization algorithms characterized by the active manifold identification property. This class includes a diverse array of methods such as the proximal point method, proximal gradient method, proximal linear method, proximal coordinate descent method, Douglas-Rachford splitting (or the alternating direction method of multipliers), and the iteratively reweighted $\ell_1$ method, among others. Under the assumption that the optimization problem possesses an active manifold at a stationary point, we establish a local R-linear convergence rate for the Anderson-accelerated algorithm. Our extensive numerical experiments further highlight the robust performance of the proposed Anderson-accelerated methods. |
| title | Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification |
| topic | Optimization and Control Machine Learning Numerical Analysis |
| url | https://arxiv.org/abs/2410.09420 |