Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper considers the stability of the stochastic gradient decent algorithm under different conditions. They show a lower bound for the stability of SGD in the smooth and convex case, and show that the bound can be tightened for linear models. They give a tight bound for the stability of SGD with decreasing step size in the non-convex case.  Then they propose the Hessian Contractive condition, and under this condition a tight bound for the stability of SGD with constant step size is given. 

pros: 1, They propose the Hessian Contractive condition which is weaker than strongly convex and show that the family of widely used (convex) linear model loss functions will satisfy the Hessian Contractive condition. 

2, They analyzed the stability of SGD and give the lower and upper bounds for the stability in many cases. 

cons: 1, In Theorem 3, they give a lower bound for the stability of SGD with decreasing step size in the non-convex case. However, this lower bound is larger than the upper bound in Hardt 2016 when T goes to infinity and the other parameters fixed. This contradiction implies that the results in Theorem 3 should be incorrect. 

2, They claim the O(1) uniform stability of SGD in under the Hessian Contractive condition. But the uniform bound of $||w^* - w^{*\prime}||$ is not proved. 

After the rebuttal.

The authors partially addressed my concerns. I have read other reviewers' comments. I decide to remain the current score.
review_title: Reviews for Revisiting the Stability of Stochastic Gradient Descent: A Tightness Analysis

final_score: rating: 4: Ok but not good enough - rejection
review_content: 1.	In my understanding, a learning algorithm is stable when a small perturbation in the training does not affect the outcome drastically. Based on this notion, in [Data-Dependent Stability of Stochastic Gradient Descent, Kuzborskij and Lampert, ICML 2018] used (Hardt et al., 2016) and extended them to the distribution-dependent stability setting for both convex and non-convex cases. I also understand that the bounds of (Hardt et al., 2016) are stated in terms of worst-case quantities, but Kuzborskij and Lampert revealed new connections to the data-dependent second-order information. First, among several important works that analyze the stability of SGD, you missed the work of Kuzborskij and Lampert. I suggest that you please include this work, discuss it, and show how you are similar or different than them and how tighter or relaxed your bounds are compared to them. Since both works are based on the seminal work of Hardt et al., 2016, in my opinion, without a proper comparison/discussion this work is incomplete. However, I consider this present manuscript is a fairly well-written manuscript but it is not complete yet. 

2.	In the context of uniform stability, [London, B. Generalization bounds for randomized learning with application to stochastic gradient descent, 2016], “partially” addressed how data-independent component such as step-size affects the stability. What is your input on that? Theorem 6 in your manuscript mentions about fixed stepsize but other than that I do not see any discussion on step-size which is in my understanding is an important component in the performance of SGD. 

3.	Please correct me if I am wrong: In the proof of Theorem 6 did you use the uniformly bounded gradient? But one can even strongly argue that this bound is actually $\infty$. In my understanding, uniformly bounded gradient with strong convexity leads to a contradiction. That is a stronger argument can be made that the above assumption is in contrast with strong convexity. Please see ["SGD and Hogwild! Convergence Without the Bounded Gradients Assumption" by Nguyen et al.] as one of the instances. How about using more relaxed assumptions such as Strong growth condition on a stochastic gradient as in Assumption 4 of [Dutta et al. AAAI 2020, On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning]? 

review_title: This paper analyzes the stability of SGD on both convex and non-convex functions based on the seminal work of Hardt et al., 2016.

final_score: rating: 7: Good paper, accept
review_content: Summary:

The paper studies the stability of stochastic gradient descent (SGD), which is one of the framework used for explaining generalization. More specifically, the paper investigates the tightness of the algorithmic stability bounds for SGD given by Hardt et al. (2016). Furthermore, the authors propose the Hessian contractive condition, which characterizes deep learning loss functions with good generalization properties, when being trained with SGD.

Pros:

1. The paper concerns the stability-based analysis, which is one of the approaches used for explaining the strong generalization performance of deep neural networks in practice.

2. By investigating the tightness of the stability bound for various types of problem (convex, non-convex), the paper shows that in general, using stability framework seems to hit an obstacle on the way to explaining generalization. Hence, further conditions are needed to guarantee generalization. By this point, the authors propose Hessian contractive condition which is satisfied by potentially many machine learning loss functions and is sufficient to guarantee a better generalization properties.

3. The paper provides empirical evidences / experiments which make the theoretical claims more comprehensible.

Cons:

Apart from the strong points, I still have one concern about the clarity of the paper:

1. The lower bound in Theorem 1 is larger than the upper bound in Theorem 3.8 in Hardt et al. (2016) when the Lipschitz constant is smaller than 1. Can you explain this mismatch?

I hope the authors can address my concern to improve the quality of the paper.
review_title: The paper studies the stability of stochastic gradient descent (SGD), which is one of the framework used for explaining generalization.  Overall, I vote for accepting the paper.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies stability of SGD which is a popular optimization algorithm. The authors aim to build a tight stability analysis. In particular, the authors show by constructing specific problems that the existing stability bounds for SGD applied to convex problems are tight within a constant factor. Then, the authors refine the stability analysis in non-convex case by presenting new bounds, and show the new bounds are tight. The authors also provide new conditions weaker than strongly convex assumption in both convex and non-convex case. The paper is clearly written and is easy to follow.

Comments:
1. I have doubts in the proof of Lemma 1. It seems that the identity
\[
E\|\triangle_{t+1}\|=(1-\alpha_t\lambda)E[\|\triangle_t\|]+\frac{\alpha_t}{n}\|x_i-x_i'\|
\]
is not correct. The underlying reason is that we can not exchange the expectation and norm. As far as I can see, one can only show
\[
E[\|\triangle_{t+1}\|]=\frac{(n-1)(1-\alpha_t\lambda)}{n}E[\|\triangle_t\|]+\frac{1}{n}E\big\|(1-\alpha_t\lambda)(w_t-w_t')-\alpha_t(x_i-x_i')\big\|
\]
Therefore, I think Lemma 1 may not be right. As a result, the lower bounds on the stability bounds may not be right.


2. The self-corrected condition depends on the dataset S. However, for the uniform stability, one needs to consider all datasets S. Therefore, the divergence bound in Theorem 2 can not be used to get stability bounds. Furthermore, $\xi$ should be zero if one considers all the dataset.

3. In Theorem 4, $\alpha_t=\alpha/(\beta n)$ should be $\alpha_t=\alpha/(\beta t)$? Furthermore, I find it hard to follow the proof. For example, I cannot understand why the authors use the inequality $(1-1/n)^r\leq n/(n-r)$. Is it clear that $(1-1/n)^r\leq 1$? In eq (16), the last third term involves $t_{k-1}$ and $t_k$, while the last second inequality involves only $t_{k-1}$, which is not very meaningful. I also cannot understand well the deduction in eq (20).

4. In the statement of Theorem 6, the authors indicate that $\|w_T-w^\star\|\leq\sigma$. However, the authors only prove this result in expectation. Furthermore, if this inequality only holds in expectation, then one can not use the Definition 6 which requires $w_t$ to be close to $w^*$ almost surely.

In conclusion, although this paper considers a very interesting problem, there are some issues on the correctness of the deduction.
review_title: Proofs seem not to be rigorous

Meta-review: The AC and reviewers agree this is an important line of research. However, only one reviewer was initially positive, as the other reviewers raised some issues, and the rebuttal only partially addressed some of them (e.g., the reviewer is now OK with Lemma 1 being correct), but there are typos in the proofs, and there were other issues like the uniform bound that R3 brought up which was retracted in the revision, and such. These issues give us a bit of lack of confidence in the rigor of all the results.

In addition to the lack of carefulness in places, this paper (more than usual for an accepted paper) seemed to miss references in the literature. In addition to all the ones pointed out in the reviews (especially R3's, which I don't think was fully adequately discussed in the rebuttal), other tight lower bounds on uniform stability have been developed recently (see Thm 4.2 in Bassily et al. https://arxiv.org/pdf/2006.06914.pdf).  From the optimization point of view, it is undesirable to introduce new conditions unless really necessary, and often these new conditions are previously known under a different name; if they really are new, they should be compared to old conditions. In particular, then new "Hessian contractive condition" should be compared to standard non-convex conditions like strong growth, error bound, Polyak-Lojasiewicz, etc.

Finally, this is based off the Hardt/Recht/Singer 2016 paper, but there is a more recent Hard/Recht work that argues that algorithmic stability is not the right tool, because it cannot explain the fact that training error drops roughly the same with real data or with data with completely random labels -- so any generalization theory has to be data dependent. See: "Understanding deep learning requires rethinking generalization" (https://arxiv.org/abs/1611.03530) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals.  So this issue should be addressed as well.

Overall, this could be a promising paper and the AC recommends the reviewers make a substantial revision addressing these concerns.
Decision: Reject