On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias
Authors: Itay Safran
Gal Vardi
Jason D. Lee
Venue: NeurIPS 2022 Accept (2022)
Keywords: Deep Learning Theory
Non-convex Optimization
Gradient Flow

Abstract: We study the dynamics and implicit bias of gradient flow (GF) on univariate ReLU neural networks with a single hidden layer in a binary classification setting. We show that when the labels are determined by the sign of a target network with $r$ neurons, with high probability over the initialization of the network and the sampling of the dataset, GF converges in direction (suitably defined) to a network achieving perfect training accuracy and having at most $\mathcal{O}(r)$ linear regions, implying a generalization bound. Unlike many other results in the literature, under an additional assumption on the distribution of the data, our result holds even for mild over-parameterization, where the width is $\tilde{\mathcal{O}}(r)$ and independent of the sample size.

On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias
Itay Safran" Princeton University
Gal Vardi*
Jason D. Lee
TTI-Chicago and Hebrew University
Princeton University
Abstract
We study the dynamics and implicit bias of gradient flow (GF) on univariate ReLU neural networks with single hidden layer in a binary classification setting. We show that when the labels are determined by the sign a target network with neurons, with high probability over the initialization of the network and the sampling of the dataset, GF converges in direction (suitably defined) to a network achieving perfect training accuracy and having most ((r) linear regions, implying a generalization bound. Unlike many other results in the literature, under additional assumption on the distribution of the data, our result holds even for mild sereparrameterization, where the width is Ö(r) and independent of the sample size.
Introduction
Over-parameterized neural networks are known to be easier to train compared to their smaller coun- terparts, despite the resulting increase in the problem's 's dimensionality and the required computational resources [Daniely, 2017, Allen-Zhu et al., 2018, Safran and Shamir, 2018, Du et al., 2018, 2019, Ji al., 2019, Zou et al., 2020, Li et al., 2020, Safran al., 2021, Zhou et al., 2021]. However what is perhaps more surprising, is that stark contrast to our classic understanding of generalization in machine learning models, this does not learned model in spite of the significant increase in its capacity. It is widely believed that what plays a key role in explaining this phenomenon what is commonly referred to in the literature as implicit bias/regularization [Neyshabur et al., 2014, Zhang et al., 2021], where the optimization algorithm used inadvereently exhibits a bias towards empirical minimizers with certain property that might induce better generalization. For example, such properties may include having a small norm or quasi-norm mussi-norm of the weights (c.g. Neyshabur [2017]. Neyshabur al. [2017]. Lyu and Li [2019], Woodworth et al. [2020], Ji and Telgarsky [2020]) or a low rank solution (e.g. Razin and Cohen (2020]).
degrade the generalization capabilities of the
In this work, we study the dynamics and the implicit bias of GF on univariate ReLU neural networks, with the underlying assumption that the labels are determined by the sign of target network of width r (which thus changes sign between -1 and at most r times). Our analysis reveals that under the assumption of an i.i.d., normally-distributed initialization of the weights and biases of the network, over- pnrerparameterizziionn (i.e. the use of width strictly larger than r) is necessary for attaining a small population loss. Moreover, we also assume that the width scales least linearly (up to logarithmic terms, excluding dependence on the confidence parameter) with the length of the shortest interval on which the labels do not change sign, then with high probability over the initialization of the network and the sampling of the data, vneeparramttiizaaioonn is sufficient for driving the empirical loss to be
Equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

small enough so that all data instances are classified correctly. Thereafter, by analyzing the implicit bias of GF as the time tends infinity, we show that we converge in direction (see Section 2 for a formal definition) to a network having at most (r) linear regions. Since the minimal number of neurons required to express a network with an arbitrarily small loss in general is r, this demonstrates that the implicit bias of GF in our setting is such that optimization converges to solution which effectively has the optimal number of neurons up to a constant factor, which also provides a clear geometric interpretation with an intuitive generalization bound. This is in contrast to norm-based results where the characterization of the implicit bias in function space is less clear. Overall, our analysis provides an end-to-end result on the learnability of univariate ReLU neural networks with respect to GF in a binary classification setting.
The remainder of this paper is structured as follows: After specifying our contributions in more detail below we turn to discuss related work. In Section 2, we present our notations and assumptions used throughout the paper before we present our main theorem. In Section 3 we formally present our optimization result. In Section 4 we turn to analyze the implicit bias of GF in our setting. Finally, in Section 5 we show that the implicit bias leads to a generalization bound.
Our contributions
We prove that when training a sufficiently wide network which is initialized appropriately (Assumption 2.1) and under a suitable assumption on the distribution of the data (Assump- tion 2.2), then with high probability there exists some time to where GF attains training error at most 1 on a size-n sample (Theorem 3.1). Our width requirement depends on the length of the shortest interval where the classificiation does not change sign, which in certain cases requires only mild over- wverppraaeterization with far fewer parameters in the model compared to observations in the dataset (see Remark 2.1).
We show that if GF achieves training error smaller than 4 at some time to. then it converges to zero loss and converges in direction (see Section 2 for a formal definition) to a network with at most (r) linear regions (Theorem 4.2). Since this result provides simple and intuitive geometric interpretation to the implicit bias of GF in our setting, it readily translates generalization bound using standard argument (Corollary 5.1). We point out that unlike our optimization guarantee, this result holds regardless of the initialization of the network.
Finally, we combine our optimization and generalization results to derive our main theorem (Theorem 2.3), which establishes an end-to-end learnability result for GF in our setting. This indicates that a wide model facilitates optimization, yet at the same time implicit bias prevents us from overfitting, even if the architecture we train is far wider than what is necessary. The result holds in the rich regime, and thus provides a guarantee which goes beyond the analysis achieved using NTK-based results (see Remark 2.3).
As an additional contribution, we show (under our assumption on the initialization) that width at least 1.3r is necessary for GF to attain population loss less than an absolute constant over a particular target function (Theorem 3.2). Along with previous results, this shows that over-parameterrizaionn is not just sufficient, but also necessary for successful learning.
We now turn to discuss some of the related work in the literature which is most relevant to ours in more detail.
Related work
Implicit bias in neural networks. The literature on the implicit bias in neural networks has rapidly expanded in recent years, and cannot be reasonably surveyed here (see Vardi [2022] for a survey). In what follows, we discuss only results which apply to depth-2 ReLU networks.
By Lyu and Li [2019], Ji and Telgarsky [2020] homogeneous neural networks (and specifically 2 ReLU networks) trained with exponentially-taile classification losses converge in direction to KKT point of the maximun-margin problem. Our analysis of the implicit bias relies on this result. We note that the aforementioned KKT point may not be global optimum (see discussion in Section 4). For 2 ReLU networks trained with the square loss there are no known guarantees on the implicit bias (cf. Vardi and Shamir [2021], Timor et al. [2022]).

---

Several works in recent years studied the implication of minimizing the l2 norm of the weights on the function space in 2epth-2 univariate ReLU networks. In Savarese al. [2019] and Ergen and Pilanci [2021a] it is shown that a minimal-norm fit for a sample is given by the linear spline interpolation (i.e., a "connect-the-don is small. The former work considered only regression, while the latter considered both regression and classification. Note that naagii-maximization is equivalent to norm-minimization with margin at least 1. Thus, our result can also be viewed as an analysis of the implication of the bias towards norn-minimization on the learned function. We emphasize three important differences between the results from Savarese et al. [2019], Ergen and Pilanci [2021a] and ours:
function). In such linear spline interpolation the number of linear regions
1. As we already mentioned, the result of Lyu and Li [2019], Ji and Telgarsky [2020] implies a certain bias towards margin maximization, but it does not guarantee convergence to a global optimum (or even to a local optimum) of the maximum- margin problem. The only guarantee is that GF converges point, and (unlike Savarese et al. [2019] and Ergen and Pilanci [2021a]) it does not assume convergence to global optimum. As result, we are able to obtain provable generalization bounds for GF.
KKT point. Our result relies only convergence to such KKT
2. In Savarese et al. [2019] and Ergen and Pilanci [2021a] it is shown that the linear spline interpolation minimizes the weights' norms. However, they also show that it is not unique minimizer. Thus, in addition to the linear spline interpolation there are also other networks that fit the training set and minimize the norms. Therefore, even under the assumption that the weights' norms are minimized, their results do not guarantee convergence to a function with small number of linear regions (as in our result).
3. Savarese et al. [2019] and Ergen and Pilanci [2021a] consider norm-minimizatie of the weights without the bias terms, while the implicit bias towards margin-mant maximization due to Lyu and Li [2019]. Ji and Telgarsky [2020] (which we rely on) is w.r.t. all the param- eters, including the bias terms. Hence, the implicit bias in depth-2 ReLU networks with exponentially-tailer losses does not minimize the norms in the sense considered in Savarese et al. [2019], Ergen and Pilanci [2021a].
We note that Ergen and Pilanci [2021b] showed that linear spline interpolators minimize the norms also in deep univariate networks. The result from Savarese et al. [2019] was extended to multi- variate functions in Ongie et al. [2019]. Parhi and Nowak [2020] studied the relation between norm minimization and spline interpolation for a broader family of activation functions. Hanin [2021] gave a geometric characterization of all depth-2 univariate ReLU networks with a single linear unit, that minimize the &g norm of the weights (excluding bias terms) and interpolate a given dataset (in regression setting). Blane et al. [2020] studied the relation between the implicit bias of SGD in depth-2 univariate ReLU networks (in a regression setting) and the number of convexity changes of the learned network. Maennel et al. [2018] showed that for given training dataset there only finitely many functions that GF with small initialization may converge to in depth-2 ReLU networks, independent of the network size. Chizat and Bach [2020] studied the dynamics of GF on infinite width depth-2 networks with exponentially-taile maximization w.r.t. certain function norm known as the variation norm. Phuong and Lampert [2020] studied the implicit bias in depth-2 ReLU networks trained on orthogonally separable data.
losses and showed bias towards margin
Convergence of gradient methods under extreme paramttrrizaaiinnnn In recent years, many theoretical works have focused on providing convergence guarantees for training depth-2 neural networks with non-linear activations. Andoni al. [2014] provide convergence guarantee for learning polynomials of degree r in d-dimensional space in a regression setting using networks of width roughly der. Since their architecture excludes bias terms which can be simulated by incrementing the input dimension by 1, their result in fact requires width 22r in our univariate setting, whereas our width requirement typically much milder. Following the success of the NTK [Jacot et al., 2018 8]. a spate of papers provided convergence guarantees when training using GD (e.g. [Allen-Zhu et al., 2018, Du et al., 2018, 2019, Ji et al., 2019, Zou al., 2020]). The main difference that sets our work apart is that our width requirement is given in terms of the complexity of the teacher network, irrespective of the sample size n, whereas these works require that the width scales polynomially with n, which could be significantly larger. Moreover, as mentioned earlier, such results operate in the lazy regime where the features that are learned are dictated mainly by the initialization rather than the training process, whereas our analysis enters the rich regime once the
3

---

loss becomes sufficiently small, and provides result that goes beyond NTK- basee analyses. On the flip side, our analysis only holds for binary classification in the mee-iimnsioonl setting. Similarly to us, Soltanolkotabi et al. [201 8] provide convergence guarantees by establishing that the objectíve function satisfies the PL-condition (see Polyak [1963]) however unlike our optimization guarantee and similarly to previously discussed works, their result requires that the network has more trainable parameters than data instances. Chizat et al. [2019] establish that by scaling a model appropriately, we can effectively interpolate between the lazy and the rich regime. While we use this observation in our optimization result to drive the loss to become sufficiently small in the first stage of optimization, our implicit bias result nevertheless operates in the rich regime regardless of this scaling.
Teacher-student setting and mild pauerarrattteiiaiionn. In this paper, we assume that the labels of the data are determined by the sign of teacher network of width r. Such similar teacher- student setting but for a regression problem allowed the study of mild over-paramette per-paraantterzzaionn in quite few recent works. Safran and Shamir [2018], Arjevani and Field [2020, 2021] show the existence of spurious (non-gd mon-globbl)) local minima in the loss landscape in this setting. Other works provide certain recovery guarantees; assuming absolute value activations, Li et al. [2020] provide a global convergence guarantee to loss at most (1/r), and Safran et al. [2021], Zhou et al. [2021] provide local convergence guarantees for ReLU or absolute value activations. These works require width at least poly(r) for convergence, whereas in our setting show that width ((r) suffices in certain cases, and that over reeepprrameterization is also necessary for successful optimization under our assumptions. While our results might superficially seem to provide stronger guarantees, we stress that the seemingly stronger bounds we derive are made possible in part due to the different assumptions made which include a univariate domain with biases compared to a multivariate domain with no biases nor output layer weights, thus highlighting the difference between the two architectures. In light of this, we argue that the bounds in these results are not directly comparable to ours.
2 Preliminaries and main result
Notations. We use bold-face letters to denote vectors, e.g., x (i,,...,ra)) For x Rd we denote by ||x|| the Euclidean norm. We denote by [:] the indicator function, for example 1 2 5] equals 1 t 2 5 and 0 otherwise. We denote sign(2) 1 if 2 0 and -1 otherwise. For integer 2 1 we denote [d] = {l....,dd d}. We use standard asymptotic notation O(-) to hide constant factors. function f: - I which is twice continuously differentiable in a domain D S Rd is said to satisfy the Pl.-condition there exists such that 1 [|V[(x)]]² 2 A(f(x) - f*), where f == infx (xx.
Neural networks. The ReLU activation function is defined by o()) max 10,ax(0,,33 z). In this work we consider depth-2 ReLU neural networks with input dimension 1. Formally, depth-2 network No of width is parameterized by 0 = [w, b, v] where w, b, E IR*, and for every input x E IR we have
No(w)= Σ uoolwy bz).
JE(M]
We sometimes view θ as the vector obtained by concatenating the vectors w, b, Thus, ||0] denotes the lg norm of the vector O. We denote
(0; = (x)
Given network, (No() above, refer to the set of its non-differentiable points (w.rt. the variable I)) as its breakpoints.
Gradient flow (GF) and implicit bias. Let S (<,,,)) C x (-1,1} be binary classification training dataset. Let (0;-) : IR + IR be a neural network parameterized by 0. For a loss function & IR- + R the empirical loss of (0;--) on the dataset 5 is
(())- = 1
((.,0(0;
(2)
We focus the exponential loss E(g)) = - and the logistic loss f(g) log(1 + e9)

---

We consider GF on the objective given in Eq. (2). This setting captures the behavior of GD with an infinitesimally small step size. Let ((t) be the trajectory of GF. Starting from an initial point ( the dynamics of (t) are given by the differential equation de(c) dt E - (()()). Here, 0 denotes the Clarke subdifferential, which is generalization of the derivative for non-differentiable functions (see Appendix A for formal definition). We say that trajectory 0 (t) converges in direction to 0 if
lim
((4) 0" (C)I
| 11
2.1 Assumptions
Our main result holds under the following assumption the initialization of the weights of the network.
Assumption 2.1 (Network initialization).
The weights and biases ws, b, of each neuron E [k] in the hidden layer are i..dd and satisfy
Wi, b, ~ ((0,0))
The weights us i E [k] of the output neuron are i.i.d. and satisfy
~ (0,
We point out that our particular choice of normally distributed weights is not essential, and that our results will also hold for example under the assumption of uniformly distributed weights, but with a slightly different proof and constants in the resulting bounds. To facilitate our analysis, we make the following assumptions on distribution of the data and its corresponding labels.
Assumption 2.2 (Data distribution). There exist a natural and real R 2 1 and C,p > 0 such that following hold:
There exists depth-2 ReL.U network No of width r such that the examples (x. y) of the data satisfy ~ 'D and sign(X*((t)
The density D denoted by p. satisfies plz) 0 for all $ [- R.R. R).
sup, u(x)= S.C. C.
p >> 0 is the length of the shortest interval I S [-R, R. R) such that sign(N (x)) is the same for all x I, and for all I', there exist x. x' I' such that sign(N" (x)) + sign(N* (x))).
remark that the above assumption mostly mild. The main non-trivial requirement is that the distribution is compactly- y is continuous on for example, and any target function that changes sign at most r times can be expressed by network of width r.
however the last two assumptions always hold for some C, >> 0
2.2 Main result
Having stated our assumptions, we now turn present our main theorem in this paper. Theorem 2.3. Under Assumptions 2.1 and 2.2, given any 8 E (0, 1), suppose that the following hold
r rlog(1/e) log(2/5)
Re log 8
2 Co
1: 2 6144
Th 2 8400
O, 4k Ran log 12k
8p
where Co universal constant. Then with probability least 8 over the randomness in the initialization of the network and the sampling of a size-n dataset, GF converges to zero loss,
We also remark that the assumption R > 1 is only for simplicity of presentation, since our results also hold for any R < with the same bounds get when plugging R = 1.
5

---

and converges in direction to 0 such that the network Ng. has at most 32r + 67 linear regions and satisfies
P PEWD (sign(No= & sign(N" (x))) S..
Our theorem is result of breaking the proof into two different stages and combining them using a simple union bound. Specifically, at the first stage we use Theorem 3.1, which establishes that the empirical loss drops below 1 with high probability; and in the second stage we use Corollary 5.1 to argue that the implicit bias takes effect once the empirical loss is sufficiently small which results in generalization bound. The theorem suggests two interesting implications: (i) We may train an arbitrarily wide network without risk of overfitting since the implicit bias of GF dictates that we converge to a model with low capacity;² and (ii), we further gain a sample complexity bound which independent of p and R. We also note that only the direction of 0 affects the classification and the number of linear regions in No. and that the scale of 0 is not important here. Namely, for every 0, and every a > 0 we have No (x) = aNNo (z(),, and thus the scale of 0 affects only the scale of the outputs of No and not the classification nor the partition to linear regions and therefore nor does it affect the generalization properties of 0.
Lastly, we remark that our initialization scheme used in Theorem 2.3 is somewhat unorthodox, in the sense that we require the hidden layer to have rather large variance which scales polynomially with the sample size. While in practice it is more common that the weights in the hidden layer have a smaller variance (e.g. Glorot and Bengio [2010], He et al. [2015]); our scaling prevents the breakpoints of the neurons in the trained network to move too much before we are able to decrease the training error sufficiently, and the impact of the magnitude by which we scale the hidden layer upon initialization on the dynamics of GF was studied in similar univariate regression setting [Williams et al., 2019, Sahs et al., 2020]. We now conclude the discussion of our main result with the following remarks on the setting studied in our paper.
Remark 2.1 (Mild vs. extreme over- parameterrraztiinn) In this paper, we make a distinction between what we call the mild over- parameterization regime, where the required width of the network k scales with but not with the sample size n; and the extreme over- wver-paramtterization regime, where the width k' of the network exceeds n. Under this distinction, for sufficiently large n, we will always have that n W, and thus < k'.
Remark 2.2 (GF vs. GD). It is important to stress that our results hold for GF which ignores computational considerations and does not necessarily imply the convergence of GD. For this reason, it is of utmost importance to generalize our results to hold for GD rather than just GF. That being said, there is some recent evidence suggesting that at least in certain cases. positive results GF may be translated to GD [Elkabetz and Cohen, 2021]. Moreover, at the very least, Theorem 3.1 can indeed be generalized to hold for GD (see discussion after the theorem statement). In any case, for the sake of coherence we focus in this paper on GF, and we leave generalizations for GD as an important fature work direction.
Remark 2.3 (Rich vs. lazy regime). Our optimization analysis operates in the lazy regime where the hidden layer does not move much and most of the learning is performed in the output neuron. However, once our analysis goes into the second stage where the implicit bias takes effect, we essentially move into the rich (aka the feature-lerrning) regime, where redundant features (i.e. excess neurons) are being effectively discarded at the limit t + oo. In light of this, as was discussed in the related work section, our result provides guarantee which goes beyond the analysis achieved using -hasedd results.
3
Over-paramettriration leads to small empirical loss
In this section, we analyze the dynamics of GF on the objective defined in Eq. (2). Our main contribution is to establish that sufficient permpearatttiizitionn guarantees that GF leads to point with empirical loss which is sufficiently small. Formally, we present the following theorem.
3 'Note that in our univariate setting we can deduce r by analyzing data and possibly estimate minimal required width for attaining small training error using our derived bounds, however in more general settings (e.g. the multivariate case) may not be easily deduced from the dataset, which might prompt us to train the widest network possible given available computational resources.

---

escape the neighborhood in Theorem 3.1. Under Assumptions 2.7 and 2.2, given any d E (0, 1), suppose that the following hold
24r R log
P2CR355vt and
1
k 2 6144
O 2 4200
(3)
P
6p
4k 4kRoa log
6K
Then with probability at least 1 ó over the randomness in the initialization of the network and the sampling of a size-n dataset, there exists time to such that GF initialized from ( reaches a point (1o) satisfying
1
((O(t))) 2n
The above theorem essentially requires that we use width which is proportional to 1/p up to logarith- mie factors to facilitate optimization. If p 22 (r) then this requires that we over-parameterize by multiplicative constant up to logarithmic factors. We remark that result can also be adapted to hold for GD rather than GF with a polynomial number of iterations." In any case, as discussed in Remark 2.2, we stress that focus here is to show that GF attains sufficiently small loss so that our implicit bias analysis takes effect, and we leave generalizations for GD and milder width requirements for future work.
The proof of the above theorem, which appears in Appendix C, relies on over- pereparameterizing sufficiently to the extent of having at least three breakpoints each constant segment where the data does not change classification, and four additional neurons that are active on the data instances. The key observation is that under such peee-parameterization, we can identify direction in weight space which moves the current network configuration in a manner which strictly decreases the objective value. This allows to establish that the objective function satisfies the PL-condition locally in a neighborhood around our initialization. Finally, by bounding the length of the trajectory of GF, show that the objective value decreases to which the PL-condition satisfied.
1 before
Interestingly, Theorem 3.1 already implies generalization bound if the sample size is sufficiently larger than the degrees of freedom in the student network. Nevertheless, such an approach alone not capable of obtaining sample complexity which is independent of and R (since the width of the student network and thus also capacity scale with these parameters, implying generalization bound that explicitly depends them). Moreover, understanding the implicit bias of GF is of independent interest, even if we ignore the improvement provides to the sample complexity.
It is natural to explore what is the minimal amount of over parameterization required for attaining small loss in our setting. modest requirement is that we are able make the generalization error arbitrarily small given sufficiently large sample. It is thus interesting to present the following theorem, which establishes that under Assumption 2.1, GF is not capable of attaining loss below an absolute constant unless k 2 [1.3r]. regardless of the sample size.
Theorem 3.2. Define the population loss of network with weights O w.r.. a distribution D and teacher network (-) as
(D( = E [e(No(z) sign(N((x)))) I-D
Let > 1 and suppose that an architecture as in Eq. (1), having width k = |or] ] is initialized according to Assumption 2.1. Then there exists distribution D and (-) of width such that for any time t 2 0 and any 2 1, for size-n sample drawn from D and labeled by sign(N* (-)), with probability least 0.25 over the initialization of the network, GF trained on Eq. (2) attains population loss at least
1 0.75a).
(o(((t))
4
Thus, under the theorem's assumptions, over-parameterizzation by a constant factor required. We refer the reader to Appendix D for the construction of 'D and (* some further discussion, and the full proof of this lower bound.
'To show this, one would need to bound the length of the trajectory of GD for objectives that satisfy the PL-condition locally. See Appendix C for further detail.
7

---

The implicit bias of GF
In this section, we show that GF converges to networks where the number of linear regions is minimal up to constant factor. We first give some required background and discuss an important result on the implicit bias which applies to depth-2 ReLU networks, and then state our result.
4.1 Required background
The following theorem gives an important characterization of the implicit bias in depth-2 ReLU networks:
Theorem 4.1 (Lyu and Li [2019], Ji and Telgarsky [2020]). Let ((0;-) be a depth-2 2 ReLU neural network parameterized by 0. Consider minimizing either the exponential or the logistic loss over binary classification dataset ((x4,))) using GF. Assume that there exists time to such that
((O( 1 n'
namely, y, (tt); xz) > 0 for every Is, Then, GF converges in direction to a first order stationary point (KKT point) of the following maximum margin problem in parameter space:
min 0
|1012
S.L.
Vie [n] y: 21
(4)
Moreover, L(O(t)) + 0 and ||0(t)] as t oo.
We note that the above theorem holds for the more general case of homogeneous neural networks (in parameter space), but for this work it suffices to consider depth-2 networks, which are indeed homogeneous. Note that in ReLU networks Problem (4) is non-smooth. Hence, the KKT conditions are defined using the Clarke subdifferential. See Appendix A for more details of the KKT conditions. Theorem 4.1 characterized the implicit bias of GF with the exponential and the logistic losses for depth-2 ReLU networks. Namely, even though there are many possible directions TØT that classify the dataset correctly, GF converges only to directions that are KKT points of Problem (4). We note that such KKT point not necessarily a global/local optimum (ef. Vardi et al. [2021]). Thus, under the theorem's 's assumptions, GF may not converge to an optimum of Problem (4), but it is guaranteed to converge to a KKT point. This is demonstrated in the following example for the case of depth-2 univariate networks, which is our focus.
Example 1. Let No be a depth-2 univariate network of width 2, namely,
No(x) v1o(w11 b,) + U20 (W12 + b2))
Let S = ((11, Vr), (22.82)) be a size-2 dataset such that Xı = 4, I2 = -4 and y/ = Y2 = 1. Suppose that we train No the dataset 5 using GF with the exponential or the logistic loss, and that the initialization ((0) is such that bj 01 and wT = W2 = b2 = 0. Note that
1 (()(0)) - 20(1)
1 2
(for both the exponential and the logistic loss). Hence, by Theorem 4.1 GF converges to zero loss, and converges in direction to KKT point 0" of Problem (4). By observing the gradient V VoC(O) it is not hard to show that for every time we have Wz((t) = b2(t) = (z(() = 0, namely, the second neuron remains inactive, and we have 0* (()) (see Appendix B for details). However, 0" is not g global optimum of Problem (4). Indeed, consider 6' such that w 2 = 0/2 = 4, w// = - and
& b/2 = O. Then, y:Nor (I;)) = for all E [1,2], and we have |00 I|2 = 1 < 2 10
The above example implies that although GF has a certain bias towards margin maximization (as shown in Theorem 4.1), it may not maximize the margin. Hence, we cannot obtain margin-baseed generalization bounds based on the bias towards margin maximization.
4.2 Characterization of the implicit bias
We now state main result on the implicit bias:
8

---

Theorem 4.2. Let S = (1) CRX(-1,1) be dataset such that 21 <... E...& In- and for all [n]] we have y (Ii) > where :R:R= + R is a depth-2 ReLU network of width r. Note that Hi E (n- yı + ye+1 H I r. Consider GF depth-2 neural network No w.I. the dataset S. Assume that there exists time to such that
((O(t))) 1
Then, GF converges to zero loss, and converges direction to a KKT point 0* of Problem (4), such that the network N has at most 32r + 67 linear regions.
Since the labels in the dataset S may switch sign times, then network that correctly classifies S must contain at least linear regions. Hence, the theorem implies that GF minimizes the number of linear regions up to constant factor. We remark that the constants 32 and 67 in the above result can be improved, but we preferred here a simpler proof over a tighter bound.
The formal proof of the theorem is given in Appendix E. Below we discuss the high-level approach. By Theorem 4.1, if there exists time to such that (t)( x then GF converges to zero loss, and converges in direction to KKT point of Problem (4). We denote
No(w) = Σ
0yo(wyy b2).
JE
Assume that No satisfies the KKT conditions of Problem (4). Thus, there are A An 2 0 such that for every j E [K] we have
Wy
A Ow,
(x=))
Σ
(5)
iE(m]
where o'. is subgradient of a at wi
+ bj. and A 0 if (xx) + Likewise, we have
i
by = Σ
(vnNo(a))))
Σ ie(n
bb
xEfn]
In the proof we show using a careful analysis of Eqs. (5) and (6) that in an interval [xpp Fig where the labels do not switch sign (i.e., Mp 1/p+1 kinks. Since the labels switch sign at most r times then we are able to conclude that No has (rr) kinks required.
Wg) the network No has a constant number of
5 Implicit bias leads to a generalization bound
of width r. By Theorem 4.2, if GF reaches sufficiently small loss at some time to. it converges in direction to network A' with O linear regions that classifies the training dataset correctly. Thus, even the width & of the learned network is extremely large, the result in Theorem 4.2 guarantees that GF converges to network with a small number of linear regions. Consider the function f' + (-1, 1) defined by f'(x) = sign(A"(()) Since A' has (rr) linear regions then f' can be expressed by polynomial threshold function of degree (r)) That is, we have fa(x) sign(p' (æ)) where p' polynomial of degree (r)). Since ' attains 100% classification accuracy on the size-n training dataset, then we can view GF as empirical risk minimization (ERM) w.r.t the 0-1 loss over a class of degree- polynomial threshold functions in the realizable setting. The VC-dimension of this class is O(r), and thus we have the following generalization bound w.r.t the 0-1 loss (see, e.g., Theorem 6.8 in and Ben-David [2014]).
Consider depth-2 teacher ReLU network A R
Corollary 5.1. There exists a universal constant Co > 0 such that the following holds. Let N R - R. be depth-2 2 ReLU network of width Let e, (0, 1) and let Cn T Tloo(11// log(1/0)
Let S be a size-n binary classification dataset drawn from a distribution 'D and labeled according to N Consider GF on a depth-2 neural network No w.r.t the dataset S, and suppose that there exists time to such that
((((to)) 1
n

---

Then, GF converges in direction to 0 such that the network No- has at most 32r + 67 linear regions. and with probability least 8 over the sampling of S we have
P P [sign(No~ (x)) + (N
Acknowledgments and Disclosure of Funding
Work done while GV was at the Weizmann Institute of Science. We thank Noam Razin and Gilad Yahudai for pointing out several relevant papers to discuss in the related work section.
References
Z. Allen-Zhu, Y. Li, and Song. A convergence theory for deep learning via over- over-parameterizzatinn. 2018.
arXiv preprini arXiv:
A. Andoni, R. Panigrahy, G. Valiant, and L. Zhang. Learning polynomials with neural networks. In Proceedings of the 31st International Conference Machine Learning, pages 1908-1916, 2014.
Y. Arjevani and M. Field. Analytic characterization of the hessian in shallow relu models: A tale of symmetry. Advances in Neural Information Processing Systems, 33:5441-5452, 2020.
Y. Arjevani and M. Field. Analytic study of families of spurious minima in two-layer relu neural networks: tale of symmetry ii. Advances in Neural Information Processing Systems, 34, 2021.
G. Blanc, N. Gupta, G. Valiant, and P. Valiant. Implicit regularization for deep neural networks driven by an ornstein -aateinnuhhlenbek like process. In Conference on learning theory, pages 483-513, PMLR, 2020.
L. Chizat and F. Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338. PMLR, 2020.
L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
F. H. Clarke, Y. S. Ledyaev, R. J. Stern, and P. R. Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science Business Media, 2008
A. Daniely. Sgd learns the conjugate kernel class of the network. In Advances in Neural Information Processing Systems, pages 2422-2430, 2017.
DLMF. NIST Digital Library of Mathematical Functions. http://dllff Release 1.1.3 of 2021-09-15. URL http: / / dlmmf .nitt gov/. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
S. Du, Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019.
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018.
J. Dutta, K. Deb, R. Tulshyan, and R. Arora. Approximate kkt points and proximity measure for termination. Journal of Global Optimization, 463-1199,, 2013.
O. Elkabetz and N. Cohen. Continuous vs. discrete optimization of deep neural networks. Advances in Neural Information Processing Systems, 34, 2021.
T. Ergen and M. Pilanci. Convex geometry and duality of over-parameterized neural networks. Journal of machine learning research, 2021a.
Ergen and M. Pilanci. Revealing the structure of deep neural networks via convex duality. In International Conference Machine Learning, pages 3004-3014, PMLR, 2021b.
10

---

X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statisties, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
C. Gupta, S. Balakrishnan, and A. Ramdas. Path length bounds for gradient descent and flow. Journal of Machine Learning Research, 22(68):1-63, 2021.
B. Hanin. Ridgeless interpolation with shallow relu networks in 1d is nearest neighbor curvature extrapolation and provably generalizes lipschitz functions. arXiv preprint arXiv:2109.1296/ 2021.
K. He, X. Zhang, S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level per- formance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances neural information processing systems, pages 8571-8580, 2018.
Z. Ji and M. Telgarsky. Directional convergence and alignment deep learning. Advances Neural Information Processing Systems, 33:17176-17186 2020.
Z. Ji, M. Telgarsky, and R. Xian. Neural tangent kernels, transportation mappings, and universal approximation. arXiv preprint arXin:19/0.06956, 2019.
Y. Li, T. Ma, and H. R. Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference learning theory, pages 2613-2682. PMLR, 2020.
K. Lyu and Li. Gradient descent maximizes the margin of homogeneous neural networks, arXiv preprint arXiv:1906. 05890, 2019.
H. Maennel, O. Bousquet, and S. Gelly, Gradient descent quantizes relu network features. arXiv preprint arXiv:1803 1et.:1883.0887,, 2018
B. Neyshabur. Implicit regularization deep learning. arXiv preprint
2017.
B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning, arXiv preprint arXiv:1412.6614 2014.
B. Neyshabur, S. Bhojanapalli, D. McAllester, and N. Srebro. Exploring generalization in deep learning. In Advances in Neural Information Processing Systems, pages 5947-5956, 2017.
G. Ongie, R. Willett, D. Soudry, and N. Srebro. A function space view of bounded norm infinite width relu The multivariate case. arXiv preprint 1rXiv:1910.01635, 2019.
D. B. Owen. Tables for computing bivariate normal probabilities. The Annals of Mathematical Statistics, 27(4):1075-108) 1090, 1956.
R. Parhi and R. D. Nowak. The role of neural network activation functions. IEEE Signal Processing Letters, 27:1779- 1783, 2020.
M. Phuong and C. H. Lampert. The inductive bias of relu networks on orthogonally separable data. In International Conference on Learning Representations, 2020.
B. T. Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki i Matematicheskoi Fiziki, 3(4):643-653, 1963.
N. Razin and N. Cohen. Implicit regularization in deep learning may not be explainable by norms. Advances in neural information processing systems, 13:21174-21187, 2020.
I. Safran and O. Shamir. Spurious local minima are common two-layer relu neural networks. In International conference on machine learning, pages 4433 4441. PMLR, 2018.
I. M. Safran, G. Yehudai, and O. Shamir. The effects of mild reeeparrametrizztioon on the optimization landscape of shallow relu neural networks. In Conference on Learning Theory, pages 3889-3934. PMLR, 1021.
11

---

J. Sahs, R. Pyle, A. Damaraju, J. O. Caro, O. Tavaslioglu, A. Lu, and A. Patel. Shallow univariate relu networks as splines: initialization, loss surface, hessian, & gradient flow dynamics. arXiv preprint arXiv:2008.01772, 2020.
P. Savarese, I. Evron, D. Soudry, and N. Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
M. Soltanolkotabi, Javanmard, and Lee. Theoretical insights into the optimization landscape of over-parameterrzze shallow neural networks. IEEE Transactions on Information Theory, 65(2): 742-769, 2018.
N. Timor, G. Vardi, and O. Shamir. Implicit regularization towards rank minimization in relu networks. arXiv preprint arXiv:2201.1221 /2760, 2022.
G. Vardi. On the implicit bias in deep-learning algorithms. arXiv preprint arXiv:2208.12591, 2022.
G. Vardi and O. Shamir. Implicit regularization in relu networks with the square loss. Learning Theory, pages 4224 4258. PMLR, 2021.
Conference
G. Vardi, O. Shamir, and N. Srebro. On margin maximization in linear and relu networks. arXiv preprint arXiv:2110.027322 2021.
F. Williams, M. Trager, D. Panozzo, C. Silva, D. Zorin, and J. Bruna. Gradient dynamics of shallow univariate relu networks. In Advances in Neural Information Processing Systems, pages 83877 2019.
B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, Golan, D. Soudry, and N. Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635 3673. PMLR, 2020.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
M. Zhou, R. Ge, and C. Jin. A local convergence theory for mildly weerpparameterized two-layer neural network. In Conference on Learning Theory, pages 4577-4632. PMLR, 2021.
D. Zou, Y. Cao, D. Zhou, and Q Gu. Gradient descent optimizes over-parameterized deep relu networks. Machine learning, 109(3):467-492, 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] The paper theoretical in its nature and holds no foreseeable societal impacts as far as we can discern.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
12

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "kTOkr8zQE36", "reviewer": "Reviewer_SJ3s", "summary": "This paper studies the convergence and generalizations of two layer ReLU networks trained by gradient flow (GF). It first gives a convergence guarantee of gradient flow. Then, using this result, the author proves that the gradient flow converges to a predictor whose number of linear regions is minimized up to a constant factor. Finally, using this characterization of implicit regularization, the author shows that two layer ReLU network trained by gradient flow generalizes.", "questions": "(1) The results of this paper only applies to depth two ReLU networks and it seems that the main reason for this restriction is that ReLU network with bias terms is no longer homogeneous when the depth is greater than two. Does a similar result holds for homogeneous ReLU networks (the one without bias terms) of general depth? If the results in [1] could be extended to the non-homogeneous case (i.e. neural networks with bias terms), could the results of this paper be extended to ReLU networks with general depth? Indeed, as observed in [1], the generalized results of [1] still holds experimentally even if the network has bias terms.\n\n(2) This paper gives a nice characterization of the implicit bias of ReLU networks but the same results seem to work for all architectures (I mean the underlying graph of this network). As a result, it does not study how changes in architectures could affect generalization. Is it possible to extend the results in this paper to study the relationship between architectures and generalizations? In linear case, this question has been studied for various architectures [2]. It might be interesting to have some discussions of possible fusions of results in [2] and results in this paper.\n\n\nReferences:\n\n[1] K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv\npreprint arXiv:1906.05890, 2019.\n\n[2] Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural networks:\nAnalysis and design. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors,\nAdvances in Neural Information Processing Systems, 2021.", "limitations": "The authors addressed the limitations of this work but not social impact. However, I think this is fine since the work is theoretical.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The results in this paper are new to the best of my knowledge. The result on implicit regularization of two layer ReLU networks is very interesting. The result on generalization of two layer ReLU network is significant as it helps us understand why neural network generalizes. The presentation is clear.\n\nOne weakness of this paper is that the results are limited to two layer ReLU networks. Thus, it does not explain the success of deep neural networks, which occur more frequently in practice. However, I think the results in this paper is a good beginning to understand implicit regularization and generalization of deep neural networks. Another weakness is that this paper studies gradient flow instead of gradient descent, which is more interesting. However, I still think the results are interesting enough as it is common to first prove something on gradient flow and then discretize the results.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iLeOXmHahX", "reviewer": "Reviewer_THUX", "summary": "This paper studies the dynamics and implicit bias of gradient flow (GF) on two-layer univariate ReLU Networks in a binary setting. It shows that under a teacher network (with r neurons), (over-parameterized) GF is guaranteed to achieve perfect training accuracy, which learns a network that has at most O(r) linear regions. This is characterized by the paper as the implicit bias of GF, which leads to a generalization bound. In addition, the paper proves a necessary condition for successful learning with over-parameterization in terms of a lower bound on the number of neurons.", "questions": "1. Since the theoretical results are derived under a simplified setting, I am wondering what are the implications of your results for more realistic settings that are typically adopted for deep learning? ", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The paper studies an important problem in deep learning theory. The provided characterizations of the underlying dynamics of gradient flow may explain fundamentally the success of gradient-based deep learning.\n\n2. The paper is well-structured, which presents the theoretical results in a coherent and logical way: over-parameterization -> small training error -> implicit bias towards a network with small complexity -> a generalization bound.\n\n3. The result on the sufficiency of over-parameterization for successful learning is new.\n\n\nWeakness:\n\n1. The results of this paper build upon a couple of assumptions with respect to the underlying data distribution and the neural network class. In particular, it assumes a univariate neural network setting, where the inputs have a single feature. This seems to be a strong assumption to me, which should be discussed more in the paper. The challenges of extending the presented results to a multivariate setting, such as [1], are not clear to me.\n\n[1] GRADIENT DESCENT MAXIMIZES THE MARGIN OF HOMOGENEOUS NEURAL NETWORKS, Kaifeng Lyu & Jian Li, ICLR 2020\n\n2. Compared with existing literature that aims to understand the dynamics of gradient descent, the technical contributions of this paper are not clearly presented. It seems that the proof techniques of this paper are based on existing known techniques.\n\nMinor ones:\n\n1. I understand this is a theoretical paper, but synthetic experiments which test the theoretical claims (or even better, experiments under settings that go beyond your assumptions) will largely strengthen the paper. \n\n2. A Typo: point our that -> point out that in line 193\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PqiyswGS7p", "reviewer": "Reviewer_bw4F", "summary": "The paper studies the optimization dynamics and implicit bias of GF on univariate single hidden layer ReLU networks in a binary classification setting. Under some assumptions on the initialization and data distribution, the authors show that sufficiently wide networks attain, with high probability, a training error $\\le \\frac{1}{2n}$, where $n$ is the number of training samples. Then, the authors show that if at some time GF attains a training error smaller than $\\frac{1}{n}$ then it converges to zero loss and converges in direction to a network with at most $O(r)$ linear regions. This implicit bias characterization yields a generalization bound. Finally, the authors combine their results to derive their main result that characterizes GF implicit bias and, with high probability, guarantees convergence to zero loss and a generalization bound for sufficiently wide networks under some assumptions on the initialization and data distribution. To complement these results, the authors demonstrate that without sufficient over-parametrization GF is unable to achieve population loss below some absolute constant.", "questions": "1. Missing citation: \nMulayoff, R., Michaeli, T. and Soudry, D., 2021. “The implicit bias of minima stability: A view from function space”. NeurIPS 2021.\n2. Can you please clarify the difference between $k$ and $k’$ in Remark 2.1?\n3. I think that adding an explanation for what are “breakpoints” will make the paper clearer.", "limitations": "The authors mentioned and justified the limitations of their results. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\nThe paper is clear and well written, and it establishes several important results, detailed above, on GF optimization dynamics and implicit bias for univariate single hidden layer ReLU networks in a binary classification setting.\n\n*Weaknesses:* \nThe main weaknesses, in my opinion, are the assumptions regarding GF (in contrast to GD) and the assumption on $\\sigma_h$ in the initialization, which is not trivial. However, the authors discussed these issues in the paper and despite these limitations, I still think the paper made a significant contribution.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "38AsjP-_mqZ", "reviewer": "Reviewer_X6Ek", "summary": "The paper studies two-layer neural networks with a single input dimension for binary classification with exponential or logistic loss in a teacher-student setting. The teacher network is assumed to have a fixed number of hidden neurons (hence a fixed number of linear regions), and the paper explores the type of solution that gradient flow converges to, if the student network has a (much) larger number of hidden neurons. This reveals that, no matter how many neurons the student network has, gradient flow converges to a solution with small training loss and a restricted number of linear regions. \n\nThe proof is achieved in two steps: (i) Overparameterization implies convergence to sufficiently small loss (with high probability over a certain initialization) where all samples are classified correctly (ii) Gradient Flow then converges to a solution with a limited number of linear regions that depends (linearly) on the target network width (and hence the number of linear regions of the target network).", "questions": "- In what way would the authors argue that their results in the extremely restricted setting (univariate, one hidden layer) can tell us something about deeper networks on more input dimension? \n\n- Similarly, what are the main challenges to go beyond the univariate setting or deeper networks? Is it conceivable that the methods develeoped here can be extended to a more general setting?\n\n- In the lines 360-363: Is it possible to provide an intuitive explanation why the networks converges to a weight configuration with a constant number of kinks in intervals of unchanged label?\n\n- Please clarify line 284 :\"since the number of observations in the dataset far exceeds the degrees of freedom in the trained model“:\nWhat are the \"observations\" this sentence refers to, and does the \"trained model\" refer to the student network? I suppose that the\"observations“ refer to the samples, but since no assumption on the number of samples is made, their number cannot be used as a basis for an argument (\"since the number of....\"). Similarly in the following sentence („since the width of the network and thus also the model’s capacity scale with them, implying a bound that explicitly depends on them“), does\"them“ still refer to these observations?\n", "limitations": "The paper studies a very restricted setting (see above), but all the necessary assumptions are clearly indicated and discussed.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\\+ The authors follow a novel approach that depends on the number of linear regions of the teacher network, irrespective of the sample size. The implicit bias found by the authors in their setting, is geometrically understandable in the sense that the point of convergence is a network with limited number of linear regions in relation to the target network function‘s number of linear regions. \n\n\\+  Since these main results are independent of the sample size, they can then be nicely combined with a generalization bound for finite VC dimension to obtain a generalization bound also for the solution of the gradient flow algorithm.\n\n\\+  While the setting is quite limited (single input dimension, single hidden layer), the results are important for the understanding of the implicit bias of gradient flow (i.e., what solutions are favored by training with gradient flow). The techniques are interesting and novel, and they build upon two recent papers by Lyu, Li and Ji, Telegarsky.  The paper provides complete, detailed proof, which look sound and correct to me (I did not check all the proofs in the supplement in complete detail).\n\n\\+  The authors provide an additional result, which shows that overparameterization is necessary for learnability, i.e., that small loss can be achieved with high probability over the weight initialization no matter the input distribution (with labels given by a 2-layer target network). This rounds up the (simplified) take-away that sufficient overparameterization is both necessary and sufficient for learning with gradient flow (in their setting).\n\n\\+ The paper is very well-written. In particular I appreciated that the author‘s motivate the key ideas of the proofs and clarify their assumptions and limitations. \n\n\\- The main weaknesses come from the very restricted setting and certain assumptions that are (technically) necessary for the results. Firstly, the proof technique seems to strongly depend on the univariate setting (one input dimension) and the non-existence of additional hidden layers. So it remains unclear how and whether the results could generalize to deeper networks in a more general setting.  Secondly, while the assumptions in Section 2.1 are indeed very mild, the additional assumptions in the main theorems appear stronger in the sense that the network‘s under study may not be similar to networks used in practice: The student network is required to be extremely wide (much larger than the teacher network), and the initialization technique is unconventional (hidden weight samples from a normal distribution with extremely large variance and output weights sampled from a normal distribution with extremely low variance).\n\n*****\nTaken together, I consider this a very nice, carefully composed paper, where the problem of applying only to a restricted setting is largely outweighed by the novel insight.\n*****\n\nMinor additional comments:\n\n- Lines 360-363 explain the idea of the proof, but fail to give an intuition of it: In particular, it would be helpful to (intuitively) explain why(!) the networks converge to weight configuration with a constant number of kinks in an interval where the labels do not change sign.\n\n- The statement in the abstract that something \"may already hold“ is hard to follow if no additional context is given why the result may or may not hold.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept