# Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations

arXiv: https://arxiv.org/abs/1808.03971 · HTML: https://mlsanity.com/paper/1808.03971/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2018.

## Built on by (most cited first, 25 of 25)

- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [Joint inference and input optimization in equilibrium networks](https://mlsanity.com/paper/2111.13236/) (2021)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Neural Fixed-Point Acceleration for Convex Optimization](https://mlsanity.com/paper/2107.10254/) (2021)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)
- [Coordinate Descent for SLOPE](https://mlsanity.com/paper/2210.14780/) (2022)
- [From Optimization to Control: Quasi Policy Iteration](https://mlsanity.com/paper/2311.11166/) (2023)
- [Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Study](https://mlsanity.com/paper/2410.11279/) (2024)
- [Rank-One Modified Value Iteration](https://mlsanity.com/paper/2505.01828/) (2025)
- [An Adaptive State Aggregation Algorithm for Markov Decision Processes](https://mlsanity.com/paper/2107.11053/) (2021)
- [An Operator Splitting View of Federated Learning](https://mlsanity.com/paper/2108.05974/) (2021)
- [Weighted Low-Rank Matrix Approximation: Acceleration and Applications](https://mlsanity.com/paper/2109.11057/) (2021)
- [Enhancing Electrical Impedance Tomography reconstruction using Learned Half-Quadratic Splitting Networks with Anderson Acceleration](https://mlsanity.com/paper/2304.14491/) (2023)
- [OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regression](https://mlsanity.com/paper/2105.13271/) (2021)
- [An information-matching approach to optimal experimental design and active learning](https://mlsanity.com/paper/2411.02740/) (2024)
- [Sparse Partial Optimal Transport via Quadratic Regularization](https://mlsanity.com/paper/2508.08476/) (2025)
- [An Efficient Nonlinear Acceleration method that Exploits Symmetry of the Hessian](https://mlsanity.com/paper/2210.12573/) (2022)
- [Improved Convergence Factor of Windowed Anderson Acceleration for Symmetric Fixed-Point Iterations](https://mlsanity.com/paper/2311.02490/) (2023)
- [Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting](https://mlsanity.com/paper/2403.01919/) (2024)
- [Anderson acceleration for iteratively reweighted ℓ1 algorithm](https://mlsanity.com/paper/2403.07271/) (2024)
- [Online multidimensional dictionary learning](https://mlsanity.com/paper/2503.09337/) (2025)
- [Efficient Solvers for SLOPE in R, Python, Julia, and C++](https://mlsanity.com/paper/2511.02430/) (2025)
- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)

## Abstract (arXiv)

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.