返回Google圖書搜尋

Stabilizing Anderson Mixing for Accelerated Optimization

出版	Stanford University, 2021
URL	http://books.google.com.hk/books?id=I35fzgEACAAJ&hl=&source=gbs_api

註釋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.