Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies, in more detail than predecessors, the generalization gap between Adam and gradient descent for image-like datasets.
main_review: The paper makes interesting observations about generalization properties of GD vs ADAM on a few settings.

Strengths
- Global convergence results for full batch ADAM and GD in non-convex setting when proper regularization is applied.
- Both Thrm 4.1 and 4.2 explores interesting differences/non-differences of ADAM and GD with respect to their generalization abilities.
- Based on a carefully constructed data distribution, the paper makes the argument that the inferior generalization performance of ADAM is closely tied to non-convex landscape of deep learning.

Weakness
- While all their observations are interesting in their own right, to me, the main weakness of the paper is its limited scope (2 layer conv net, full batch ADAM instead of online setting), some of which the authors also acknowledge in Section 7.
- Since ADAM performs *better* than SGD in when used with transformer/lstms in language setting, a more complete analysis would be to also consider a data distribution/model where that can be explained as well.
summary_of_the_review: This paper makes interesting and novel observations about generalization gap between adam and GD. Their observations are somewhat limited in scope.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new perspective to explain the difference in generalization ability between Adam and SGD. The main contribution of this paper is that it analyzes the behavior of Adam and SGD training on a two-layer network and a very special dataset, and the authors claim that Adam generalizes poorly while SGD generalizes well. The authors also provide analysis for convex functions and some experimental results to validate their claims.
main_review: Strengths:
1. The proposed analysis of the comparison between GD and Adam is, as far as I am concerned, novel.
2. The results look interesting and promising, the dataset proposed by the authors is interesting and could be useful in other analyses as well.


Weakness:
Although I am not an expert on the NN analysis literature, I happen to be familiar with some of the papers the authors have mentioned, especially those related to NTK. I have to admit that the settings in this paper are so novel that it looks a bit strange to me. Although I understand that it is hard to analyze neural networks, especially when the authors are trying to compare GD with Adam, which is notoriously known to be unnecessarily fancy, I still have the following questions/concerns.

1. First of all, the dataset looks interesting to me, but it seems that it is particularly designed for Adam on purpose. That is to say, it is already known to the public that Adam has convergence issues (Reddi et al, 2018), then it may not be too hard to construct such a dataset where Adam performs badly. Also, such a specific construction process raises the question of whether it is also possible to construct a case where GD performs pretty badly but Adam performs fairly well. I would sincerely encourage the authors to give more intuitions about their dataset, and maybe relax the assumptions (at least for GD)

2. Second, the neural network looks a little strange to me. The authors are using a truncated polynomial activation function, instead of ReLU. Is this on purpose? I don't see such kinds of activation functions very often in the literature. Is it possible to replace it with, say, sigmoid, tanh, or maybe ReLU so that the analysis is more similar to the real training process? I do not see where the technical difficulty is. It would be helpful if the authors can explain it a little.

3. If I understand it correctly, all the algorithms in this paper use full-batch gradients as their updates, instead of mini-batch gradients. I wonder whether it is possible to generalize the results to the stochastic mini-batch version.


Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.


summary_of_the_review: Although I find this paper to be novel and interesting, I have to admit that some of the settings in the paper look strange to me. However, I would like to encourage such explorations and vote for acceptance because the authors are not using NTK, and I could imagine how difficult it is when trying to analyze Adam on neural networks. However, I would also like to encourage the authors to further generalize and improve their analysis.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper aims to explain why there is a generalization gap between Adam and gradient descent in learning neural networks, even with proper regularization. To this end, the authors construct an artificial dataset in attempt to capture the basic properties of real image datasets that can lead to the generalization gap. Based on this dataset, the authors prove that Adam is more likely to fit noise in data, while GD tends to fit real features. The theoretical results are verified by experiments on the proposed dataset.
main_review: Using artificial datasets to simplify the analysis of complex optimization dynamics seems to be a highly promising approach. It has the potential to provide a theoretical yet intuitive understanding of the interactions between data, models, and optimizers. While I believe this paper has made some progress in this direction, many of its assumptions are too contrived.

Firstly, the same dimensions of different patches of the constructed data are reserved for either feature or feature noise, and the norm of the noise vector is specifically chosen to be much smaller than that of the feature vector, both of which are not well motivated. It would be interesting to see if some of the results still hold with weaker assumptions. Secondly, it seems the convolution part of the two-layer model is only introduced to impose weight sharing, such that the feature patch and the noise patch have to compete for the same set of weights, which is not necessarily the case in practice. Furthermore, the choice of truncated polynomial activation function is unconventional, and the second layer of the model simply sums up all the activations of the first layer without learned weights. Thirdly, in practice, the generalization gap is mostly observed between Adam and SGD rather than GD, and it is well known that SGD usually generalizes better than GD; therefore making directly comparisons between Adam and SGD would be more convincing.
summary_of_the_review: This paper presents a promising approach to explaining the generalization gap between Adam and gradient descent, but many of the assumptions on its data, model, and optimizers are far from realistic.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper propose a non convex optimization problem where the batch version of Adam has worse generalization than GD. Both methods achieve 0 training loss asymptotically but GD has a zero loss on the test set, while Adam has a large loss.

The paper studies a simplified CNN model with only two patches. The two layers are multiplied with the same weight matrix, fed into the activation function and then summed. A cross entropy loss is used for the classification. The activation function must be of the form $\max(0, x^q)$ for $q \geq 3$. Note that the second layer weights are not learnable and fixed to 1.

The dataset is built as follow: the label is y in {-1, 1}. One of the patch is just $x_1 = [y, 0, 0, ...]$. The second patch is $x_2 = [-\alpha y, \text{sparse gaussian noise}]$ ($0 <\alpha < 1$). The sparsity level is so high that no two examples have the same features.

The idea is that Adam will use a much larger effective learning rate for the sparse noise features than SGD, and grow the coordinates quickly. At some point the dot product with the noise in $x_2$ will be larger than the dot product with $x_1$. Because the activation function is of the form $x^q$ with $q \geq3$, this means the gradient from $x_2$ will overtake the one from $x_1$ and the weight for the first dimension will be negative (while a positive weight is the best thing to classify from $x_1$).
So Adam will focus on the weaker signal from $x_2$ (remember $\alpha < 1$).

To summarize further, one patch has the right answer, the second path has the right answer (but with opposite sign) + noise. Adam will focus on the second patch which has lower signal, while GD will focus on the first patch and ignore the noise.

The authors provide experimental verification of this fact.

main_review: Strength:
- experimental verification helps believe the result is true, as the proof is complex.
- a simplified version of the result is presented assuming SignGD is used instead of Adam and can be intuitively understood.
- food for thought paper on the limitations of Adam even if on a very specific example.

Weaknesses:
- not really a two layer network because the second layer is not learnable. If it were learnable, then setting a negative weight on the second patch would remove the issue that the dimension with the answer has different signs in the two patches.
- The behavior only exists because q>1 (amplification of the gradient from the dot product with the noise in the second patch). Otherwise, the gradient from the first patch for the coordinate 1 would always win.
- Behavior only exist for d > n^4.
- The level of sparsity is quite strong ($\sqrt{d} / n^2$), which seems a bit unlikely for a neural network (the citation (Papyan et al. 2017) does not just really justify such as assumption).
- The result is for batch GD and Adam. Notice that for the stochastic version, we wouldn't have such a strong difference between GD and Adam, because most of the time the gradient would be zero for the noise coordinates, and when they are seen, Adam would rescale by 1/sqrt(n) rather than 1/n with the batch version.


Questions:
- Each noise coordinate is present only once. So its gradient will be of the order of 1/n. Adam will rescale the gradient by a factor of n. What if you would do GD but with a learning rate n times bigger for the sparse features ?

Minor remarks:
- Lemma numbering is not aligned between main paper and appendix, while the Lemmas are the same. Either use same numbering or mention the Lemma number in the appendix with the proof.
- mention that you assumme d>>n^4, this is not expicitely the case.
- definition of Adam is missing the initialization bias correction, mention you drop it for simplicity.

update: after discussing with the authors on the activation function, I believe the authors reply on the smooth ReLU, while technically correct, is unrealistic. In particular, the authors rely on the scaling down of the pre-activation outputs to a region where the smooth ReLU is polynomial, in order to obtain again the amplification that allows the bit flipping. Neural network initialization is specifically made so as to avoid such small pre-activation outputs, and I believe this makes this theoretical example too far off current practices to be considered an illustration of the generalization issues faced by Adam.
summary_of_the_review: Interesting example where Adam generalizes worse than GD. The assumptions are very far from a real network, and removing any of them make this example incorrect: second layer is not learnable, very high level of sparsity, and activation function has an amplification behavior.

As far as I can say, claims are correct but the proof is quite hard to verify.

To summarize, I'm recommending weak acceptance, because the example is interesting but the assumptions are unrealistic.
review_title: null

Meta-review: The paper considers the difference between GD and ADAM in terms of implicit bias. It considers a specific distribution and architecture where the two algorithms converge to different solutions while perfectly fitting the training data. The authors highlight the fact that this happens while adding regularization, which does not happen in the linear case.
The reviewers found some of the insights and analysis interesting. However, they also had reservations about the impact of the results given that it is known that GD and ADAM have different implicit biases, and that the distribution appears specifically crafted towards  showing this effect for the architecture studied.
In future versions, the authors are encouraged to better motivate the chosen distribution, use more standard neural architecture (e.g., standard relu), and provide more explanation about the role of regularization in their result.
Decision: Reject