Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification
This work addresses convergence issues in nonsmooth optimization for researchers and practitioners, but it is incremental as it extends existing theory to a broader class of methods.
The paper tackles the challenge of analyzing Anderson acceleration's convergence in nonsmooth optimization problems by focusing on algorithms with active manifold identification, establishing a local R-linear convergence rate under certain assumptions.
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.