Abstract
We consider the application of the type-I Anderson acceleration to solving general non-smooth fixed-point problems. By interleaving with safe-guarding steps, and employing a Powell-type regularization and a re-start checking for strong linear independence of the updates, we propose the first globally convergent variant of Anderson acceleration assuming only that the fixed-point iteration is non-expansive. We show by extensive numerical experiments that many first order algorithms can be improved, especially in their terminal convergence, with the proposed algorithm. Our proposed method of acceleration is being implemented in SCS 2.0, one of the default solvers used in the convex optimization parser-solver CVXPY 1.0.
Introduction
Many problems in science and engineering—from training machine learning models to solving Nash equilibria—can be framed as finding a fixed point: $x = f(x)$. While simple iterative methods like the Krasnosel’skiĭ-Mann (KM) iteration are guaranteed to work, they are often agonizingly slow.
Anderson Acceleration (AA) is a popular technique used to speed up these iterations by using a "memory" of past steps to find a better update. However, traditional AA has two major flaws:
- Instability: It can easily "blow up" or get stuck if the underlying function isn't smooth (differentiable).
- Lack of Theory: Most convergence proofs for AA require the function to be continuously differentiable, which excludes many modern optimization tools like projections or proximal operators.
This paper bridges this gap by creating a version of AA that is both mathematically guaranteed to converge and practically faster for non-smooth problems.
The Anderson Acceleration Framework
The standard Anderson Acceleration prototype uses a history of previous iterates to compute a more informed update than a simple fixed-point step.
As shown in Algorithm 1, the method selects weights based on the last $m_k$ iterations. While effective as a heuristic, this prototype lacks global convergence guarantees for non-smooth mappings, which are common in modern optimization.
Proposed Methodology: AA-I-S-m
The authors propose a stabilized algorithm called AA-I-S-m. It builds on Type-I Anderson Acceleration (related to the "good" Broyden quasi-Newton method) and adds three critical components:
- Powell-type Regularization: This prevents the approximate Jacobian matrix from becoming singular (uninvertible), a common cause of numerical instability in standard AA.
- Restart Checking: The algorithm monitors the "linear independence" of past updates. If the updates become too similar (suggesting stagnation), it clears its memory and restarts to ensure it doesn't get stuck.
- Safeguarding Steps: This is the "safety net." The algorithm checks if the residual norm is decreasing fast enough. If an acceleration step fails to meet a specific threshold, the algorithm falls back to a standard, reliable KM step.
Crucially, this hybrid approach is globally convergent for any non-expansive mapping, meaning it will eventually find the solution regardless of the starting point.
Key Results and Insights
The algorithm was evaluated across a wide variety of synthetic and real-world problem instances, including the UCI Madelon dataset for logistic regression and Markov Decision Processes.
- Massive Speedups: In experiments like regularized logistic regression, the stabilized AA-I-S-m achieved a 100x to 1000x improvement in residual norms compared to standard gradient descent.
- Terminal Convergence: While first-order methods are great at getting near a solution, they struggle to pin it down precisely. This accelerated method shines in that "final mile," reaching high accuracy orders of magnitude faster than vanilla methods.
- Robustness: In cases where the original AA-I completely failed, the stabilized version remained stable and outperformed the vanilla algorithm.
- Practical Integration: The method is so effective that it has been implemented in SCS 2.0, a core solver behind the widely-used optimization parser CVXPY 1.0.
Conclusion
This work provides the first globally convergent variant of Type-I Anderson Acceleration for non-smooth problems. By acting like a high-performance acceleration method when the path is clear and switching to a rugged safeguarding step when necessary, the algorithm offers the best of both worlds. Future research will explore theoretical convergence rates for non-smooth cases and extensions to stochastic settings like deep learning.
Summary updated