Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides new generalization bounds for SGD using the stability analysis framework for both convex and non-convex cases using a normalized loss function, stability as measured in the form of anglewise stability as supposed to standard euclidean distance.
main_review: The paper is generally very well written. The idea of using normalized losses and angle-wise stability to analyze SGD is interesting and novel. One minor concern I have is the motivation/justification behind using angle-wise stability and overall applicability in neural network learning. Authors claim that in the framework of on-average stability and normalized losses, larger norms of parameters are beneficial to stability. However, it is known that this is probably not generally the case. Even though authors show some empirical evidence in Fig 3, this argument can be better motivated.
summary_of_the_review: I feel the theoretical results are strong and the authors provide sufficiant empirical results to validate their theoretical findings.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper conducted a stability analysis of Stochastic Gradient Descent (SGD) for empirical risk minimization induced by the so-called normalized loss function. Here, the normalization is taken with respect to parameters involved in an individual loss; see (4) for the definition of the normalized loss function. The paper should be regarded as a theoretical paper. The main results are stability bounds of SGD for convex and nonconvex ERM schemes.   
main_review: My main concern about this paper is its motivation for considering/highlighting the normalized loss function. To me, it is a serious concern as all the analysis conducted in this paper is built upon the normalized loss. However, here the normalization, in my opinion, is more of a trick in the analysis. I read through the two papers, Poggio et al., 2019 and Liao et al., 2018, which, according to the authors, introduced normalized loss function. However, it seems that the normalization was used only to simplify the analysis and similar theoretical results could be obtained without normalization. Such comments may also apply to the present paper. In short, I cannot agree with the authors that it is the normalization operation that leads to the results developed in this paper. 

In addition, in my opinion, the presentation of the paper needs to be greatly improved. For instance, the authors highlighted the normalized loss throughout, including the title. The notation of normalized loss is also used in Definitions 1 and 2 from Section 3. However, the definition of normalized loss function was only introduced in Section 4. I believe that the normalized loss is not something well-established in the literature. From the two papers mentioned by the authors, I failed to find an explicit definition of the normalized loss function. Therefore, I think the authors really need to define the loss before using the concept again and again. On the other hand, when stating the motivation and the origin of the normalized loss function, the authors only mentioned them in passing at the beginning of Section 2. It seems to me that the authors said a lot about the literature but were trying to avoid answering the question "why this work". I do think that the authors need to take care of this part more seriously.       
summary_of_the_review: Based on my comments above, I cannot recommend its acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of understanding the generalization of SGD using the stability framework. The well-known result in this line of work is the paper by Hardt'16. In Hardt'16, the stability is measured using the difference between the "actual" weights of two copy of SGD which differ in a single data point. The main observation by the authors in this paper is that in many cases, the loss function is invariant to the scaling of weights. Then, they reformulate the stability analysis using the "normalized loss function" which is defined by  l^alpha(w,z) = loss(alpha*w/||w||,z) where alpha is a constant.

Their main results are the new stability analysis for this new notion for convex and non-convex settings. Specifically, for the convex case the analysis is very similar to the Hardt paper. For the non-convex the authors define a new measure for generalization "zeta" in Theorem 4 which governs the stability.
main_review: 1- The definition of the stability is for normalized surrogate loss. For instance we might measure the performance with 0-1 loss but train using the cross-entropy loss. I could not find the result in the paper that relate the stability parameter of normalized surrogate loss to 0-1 loss? Note in the Hardt el al paper, we only have one loss function. For instance, in Theorem 2 of  Kuzborskij and Lampert, you can find a such a result.

2- In general, I find it difficult to interpret the results in this paper. Theorem 2 implies that if the initialization point has a very large norm then it helps generalization. Could you please provide more intuition behind this result? Also, please compare your result with Theorem 3 of  Kuzborskij and Lampert, where their bound basically implies that if the distance between the initialization and the optimal point is small, then the sgd is stable for convex case. 

3-A technical question is can you provide more details to proof of Theorem 2. Specifically, how do you relate the normalized loss to 0-1 loss?

4-  In the definition of zeta_t, what prevents the denominator to not be close to zero while the numerator be bounded away from zero?

5-  The main quantity for the non-convex setting is the zeta. I could not find any intuition behind this term? Also, how can we compare it with Lipschitz constant?

6- In your experiment you used the batch normalization. However, the theoretical result is obtained for vanilla SGD.

7- In general the figures quality is not good. For instance in Figure 4, the legend and labels are not clear at all. 

8- In general, there are lots of "proposal" for the relevant complexity measure for generalization. It would be nice to compare your zeta with the proposals. Please check the Table 1 of "Uniform convergence may be unable to explain generalization in deep learning" by Nagarajan, Kolter to find a list of such measures. 
summary_of_the_review: Interesting motivation and direction however the paper is not well written and there is no discussion for the results. Also, the numerical results section can be improved greatly.
review_title: null

Meta-review: The paper focuses on providing generalization bounds for SGD for functions that are invariant under scaling. The paper's analysis is based on the stability framework but instead focuses on a metric that is based on the anglular distance as compared to the euclidean distance.

Overall the reviewers found the paper to be interesting and the results to be useful. However the reviewers found the paper to be significantly lacking in terms of its presentation. In particular a clear exposition of the central object of the paper, i.e. normalized loss function was missing as well as clear comparisons between the presented results and existing results. I recommend the authors to motivate their results better and contrast their presented results with existing results to fully highlight the impact of their presented result. Hopefully the suggestions made by the reviewers in terms of presentation will be helpful to the authors towards improving the paper.
Decision: Reject