TL;DR
This paper introduces Stochastic Anderson Mixing (SAM), adapting a classic scientific computing acceleration technique for nonconvex stochastic optimization in deep learning. By incorporating damped projection and adaptive regularization, SAM establishes solid convergence guarantees and empirically outperforms standard optimizers like Adam and SGD across various popular neural network architectures.
What Problem Does This Paper Address?
Stochastic optimization is the backbone of modern machine learning, powering everything from simple linear models to massive deep neural networks. While first-order methods like Stochastic Gradient Descent (SGD) and Adam are widely popular, they can struggle with slow convergence or get trapped in poor local extrema. Second-order methods (like quasi-Newton methods) offer faster convergence by estimating curvature, but they are often computationally prohibitive or unstable when exposed to the high noise and nonconvex landscapes typical of machine learning datasets.
The authors look to Anderson Mixing (AM), a well-established sequence acceleration method used in scientific computing (such as quantum chemistry electronic structure calculations) to speed up fixed-point iterations. However, AM has traditionally lacked a clear convergence theory for nonconvex problems, and a naive application to stochastic machine learning fails due to gradient noise and the absence of line-search mechanisms. This paper bridges that gap.
Methods
The authors propose Stochastic Anderson Mixing (SAM) and its practical variant AdaSAM, introducing two fundamental modifications to stabilize the classical algorithm:
- Damped Projection: Classical AM relies on local quadratic approximations that can be highly inaccurate in nonlinear optimization. SAM introduces a damping parameter ($\alpha_k$) to stabilize the intermediate steps and prevent the optimizer from overshooting.
- Adaptive Regularization: To handle rank-deficient or unstable least-squares problems caused by noisy gradients, the authors introduce a data-dependent regularization parameter ($\delta_k$). This parameter dynamically adjusts based on spatial curvature changes and gradient noise, acting similarly to an annealing stepsize.
To further boost performance, the authors present two extensions:
- SAM-VR: Integrates the Stochastic Variance Reduced Gradient (SVRG) technique to explicitly combat stochastic gradient noise.
- Preconditioned SAM (pAdaSAM): Allows SAM to utilize existing optimizers (like Adagrad or RMSprop) as preconditioners, combining the benefits of adaptive learning rates with multisecant acceleration.
Datasets
The authors evaluated their methods on standard machine learning benchmarks:
- MNIST: Used for training a vanilla Convolutional Neural Network (CNN) with large batch sizes to evaluate empirical risk minimization.
- CIFAR-10 & CIFAR-100: Used to train deep residual networks including ResNet (18/20/32/44/56), WideResNet16-4, ResNeXt50, and DenseNet121.
- Penn TreeBank: Used for evaluating language modeling performance using 1, 2, and 3-layer LSTMs.
Key Insights and Ideas
- The Quasi-Newton Connection: The paper highlights that Anderson Mixing is implicitly a multisecant quasi-Newton method. Instead of computing expensive Hessian-vector products, it elegantly uses differences in historical gradients to approximate curvature.
- Noise Tolerance via Regularization: The "aha moment" of AdaSAM is its specific choice of adaptive regularization. By scaling the penalty term based on the ratio of the gradient norm to the step distance, the optimizer automatically behaves cautiously when encountering dramatic landscape changes.
- Erratic Training, Superior Generalization: During the early epochs of training on CIFAR, AdaSAM exhibits somewhat erratic test accuracy curves. However, due to its larger weight decay and unique exploration of the history space, it ultimately stabilizes to achieve superior generalization performance on the test set compared to standard baselines.
Key Results
- MNIST Optimization: As shown in Figure 1, AdaSAM minimizes training loss significantly faster than SGD, Adam, and SdLBFGS. When variance reduction is added (AdaSAM-VR), it drives the training loss down to an impressive $10^{-9}$.
- CIFAR Image Classification: AdaSAM consistently achieved the highest TOP1 test accuracy across almost all tested architectures. Notably, on CIFAR-100 using DenseNet, AdaSAM achieved 80.09% accuracy, outperforming SGDM (78.49%) and Adam (70.80%).
- Language Modeling: On the Penn TreeBank dataset, the preconditioned variant (
pAdaSAM) achieved the lowest test perplexity across 1, 2, and 3-layer LSTMs, demonstrating its versatility beyond computer vision tasks.
Limitations and Future Work
The primary limitation of SAM is its computational and memory overhead. Storing historical iterations requires an extra $2md$ space (where $m$ is the history length and $d$ is the parameter dimension), and solving the internal least-squares problem introduces matrix operations of complexity $O(m^2d) + O(m^3)$ per iteration.
Although the authors demonstrate that this overhead becomes marginal as the mini-batch size increases (since gradient computation time dominates), optimizing these dense matrix operations for highly parallel, high-performance computing environments remains an open area for future enhancement.
Summary updated