Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: One of the main contributions of this paper lies in the generalization error of O(1/n) under the P-L condition given by Theorem 1. It provides a generalization bound instead of the hypothesis stability or uniform stability in previous discussions. The result explains generalization even under overparameterized model.


Strength:
+ The theoretical result is novel, according to the authors this is the first paper to model the generalization bound in terms of a $O(1/n\beta)$ term plus the convergence rate of the optimization algorithm
+ The authors applies the main theorem on practical algorithms and derive convergence rate on generalization error while previous literature on those algorithms are mainly on  training error.


Weakness:
- Some of the background description and preliminaries are vague, for example the $E_{S, A}$ concerning taking an expectation over an algorithm A are not explained.
- The relation of related works with this work is not clear enough. The two paragraphs, "Algorithmic Stability" and "Generalization Analysis" all ends up with areas that stability/generalization is applicable, while I care more about how previous literature shed lights on this work.
- I see no experimental results to support their theory

I think it is a good paper that provides novel aspects of understanding. It provides new insights in understanding important phenomenons in training deep neural networks whose Lipchitz constant might be very large. The bound removes the Lipchitz constant and uses training error of the best model instead. It explains why interpolation does not lead to overfitting. However the first part of this paper is a little bit rash while the experimental support is insufficient.

Question:

How widely is the PL condition applicable? Are there any examples when the PL condition does not hold?

In Theorem 1 the assumption is $L \leq n\beta/4$, while in Corollary 2 the assumption becomes $L < n\beta/2$, what makes the difference?
review_title: Provide new understanding on generalization, however need more experiments

final_score: rating: 7: Good paper, accept
review_content: This paper mainly studies the generalization performance of stochastic algorithms. Compared with previous results which rely on Lipschitz condition, this paper assumes smoothness condition and Polyak-Lojasiewicz Condition, and then prove the excess generalization bound that is a summation of $\frac{1}{n\beta}$ and empirical optimization error. This result looks impressive, not only because the first term looks shaper than previous $\frac{1}{\sqrt{n}}$ of generalization bound , but also it implies optimization benefits generalization, which may help understand some empirical observations in modern machine learning. What's more, authors analyze some common stochastic algorithms as concrete examples to show the corresponding theoretical guarantee.  Besides, the whole paper is well-written and easy to follow. 

Though results in this paper look stronger than previous results, authors use different assumptions (say smoothness instead of Lipschitz condition) compared with previous paper, and it would be better if authors could make these comparisons more clear (say in abstract etc.). Besides, though there is a $\frac{1}{n\beta}$ term in the generalization bound, it holds in expecation, and I think an extension to high probability bound will lead to an additional $\frac{1}{\sqrt{n}}$ term, which should also be stated clear when comparing with previous results. Finally, I wonder whether it is possible to extend the results to non-smooth loss function, at least for some special case, such as DNN with ReLU activation unit.
review_title: Impressive Results and Well-Writen Paper

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the generalization performance of stochastic algorithms in nonconvex optimization with gradient dominance condition. In detail, the authors suggest that for any algorithm, its generalization error can be bounded by $O(1/(n\beta))$ plus the optimization error of the algorithm, where $\beta$ is the gradient dominance parameter. The main idea for the authors to obtain such an improved bound is an advanced analysis based on a weaker on-average stability measure. 

Here are my detailed comments. 
- It seems that to do a comparison, the authors need to ‘translate’ previous complexity results such as stability results (Charles & Papailiopoulos, 2018) to generalization results, considered in this paper. To do such a translation, Theorem A.1 is proposed. However, I did not find the proof to Theorem A.1 except its part c. Since the translation is crucial for a fair comparison, the authors may want to complete the proof to Theorem A.1 or point out some relevant references about that. 
- Assumption 1 and 2 suggest that $L$ and $\beta$ are two parameters about $F$ itself, in other words, independent of any specific data set $S$. However, in Example 1 and 2, the authors suggest that $L/\beta$ is in the order of $\sigma_{max}(\Sigma_S)/\sigma_{min}(\Sigma_S)$, which depends on the random data $S$. Can the authors explain more about that? Shall we need some more assumptions about the data distribution (for instance, the support set of $x$ is finite) to support such a claim?
- $O(1/(n\beta))$ generalization gap is standard for the case where $F$ is convex, and this work tries to extend it from convex to nonconvex with PL condition, just as the authors suggest in Remark 3. Does the $O(1/(n\beta))$ gap still hold under other nonconvex relaxing conditions such as one-point strongly convexity or quadratic growth [1]? 

[1] Necoara, Ion, Yu Nesterov, and Francois Glineur. "Linear convergence of first order methods for non-strongly convex optimization." Mathematical Programming 175.1-2 (2019): 69-107.

review_title: Review for 'Sharper Generalization Bounds for Learning with Gradient-dominated Objective Functions'

final_score: rating: 5: Marginally below acceptance threshold
review_content: 

The whole paper is focused on the theoretical part. I am missing the important experiment part to back up the theory. I could not vote for acceptance without the experiments, and I will increase the score if satisfying experiment results can be included.

It is also important to verify the condition $L \leq n\beta/4$ in the experiment, i.e. how large the sample size needs to be. In terms of this constraint, I saw that the authors tried to investigate and interpret it. But I still have some questions on them. Please correct me if any of my understanding is wrong:

Both $L$ and $\beta$ seem to depend on $n$ and are not absolute constants here. For example $L/\beta$ is about $\sigma_{\max}(\Sigma_S) / \sigma_{\min}(\Sigma_S)$ in the examples. Here my understanding is that $L/\beta$ could be large if $n$ is small. When $n$ becomes super large then $L/\beta$ would be close to some constant

- if n is super large, then the constraint $L \leq n\beta/4$ would be satisfied. But since n is super large, this constraint is also very trivial and seems not imposing any "implicit constraint" on the complexity of the problem.
- if n is moderate, then this constraint $L \leq n\beta/4$ might not be satisfied
review_title: Good theory on the study of generalization error, but experiments are missing

Meta-review: In this work, the authors develop an improved generalization bound for stochastic optimization algorithms. Reviewers agree that the theoretial results are significant. Several reviewers had concerns about the lack of experimental validation, which the authors addressed during the discussion phase. Other more minor concerns were also adequately addressed by the authors. The final recommendation is therefore to accept.
Decision: Accept (Poster)