# Stochastic Anderson Mixing for Nonconvex Stochastic Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 70 references that are in the map.
- First posted on arXiv 4 Oct 2021.

## Builds on (most cited first, 30 of 30)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Aggregated Residual Transformations for Deep Neural Networks](https://mlsanity.com/paper/1611.05431/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Lookahead Optimizer: k steps forward, 1 step back](https://mlsanity.com/paper/1907.08610/) (2019)
- [AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients](https://mlsanity.com/paper/2010.07468/) (2020)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks](https://mlsanity.com/paper/1907.04595/) (2019)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (2014)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)
- [Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/1607.01231/) (2016)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Regularized Nonlinear Acceleration](https://mlsanity.com/paper/1606.04133/) (2016)
- [Anderson Acceleration for Reinforcement Learning](https://mlsanity.com/paper/1809.09501/) (2018)
- [Replica Exchange for Non-Convex Optimization](https://mlsanity.com/paper/2001.08356/) (2020)
- [Anderson Acceleration of Proximal Gradient Methods](https://mlsanity.com/paper/1910.08590/) (2019)
- [Damped Anderson acceleration with restarts and monotonicity control for accelerating EM and EM-like algorithms](https://mlsanity.com/paper/1803.06673/) (2018)
- [Nonlinear Acceleration of Stochastic Algorithms](https://mlsanity.com/paper/1706.07270/) (2017)
- [SPAN: A Stochastic Projected Approximate Newton Method](https://mlsanity.com/paper/2002.03687/) (2020)
- [Nonlinear Acceleration of CNNs](https://mlsanity.com/paper/1806.00370/) (2018)
- [Secant Penalized BFGS: A Noise Robust Quasi-Newton Method Via Penalizing The Secant Condition](https://mlsanity.com/paper/2010.01275/) (2020)

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

- [Beyond L1: Faster and Better Sparse Models with skglm](https://mlsanity.com/paper/2204.07826/) (2022)
- [CoMMIT: Coordinated Multimodal Instruction Tuning](https://mlsanity.com/paper/2407.20454/) (2024)
- [GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration](https://mlsanity.com/paper/2110.02457/) (2021)
- [An Efficient Nonlinear Acceleration method that Exploits Symmetry of the Hessian](https://mlsanity.com/paper/2210.12573/) (2022)
- [Accelerating AI Performance using Anderson Extrapolation on GPUs](https://mlsanity.com/paper/2410.19460/) (2024)
- [FedOSAA: Improving Federated Learning with One-Step Anderson Acceleration](https://mlsanity.com/paper/2503.10961/) (2025)
- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)

## Abstract (arXiv)

Anderson mixing (AM) is an acceleration method for fixed-point iterations. Despite its success and wide usage in scientific computing, the convergence theory of AM remains unclear, and its applications to machine learning problems are not well explored. In this paper, by introducing damped projection and adaptive regularization to classical AM, we propose a Stochastic Anderson Mixing (SAM) scheme to solve nonconvex stochastic optimization problems. Under mild assumptions, we establish the convergence theory of SAM, including the almost sure convergence to stationary points and the worst-case iteration complexity. Moreover, the complexity bound can be improved when randomly choosing an iterate as the output. To further accelerate the convergence, we incorporate a variance reduction technique into the proposed SAM. We also propose a preconditioned mixing strategy for SAM which can empirically achieve faster convergence or better generalization ability. Finally, we apply the SAM method to train various neural networks including the vanilla CNN, ResNets, WideResNet, ResNeXt, DenseNet and RNN. Experimental results on image classification and language model demonstrate the advantages of our method.