A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization

Zhize Li, Jian LiAISTATS 2020 · OpenReview

Abstract

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-\alpha \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(\sqrt{\kappa}\ln\frac{1}{\epsilon})$, which improves the previous result $O(\kappa\ln\frac{1}{\epsilon})$ provided by (Toth & 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.

Introduction

Optimization is a cornerstone of modern machine learning, with Gradient Descent (GD) serving as the primary tool for minimizing objective functions $f(x)$. However, GD often suffers from slow convergence in ill-conditioned problems. While Nesterov’s Accelerated GD (NAGD) offers improvements, Anderson acceleration—a technique dating back to 1965—has emerged as a powerful alternative. Anderson acceleration utilizes a history of previous iterations to extrapolate a more accurate next step. Despite its empirical success, theoretical guarantees for its optimal convergence on quadratic problems and its robustness for general nonlinear functions have remained elusive. This paper introduces Anderson-Chebyshev Acceleration (AA-Cheby), bridging this gap by integrating Chebyshev polynomials into the Anderson framework.

Methodology

The proposed approach consists of two primary innovations:

  1. Anderson-Chebyshev Acceleration (AA-Cheby): Standard Anderson acceleration solves a least-squares problem to determine mixing parameters for previous iterations. AA-Cheby refines this by selecting mixing parameters ($\beta_t$) based on Chebyshev polynomials. This mathematical choice effectively dampens errors across the function's eigenvalue spectrum, enabling the algorithm to reach the theoretically optimal convergence rate of $O(\sqrt{\kappa} \ln \frac{1}{\epsilon})$ for quadratic problems.
  2. The Guessing Algorithm: Practical optimization often requires knowledge of hyperparameters like the Lipschitz constant ($L$) and strong convexity parameter ($\mu$), which are typically unknown. The authors propose a dynamic "doubling" strategy to guess these parameters on-the-fly.
The guessing algorithm dynamically estimates hyperparameters, maintaining rapid convergence even when parameters are unknown.

Experimental Evaluation

The authors evaluated AA-Cheby against several benchmarks, including vanilla GD, NAGD, and Regularized Minimal Polynomial Extrapolation (RMPE). Testing was conducted on:

  • Synthetic Datasets: Quadratic functions with varying condition numbers ($\kappa$).
  • Real-World UCI Datasets: Logistic regression tasks using the "Diabetes" and "Cancer" datasets.

Key Results and Insights

Experimental results confirm that AA-Cheby significantly outperforms standard first-order methods. For quadratic problems, the method achieves the optimal speed limit. For general nonlinear functions, it exhibits "linear-quadratic" convergence, capturing some benefits of second-order methods without the high computational cost of Hessian calculations.

AA-Cheby demonstrates superior convergence speed compared to GD, NAGD, and RMPE on real-world datasets.

The method is also highly efficient in terms of memory, performing well with a small window of only 3 to 5 previous iterations. Furthermore, the "Guessing Algorithm" ensures that AA-Cheby remains effective even when problem parameters are not precisely known beforehand.

Conclusion

Anderson-Chebyshev Acceleration provides a robust and theoretically grounded method for speeding up nonlinear optimization. While currently focused on deterministic settings, its superior performance on ill-conditioned problems makes it a valuable tool. Future work may involve extending these optimal bounds to stochastic gradient settings and refining rules for selecting the memory parameter $m$.

Summary updated

Abstract

emph{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-\alphaabla 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(\sqrt{\kappa}\ln\frac{1}{\epsilon})$, which improves the previous result $O(\kappa\ln\frac{1}{\epsilon})$ provided by (Toth & 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 \emph{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.
BibTeX
@inproceedings{li2020fast,
  author = {Zhize Li and Jian Li},
  title = {{A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=zMg2wFBcma3},
}
Figure