Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence
Authors: Margalit Glasgow
Colin Wei
Mary Wootters
Tengyu Ma
Venue: ICLR 2023 poster (2023)
Keywords: generalization
uniform convergence
overparameterization
learning theory
max-margin
two-layer neural network

Abstract: A major challenge in modern machine learning is theoretically understanding the generalization properties of overparameterized models. Many existing tools rely on uniform convergence  (UC), a property that, when it holds, guarantees that the test loss will be close to the training loss, uniformly over a class of candidate models. Nagarajan and Kolter (2019) show that in certain simple linear and neural-network settings, any uniform convergence bound will be vacuous, leaving open the question of how to prove generalization in settings where UC fails. Our main contribution is proving novel generalization bounds in two such settings, one linear, and one non-linear. We study the linear classification setting of Nagarajan and Kolter (2019), and a quadratic ground truth function learned via a two-layer neural network in the non-linear regime. We prove a new type of margin bound showing that above a certain signal-to-noise threshold, any near-max-margin classifier will achieve almost no test loss in these two settings. Our results show that near-max-margin is important: while any model that achieves at least a $(1 - \epsilon)$-fraction of the max-margin generalizes well, a classifier achieving half of the max-margin may fail terribly. Our analysis provides insight on why memorization can coexist with generalization: we show that in this challenging regime where generalization occurs but UC fails, near-max-margin classifiers simultaneously contain some generalizable components and some overfitting components that memorize the data. The presence of the overfitting components is enough to preclude UC, but the near-extremal margin guarantees that sufficient generalizable components are present.

Published as a conference paper at ICLR 2023
MAX-MARGIN WORKS WHILE LARGE MARGIN FAILS: GENERALIZATION WITHOUT UNIFORM CONVERGENCE
Margalit Glasgow, Colin Wei, Mary Wootters & Tengyu Ma Department of Computer Science
Stanford University Stanford, CA 94305, USA
(mglasgow, col wwwowiwe,,,io marykw, haaryyyw..egyuuaasstttfforr.dddd
ABSTRACT
A major challenge in modern machine learning is theoretically understanding the generalization properties of overparameterized models. Many existing tools rely on uniform convergence (UC), a property that, when it holds, guarantees that the test loss will be close to the training loss, uniformly over class of candidate models. Nagarajan & Kolter (2019b show that in certain simple linear and neural- network settings, any uniform convergence bound will be vacuous, leaving open the question of how to prove generalization in settings where UC fails. Our main contribution is proving novel generalization bounds in two such settings, one linear, and one non-linear. We study the linear classification setting of Nagarajan & Kolter (2019b), and a quadratic ground truth function learned via a two-layer neural network in the non-linear regime. We prove a new type of margin bound showing that above a certain signal-to-noiss threshold, any near-max seer-max-manne max-margiin classifier will achieve almost no test loss in these two settings. Our results show that near-max- margin is important: while any model that achieves least a (1 c)-fraction of the max-margin generalizes well, a classifier achieving half of the max-man max-mnrgin may fail terribly. Our analysis provides insight on why memorization can coexist with generalization: occurs but UC fails, near-me ma--mmmaaaaaaaaea margin classifiers contain both some generalizable components and some overfitting components that memorize the data. The presence the overfitting components is enough to preclude UC, but the near-extremal margin guarantees that sufficient generalizable components are present.
show that in this challenging regime where generalization
INTRODUCTION
A central challenge of machine learning theory is understanding the generalization of overparame- terized models. While in many real-world settings deep networks achieve low test loss, their high capacity makes theoretical analysis with classical tools diffieult, sometimes impossible ZZangg et al., 2017; Nagarajan & Kolter 2019b). Most classical theoretical tools are based on uniform convergence (UC), a property that, when it holds, guarantees that the test loss will be close the training loss, uniformly over a class of candidate models. Many generalization bounds for neural
networks are built on this property, e.g. Neyshabur et al. 2015 2017b 2018): Harvey et al. (017)
Golowich et al. (2018).
The seminal work of Nagarajan Kolter (019b) gives theoretical and empirical evidence that UC cannot hold in natural overparameterized linear and neural network settings. The impossibility results of Nagarajan and Kolter are strong: they rule out even UC on the smallest reasonable algorithm- dependent family of models, that is, any possible models output by learning algorithm on typical datasets. In particular, they prove that in an overparameterized linear classification problem, models found by gradient descent will achieve small test loss, but any UC bound over these models will be vacuous. In a two-layer neural network setting, Nagarajan & Kolter (2019b) empirically demonstrate the same phenomenon for the 0/1 loss.
Many margin-basee generalization bounds do not technically fit into the category of UC bounds defined by Nagarajan and Kolter, but still may be intrinsically limited for similar reasons. Classical

---

Published as a conference paper at ICLR 2023
Year-max-margs solns do not always generalize (Prop. (.3)
mear-max-margin solns generalize (Thms 3.1 3.2
UC and polynomial margin bounds impossible
k dr captures the signal-to-noise ratio
n
(Props 3 5.4 3.5 3.6
Ki geen
Ruc
Figure Thresholds for Uniform Convergence and Generalization.
margin-based generalization guarantees bounds (see eg. Shalev-Shwartz & Ben- Ben-David (2014);
Kakade et al. (2009)) and related margin bounds for neural networks (Wei & Ma 2019a 2020
Bartlett et al. 2017] Golowich al. 2018) scale inversely polynomially in the margin size, and are typically proved via uniform convergence on surrogate loss (eg. the hinge loss or ramp loss) that upper bounds the 0/1 misclassification loss. Nagarajan and Kolter's results show that any UC bound on the ramp loss is vacuous in overparameterized linear setting, suggesting (though not proving) that classical margin bounds may not be useful. Muthukumar et al. (202T) shows empirically that such margin bounds vacuous in broader linear settings. In light of this, it is very important to develop theoretical tools to analyze generalization in settings where uniform convergence cannot yield meaningful bounds.
In this paper we establish novel bargin-based generalization bounds in regimes where UC provably fails. These bounds guarantee generalization in the extremal case where the model has near- maximal margin, and thus we call them extremal margin Indedd,Indeed, near max- max-margin solutions achievable by minimizing the logistic loss with weak fz-regularization (Wei al., 2019), and minimizing the unregularized logistic loss with gradient descent converges to a stationary points of the max- -arain objective (Lyu Li 2019: Lyu al. 2021). In linear settings, SGD converges the max- max-margin (Ncson et al. 2019).
Our results consider two settings, the linear setting of Nagarajan Kolter (019b), and commonly studied quadratic problem learned on by two-layer neural network (Wei et al., 2019 Frei et al.) 20226). In Theorems 3.I and 3.2. we prove that above a certain signal-to- egnal-to-noise threshold Kgen near- max-margin solutions will generalize. Below this threshold, max-margin solutions may not generalize (Proposition (.3). Below second higher threshold, Kige uniform convergence fails (Proposition (34)) In Figure I we illustrate these three regions; the main significance of our results is in the challenging middle region between figen and Kye where generalization occurs, but UC fails.
Additionally in this regime where UC fails, we show that classical margin bounds can only yield loose guarantees, even for the max-margin solution (Proposition 3.5) and 3.6). We prove this by showing the existence of models that achieve a large but non-near near-max max-marggin (e.g., half the max- margin), but do not generalize at all. This phase transition between good-margin and hear-max-mare cannot be captured by classical margin bounds where the generalization guarantee decays inversely polynomially in the margin. Our extremal margin bounds are fundamentally different from classical margin bounds and are not based on uniform convergence.
Prior works have also studied the challenging regime where uniform convergence does not work. In linear regression setting, Zhou et al. (2020) and Koehler et al. (202T) show that the test loss can be uniformly bounded for all low-norm solutions that perfectly fit the data (this uses the data -ependee interpolation condition to improve upon UC bounds); nevertheless, Yang al. (202T) shows that such bounds are still loose on the min-norm solution. Negrea et al. (2020) suggests an alternative framework based on uniform convergence over less complex family of surrogate models; they use this technique to show generalization in linear setting and in another high- -igh-dimensional problem amenable to analysis. To our knowledge, our results are the first instance of theoretically proving generalization in neural network setting (that is not in the NTK regime) where UC provably fails.
We leverage near-mon max- max-mngginn in a unified way for both the linear and nonlinear settings, and we hope that this approach will be useful more broadly in overparameterized settings. In the challenging regime of generalization without UC, good learned models contain some generalizable signal components and some overfitting components that memorize the data. Our main technique is to show that any
2

---

Published as a conference paper at ICLR 2023
near max- max-marre mar-in solution has to contain both signal components and overfitting components. The overfitting component causes UC to fail, but fortunately. has a reduced influence on random test example, whereas the signal component has similar influence on training and test examples.
1.1 ADDITIONAL RELATED WORK
large body of work highlights challenges in using classical statistical theory to explain generalization in deep learning. Experimental results (Zhang et al., 2017 Neyshabur et al. 201 7 point out that despite being large in traditional capacity measures such as Rademacher complexities, deep networks
still generalize well, and new explanations
needed to understand this behavior. [Belkin al. (2018)
show that similar challenges hold in kernel methods. Beyond the work of Nagarajan & Kolter (2019b), Bartlett & Long (202T) prove that in linear interpolation setting, model-dependent generalization
bounds fail for the min-norm solution. Koren et al. (2022) show that SGD can exhibit benign underfitting phenomenon where the test loss is small but empirical loss large.
One related body of work has focused on characterizing "benign overfitting", where the model overfits to noise labels of the training data but still attains good test performance. Our setting differs from benign overfitting because we study models that overfit prohibitively enough to preclude UC even with clean data. For models that overfit to noise, (i) still may be possible to for algorithn-depente notions of UC bound to explain generalization
clean data, and (ii) if the overfitting is avoided with regularization, UC bounds may also be possible. Most the results in this area concern linear models: Bartlett et al. (2020) analyze benign overfitting in regression problems by leveraging closed form expression for the min-norm solution. Muthhukmar et al. 20 Shamir (2022); [Cao et al. (202T):
Wang & Thrampoulidis 2020);; Chatterii & Long (2021) and Wang et al. (2021) study classification settings. The setting of Chatterji & Long (2021 is particularly similar to ours since it considers
the max-margin solution under Gaussians mixture. The works of Muthukumar et al. (2020) and
Shamir (2022) reveal that is often possible to have benign overfitting in classification, whereas in regression for the same covariate distribution, the overfitting would imply poor generalization. Also closely related to our work on linear classification is the work of Montanari et al.
(2019). which
asymptotically characterizes the generalization of the max-margin solution as n, overfitting in neural networks has been shown in several simple settings. Frei et al. (202a)) analyzes two-layer neural networks trained by gradient descent on studies benign overfitting for two-layer simplified convolutional network. Their techniques involve decomposing the output of the network into a sum of two terms, one involving the signal feature, and one involving the noise feature. Our techniques are very different because this decomposition is not possible for a fully connected 2-layer neural network.
00. Benign
separable data. Cao et al. (2022)
More broadly, variety of new generalization bounds have been derived in hopes of explaining generalization in deep learning. While none of these bounds have been explicitly proven to succeed in regimes where UC fails, they leverage additional properties of the training data or the optimization process and thus are not directly susceptible to the critiques of Nagarajan & Kolter (2019b). Among these are works that leverage properties such Lipschitzness of the model on the training data (Arora
et al.
2018 Nagarajan & Kolter, 2019a Wei & Ma 2019a b), use algorithmic stability (Mou et al.
2018
Li al. al. 2019a] Chatterjee & Zielinski 2022). y or information information-ttheortiec thhooretic perspectives (Negrea
et al.
2019 Haghifam et al. 2021))
Finally, body of work seeks draw connections between optimization and generalization in deep
learning by studying implicit regularization effects of the optimization algorithm (see e.g. (Gunaseka kar
al. 20177] [i et al. 2017 Gunasekar et al. 2018a Woodworth et al. 2020. Damiia al.) [022]]
HaoChen et al. 2020 Li et al. 2019b Wei et al. 2020) and related references). Most relevent in this
literature is the aforementioned work connecting gradient descent and max-margin solutions.
PRELIMINARIES
Our work achieves results in two settings. The first is a linear setting previously studied by Nagarajan & Kolter (2019b) where both the ground truth and the trained model are linear. In the second nonlinear setting, studied before by Wei et al. 20119::[e Frei et al. (2022b), the ground truth is quadratic, and the trained model is two-layer neural network. In both settings, the data is drawn from product
3

---

Published as a conference paper at ICLR 2023
1/o²
Generalization
XORR
UC Fails
XOR
1/2
Agg
Generalizztion
d/n
35 h
(2)
XOR,h (green) as function of h. Right: Regions which theorems hold, As shown this figure, our results only hold when there is sufficient overparameterizztioo that is, d 2 en for constant
Figure 2: Left: Quadratic XOR Problem. Middle: Kigen (red) and Ruc
XOR,
distribution on features involved in the ground truth labeling function, and "junk" features orthogonal to the signal. We formalize the two settings below.
Linear setting
Data Distribution. Fix some ground truth unit vector direction μ E Rd. Let x &. where
and is uniform on the sphere of radius vd - la in d - dimensions,
orthogonal to the direction μ. Let y μ² x, such that y = with probability 1/2 and -1 with probability 1/2. We denote this distribution of (x, y) on Rd x {-1,1} by Duo
Model. We learn model w E IRd that predicts 9 = sign ( where fu(()) = = wt'x.
Setting for Two-Layer Neural Network Model with Quadratic "XOR" Ground Truth
Data Distribution. Fix some orthogonal ground truth unit vector directions μl and Ag in Rd.
Let x = - E. where z ~ Uniform (11, 1|1111A0 -11, N2: 12: -#2}) and E is uniform on the sphere of radius vd 20
2 dimensions, orthogonal to the directions μl and P22 Let y = (nt x) (uZx)) x) for some orthogonal ground truth directions μ1 and μlz (see Figure leeff)) We denote this distribution of (x, y) on Rd x {-1,1} by D Du We call this the XOR problem because
(- + (z))".) For instance, if μn éj and juz = e2, then = xf - x². As be seen in Figure left), this distribution is not linearly separable, and nonlinear model to learn in this setting.
= XOR ((/1 + 122
must use
Model. Fix a 11 so that Σ. a; 0. The model is two-layer neural network with m hidden units and activation function Φ, parameterized by W Rmxdd W (which will be learned) represents the weights of the first layer and (which is fixed) is the second layer weights. The model predicts fw (x)
Di=1 a u z)., where w, Rd denotes the i' th column of W. We work with activations & of the form (b2) max (0, 2^th for [1, 2). and require that m divisible by 4
We define a problem class of distributions to be set of data distributions. In this paper, we work with the linear problem class lliner = {D (Dp.o.d ad μ Rd |||||| 1}. and the quadratic problem class P == (Dpisngaad 14 1 #22 E Rdd, |p | = 1). Here || denotes the lg norm.
We will sometimes abuse notation and say that x ~ D instead of saying that (z. v) ~ D.
Before proceeding, make some comments on the parameter settings and compare to related work.
Large dimension assumption. In both the linear and non-linear settings, our focus is an overparame- terized regime where the dimension d is at least constant factor times larger than n, the number of training samples. Such an assumption is mild relative to the assumptions made in related work, which require d w(n) (see eg. (Cao
2021 Wang & Thrampoulidis, 22200) Muthukumar et al.] 2021 Shamir 2022 Chatterji & Long 2021) on linear models; for neural networks, the closest related
works of Frei al. (2022a) and Cao al. (022) assume that d n² or stronger). When the dimen-
'The assumption that is divisible by 4 is for convenience, and he removed if large enough.
4

---

Published as a conference paper at ICLR 2023
sion is sufficiently large (in particular, at least (n))), with high probability. the max-margin solution coincides with the min-norm regression solution (see Hsu et al. (202I)), meaning the max max-margin solution can be analyzed via a closed-fone expression. Our work is fundamentally different from the work on linear classification which operates in the d = w(n) regime, because in our setting when d (n), these two solutions do not coincide.
Assumption on Data Covariance. Many works on linear classification study more general data models which allow arbitrary decay of the eigenvalues of the covariance matrix (eg. Muttuukuar et al. (20TT) Wang & Thrampoulidis (2020); Cao et al. (202T)), or variance in the signal direction, that 1s, μ o y (eg. [Shamir (2022)). We work with simpler distribution, which is still challenging.
because it defies existing analyses built on UC or closed- forsed-form solutions.
2.1 BACKGROUND AND DEFINITIONS ON UNIFORM CONVERGENCE
In this subsection, we provide some definitions from Nagarajan & Kolter (019b) on algorithm- dependent UC bounds. We also provide some definitions and background on margin bounds.
For a loss function C : R x R + R. and a hypothesis h mapping from a domain X' to R, we define the test loss on distribution D be LD (h) == (()))) v). For set of examples S {(1), se)) we define Ls (h) = En ((h(2,), De) to be the empirical loss.
Unless otherwise specified, we will use L to denote the 0/1 loss, which equals 1 if and only if the signs of the two labels disagree, that is, C(y, s/) = (ysign(y) # sign(y")).
Typically in machine learning one considers a global hypothesis class G that algorithm may explore (e.g.. the set of all two-layer neural networks). A uniform convergence bound, defined below, may hold over smaller subset H. of G, eg. the subset of networks with bounded norm.
Definition 2.1 (Uniform Convergence Bound). A uniform convergence bound with parameter cunif for a distribution D, a set of hypotheses H. and loss is a bound that guarantees that
Pr [sup (h) Ls(h)) 2 Cunit) S 4" S~D" NEH
(2.1)
uniform convergence bound can be customized algorithms by choosing H depend on the implicit bias of an algorithm. For instance, if an algorithm A favors low-norm solutions, one could choose H. to be the of all classifiers with bounded norm. Of course, 7 is too small, it may not be useful for proving generalization, because A will never output a solution in H. We formalize the notion of choosing a useful algorithm-dependent set H as follows.
Definition 2.2 (Useful Hypothesis Class). A hypothesis class H is useful with respect to an algorithm A and a distribution 'D if PrS-DD
E H| 2 3.
Remark 2.3. Our definition of a uniform convergence bound on a useful hypothesis class is essentially equivalent the definition of algorithm-dependent uniform convergence bound in Nagarajan & Kolter 2019b).
We introduce new terminology since we use it later in our results on margin bounds.
More generally, we can have generalization bounds that do not yield the same generalization guarantee for all elements of H. Instead, their guarantee scales with some property of the hypothesis h and the sample S. We call these data-deeendent bounds. Such bounds are useful the favorable property is satisfied with high probability by the algorithm of interest.
One specific type of data-dependent bound depends on the margin achieved by the classifier on the training sample. We recall the definition of margin:
Definition 2.4 (Margin). The margin yhh, S) of a classifier h sample S equals min y1(z))
In certain parameterized hypothesis classes it is useful to define a normalized margin. If Jw is h-hoomgeneous, that is. few (x) = c² (I( for a positive scalar e, we define the normalized margin
7(f,,S) = ((w, S) |
= >).
(2.2)
where we define the norm |||| equal v RiE|m [w:| [I.. where we is the i'th column of W.
5

---

Published as a conference paper at ICLR 2023
We will use (S)) denote the maximum normalized margin. When are discussing the linear problem, we let (S) be the max- max-marginn over all vectors w E R' with norm 1, that is (S) := s ((5, fw)). In the XOR problem, use y (S) to denote the max-margin over all weight matrices W E Imxx with norm 1, that y ((S) == supw:|IWils: (w):
Most classical margin bounds prove that the generalization gap can be bounded by a term that scales inversely linearly quadratically in the margin (Koltchinkki & Panchenko 2002 Kakade et al. 2009). More generally, we will call margin bounds in which the generalization guarantee scales
with ((S.w)) for constant p a polynomial margin bound. Such bounds usually rely on proving
uniform convergence for continuous loss that upper bounds the 0/1 loss. As we will show in the next section, such bounds are also intrinsically limited in regimes where UC fails on the 0/1 loss.
In contrast to this, in our work, we prove bounds for classifiers that achieve mear-maximal margins. Definition 2.5. A classifier is a (1 maax-marrin solution for S if (h,, S) 2 (1 - -))
We refer to bound that holds for (1 ----maa--marar solutions extremal margin bound.
3
MAIN RESULTS
In the following section, we state our main results for the linear and quadratic problems, and provide intuition for our findings. As illustrated in Figure [] and in more detail in Figure Sesureeright righht), our results show different possibilities for near max- max-ma solution depending on the size of x: := dØz. signal-to-noiss parameter, where a, d are as in Section 2 When is smaller than some threshold Kgenn we are not guaranteed to have learning: even near max-margin solution may not generalize. When k exceeds Kigen by an absolute constant and when o² << 1, our results show that any near max-margin solution generalizes well. Finally, we show that if к is smaller than a second threshold Kicc then uniform convergence approaches will fail to guarantee generalization. All of our results additionally include overparameterizztion condition that d 2 for constant
is pictured in Fig 2 right).
The exact thresholds Kigen and Kaz depend on the problem class of interest, but in both the lincar setting and the nonlinear setting study, we show that fine Kigen- Thus we observe regime where uniform convergence fails, but generalization still occurs for near max-margin solutions.
For the linear problem, we define the universal constants
linear linear := O and Kig Aggen
:= 1.
(3.1)
For the XOR problem with activation relu for h E [1, (1,2), we define the constants
XOR,A gen
the solution to 2 V
K
16 and NOR, =- 4. (3.2)
4 k4+
The constants
2 right) a function of h. Observe that for h (1, XOR > When h = and the activation is relu, we have have Kigen < Nic XOR, and Kigen
pictured in Figure
X
X and thus we do not expect to have a regime where uniform convergence fails, but max-margin solutions generalize. We elaborate more intuitively on why h allows for
Kigen
= Kuc
generalization without UC in Section A
Our first theorem states that when K >> Kgenn any near-max- mar-margin solution generalizes.
Theorem 3.1 Naattemal-Marghh Generalization for Linear Problem). Let 8 > O. There exist constants E E()) and c(6) such that the following holds. For any n, d, a and D E Diinear satisfying
linear + + < < 3. and d 2 then with probability 1 - -e over the randomness of training "ggnn
set S ~ Dn for any w E &Rd that is (1 -)--mx--mmaaa marxi- solution (as in Definition 2.5 have
LD(fw) Se 36d04 + nn/8
Attentive readers may observe that since >dinear = O, Theorem 3.1 can guarantee asymptotic general- nh ization for some sequences of parameters (n4, d,, 1 even when पे o (1), as long as of decays fast enough. In Theorem in the appendix, we state a more detailed version of this theorem which states the exact dependence of e and 5, yielding precise results for x. (())
Kigen

---

Published as a conference paper at ICLR 2023
We prove a similar generalization result for XOR problem learned on two-layer neural networks.
Theorem 3.2 EExtremal-Marghn Generalization for XOR on Neural Network). Let h E (1, and let
ò > O. There exist constants <(0) and c c(6) such that the following holds. For any n, d, a and XORRk + 6 and _ 2 c, then with probability - --e--/e over the training set ~ D", for any two-layer neural network with activation function relu and weight matrix W that is (1 max-marrin solution (as in Definition 2.5 we have LD(fw) S e =
D E QXOR satisfying K daz
_ 2 gen
This theorem guarantees meaningful results whenever a small enough. To see this, note that the assumptions of the theorem require that _ cc (2( If a is small enough (in terms of 8), this interval is non-empty. Further, the generalization guarantee is good if is small enough (since exp( -1/(co")) tends to 0 as a approaches 0). For instance consider a setting where d' > n, and の² d. Then our theorem guarantees that (f(ww) < 1.
Key intuitions for generalization theorems. We demonstrate the gist of the analysis for the linear problems with some simplifications. It turns out that two special solutions merit particular attention: (i) the good solution Weg that generalizes perfectly, and (ii) the bad overfitting solution Wp :2 Vndo E3 B that memorizes the "junk" dimension of the data, and satisfies
C Wb R Vndo Viles = viv d for all i. We examine the margin of the two solutions and have
do
7( 5) and 7(w,, 8) =
(3.3)
At first glance, one might conclude that when (w2g 5) < (wh. S), the max margin solution will be wh. which does not generalize. However, our key observation is that any (near) max margin solution w always contains a mixture of both Wig and wy. When the W/ component is small but non-trivial and the Wh component is large, the solution can simultancously generalize but contain a large enough overfitting component to preclude UC.
More concretely, suppose we consider the margin of a linear mixture w = aww + Buy satisfying a² + 3 so that ||l||2 1. It is easy to see that the margin on the training set is
7ww, S) = (1 S) + (7(,,
(3.4)
Meanwhile, the margin on an test example x: is only slightly affected by ws:
7w, x)) ze (w S) + Bwg x x an(wg. S) + (7 5) n
(3.5)
The effect wi x of the bad solution the test sample is is smaller than 7(w, S) by V factor because x is high dimensional random vector, and thus mostly orthogonal to wp. Therefore, even if the margin on the training set mostly stems from the bad overfitting solution, that is, an S) < (7 S). the model may still generalize long as (1g S) 2 (7 /
The optimal a, 3 satisfying a² + 32 that maximize the margin turns out to be proportional the (( yielding a max-margin of Vf(wg. SY² + 7 S)2² ~ original margin: 3)
Therefore, we have ( 8) In other words, we should expect reasonable generalization
(S) S1=
of near-max margin solutions as long as S(w..S) > 12/ which by eq. 3.3 occurs when n d
5(W,.S)
> 1.
In Appendix A, we describe the challenges that arise when adapting these intuitions to nonlinear setting, and our techniques for overcoming them.
Before proceeding to our lower bounds, observe that a typical margin bound for the linear setting
would yield (CD(w)- (s(w)) <
2|x]
2vdo /1+1/x which is at least 2 for S Aig
linear 1.
vn
Moore precisely, we will choose us he the rescaled min-norm vector satisfying ş. ws = ys for all This distinction is important the case when is only a constant factor larger than n, and the solution Vndo Σ, m does necessarily correctly classify the training data.
7

---

Published as a conference paper at ICLR 2023
We now proceed to present our lower bounds, which show when near max- max-margin solutions may not always generalize, and when UC bounds and polynomial margin bounds are impossible.
If K Kggnn it is possible that near-max margin solution does not generalize at all. Since Kigen 0 in the linear setting, we only state this result for the XOR problem.
Proposition 3.3 (Region where Max- Max-Margin Generalization not Guaranteed). Let h E (1.2), and let e > O. There exists a constant c c(e) such that the following holds. For any n. d, a and D E o satisfying gon XOR.B and 2 c, with probability 1 - 3e- over S ~ DD, there exists some W with [W|| = and (fw, .) 2 (1 - (S) such that (D(Sw) = 2"
Theorems 3.2 and Prop. 3.3 demonstrate that in the XOR problem, there is a threshold in K. above which generalization occurs. i: is above this threshold, we achieve generalization when o² << 1.
The next proposition states that when K. < Kuc, any dlgorith--depende will be vacuous, that is, its generalization guarantee will be arbitrarily close to We state our results for the linear and XOR neural network settings together; we state the more complicated XOR result in full and then mention how the linear result differs.
uniform convergence bounds
Proposition 3.4 (UC Bounds are Vacuous). Fix any l E (1,2), and ó > O. For any d, and D E DXOR if gige if XOR. + 8 S K S Kicc K.XOR, - ô, there exist strictly positive constants e = <(6) and e)-max-marge two-layer neural network fw for any S E (R& x - Let HH be any hypothesis class that is useful for 'D (as in Definition (.2). Suppose that Cunif is a uniform convergence bound for 'D and H that Prs-D" [SuPhEH (h) Ls(hh) 2 Cunit] S 1/4. Then if d 2 c and n > C, we must have n
c c= =()) such that the following holds. Let A be any algorithm that outputs
Eunif 11 1 6.
A similar result holds for the linear problem with g.linear 8 < K. Kiwe
I.lnear
8 and any D Dlinear
In this case we achieve the guarantee that Cunit - 36de e n/8
Prop. 3.4 is proved using the same technique in Nagarajan & Kolter (011b)) we show that with high probability over S ~ DDm the hypothesis A(S) has good generalization, but on an "oppositite" dataset (S)) with the junk components reversed, the empirical error of A(S)) is close 1. This large gap between empirical error and generalization forces éunif-alg to be large.
Further extending this technique, we can also show the limitations of classical polynomial margin bounds which achieve an bound that scales inversely polynomially with >(h, S). We show that with high probability over S ~ D the hypothesis ((v(S)) has large margin on the set (a constant fraction times the max-margin), but poor generalization on D. Since any polynomial margin bound cannot predict much better generalization for the max-margin solution than for a solution with a constant-fraction of the max-margin, we conclude that any such margin bound is far from showing good generalization for the max- -argin solution.
One subtlety to this approach is that here (unlike in the work of Nagarajan & Kolter (2019b)), the "opposite" data set (S)) is defined to be the data set with the signal features reversed. Thus we can only show the limitations of polynomial margin bounds that are useful for both 'D and for its "oppostite" distribution (D), which has the opposite ground-truth vector(s), which is a slightly stronger assumption than in the work of Nagarajan & Kolter (0019)). Formally, if D Diinear then we define (DD) = Dlincar -p.o
p.o
If D = Mi..2.0 then (D) == XOO
P2.A1.0'
The following results state that if Kuc. then certain types of margin bounds cannot yield better than constant test loss on even the max-margin solution.
Proposition 3.5 (Polynomial Margin Bounds Fail for Linear Problem). Fix ò O. For any n. d, and D E D such that ,.lincar
Agen + 8 < K < linear - 8 and d 2 c, the following holds. Let A be any algorithm so that A(S) outputs a (1 -) mmmmx--mrrinn solution for any S E (IR. x =))
'We believe considering such types of margin bounds is natural. Indeed, for most problems, the designer of the generalization bound would not know in advance the ground truth distribution, but might know that the data comes from some problem class, e.g., linearly separable distributions, or linearly separable distributions with a sparse ground truth vector. In such cases, they would likely have to design a generalization bound that holds for data coming from two distributions with opposite ground truths.
If we make this same stronger two-distribution assumption in Prop. 3.4 we can additionally rule out one-sided UC bounds, which only upper bound LD Ls.
8

---

Published as a conference paper at ICLR 2023
Let H. be any hypothesis class that is useful for (as in Definition 2.2 Suppose that there exists an polynomial margin bound of integer degree p. that is, there some G that satisfies for D {D, (D)).
both Diinear and D -H.o-
G
Pr
sup L (h) 2
S
S-D=
LiEH
7(, Syp
Then with probability solution, that is, constant.
3e over S ~ DD", the margin bound is weak even on the max-margin
G (T
max
t
364 n/8
3x which is more than an absolute
This theorem says that no polynomial margin bound will be able to show that the test error of the max- mar-mnrgin solution is less than absolute constant. We know however from Theorem 3.1 that in this same regime, the test error of the max margin solution can be arbitrarily small for small enough a. Thus no polynomial margin bound can predict this behaviour.
The attentive reader again may notice that & + O as n. and d grow, but generalization occurs, any such margin bound is vacuous, in that G (") 1. In Prop ??, we prove more precise version,
..linear and k Illeaar yielding the exact dependence of and on the gap between & and the boundaries Kige
We achieve similar result in the XOR setting.
Proposition 3.6 (Polynomial Margin Bounds Fail for XOR on Neural Network). Fix an integer c(p,e) e) such that the following holds for any d, and
p 1. and any x.XOR, + < K < Kag X.ORk -, d and 2 Let H be any hypothesis class
O. There exists
D NXOR with Figen
such that for D E {D, (D))
Pr [all (1 -amxx-aargin two-layer neural networks fw for S lie in H. 2 3/4.
SwIr
Suppose that there exists polynomial margin bound of degree pt that is, there is some G that satisfies for D {D, (D))),
G
Pr sup (h) -cs(h)
S
SwDD
LicH
7(h, SyP
Then with probability -e---ng n/c over S Dn, on the max-margin solution, the generalization guarantee is no better than 1, that is, 7ー( 1.
The polynomial margin impossibility results slightly weaker for the XOR problem. Namely, the hypothesis class H we consider larger in the XOR problem: it must contain with probability any near max-margin solution, instead of just the one output by A.
Remark 3.7.
The combination of our generalization results and our margin possibility results suggest a phase transition how the margin size affects generalization. If the margin is near-maximal, Theorems 3.] and Prop. 3.2 show that we achieve generalization. Meanwhile, the proof of Props 3.5land 3.6 suggest that solutions achieving constant factor of the maximum margin may not generalize.
The proofs of all of our results concerning the linear problem are given in Section C The proofs for the XOR problem are Section
CONCLUSION
In the work, we give novel generalization bounds in settings where uniform convergence provably fails. We use a unified approach of leveraging the extremal margin in both linear classification setting and non-linear two-layer neural network setting. Our work provides insight on why memorization can coexist with generalization.
Going beyond our results, is important to find broader tools for understanding the regime near the boundary generalization and no generalization. We conclude with several concrete open directions in this vein. One question is how to prove generalization without UC when d n, but the model itself (e.g. a neural network) is overparameterized, and thus can still overfit to the point of UC failing. A second direction asks if we prove similar results in the non-linear network setting for the solution found by gradient descent, this solution is not a near max max-mane mar-mn solution. Indeed, in a non-convex landscape, it not guaranteed that that gradient descent will find the max-margin solution.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank Jason Lee for helpful discussions. MW acknowledges the support of NSF Grant CCF- 1844628 and Sloan Research Fellowship. TM supported by NSF IIS 2045685.
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. arXiv preprint 10X.v:8802.0522 2018.
Peter Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalieed margin bounds for neural networks. arXiv preprint (Xtv:1706.08498, 2017.
Peter I. Bartlett and Philip M Long. Failures of model-dependent generalization bounds for least-norm interpola- tion. Journal of Machine Learning Research, 22 2021.
Peter L Bartlett, Philip M Long, Gabor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117748):330633330777 2020.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. understand deep learning we need understand kernel learning. In International Conference on Machine Learning (ICML), 2018.
Yuan Cao, Quanquan Gu, and Mikhail Belkin, Risk bounds for over-parameterized maximum margin clas- sification on sub-gaussian mixtures. Advances in Neural Information Processing Systems, 34:8407-8418, 2021.
Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. arXiv preprint 220.002202006666, 2022.
Satrajit Chatterjee and Piotr Zielinski. On the generalization mystery in deep learning. arXiv preprint arXiv:2203. /0036, 2022.
Niladri S Chatterji and Philip M Long. Finitc-sample analysis of interpolating lincar classifiers in the overparam- eterized regime. Journal of Machine Learning Rexearch, 22(119)):-30. 2021.
Alex Damian, Tengyu Ma, and Jason Lee. Label noise sgd provably prefers flat global minimizers, 2021.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without lincarity: Neural network classifiers trained by gradient descent for noisy linear data. arXiv preprint arXiv:2202.05928, 2022a.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Random feature amplification: Feature learning and generalization in neural networks. arXiv preprint (rxXi::2022.06626 2022h.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297-299, PMLR, 2018.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
Suriya Gunasekar, Jason Lee. Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. arXiv preprint 1cXiv:180.008244 2018a.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461 19711, 2018b.
Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, and Dan Roy. Towards a unified information- thcoretic framework for generalization. Advances in Neural Information Processing Systems, 34, 2021.
Jeff 7, HaoChen, Colin Wei, Jason D Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint 2xXi:2006.006680 2020.
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension bounds for piccewise linear neural networks. In Conference Learning Theory, pp. 1064-1068. PMLR, 2017.
Daniel Hsu, Vidya Muthukumar, and Ji Xu. On the proliferation of support vectors in high dimensions. In International Conference on Artificial Intelligence and Statistics, pp. 91-99. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2023
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds. margin bounds, and regularization. In Advances in Neural Information Processing Systems (NeurIPS), 2009.
Frederic Knehler, Lijia Zhou, Nathan Srebro, al. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting. Advances in Neural Information P Processing Systems, 34:20657-20668, 2021.
Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1- 50, 2002.
Tomer Koren, Roi Livni, Yishay Mansour, and Uri Sherman. Benign underfitting of stochastic gradient descent. arXiv preprint arXiv: 13361, 2022.
Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. arXiv preprint 1902v09902.0066 2019a.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization over parameertteee matrix sensing and neural networks with quadratic activations. arXiv preprint arXiv:1112.09003, pp. 2 2-47, 2017.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In Advances in Neural Information Processing Systems, pp. 11669-11680, 2019b.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint 3906::900.0555 2019.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34, 2021.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arXiv preprint 1rXiv:19/ 2019.
Wenlong Mou, Liwei Wang. Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 605 638. PMLR, 06 09 Jul 2018. URL hEEp: /ttpccpp/proccc...ieo
mlr wwtppppssssssseeepe mou1 8a. htm.1
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1):67-83, 2020.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression overparameterized regimes: Does the loss function matter? Journal of Machine Learning Research, 22(222))1-69. 2021.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3051-3059. PMIR, 2019.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds deep networks via generalizing noise-resilience. arXiv preprint arXiv:/905. 13344, 2019a.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. arXiv preprint arxiv: 2019b.
Jeffrey Negrea. Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Information- theoretic generalization bounds for sgld via data-dependent estimates. Advances Neural Information Processing Systems, pp. 11013-1002, 2019.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors, In International Conference on Machine Learning, pp. 7263-722 7272. PMLR, 2020.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956, 2017a.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srehro. A pac-hayesian approach to npemtielyy-oormalieedd margin bounds for neural networks. arXiv preprint arXiv: /000.:/770000000 09564, 2017b.
11

---

Published as a conference paper at ICLR 2023
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over over-earameenn paramettiizzonn generalization of neural networks. arXiv preprint 188i 12076, 2018.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms.
Cambridge university press, 2014.
Ohad Shamir. The implicit bias of benign overfitting. arXiv preprint arXiv:2201.1199) 2022.
Roman Vershynin. High-dimensionul probubility: An introduction with applications in data science, volume 47.
Cambridge university press, 2018.
Ke Wang and Christos Thrampoulidis. Binary classification of gaussian mixtures: abundance of support vectors, benign overfitting and regularization. arXiv preprint (:X:::2011.014444 2020.
Ke Wang. Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in multiclass classification: All roads lead interpolation. Advances in Neural Information Processing Systems, 34, 2021.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmenta- tion. In Advances in Neural Information Processing Systems, pp. 9722-9733, 2019a.
Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification via an all-layer margin. arXiv preprint arXiv:1910.04284, 2019b.
Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification via an all-layer margin. In International Conference Learning Representations (ICLR), 2020.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets their induced kemel.. In Advances in Neural Information Processing Systems, pp. 9709-9721, 2019.
Colin Wei, Sham Kakade, and Tengyu Ma. The implicit and explicit regularization effects of dropout. arXiv preprint arXiv:2002. 12915, 2020.
Blake Woodworth, Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. Conference on Learning Theory (COLT), 2020.
Zitong Yang, Yu Bai, and Song Mei. Exact gap between generalization error and uniform convergence in random feature models. International Conference on Machine Learning, pp. 11704-11715. PMIR, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations (ICLR), 2017.
Lijia Zhou, Danica J Sutherland, and Nati Srehro. On uniform convergence and low-norm interpolation learning. Advonces Neural Information Processing Systems, 33:8667-6877, 2020.
12


Reviews:
[{"review_id": "mE2nhRjj3r", "reviewer": "Reviewer_qDFy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "See above", "strength_and_weaknesses": "Strength:\n\n- 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. \n\n- 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. \n\nQuestion:\n\n- 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? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Hik2CQUKdm", "reviewer": "Reviewer_pEEx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is an extension of the existing paper by Nagarajan & Kolter. \nPreviously, 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. \nIn 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. \nOverall, I think this paper is very interesting and extends the scope of generalization analysis. ", "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. \nTherefore, I give a general rating of acceptence. ", "strength_and_weaknesses": "Strength:\n1. This paper focuses on a very important topic: generalization. \n2. This paper extends the previous results on linear cases to non-linear cases.\n3. 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.\n4. The authors further provide some insights on the notion of margin, which explains how generalization works while UC fails. \n\nFlaws:\n1. 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? \n2. 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. \n3. 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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8ePJ_MChY7", "reviewer": "Reviewer_DBpB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\nThis is a pure theory paper. The contributions are the quantification of the aforementioned effects, together with their proofs and discussions.", "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. ", "strength_and_weaknesses": "Strengths\n- 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.\n- The existence of regimes where different generalization bounds apply is very interesting and to some extent unexpected.\n- In addition to linearly separable data, a variant of the XOR problem is analyzed.\n\nWeaknesses\n- 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.\n- Reproducibility: The proofs are kept rather short. In consequence, I am unable to confirm the correctness of the results.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "4UseuJBz6r", "reviewer": "Reviewer_TxXm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "summary_of_the_review": "Overall this paper is well written. More discussions should be added according to my comments in the weakness section.", "strength_and_weaknesses": "\nStrength:\n* This paper provides a new margin-based generalization bound for linear and two-layer network models on certain data set.\n* This paper shows that the max-margin solution will contain both generalizable and overfitting components.\n* This paper clearly identifies the settings that the margin-based results and uniform convergence based results will give vanishing or vacuous generalization bound.\n\nWeakness:\n* 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.\n\nChatterji, N. S., & Long, P. M. (2021). Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime. J. Mach. Learn. Res., 22, 129-1.\n* 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?\n* 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?\n* 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). \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster