Anderson acceleration for iteratively reweighted $\ell_1$ algorithm

2024-03-12 · Kexin Li

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.

📄 PDF Abstract BibTeX arXiv:2403.07271

Code (0)

등록된 구현이 없습니다.

Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification

2024-10-12 · Kexin Li, Luwei Bai, Xiao Wang, Hao Wang

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 investig…

A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization

2018-09-07 · Zhize Li, Jian Li

Anderson acceleration (or Anderson mixing) is an efficient acceleration method for fixed point iterations $x_{t+1}=G(x_t)$, e.g., gradient descent can be viewed as iteratively applying the operation $G(x) \triangleq x-\a…

subspace methods

Anderson Acceleration of Proximal Gradient Methods

2019-10-18 · ICML 2020 1 · Vien V. Mai, Mikael Johansson

Anderson acceleration is a well-established and simple technique for speeding up fixed-point computations with countless applications. Previous studies of Anderson acceleration in optimization have only been able to prov…

Accelerated Value Iteration via Anderson Mixing

2018-09-27 · YuJun Li, Chengzhuo Ni, Guangzeng Xie, Wenhao Yang 외

Acceleration for reinforcement learning methods is an important and challenging theme. We introduce the Anderson acceleration technique into the value iteration, developing an accelerated value iteration algorithm that w…

Atari Games Q-Learning reinforcement-learning Reinforcement Learning (RL)

Damped Anderson Mixing for Deep Reinforcement Learning: Acceleration, Convergence, and Stabilization

2021-10-17 · NeurIPS 2021 12 · Ke Sun, Yafei Wang, Yi Liu, Yingnan Zhao 외

Anderson mixing has been heuristically applied to reinforcement learning (RL) algorithms for accelerating convergence and improving the sampling efficiency of deep RL. Despite its heuristic improvement of convergence, a …

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)