Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a stochastic Anderson mixing (SAM) scheme and its variance reduction version to solve nonconvex stochastic optimization problems. Extensive experiments are conducted to verify the efficacy of the proposed methods. 
main_review: The paper provides promising results and the idea of using damped projection combined with adaptive regularization is new. I'm impressed with the experiments. 

1. Provide the (approximate) formula of $M_f$ in (20). This constant is important to visualize the rate of $1/N \sum E || \nabla f(x_k) ||^2$, see (23).

2. How is the batch size $n_k$ in Theorem 4 estimated (see line 205) when $\sigma$ in Assumption 2 is not easy to determine? 

3. Is the batch size in the experiments chosen following the theory? 
limitations_and_societal_impact: N.A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a variant of Anderson mixing applied to a stochastic optimization problem. Convergence analysis is carried out and experiments show good results.
main_review: The proposed method relies on damping and regularization. These techniques are very common in Anderson mixing (AM) methods due to the potential divergence of AM and the numerical instability when solving its subproblems. 

In this paper, the positive definiteness of a matrix, acting like an approximate Hessian, is checked at every step. This allows the author(s) to obtain convergence guarantees, which are otherwise impossible for AM. The damping condition enforces the method to stay close to a stochastic descent method; when alpha_k is small (to satisfy condition (15)), we essentially take an SGD step. 

My concerns are that:

(i) since the stepsize beta is very small and is often reduced further as the algorithm proceeds, condition (15) enforces that alpha should tend to zero too. So, effectively we are just running SGD most of the time. It would be interesting to profile and see how often the Anderson step are performed compared to SGD.

(ii) the rate does not show the benefit over SGD type methods that require much less memory footprint. I am not concerning the extra computations as they are just some matrix-matrix multiplications and GPUs are super efficient at this. However, the memory footprint is extremely important when it comes to training large models on GPUs. GPU's memory is very small compared to CPUs, and a single model would contain millions if not billions of parameters. The ADM method stores two extra matrices that would need 2*m times the memory required to store one model, which would be otherwise used to increase the mini-batch size and hence reduce the runtime.

Some other comments:

In Algorithm 1, it is stated that beta_k = alpha_k = 1, but the conditions on Theorem 1, 2, 3 require beta_k -> 0. I believe it shoud be beta_0 = 1??

Theorem 2 needs smoothness and boundedness of f + bounded variance and second moment of the gradients, which seems not very standard.
limitations_and_societal_impact: See above
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: In this manuscript, the authors proposes a Stochastic Anderson Mixing (SAM) scheme to solve nonconvex optimization problems. Under the smoothness, unbiased gradient estimate with bounded variance assumptions, the authors show different variants of the scheme (SAM, SAM with variance reduction, Ada-SAM) have asymptotic and non-asymptotic convergence. Experiments on MNIST, CIFAR and Penn Treebank seem to show the superior performance over other baselines. 
main_review: Originality: 
To the best my knowledge, the nonconvex Anderson mixing for nonconvex optimization does not appear in the previous literature.

Clarity:
The paper clearly states its contributions. I would also suggest the authors to create a table to compare the SAM-based approach with existing approaches in stochastic nonconvex optimization.

Significance:
This is my concern about this paper. 

1. The motivation of this paper is vague. What are the limitations of SGD and SVRG for nonconvex optimization that make Anderson-Mixing approach important?

2. In my view, the SAM method (Algorithm 1) is worse than nonconvex SGD from every aspect. First, the convergence of nonconvex SGD does not require a large minibatch but it is required for SAM (Theorem 4). Second, Although SAM has the same iteration complexity compared with SGD, SAM has higher per-iteration time complexity (line 9 and line 10) and more memory (line 7 and line 8). I also doubt that it works better than SGD if the authors report running time in the experiments section (in section 4, only the loss versus epochs results are reported).

3. For Algorithm 2 (SAM-VR), it basically mimics the result of [Reddi et al. 2016], but again, the per-iteration complexity is still worse than nonconvex SVRG, since SAM-VR calls SAM as a subroutine. Also the number of SFO calls should be $O(T+T^{2/3}/\epsilon)$ in Theorem 5.

4. In section 3.2, it is important to have a formal theorem describing the convergence of AdaSAM. The current description of this section is vague and I am not sure if it is correct.

Experiments:

1. As I mentioned, since SAM-based approach has high per-iteration complexity and requires more memory, I would suggest the authors to report the running time comparison. 

2. Only training loss results are reported. I understand the theory is only for the training loss, but test loss is also important for practitioners.

3. In Figure 1, only large batch size experiments are reported. I understand that the goal is to make it somehow consistent with the large batch requirement in the theory. However, it is known that large batch ends up with worse generalization in machine learning. What is the performance of this algorithm if small batch size is used?

4. In Figure 1(c), why AdaSAM-VR is used? What about the performance of SAM-VR? 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The main idea of this paper is to introduce a stochastic Anderson mixing method which leads to faster convergence, accelerating the training. The main contribution of the paper is the convergence analysis part which gives the theoretical analysis of the proposed method. 
main_review: Slow convergence is a notable and annoying problem during training, especially when training some nets with high complexity, such as GAN. The idea of using Anderson acceleration to improve the performance of the optimisation method is not novel, but I’m still impressed by the good performance of the AdaSAM. Actually, the core algorithm, using the damped projection and the adaptive regularisation, are not innovative enough. However, the convergence analysis and the abundant experiments shown the effectiveness of SAM, which gives me confidence.
Here are some questions that I had during the reading:
Line 41 - Why SAM is a second-order method? 
The convergence analysis based on the assumption that f is continuously differentiable. Is it a realistic assumption? 
Line 86 Remark 1 - The fixed point assumption is necessary actually, promising the equation in line 87 holds when j,k->\infinity.
Line 184 - Why the eq. 19 promises the convergence of the original problem? Is it possible to be stucked in a local minimal?
Figure 2: What is the training loss goes like when compared with Lookahead on CIFAR? 
Figure 7 in appendix: It seems that the training loss of AdaSAM fell behind that of SGDM, does it means that AdaSAM cannot saving training time in some cases?
It seems that the cases shown here only needs hundreds epochs to converge. How well does the SAM perform in the more time-consuming cases?
limitations_and_societal_impact: The author(s) could extend the limitation part. Are there any situations where the convergence speed of SAM lags behind SGD? Could you please provide some specific analysis? So that readers can understand when to switch to SAM after reading.
review_title: null

Meta-review: The direction is novel and interesting, the analysis of a stochastic version of AM could be independently interesting. Even though the practical aspects are not the strongest, I recommend acceptance; in my opinion the results are of interest to the community.

The authors did generally a good job responding to reviewers questions resulting to one reviewer raising their score. 

There are legitimate arguments by one reviewer saying that there are no theoretical benefits of SAM over SGD (both achieve theoretical optimal, with SGD being simpler, less memory and computation-intensive). And I encourage the authors to include relevant discussion. 

Decision: Accept (Poster)