Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations
arXiv:1808.03971
Abstract
We consider the application of the type-I Anderson acceleration to solving general non-smooth fixed-point problems. By interleaving with safe-guarding steps, and employing a Powell-type regularization and a re-start checking for strong linear independence of the updates, we propose the first globally convergent variant of Anderson acceleration assuming only that the fixed-point iteration is non-expansive. We show by extensive numerical experiments that many first order algorithms can be improved, especially in their terminal convergence, with the proposed algorithm. Our proposed method of acceleration is being implemented in SCS 2.0, one of the default solvers used in the convex optimization parser-solver CVXPY 1.0.
arXiv comment47 pages
References in corpus (5)
- Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
- Nonlinear Acceleration of Stochastic Algorithms
- AA-ICP: Iterative Closest Point with Anderson Acceleration
- A Semismooth Newton Method for Fast, Generic Convex Programming
- Fast K-Means Clustering with Anderson Acceleration
Cited by in corpus (13)
- An accelerated staggered scheme for phase-field modeling of brittle fracture
- Anderson Accelerated Douglas-Rachford Splitting
- Geometry of First-Order Methods and Adaptive Acceleration
- First-Order Methods for Wasserstein Distributionally Robust MDP
- Fast and Stable Nonconvex Constrained Distributed Optimization: The ELLADA Algorithm
- Consistency and Computation of Regularized MLEs for Multivariate Hawkes Processes
- Safeguarded Learned Convex Optimization
- Rapid Convergence of First-Order Numerical Algorithms via Adaptive Conditioning
- Nonmonotone Globalization for Anderson Acceleration via Adaptive Regularization
- A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization
- Anderson acceleration of coordinate descent
- Anderson Acceleration for Seismic Inversion
- Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates