Stabilizing anderson mixing for accelerated optimization
Abstract/Contents
- Abstract
- The acceleration of existing algorithms has been a continual effort in the field of optimization, in which Nesterov's acceleration and (quasi-)Newton methods are two of the most representative examples. However, Nesterov's acceleration is specific to gradient methods. And while (quasi-)Newton methods have been commonly adopted to accelerate general iterative algorithms by viewing them as fixed-point iterations, they are typically memory consuming and require sophisticated and potentially expensive line-search procedures. To design widely applicable schemes for black-box, memory-efficient and line-search free acceleration, we resort to Anderson acceleration (AA), which dates back to the 1960s. AA belongs to the family of sequence acceleration methods, which achieve faster convergence through certain sequence transformations. Despite its elegance in implementation, popularity in chemistry and physics, and success in specific optimization problems, a systematic treatment of AA in optimization-related applications was lacking. In addition, although AA has been demonstrated to work well on a wide spectrum of (unaccelerated) algorithms with a small memory (typically 5--10) and essentially no line search in many cases, it also suffers from severe instability issues in general. Moreover, on the theory side, the global convergence theory was missing for AA. This dissertation fills the aforementioned gaps by taking a unified view of AA as either an extrapolation method or a generalized quasi-Newton method, and showing that unlike classical quasi-Newton methods, it is effective without a line search and requires less computation and memory per iteration so long as certain stabilization measures are adopted. Our discussions cover both convex and nonconvex settings, as well as both solvable and pathological scenarios.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Zhang, Junzi |
|---|---|
| Degree supervisor | Boyd, Stephen A |
| Thesis advisor | Boyd, Stephen A |
| Thesis advisor | Kochenderfer, Mykel J, 1980- |
| Thesis advisor | Saunders, Michael |
| Degree committee member | Kochenderfer, Mykel J, 1980- |
| Degree committee member | Saunders, Michael |
| Associated with | Stanford University, Department of Computational and Mathematical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Junzi Zhang. |
|---|---|
| Note | Submitted to the Department of Computational and Mathematical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/yw770rs8270 |
Access conditions
- Copyright
- © 2021 by Junzi Zhang
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...