Feature selection and low test error in shallow low-rotation ReLU networks
Authors: Matus Telgarsky
Venue: ICLR 2023 poster (2023)
Keywords: gradient descent
gradient flow
margin maximization
test error
neural collapse
generalization

Abstract: This work establishes low test error of gradient flow (GF) and stochastic gradient descent (SGD) on two-layer ReLU networks with standard initialization scale, in three regimes where key sets of weights rotate little (either naturally due to GF and SGD, or due to an artificial constraint), and making use of margins as the core analysis technique. The first regime is near initialization, specifically until the weights have moved by $\mathcal{O}(\sqrt m)$, where $m$ denotes the network width, which is in sharp contrast to the $\mathcal{O}(1)$ weight motion allowed by the Neural Tangent Kernel (NTK); here it is shown that GF and SGD only need a network width and number of samples inversely proportional to the NTK margin, and moreover that GF attains at least the NTK margin itself and in particular escapes bad KKT points of the margin objective, whereas prior work could only establish nondecreasing but arbitrarily small margins. The second regime is the Neural Collapse (NC) setting, where data lies in well-separated groups, and the sample complexity scales with the number of groups; here the contribution over prior work is an analysis of the entire GF trajectory from initialization. Lastly, if the inner layer weights are constrained to change in norm only and can not rotate, then GF with large widths achieves globally maximal margins, and its sample complexity scales with their inverse; this is in contrast to prior work, which required infinite width and a tricky dual convergence assumption.


FEATURE SELECTION AND LOW TEST ERROR IN SHALLOW LOW-ROTATION RELU NETWORKS
Matus Telgarsky
m
ABSTRACT
This work establishes low test error of gradient flow (GF) and stochastic gradient descent (SGD) on two-layer ReLU networks with standard initialization scale, in three regimes where key sets of weights rotate little (either naturally due GF and SGD, or due to an artificial constraint), and making use of margins as the core analysis technique. The first regime is near initialization, specifically until the weights have moved by ((m)), where m denotes the network width, which is in sharp contrast to the ((1) weight motion allowed by the Neural Tangent Kernel (NTK); here it is shown that GF and SGD only need a network width and number of samples inversely proportional to the NTK margin, and moreover that GF attains at least the NTK margin itself and in particular escapes bad KKT points of the margin objective, whereas prior work could only establish nondecreasing but arbitrarily small margins. The second regime is the Neural Collapse (NC) setting, where data lies in well-separated groups, and the sample complexity scales with the number of groups; here the contribution over prior work is an analysis of the entire GF trajectory from initialization. Lastly, if the inner layer weights are constrained to change in norm only and can not rotate, then GF with large widths achieves globally maximal margins, and its sample complexity scales with their inverse; this in contrast to prior work, which required infinite width and a tricky dual convergence assumption.
INTRODUCTION
A key promise of deep learning is automatic feature learning: standard gradient methods are able to adjust network parameters so that lower layers become meaningful feature extractors, which in turn implies low sample complexity. As running illustrative (albeit technical) example throughout this work, in the 2-sparse parity problem (cf. Figure (]. networks near initialization require d² /e samples to achieve e test error, whereas powerful optimization techniques are able to learn more compact networks which need only d/c samples (Wei et al. 2018). It is not clear how to establish this improved fcature learning ability with a standard gradient- gradient-based optimization method; for example, despite the incredible success of the Neural Tangent Kernel (NTK) in proving various training and test error guarantees (Jacot et al.] 2018 Du et al. al.] 20118b: Allen-Zhu et al.) 2018 Zou et al.) 2018 Arora al. 2019 Li & Liang 2018 Ji & Telgarsky 2020b; Oymak & Soltanolkotabi 2019)
ultimately the NTK corresponds to learning with frozen initial random features.
The goal of this work is to establish low test error from random initialization in an intermediate regime where parameters of individual nodes do not rotate much, however their change in norm leads to selection of certain pre-existing features. This perspective is sufficient to establish the best known sample complexities from random initialization in variety of scenarios, for instance match- stochastic gradient
ing the d2 /c within-kernel sample complexity with a computationally-effiie descent (SGD) method, and the beyond-kerne d/c sample complexity with an inefficient gradient flow (GF) method. The different results are tied together through their analyses, which establish not merely low training error but large margins, classical approach to low sample complexity within overparameterized models (Bartettt 1996). These results will use standard gradient methods from standard initialization, which is in contrast to existing works in feature learning, which adjusts the optimization method in some way (Shi et al. 2022 Wei et al. 2018). most commonly by training the inner layer for only one iteration (Daniely & Malach 2020
Abbe et al., 2022 Barak et al. 2022

---

Damian et al. 2022), and typically not beating the within-kernel d? /e sample complexity the 2-sparse parity problem (cf. Table
Contributions. There are four high-level contributions of this work. The first two consider net- works of reasonable width (e.g,, O(d)) for 2-sparse parity). and are the more tractable of the four. In these results, the network parameters can move up to O(ym) where m is the width of the network; this is sharp contrast to the NTK, where weights can only move by (1). The performance of these first two results is measured in terms of the N7K margin Tiu. a quantity formally defined in Assumption 1.2. These first two contributions are as follows.
1. Non-trivial margin KKT points. Prior work established that features converge in strong sense: features and parameters converge to KKT point of natural margin objection (cf. Section I.I
Lyu & Li 2019 Ji & Telgarsky (020a)). Those works, however, left open the possibility that the limiting KKT point is arbitrarily bad; instcad, Theorem 2.1 guarantees that the limiting GF margin is least / /496, where 7hu is distribution deeribbution-deeeddeen constant.
2. Simultaneous low test error and low computational complexity. Replacing GF with SGD in the preceding approach leads to computationally efficient method. Applying the result- ing guarantees in Theorem 2.3 to the 2-sparse parity problem yields, as detailed in Table a method which saves a factor d against prior work with sample complexity d and Tac- tor 1/c in computation against work with sample complexity d² /e². Moreover, Theorem 2.3 guarantees that the first gradient step moves parameters by / /m and formally exits the NTK.
The second two high-level contributions require intractable widths (e.g.. 2d)) but are able to achieve much better global margins Yho which as detailed in Sections L.1 and possible under strong assumptions or unrealistic algorithmic modifications.
were previously only
3. Neural collapse. Theorem 3.2 establishes low sample complexity in the neural collapse (NC)
regime (Papyan et al.) 2020), where data are organized in well-separated clusters of common label. By contrast, prior work did not analyze gradient methods from initialization, but instead the relationship between various optimality conditions (Papyan et al., 2020; Yaras et al. 2022 Thrampoulidis et al. 2022). The method of proof is establish global margin maximization of GF; by contrast, for any type of data, this was only proved in the literature with strong assumptions and modified algorithms (Wei al., 2018 Chizat Bach, 2020 Lyu al. 2021)
4. Global margin maximization for rotation-free networks. To investigate what could be pos- sible, Theorem 3.3 establisses global margin maximization with GF under restriction that the inner weights can only change in norm, and can not rotate; this analysis suffices to achieve d/c sample complexity on 2-sparse parity, as in Table I and the low-rotation assumption backed by preliminary empirical evidence in Figure 2
As purely technical contributions, this work provides new tools analyze low-width networks near initialization (cf. Lemmas B.4] and C.4). a new versatile generalization bound technique (cf. Lemma C.5). and a new potential function technique for global margin maximization far from ini- tialization (cf. Lemma B.7 and applications thereof).
This introduction concludes with notation and related work, Section Sastom/[collee collects the KKT point and low computation guarantees, Section 3 collects the global margin guarantees, Section 4 provides concluding remarks and open problems, and the appendices contain full proofs and additional tech- nical discussion.
1.1 NOTATION
Architecture and initialization. With the exception of Theorem 3.3 the architecture will be a 2-layer ReLU network of the form x + F(x; W) = (u))(() a"o(Vx), where a(2) = max (0, =) the ReLU, and where a E Rm and V E RRxd have initialization scale roughly matching pytorch defaults: a NN/mm//4 (m iid Gaussians with variance 1//m) and V Nmxa/ / dd/m (m x d iid Gaussians with variance 1/(d/m))); in contrast with pytorch, the layers approximately balanced. These parameters (a, V) will be collected into tuple W
2

---

(a. V) R xR R=x(d+1), and for convenience per-node tuples wy (aj, 0ÿ) E ExR R+t1 will often be used well.
Given a pair (a, y) with æ E R and y E {+1}, the prediction or unnormalized margin mapping is p(r, y; W) = yF(;; W) yaaooVV (VV);; when examples ((z,, y:)) are available, simplified notation ps (W) := p(z,, y:: W) often used, and moreover define a single-node variant p: P:(wy) ==
(1) Throughout this work, || S 1, and unmarked norms Frobenius norms.
SGD and GF. The loss function will be either the exponential loss (e)p(2) exp(-2), the logistic loss (z) = 1n(1 + exp(-2)); the corresponding empirical risk R is
R(p(W))
(()(WW),
which used p(W) == (Pi(W).... (W)) E R". The two descent methods are
W++1 W, nyww (W.)),
stochastic gradient descent (SGD),
(1.1)
W, = - W/ - Uw R R(w(W)))
gradient flow (GF),
(1.2)
dt
where ô and ô are appropriate generalizations of subgradients for the present nonsmooth nonconvex setting, detailed as follows. For SGD, ô will denote any valid element of the Clarke differential (i.e., measurable selection); for example, (z; W) =(a(Vz), E, a, (v)x)e_)) where ej denotes the jth standard basis vector, and o (u]Jas)) E [0, 1] is chosen in some consistent and mea- surable way, for instance chosen by pytorch. For GF, å will denote the unique minimum norm element of the Clarke differential; typically, GF is defined as a differential inclusion, which agrees with this minimum norm Clarke flow almost everywhere, but here the minimum norm element is equivalently used to define the flow. Details of Clarke differentials and corresponding chain rules are differed to the now-extensive literature for their use in margin analyses (Lyu Li 2019 & Telgarsky 2020a Lyu et al.) 202T).
Due to clutter, the time indices (written as W, or (t)) will often dropped.
Margins. To develop the margin notion, first note that that F and y) are 2-homogeneous in W. meaning F(x; = ca ca'o(cVz))
Fx; ; W) for any x E Id and c 2 0 (and (c(W)) = (W)). It follows that F(x; W)) || F(x; W[],, and thus F and ps scale quadratically in [W], and makes sense to define a normalized prediction mapping Pú: and margin y as
Ps (W) |
7() min, (:WW) min (WW).
P. (W)
[
Due to nonsmoothness, 7 can be hard to work with, thus, following Lyu & Li 2011)) define the smoothed margin and the normalized smoothed margin 7
7(W)= = (nR(w)) =t- { =(cee(m)))
(WW) = 7(W)
||]
where key result is that is eventually nondecreasing (Lyu & Li 2019). These quantities may look complicated and abstract, but note for Eep that (WW) == In (2, exp(-p: (W))). An interesting
technical consideration is that normalization by | can be replaced by ||a|| [|V]] or E, ||ر,,ر1|
as appears throughout the proofs of Theorems 2.1 3.2 and 3.3
Corresponding these definitions, the global max margin assumption is that some shallow network can achieve a good margin almost surely over the distribution.
Assumption 1.1. There exists Ya > 0 and parameters (k)) with |all| s and || so that almost surely over the draw of any pair (z, v), then y Ex a Ya-
The & norm on a is due to 2-homogeneity: for any 2-homogeneous generalized activation and parameters (wy) organized into matrix W E md+11) then Σ, (w
3

---

(a) Trajectories ((ayly)))², with 16.
(b) Trajectories (laylu,)5= with m 256.
Figure 1: Two-dimensional projection of = 64 samples drawn from the 2-sparse parity distribution in d 20 dimensions (cf. Proposition| I.3). with red and blue circles respectively denoting negative and positive examples, Red paths correspond to trajectories (ay Juy across time with dj < 0, whereas blue paths have aj
(ll,s,l1/1114 ()) ( ((1r/ //|r a)), and in particular E, 1|/ 1. This use of the & norm is standard in works studying global margin maximization, see for instance (Chizat & Bach 2020 Proposition 12, optimality conditions). Near initialization, the features have not changed much, and it is therefore reasonable to consider second margin definition as linear predictors on top of the random initial features.
Assumption 1.2. There exists V/n > O and weight mapping 0 Rd+1 + Rd+1 with 0(w) = 0 whenever | 2 2 and [[0(w)) S otherwise, so that almost surely over the draw (æ, y). then Eu--No (0(w). 0,,,((;;;)) w)) 2 Your where w = (a, ~ No means a ~ N and v Na/ / and p(z, 1/: w) p(., yi (a, v)) y as before.
Assumption 1.2 may seem overly technical, but by taking an expectation over initial weights, it can not only seen as an infinit-wwdth linear predictor over the initial features, but moreover is deterministic condition and not random variable depending on the sampled weights. This assumption was originally presented by Nitanda Suzuki (2019) and later used (Ji & Telgarsky, 2020b); follow-up work with similar proof techniques made the choice of using kiite-width assumption which is a random variable (Chen et al. 2019)..
The 2-sparse parity problem, finally formally defined in Proposition 1.3 follows and depicted in Figure D allows significantly different estimates for Assumption I.1 and Assumption 1.2 A notable feature of this version, in contrast to prior work, is that only the support of the distribution matters.
Proposition 1.3, Consider any 2-sparse parity data distribution: inputs are supported on Ha == {+1/ Vayd, and for any E Ha, the label is the product of two fixed coordinates == dx, with a + Then Assumption 1.2 holds with 7/aa 2 50a and Assumption holds with 7 2 Vad
Lastly, following (Lyu & Li 2019) but simplified for the 2-homogeneous case, given examples ((x;, 1:)) then parameters W (a, V) are KKT point if there exist Lagrange multipliers (A1...., An) with X; 2 O and X; > 0 only if (W) = 1, and moreover, for every j. then aj = E, (uJx:) and 0j E a; Σ, (( where å, denotes the Clarke differential with respect to tj. Call W KKT direction if there exists scalar Lastly, the margin of a KKT point W is [|?, and the margin of a KKT direction is the margin of the corresponding KKT point; further details on these notions are deferred Appendix B.
0 so that rW is KKT point.
1.2 FURTHER RELATED WORK
The concept and analytical use of margins in machine learning originated in the classical perceptron convergence analysis of Novikoff (1962). The SGD analysis in Theo- rem 2.3 well as the training error analysis in Lemma were both established with variant
Margin maximization.
4

---

Reference
Algorithm
Technique
m
n
Ji & Telgarsky
2020b)
SGD
perceptron
dB
d' fe
d² /
Theorem
2.3
SGD
perceptron
d2
d3 /
d2
Barak 2022)
2-phase SGD
correlation
(1))
d' /22
d d2/e2
Wei et al. 2018)
WF+noise
margin
00
d/c
00
Chizat & Bach 2020)
WF
margin
00
d/c
o
Theorem 3.3
scalar GF
margin dd/2
d/c
Table 1: Performance on 2-sparse parity by variety of works, loosely organized by technique; see Section 1.2 for details. Briefly, m denotes width, n denotes total number of samples (across all iterations), and & denotes the number of algorithm iterations. Overall, the table exhibits many tradcoffs, and there is no single best method.
of the perceptron proof; similar perceptron-based proof' appeared before (ji & Telgarsky 2020b Chen al. 2019 however they required width 1/7 unlike the 1 1/7 here, and moreover the proofs themselves were in the NTK regime, whereas the proof here is not.
Works focusing on the implicit margin maximization implicit bias of descent methods are more
recent. Early works on the coordinate descent side are (Schapire et al. 1997 Zhang & Yul 2005
Telgarsky 2013); the proof here of Lemma C.4Juses uses roughly the proof scheme in Telgarsky 2013).
More recently, margin maximization properties of gradient descent were established, first showing global margin maximization in linear models (Soudry et al.] 2017; Ji & Telgarsky 2018b), then showing nondecreasing smoothed margins of general homogeneous networks (including multi-layer ReLU networks) (Lyu & Li. 2019), and the aforementioned global margin maximization result for 2-layer networks under dual convergence and infinite width (Chizat & Bachh 2020). The potential
functions used here in Theorems 3.2 and [33 use ideas from (Soudry et al. 2017 Lyu & Li 2019
Chizat & Bach 2020), but also the shallow linear and deep linear proofs of Ji & Telgarsky 2019
2018a).
Feature learning. There are many works in feature learning, a few also carrying explicit guaran- tees on 2-sparse parity are summarized in Table An early work with high relevance the present work is (Wei et al. (2018), which in addition to establishing that the NTK requires (dd /c) samples whereas (dde)) suffice for the global maximum margin solution, also provided a noisy Wasserstein Flow (WF) analysis which achieved the maximum margin solution, albeit using noise, infinite width, and continuous time to aid in local search. The global maximum margin work of CChizat Bach (020)) was mentioned before, and will be discussed in Section 3 The work of Barak et al. (2022) uses a two phase algorithm: the first step has a large minibatch and effectively learns the support of the parity in unsupervised manner, and thereafter only the second layer is trained, convex problem which is able to identify the signs within the parity; as in Table this work stands alone in terms of the narrow width it can handle. The work of (Abbe et al. 2022) uses similar two-phase approach, and while it can not learn precisely the parity, it can learn an interesting class of "stair- case" functions, and presents many valuable proof techniques. Another work which operates in two phases and can learn an interesting class of functions is the recent work of (Damian et al. 2022); while it can not handle 2-sparse parity explicitly, it can handle the Hermite polynomial analog (prod- uct of two hermite polynomials). Other interesting feature learning works are (Shi et al. 2022 Bai
Lee 2019
Allen-Zhu & Li 2020).
2
Low TEST ERROR WITH MODEST-WIDTH NETWORKS
This section states the aforementioned results for networks of width 2(1 ((1/2)), which be small: as provided by Proposition 1.3] this width is ((d2) for the 2-sparse parity problem. This section will first give guarantees for GF, establishing via Theorem 2.1 and Corollary 2.2 that non-trivial KKT points are achieved. Similar ideas will then be used to give fully-tractable SGD approach in Theorem 2.3 To start, here is the low test error and large margin guarantee for GF.
Theorem 2.1. Suppose the data distribution satisfies Assumption 1.2 for some Yia > and the GF (640)((n/)) Thkk
curve (W,) 2220 uses E {Loxps [ing] on an architecture of width m 2
Then, with
5

---

probability at least 156, there exists with [[; Woll You fuvym/32 that, for all 2 t,
7(W))
Yau
and
Prip(æ, ys W.
S
In(n)
In
3
||a||| [[all
2048
ny
n
and moreover lim inf (W,) = lim inf min, (.W.. Tht 21|a,11-11, 4096
Before sketching the proof, one interesting comparison is leaky ReLU convergence analysis on a restricted form of linearly separable data due to et al. (202I). That work, through an extremely technical and impressive analysis, establishes convergence to a solution which is equivalent to the best linear predictor. By contrast, while the work here does not recover that analysis, since Ya = ((70) where "Nu is the linear separability margin (cf. Proposition B.I.. then the margin and sample complexity achieved here are within constant factor of those in (Lyu et al. (021), but via simpler and more general analysis (dropping the additional data and initialization conditions).
The proof of Theorem 2.1 is provided in full in the appendices, but has the following key com- ponents. The main tool powering all results in this section, Lemma [B.4] can be roughly stated as follows: gradients at initialization are aligned with a fixed good parameter direction B E fgmx(d+1)
with |0]| S 2, meaning 00 (Wo)) 2 Yma / mm/2 2, and moreover nearly the same incquality holds
with Wo replaced by any W E mx=x((+1) with JW- Woll I %oa Vm.mm. This is a form of Polyak- Lojasiewicz inequality, and guides the gradient flow in good direction, and is used in strengthened form to obtain an empirical risk guarantee for GF (large margins and low test error will be discussed shortly). While a version of this inequality has appeared in prior work (Ji & Telgarsky 2020b), de- spite adaptations to multi-layer cases (Chen et al.] 2019), all prior work had a width dependence of 1/78, many careful refinements here lead to the smaller width 1//22. Overall, in (Ji & Telgarsky 20206), the proof technique is based on the classical pereeptron analysis, and the width requirement here matches the width needed by perceptron with frozen initial features.
The proof then continues by establishing large margins, and then by applying a large-margin gener- alization bound. The margin analysis, surprisingly, is 2-homogeneous adaptation of large-margin proof technique for coordinate descent (Telgarsky) 2013), and uses the preceding empirical risk guar- antee for warm start. The generalization analysis follows a new proof technique and may be of independent interest, and appears in full in Lemma C.6 An interesting detail in these proofs is that the margins behave better when normalized with the nonstandard choice ||a|| ||V|]
As discussed above, Theorem 2. is complemented by Corollary 2.2 which establishes that GF can sometimes escape bad KKT points.
Corollary 2.2. Let To E 1/4) be given, and consider the uniform distribution on the two points 21 = (%o. + +-11-1) and 22 = (7o. -VI-V---- with common label = +1. With probability 21-n over an iid draw from this distribution, for any width m, the choice a and "y = (1, 0) for all j is a KKT direction with margin 2to/22. On the other hand, with probability at least - 155, GF with loss Loxp or frog on an iid sample of size n from this data distribution using width least m 2 250 In(n/6)2 converges to a KKT direction with margin at least 2 27
at least
Summarizing, GF achieves at least constant margin 2 27, whereas the provided KKT point achieves the arbitrarily small margin 20/2; as such, choosing any < 2 2-6 guarantees that GF converges to nontrivial KKT point. While this construction may seem artificial, is simplified instance of the neural collapse constructions in Section 3) and by contrast with the results there, is achievable with reasonably small widths.
To close this section, the corresponding SGD guarantee is as follows. This result gives fully tractable method, and appears in Table Notably, this proof can not handle the exponential loss, since gradient norms do not seem to concentrate.
Theorem 2.3. Suppose the data distribution satisfies Assumption 1.2 for some T'm > O, let time & be
given, and suppose width m and step size satisfy
(44ln(t/0)
Youk
2
m2 >
and
1 E
Tak
10
6400

---

Then, with probability at least 1 86, the SGD iterates (We) with logistic loss E blog satisfy
min Pr p(x,, yr W.) s 8 (lm(1/
2560
(test error bound),
80n /m
max W Woll s<t
(norm upper bound),
Yink Yyu 8+
m
[[ Woll
(norm lower bound).
8
A notable characteristic is exiting the NTK: choosing the largest allowed step size v) 7 /6000, follows that W Woll 2 6 /ou/m//e //mm///1000 whereas the NTK regime only permits ||W Woll = (L). Of course, despite exiting the NTK, this sample complexity is still measured in terms of Yau- suggesting many opportunities for future work.
few remarks on the proof are as follows. Interestingly, is much shorter than the GF proof, as it mainly needs to replicate GF's empirical risk guarantee, and then apply a short martingale concentration argument. A key issue, however, the large squared gradient norm term, which is the source of the large lower bound on || Woll- A typical optimization analysis technique is to swallow this term by scaling the step size with 1/Vi or 1//m, but here constant step size allowed. Instead, controlling the term is possible again using nuances of the perceptron proof technique, which controls the term Ei<, (((pp(W))), which appears when these squared gradients are accumulated.
3 LOWER TEST ERROR WITH LARGE-WIDTH NETWORKS
This section provides bounds which are more ambitious terms test error, but pay a big price: the network widths will be exponentially large, and either the data or the network architecture will have further conditions. Still, these settings will both be able to achieve globally maximal margins, and for instance lead to the improved d/c sample complexity in Table
3.1 NEURAL COLLAPSE (NC)
The Neural Collapse (NC) setting partitions data into well-separated groups (Papyan et al. 2020 these groups form narrow cones which meet at obtuse angles.
Assumption 3.1. There exist ((au, 3 3x)) with ||& = and a E {=1/r} and %oe > 0 and e E (0, 7..) so that almost surely for any (x, y), for each (au, B&) exactly one of the following hold:
either x lies in a cone around 3r, meaning (gn(a))8rr) 2 7he and (1-8.9%) 18
S Ve/2:
or æ is bounded away from the cone around 3r, meaning
-
follows that Assumption 3.1 limpiee Assumption 1.1 with margin Ya 2 %r/ but the condition is quite bit stronger. The corresponding GF result is follows.
Theorem 3.2. Suppose the data distribution satisfies Assumption 3.1 for some (r, Yhe 6), and con- sider GF curve (Wz)e2o with & {lexps liog) and width m 2 4 (2)
In t.. then, with probability
at least - 8, it holds for all large that
(
1 In(n)3 n(7 -]²
+ In 8
7(W) 2
-
and
Pr [p(p, Wi) 5 =
2r
Before discussing the proof, here are a few remarks. Firstly, the standard NC literature primarily compares different optimality conditions and how they induce NC (Papyan al. 2020 Yaras al. 2022 Thrampoulidis et al., 2022]; by contrast, Theorem 3.2 analyzes the behavior of a standard descent method on data following NC. Furthermore, Theorem 3.2 does not establish that GF neces- sarily converges to the NC solution, since Assumption [.I allows for scenarios where the globally maximal margin solution disagrees with NC. One such example is to take points the surface
7

---

of the sphere and which form angle just beyond 7/2; in this case, the globally maximal margin solution is equivalent to a single linear predictor, but Assumption [3T] and Theorem |.2]st The similar construction in Corollary 2.2 took those two points and pushed their angle to be just below т, which made NC the globally maximal margin solution. Overall, the relationship between NC and the behavior of GF is quite delicate.
still apply.
The proof of Theorem 3.2 hinges on a potential function ((W,) 1e onk In E, (x;)( i. where (w,)(W)) is near 1 when U//lluyll SR. and 0 oth- erwise. This strange-looking potential has derivative scaling with 7./r and a certain technical factor Q: meanwhile, the derivative of In ||W; scales roughly with ((W) with>(W;; Q Together, it follows by considering their difference that either ((W) must exceed (7~ - //r,, or mass must concentrate on the NC directions. This suffices to complete the proof, however there are many technical details; for instance, without the NC condition, data can pull gradients in bad directions and this particular potential function can become negative; in other words, the NC condition reduces rotation. The use of In(.) may seem bizarre, but causes the gradient to be self-normalizing: similar self-normalizing ideas were used throughout earlier works on margins outside the NTK (Lyu & Li] 2019 Chizat & Bach 2020 Ji & Telgarsky 2020a). This discussion of & will resume after the proof of Theorem 3.3] which uses similar construction.
and that same factor
One technical point of potentially independent interest is once again the use of ||a,,y| || as a surrogate for ||uy|1? (where ||, 2 2 2||a,0y]1> this seems crucial in the proofs, and was also used in the proofs of Theorem 2.1 and also partially motivated the use of [ayley when plotting the trajectories in Figure | While it is true that these quantities asymptotically balance (Du et al. 2018a), it takes quite long time, and this more refined norm-like quantity is useful in early phases.
3.2 GLOBAL MARGIN MAXIMIZATION WITHOUT ROTATION
The final theorem will be on stylized networks where the inner layer is forced to not rotate. Specifi- cally, the networks are of the form
I. ト Eajo(baoaa,
where ((az, by) )/) are trained, but 2y are fixed at initialization; the new scalar parameter is effectively the norm of vy (though it allowed to be negative). As a further simplification, ay and by are initialized to have the same norm; this initial balancing is common in many implicit bias proofs, but is impractical and constitutes a limitation to improve in future work. While these are clearly significant technical assumptions, we note firstly in Figure that low rotation seems to hold empirically, and moreover that the only other works establishing global margin maximization used either significantly different algorithm with added gradient noise (Wei et al., 2018). in the case of (Chizat & Bach, 2020), heavily relied upon infinite width (requiring weights to cover the sphere for all times t), and also a dual convergence assumption detailed in the appendices and circumvented here.
Theorem 3.3. Suppose the data distribution satisfies Assumption 1.1 for some No > with reference architecture ((ax, Ne-) Consider the architecture x Σj (bjo3a)) where are sampled uniformly from the two choices #1/m² //, and uy (0) sampled from the unit sphere (e.g., first vt Na. then v,(0) r///lle;1l, and the width m satisfies
d-1 In Then, with probability at least 1 - ō, for all large i, GF on (aj, by))
m 2
7d with loss E (lexps boog satisfies
[I((n) ny n
In }
7 (()(t))(()) Na
and
Pr [ppp, y. (a()),(()) - =0 0
The proof strategy of Theorem 3.3 follows a simplification of the scheme from Theorem 3.2 First, due to the large width, for each k there must exist weight j with sgn(b, )u, Pg- Second, since this inner layer can not rotate, we can reorder the weights so that simply sgn (bx) RJ Br, and define a simplified potential
((W)) := 4 Σ lasl In aa + b9.
8

---

with 255 with 13M w2 4200
w03 233
1.0
18
(a) Rotation for 2-sparse parity, {16, 64, 256}.
(b) Rotation for mnist, {256, 1024, 4096).
Figure 2: Cumulative distribution functions (CDFs) for rotation on 2-sparse parity and mn it digits
3 vs 5, with three choices of width; both are run with small step size and full batch gradient descent until the empirical logistic risk is 1/n, and the 2-sparse parity plots match the same invocation which
gave Figure To measure rotation, for any given width m, per-node rotations < [2 My (t(
(T) TTy (C]l
are first calculated, and then treated as an empirical distribution, and their CDF is plotted. The
overall trend is that m increases, rotation decreases. While this trend is consistent with the NTK,
the rotations are still too large to allow an NTK-style analysis; further experimental details are in Appendix B.2
As mentioned after the proof of Theorem 3.2 it's possible without Assumption 3.1 for data to pull weights in bad directions; that ruled here via the removal of rotation, and spiritually this situation is ruled out in the proof by Chizat & Bach (020) via their dual convergence assumption.
CONCLUDING REMARKS AND OPEN PROBLEMS
Stated technically, this work provides variety of settings where GF can achieve margins 7vx and To (and SGD, in one case, can achieve sample complexity and computation scaling nicely with 7 and whose behavior can be interpreted as GF and SGD selecting good features and achieving low test eтror. There are many directions for future work.
Figure demonstrated low rotation with 2-sparse parity and mnist; can this be proved, thereby establishing Theorem 3.3 without forcing nodes to not rotate?
Looking to Table for 2-sparse parity, the approaches here fail achieve the lowest width; is there some way to achieve this with SGD and GF, perhaps even via margin analyses?
Theorem 2.3 and Theorem 2.1 achieve the same sample complexity for SGD and GF, but via drasti- cally different proofs, the GF proof being weirdly complicated; is there a way to make the two more similar?
The approaches here are overly concerned with reaching a constant factor of the optimal margins; is there some way to achieve slightly worse margins with the benefit of reduced width and computa- tion? More generally, what is the Pareto frontier of width, samples, and computation in Table [
The margin analysis here for the logistic loss, namely Theorem 2.1 requires long warm start phase. Does this reflect practical regimes? Specifically, does good margin maximization and feature learning occur with the logistic loss this early phase? This issue also appears in prior linear max margin works with the logistic loss.
The analyses here work best with E, ||ay,ı|| in place of [|]]2 are there more natural choices, and this choice be used in other aspects of deep learning analysis?

---

ACKNOWLEDGMENTS
MT thanks Fanny Yang, the Simons Institute, and the NSF (grant IIS-1750051).
REFERENCES
Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. The merged-staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. arXiv preprint urXiv:2202.08633 220.008622...88 2022.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pp. 1638-1646, PMLR, 2014.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. 2020. URL htt.tt/ss///a.....oo////////////
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv: 1.03662, 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of
optimization and generalization for overparameterized two-layer neural networks. arXiv preprint /rXiv:/901.08:0 2019.
Yu Bai and Jason D Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. arXiv preprint arXiv: 1910001691, 2019.
Keith M. Ball. An elementary introduction to modern convex geometry. In Flavors of Geometry, Mathematical Sciences Research Institute Publications, pp. 1-58. Cambridge University Press, 1997.
Boaz Barak, Benjamin L Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit. arXiv preprint arXiv:2207.08799, 2022.
Peter L. Bartlett. For valid generalization, the size of the weights is more important than the size of the network. In NIPS, 1996.
Avrim Blum, John Hoperoft, and Ravindran Kannan. Foundations of data science, 2017. URL hitpps:/ei //wwwwa.... cs cornelloe...ooooooo www.eel..du.ieieee.eeee.......el wwtp///eeeboo..o/oeo/////oo
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much parmmteriizaionn is suffi-
cient to learn deep relu networks? arXiv preprint arXiv: 123600 2019.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.04486, 2020.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pp. 5413-5452. PMLR, 2022.
Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Infor- mation Processing Systems, 14:20356-20365. 2020.
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in Neural Information Processing Systems, 31, 2018a.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint 18/1v:18/1.08800 2018b.
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison- Wesley Longman Publishing Co., Inc., USA, 2nd edition, 1994. ISBN 0201558025.
10

---

Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv:1810.02033 2018a.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv:1803. 07300v3 (cs.LG) 2018b.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. arXiv preprint arXiv:1906.045: 04540, 2019.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. arXiv preprint arXiv:2006. 200.:20000006657,, 2020a.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent achieve arbi- trarily small test error with shallow ReLU networks. In ICLR, 2020b.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kemels,, transportation mappings, and universal approximation. In ICLRR 2020.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 19066.58900 2019.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang. and Sanjeev Arora. Gradient descent two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34, 2021.
Atsushi Nitanda and Taiji Suzuki. Refined generalization analysis of gradient descent for over- parameterized two-layer neural networks with smooth activations on classification problems. arXiv preprint arXiv: 1905.0/99900087777 2019.
Albert B.J. Novikoff. On convergence proofs perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata, 12:615-622, 1962.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterizaatoo:: global conver- gence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.04674 2019.
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 2020.
Robert Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. In ICML, pp. 522-330, 1997.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Zhenmei Shi, Junyi Wei, and Yingyu Liang. A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. In International Confer- ence on Learning Representations, 2022. URL hhttps://openzevies net/ forum?id
wMpss AI E
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. arXiv preprint 170.1447,, 2017.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In NIPS, 2010.
Matus Telgarsky. Margins, shrinkage, and boosting. In ICML, 2013.
11

---

Christos Thrampoulidis, Ganesh R. Kini, Vala Vakilian, and Tina Behnia. Imbalance trouble: Re- visiting neural-collapse geometry. 2022. URL htLp:tt::// arwaa.iiiv...... http://www.....o////2//22/ 05512
Gal Vardi, Ohad Shamir, and Nathan Srebro. The sample complexity of one-hidden-layer neural networks, 2022. httttt:ss///kat http:/iwww.rrgbb////oo// 0622322233333333 06233
Martin J. Wainwright. High-Dri Siahh-Dimesiional Statistics: A Non-ssympi Viewpoint. Cambridge Uni- versity Press, edition, 2019.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. arXiv preprini arXiv: 2018.
Can Yaras, Peng Wang, Zhihui Zhu, Laura Balzano, and Qing Qu Neural collapse with normalized features: A geometric analysis over the riemannian manifold, 2022. URL https://arxiv:
akq/abs/2209. 09211
Tong Zhang and Bin Yu. Boosting with early stopping: Convergence and consistency. The Annals of Statistics, 33: 1338-1997 2005.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.068 088888, 2018.
A Sincerest apologies to The Reader
Dear Reader,
I mismanaged time and my "plan" to prepare the camera ready in the final days was thwarted by travel ambush. Please see the arXi v versions dating from after March 2023 (hopefully available before March 31, 2023).
(This present version does not even address reviewer comments which were resolved the rebuttal phase, updates will come shortly!)
B TECHNICAL PRELIMINARIES
This first appendix section contains tools used throughout, extra background, and further experi- mental details.
B. FURTHER NOTATION, BACKGROUND, AND ESTIMATES OF "/a AND 7
Firstly, in many of the proofs, it is useful to normalized parameters: define ūj := :::;//lug n//1|up|| and āj sgn(a,) aj/ layl Furthermore, write (WW) ((p:(W)) and ((W)) = (P)())) are used; since & is negative, often [4]] is written.
annoying write [6]] over and over, however, interestingly, these nonnegative derivatives can be transformed into a notion of dual variable, which will be used throughout the proofs. Concretely, define dual variables (q:)
Σ E(())) = V, E. ((p)) (2, ((p))) ((((p))
= V,E,(m)
= V
which made use of the inverse function theorem. Correspondingly define Q = - whereby - = qi Q; for the exponential loss, Q Σ; exp(-P:) and Σ, 9: 1, and while these quantities complicated for the logistic loss, they eventually satisfy E, q: > 1 (Ji & Telgarsky 2019 Lemma 5.4, first part, which does not depend on linear predictors). Overall, these dual varaales match the usual interpretation in margin problems of corresponding examples of high error, and also relate to the Lagrange multipliers used in the definition KKT point.
On the topic of KKT points, further detail the formalism is follows. Firstly, (yu & Li 2019) provided definition for general L-homogeneous models, and the version here is equiva- lent for the simplified choice of 2-homogeneous models of the form æ + E, (za(()))) Given
12

---

KKT point W. the complementary slackness conditions imply min, (W) 1, whereby (WW = min, p. ( 2 / 1/[[ justifying the choice 1/|| as the margin. Lastly, given any arbitrary W (not necessarily KKT point), the optimality conditions on oj and 1 hold iff they hold for any rescaling rW (since the term r appears on both sides), and thus r can be adjusted to make the complementary slackness conditions tight, justifying the definition of a KKT direction's margin.
To close, this section will collect various estimates of The and Ti. Firstly, both function classes are universal approximators, and thus the assumption can be made to work for any prediction problem with pure conditional probabilities (Ji et al., (020). Next, as a warmup, note the following estimates of You and Tae for linear predictors, with an added estimate of showing the value of working with both layers the definition of Tma-
Proposition B.1. Suppose the data distribution is almost surely linearly separable: there exists | = 1 and 7 > O with yı:' ū 2 7 almost surely.
1. Choosing (a, v) (0, sgn(a) [ll( u)ll S 2). then Assumption 1.2 holds with 7/a Z 32'
2. Choosing 0(a,v) v) (sgn (v) 0) [l] w) 2}. then Assumption 1.2 holds with V 2
16Vd'
3. Choosing a = (1/2, and 3 = (ū, ü), then Assumption 1.1 holds with % 2 2"
Proof. The proof considers the three settings separately; in each, let (z, v) be random draw, which almost surely satisfies u'ay 2 7.
1. To start,
Eu (((w), Swp(s, = (,,0) laju (uo' x [[((, w)ll 2
2 (a lalo (vT Ill(a w)ll s 2).
control the expectation, note that with probability at least 1/2, then 1/4 S |a| S v2, and thus by rotational invariance
el < 2]
E (a, (v'x)1
S 2
IV
o (1:) s 2
8
1
32
2. For convenience, write (a, v) = w, whereby w ~ Ny means a ~ Na and v ~ Nr. With this out of the way, define orthonormal matrix M Raxd where the first column is the second column is (7 - üu "u))=// /x/ - ūu )æ[l. and the remaining columns are arbitrary so long as M is orthonormal, and note that M = and Mr = e u x + e2T2 where T2 == / | (7)
Then, using rotational invariance of the Gaussian,
Ew (B(w), 8p(z, w.w)) = yE (a.)) ( [|] s 2]
M MT))
Biko.:ollees/ggn())))/ddv myy 02r2)
Blcc::olssarnggn()))))(sseoeeeee xy v2r2)
E [[c [ 17 xy 0272) aa-loi/ū 2272)
2sgn("1)
20
+ a(v la lazz -222) o0-lv110 xy 2222)
13

---

Considering cases, the first ReLU argument is always positive, exactly one of the second and third is positive, and the fourth is negative, whereby
yE (x.:)[==a(1)((((²)) = E [|
[|01 [7 ay + 2272 + |22 xy v2r2]
usgn(v))=1
0220
2E (((..)) [1lj"aa ay
pagn(
2 271E
| |u1|
vagn(v:)=11
= =arill(a, e) - 2 E [1a] II(a, w)ll =2).
where (a( v) S 2] 2 1/4 since (for example) the x² random variables corresponding
to |a|² and |/||² have median less than one, and the expectation term is least 1/(4v by standard Gaussian computations (Blum et al. 2017 Theorem 2.8).
3. It suffices to note that
2y
(B0() = yo(uu x)) yo(-uux))
j=1
1ly = [lo(v''z)) + 1lv = 1]o x)
yū'x x
2 7.
Next, estimates for Yg and Y on 2-sparse parity were stated the body in Proposition 1.3 The key that Yia scales with 1/d whereas ", scales with 1/vd, which suffices to yield the separations in Table ! The bound Yaa is also necessarily upper bound, since otherwise it would be possible to beat the NTK lower bound (Wei et al. 2018).
This proof shares ideas with (Wei et al. 2018 Ji Telgarsky 2020b), though with some adjustments to exactly fit the standard 2-sparse parity setting, and to shorten the proofs.
Proof of Proposition L.3
Without loss of generality, due to the symmetry of the data distribution about the origin, suppose Ha, the correct label d2, the product of the first two
and 2, meaning for any coordinates. Both proofs will use the global margin construction (the parameters for %2). given as
follows: p(æ, ys (a, ()) y ش - a.o (8).)) where (1/4, 1/4, 1/4, 1/4) and
1
1
B1
0
0
R
V5
V2
1
-1
32
0,
0
R
V2 22"
-1
3g
ERd
V2
22
1 -1
Ba
ER.
V2 2
Note moreover that for any Ha. then 3]x >> 0 for exactly one which will be used for both Yi and y The proof now splits into the two different settings, and will heavily use symmetry within Ha and also within (a, 8).
1. Consider the transport mapping
sgn(a)
((a,u))
Σ
3,1 3,1
0l
2
==1
14

---

note that this satisfies the condition [[0(w)) || hemisphere, and (31, 31) together partition the sphere once, and (32, Bs) similarly together partition the sphere once.
< thanks to the factor 1/2, since each 3, gets
Now let any æ be given, which as above has label y = 2 22. By rotational symmetry of the data and also the transport mapping, suppose suppose B1 is the unique choice with 0/ O, which implies y = 1, and also ØJ. = 0 = Zgz = 0, however 31 = -j.. Using these observations, and also rotational invariance of the Gaussian,
Ea,v (f(a, u), 0p(z, w))
la
Ea,e
3 a
[3)
2 0J
10'000
2
j=1
|a|
x
Es
(E. 1 [8 20 1(''2 2 - 2 0] 1/' x 2 0))
Now consider E,, [ 2 0] | x 2 0J. A standard Gaussian computation is to introduce
rotation matrix M whose first column 3,, whose second column is (I f1,3)) )
81 )r]l, and the rest are orthogonal, which by rotational invariance and the calculation 8 V /2d gives
1 2 1[0' 1. 2 0) 1 2 0]
= [m 2 0 11018/1 + 22 1 (8Tx))
E. (m 2 0 1m 12 d/2 0].
Performing a similar calculation for the other term (arising from 07x) and plugging all this back in,
Bu,, (0(a, v), Öp(2x y: w))
2 -va
B aa [ E. [1i 20 (1 -2/ 12 1[-11 02 02 d/2 120)
To finish, a few observations suffice. Whenever en 2 (which is enforced by the common first
term), then -1 + U2T S V1 + / /22d/2- so the first indicator is 1 whenever the second indicator is 1, thus their difference is nonnegative, and to lower bound the overall quantity, it d/2 / To lower bound this event, it suffices to lower bound
suffices to asses the probability that 01 12v
2 whereas 21 + 02 dd/2 1 < 0.
Pr(m 2 0 A 0/ 2 0 A en 2 02 22/ 4/2-1 2 Pr(u 2 v122 Pr[O S v2 S vidd.
The first term is at least 1/5, and the second can be calculated via brute force:
1 1/va
1/va
1
Pr(c2 2 1/Vd
2m exp(-2²)dr
2 Jo
exp(-1/d)dr 2 2T
which completes the proof after similarly using E,, 2 1, and simplifying the various con- stants.
2. Let any x E Ha be given, and as above note that 83x > for exactly one j. By symmetry, suppose it is 31, whereby y 01 = and
1( 2 =
Yo 2 p( B)) = (3)((( laal
ATx= -|aal
4
2d
/d
To close, consider the k-sparse parity problem, the natural k-bit analog of the 2-sparse parity prob- lem: now the target label depends on the product unknown input bits, but otherwise the problem the same, meaning the data distribution is again supported on H == {=1/ Vd)d,, and only the support of the distribution is used in the margin analysis.
15

---

Proposition B.2. Let k 2 4 be an even integer, and consider any k-sparse parity data distribution: inputs are supported on Ha == {#1/vd]d (as in Proposition 1.3 and for any E. Ha. the label
is the product of l fixed coordinates: y d Iigs 24 with S k. Then Assumption 1.1 holds
with 7A 2 2k.dd
Proof. Let P(S) range over the 2 possible vectors which are =1/Vk on elements of S, and 0 otherwise, whereby P(S) has ||w||| Moreover, for convenience, define shorthand sgn(z) sgn #4). With this in hand, define target mapping
h(x) (-1)8/2-1
Σ
sgn(v)o(u'an z),
PEP(S)
which is of the desired form for Assumption 1.1 with o, sgn(o)(-114/2211/2= and 3, v, and
moreover En |oxl and || = 1.
Now let any
Ha with corresponding label y sgn(r) be given. To develop first simpli- fication of the margin yg(x), let [=;)] denote v E P(S) where the signs of x and v have
disagreements within the support of S, whereby [r; jll = ()) and
(-1)*/2-1 (gn(())
vg(x) = sgn(z)
o(vTx)
2*
PEP((S
sgn(u)sgn(zr)
k: 2j (kk-2j)
= ---1)//2-1
Σ
2
σ
Vkd
1=0 PEP(S))
k/2
(-1)
k- 2j
(-11)//2-1 Σ
2
Vkd
(m)
(-1)6/2-1 k/2
Σ (-1))
(h: 2j).
2kd 1=0
1
16

---

The inner sum can now be handled via few binomial tricks from (Graham et al. 1994 Chapter 5):
k/2
(I:
2j)
5=0
k/2
k
+
Σ
1-1
(k: 22)
j=1
k/2
k 1) 2j
kk + Σ
1
GGaham et al.
1994 eq. (5.6)
i-1
j
j=1
k/2
(6-]]
k 1
2j 2j-k
= k + Σ
1-10-1
11
i-1 j
1=1
k/2
(j- 1 - (k- 1) 1)
2j -k
= k A Σ
Graham et al.
1994 eq. (5.14))
j-1
j
5=1
1/2
k ) ク
(j- k (3-=- 1
= k + k Σ
j -0--1
+
1=1
k Σ
4/2
k)
k
6/2-1 Σ
(j-k) k)
)
1=0
k/2
+ b)-))
(6/2--) [
Graham et al. 1994 eq. (5.9))
k/2
(-1))t2 (k- ()-2) + (-11)//2-1 (
k/2 )
k k
k
Graham et al.
1994 eq. (5.14))
k/2
As an elementary simplification,
k 2-2 2 k/2 (1/2- -1=²) -
k/22 (kx77)
(k 2)!
(k 22)
(k:22 - 1)1(k/2 - 1)1
(k/2 2)((k:/)
(K: (4-3) 3)1
k- 2
k- 2
(k/2 - 2)1(k/2 1)1
k/2
1/2
(x/2-1) 1) Ke'
k -33 4
1//2
which combines with the preceding to give
k/2
1: (+) (k: - 2ÿ) = (-138/2 k 2-
2-2 )
1
+ +--1)8/2-1
k/2
k/2
1=0
=
( 3 4
1/2 1 Ke'
which after combining with the original simplification gives
(-1)k/2-1 k/2
yg(x)
11 (k: 22j)
2 //d
1=0
(-1)
( k- 3 4
k k(-1)b/2-1
2 /lod
k/2 1) l.
4
k - 3
2h 2kv
kk/2
17

---

w5 233
widh 259
vidhi 1224
1.0
10
Jidif 4230
(a) Norms for 2-sparse parity, {16, 64, 256}.
(b) Norms for mni {256, 1024, 4096).
Figure 3: CDFs of norm growth on 2-sparse parity and mnist digits vs 5, with three choices of width, and all other experimental details in Figure | Figure 2 and Appendix B.2 Here, for each width m, the norm growth of node j is interpreted as /mlluy(() the gradient of 1; scaling with aj, which initially has magnitude roughly 1/ym, and results in overlapping CDFs. One measure of exiting the NTK, though bit weak, is that most rescaled norms are far beyond 1; an experiment finer accuracy could be interesting direction for future work.
(0)];: ; the v'm factor is due
To close, for the final estimate, if = then
4
k/2 1 )
h: -
4
1
2 / kd
2'
4d
2kvd
and otherwise, ls 4, note firstly via standard lower bounds on the central binomial coefficient that
k k-3
k k- 3
k 2
h: h-3
2
2 k 2
1/2211
22
k/2 2
k/2 -
k/2 2
Vh
vk
and thus
1//2 - )
k k-3
2
2
2 / hd
(k-
1) kd
kvd
B.2 EXPERIMENTAL DETAILS
This brief section summarizes various choices used in the experiments behind Figure and Figure 2 and provides an additional companion figure Figure
The i st data was limited to classes and give binary classification problem which is not linearly separable, and otherwise unmodified. The 2-sparse parity data was uniform over HJ, the corners of the rescaled hypercube as defined in Proposition 1.3] and further described in Figure (e.g.. n 64 samples and d 20 dimensions).
To simulate gradient flow, full-batcl gradient descent was used together with the logistic loss. Ini- tially the step size 0.01, but eventually the mnist plots switched step size 1, which did not lead to any discernible change. All experiments were run until the empirical logistic risk was approximately 1/n.
companion figure to Figure from the paper body is to plot the CDFs of norm changes of the inner layer; this presented here in Figure 3, and detailed in the caption, also indicates an exit to the NTK. though it unclear it is quite to the significant level W Woll = O(ym) allowed by the theoretical guarantees.
18

---

B.3 GAUSSIAN CONCENTRATION
The first concentration inequalities are purely about the initialization.
Lemma B.3, Suppose ~ Nm// /m and V NNxxa Vd.
1. With probability at least 1 8, then ||a|| I + v (n similarly, with probability at least 6, then | & vm + 22
2. Let examples (I15..., In) given with ||>||| S With probability at least 46,
max Σ a)o())
S 4lnnn/8).
Proof. 1. Rewrite à aym, that à
N Since à H
|āll//m
|all is (1/vm)-
Lipschitz, then by Gaussian concentration, Wainwright 2019
Theorem 2.26),
||||| = ||āl|/ v
S E| B| Vm + 221n(1/8)/m
/B|a|// /mlp///m= + 2l1(//m)mm
221((1/))/m
Similarly for V. defining V = V whereby V. Nmxxd Gaussian concentration grants
[V] = IVV1/V
2m/(1/8)/d
2. Fix any example F;, and constants 61 > and E2 > 0 to optimized at the end the proof, and define d, d/ 2/| for convenience. By rotational invariance of Gaussians and since ay is fixed, then oVV,,) is equivalent in distribution ||>]|/((g)/ Vd alg)/Vd, where ~ Nm. Meanwhile, - [lo(g))l/Vdd, is Theorem 2.26),
with E| (g)ll /m, and so,
by Gaussian concentration (Wainwright) 2019
-dee 2
Pr[[lo(Va:))] 2 vml P +V
Vm eepp
Next consider the original expression (Vo() To simplify handling of the 1/m variance of the coordinates of define another Gaussian h := aym, and new constant := md;; for convenience, whereby
(V.) ( is equivalent in distribution to equivalent in distribution to (Ta(y)/ Vc, since and V are independent (and thus ht and V are independent). Conditioned on g. since Eh = O, then E[h (gg)gg) = O. As such, applying Gaussian concentration to this conditioned random variable, since h + h' (r)g) V is (lo0g))ll /c: Lipschitz, then
- 2
Pr(h'o(g)/vG 2 s exp
19

---

Returning to the original expression, it can now be controlled via the two preceding bounds, conditioning, and the tower property of conditional expectation: Pr(h'o())/VG22 Pr h'o(g)/Vaze |acl://aaaallool//VV[//333. vm Pr S -Pr(No(()//a
vml Pr ( vm
E pilloo())aa 22 - Pr(lla())l// <1 vm
5 + vml
> + - PPr(Wo(g)// /
vmpr|oo0a)l/ >
vmll
$ E
exp
|| d 1 vm
+exp ( (-dr)//2
c,
+ exp (-d.6/22)
S exp
4dieř + 4d,
As such, choosing := 4 4l((n/0) /d//// = 4 1n(n/0) and 61 == 22ln(n/6)/dd gives
5 n
(Va')((V,)) 2 o2] = Pr(h [t)h'o())// 2 x2) S
which is sub-exponential concentration bound. Union bounding over the reverse inequality and over all n examples and using max; ||x;|] S gives the final bound.
Next comes a key tool in all the proofs using Y guarantees that the infinite-width margin assump- tions imply the existence of good unite-width networks. Lemma B.4. Suppose the data distribution satisfies Assumption 1.2 with corresponding 0: Rd+1_
Id+1 and Ya > 0. and let ((I,, y)))²= be an iid draw.
1. With probubility at least
8 over the draw of (w;)}= defining 02 := ((w;)/ /mm then
min Σ Fy )p,(w;))) 2 7mvm mmn
2. With probability at least 1 - 78 over the draw of W with rows (w,)) with m 2 2m((1/)),
defining rows 03 == 0(w,)/ of 0 E [mxx(d+1), then for any W and any R 2 | W'll and any ro 2 0 and rw 2 0,
rro rw W. Op.()) (W') 2 Tarovm re [ 0 8R 4
-w [4ln(n/0) 2R 2R + 44m
and moreover, writing W (a, V), then ||a|| 2 and [| < 2/m For the particular choice rg := R/8 and Fw = 1, if R 2 and m 2 (641n(n/8)/mm P, then
(ro + W, W.Op((W')) (:W' 2
Turovm m
160r3-
2
Proof. 1. Fix any example (zx, v.), and define
:= En (0(w), 0p, (p.(ww).
where a 2 Ymu by assumption. By the various conditions on 8, it holds for any (a, = w E Rd+1 and corresponding (a, 0) := f(w) Rd++ that
(0(w).
Wn | (vTx;)) + (t, anoo (o ax))
VI
|a|
|[||||| < 2] ||||||
||اا||| + ||
|a|- 1|[a| s 2] -|==
A
4.
20

---

and therefore, by Hoeffding's inequality, with probability at least 1 5/n over the draw of m iid copies of this random variable,
(((()))) 2 my v 32m ln(n/6) 2 m//k /32m In(n/6),
3
which gives the desired bound after dividing by vm, recalling 8j := 0(ws)/ Vm, and union bounding over all examples.
2. First, suppose with probability least 76 that the consequences of Lemma B.3 and the preceding part of the current lemma hold, whereby simultaneously ||a]| S 2, and and
VI S m,,
min p. (W) 2 -4ln(/6)), and min (p),0p(()))) 2 Tra Vm v 32 in(n/o).
The remainder of the proof proceeds by separately lower bounding the two right hand terms in
(ra0 + r, (p:()) TuPi (.P::WW)) = To (0.8)x(w)) + (0. - (w))
+ rw (W.. - rwn)
For the first term, writing (a, 17) = 0 and noting ||||| s 2 and || s 2, then for any W (al, V') (B. -
Σ ag (((oz8))oo((zz)))
Σ x
+
d
(o(o)o)) (ufa:))
l uy [ajo' 1/) ajo' (a' o//]
+ Σ |m/ - (, (x'2/ 1/)) - a, (x' 0/})
< ||l|l-IVV' - VII Ila' all ..D-1111 ||l|| ||
< 4R+4
For the second term,
(w. (r.(0((()))pp((() -
= (a, (ww))) <v.âvv((w))) (vr
Σ (
[0 o (x)
< pi(w) + vi Σ as (a(alo)) + +
11u5 r
< 41n(nd) + ||a|| ||V V'Il + I|a' + + - l'll < 4ln(n)) 4 + R²
Multiplying through by re and r and combining these incqualities gives, for every i, (rol + rw W, (,8))))))) Tw.P:WW)) 2 Tarovm re [V32ln(n/0) + 4R + 4
Tw 4lm(n/6) + 4R + R²
21

---

which establishes the first inequality. For the particular choice ræ R/8 with R 8 and
Fw = 1, and using m 2 (64 ln(n/6)/% the preceding bound simplifies to
rroB + rm W. 8p:()))) - -r.PP(W")) 2 Ye m
To
Na /
32r + 32ra
8
Tau m m
+ 32ro
64r
16
Yuu revmm
160r
2
B.4 BASIC PROPERTIES OF Z-HOMOGENEOUS PREDICTORS
This subsection collects a few properties of arbitrary I-homogeneous predictors in a setup more general than the rest of the work, and used in all large margin calculations. Specifically, suppose general parameters ü, with some unspecified initial condition ug, and thereafter given by the differ- ential equation
ún -.,R((((u)),
(B.1)
where
p(u) (pi (w), (.),...,,)))... Pm (u)) E R",
(.(u) = (FF(
F(2; cu) = c² F(Z;; u)
Vc 2 0.
The first property is that norms increase once there is positive margin. Lemma B.5 (Restatement of (Lyu & Li. 2019 Lemma B.1)). Suppose the setting of eq. also E (fexp: b If ((,)) < ((0)/n, then, for every t 2 T,
B. and
dl |ell > 0 and
(u,, de) > 0,
and moreover lim; ||u.|| 00.
co.
Proof. Since is nonincreasing during gradient flow, suffices to consider any u, with R(u,)) < ((0)nn. To apply (Lyu & Li 2019 Lemma B.1), first note that both the exponential and logistic losses can be handled, e.g., via the discussion of the assumptions at the beginning of (Lyu & Li 2019 Appendix A.1). Next, the statement of that lemma is
d
In ||u.|| > O, ds
but note that ||u,|| > 0 (otherwise R(us) E(0)/n is impossible), and also that
d
(ux, (dg) |usl
(us (g)) [1 2
|us
and
In |ual|
ds
ds
which together with (d/ ds) In ||u,|| > 0 from (yu & Li 2019 Lemma B. imply the main part of the statement; all that remains to show is ||u, B.6).
> 20, but this is given by Lyu & 2019 Lemma
Next, even without the assumption R(u.) E(0) n (which at minimum requires two-phase proof, and certain other annoyances), note that once ||u,|| is large. then the gradient can be related to margins, even if they are negative, which will be useful in circumventing the need for dual conver- gence and other assumptions present in prior work (e.g., in (Chizat & Bach] (020)). We note that while the closest inequalities in the literature require the condition R(u,) < ((0)/n (Ji & Telgarsky 2020al Lemma C.5), those results aim for a more stringent goal, replacing n in the bound below with In(n;; this simpler goal is sufficient in the present work.
22

---

Lemma B.6 (See also (Ji & Telgarsky 2020a Proof of Lemma C.5)). Suppose the setting of Then, for any u and any ((2, yo));= (and corresponding
eq. B.1 and also E flexp l.
R).
uu, -in,d(((()
Q [(())+ + /ull
s Q
(w)
+
n
L|
|u||
Proof. Define := p(u) for convenience, well as T(6)
{(4)) (u), whereby
q- = (v), and a is (unconditionally) concave (Ji & Telgarsky these facts,
2020a
Lemma C.8). Combining
u1, nā n
= E (u.
122
_ gev; = LQ (VoT(V).0)
= LQ LV . -)
- (0)
Simplifying (0) now proceeds separately for Loxp and blog: for Lexp. then
(0)) = In Σ exp(O)) = In(n),
whereas for loog, then fTog (r) = -In(e" - 1), thus
(0) = In exp Σ In(1 + exp(-O))) -1) In (exp (nln2)-) = In (2" -1) s 2nln2.
As such, in either case,
u. (i.-nd, = LQ ((e) - x0)] s LQ +
Next, since é is strictly decreasing in both cases, then e-1 is strictly decreasing as well, whereby letting k denote the index of any example with min; vs then additionally using the positivity of gives
=
Σ ((Os) (--1(((uss) 2k (1))|uu14
Combining these inequalities and dividing by & gives the desired bounds.
Lastly, a key abstract potential function lemma: this potential function is proxy for mass accumu- lating on certain weights with good margin, and once it satisfies a few conditions, large margins are implied directly. This is the second component needed to remove dual convergence from (Chizat & Baahh 2020).
Lemma B.7. Suppose the setting of eq. B.1 with L = 2. and E {lesps (ogg Then, uncondi- tionally, lim, fo Q. ds = co. Moreover, if there exists a constant & > 0, a time T, and a potential function (u) so that ((u+) >- -o0, and for all 2 T,
d (u) 2 1 2u49.
(u) < i In |ull| and
dt
then it follows that R(u)= + and ||l|||
+ oc, and lim (ux) 2 7.
Proof. The unconditional claim fer Q.a ds + oo is shown by considering two cases: either inf, R(u.)= = 0, or R(w.)= > 0 (the case inf, R(us) 0 not possible since is nonnegative).
1. First suppose inf, R(u,,) > 0. For both losses, it will be argued that inf, 2, > 0, whereby Se Q. ds 2 .eº inf, e ds = xc. In the case of lexp. then R(u,)) 1 Q,, and inf, Q, > directly. In the case of biog, note f
In(e" - 1) and (()) = -(1 + + whereby
-1
1 1-6" e
(lug (T) = 1 (e" -1--
exp(-r) - 1. 1+1
er
23

---

As such,
inf Q2 inf (foog o (n inf (1-cxp(-nR(u.)))
11-exp(--n inf R((a))) > (1--e(((-0) = 0,
meaning inf, Q > 0 as desired.
2. inf, ((.)) = O, then we can choose a time with R(u,) < ((0), and it follows that margins
increase monotonically and R decreases monotonically (Lyu et al. 2021), and moreover by Lemma that ||v,]]| is increasing and lim, ||u,]| = co. Furthermore, for Lexp- then E; 9: 1,
whereas for Aog- R(us)) < E(O) (which holds for all 2 r) implies E. %.())) E [1.2] Ji &
Telgarsky 2019
Lemma 5.4). such, for any 2 T,
2 2 16,1 (Ma, (p:((u))
4Q, E, (())p(( s 88..
In |u.1
ds
||u,|12
|
whereby it follows that
lim In ||ue|| = [.a0 ||u]|1 S
Q ds.
meaning 100 Q, ds oo, whereas Ji Q. ds > via the analysis in the preceding case, and
together Jo Q, cs co.
Combining these cases, then So Q, ds unconditionally.
Now consider the second statement, with $; r given. If lim inf, "/t 2 well-defined and positive via nondecreasing margins, and moreover ||u| Do via Lemma B.5 and < lim sup, R(w,) S limssup 6(-7>||w;
3 > 0, then lim, 2 is
= Alternatively, suppose contradictorily that lim inf, " < 7. and choose any e E (0, 7/4) so that lim inf, Yt < 9--3;; 3e; noting that is monotone once there exists some % > 0. choose t 2 T large enough so that 7 s > 3e for all s > t. Next,
note that ||u||| + even in this situation (which may violate the conditions of Lemma B.5 since
the assumptions & and the unconditional property fo fo Q. ds imply
1 In [|uel| 2 liminf (uu) ((ur) + ((ur) )(ur) lim inminf inf f lim L
d (u.)
ds
(bu)) lim [[ 92, ds x., n
meaning ||u,|| + oo; henceforth, choose to > t1 that that ||u,||2 2 n/c for all 2 12.
follows by Lemmal B.6land and the assumption = 2 that
lim 1
In [|uell (ux)
[|rr ((ess) + lim inf /"
In [lu.. v(u.)
ds
Jtg ds
(ug Uz)
L In ||us, || - -((c)) + lim inf
2(u.) ds
ds
2 u. 1
< 1 In |utg || (((()))) + lim inf
(%6 +n)
2,7 ds
n ne/lual' 112
n
< In ||ue, || - ((u,)) ) lim inf
[-c ds
L
000
contradiction, and since 9047/4) arbitrary, it follows that lim inf 74 2 7.
24

---

C PROOFS FOR SECTION
This section contains proofs for Section 2 all of which have a dependence Vin rather than 7p-- The SGD proof' will come first, as they are easier and serve as a warmup.
C.1
SGD PROOFS
Before proceeding with the proof of Theorem 2.3 the following technical lemma (little more than an application of Freedman's inequality) will be sufficient martingale concentration inequality for the test error bound.
Lemma C.1 (Nearly identical to (Ji & Telgarsky 2020b
Lemma 4.3)). Define Q(W)
Ex,y 1e" (p(x,, y; W))l and (W) == 1e' (p(ai, Us: W)). Then Eist (Q(W,) - (W.)) is mar-
tingale difference sequence, and with probability at least 1 5,
Σ S 4 (((W))+44(11/))) 411(11/)), KE
+
Proof. This proof is essentially a copy of one due to Ji & Telgarsky (2020b) Lemma 4.3); that one stated for the analog of pt used there, and thus needs to be re-checked.
Let F; == {((zg, vÿ)) j < it denote the a-field of all information until time i, whereby D; is independent of F,, whereas wy deterministic after conditioning on F,. Consequently, E [Q(W.) (W:) 0, whereby Eist [Q(W:) (W.)) is a martingale difference se- quence.
The high probability bound will now follow via version of Freedman's inequality (Agarwal et al., 2014 Lemma 9). To apply this bound, the conditional variances must be controlled: noting that [x(z]] E [0,1], 1]. then Q(W)) (W,) s 1, and since (W,) [0, 1]. then Q.W.)² I (.W)),
and thus
E (((w.))- e.(W.))
[ = (w:)) F 2(W;)
E (w F3
Q(W).
As such, by the aforementioned version of Freedman's 's inequality (Agarwal al. 2014 Lemma 9),
Σ R<E
((w) (wW)) S (c- 10--2 2) Σ E
(Q(W,) (.W))) F + In(1/8)
i<t
(e - 2) Σ <
it
which rearranges give
Q(w)) S Σ
e(W)) + (115)),
which gives the result after multiplying by 4 and noting 4(3 e) > 1.
With Lemma C. and the Gaussian concentration inequalities from Appendix B.3 in hand, the proof
of Theorem 2.3 is as follows.
Let (wy) be given with corresponding (āz, 0.)) = 0, = =(ww))/vi (whereby ||0 < by construction), and define
Proof of Theorem 2.3
= 10nym m
Yuu m
80mym
m
R = 8r
W == r0 Wo.
Yokk
640
Yon
80
25

---

which implies 2 1, and R 2 1, and 17 I R/16. For the remainder of the proof, rule out the 78 failure probability associated the second part of Lemma B.4. whereby simultancously for every I|W" -Woll - R.
min (W, (W)))((')) 2
M/ 160r² -
MY V
Vime
= In(t),
(C.1)
2
2560
min (0, 2 Tuu m /321n(n/0) - 4R - 42 7m
Nam Bayn m
Yau V m
You V m
m
8
10
2
(C.2)
and also ||ao|| 2 and ||Vo|| I 2/mm.
The proof now proceeds as follows. Let T denote the first iteration where IIW, - Woll 2 R, whereby and max,<r IW, Woll s R. Assume contradictorily that 8; it will be shown that this implies ||W Woll s R.
Consider any iteration r. Expanding the square,
[Wa+1= - w = |Wa- - (W - WI2
|Wa w112 -21 (
W. W.) + + ,1²
IWa- - W12 + 27t (8ps(W.), W -w.) + t (W
By convexity, IIW, Woll s R, and eq.
C.1
(.(W.) (Bp, W - W.) ((W.)) (K(B0.(W.))))))) -Pa()))) -
{ (W.)
s f, ( ((8p, WV - -Pa(W.) (W.(
< 1n(1 + exp( (n(())(()))))))))))))))))) Ra(W.)
$ t
l. (W.),
which combined with the preceding display gives
+ +m (1 - f. (W.)) + + (F
|| - W < [. - W1 -01--W1--
Since this inequality holds for any s < T, then applying the summation Ener and rearranging gives
IW - W 12 2m
Σ (W.) < |Wo W 22 +2 + Σ (..)) ([..:))((pp.(( (pp
<<T
2<T
To simplify the last term, using |Vo|| s 2 and ||ao|| S and IW, Woll S R gives
[pp((w)
= (V + Σ ejaijo'
< ||o((v..))1
+ |||,!|
< 2/1V, 20 + 21 21|a, - -all2 + 2|laol1 1
< 2R² + 8m + 8,
< 10m,
and moreover the first term can be simplified via
W - W = IW, - Woll - 2 (W, - Wo. W- Wo) + +| - Woll
IW, Wo 2r| Woll + || - -Wall
26

---

whereby combining these all gives
|W, Woll - 2r|[ - Woll + 1|W Woll? + 2n Σ (W.))
S<T
< |W, w11++ + +2n Σ (.(W)
< IW, W1 2n Σ " C. (W., (00.) /
< IW W/ 12 + 2n + 10m2m (WW))))
which after canceling and rearranging gives
I woll + 2n
Σ
(W.)) - 2r| Woll + 2n + 10y²m Σ ((W)))
S<T
To simplify the last term, note by eq.
C.2 that
IW - Woll
sup ||
(W, W, - Wo)
0. W - -Wo)
Σ (-0, (W.))
Σ (.(W))) (B. (p.)).
(((WW))) Tna m
2 <<T
(C.3)
2
and thus, by the choice of R, and since IW, - Woll 2 and S R/16,
40ny m
W Wo
|W, 2oll2 + 2n Σ (WW)) < 2r - Wol + 2n +
7/
R
R
R 2
W, - -Wol-
Dropping the term 2n Exet (W.)) 2 0 and dividing both sides by ||W, Woll 2 R gives
R
R
R 2
||, 1o |1 <
R,
the desired contradiction, thus 7 > f and all above derivations hold for all s < To finish the proof, combining eq.
C33 with [[W - Woll || - R = 80m m/ m/Ya gives
(.(W)) - 4||We Woll 320
Σ
<
17/, v m
7
S<I
Lastly, for the generalization bound, defining Q(W) = En,y (p( y W)),, discarding an addi- tional 5 failure probability, by Lemma C.I
1280
Σ Q(w)) S 4ln(1/)) +4 Σ (CW(W)) 4lm(1/5)
22
Since (W.)) 0) < (W.)), the result follows.
It remains to argue that || Wall is large; to this end, it already holds by instantiating eq. with 7 that
C33
W Woll > Meu (Wo)) v
4
27

---

so it only remains to show that 16 (Wa)l is not too small. By Lemma B.3
discarding additional
failure probability 6, holds that [26: Wo) I 4 lm(1/6), and therefore
1
(WW)) 1+ exp(po(Wo)) 2 1+ 1/84 2 84,
which combines to give [W1 - Woll 2 mmnd" as desired.
C.2
GF PROOFS
which is broken into few main lemmas: Lemma C.3 first controls the empirical risk R similarly to the proof of Theorem 2.3 then Lemma C.4 establishes large margins, whereby Lemma [Coleoossopp a suitable Rademacher complexity bound, which combine quickly give the proof of Theorem 2.1
This section culminates in the proof of Theorem 2.1
Before proceeding with the main proofs, the following technical lemma is used to convert bound on bound l.
Lemma C.2. For E E {flog: (exp]. then [e'(z) < 1/8 implies {(z) s (1)(
Proof. If f loxp. then -l, and thus ((z) s 2])((=) automatically, If {(z) bings the logistic loss, then [f)( 1/8 implies 2 2. By the concavity of In(.), for any 2, since 1+e < 7/6, then
(7/6)e
((2) = -ellee =e Se
1te S (1),,
thus completing the proof.
Next comes the proof of Lemma which follows the same proof plan as Theorem 2.3
Lemma C.3. Suppose the data distribution satisfies Assumption 7.2 for some Tan let time t be given, and suppose width m satisfies
(640ln(t/0) 2
m 2
Then, with probability least 1 76, the GF curve (We)selo.1) on empirical risk R with loss É (hogg 3exp3 satisfies
R(w)) I
(training error bound),
5t
W. Woll 7em V
sup <<t
(norm bound).
80
Note that this bound is morally equivalent to the SGD bound in Theorem 2.3 after accounting for the 7 "units" arising from the step size.
Proof of Lemma C.5
This proof is basically identical the SGD in Theorem 2.3 Despite this,
proceeding with amnesia, let rows (wr))² of Wo be given with corresponding (ā,, 0,) 0, ((w))/ /m (whereby ||0 < 2 by construction), and define
Yoa /m
/
R : 8r
W = r Wo.
640
80
with immediate consequences that r > 1 and 8. For the remainder of the proof, rule out the 78 failure probability associated with the second part of Lemma B.4 whereby simultancously for every W Woll < R.
min (W. TW.pp((W') >
T7 mm 160, > T7 m
2/2 m
> In(t),
(C.4)
2
2560
min (0.0p((W')) 2ma 3
(32
4R 4 Van m
Nak m
Yau m
m
8
10
(C.5)
28

---

The proof now proceeds follows. Let T denote the earliest time such that ||W; Woll R: since W, traces out a continuous curve and since R > = |W - -Woll, this quantity is well-defined. As consequence of the definition, sup,<r [W, Woll I R. Assume contradictorily that I t; it will be shown that this implies |[W, - Wo < R.
By the fundamental theorem of calculus (and the chain rule for Clarke differentials), convexity of e, and since [W, Woll & R holds for s E [0, which implies eq. (C.4) holds,
d
I 2 I W11
W. 2 ds
ds
Wai W. (.) w)ds
2
Σ ((w))) (Bur(Wa),,, W. w) ds
Σ ((WW)) (((8b((2)))))) -D((Ws) pc(Wa)) ds
2
n
2
Σ
((BD((W.)) W) pc(W.)) -e((V.) ds
4
n 0
n1 1
2
Σ
|
-(((.)) ds
1
2 /' R(W.) ds.
< 2
To simplify the left hand side,
-WW--W|-- [WW--W]jjlWoowW/ W1 ||W, ||W,-Wol (W, - Wo, W -Wo) 2 - Woll.
which after combining, rearranging, and using 2 and IW, Woll 2 N gives
IW- Woll + [' R(W.) ds 2 2r wW Woll s 4r W Woll,
which implies
R R,
IW, Woll 2r
a contradiction since W, is well-defined as the earliest time with I|W Woll = R. which thus contradicts 7 < l. As such, + 2 f, and all of the preceding inequalities follows with 7 replaced by t.
To obtain an error bound, similarly the key perceptron argument before, using eq. C..5
||, - Woll = sup ||
(W, W. Wo)
2 0, W. Wo
0, L às ds
1
1 Σ (((W.)) (0. (W.)) ds
2n
Tha m S' L'> (((.))
4n
which implies
1
4/|W, - Woll
Σ
(. ds
< 20
0
Vou mm
29

---

and in particular
inf Σ (((W)) / Σ (((w)) =E(0,)] n
4|W, Woll
Vina Vlam m
20
and there exists & [0, with
1 1 Σ ((WW)) &
10t
Since this also implies max; (W&)) - n/ m10t) I 1/10, it follows by Lemma C.2 that R(W)) - 1/(5t), and the claim also holds for 2 / since the empirical risk is nonincreasing with gradient flow.
Next the explicit maximum margin guarantee, which was missing from the SGD analysis.
Lemma C.4. Suppose the data distribution satisfies Assumption 1.2 with margin You > O and pa- rameter mapping and let ((r;, y:)) an iid draw. Let (Ws)s20 denote the GF curve resulting from loss & E {flog: l- Suppose the width satisfies
256 In(n/6)
m 2
fix a distance parameter :== = 3m/m3/3 and let time T be given so that [W, -Woll I R/2 and R(W,) ((0)/n. Then, with probability at least -76, there exists time with [ Woll R so that for all 2 t,
m
IW, - Wol 2 R and 7(W.) 2
4096'
and moreover the rebalanced iterate W. == (at/ Tous T satisfies (1,,;;W) =p(x, ys W.) for all (xr, y), and
7(W,) 2| [[ 2 ((W) 2
Tie
4096'
Before discussing the proof, few remarks are in order. Firstly, the final large margin iterate W stated as explicitly achieving some distance from initialization; needing such claim is unsurprising, as the margin definition requires a lot of motion in good direction to clear the noise in Wn- In particular, is unsurprising that moving O(ym) is needed to achieve good margin, given that the initial weight norm is (V/m); analogously, it is not surprising that Lemma C.3 can not be used produce meaningful lower bound v(W,) directly. Lastly, while these comments seem [[V]] does not obviously have these
natural when normalizing by |[W W,! 1? the normalization ||a,]| deficiencies.
Another thing to highlight is that the use of Lemma for warm start is only needed for laog- and not for lexp: it is unclear how this discrepancy translates to practice, where flog dominates.
Proof of Lemma C.4
By the second part of Lemma B.4 with probability at least 75, simultane- ously ||a|| < and V < 2/m, and for any W Woll
R, then
min (8, 10 (w'))) 2 Tavm [V 32 In(n/) 8R +8+
Yim v
2
where 0y == 0(w))/ m as usual, and |0] < 2; for the remainder of the proof, suppose these bounds, and discard the corresponding 78 failure probability. Moreover, for any W with R(W") ((0)/n and ||W Woll < R, as a consequence of the preceding lower bound and also the property (W') 2 Ji & Telgarsky (2019) Lemma 5.4, first part, which does not depend linear
30

---

predictors),
|85(W))||
(W, (W,O((''))
sup |s 11
2 2
0,
Σ (.pp((w))
Σ
(0. (p')
=
Yna
mm
4
v m
4
Now consider the given W with R(W,)) 8(0)/n and |W, l S R/2. Since + W, traces out a continuous curve and since norms grow monotonically and unboundedly after time r (cf. Lemma B. then there exists a unique time r with I|W - Woll = R. Furthermore, since R is nonincreasing throughout gradient flow, then R(W.) < ((0)/n holds for all [T, 4j. Then
(WW) - -(,,) = I (85(W)), W. ds
J. (107(W.)) .)I
[[a)] ds
Van m
[W.ll ds
4
Vau V m
J- W. ds
4
Tea m
I|: W,, ds
4
Yan Rym m
8
m
256
Since ||olll s 3 thus | s 3/m++/////////// +/a // /m/32 S 4/m, and the normalized margin satisfies
7(W+)
|W |WII J
d
m/252
7
<(W)) Z
7(.) ds 0+
ds
16m
4096
Furthermore, it holds that ((W) Z (W,) for all > t Lyu & Li 2019 proof for Wt under the standard parameterization.
which completes the
Now consider the rebalanced parameters We (ar/ Taa Tm);; since m 256/ which
means 16 < Ya m, then
||x||| < || ll + ||a, aoll < 2 R You m
Voa m
You m
8
32
|| < || [/]l + ||V Voll < 22m + R < 3
then the rebalanced parameters satisfy
W || S |la// + 11 Tmll < Mm
+ 3 3 S 4
and thus, for any (x, v). since
Σ (t(t)
(.,;:W)) Σ ((()))((((())))==
o Tin ( (t))(()) = p(e M. We),
Tia
31

---

then
(W))
P.(W.)
mm/225
(W,) min
min
I
|W
mm
4096'
and lastly to complete the proof note by AM-GM that
|W&rl1
-
||a.112
Tea
2|
7am
whereby >(W)
7(W.) [[, 2
7(W)) 211a,11-1lv
Next comes a margin-based Rademacher complexity bound; as Rademacher complexity has not been used or defined within this work, here is brief description of the main definition, with further detail deferred tp standard references Schalev-Shwarde Ben- Ben-David 2014). First, for a given set of vectors V C R", the Rademacher complexity Rad(V) is
RVd(V) = R. sup (c, u) weV
where e {+1)" has iid Rademacher coordinates, meaning Pr(e; +1] = Pr|c, Pr/s, -1]. The set V will typically be the set of outputs of some class of predictors G on a finite sample X' (z;) of size n, using the notation
( (g(o1), :
91x =
Our bound below will replace with a variety of bounded two-layer networks of any width. This bound can be viewed as strengthening of the proofs of (Vardi et al. (202)), where the bound here holds for all widths simultancously (with no dependence on width), and is normalized by the tighter quantity En ||ايUر||-
Lemma C.5. For any B 2 and any X (xx);= with ||=;|| S 1,
Rad (f (for+ ( F):;W) : m 2 0, W E (m) || - 2B f(x)
< Rad
2 11;+F(2;W) m m 0. = w = R Rmx (x+((1))) ||all -I1 s B
12
< Rad
x F(::W) m (, = w W mx Σ |1a S B
2B vn
<
Proof. The first two inequalities are easier, and follow by set inclusion. detail, note for any fixed W = (a, V), by Cauchy-Schwall and AM-GM, that
1 (lal1 + +1I111) |
Σ Ell = |asl |,yl|| <
|a|| [II|IIIIII
< 2
which implies for each m the inclusions
( (mx((+1) ||w12 < <BB
C (a, V) = W m=+(d+)) ||al| ||V| s B}
c (a. V) w w m=+(1)))
Σ |ay,, S B
which in turn implics the first two Rademacher inequalities in the statement since Rademacher com- plexity not decrease with the growth of sets.
32

---

For the final inequality, recall the definition of symmetric convex hull sconv(-) as used throughout Rademacher complexity (Shalev-Shwartz & Ben-David 2014):
sconv (oonv(S:: = pruj m 2 0.p Rm |lpll S u E S
Then, recalling the notation āj and ū for normalized counterparts aj and Vy. the set of vectors U in the final Rademacher term can be written
x + Σ a,)(1 m m2 2,0 E 1=x(d+1) Σ
||,225|| S B
)
12
Σ
| (1) m 0, W Rmx((+1)
m 2 O,W E 1Rx((++11, lazUyl 00 (U)x))
Σ
|ax
Σ
Σ
|lyes|l SB.
|
h
1.0
B x Σ (.o(ū)a)) m 2 0, W mm
p E R 11lll11 S
1x
B sconv ((z~ |ella 1 x
and by standard rules of Rademacher complexity (Shalev-Shwartz & Ben-David, 2014).
Rad(U) (U) S B Rad sconv ((=+) ||ll|2 = =11 1xx)
< 2B Rad (I>~)()')))
(()'x)) ||l|2 1} 1)1x)
< 2B
Vn
The large margin generalization bound now an immediate consequence of Lemma C.5 and refined margin-based Rademacher bound due to Srebro et al. (2010) Theorem 5). This bound will use the refined normalized margin
71 (W) == min, (W)
(C.6)
Σ, ||a
where
and AM-GM imply 71 (W) 2 min, P.WW |all-| VII
2 2y(W) as in the proof of
Lemma C.5
Lemma C.6. With probability at least 1 - 8 over the draw of ((1;, ys)
1-1 for every width m, every
choice of weights (a, V) = W (d++1) with 7: > 0 (cf. eq.
C.6 satisfies
Pr|p(r, y: W) S 0] 5 In(n)3
(
In 5
(W)²
n
Proof. Combining a refined Rademacher-based margin bound due to (Srebro et al. 2010 Theorem 5) with the 2-layer Rademacher complexity estimate from Lemma C.5 gives, with probability at least 1 - 8, for every margin level 7/2 0, for every W E (d+ with 71 (W) 72, defining
33

---

U/ = { F(2; w\/ w, |ly (W) 2 22/
In In
1 72
+
In
Prip(z,y:W) <
Rad (Unz)²
7/
n
In(n)s
In
+
72
which implies the desired statement.
Thanks to Lemmas and C.4 the proof of Theorem 2.1 is now immediate.
Proof of Theorem 2./ As in the statement, define R You mm/22 the analysis now two stages. The first stage is handled by Lemma C.3 run until time == whereby, with probability at least 1 76,
R(W,)
{())
I, Woll S
Yam Ta m
R
5n
80
2
C.4 since W, as above satisfies all the conditions of Lemma C.4, there exists W with ||, Woll
The second stage now follows from Lemma
and (W,) (WW)(((L) [[ 2 //a//2048 and since
even these mixed-nome -orm margins are nondecreasing (yu & Li 2019, Section H), the claim also holds for all W. with 8 2 f, and the generalization bound follows from Lemma C.6 using Σ, ||a,,,, s ||a||-[[V] and min, P. (W) 2 FW). which holds for both { {Mlog (exp). Lastly, since [W, + 00 and since lim,- ||a.||[[[V,]] = (Du et al. 2018a), it follows that lim [W,1l2/([aas [|llaa/lI]]// [[V 2, which gives the final claim.
Lastly, the proof of Corollary 2.2 giving a simple construction where GF escapes bad KKT points.
Proof of Corollary 2.2 First it is shown that the provided choice (a, V) with aj = and V, = (1, 0) a KKT direction. With probability 2' both elements of the support of the distribution are sampled, and for convenience reorder the sampled data so that will be shown that the choice A1 = 12 and Å 0 for i 2 3 are valid choice of Lagrange multipliers, certifying that (a, V) is a KKT direction. Firstly, derivative condition casy to check since the Clarke diffcrential evaluated where the ReLU differentiable, and it holds directly that
21. and = and
the other data are arbitrary (though y; +1 for all examples).
aj
70
70
+
2%
2%u
\1o (v)=1)
A20 (1)022),
ey (1,0)
70.
70
V 70
V 70
27/0
270"
270
270
A1azIı + A2a282
\1a v ( + X2a, (00(0)2)).
Lastly, note that Pı (W) = mho = PW), therefore the rescaling W = W/ymmo correctly
satisfies Pı (W) = 1 = P2 (W). whereby W KKT point with margin m/o// 7v/2, and W is KKT direction with margin 7
For the GF guarantee suffices to provide a quick estimate for 7. and invoke Lemma C.3 ically, consider the rather loose but convenient weight mapping
Specif-
(a,a w)ll 2 2,
0(a, v) = (0, sgn (0),
U2 2 |11
(asssg(((()) -1)
U2 1
34

---

Then, for the point 21, since v1-% Yo. it follows that
E (O((a, v)), 0p(21, +1; (a;
= -E 2 |ua| (I ا|ll - 2| 0 |alaaaa (7002 + -11-18 1
E1 12 < 0 (a,, e) $ 2
0 - 1-1aao + V1 -1)02)) 1 -0
E/a 1 U22 1ul A [(a, 2 -
16
where the last step follows from standard Gaussian computations.
The case for 22 is analogous, which establishes that Assumption 1.1 holds with Tiak 2 vi 76,1, which implies the result by
applying Theorem 2.1 using the simplification
1/2 since % < 1/4, and lastly obtaining convergence to KKT directions via (yu & Li 2019 Ji & Telgarsky 2020a).
D PROOFS FOR SECTION 3
Before proceeding, here is quick sampling bound which implies there exist ReLUs pointing in good directions at initialization, which is the source of the exponentially large widths in the two statements.
This section develops the proof's of Theorem 3.2 and Theorem 3.3
Lemma D.I. Let O and (lay, Bk)) with (aks, 3&) E R H be given with ||,3 = 1, and
suppose ((ag, 75)) are sampled iid so that with Pr[sgn(a,) = +1] = Prisgn(a,) = 1] = 1/2
and Bi is distributed uniformly on the surface of the unit sphere in RRd (e.g., sample vj ~ Na and choose 0j := w///ll,, [)) If
2 d-1
m 2
In
then with probubility at least 1 - 8, for every (0K,, Bk) there exists (aj, Ty) with sgn(ax) = sgn(a;)
and [| - أ7511 S (equivalently, 07,82 2 2222).
Proof. By standard sampling estimates Ball 1997
Lemma 2.3), for any fixed ie and j. then
d-1
Prill 8xl S
2
and since all (la,, 8,)) are iid,
Pr[] sgn(ax) sgn(a,) |6ū Ball S E]
Pr[Vj sgn(ax) sgn(a;; ||ū 8x c]
Prisgn (a)) * sgn(a;) V प0 3xll > e!Th
(1/2 (1/2) (1 Pr[lāi Bell <]))
(1 (1- (c/2) m
exp (-m(c/2)
and union bounding over all (3x) gives the first claim; for the alternative form, suffices to note
|لū 11
20, 3y and to rearrange.
First comes the proof Theorem 3.2 whose entirety is the construction of a potential / and a verification that satisfies the conditions in Lemma B.7
35

---

Proof of Theorem 3.2 The method of proof is to define potential +
1 4 Elaa Jows In Σ الوااااا
((W) =
where (heavily dropping time indices and even the argument wy to reduce clutter)
(wn) == ok.j @ (ū) ((=)= == m0 min }))
and to then verify the conditions of Lemma B.7 with 7 0 and 7 Inp where the test error bound follows by Lemma C.6 By the lower bound on m and Lemma D.1 it follows that (WW) > -o, and moreover, for any 2 by AM-GM,
+ (W,) S Σ Jasl In Σ SR. 11,
S 2 Σ az In |
In [Wall.
whereby it only remains to show / dt 2 Q7/n. To this end, note that we could show
d
dt 0k. (w) (t) 0 Vj,k,t
(D.1)
then the proof is complete, since after noting the calculation
d
d d (a)0),,,0))112 dt
|لررر
dt
2( + ta
2(1r)),073)" 1/2
ayy, - E, Cys ( ajo (o3(())))
n||a,uحll
Σ, Cps (w;)))ll nl|ayeرl| ||
then (d/ (W)) can be lower bounded
Σj ΦR d de layzll + ||y
d (w)) dt
1
Σ lokk
E, Øk.j |,,ير||
1
Ex Cly. E, ok a wwyl1)
>
[acl
4
Eg Dh.j |1111
1
Vi E, 2h. ā (Lū, 3x Bx) ||w,|1
4n
E, ok ||a,,51
VESt
Σ, ØK (7/ e)2(laay))
4n
Osk
9i
Eg 2k. 0k.01a,,,
VESt
Yhe
12
2r
the rest of the proof will establish eq. D.I.) Note moreover that eq. tion nodes getting trapped in good directions.
(.II has an explicit interpreta-
36

---

Fix any j, k,, and first note
dt ( - ã* a + +as at ((5
d
Otk Σ Lui a2)
Σ Gye [110)100,
whereby (d/ di)
when the argument to @ is not [0, 1]. and otherwise
d
dt 0k =
- (1-
dt
Eyee |0s [ (ānāza(((BBk) (1 -1)))
n
+ ag -1- (1-o))
Analyzing the two bracketed terms separately, the first (the coefficient to ||/|| nonnegative since the term in parentheses is rescaling of the argument to & within Φk.j. which was assumed in [0, 1], meaning (03,3) - (1 - <) 2
The second bracketed term (the coefficient of az) is more complicated. To start, fix any exam- ple (z), define 2; == TiYi for convenience, and define and orthogonal decomposition 2; == cBe + 21 with ||= = and necessarily e1 S v1 - c since || < 1, but more importantly cl/c < ve/2 by Assumption 3.1 Similarly, define ū ;= ājūة for convenience, and additionally an orthogonal decomposition újj g8x= v1 -qau1, which made use of ||ū,|| |اراا| and note
0² (1 +)² 2e 2² Se. 2c.
With this notation in hand, the second term becomes
Ta (1 11-e)ā,faay. c
E) ( (g3k + v1 --- BB2 + 1112
C1 v1 - 92
cc)
q
c
26 1 - (1 - 6) (1+ ve/2. v2e)
1 (1 2c +
20,
as desired: d di 2 for every pair (). meaning eq. D.. has been established, and the proof is complete.
To close, the proof of Theorem 3.3
the method of proof will be construct a potential function + and then verify the conditions on Lemma B.7 with the choices J = 0 and : 7 = % where e : 7a/2 throughout the proof, and then apply Lemma C.6 to obtain the test error bound. Throughout the proof, use W = ((aj. bx))) to denote the full collection of
Proof of Theorem 3.3 As in the proof of Theorem 3.2
parameters, even in this scalar parameter setting, and define b, := sgn(b;) in mimicry of aj and Tz. To develop +, few other properties must first be checked.
37

---

The first property is that o bi for all times t; this follows directly, from the initial condition a,())) = by (0)² = 1/ since at any later time it holds that
ax (t) - (t)² - (1) a0)2 - (b())² + (0)
!/" (arás baba) ds
/, Σ 1e'1 (an - and (boofto; ds
0.
This also implies that oz + 1g 2 2|ax| |by| throughour
Next, for each 3R. choose j so that |bا (0) 5 = 7 and (0) - sgn(ow)) ): this holds
with probability at least - 8 via Lemma since 1y (0)ū, is equivalent in distribution sampling by alone. For the rest of the proof, reorder the weights ((aj, by. my)) so that each (ax, .2)) is
associated with (ag. 6y. ux). Moreover, it will be shown later in the proof that [Íb,(t)ū .x S c and (t) sgg(ag) in fact hold for all t.
Now define the potential
((W)
Joo In
0
Note directly that ((w)) (o))= and moreover that
-o0 by the above application of Lemma
D.1 and choice of
(W) =
ax
[l + bg
S 4 k=1
aao In |
In WI]
2
whereby it only remains to verify (d/ (l,)) 2 @20/
To this end, let T denote the earliest time such that as (T) = 0 for some h: {1, (1....,r], r.....,), which also
means (T) = 0 for that & and moreover T the earliest time by (T) = 0 for any E (1,...,,r) since of 6% unconditionally for all Then, for any E [0, T').
d (W)
1
(bo v[..)) oi by (alllbau ((x 2/ax| [bxl
dt
n1
1
Pithia
n
1
2
Σ
(T2
-xx + BBa) Bab)aaa)
k
Σ Σ
9ilhaaa (f[x;)
-
1 -1 E 9e 2laa
To 3x
n
k
1
Q Σ
c eE 4/a4|
qi
n
n
27 > 0.
Σ 4a (7g -)
n
which establishes the desired lower bound on (d/ df for [o, but moreover establishes -o, which means there can not exist h
(after integrating along [0, T)) that ((W)) > (WW)
with a& (T) 0, since that would mean (T) = 0 as well (as above) and thereby ((Wr) -00.
Consequently, T = oo and (d/ d 2 22)/(2n) holds for all I, and the proof is complete. O
38


Reviews:
[{"review_id": "uVnDE_tjG7", "reviewer": "Reviewer_Wf2D", "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": "In this paper, the authors studied the optimization and generalization of two-layer ReLU network when the first layer neuron rotate little. Three regimes are considered, including the near initialization regime, Neural Collapse regime and non-rotate regime. The results show that low test error could be achieved and have some improvements over prior works in terms of either sample complexity or the width of networks. Several interesting proof ideas/techniques are discussed. Numerical experiments are also provided to support the theoretical results.", "summary_of_the_review": "In summary, this work studied the problem of using GF and SGD on two-layer ReLU network in the classification setting and focus on the regime where the first layer neurons do not rotate much. The results show that a low test error could be achieved under different assumptions. Some of the proof ideas/techniques are also interesting. However, as mentioned in the weakness part, I currently have the concern of some part of the proof. Therefore, I’m currently leaning towards rejection. I’m willing to increase my score if authors could clarify my concerns.", "strength_and_weaknesses": "Strength:\n- The paper is overall well-written and easy-to-follow.\n- Understanding the optimization and generalization of neural networks with finite samples is a very important problem in deep learning theory, and current paper studies it in the two-layer ReLU networks with low-rotation of the first layer and gives some interesting results.\n- Some of the interesting proof ideas/techniques are presented, which uses the idea of margin. These might be of independent interest.\n\nWeaknesses:\n- While the result in Corollary 2.2 is interesting as it shows that gradient flow could escape bad KKT point in certain cases, the example here seems to be somewhat artificial in the sense that the dimension is only 2 and the labels are all +1. Given that this is a classification problem, it is a bit strange to me that the data have the same label.\n- Concerns about the correctness of Theorem 2.1 and 2.3\n    \n    First, there is a mismatch of the initialization scale of the second layer $a$ between $a\\sim N_m /\\sqrt{m}$ in section 1.1 (page 2) and $a\\sim N_m$ in Assumption 1.2. Under the initialization scale in Assumption 1.2, Proposition 1.3 indeed holds. Then, Proposition 1.3 was directly used in Lemma A.3. However, there seems to be an issue here: I believe Lemma A.3 in fact uses the initialization scale of $N_m/\\sqrt{m}$ instead of $N_m$ because later Lemma A.3 was directly used in the proof of Theorem 2.1 and 2.3 which use the fact that $a\\sim N_m/\\sqrt{m}$. If the above is true, then after fixing such issue, the lower bounds in the RHS of Lemma A.3 should be scaled down by a factor of $\\sqrt{m}$, which I believe would greatly change the results of Theorem 2.1 and 2.3. I would greatly appreciate if authors could comment on this to clarify my concern, and please correct me if I misunderstood any part of the proof.\n- The results for the networks with large width require exponential in $d$ (input dimension) number of neurons, which makes the result not very satisfying.\n\nMinor:\n- In the line 5 of the second paragraph of page 6, $\\gamma$ should be $\\gamma_{ntk}$\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "RSArK1lOoD", "reviewer": "Reviewer_kiWi", "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 considers shallow neural networks trained with gradient methods (stochastic gradient descent or gradient flow) under logistic or exponential loss. The authors prove that a low test error can be achieved in a regime that still exhibits low rotations in the weights, but is capable of exiting the NTK regime (in which the weights do not move much from their initialization).\n\nMore specifically, the authors consider networks with moderate width (order of $d^2$) and prove that a margin scaling linearly with $\\gamma_{\\rm ntk}$ can be achieved by either stochastic gradient descent (Theorem 2.3) or gradient flow (Theorem 2.1). This improves upon the width requirement in an earlier work by Ji & Telgarsky, (2020b) and upon the number of samples needed by an earlier work by Barak et al., (2022) -- although reaching the Pareto frontier of width, samples and computation remains a (possibly rather difficult) open problem.\n\nNext, the authors consider a setting close to the 'neural collapse' (NC) popularized by the recent paper by Papyan et al., (2020). Here, the networks widths are impractical (exponential in $d$), but the authors can show a margin scaling linearly with the *global* margin $\\gamma_{\\rm gl}$ -- as opposed to the previous results scaling with $\\gamma_{\\rm ntk}$. These results also require either an assumption on a NC property of the dataset (Theorem 3.2) or on the inability of the inner weights to rotate (Theorem 3.3).", "summary_of_the_review": "Overall, the paper contains a number of new results fuelled by new analysis ideas. The weaknesses mentioned above are overcome by the strengths, and I am positive about the submission. ", "strength_and_weaknesses": "Strengths:\n\n(1) Theorem 3.3 improves in the network width over (Ji & Telgarsky, 2020b) and in the number of samples over (Barak et al., 2022). \n\n(2) Interesting technical innovations over existing work.  \n\n(3) The assumption on low rotation, although strong, does allow for stronger results (achieving the global margin) and seems to be satisfied experimentally.\n\n(4) [Minor, but still nice to see...] Well written paper with the various assumptions properly discussed, the related work discussed in details, and interesting open problems. \n\nWeaknesses: \n\n(1) Model still somewhat artificial.\n\n(2) The optimality of the results remains unclear. Theorem 2.3 leads to a bound on the network width of order $d^2$. This follows from having the width scaling as $1/\\gamma_{\\rm ntk}^2$ and then showing that $\\gamma_{\\rm ntk}$ scales at least linearly in $1/d$. Is any of these two bounds optimal (in some sense)? For the regression setting, the minimum width has to scale linearly with the number of parameters (this follows from counting degrees of freedom, or from VC-dimension bounds). However, for classification, it is not entirely clear what the minimum width should be. I would encourage the authors to discuss in more detail this point, which is only briefly mentioned as the open problem of understanding 'the Pareto frontier of width, samples, and computation'. \n\n(3) In the statement of Theorem 2.1, the authors claim that there exist $t$ with $||W_t-W_0||=\\gamma_{\\rm ntk}\\sqrt{m}/32$. Did the authors intend to put an upper bound here? \n\n(4) Is the probability bound of Theorem 2.1 uniform in $s$?", "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": "QtAHfmHj0eN", "reviewer": "Reviewer_FAxZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 studies the test error of the gradient flow (GF) and stochastic gradient descent (SGD) for two-layer ReLU networks. The authors provide several improved results over existing studies under several margin conditions for classification problems. Specifically, the required network width is significantly improved from $d^8$ to $d^2$ (Theorem 2.1 and 2.3) under NTK-margin assumption and from $\\infty$ to $d^{d/2}$ (Theorem 3.3) under the global max margin assumption. Moreover, the lower sample complexity (Theorem 3.2) is shown under the neural collapse condition.", "summary_of_the_review": "This paper makes a certain contribution in the context by improving existing results, but there is room for improvement in presentation.", "strength_and_weaknesses": "**Strengths**:\n\n- The improvement of the required network width (Theorem 2.1, 2.3, and 3.3) over existing results is good.\n- This work develops several proof techniques: (i) tools to analyze low-width networks\nnear initialization, (ii) a new generalization bound technique, and (iii) a new potential function technique for global margin maximization far from initialization. These techniques will be helpful for future work.\n\n**Weaknesses**:\n\nThe presentation is somewhat involved. \n\n- Although the standard margins (normalized margin and normalized smoothed margin) are introduced, they are not used in the main text. Thus, the reasons why these were introduced are unclear, which may confuse the reader.\n- The explanation of the potential function on page 8 is abrupt and difficult to understand. To help readers understand the benefit of the potential function, it would be better to first explain the motivation for using it.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "GFgUlxA10hg", "reviewer": "Reviewer_ECNr", "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 submission studies the gradient descent/flow dynamics of a two-layer neural network with ReLU activation function and losses with exponential tail. The authors presented the following results: (i) an improved perceptron analysis based on the NTK margin that allows the parameters to move away from the NTK regime, and it is shown that a polynomial-width neural network achieves low test error; when specialized to the 2-parity problem, this gives learning guarantees that matches kernel methods. \n(ii) under a neural collapse assumption, an exponential-width neural network with exponential loss can achieve large margin and low test error. (iii) in a scalar gradient flow where the neurons cannot rotate, it is shown that an exponential-width neural network can find the global max-margin solution (up to constant); for the 2-parity problem, this implies superiority over kernel methods. ", "summary_of_the_review": "I am not very familiar with the max-margin literature, and I did not read the Appendix in details. \nHowever, I believe the results presented in this submission are relevant to the ICLR community. ", "strength_and_weaknesses": "I find this submission fun to read. Despite the highly technical/theoretical content, the authors provide nice intuitive explanations of the analysis in the main text (e.g. on the construction of potential function). Also, the limitations of each approach and comparison to prior results are carefully discussed. I believe the following contributions are meaningful: \n\n- The NTK margin analysis allows the parameters to move up to $\\mathcal{O}(\\sqrt{m})$ and improves the required width in terms of the NTK margin. It is also interesting that the margin-based Rademacher complexity bound has no dependence on the network width (due to manipulation of the homogeneity property).  \n- To my knowledge the scalar gradient flow analysis is novel. It outlines a new assumption (low rotation) that leads to global margin maximization, which differs from prior results that assume noisy dynamics or dual convergence. Moreover, this low-rotation assumption seems to hold empirically when the network width is large. \n\nThe weaknesses of this submission are also clear (as acknowledged by the authors). If we focus on the sample complexity of learning the 2-sparse parity function, then the improvement over existing results is not very significant. While the perceptron analysis is not an NTK proof, the resulting sample complexity does not show any advantage over the NTK model. As for the scalar gradient flow, the required model width still exponential even under this rotation-free parameterization. \n\nI have the following questions/comments. \n\n1. The authors used the 2-sparse parity problem as an illustrative example throughout the paper. What is the motivation of using this particular problem? How would the margin values change if we generalize to $k$-parity? And is the sample complexity still better than kernel methods? \n\n2. Is there an intuitive explanation of why the large-width analysis can only handle the exponential loss? \n\n3. Is the empirically-observed low-rotation property specific to the ReLU (or homogeneous) activation function? \n\n4. A few more related works: the learning of parity-like functions using two-layer neural networks has been studied in [1] [2]. The two-phase algorithm (learning the features and then the second layer) has been analyzed in the regression setting in [3] [4].  \n[1] Refinetti et al. Classifying high-dimensional gaussian mixtures: where kernel methods fail and neural networks succeed.  \n[2] Frei et al. Random feature amplification: Feature learning and generalization in neural networks.  \n[3] Ba et al. High-dimensional asymptotics of feature learning: how one gradient step improves the representation.  \n[4] Bietti et al. Learning single-index models with shallow neural networks.  ", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster