Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers generalization aspects of learning algorithms on toy data. For the considered data distributions uniform convergence generalization bounds, as well as polynomial margin bounds, provably fail. Nevertheless, a maximum margin classifier can still generalize on such distributions.
This is a pure theory paper. The contributions are the quantification of the aforementioned effects, together with their proofs and discussions.
strength_and_weaknesses: Strengths
- The paper extends prior results by Nagarajan & Kolter (NeurIPS 2019), as it shows that not only uniform convergence but also polynomial margin bounds, might be unable to explain generalization in deep learning.
- The existence of regimes where different generalization bounds apply is very interesting and to some extent unexpected.
- In addition to linearly separable data, a variant of the XOR problem is analyzed.

Weaknesses
- Section 3 of the paper (which presents the results) is **very** difficult to understand and technical. A careful and extensive polish is necessary. This includes a more thorough comparison with related work.
- Reproducibility: The proofs are kept rather short. In consequence, I am unable to confirm the correctness of the results.
clarity,_quality,_novelty_and_reproducibility: **Regarding Novelty**

The Theorem 3.4 on the vacuity of uniform convergence bounds is similar to a prior result from Nagarajan & Kolter (NeurIPS 2019) and uses the same proof technique. Theorems 3.5 and 3.6 on the vacuity of polynomial margin bounds are novel as far as I am aware. While equally being based on the proof technique from Nagarajan & Kolter (NeurIPS 2019), this is a key contribution, particularly in combination with Theorems 3.1 and 3.2 which show that the maximum margin classifier still generalizes.

However, the differences between this paper and Nagarajan & Kolter (NeurIPS 2019) are not obvious and demand a proper comparison.  
1) Nagarajan & Kolter (NeurIPS 2019) already consider UC for the ramp loss, i.e. a polynomial margin loss.  
2) According to the paper, the definition of usefulness is "essentially equivalent" to the definition of algorithm-dependent uniform convergence bounds from Nagarajan & Kolter. Yet, usefulness seems to be necessary for the results on margin bounds, i.e. algorithm-dependent uniform convergence cannot be used there.  This suggests that usefulness is not equivalent, but a stronger assumption.  
3) Nagarajan & Kolter (NeurIPS 2019) argue that "showing failure of uniform convergence in these [linear] models is, in a sense, the most interesting." I would like to hear the authors perspective on this, as they do consider two layer networks specifically.  
4) The third paragraph of the introduction is confusing. It begins with that the results of Nagarajan & Kolter do not apply to many margin-based generalization bounds but later it states that the results suggest that "classical margin bounds may not be useful".

The intuitions section it shows, that the max margin classifier corresponds to the empirical mean of the data. Since Theorem 3.1 assumes that the data distribution is from a family parametrized by $\mu$, is achieved, if the parameter $\mu$ is estimated accurately enough. This suggests that Theorem 3.1 could be considered as a classic mean estimation problem and the relation to the max-margin might only be by chance (or construction). I would like to see a discussion.
This observation also suggests a more direct proof; see the end of the review.

--------------------

**Regarding Clarity** 

- The paper is difficult to understand and the results in Section 3 are presented quite technically. If theorem statements could be changed so that they focus on the key findings, this would be a major improvement.

- The main assumption seems to be the value of the "signal to noise ratio" $\kappa$, as it determines the generalization regime (see Fig. 1). However, in the theorem statements, there are additional implicit assumptions on $\kappa$ (e.g. Theorem 3.4 requires $\frac 1 {\kappa \sigma^2} = d/n\ge c$, Theorem 3.1 requires $d/n\ge c \frac 1 {\kappa^2}$, which is equivalent to $\kappa\ge c \sigma^2$). Similarly, the section "key intuitions for generalization theorems" requires $\frac n {d \sigma^4} = \frac \kappa {\sigma^2}$ to be large.
It seems that $\kappa$ alone is insufficient to determine the generalization behavior and Figure 1 is too simple.

- Connected to the previous point is that the assumptions of the theorems are not clear.
Many assumptions are interconnected and identifying the validity region of the theorems is difficult.
For instance, Proposition 3.5 requires $\frac n d  \le \frac 1 c \kappa^2(\kappa_{uc}-\kappa)^4$ or equivalently $\sigma^2 \le \frac 1 c \kappa(\kappa_{uc}-\kappa)^4$. But $\kappa$ is again a function of $\sigma$, so this inequality actually determines the range for $\sigma$ given $n/d$.

- The remark after Theorem 3.2 indicates that for a given probability distribution, i.e. given $\mu, \sigma, d$, the theorem only holds if the sample size $n$ is **small enough**. This is quite unusual.

- The theorems are not limited to the maximum margin classifiers but consider also ($1-\epsilon$)-maximum margin classifiers. I might be missing something, but this does not appear to be a strengthening of the results. If the bounds hold for maximum margin classifiers, then continuity implies that the bounds still hold in a sufficiently small neighborhood, e.g., in a sublevel set of the margin operator.

-----------------------------

**Regarding Reproducibility**

The proofs are kept short and many steps must be filled in by the reader. Due to the short reviewing period, I could only check proofs for the linear setting.

Below, I will list points, where I am not sure, if the proof is correct and I just missed something, or if there is a mistake. And if so, if it can be corrected such that the theorems still hold.


- **Proof of Lemma B.1:** Why does invertibility of $\Xi^T \Xi$ imply $v = \Xi (\Xi^T \Xi)^{-1} c$? By assumption $\Xi^T v = c$ and so $v= (\Xi \Xi^T)^{-1} (\Xi \Xi^T) v = (\Xi \Xi^T)^{-1} \Xi c$. Further, why does this imply that  $\|v\|$ is in the interval specified in Eq. B.5?

- **Proof of Lemma C.1:**  How is Lemma B.1 applied here?
What would be $c$ and what would be the corresponding minimum vector $v$?

- **Proof of Lemma C.3:** Typo. In Eq. C.17, "$\le$" needs to be replaced with "$\ge$".

- **Proof of Lemma A.1:** Could you elaborate on Eq C.36. I understand that $f_v^2$ is beta(1/2, (d-2)/2) distributed, but then I am out.

- **Proof of Theorem 3.1:** The last inequality uses $d>n$, but this is not listed as an assumption.

------------------

Unrelated to score. A more direct proof of Theorem 3.1 (and perhaps 3.2) seems possible. In the intuitions section it is shown, that the max margin classifier corresponds to the empirical mean of the data and that its "overfitting component" $v$ is the empirical mean of the spherical noise. Thus, concentration inequalities, e.g. vector Bernstein, allow to bound $\|| v\||$ with high probability and could be used instead of Lemma C.2.

Typo on page 7 $\sqrt{\gamma(w_b,S)^2+  \gamma(w_b,S)^2}$ change to $\sqrt{\gamma(w_g,S)^2+  \gamma(w_b,S)^2}$
summary_of_the_review: The observation that there exists data sets where max-margin classifiers work but polynomial margin bounds fail is quite interesting. This will be a good paper, if presentation is improved, i.e. theorems simplified and and put into context. However, doing so might require a major revision of the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is motivated by the failure of uniform convergence based generalization bound. Accordingly, this paper proves a new type of margin based generalization bound in two settings: linear and two-layer nonlinear network model. In particular, this paper provides a threshold on the signal-to-noise ratio to indicate under which regime the margin based results and uniform convergence based results will success or fail. The authors also show that the max-margin solution will contain both generalizable components and some overfitting components.

strength_and_weaknesses: 
Strength:
* This paper provides a new margin-based generalization bound for linear and two-layer network models on certain data set.
* This paper shows that the max-margin solution will contain both generalizable and overfitting components.
* This paper clearly identifies the settings that the margin-based results and uniform convergence based results will give vanishing or vacuous generalization bound.

Weakness:
* The generalization analysis in linear case is quite similar to that in [Chatterji and Long, 2021], a thorough discussion should be added. In fact, [Chatterji and Long, 2021] study the generalization error of gradient descent for learning high-dimensional Gaussian mixture model (their dimension assumption is a bit stronger than this paper as they require $d>n^2\log(n)$), which can be also extended to derive certain margin-based generalization results.

Chatterji, N. S., & Long, P. M. (2021). Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime. J. Mach. Learn. Res., 22, 129-1.
* As claimed by the authors, the max-margin solution will contain both generalizable and nongeneralizable (or overfitting) components, then why should one still prefer to consider max-margin solution? I can understand this for linear case since GD will finally give max-margin solution, but for nonlinear case, I have two concerns: 1) is (2.3) a good definition of the margin; and 2) why is studying such a max-margin solution, or near max-margin solution a good direction to understand the generalization?
* In Proposition 3.3, the failure of near-max-margin solution will not generalization is only shown in terms of existence, while it is not clear whether this “bad near-max-margin” solution is able to be discovered by training algorithms. For instance, assuming the gradient descent will finally converge to the max-margin solution, then applying proper early-stopping will likely give a  near-max-margin solution. Then will this type of near-max-margin solution give bad generalization?
* For xor case, it would be better to also consider $h\ge 2$, as studied by [Cao et al., 2021] (though the over-parameterization conditions are different). Besides, a discussion in terms of the theoretical results compared with this prior should be added (after the theorem). 

clarity,_quality,_novelty_and_reproducibility: The clarity and quality are generally good. In terms of novelty, the authors may need to add more discussions on the comparison to prior works, as commented in the weakness section.

summary_of_the_review: Overall this paper is well written. More discussions should be added according to my comments in the weakness section.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper is an extension of the existing paper by Nagarajan & Kolter. 
Previously, Nagarajan & Kolter show that there exist cases such that the true generalization gap is non-vacuous while uniform convergence fails, using an overparameterized linear regression case. 
In this paper, the authors show that such a phenomenon happens in both linear and non-linear cases and provides the threshold for the phenomenon happens. 
Overall, I think this paper is very interesting and extends the scope of generalization analysis. 
strength_and_weaknesses: Strength:
1. This paper focuses on a very important topic: generalization. 
2. This paper extends the previous results on linear cases to non-linear cases.
3. Further, the authors also propose two thresholds for the signal-to-noise ratio. Under the first threshold, UC fails, and under the second threshold, generalization fails. The two thresholds are proven to be tight.
4. The authors further provide some insights on the notion of margin, which explains how generalization works while UC fails. 

Flaws:
1. I am not sure how many technical contributions are contained in this paper. The authors could restate the theoretical contributions more carefully. For example, from the linear case to the non-linear case, which technique is the core? And how does the non-linear case differ from the other non-linear cases since the XOR case proposed in this paper is solvable? 
2. It would be more interesting if the authors could provide some difficulties when generalizing the results to general cases, which, of course, is pretty hard. 
3. Although the title claims "max margin" and "small margin", this is only discussed in the final part of the paper and has a weak relationship with the main text. 
clarity,_quality,_novelty_and_reproducibility: This paper extends the existing papers. The techniques in this paper are somehow novel. 
Besides, this paper is well-written and easy to follow. 
summary_of_the_review: Although there are some small flaws in this paper, I believe this is an interesting topic and brings some insights into the deep learning community. 
Therefore, I give a general rating of acceptence.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper develops a new type of generalization bound for both the linear classification setting and the quadratic ground truth function learned via a two-layer neural network in the non-linear setting. The main result of this paper is to show that above a certain signal-to-noise threshold, any near-max-margin classifier will generalize, while in a certain regime of the signal-to-noise threshold, uniform convergence generalization bounds are vacuous but the new generalization bound shows that memorization can coexist with generalization.
strength_and_weaknesses: Strength:

- The new generalization bound developed in this paper is in contrast to the existing uniform convergence bounds, which have been shown to be vacuous in some settings. 

- The main discovery of this paper is to show that when the SNR of the data is in a certain range, uniform convergence bounds fail but near-max-margin solutions generalize. In this case, near-max-margin classifiers contain some generalizable components and some overfitting components that memorize the data. 

Question:

- The data samples are generated by perturbing two points with random noises. What would happen if the data samples from both classes are overlapping and do not have a clear margin? 
clarity,_quality,_novelty_and_reproducibility: Paper is well-written and the presentation is clear. 
summary_of_the_review: See above
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper derives novel generalization bounds in settings where uniform convergence provably
fails. More specifically, the new bounds derived in the paper are maximum margin bounds that can still generalize for linear and two-layer network models on distributions where uniform convergence fails.

The reviewers are overall positive. They did find the paper very technical and hard to read at times. One reviewer in particular was more negative before the discussion with the authors but agreed to increase their score afterward. I will recommend acceptance but I strongly urge the authors to revise the paper to make its results more accessible to a wider audience (for instance by providing further explanation of the key results and proof techniques).
justification_for_why_not_higher_score: The paper extends prior results of Nagarajan & Kolter. It is also high technical so probably of less interest to a wider audience.
justification_for_why_not_lower_score: All reviewers agree this is worth accepting.
Decision: Accept: poster