Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper analyzes the differences in the convergence of SGD and GD when using "small" and "moderate" learning rates to shed light on why SGD with "moderate" and annealing learning rates perform well in practice. Focusing on an overparametrized linear regression problem, the paper claims that SGD with a "moderate" learning converges differently (along the large eigenvalue directions) compared to SGD/GD with a "small" learning rate (along the small eigenvalue directions).  They further show analytically for this problem that there exists a learning rate schedule (with moderate learning rates) such that SGD will perform + generalize well, while there exist small learning rate schedules such that GD will perform + generalize poorly.  

This paper is clearly written and presents a clear illustration of their hypothesis for why SGD with a moderate learning rate performs well in practice through Figure 1 and a simple linear regression example in section 3. The paper focuses most of its analysis on a toy example problem (overparametrized linear regression) and the empirical experiments do not clearly support the paper's claims.
 
This paper should be rejected as is. Although the motivating example and illustrations are interesting, the analysis for the overparameterized linear regression problem is too specific to clearly claim that this "directional bias" is why SGD with moderate learning rates is successful. 

I have two main concerns: (1) in the special case of overparametrized linear regression, Theorem 2 only shows that GD with small learning rates converge along the smallest eigenvalue direction. It does not preclude GD from having the same behavior as SGD for larger learning rates. I also do not agree with remark 4.
(2) it's not clear how or why the results for overparameterized linear regression would extend to generic NN losses. The example experiments (Fig 2) need more detail to be clear and are not sufficient to support the hypothesis in the paper.  

Questions:
In section 3, doesn't Eq (3) show that GD will behave identically to SGD if the learning rate is doubled? What is considered a "moderate" learning rate for GD + SGD does not need to be identical, right? 

For the overparametrized regression, why do we not include some form of regularization on the weights (as would commonly be done in practice)? Does this affect the results?

What is the minibatch size for SGD in the experiments? How are the results (in Figure 2a + 2b) sensitive to random initialization?  

Minor comment: Page 6: the definition of level set probably needs a $\leq$ sign.

review_title: Too specific with weak experiments.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
In this paper, an implicit bias of SGD and GD in terms of the direction of convergence points is studied. This study shows that, in a setting of linear regression, SGD and GD converge to different directions, which are determined by the largest/smallest eigenvectors of a data matrix when the learning rate is moderately large. Experiments using synthetic data and Fashion MNIST support the theoretical results.


Detailed comments:
First of all, I don't have much experience in the analysis of SGD/GD and my assessment for technical points may miss some important points. 

Overall, the paper is well written. The motivation and problem setting are clearly written. Related work is sufficiently introduced. 

The main theoretical results (Theorems 1, 2, 4) are interesting. As far as I know, there's no study to reveal the implicit bias in terms of direction. However, I have several concerns.

1. In the data generation process, the noiseless output y = <w*, x> is assumed. However, the output often contains observations noise such as an additive Gaussian model as y = <w*, x> + $\xi$ where $\xi$ is small Gaussian noise. Would it be possible to show similar results in the noisy case?

2. More importantly, the benefit of the directional bias is not clear. Theorem 4 shows SGD achieves $\epsilon$-optimal solution and GD achieves $M$-suboptimal solution. However, we cannot conclude that SGD solution is better than GD solution because the generalization performance depends on the unknown constants $\epsilon$ and $M$. So, GD may win in some cases but SGD may win in other cases, but it seems there is no way to know in what conditions $\epsilon$ and $M$ satisfy some specific values so that SGD beats GD. Would it be possible to clarify the conditions?
review_title: Interesting and novel analysis but I have a few concerns

final_score: rating: 7: Good paper, accept
review_content: In the paper the authors analyzed the convergence dynamics toward a minimum of gradient descent (GD) and stochastic gradient descent (SGD). The algorithms are considered to start in the basin of attraction of a minimum, and using discrete steps they approach the bottom. The main result of the paper concerns the fact that, with moderate learning rate, SGD approaches the minimum along the steepest direction, contrary to GD.
The authors conclude that the implicit bias of SGD does not appear in small learning rate formulation, but it becomes manifest when a moderate learning rate is considered.

* It seems from the analysis that SGD differs from GD because its learning rate is modified by the batch size and therefor it uses an "effective learning rate". The question is : what would happen if GD is taken with a learning rate that matches the effective learning rate of SGD? This situation is very similar to the one observed in [Nakkiran (2020)] (and also close to [Lewkowycz et al. (2020)]), where they consider GD and draw similar conclusions. 

* Another questions is whether it is really necessary to have discrete steps to have a difference between GD and SGD in the continuous formulations. In the introduction the authors make a comparison between the implicit biases in the literature for GD and SGD claiming that they are the same because of the small learning rate. However this is not clear to me, could the authors cite papers where this is explicitly shown? 
In particular there is a literature on the effect of SGD in the continuous formulation [e.g Jastrzebski et al. 2018 (arXiv:1711.04623); Zhu et al. 2019 (ICML2019); Xie et al. 2020 (arXiv:2002.03495)] using stochastic differential equations it was possible to show that SGD has an implicit temperature that adapts to the geometry of the landscape favoring, in particular, flatter solutions. In few words, do we need to rely on the discrete formulation to understand the advantages of SGD?

* The result by [Nakkiran (2020)] seems to heavily rely on having a data distribution that is highly homogeneous to observe the difference between the training and the generalization loss. Do we have evidence that this is relevant for practical situations?
I would happy have more numerical experiments as the one in Fig.2 . In particular showing the effect of increasing the learning rate in GD (and SGD) from the current "small" value to a value large enough so that it does not converge anymore. Both in the synthetic and real dataset.

The questions above block me from giving a higher rating, but I will be happy to increase the rate given satisfactory answers.
review_title: An interesting contibution that needs some clarifications 

Meta-review: This work compares and contrasts the learning rate dynamics of GD and SGD and shows that under practical learning rate settings, SGD is biased to approach the minimum along the direction of steepest descent, leading to better performance. Reviewers agree that the theoretical results are significant. The authors satisfactorily responded to reviewers’ questions and improved the paper’s clarity during the discussion phase.
Decision: Accept (Poster)