# Anderson acceleration for iteratively reweighted ℓ1 algorithm

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 50 references that are in the map.
- First posted on arXiv 12 Mar 2024.

## Builds on (most cited first, 16 of 16)

- [Group Sparse Regularization for Deep Neural Networks](https://mlsanity.com/paper/1607.00485/) (2016)
- [A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems](https://mlsanity.com/paper/1303.4434/) (2013)
- [Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations](https://mlsanity.com/paper/1808.03971/) (2018)
- [Regularized Nonlinear Acceleration](https://mlsanity.com/paper/1606.04133/) (2016)
- [A proximal difference-of-convex algorithm with extrapolation](https://mlsanity.com/paper/1612.06265/) (2016)
- [Nonconvex and Nonsmooth Sparse Optimization via Adaptively Iterative Reweighted Methods](https://mlsanity.com/paper/1810.10167/) (2018)
- [Anderson Acceleration of Proximal Gradient Methods](https://mlsanity.com/paper/1910.08590/) (2019)
- [Anderson Accelerated Douglas-Rachford Splitting](https://mlsanity.com/paper/1908.11482/) (2019)
- [Trajectory of Alternating Direction Method of Multipliers and Adaptive Acceleration](https://mlsanity.com/paper/1906.10114/) (2019)
- [An Extrapolated Iteratively Reweighted l1 Method with Complexity Analysis](https://mlsanity.com/paper/2101.03763/) (2021)
- [Towards An Efficient Approach for the Nonconvex ℓp Ball Projection: Algorithm and Analysis](https://mlsanity.com/paper/2101.01350/) (2021)
- [Nonlinear Acceleration of Stochastic Algorithms](https://mlsanity.com/paper/1706.07270/) (2017)
- [Anderson Acceleration for Nonsmooth Fixed Point Problems](https://mlsanity.com/paper/2209.10336/) (2022)
- [Iteratively reweighted ℓ1 algorithms with extrapolation](https://mlsanity.com/paper/1710.07886/) (2017)
- [Proximal Iteratively Reweighted Algorithm with Multiple Splitting for Nonconvex Sparsity Optimization](https://mlsanity.com/paper/1404.6871/) (2014)
- [A subgradient method with non-monotone line search](https://mlsanity.com/paper/2204.10009/) (2022)

## Abstract (arXiv)

Iteratively reweighted L1 (IRL1) algorithm is a common algorithm for solving sparse optimization problems with nonconvex and nonsmooth regularization. The development of its acceleration algorithm, often employing Nesterov acceleration, has sparked significant interest. Nevertheless, the convergence and complexity analysis of these acceleration algorithms consistently poses substantial challenges. Recently, Anderson acceleration has gained prominence owing to its exceptional performance for speeding up fixed-point iteration, with numerous recent studies applying it to gradient-based algorithms. Motivated by the powerful impact of Anderson acceleration, we propose an Anderson-accelerated IRL1 algorithm and establish its local linear convergence rate. We extend this convergence result, typically observed in smooth settings, to a nonsmooth scenario. Importantly, our theoretical results do not depend on the Kurdyka-Lojasiewicz condition, a necessary condition in existing Nesterov acceleration-based algorithms. Furthermore, to ensure global convergence, we introduce a globally convergent Anderson accelerated IRL1 algorithm by incorporating a classical nonmonotone line search condition. Experimental results indicate that our algorithm outperforms existing Nesterov acceleration-based algorithms.