Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

This paper considers the generalization bound for stochastic gradient descent. The authors leverage normalized loss function to analyze the stability of SGD algorithms which further yields the generalization bound. They provide the on-average stability result for non-convex optimization under the ReLU neural network setting. The theoretical results deepen our understanding of the performance of the SGD algorithm and an experiment is provided to illustrate theoretical findings.  

Reasons for score: 

Overall, this paper is well-written, and the idea of using normalized loss function to assist the theoretical analysis is interesting. My major concerns are listed below. Hopefully, the authors can address them in the rebuttal period. 

Here are some comments:

1) The idea of the normalized loss function should be discussed in detail. It is not very clear what is the motivation behind it and how this assists the theoretical analysis.

2) In the experiment, the authors compare their analysis with the one in Hardt et al. (2016). However, I think they should compare it with the one in Kuzborskij & Lampert (2018). Throughout this paper, this comparison should also be provided in their theoretical results. 

3) Their main theoretical results seem to be direct corollaries following from Hardt et al. (2016) and Elisseeff et al. (2005). The proof is trivial and it is preferred to explain their technical innovation.

review_title: An interesting paper but need some detailed explanations

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper discusses the uniformly statbility and on average stability of SGD on convex and nonconvex optimization algorithms. With proper choice of step size, the stabilities can be theoretically bounded. The convex case extends from Hardt et al. For the nonconvex case, the result is concrete and can be applied to neural nets.

A few questions/suggestions about writing. If they are addressed I'm glad to raise my rating.

1. I'd like to see more discussions about the bound for non-convex theorem. The quantity in Thm4 is a bit hard to interpret. Perhaps some examples can be given in appendix, such as matrix factorization, neural networks, and compute $\epsilon_{av}^\alpha$ with respect to data and parameters.  
2. I'd like to see more comparison with related literatures, specifically carefully compare to Hardt et al. Thm5 is kind of similar to Rademacher complexity which is widely used in other generalization type of papers, such as Du and Allen-Zhu's papers, so I'd like to see them as well.
3. If the length is not limited for appendix, it's more clear to put Hardt et al proof in it. Even if the exact same procedures are used, the sequence of lemmas and critical ideas can be listed so readers know which thm is quoted/replaced for the scope of this paper. 
4. If possible I want to see an end-to-end result in appendix. Say we take an nn and train it with some algorithm, what is the time complexity, training error and generalization error, and what is the overall algorthm for this ml task and how to tradeoff, etc. 
5. Defs need more clarification. With $l(w,z)$ and $l^\alpha(A(S),z)$, $S = \{z_1,...,z_n\}$, I feel that $z$ is the data. So $w$ and $A(S)$ are also data? When saying "$A(S)$ is the output of $A$", does it mean the algorithm recovers the parameter, and uses the model with this parameter to label the training set, and you observe the difference with true training labels? In Def. 2, is $z$ a single random sample or the set of samples $z_1,...,z_n$? Since $S= \{z_1,...,z_n\}$ also shows up, I guess that $z$ is another single random sample to avoid redundancy. In $l^\alpha(A(S^i),z)$, $z$ replaces some data, and what about $l^\alpha(A(S),z)$, why does $z$ appear here? And what does the superscript $\alpha$ mean?

===================== Update =====================

Raised to 6. A theoretical calculation on 4. would be great, if it can be done before publication. NN can be simplified, say linear, or one hidden layer linear. 
review_title: Good paper, suggest more illustration

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper develops new stability bounds for SGD. The main difference from the existing studies is that they consider stability bounds for normalized loss functions where the parameters are normalized to have a norm of $1$. This paper considers both convex and nonconvex cases. For the convex case, the authors develop uniform stability bounds and high-probability bounds. For the nonconvex case, the authors develop on-average stability bounds for neural networks. Experimental results are also given.

Comments:
1. The motivation should be further clarified. In particular, it is not quite clear to me the advantage of considering normalized loss as compared to the standard loss. At least I can not see the advantages from the theoretical results.

2. In Thm 1, the authors assume that the norm of the initial weight is larger than the summation of step sizes. I think this is a very strong assumption and can be violated if we run sufficient number of iterations. Furthermore, it seems that the argument is incremental. The analysis heavily uses the existing stability bounds in Hardt 2016. It seems that the authors do not introduce new techniques. The stability bounds grows as a linear function of the batch size. This dependency on the batch size is not desirable since it means that the generalization would decrease by a large amount if we increase the batch size.

3. In the non-convex case, the authors consider RELU neural networks and assume the smoothness of loss functions. However, RELU networks are not smooth. Therefore, the smoothness assumption in the theoretical results is violated.

4. In Thm 4, the authors assume a growing norm assumption: the norm of layer-wise weights are non-decreasing after some iterations. This is a very strong assumption and can be easily violated in practice. Although the authors give some examples to show this can happen, I still believe it is far from true in general.

5. The stability bound in Thm 4 depends on $1/\|w\|$. If we encounter weights with very small norms, the bound would be very large. Furthermore, both the stability bound and the generalization bound involves $\epsilon$, which is not decreasing w.r.t. either $T$ or $n$. This shows that the result is not converging which is a basic requirement in statistical learning theory.
review_title: Assumptions are strong and analysis is a bit standard

Meta-review: The paper considers generalization analysis of SGD using stability analysis. The authors argued the use of normalized version of the loss function, and angle-wise stability. However, the reviewers pointed out that both motivation and novelty of the current work are not strong enough for it to be accepted by ICLR.
Decision: Reject