Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the trajectory of GD and SGD for kernel regression, and the connection to generalization. The paper shows that, under some stepsize choices, SGD has a directional bias towards sharp eigendirections of the kernel matrix. The authors link this feature to generalization using the properties of quadratics.
main_review: The paper is interesting and deals with a very important issue: generalization in simple problems, and the effects of training with SGD compared to GD. Focusing on simple tasks is very powerful and definitely we need more insights in this direction. However, I think the paper has a few drawbacks and deserves a few months of more work. Here are some concerns/questions for the authors. I will read the review, discuss with the authors and potentially upgrade my score.

1) The main concern I have in the link to generalization and the link to properties in the *training* landscape. Theorem 8 is trivial and is well known, however the link to generalization definitely does not follow: A is the training matrix, and GD converges exactly to w^* – the problem is that the w^* in test loss is different! In general, even though i might be missing something here, I invite the authors to tone the claim down: "explaining generalization" is the the holy grail of ML, such cold claims are somewhat unacceptable in published research.

2) Theorem 4 and 6 are nice and novel, however how do they compare? I have read Remark 7 but I do not feel like this is good enough: for SGD you use 2 different stepsizes and you also have a particular choice dependent on the C_i constants. My question is simple: lets take eta = 0.01 for both GD and SGD, fixed during learning. does the remark still hold? why? Please, show this experimentally (yes you can, and its a different setting compared to figure 1)!

3) Going exactly to experiments: why is there no experiment on generalization for kernel regression? your paper is about that! I would be surprised if you find that SGD generalizes better than GD in a fair setting (i.e. you tune the methods, and you use the same tricks for both). 

4) Second experimental concern: why in your FMNIST experiment you do not select the same stepsizes ranges for GD and SGD? You do not show GD performance with the "moderate stepsize" you have in SGD

5) Suggestions/ typos
- explain better directional bias in the intro
- typo in sentence "we prove that a two-stage SGD has b_t converges in the direction of the largest eigenvector of K"
- again typo  "that GD hasbt converges" before thm 6 

summary_of_the_review: The topic of the paper is very nice, but I have some concerns and hope to have a nice conversation with the authors!
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the directional bias of SGD in kernel regression. In particular, this paper shows that when using moderate or small step size, GD converges along the direction corresponding to the smallest eigenvalue of the covariance matrix. In contrast, when provided with a moderate initial learning rate with annealing, SGD converges along the direction corresponding to the largest eigenvalue. Consequently, the authors show that such directional bias of SGD can result in an estimator that is closer to the ground truth, which further leads to better generalization. 
main_review: 
Basically, this paper is well organized and the results are clearly presented. However, my major concern is regarding the novelty of this paper, given the closely related prior work [Wu et al., 2021].


**1.** It seems that given Assumption 1 and Proposition 14, the model is pretty similar to the linear setting considered in  [Wu et al., 2021], while the only difference is to replace the Gram matrix in  [Wu et al., 2021] with kernel matrix. 

**2.** It is true that the SGD algorithm considered in this paper is different from the epoch-wise SGD in [Wu et al., 2021], but it seems that the proof technique will not be that different as claimed by the authors. One difference I can see is that when using SGD in steps, one can focus on the expected components of the iterates along different directions, while for SGD in epochs, one can directly calculate the components rather than taking expectations. The authors may need to clearly clarify the difference in the Introduction.

**3.** Can you provide some intuition regarding the case when the gram matrix is not diagonal dominant? Does the result still hold or can the proof technique still work?

**4.** Experiments in figure 2 are basically the same as those in [Wu et al., 2021], could you clarify some differences between them? Otherwise, these experiments may not be necessary since they do not provide any new message.

**5.** Regarding Assumption 1, it would be better to provide some example kernel functions and data models right after this assumption rather than deferring them to Appendix. 

==========================

Thanks for your response. I suggest you revise your paper accordingly at least to highlight the difference and novelty compared to [Wu et al., 2021] .  Besides, it could be better if you can consider more challenging settings (e.g., the gram matrix is not that diagonal dominant), which could be closer to the practical cases.
summary_of_the_review: Given my concern about the novelty and contribution of this paper, I do not recommend acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies directional bias of SGD vs. GD in the setting of kernel regression. The presented results well-recover those for linear regression shown by prior work (Wu et al. 2021). Both theory and experiments are presented. 
main_review: # Pros:
+ The paper is very well written and easy to follow. Related works are well discussed.
+ Prior work only shows the directional bias of SGD for linear regression. It is good to learn that the directional bias of SGD also works for kernel regression.

# Cons:
- Most of the proof techniques are from (Wu et al. 2021). Given prior results for linear regression, an extension to kernel regression seems a bit incremental to justify a conference paper. 
summary_of_the_review: I cannot recommend an acceptance to this paper as most of the results are more or less incremental given prior work.
review_title: null

Meta-review: This is an interesting paper, aiming to separate the generalization properties of SGD and GD.  Unfortunately, the reviewers had many significant concerns, primarily on the topic of the relationship to prior work by Wu et al. (which has a similar setting and similar proof techniques), but also regarding presentation and interpretation of results in general.  As such, I recommend the authors continue with this line of valuable work, aiming in particular to further separate it from existing results.
Decision: Reject