Stochastic Anderson Mixing for Nonconvex Stochastic Optimization
arXiv:2110.01543
Abstract
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.
arXiv commentAccepted by the 35th Conference on Neural Information Processing Systems (NeurIPS 2021)
References in corpus (11)
- Adam: A Method for Stochastic Optimization
- ADADELTA: An Adaptive Learning Rate Method
- Lookahead Optimizer: k steps forward, 1 step back
- Learning to Optimize
- AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients
- Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
- Anderson Acceleration of Proximal Gradient Methods
- Nonlinear Acceleration of Stochastic Algorithms
- Secant Penalized BFGS: A Noise Robust Quasi-Newton Method Via Penalizing The Secant Condition
- Nonlinear Acceleration of CNNs
- SPAN: A Stochastic Projected Approximate Newton Method