Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces 3 new variants of Anderson Mixing methods relying on very limited short term memory. This makes these methods more attractive for usual machine learning workloads.
The paper also provides detailed analysis of the performance of each of these AM algorithms, as well as thorough experiments, showcasing improved performance of select neural network training.
main_review: The paper tackles an ambitious goal, which is to design better optimizers for machine learning workloads than the first order methods which have come to dominate the field. It makes an interesting contribution with several well-motivated new algorithms, establishing convergence proofs and running detailed experiments to check whether the theory matches the practice.
The paper is generally well-written and nice to read, with special care taken to cite appropriate earlier works.

Here are a few outstanding issues, however.
1. The paper is perhaps not as self-contained as one could hope for, and assumes a strong familiarity with many topics: e.g. Anderson Mixing, the properties of first order methods on fixed point problems, preconditioning (which is only made explicit far in the Appendix). It would make the paper more readable and easier to understand to add more context to it.

2. A claim is made that the memory footprint of the algorithms is close to that of GD or SGD, but a more precise theoretical comparison would be helpful. For instance, we see that the memory footprint seems to only increase by 5% over SGD in some experiments, but are bigger than Adam in others which leaves the reader wondering how these seemingly inconsistent results came about.

3. Finally, the biggest issue with the paper is its experimental section. While thorougly reported (which is appreciated), it relies on toyish datasets which make the claims of the paper more difficult to support. Another issue is that the authors chose RNNs for language tasks while transformers have obtained SOTA results for years, and Adam seems to be more critical to good transformer performance than good RNN performance. All told, it seems like the experimental section, while well-executed, misses key points to make it really relevant to the community.

All told, this is a nice paper which clears the bar for publication at ICLR this year, but which could be much improved with a revamped, more ambitious experimental section.

Details
- section 3.4, first paragraph: optimizaiton --> optimization
- fig 1 caption : Probrem --> Problem
- page 34 precondtioner --> preconditioner
summary_of_the_review: Interesting new algorithms, well-motivated, delivered with good theoretical analysis. The experimental section is a bit lacking, but that's not sufficiently concerning not to recommend the paper for publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new class of memory-efficient Anderson mixing (AM) methods. Compared with classical Anderson mixing which requires saving m historical iterates, the new variants require only storing two historical iterates while keeping good performance. Convergence analyses are given to the proposed variants showing a variant for strongly convex quadratic problem enjoys the same guarantee as full-memory AM, and another variant converges with a similar convergence rate as SGD (O(1/\sqrt{number of iterations})) on nonconvex problems. Experiments on MNIST, CIFAR-10, and PENN TREEBANK with some popular deep models validates the superior performance of one of the proposed method.
main_review: I think overall this is a paper with solid theory and experiments. The theoretical and experiments can be separated into two parts, one part is for the basic version of ST-AM designed mostly for nice problems like strongly convex quadratic ones, the other part is for RST-AM designed for neural network training. In my perspective, the first part may not be of too much interest to the audience of ICLR and is more suitable for optimization journals. Yet, the part of the MST-AM algorithm could be of great interest since it is applicable to training deep models. For the weakness, I feel the discussion on improvement of MST-AM over SAM (Wei et al., 2021) could be improved. The paper mentioned MST-AM is motivated by SAM  and talked about which steps are different. It could be better if the authors could provide a discussion on intuitions why MST-AM outperforms SAM in the paper. Also, the content of the paper is quite dense, it might be better to move some less important results into appendix and provide more discussion on intuitions in the main paper.
summary_of_the_review: In summary, I think this is a relatively strong paper due to the technical depth and the empirical studies, though some parts could be improved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces three variants of Anderson acceleration: short-term Anderson mixing (ST-AM), modified short-term Anderson mixing (MST-AM), and regularised short-term Anderson mixing (RST-AM). These may be used to obtain the solution to linear systems, nonlinear systems, and optimisation problems.
main_review: I begin by noting that I am not an expert on the finer details of the theory of (non)linear solvers, so my review is primarily focused on the application side of things.

This appears to be an excellent paper. The quality of the writing is uniformly high throughout. I appreciated the various remarks throughout, used to elucidate the occasional mathematical detail.

My first comment is that I think it would be really beneficial to more explicitly state the delta between this work and previous work. When is it worth the effort to implement the introduced methods as compared to some off-the-shelf competing method? (LU solvers for linear problems; quasi-Newton for nonlinear problems; Adam for supervised learning etc.) For the audience interested in applications, rather than theory, I believe a section describing this would be especially valuable.

I would describe the experiments as still having room to improve. (And I apologise for being "that reviewer" who asks for more experiments, in a paper that already features several.) Numerical methods for the solution of (non)linear systems are applied widely across disparate fields, so in this case I think it is particularly important to check how broadly applicable any new technique is. I would regard the following as being particularly important extra comparisons:

- Section 4.1: how does the proposed method compare to Newton and standard quasi-Newton methods (BFGS, L-BFGS, chord, Levenberg–Marquardt, etc.)? For those problems for which the Jacobian is available -- an increasingly common case following the popularisation of autodifferentiation -- these are still the go-to technique in many/most regimes.
- Section 4.1: the test problems considered are all very simple. What about more complicated test problems? In particular I would be interested in finding the fixed point of "complicated" nonlinear functions (e.g. a neural network, or the system arising from an implicit ODE solver).
  - Focusing on the implicit ODE case: at present this is ubiquitously done via Newton's method or the (quasi-Newton) chord method. (And in particular not via Picard iterations, which can introduce an undesirable loss of stability to the overall numerical method.)
- Training GANs. The choice of optimiser can have a *very* dramatic impact when training GANs: easily making the difference between convergent and divergent training, despite the same change in optimiser having minimal-to-no effect in the supervised learning case. A few examples:
  - [1] consider a case in which GAN training with SGD/Adam fails completely, but training with Adadelta produces stable/convergent results.
  - [2] derive optimisers by solving the gradient flow ODE. [Usually not a great idea in the supervised learning case, but the unreliability of other optimisers in the adversarial case motivates a return to this idea.]
  - [3, 4] consider using negative or complex momentum within the optimiser.
  - [5] consider taking Cesàro means over the parameters being optimised, during training. (This is commonly also done in theoretical studies of optimisers.)

An in addition the following would be nice as extra comparisons, but I think they are less important than those suggested above:

- Section 4.2: MNIST: SAM and RST-AM preconditioned with Adam is noticeably absent.
- Section 4.2: CIFAR: SAM and RST-AM with Adadelta/Adagrad/Adam/RMSprop preconditioners. These seemed to help a lot on MNIST. (Figure 2(c))

## Minor points / typos

Equation (1): I think specifying $X_k \in \mathbb{R}^{m \times d}$, $R_k \in \mathbb{R}^{m \times d}$ would improve readability slightly.

Remark 1: I'd suggest including here that the mixing step is essentially a gradient descent step ($\bar{r}_k$ is some linear combination of $\nabla f(x_j)$; c.f. also the standard condition given by equation (14)).

Top of page 4: both $\bar{x}_k^G$ and $x_k^G$ are used. Neither notation is really defined precisely, but I am guessing that $\bar{x}_k^G$ is meant to be $x_k^G$.

Top of page 4: it is stated that $\bar{x}_k = \bar{x}_k^F = x_k^G$ . This would seem to indicate that the $\bar{x}_k$ iterates of ST-AM compute exactly the same values as AM (with the corollary that the actual output $x_k$ is almost identical), and as such ST-AM is a strict improvement  over AM due to its lower memory requirements. This seems at odds with the rest of the text, which seems to suggest that the use of ST-AM represents a trade-off.

Theorem 2: "constant $\kappa$..." -> "constants $\kappa$..."

Section 3.4, end of second paragraph: $\nabla_{S_k} f(x_k)$ -> $\nabla f_{S_k}(x_k)$.

Equation (14): some space (\qquad) between the equations would be nice.

End of page 8: "less training epochs" -> "fewer training epochs"

Page 9: "less epochs" -> "fewer epochs"

## References

[1] Kidger et al. "Neural SDEs as Infinite-Dimensional GANs" NeurIPS 2021 https://arxiv.org/abs/2105.13493

[2] Qin et al. "Training Generative Adversarial Networks by Solving Ordinary Differential Equations" NeurIPS 2020 https://arxiv.org/abs/2010.15040

[3] Gidel et al. "Negative Momentum for Improved Game Dynamics" AISTATS 2019 https://arxiv.org/abs/1807.04740

[4] Lorraine et al. "Complex Momentum for Optimization in Games" 2021 https://arxiv.org/abs/2102.08431

[5] Yazici et al. "The Unusual Effectiveness of Averaging in GAN Training" ICLR 2019 https://arxiv.org/abs/1806.04498
summary_of_the_review: I recommend acceptance due to the high quality of the paper. My main two concerns are (a) readability wrt applications and (b) experiments across a broader range of regimes.
review_title: null

Meta-review: The reviewers found this work well-motivated and the additional experiments conducted during the response phase were greatly appreciated. Anderson's acceleration appears to be a simple device that may be of great value to this field, and therefore this work is a timely contribution. The presented theoretical results justify the authors' modifications, although at times it felt more comparisons would be welcome: (a) Section 3.2 could have compared to a lot of three-term recurrences that lead to the optimal dependence on the condition number, including Chebyshev's polynomial and conjugate gradient, as well as the results in Brezinski et al. (2018); (b) Section 3.3 would benefit from some comparison with "Evans, Claire, Sara Pollock, Leo G. Rebholz, and Mengying Xiao (2020). “A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)”. SIAM Journal on Numerical Analysis, vol. 58, no. 1, pp. 788–810." (c) the results in Section 3.4 seem to be a bit preliminary and it would be great if the authors could compare to standard rates of SGD. 

Overall we believe this work will generate more interest on memory-based optimization techniques in deep learning, and we encourage the authors to thoroughly polish their draft by incorporating the reviewers' comments and the responses during the discussion phase.
Decision: Accept (Poster)