Introduction
In convex optimization, first-order methods like gradient descent (GD) are the standard tools for large-scale machine learning and signal processing. However, these methods—and even accelerated variants like Nesterov’s Accelerated Gradient Descent (AGD)—often rely on global, worst-case bounds such as the Lipschitz constant or global strong convexity. In practice, the local geometry near an optimal solution is frequently much more favorable than these global bounds suggest. Standard algorithms, however, do not automatically adapt to this local structure.
Anderson Acceleration (AA) is a classic numerical technique designed to speed up fixed-point iterations by using a history of previous iterates to extrapolate a better next step. While highly effective for smooth, unconstrained problems, AA traditionally struggles with the non-smooth or constrained problems common in modern optimization. This paper introduces a framework to safely and effectively apply AA to Proximal Gradient (PGA) and Bregman Proximal Gradient (BPG) methods.
The Anderson Acceleration Framework
At its core, Anderson Acceleration attempts to find a linear combination of previous iterates that minimizes the residual of a fixed-point mapping. The basic logic is captured in Algorithm 1.
To make this viable for non-smooth composite optimization (e.g., problems with $L_1$ penalties or hard constraints), the authors introduce three key innovations:
- AA-PGA (Anderson Accelerated Proximal Gradient Algorithm): Instead of applying AA to the constrained iterates $x_k$, which could result in infeasible points, the authors apply AA to the unconstrained auxiliary sequence $y_k$ generated before the proximal step. This ensures feasibility while maintaining the benefits of extrapolation.
- Guarded AA: The authors prove that native AA can diverge even on simple 1D strongly convex functions. To ensure global convergence, they introduce a "guard step": if the AA step does not provide sufficient descent compared to a standard proximal gradient step, the algorithm falls back to the safe, standard step.
- AA-BPG (Bregman Proximal Gradient): For non-Euclidean geometries (like Mirror Descent), AA is performed in the dual space using the mirror map, avoiding boundary violations in the primal space.
Key Insights and Theoretical Contributions
A major contribution of this work is the proof that safeguarding is not merely a theoretical formality but a practical necessity. By constructing a specific case where native AA enters a periodic orbit and fails to reach the optimum, the authors justify the "Guarded" approach. This "Best of Both Worlds" strategy provides the ironclad global convergence guarantees of standard proximal methods while allowing for the blazing-fast, parameter-free local acceleration of AA when iterates enter well-behaved regions.
Furthermore, the authors established local convergence for AA-PGA under mild conditions (generalized second-order epi-differentiability) and proved global convergence for the guarded variants.
Empirical Results
The proposed methods were evaluated on several ill-conditioned datasets, including Madelon, Gisette, and Sido0, for tasks like constrained logistic regression and non-negative least squares.
As shown in the figures above, AA-PGA (labeled as AA-GD in these instances) achieves several orders of magnitude speedup in both iteration count and wall-clock time compared to standard and Nesterov-accelerated methods. Crucially, the algorithm consistently achieves fast linear convergence rates in practice, empirically validating its ability to adapt to local strong convexity without manual hyperparameter tuning.
Conclusion and Future Work
This work bridges the gap between classical numerical acceleration and modern non-smooth optimization. By extrapolating in the correct space (auxiliary or dual) and implementing a simple guard step, Anderson Acceleration becomes a robust, highly practical tool for speeding up first-order methods.
Future research directions include closing the theoretical gap for the local convergence of AA-BPG when solutions lie on the domain boundary, and investigating whether AA with finite memory can be proven to have a strictly superior convergence rate than standard proximal gradient methods in a general setting.
Summary updated