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.

提出了一种基于 Anderson 加速的 IRL1 算法，并建立了其局部线性收敛速度，扩展了该收敛结果到非光滑情况。为了确保全局收敛性，引入了经典的非单调线搜索条件，实验结果表明该算法优于现有的基于 Nesterov 加速的算法。