# A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2018.

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

- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.04755/) (2021)
- [Acceleration via Fractal Learning Rate Schedules](https://mlsanity.com/paper/2103.01338/) (2021)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration](https://mlsanity.com/paper/2410.07272/) (2024)

## Abstract (arXiv)

Anderson acceleration (or Anderson mixing) is an efficient acceleration method for fixed point iterations xt+1=G(xt), e.g., gradient descent can be viewed as iteratively applying the operation G(x) triangleq x-αnabla f(x). It is known that Anderson acceleration is quite efficient in practice and can be viewed as an extension of Krylov subspace methods for nonlinear problems. In this paper, we show that Anderson acceleration with Chebyshev polynomial can achieve the optimal convergence rate O(√kappalnfrac1ε), which improves the previous result O(kappalnfrac1ε) provided by (Toth and Kelley, 2015) for quadratic functions. Moreover, we provide a convergence analysis for minimizing general nonlinear problems. Besides, if the hyperparameters (e.g., the Lipschitz smooth parameter L) are not available, we propose a guessing algorithm for guessing them dynamically and also prove a similar convergence rate. Finally, the experimental results demonstrate that the proposed Anderson-Chebyshev acceleration method converges significantly faster than other algorithms, e.g., vanilla gradient descent (GD), Nesterov's Accelerated GD. Also, these algorithms combined with the proposed guessing algorithm (guessing the hyperparameters dynamically) achieve much better performance.