Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The contribution proposes Min-AM, which is the minimum memory variant of Anderson Mixing/acceleration well-known in fixed-point recursions.  
strengths_and_weaknesses: + The main ideas and results are well-organized and presented with clarity.

+ In this reviewer's understanding, the main/novel contribution of this work are contained in Sections 3.2 and 3.3.

+ The Appendix is very detailed and provides the technical support behind the statements in the main text.

+ Fig. 1(d),(e),(f) are illegible due to the lack of correspondence info between the pluses and circles.


questions: + Is it possible to clarify some figures as commented above? In particular, the authors may want to plot the error between the corresponding pairs of eigenvalues to show the results more clearly.

+ What is/are the limitation(s) of the proposed method?
limitations: I did not find any discussion on this.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a new variant of the Anderson mixing algorithm with minimal memory size. 
strengths_and_weaknesses: The theoretical development for the proposed algorithm seems solid, but the numerical improvement seems incremental. 
questions: 1. Page 9, upper panel of Table 1: Compared to ST-AM, the numerical results presented in Table 1 are not  statistically significant (except for the case of VGG16).  It is hard to justify the significance of the method in test accuracy improvement. 

2. Page 9, lower panel of Table 1: It seems that the improvement is marginal for large-scale problems such as CIFAR100. Please comment on how the performance of the algorithm changes with the scale of the problem. 
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this article, the authors introduce a new Anderson mixing method called Min-AM (with restarted and stochastic variants). 
The Min-AM method aims at solving the problem of memory required by other Anderson mixing algorithms in the large-scale setting.
It iteratively approximates the inverse of the Hessian by only storing a vector pair $(p_k, q_k)$ capturing the increment in the iterates and in the residuals at previous step. This is why their algorithm achieves minimal memory: $m=1$. 
The authors provide 
- strong theoretical guarantees concerning the linear-quadratic convergence of the Restarted Min-AM version in Theorem 1
- and convergence guarantees for the stochastic version leading to a $\mathcal{O} (1/ \epsilon^2)$ iteration complexity 

Finally, the authors perform 3 sets of experiments on 
- quadratic strongly convex synthetic problem : to test the performance of the basic Min-AM algorithm versus other methods (first order or quasi-Newton) and the online eigenvalue estimation (with Lanczos algorithm) required to compute the mixing parameter $\beta_k$
- 2 regularized logistic regression problems on real datasets (a9a and madelon) to compare against other methods as before monitor the spectrum evaluation
- 3 image (large scale) datasets CIFAR10/100 and Imagenet on multiple deep architecture to prove the comparable efficiency of Min-AM with SGD with momentum

~~~~~~~
Score updated after rebuttal (see discussion with the authors), new score: 7
strengths_and_weaknesses: Strengths:
- this paper provides a valid solution to the memory problem of AM methods which usually require to store large matrices of previous forward differences between past iterates and residuals
- the authors suggest a method to choosing the mixing parameters $\beta_k$ which are based on spectral knowledge of the Hessian
- The restarted and the stochastic variants of the introduced algorithm come with solid convergences proofs.
- The Min-AM method is clearly extended to the stochastic setting making it a valid candidate for training deep architectures
- Experiments, especially on deep net, are very convincing as they show that Stochastic Min-AM competes with SGD + Momentum to train models on CIFAR10, CIFAR100 and Imagenet.

Weaknesses
- Many hyperparameters: the stochastic version for instance method relies on 4 hyperparameters $\alpha_k, \beta_k, \delta_k^{(1)} and \delta_k^{(2)}$ which is not underlined in the paper. 
- All the experiments are showing iterations/epochs plots and thus omit many computations required for the evaluation of the spectrum of the Hessian, which is very important as this knowledge is at the core of the setting of the mixing parameters and guarantees good convergence whereas SGD + Momentum would not require this knowledge. Clear time plots with initialization time would have been more informative especially when comparing first order and quasi-Newton methods
- There is no step back taken by authors (even in the conclusion) about weakness or limits or their method (neither theoretically nor numerically) 
questions: I'll start with minor comments and typos and then present my questions to the authors:

Minor comments:
- A.1) Notations: I recommend placing real number before vectors in eq (7), that is moving coefficients such as $p_k = \Delta x_{k-1} - \zeta_k p_{k-1}$, same for $q_k$
- A.2) Typo: line 142 "Min-AM and CG are" instead of "is"
- A.3) Algorithm 1: remove "Output: $x \in \mathbb{R}^d$, we don't know what is x and it is redundant with line 21 of the Algorithm 
- A.4) line 164 : I think it's good to give names to these 4 quantities $\mu, L, \hat{\rho}$ and $\hat{\kappa}$, What is $\hat{\kappa}$ ?
- A.5) Assumption 2: what is $f^{\text{low}}$?
- A.6) The end of Assumption 3 is strangely written. Again I suggest removing the $\xi_i$  
- A.7) Assumption 4, line 248: typo: "are" instead of "is"

Moderate importance comments:
- B.1) In the definition of $r_k^2$ there is an $A$ matrix (line 124) which I find strange as it does not appear in eq (10). I tried to redo the computations and I think there is a mistake here
- B.2) Very strange notations for the Empirical Risk Minimization problem formulation: canonical writing is $f(x) = \frac{1}{n} \sum_{i=1}^n f_i$. I don't think the $\xi_i$ notation is useful, it looks like a random variable but it is not the case.
- B.3) Notations: again, use $T$ iterations instead of $N$
- B.4) line 257: what are the possible values of $k$?

Major comments: 
- C.1) Remark 5: I find it unfair to say that NAG requires the knowledge of $\mu$ and $L$ without even mentioning that Min-AM does (through $\theta_k$) and in a more than NAG (as the knowledge of $L$ suffices in practice)
- C.2) line 207: what are $\tilde{\mu}$ and $\tilde{L}$ ?
- C.3) All the plots are in iterations or epochs. Not a single one shows a result in flops or time. Here the compared methods are very different with very different grid-searching schemes and initialization steps. I really wonder what is the performance of Min-AM when the knowledge of the spectrum is not given. I suspect two things: (i) that this initialization computing the spectrum is very costly and (ii) that it is hard to fine-tune the 4 hyperparameters of Stochastic Min-AM
- C.4) There is no explanation, no analysis, no comment of Theorem 4 and 5. The reader directly jumps from one to the other 


Questions:
- D.1) Could you please give an intuition about why $H_k$ defined in eq (10) is a (good ?) estimate of the inverse of the Hessian ?
- D.2) Remark 3, line 147: which kind of equivalence are you referring to when you say "it has no equivalence to the fully-memory methods" ? Is this a mistake ?
- D.3) Why do you use pseudo inverse at line 18 of the Algorithm 1 instead of inverse as these quantities are real numbers ?
- D.4) How is the regularization in eq (21) combined with Min-AM. Is it which the basic Min-AM or the restarted one ?
- D.5) How is it possible to have larger time per epoch and smaller total running time for sMin-AM in multiple case of Table 1(b) ?
- D.6) Appendix: Figure 4 : how is it possible to have a condition number smaller than 1 ? By definition, $L > \mu$, so $L/\mu > 1$ and thus cannot equal $10 ^{-2}$ or $10 ^{-8}$.


limitations: Overall, I am very enthusiastic by the results of the paper, arithmetically and numerically (even though I would like to have more information about practical usage of such methods, especially regarding the initialization and the computation of hyperparameters, sensitivity to them etc)

Yet, I find that the writing and moreover the conference format is degrading the authors' messages. Every result is touched on very quickly (eg the basic and stochastic version of the algorithm are not in the main text, neither the deep comparison with other methods done instead in Appendix A) and thus many explanations are deferred to the appendix (which is ... 33 pages). I would recommend this work to be reorganized and submitted to a journal. 

Note that the paper being to dense, I could not go through many proofs.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present the Min-AM method - an Anderson acceleration technique whose memory is one. The procedure takes advantage of extra projection steps that prevent the loss of some information. The authors show the algorithm's effectiveness by showing its link to conjugate gradient when applied to quadratic functions and its connection with BFGS when looking at the update. Some heuristics are presented to extend the algorithm to nonlinear or stochastic functions, such as restarts, regularization, or adaptive step size.
strengths_and_weaknesses: The paper tackles a critical problem of the Anderson Acceleration technique: the memory required to perform an acceleration step. In particular, when solving large-scale optimization problems in a resource-limited machine, the memory requirement may be the bottleneck. The small memory also enables a better analysis of the rate of convergence of the algorithm - as in min-AM, we only have one stored vector rather than a matrix.

From a technical point of view, the paper is solid. It proposes a novel method, makes a connection with classical algorithms, and shows rates of convergence. Moreover, the assumptions made in this paper are rather classical and nonrestrictive.

I have more concerns about the clarity of the paper. 
I think some parts could have been improved, especially section 3.1. The section is very dense, and the algorithm's derivation is unintuitive. I suggest the authors spend more time introducing the notations and explaining the purpose of all those modifications (why do 8a, 8b, and 8c help to incorporate more historical information?).
Moreover, the proofs in the appendix are also quite dense. I suggest the author split the big theorem into smaller chunks of lemma to help the reader understand the proofs.

questions: I have a few questions concerning the results and conclusion of this paper.
1) After looking at the algorithm and the Conjugate Residual method, it seems there is a connection between those schemes. I wanted to have the authors' opinion about that.
2) In the analysis of the rate of convergence of Theorem 2, you claim that the bound (13) improves on GD. I believe this may not always be the case as a) we do not know how far m_k can go, b) the constant sqrt(L/mu) is larger than one, and c) there is the quadratic factor?
limitations: See Strengths and weaknesses.
review_title: null

Meta-review: metareview: All reviewers were positive about this paper and the overall impression is very good - accept.
confidence: Certain
Decision: Accept