The inductive bias of ReLU networks on orthogonally separable data
Authors: Mary Phuong
Christoph H Lampert
Venue: ICLR 2021 Poster (2021)
Keywords: inductive bias
implicit bias
gradient descent
ReLU networks
max-margin
extremal sector

Abstract: We study the inductive bias of two-layer ReLU networks trained by gradient flow. We identify a class of easy-to-learn (`orthogonally separable') datasets, and characterise the solution that ReLU networks trained on such datasets converge to. Irrespective of network width, the solution turns out to be a combination of two max-margin classifiers: one corresponding to the positive data subset and one corresponding to the negative data subset.
The proof is based on the recently introduced concept of extremal sectors, for which we prove a number of properties in the context of orthogonal separability. In particular, we prove stationarity of activation patterns from some time $T$ onwards, which enables a reduction of the ReLU network to an ensemble of linear subnetworks.


Published as a conference paper at ICLR 2021
THE INDUCTIVE BIAS OF RELU NETWORKS ON ORTHOGONALLY SEPARABLE DATA
Mary Phuong & Christoph H. Lampert IST Austria
Am Campus 1, 3400 Klosterneuburg, Austria
(bphuong, chi e i ac.at
We study the inductive bias of two-layer ReLU networks trained by gradient flow. We identify class of easy-to-lear ('orthogonally separable") datasets, and characterise the solution that RcLU networks trained such datasets converge Irrespective of network width, the solution turns out be combination of two max-margin classifiers: one corre- sponding to the positive data subset and one corresponding to the negative data subset.
The proof is based on the little-known concept of extremal sectors, for which we prove number of properties in the context of orthogonal separability. In particular, prove stationarity of activation patterns from some time T onwards, which enables reduction of the ReLU network to an ensemble of linear subnetworks.
INTRODUCTION
This paper is motivated by the problem of understanding the inductive bias of ReLU networks, or to put it plainly, understanding what it is that neural networks learn. This is fundamental open question in neural network theory; it is also a crucial part of understanding how neural networks behave on previously unseen data (generalisation) and it could ultimately lead to rigorous priori guarantees on neural nets' behaviour.
For long time, the dominant way of thinking about machine learning systems was as minimisers & Ben-David] (014)) However, this paradigm
of the empirical risk (Vapnik 1998 has turned out to be insufficient for understanding deep learning, where many empirical risk min- imisers exist, often with vastly different generalisation properties. To understand deep networks, we therefore need more fine-grained notion of 'what the model learns'.
This has motivated the study of the implicit bias of the training procedure- - the ways in which the training algorithm influences which of the empirical risk minimisers attained. This is a productive research area, and the implicit bias has already been worked out for many linear models Notably, Soudry et al. (2018) consider a logistic regression classifier trained on linearly separable data, and show that the normalised weight vector converges to the max-margin direction. Building on their work, Ji & Telgarsky| 2019a) consider deep linear networks, also trained on linearly separable data, and show that the normalised end-to-ena weight vector converges to the max- max-margin direction. They in fact show that all first-layer neurons converge to the same 'canonical neuron' (which points in the max-margin direction). Although such impressive progress linear models has spurred attempts nonlinear extensions, the problem is much harder and analogous nonlinear results have been elusive.
In this work, provide the first such inductive-biar result for ReLU networks trained on "easy" datasets. Specifically, we
propose orthogonal separability of datasets as a stronger form of linear separability that facilitates the study of ReLU network training.
prove that a two-layer ReI.U network trained on an orthogonally separable dataset learns a function with two distinct groups of neurons, where all neurons in each group converge to the same 'canonical neuron',
characterise the directions of the canonical neurons, which turn to be the max-margin directions for the positive and the negative data subset.
A more thorough overview of related work be found Section

---

Published as a conference paper at ICLR 2021
The proof is based on the recently introduced concept of extremal sectors (Maennel al.) 2018) which govern the early phase of training. Our main technical contributions are a precise charac- terisation of extremal sectors for orthogonally separable datasets, and invariance property which ensures that the network's activation pattern becomes fixed at some point during training. The latter allows us treat ReLU networks late in training as ensembles of linear networks, which are much better understood. We hope that a similar proof strategy could be useful in other contexts as well.
SETTING AND ASSUMPTIONS
In this section, we introduce the learning scenario including the assumptions we make about the dataset, the model, and the training procedure. We consider binary classification. Denote the training data {(x, y:) y:] with x; E Id and y/ E {=1} for all i [n]. We denote by X E RR the matrix with {x,} columns and by y R the vector with {vr} entries.
Orthogonally separable data. A binary classification dataset (X,y) is called orthogonally sepa- rable if for all j E [n].
x x 0, x x S 0,
if yo yj
if + My-
In other words, dataset orthogonally separable iff it is linearly separable, and any training exam- ple can serve as linear separator. Geometrically, this means that examples with y = 1 ('positive examples') ) and examples with yı - (" ('negative examples') lie in opposite orthants.
Two-layer ReLU networks. rameterised by 0 - (W,a), a), as
define two-layer width-p fully-connected ReLU networks, pa-
So Rd - R fo(x) 2 a ((W),
where W A [wi.... wp|T Rpxd and a A lar..... apl E Rp are the first- and second-layer weights of the network, and p is the element-wise ReLU function, p(z); max (0, 21). We will often view the network as a collection neurons, {(a,, w,))
Cross-entropy loss.
We assume training loss of the form
(()) Σ (x)))x:)),
(u) A log(1 + exp (-y;u));
this is the standard empirical cross-entropy loss. More generally, our results hold when the loss is differentiable, is bounded and Lipschitz continuous, and satisfies -y,C(() > 0 for all IR.
Gradient flow training. We assume the loss optimised by gradient descent with infinitesimally small step size, also known as gradient flow. Under the gradient flow dynamics, the parameter trajectory an absolutely continuous curve (0(t) 0) satisfying the differential inclusion
a0(t) E -)()(t)),
for almost all t [0,00),
(4)
at
where de denotes the Clarke subdifferential (Clarke 1975 Clarke the gradient to not-everywhere differentiable functions,
2008 of L, extension of
de(0) A conv
lim Ve(Ox) 0, } k0000
(5)
(t) is the value of the parameters at time t, and we will use the suffix (t) more generally to denote the value of some function of 0 at time f.
2

---

Published as a conference paper at ICLR 2021
Near-zero balanced initialisation. We assume that the neurons {wy} are initialised iid from the Gaussian distribution and then rescaled such that |wy]l I X, where À > 0 is a small constant. That is, wj = X/ |ys|l for v, i N(O. I) and arbitrary X5 satisfying ' E (0, A]. We also assume that dj E { These technical conditions ensure that the neurons are balanced and small in size, [|w | Fo O, which simplifies the calculations involved in the analysis of gradient flow.
Support examples span the full space. We assume that the support examples of the positive data subset {x; 8/ = }} span the entire R and similarly that the support examples of the negative data subset {x; 8/ 1} span Rd. (We formally define support examples after introducing some more notation below.)
3 MAIN RESULT
Under the assumptions of Section 2 the network converges to a linear combination two max- margin neurons. Specifically, given a dataset y), define the positive and the negative max- margin vectors W+, w- E IR as
W+ = arg min ||w||
subject to ||] subject to w
w X2 2 for i: yi = 1,
(6)
W- = arg min
W x for i Yi =1
We call examples which attain equality in eqs. (6) and positive support examples and negative support examples respectively. We now state the main result.
Theorem 1. Let Se be a two-layer width-p ReLU network trained by gradient flow with the cross- entropy loss, initialised near-zero and balanced. Consider an orthogonally separable dataset (X. y) such that its positive support examples span Ed and its negative support examples also span I2 For almost all such datasets and with probability 1 1--1 1/2" over the random initialisation.
W(t) (uw], + zww
+
as 00,
(8)
F
for some u, z R., such that either u, 0r 2; for all E [p]. Also,
a(l)
(ull 2||w-11) 0, [a()]l
co.
The theorem says that each neuron (row of W), properly normalised, converges either to a scalar multiple of the positive max-margin direction, u. or to scalar multiple of the negative max- margin direction, 2, w... In other words, there are asymptotically only two distinct types of neurons, and the network could in principle be pruned down to width of just two. These two 'canonical neurons' moreover have an explicit characterisation, given by eqs. (6) and (7).
As for the second-layer weights, the magnitude of each aj equals the norm of the respective wj, and the sign of a, is +1 if w, approaches w4 and -1 w, approaches w..
The following corollary summarises the above in terms of the function learnt by the network.
Corollary 1. Under the conditions of Theorem 7 there exist constants 2 0 such that
[x [10())12
+ up(w]x)) =p(wIx),
as + oc.
(10)
3.1 DISCUSSION OF ASSUMPTIONS
Many of our assumptions are technical, serving to simplify the analysis while detracting little from the result's 's r These include infinitesimal step size (gradient flow), balancedness at ini- tialisation and the condition on support span. The first two could potentially relaxed to their
Forrmalyy this means that (x:} are sampled from any distribution with a density wrt. the Lebesgue measure, then the theorem (treated as an implication) holds with prohability one wrt. the data.
We verify experimentally Section 5.1 that these assumptions are indeed crucial.
3

---

Published as a conference paper at ICLR 2021
approximate counterparts, i.e. gradient descent with small constant step size and approximate bal- ancedness (Arora et al. 2019). The assumption that support vectors span IR comes from Ji & Telgarsky (2019)); Soudry al. (2018). It seems to us that it could be lifted, though have not investigated this possibility depth.
Two assumptions that deserve more attention near-zero initialisation and orthogonal separabil- ity: both are crucial for the result to hold. Near-zero initialisation grants neurons high directional mobility early in training, allowing them cluster close the canonical directions. Orthogonal separability ensures that the canonical directions are 'easy to find' by local descent. In prior work, which considered linear networks, this role is fulfilled by linear separability. The reason we need stronger condition is that ReLU updates are more local compared to linear updates: a linear neuron takes into account all examples in the training set, whereas ReL.U neuron updates only on exam- ples in its positive half-plane (its active examples). ReLU neurons therefore easily get stuck in variety directions, unless the data is highly structured.
PROOF SKETCH
In the analysis, distinguish between phases of training. The first phase takes place close to the origin, ||0| = 0. In this phase, while neurons move little in the absolute sense, they converge in direction to certain regions of the weight space called extremal sectors.
4.1 CONVERGENCE TO EXTREMAL SECTORS
(All definitions and results in this subsection are by Maennel et al. (2018). We need them later on.)
Sectors are regions in weight space corresponding different activation patterns. They are impor- lant for understanding neuron dynamics: roughly speaking, neurons in the same sector move in the same direction.
Definition (Sector). The sector associated to sequence signs o E (-1,0,1) is the region in input space defined
S a (w Rd
sign w = o,, i i [n]].
(11)
We may also refer to the sign sequence a itself as a sector
Some sectors are attractors early in training, i.e. neurons tend to converge to them. Such attracting sectors are called extremal sectors. To give a formal definition, we first introduce the function G: gd RR
G(w) Σ ((W))p((Tx.)))
(12)
Intuitively, (normalised) neurons early in training behave as they were locally optimising G, they therefore tend to cluster around the local optima of G. We formally define extremal sectors sectors containing these local optima.
Definition 2 (Extremal directions and sectors). We say that Sd is positive extremal di- rection, if it is a strict local maximum of G. We say that w is a negative extremal direction if it is strict local minimum of G. A sector is called (positive/hegative) extremal, if it contains a (posi- tive/negative) extremal direction.
The following lemma MMennel et al. 2018 Lemma 5) shows that all neurons either turn off, i.c. become deactivated for all training examples and stop updating, or converge to extremal sectors.
Lemma 1. Let two-rayer ReLU network fe be balanced initialisation and trained by gradient flow. Assume that the loss derivative E is Lipschitz continuous. Then, for almost all datasets and almost all initialisations with X small enough, there exists time T such that each neuron satisfies one of these three conditions:
(T) 8. where
and w remains constant for t 2 T.
(T) > 0 and wy (T) E 8 where is a positive extremal sector, or
(T) < 0 and (T) E 8 where is negative extremal sector.
4

---

Published as a conference paper at ICLR 2021
4.2 ORTHOGONAL SEPARABILITY: TWo ABSORBING EXTREMAL SECTORS
Lemma shows that by the end of the early phase of training, neurons have converged to extremal sectors. Although eq. (12) shows that the number extremal sectors depends only on the data (i.e. is independent of model expressivity), it is priori unclear how many extremal sectors there are for a given dataset, or what happens once neurons have converged to extremal sectors. We now answer both of these questions for orthogonally separable datasets.
First, we claim that for orthogonally separable datasets, there are only two extremal sectors, one corresponding to the positive data subset and one corresponding the negative data subset. That is, by converging to an extremal sector, neurons "choose' whether to activate for positive examples or for negative examples. They thus naturally form two groups of similar neurons.
Lemma 2. In the setting of Theorem 7 there is exactly one positive extremal direction and exactly one negative extremal direction. The positive extremal sector a is given by
if y) 1.
of
1, if yj 1 and x x; < 0 for some i with yi 1,
(13)
0,
if y1 -1 and X x; = 0 for all i with = 1,
and the negative extremal sector o is given by
1, if yj 1,
1, if 1/j 1 and x x; < 0 for some with y -1,
(14)
0, yf 1 and x = 0 for all with yi = -1.
Second, we show that once a neuron reaches an extremal sector, remains in the sector forever, i.e. its activation pattern remains fixed for the rest of training.
Lemma 3. Assume the setting of Theorem
time T the neuron (aj, wj) satisfies aj and w, (T) E Sg where a is the positive extremal sector (eq. (13), then for 2 T, wy(t) E 8 The same holds if a, (T) < 0 and a is the negative extremal sector (eq. (14).
4.3 PROOF OF THEOREM I
Once neurons enter their respective absorbing sectors, the second phase of training begins. In this phase, the network's activation patterns are fixed: some neurons are active and update on the posi- tive examples, while the others active and update on the negative examples. The network thus behaves like an ensemble of independent linear subnetworks trained on subsets of the data. Once this happens, it becomes possible apply existing results for linear networks; in particular, each subnetwork converges to its respective max margin classifier.
We give more details in the proof below.
Proof of Theorem
7 By Lemmas I andd there exists a time T such that each neuron satisfies either
wJ( E 8, where a S 0 and w, remains constant for / 2 T,
(T) 0 and wy e 8 or
aT(T) < 0 and (T) E 8.-,
where o+, o are the unique positive and negative extremal sectors given by eqs. [3 and 14 Denote by Jo. J_ the sets of neurons satisfying the first, the second, and the third condition
respectively. By Lemma 3 if j E O+ then w w,(t) E 8 for all t 2 T, and if E J_ then (1 E S. for 2 T. Hence, for 2 T. if x, is such that y/i = 1 then
fo(x;) A Σ
(gp(w]e x1)
Σ ajw],,
(15)
jElp
JEJ+
5

---

Published as a conference paper at ICLR 2021
Combined with Lemma
A.3
this implies that for le E a+,
Ōak
E
a,w3xx
w/X,,
ky==1
JE8+
(16)
ÖWk
E
e
Σ ,Ea+
a wx]x
Öt
(where we have used that Pw x, for with V/- 1 due to positive extremality). From eq. (6) it follows that the evolution neurons in 34 depends only on positive examples and other neurons in J+. The neurons behave linearly the positive data subset, while ignoring the negative subset. The same argument shows that the evolution of neurons in J- depends only on other neurons in J_ and the negative data subset, which the neurons act linearly. In other words, from time T onwards the ReLU network decomposes into a constant part and two independent linear networks, one trained on the positive data subset and the other trained on the negative data subset.
We can therefore apply existing max-margin convergence results for linear networks to each of the linear subnetworks. Denote by WT [W] or WI. W the three parts of the weight matrix. Then by (Ji & Telgarsky| 2019a] Theorems 2.2 and 2.8) and (Ji & Telgarsky 2020 Theorem 3.1), there exist vectors ú, 2, such that
W W+(1) uw?
+ 0,
as + 00,
(17)
IW -0IIF
W-(1)
TwT
- O, as f + o0.
(18)
[W](1)
(We allow ú, 2 E IR" to account for the fact that 0+, 3_ may be empty). We now need to relate [[ + lee and W-lle y to [Wil In particular, will be useful to show that a limit L + the same is true for [W_())] /log (by the same argument). If 3+ or a_ is empty, this is trivially true and the limit is 0. Otherwise, consider the learning of the positive linear subnetwork, whose objective is effectively e (0) := Eiy. (x)(xx.)). By (Ji & Telgarsky 2019a Theorem 2.2), we know that e (0())) - 0 as t + oc. Following (Lyu & 2020 Definition A.3), define
log has
(0) glog 1 (0)
(19)
++
where g(g) == log (exp(exp(-g)) - 1) for the cross-entropy loss. Then
(t)ll g(log] 1/(+(((()) - log (exp (0(()))
(20)
logt
25(
(7(1) log
Using the Taylor expansion exp(u) 1 O(u) for 0 and (Lyu & Li. 2020 we obtain
Corollary A.1
[ [ - log O
(0(1)) (C++((()))
log O log 1 (0(1) + log log 25(t) logt
(21)
logt
(t( logt
(t)
logt t
By Lyu & Li 2020 Theorem A.7:1), 5 is increasing in t and hence converges; it follows that
[W + (I / log has limit. By (Lyu & Li 2020 Corollary A.11), |/ O(log 4).
implying that the limit is finite and strictly positive. We will denote it by 2t and the analogous quantity for W_ by V_.
We now return to the main thread of the proof. We analyse the convergence of W(t) [[) by analysing Wo/ W (t W+(t) [ and (tt))/ in turn. Since [t(]]]
||oll + ||W, (+) + (ww(())]
[()]
lim 1000
14 + V-
(22)
log 1
Now observe that with probability at least - 1/2" over the random initialisation, 1/4 + V_ > 0 (or equivalently, J+ U3_ * 0). To prove this, let x,+ be any training example with ys+ and let x;-

---

Published as a conference paper at ICLR 2021
be any training example with y4- -1. Then by Lemma B.1 if neuron (aj. w,) is initialised such that aj (0) > O and w, (x) > O then for 2 0, w, ( x, > This holds in particular at time T. The neuron thus cannot be in do nor -_ implying j E J+. Similarly, if the neuron is
initialised such that (0) < and w,(0))x; x- > 0, then j E J_ The probability that one of the
two initialisations occurs for single neuron j is 1/2, P Pw, (0)(0)x > 0] = = for any fixed
x. Hence, the probability that j E do is at most 1 - 1/2 = 1/2, and the probability that [p] S do is most 1/2".
It follows that with probability at least - 1/22,
Wo W()
0,
as 00 00.
(23)
Also, by eqs. 17 and 22
W+(t)
W+(t)
[ 100lFv/llogg Voogt [[(t)] /oogt
VV+
uw
(24)
[W+(1
VV- +
and similarly
W-(t) [(OlF
VV-
Zw
(25)
VV+ +
For E 3+ and t 2 I we moreover know that if = 1 then (t)x; > 0 because w,(() E S
As the same property holds for w+, it follows that ūj 2 0. By similar argument, 2j 2 0. Combining the last three equations then proves eq. (8).
As for eq. (9) we know by Lemma A.4 that a,(t) 8y w wtt()) for some 8j E {+1), implying
[|a((]]| [ (1)ll. Hence, for j E d+.
at
Iw (+)l
(26)
|a(t)]l
W(t
by eq.
24 where u 2 0. For j 24 we also know that ay (t) 2 0, s0 = and
a}(1)
+ uy |++ll-
(27)
|a(t)]
By a similar argument, we obtain that for j E J_,
ag (l) ||(t)]]
- -2 ||
(28)
Finally, for j E Jo. (t) is constant and
ay (f) [a( 0.
(29)
5 EXPERIMENTS
In this section, we first verify that the theoretical result (Theorem I is predictive of experimental outcomes, even when some technical assumptions are violated. Second, we present evidence that similar result may hold for deeper networks as well, although this goes beyond Theorem D
5.1 TWO-LAYER NETWORKS
To see how well the theory holds up, we train a two-layer ReLU network with 100 neurons on syn- thetic orthogonally separable dataset consisting of 500 examples in 2200 The dataset is constructed from an iid Gaussian dataset by filtering, to ensure orthogonal separability and w4 ø -w_ (for visualisation purposes). Specifically, let included with label +1 if it lies in the first orthant and x 2 O, included with label -1 if it lies in the orthant opposite to the first and T 0, and discarded otherwise.
[1, -1, ... 1, -1]. A Gaussian- sampled point is

---

Published as a conference paper at ICLR 2021
We train by stochastic gradient descent with batch size 50 and learning rate of 0.1 for 500 epochs. At initialisation, we multiply all weights by 0.05. This reflects setting where both key assumptions of Theorem | orthogonal separability and small initialisation hold, while the other assumptions are relaxed to approach real-life practice.
Figure 1 shows the results. Figure Th shows the top 10 singular values of the first-layer weight matrix W E IR 100 after training. We see that despite its size, the matrix has rank only two: all singular values except the first two are effectively zero. This is exactly as predicted by the theorem. Furthermore, when we project the neurons on the cositive-variance dimensions (Figure [b), we see that they align along two main directions. To see how well these directions align with the predicted max margin directions, we compute the correlation (normalised inner product) of each neuron with its respective max-mare max-margin direction. Figure shows the histogram of these correlations. We see that the correlation is generally high, above 0.9 for most neurons. Overall we find very good agreement with theory.
a) Top values of W
b) Projected newrons
c) Correlation with max mar-margin
40
1
0.00
0.50
0.75
1.00
Figure I: a) The 10 largest singular values of the first-layer weight matrix W after training. Each dot represents one singular value. b) Neurons (rows of W) projected on the top two singular dimensions. Orange (or blue) dots represent neurons with aj > (or aj < 0). e) Histogram of correlations between each neuron and its respective max-margin direction. (There are 100 neurons in total).
5.2 DEEPER NETWORKS
We now explore the behaviour of deeper networks on orthogonally separable data. We train resid- ual network rather than fully-connected one. The reason for this is that fully-connected networks with small initialisation are hard to train: early in training, the gradients are vanishingly small but then grow very quickly. We therefore found setting numerically stable learning rate rather delicate.
We consider residual network fo Rdd R parameterised by (WI...., W.), of the form
fol (x) = W1x,
(x) fo (x) Wiplfe (x)( (x)),
for [2, L 1],
(30)
fe(x) WLP(Fb (x)),
where p the network's width, and W, Rpxd W, E Rxx and W, E RIxp are its weights.
We train such a four-layer residual net with width 100 on the same dataset and using the same optimiser and hyper-paramette as Section 5. Figure the results. The results are very similar to what we observe for two-layer nets: the weight matrices are all rank two (Figure (h-)), and the weight matrices' rows align two main directions (Figure - It is unclear what these directions are for the intermediate layers of the network, but for the first layer, we conjecture it is again the max-margin directions, as suggested by Figure] 2g.
RELATED WORK
There is a lot of prior work on the implicit bias of gradient descent for various linear models. For logistic regression, (Suudry et al. (2018) show that assuming exponentially-tailed loss and lin- early separable data, the normalised weight vector converges to the max- max--mariin direction. Ji & Telgarsky (009b) extend this result to non-separable data, Nacson al. (2019) extend it to super- polynomially sooomilly-ttileddd losses, and Gunasekar et al. (2018a) considers different optimisation algorithms. For deep linear networks, Ji Telgarsky 2019a) show that the end-to-end weight matrix converges
8

---

Published as a conference paper at ICLR 2021
Top 10 sing.values of W
b) Top 10 sing. valuus of Wa
c) Top 10 Sing.valuee of Wa
8) Correlation with max max- margin
40
30
d) Projected tows of W
e) Projected rows of W
f) Projected rowa of W
20
19.09
0.00
0.25
0.50
0.75
1.00
Figure 2: a-c) The 10 largest singular values of the first-, second- and third-layer weight matrix Wi after training. Each dot represents one singular value. d-f) Neurons (rows of Wi) projected on the respective top two singular dimensions. g) Histogram of correlations between each first-layer neuron and the closest max-margin direction. (There are 100 neurons total).
to the max-margin solution and consecutive weight matrices align. Gunasekar et al. (2018b) consider linear convolutional nets and prove convergence to a predictor related to the 62/r. bridge penalty.
A few papers have started addressing the implicit bias problem for nonlinear (homogeneous or ReLU) networks. The problem is much harder and hence requires stronger assumptions. Lyu & point during training, the network attains perfect classification accuracy. Training from this point onward, Ji & Telgarsky (2020) show that the network parameters converge in direction. [yu & (2020) show that this direction is critical KKT point of the (nonlinear) max- mar-mnariin problem. A complementary approach is taken by Maennel et al. (2018) who analyse the very early phase of training, when the weights are close to the origin. For two-layer networks, they show convergence of neurons to extremal sectors. Our work can be seen as first step towards bridging the very early and very late phase of training.
Li 2020) and [T & Telgarsky (020)) assume that
Zooming out bit, there is also work motivated by similar questions, but taking different approach. For example, [Li & Liang (2018) show that two-layer ReLU nets trained on structured data converge to solution that generalises well. Like ours, their analysis requires that the network's 's activation pat- terns change little, but they achieve by containing training in the neighbourhood the (relatively large) initialisation (this is the standard lazy training argument Chizat et al. (2019)). In contrast, initialise much closer to zero, allowing the neurons to move more. Another related paper is (Ciizat & Bach (020). Using mean-field analysis, the authors show that infinite-widtt two-layer ReLU nets converge to max-margin classifiers in a certain non-Hilbertian function space.
7 CONCLUSION
In this work, we prove that two-layer ReLU nets trained by gradient flow on orthogonally separa- ble data converge combination of the positive and the negative max-margin classifier. To our knowledge, this is the first result characterising the inductive bias of training neural networks with ReLU nonlincarities. that does not require infinite width or huge overparameterisation.
The proof rests on a distinction between two phases of learning: an early phase, in which neurons specialise, and a late phase. which the network's 's activation pattern is fixed and hence behaves like an ensemble of linear subnetworks. This approach enables us to understand nonlinear ReLU networks in terms of the much better understood linear networks. Our hope is that a similar strategy will prove fruitful in the context of deeper networks and more complicated datasets as well.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. In International Conference on Learning Representations (ICLR), 2019.
Lénaïc Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Computational Learning Theory (COLT), 2020.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in supervised differentiable programming. In Conference Neural Information Processing Systems (NeurIPS), 2019.
Frank H Clarke. Generalized gradients and applications. Transactions of the American Mathemati- cal Society, 205:247-2622 1975.
Frank H Clarke, Yuri S Ledyaev, Ronald J Stern, and Peter R Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science Business Media, 2008.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges tame functions. Foundations of computational mathematics, 20(1):119- 154, 2020.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learing (ICML), 2018a.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient de- scent on linear convolutional networks. In Conference on Neural Information Processing Systems (NeurIPS), 2018b.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning- Springer, 2008
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations (ICLR), 2019a.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Computational Learning Theory (COLT), 2019b.
Ziwei and Matus Telgarsky. Directional convergence and alignment in deep learning. In arXiv:2006.no 2666622006.06657 2020.
Yuanzhi Li and Yingyu Liang. Learning overparameterizze neural networks via stochastic gradient descent on structured data. In Conference on Neural Information Processing Systems (NeurIPS), 2018.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations (ICLR), 2020.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly. Gradient descent quantizes ReLU network features. In arXiv: 2018.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro. and Daniel Soudry. Convergence of gradient descent on separable data. In Conference on Uncertainty in Artificial Intelligence (AISTATS), 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent separable data. Journal Machine Learning Research (JMLR), 19(1):2822-2878, 2018.
Vladimir Naumovich Vapnik. Statistical learning theory. John Wiley & Sons, 1998.
10

---

Published as a conference paper at ICLR 2021
A
BASIC LEMMAS
This section collects few lemmas useful for proofs. We assume the same setting and no- tation as Sections 2 and In addition, we denote by Pw the orthogonal projection onto span {x, w = 0} and by R Rd,
72 Σ 1(0)-1(WT> P
g(w)
(31)
A. LEMMAS ABOUT SECTORS
The following lemma gives a necessary condition for vector to an extremal direction.
Lemma A.1. If gd-1 1 is an extremal direction, then g(w) Cww for some constant C.
Proof. Let w E gd-1 be positive extremal direction (the negative case is analogous), and let w E 88. A sector is called open if * 0 for all i [n]. Denote A(²) the set of all open sectors adjacent to o
A( = O {+1)"
max lo, 8.l =1
(32)
sE(n]
Since w is local maximum of G and G is sector-wirg linear, w maximises G when constrained to (the closure of) any adjacent sector, i.e. for any a E A(o),
W arg max G(w), subject to |w| 1,
(33)
o 2 0 for all i E [n].
For w in the feasible region, G can be treated as linear function with VG(w) g(wa) where wa any vector such that W, E Sg. Hence, the necessary first-order KKT conditions for the problem
33 are
g(Wa) Cw Σ NOX,
(34)
where X 2 for all i, but X; * 0 requires that the corresponding constraint tight, T,wTx; = 0. It follows that P x,,, Multiplying eq. (34) from the left by Pw therefore yields
Cw = P g(wo) = Σ (() 1f; = P
(35)
By adjacency, o; ã; whenever ā; {+1}. they can differ only when o; 0, i.e. when
Рwx; 0. It follows that
a Cw (00) 166 1) xx g(w).
((0)
(36)
The following lemma describes the local behaviour of the function (defined in eq. 12
Lemma A.2. For E 5d-1 and v E Rdd, there exists Cmax > such that for e E [0, Cmax]
G ++
w -evl
(G(W)
Σ ((()) 1[(w + =v) > 00 vTx
n
(37)
w ev
Proof. Let g be defined as in eq.
31 then
w +
(w + +vv.
(38)
w +cvl
ww + cvll

---

Published as a conference paper at ICLR 2021
We now analyse wTg(w + ev) and ev + ev) separately, starting with the former. Denote 1 == 1[ + ev) > 0}. Then g(w + ev) can be written as
n g(w+ = Σ
n 4(0)-151 P X Σ
T1 (()- (P wwter Pw ))
Pw
(39)
Define
1 Emax = maxe, E, subject to: sign {(w -v) x; sign {wTx:} 2 Vi. 2 e>0
(40)
For [0, <max], 19 1 implies 1 1, the first term in eq. 47 equals g( (w). Regarding the
second term, [5 - 1 is nonzero only if I = 1, O. For e E [0, Emax]. this can only happen if (w + =
and wxx; O. In this scenario however, Pw P 0, so the second term
in eq. (47) is zero. Regarding the third term, as long as E [0, Emax], (w + T = 0 implies w 0, so
W E span {x5] wTx, = =0} C span {x5l (w + Tx) = 07
(41)
and (PP wtte- - Pw) = wT wt = OT, follows that
w g(w + cv) w ((w( = G(w).
(42)
Turning evTg(w ev). have that
ev g ev) = T ((0) 1((w (ww)+)))xxx) 0} P PwtcvXi,
(43)
where
ev wevy = (w + ev) Pw-ev WTP WwWtter
weve = (w + =v) -w =
(44)
Plugging eq. and eq.
443 into eq. 38 yields the result.
A.2 TRAINING DYNAMICS
In the following lemma, we prove formula for the evolution of the parameters of a two-layer network trained by gradient flow (eq. (4)). The formula has appeared in Maennel et al. (2018) before (but without a proof).
Lemma A.3. Assume that the training inputs with the zero vector {x,}, U 10) are in general po- sition") Then a two-layer ReLU network trained by gradient flow on y) satisfies for all j E [v]
and almost all 2 0,
daz
(45)
Øt
dw;
Σ ((t) [ > o0o,,
(46)
Øt
Proof. Fix 0, and denote by Eg E (-1,0, 1) the activation matrix for fe. Eoli, 2 sign wJx,. Then for any sequence 02 + 0 such that (V((0+)) exists and has a limit,
lim Eo, E {
Eolj if Eolj. 1) *
(47)
Conversely, for any Σ in the set above, there exists sequence Og - such that limg Ee. Σ. To see this, observe that each wj can be approached separately. Let A be the matrix whose rows Then by the general position of inputs, A is wide full-rank matrix and A Aw; 0. It follows that for any e, Aw has solution, which can be chosen convergent to w, as - O. "That is, no l of these points lie (k- 2) dimensioonll hyperplane, for all k: 2 2.
formed by those x, for which w w
12

---

Published as a conference paper at ICLR 2021
We deduce that
(l(((()) conv {g(²)
E i] {=1}, Σb. Eo Eo(e) [ #0,
(48)
where we define g( Σ) coordinate- as
g( [ay)
((t) wJ
(49)
g 32 [wy]
(() = ay
Since the value of (z)) [y) is independent of this proves eq. 45
The proof of eq. 46 is slightly more complicated, as we need to pin down single member of (E()())). To do that, we recall a result by Davis et al. (2020), who show that for large class of deep learning scenarios (which includes ours), the objective E admits chain rule, i.e.
00 for almost all t 0,
(t) (e))))))
(50)
0t
where the right-hand side above should be interpreted as the only element of the set (hTa0/0l l (E(O()))) For such that both eq. (4 and eq. 50) hold,
80 at
0 = -0(000))00(00))
(51)
implying that
00
Öt span (8E(0(t)) -)()())))
(52)
Suppose h1 b2 satisfy both eq. and eq. 52 (taking the role of 00/0t). Then
h h2 (t)(e(t)) (e()(t))) n nspan (ae(0(t)) al()(t)) (0).
(53)
It follows that 00 is the unique member of both span (aE(O(t)) (t)))))) and (t)()
By eqs. (48) and (49).
span (8E(0(()) - al(((()) 2 span (Sij w]x: 0},
(54)
where Eijl [ij[w,] = x; and all other elements of Eij are zero. Since
00
E span (AC(e(t)) (t()(t)) C span (Ei) wJx 0
(55)
Ōt
we obtain that for all (i,j) with w]x; 0, ,w, 1. 1,, In other words,
Ow,
Ow, Øt
P ws
E conv
Σ 1
(56)
0t
where the inclusion follows from 00/30 /t (O)(())) and eqs. 48 and 49
Now observe that by
definition, P. w, x, 0 for all (i with Ee [j, i] 0, hence the set in eq. (56 only element equals eq. (46).
is a singleton whose
The following lemma shows that balanced two-layer network remains balanced and neurons keep their signs.
Lemma A4. a two-layer neural network is balanced at initialisation and trained by gradient flow with loss whose derivative is bounded, then for t 2 0.
a1(l) sign (0) [[w]((]]]-
(57)
13

---

Published as a conference paper at ICLR 2021
Proof. By Lemma A.3
for almost all t 2 0,
a wwll
dag
Σ (() (()) > a,
(58)
ōt
Ot
L.e. aj and wj grow equally fast. Since [a,(0) ||w[())| at initialisation, |aş(t) [[)) throughout training.
Next denote by B, V 0 some scalars such that (e) s for all i [n] and u R. and ||x||| S V for all [n]. Then |0a]/Ot] S nBa3V. equivalently aloga S nBV. It and hence 0g cannot
follows that (1) lies between (²( exp(pp exp((nBVV) and
cross zero in finite time, proving eq. 57
B PROOFS OF MAIN RESULTS
Lemma 2. In the setting of Theorem one negative extremal direction. The positive extremal sector o is given by
! there is exactly one positive extremal direction and exactly
1, y 1.
o
- 1, if y₁
and x x],x; x; < for some i with yi = 1, ! - and x x; = 0 for all with yi = 1,
(13)
0,
and the negative extremal sector o given by
1,
if y -1
if 1/j and x x; for some with yi 11,
(14)
0, if y) 1 and x x, for all with yt -11
Proof. We will prove the positive case; the negative G is a continuous function on a compact domain, it has a maximum. At least one maximum must moreover be strict, or otherwise G would have be constant. This shows that positive extremal direction exists; we now show there is no more than one such direction.
follows by inverting all labels. Because
extremal direction per sector; it therefore suffices to show that no sector except one, ot admits a positive extremal direction. We will show that if w Sd-1 lies any sector other than at, then w is not positive extremal; particular we show that G(w) can be locally increased.
By Lemma A. there cannot be more than
Let * a and let w 8 ngd-1. By Lemma A.2 for any v E Fd there exists Cmax
such
that for E (0, Emax),
G + cv )
G(w) ca 1 evil
(59)
+ ev|l
where
n
Σ ((0)][(W <(w Tx) 0lvix,
(60)
We analyse the different possible realisations of or, and for each find E Rd such that (G(w) + ea)/l w + ev|l > G(w) for small e.
Suppose first that oj -1 for some example with y, or that o, for some example with y/ -1. Then set := y, ||x ||. By orthogonal separability, we have that > 0. Also, à sign wTx, V; implies TTv < 0. therefore ||w - ev|l < ||w|| for small enough. It
o,
follows that (G(w) ca)/ll |v|| > G(w).
Next suppose that σ; 0 for some example with y, 1, and set x,/||x Then 0, because each term in eq. (60) is non-negative by orthogonal separability, and the term corresponding
to i = j is strictly positive:
-0) 1 ((w =ev) 0) vTxx - [e][x;]] 0|||>|| 0.
(61)
14

---

Published as a conference paper at ICLR 2021
v1+ Hence, (G(w) + ea.//lw + +vil = (G( + e1) +(()), which strictly exceeds ((w) for e small enough.
From oj _ sign wTx, = 0 it further follows that 1|w - evll
We have thus shown that if is positive extremal, then necessarily 0; for all examples with y: I, and Ø; E {0, 1 for examples with with Mjj = -1 that satisfies x]x, < 0 for some k with 3/k. = 1. Taking v := -x;/||x,) will make a strictly positive, as the term corresponding to term's s indicator equals 1, as we know from the above that o 1). Like in the previous paragraph, ||w + ev || = + O(e²), which suffices to show G(w) locally submaximal.
-1 Suppose now that a; = 0 for an example
in eq. (60) will be strictly positive (this
Finally, let x be such that yj -1 1 and x x,x; = 0 for all with yi 1, and suppose that oj -1 With =- x |P wxyll (we know that P x of 0 because w j 0 by o; 1), we have
a
PP PW
()) 1[(w + +x)x > 07 x P x,
(62)
We claim that each term in eq. 62 is zero: For terms with 0; -1 the indicator [(( + 'x > 0} is zero. For terms with o; 0, x, 0. (Also notice that such terms necessarily satisfy yi - and x,xx = 0 for all k with yı- 1, which we will need shortly.)
Lastly, for terms with a; = 1, we know y/ = 1, and hence x X1 = for all with 0 0. other words, x; 1 span {xx] w = 0}. implying Pw
x,. In the context of eq. 662 w || = 1 for
obtain
P.P: = xJx, = 0, concluding the proof that a = 0. Since o, = -, || + evil
small enough c, and (G(w) + /ll + cvll > G(w). We have thus ruled out all sectors except proving that for orthogonally separable datasets there is unique positive extremal sector. 0
Lemma 3. Assume the setting of Theorem 7 at time T the neuron (aj, W5) satisfiex aj (T) > 0
and w (T) E Sa where a is the positive extremal sector (eq. (13), then for 2 T, (( E 8 The same holds if (T) < 0 and a is the negative extremal sector (eg. (14)).
Proof. We omit the neuron index, and only prove the positive case; the negative case is analogous. Denote o (1) = sign XTw(()) We proceed by contradiction. Suppose there exists a time Ti > T such that (Ti) * (T).. Wlog, take Ti such that (1) is constant on (T,Ti) and denote this constant sector σ;; by continuity 0 = (T) if (T) o O.
Now consider d (7) = 0. By the gradient flow differential inclusion, for almost all t E (T,Ti),
Ow Xx Ot
E conv
((t) 10) ax]x
(63)
o'
where each o' in the definition of the convex hull satisfies of = (T) of) o 0, implying
{ilo] = C = -il = c (i)
=1 (1) (T) 0}
(64)
(il = and x]x, = 0 for all with yj = 1].
Denote the two sets in the last expression I+ and Jo, and consider the gradient corresponding to some o' in eq. (63). The gradient terms corresponding to i E I+ are zero (because & E Jo and so xTx; = 0) and the terms corresponding to i E 30 (if there are any) are negative. The total gradient for o' is therefore non-positive, which is preserved under taking convex hulls, and so we obtain d wTx, < 0. It follows that o + 1.
de
By Lemma
A.3 for almost all E (T, Ti) and any h E [n].
dw Xx
Σ
(65)
Ø1
==1
where 11 16; = =1} 11:- = 1} as we have shown above. Observe that for x; with yi 1, we have
Pwx; = X;, This is because Pw projects onto
span {x4 o, 03 2 span (x. (T, 0}
(66)
and x; lies in the right-hand side by the definition of positive extremal sector (eq. 13 Therefore
Tw 1()) = 1) ax]xx
(67)
Øt
15

---

Published as a conference paper at ICLR 2021
One can easily check that if (T) then wxx 0, (T) = -1 then x 0, and o (2") then & w X 0. follows that o oTi) (T)), which is contradiction.
Bt
Lemma B.1. Assume the setting of Theorem 7 If at time the neuron (aj, w;) satisfies o, (T) and w, Txx >> for some k E [n]] with yı 1, then for 2 T. w, [t) 0. The same holds if instead 0gy (T) < 0 and yl -1
Proof. We omit the neuron index, and only prove the positive case: the negative case is analogous. We will show that for almost all & E (I, Nwwxx//e 2 O. By the gradient flow differential inclusion, for almost all E (T))
TwTx Xx
E conv
Σ 20 xx
(68)
Ø1.
Fix any o' and consider the summand corresponding example i. y/ then -((() > 0 and
x!xx > 0, so the summand is non-negative. If 1, then - (t) < 0 and x, x,xx S 0, so the
summand is again non-negative. It follows that the sum non-negative irrespective a'. hence ÖwTx;/08 2 0.
Corollary 1. Under the conditions of Theorem 7 there exist constants 0 such that
[e |0(())12
+ up(w]xx =p(wIx).
as + oc.
(10)
Proof. By Lemma A.4 |0| = =|aal? WI = = Then for any x E Rd.
(x)
a(l)T W())
(69)
[[(()]]? [a(()]] [W
Denote ä = 00 a (t)]l- Then by Theorem | as 0o.
2 (x)
ā p(ww[[[wxx zw!x)
(70)
[[(())]?
=ā p(uw äT p(pww
(71)
=āTup(w x) + āTz p(wpp(ww]
(72)
where eq. (11 we used the fact that for all E [p]. either u; = or 2, 0, and in eq.
(22 we
used u, 2 0. Finally, since á = ul/w z||w |. we have
aTu u = | ju 2 0, ā
(73)
|| | Tz S O,
(74)
which completes the proof.
C RELATIONSHIP TO NONLINEAR MAX-MARGIN
Lemma C.1. Let (X an orthogonally separable dataset, let W W be defined as in eqs. (6) and (7) and let
= uw. + Iw.,
(75)
= w || -|
(76)
for some u1 z E TRP such that u; = or 2, = for all i E [p]. Also let u, z be normalised such
that ||u|| = ||w -1/2 and ||z|| = /ww -1/2 1/2 Then á A [W, a) is a KKT point of the following constrained optimisation problem:
min 2 S.I.
10112
f 21,
i E [n].
(77)
16

---

Published as a conference paper at ICLR 2021
Proof. By standard linear max- max-margin considerations (e.g. Hastie et al. (2008 Section 4.5.2)),
know that
W+
Σ
w a; C:g
(78)
for some 0; 2 0 such that o; = 0 x, is non-support vector. It follows by orthogonal separability that for with y 1,
wI,; 0,
V. S0.
(79)
and for i with yi 1,
w!Xx, 50
y.w.x, > 0:
(80)
we will need these properties shortly.
Let us now turn to checking the KKT status of 0 wrt eq. (7 We start by showing that @ is feasible.
Let x; be such that y/1 1; then
(xf((xx)) p(W))
(81)
p(uw I X; + 2w]x,)
(82)
auuwIx
(83)
=l|w+|llux [ -w]x 1,
(84)
(85)
where the last inequality follows from the definition of W+, eq. 6 Similarly, if x, is such that Y/ 1, then
yifo(x;) =-āzz w X;
(86)
= [ww-Il/||/w'1 = -w_x 2
(87)
(88)
This shows that is feasible.
Next, we show that θ is KKT point, i.e. we show that there exist At...., An 2 such that
1. for all E [n]], (x: 1) = 0, and
2. θ E Ei (x
where fofa (x) denotes the Clarke subdifferential of fo (x) wrt. 0, evaluated at Ó. Specifically, we show that the choice
Oss w
if y/
A
(89)
as [-
if
1,
satisfies both conditions above.
As for the first condition, observe that if non-support example, then ); 0A and the condition holds. If i is a support example, then by eqs. (85) and (88), fx,)) = 1 and the condition holds well.
As for the second condition, denote
gi (
[o(x:)ax]; p(Wx))),
(90)
17

---

Published as a conference paper at ICLR 2021
where [x) diag [1(
OH] Rex is the diagonal matrix whose (i, element is one if
w.x x 0 and zero otherwise. holds that gi go()) (x;) and
Ayggi 0
Σ
diag
[1 > 04l ax! pluwIxx zw[x;)]
w
k.y.
Σ
O2
diag
> 0}] āx
p(uw 2w 2w]x
w
k:gss
[||+ TxT: uwIx.]
Oi
[- || | zw x,]
[w+]
w
1
|| [uw uwI
w- ||aw Zw w-]
||+]
w
[uw] Iw ul|w+|l z||w-]]]
0.
This proves the second condition, and shows that is KKT point eq.
77
D EXPERIMENTS ON REAL DATA
In this section we explore the applicability of our result to real-world datasets and architectures (which lie outside the scope formally covered by our assumptions). We experiment on the MNIST dataset subsetted to two classes, the digit 0 and the digit
We train network consisting of six convolutional layers followed by two fully-connected layers. We view the six convolutional layers as 'feature extractor' and the two fully-connected layers as a two-layer fully-commected network of the kind we analyse this paper. The details of the architecture are given in Table We train the network by Adam with the binary cross-entropy loss and a batch size of 128. We train for 50 epochs. Prior to training, we multiply the weights of the fully-connected layers by 0.05, approximate the small-norm initialisation assumed by theory.
Layer
Type
1
conv (32, 3, 1,
1)
2
conv (32, 3, 1,
1)
3
conv (32, 5, 2,
2)
4
conv (64, 3, 1,
1)
5
conv (64, 3, 1,
1)
6
conv (64, 5, 2,
2)
7
fc (3136, 128)
8
fc (128, 1)
Table I: Architecture of the studied network. By conv (n, k, s, p) we denote convolutional layer with n kernels of size with stride s, where the input to the layer is padded by p rows or columns on each margin. By Ec (n, о) we denote a fully-connected layer whose input dimension and whose output dimension is
We conduct two sub-studies. First, we demonstrate that the network learns orthogonally separable representations all by itself, in the course of training. This is shown in Figure 3 The first subplot shows three distributions: The blue distribution is the distribution of x!x, where x; sampled from class and x, is sampled from class 1. The orange (or green) distribution is the distribution of x x, where both x,, X; are sampled from class C (or class 1). The other subplots show analogous inner-product distributions for the intermediate representations learned features of the data, i.e. (x.)) T f (x,) instead of x]xx.
What is that the network learns representations such that examples of the same class more similar to each other than examples of different classes - the orange and green distributions are generally more the right compared the blue distribution. Moreover, higher-layer representations
18

---

Published as a conference paper at ICLR 2021
Origiial data
1st layer features
2nd layer festures
3rd Jayer features
0.1
0-1
0.0
0.0
0-0
0.0
1-1
1-1
1-1
1-1
400
600
900
4000
60000
2000
4000
5000
10000
4th layer features
5th layer Seatures
6th layer features
7th layer features
0-1
3-1
0-0
0-0
0-0
0-0
1-1
1-1
1-1
1-1
10000 20000
30000
50000
100000
200000 400000
1000000
Figure 3: Distributions of feature similarity, where examples are sampled from the specified classes. Specifically. The I-th subplot shows the distribution of fg T for Xy sampled from dif- ferent classes (blue) or both from class 0 (orange) or both from class (green).
are generally more strongly separated as we move up the layer hierarchy, the orange and green distributions keep shifting rightward, whereas the blue distribution shifts leftward. Remarkably, the 7th layer representations are orthogonally separable.
In the second sub-study, we explore properties of the weight matrix learnt by the first linear layer of the network, in analogy to the first-layer weight matrix two-layer net. Figure 4p shows the top ten singular values of the weight matrix W, 1228x3166 We that despite its size, it has very few (perhaps five or ten) significantly non-zero singular values. This is similar to what we observed for synthetic data in Section 5 though the separation between small and large singular values is less crisp and there are more than two non-zero values. Figure 44 shows the rows (neurons) of W7 projected onto the top singular dimensions (note that unlike in Section [5] the projection is lossy). The neurons roughly form three clusters: mixed cluster close to the origin and two clusters corresponding to positive and negative outer-layer weights. Compared to our observations from Section 5 there is less variation in the neurons' norms, leading to them forming clusters rather than rays. This deviation from the theoretical prediction could be due number reasons, e.g. the use of biases, convolutional layers, or the large dimensionality of the layer. We leave detailed investigation of this question future work.
a) Top 10 sing values W
b) Projected neurons
0.5
7.5
5.0
0.0
2.5
0.0
Figure 4: a) The 10 largest singular values of the first linear layer's weight matrix W, after training. Each dot represents one singular value. b) Neurons (rows of W>) projected on the top two singular dimensions. Orange (or blue) dots represent neurons with W Wil > (or Ws[i] < 0).
19


Reviews:
[{"review_id": "tzzK496sMzr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the inductive bias of gradient flow for two-layer ReLU networks for classification problems. Under an orthogonally separable data assumption, it is shown that each node of the ReLU network will converge to one of two directions that linearly separate the data. I think the inductive bias of neural network training is a very important research problem and the result of this paper looks interesting. However, I also have the following concerns about this paper. \n\nPerhaps the most obvious limitation of this paper is that the orthogonally separable data assumption is too strong. Under this assumption, the classification problem can be solved trivially: one can simply randomly pick a training example and use it as the parameters in a linear predictor. It seems to be highly unlikely that this assumption can be satisfied by any challenging real-world problems.\n\nMoreover, the current submission lacks discussion and explanation of their results:\n\n(a) The result of this paper seems to be weaker than the result in Lyu & Li (2020), while also requiring much stronger assumptions than Lyu & Li (2020).  Note that the inductive bias given in Lyu & Li (2020) is in the form of a maximum margin KKT point of the ReLU network (as a *nonlinear* classifier), however, the result in this paper is more related to the maximum margin solution of linear models, which in general may be much worse than the margin achievable by wide neural networks. Therefore I guess the most straightforward question the authors should clarify is whether under their setting w^+ and w^- indeed gives a KKT point of the *nonlinear* maximum margin problem given by Lyu & Li (2020).\n\n(b) To my knowledge most of the inductive bias results for classification problems (cross-entropy/exponential loss) do not rely on specific initialization methods (except certain assumptions to guarantee achieving zero training error) (Soudry et al. (2018), Ji & Telgarsky (2019b), Lyu & Li (2020)). Therefore the authors may consider providing more explanation on why they require the specific initialization.\n\n(c) In Section 6 it is mentioned that Li & Liang (2018) contain the training in the neighborhood of the (relatively large) initialization. While this is to some extent true, I find this comment not very convincing. When studying inductive bias, it is natural to restrict the training to a fixed training dataset, i.e. to treat the online SGD in Li & Liang (2018) as finite sum SGD by considering a uniform data distribution over training samples. In this case, since Li & Liang (2018) considers classification with cross-entropy loss, the weights will eventually go to infinity and therefore will not stay in the neighborhood of initialization forever, as is shown in Lyu & Li (2020). This is also true for other classification results in the lazy training setting including [1,2,3,4]. It seems that a combination of these results mentioned above and the result by Lyu & Li (2020), which has been discussed in Ji & Telgarsky, 2020 and [5], can already imply a much stronger result compared to this paper. \n\n\n\n\n[1] Zou, Difan, Yuan Cao, Dongruo Zhou, and Quanquan Gu. \"Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks.\" arXiv preprint arXiv:1811.08888 (2018).\n\n[2] Nitanda, Atsushi, Geoffrey Chinot, and Taiji Suzuki. \"Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems.\" arXiv preprint arXiv:1905.09870 (2019).\n\n[3] Cao, Yuan, and Quanquan Gu. \"Generalization bounds of stochastic gradient descent for wide and deep neural networks.\" NeurIPS 2019.\n\n[4] Ji, Ziwei, and Matus Telgarsky. \"Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.\" ICLR 2020.\n\n[5] Moroshko, Edward, Suriya Gunasekar, Blake Woodworth, Jason D. Lee, Nathan Srebro, and Daniel Soudry. \"Implicit bias in deep linear classification: Initialization scale vs training accuracy.\" arXiv preprint arXiv:2007.06738 (2020).\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Zgc4Qsv7xng", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "(a) This belongs to the literature of implicit bias/inductive bias, which has\ngained a great deal of attention among theoretical enthusiasts with an\noptimization leaning.\n\n(b) The paper is carefully laid out and argued, and is at a nice level\nof clarity and precision.\n\n(c) The mathematical argumentation seems to me correct; \nhowever I haven't checked line-by-line.\n\n(d) The situation being studied is very very special\nand doesn't much correspond to the big kahuna\ndeep learning. Nevertheless the intellectual clarity\nof this special case is quite appealing.\n\n(e) The implied conclusion seems rather special\nas well. From one viewpoint it says that if you start \nfrom the get-go with perfect \nseparation of a particular strong form,\nthen the future evolution of the training \ncan never spoil things. This is a very weak statement,\nbut I suppose if we can't get results here in a very special case\nthat we can understand well, then the \ngeneral situation is truly hopeless.\n\nSpecific Comments.\n\n(1) Why is this max-margin if your constraints only consider one class. It seems to be more of a finding a minimum-norm vector aligned with all training data of that class. Its unclear why the concept of separating margins comes in.\n\n(2) “Theory III: Dynamics and Generalization in Deep Networks” by Banburski et al. also considers general deep relu networks and shows that the resulting margins are max-margin—requiring only separability, not orthogonal separability. In addition, that paper uses traditional DE methods rather than relying on lesser-known extremal sector techniques. Can you discuss or highlight why the simpler example in this paper might lead to insights not found in the other paper.\n\n(3) While the paper says that it is not directly applicable to deep nets, it draws motivation from the popularity of that literature. In that spirit, to justify such an evocation, can you show at least one experiment on a non-synthetic dataset such as MNIST/CIFAR/etc (perhaps even simplified with hand-engineered preprocessed features and subsetted to two-classes) that would support the potential connection to deep learning?\n\n(4) Can you provide any evidence why datasets would become orthogonally separated? Is there some feature\nengineering procedure that tends to produce orthogonal separation?\n\n(5) In Figure 1, variance is strange: shows one big outlier, but the plotted projection shows two roughly-equal-magitude directions of variation.\n\n(6) It is unclear how Definition 2 relates to strict extremal directions as defined by the sign patterns.\n\n(7) G should be clarified: What G is and what it represents should be explained to make the results more insightful\n\n\n\n 16m 50s\n\nType a message\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Cqf3_ffvFnS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the inductive bias of two-layer ReLU networks trained by gradient flow. The main challenge is to analyze the global convergence of the flow dynamics. Under a special assumption that the data are orthogonally separable, the paper shows that the dynamics converges to a unique max-margin solution. I find that the paper is well written, modulo some assumptions on the data that would be better to be made more rigorous. The overall quality is good. The novelty compared to the literature is that this paper provides a global analysis of the non-linear non-smooth dynamics without going into the over-parameterized regime. \n\nIn Theorem 1 of the paper, what does it mean « For almost all such datasets? » What is the probability distribution of (X,y)? Is there any more precision condition on \\lambda, which controls the norm of the initial weights? \n\nIn Lemma A.3, what does it mean « genetic position »? I think what is needed is to assume that the probability that all the x_i lie on some hyperplane is close to zero. This assumption is crucial for (43) to hold, therefore I think it should be made more precise. Or to put in a less probabilistic, one may assume that the maximal number of samples {x_i} that lie on some hyperplane is smaller than the dimension of x_i.\n\nFor clarity, is the experiment in 5.2 uses the same data (X,y) as in 5.1? \n\nSome typos or confusions of notations are listed below:\n- \\ell^+(t) right before (18), is confusing, as \\ell^+ is a function of \\theta, I would suggest to use L^+(t)  = \\ell^+(\\theta(t)) \n- Change W+(t) -> W_(t) to (24)\n- \\ell’_i(t) in (40) and (41) are also confusing, write L_i’(t) = \\ell_i’(\\theta(t)) ? \n- Change \\Sigma[i,j] -> \\Sigma[j,i] in (42), (43), etc. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BKzK5qYrGPz", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper characterizes the implicit bias of gradient flow of two-layer ReLU networks on orthogonally separable data trained on the logistic loss. The problem of characterizing the implicit bias of gradient descent on neural networks is an important one, and while the authors do make fairly strong assumptions on the data (data corresponding to the different labels lie in separate orthants), the proof is novel, interesting and non-trivial. The proofs are carefully carried out and seemed as far as I could verify.\n\n\nA few questions:\n1. Is it possible to characterize what the outer weights (a's) converge to? If yes, I would suggest that the authors include this either in the main theorem, or as a comment after the theorem.\n2. Does a similar result hold if the network also has bias variables? \n3. Can linearly separable data be made into orthogonally separable data (by appropriate pre-processing) and by also training a bias term?\n4. How are the lambda_j's chosen in the near zero initialization? The current description of choosing lambda_j on page 2 is quite vague.\n5. I would also urge the authors to add the additional assumption about the positive and negative examples spanning the entire space in Section 2 along with the other assumptions. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that under a very restrictive assumption on the data, ReLU networks with one hidden layer and zero bias trained by gradient flow converge two a meaningful predictor provided that the network weights are randomly initialized with sufficiently small variances. While there is some overlap with a paper by Lyu & Li (2020), the paper under review establishes its results for networks with arbitrary widths whereas using the results of Lyu & Li (2020) works, at least so far, only for sufficiently wide networks. The assumption on the data is anything than realistic and actually any "simple, conventional" learning algorithm can easily learn in this regime. Nonetheless, getting meaningful results for neural networks is still a notoriously difficult task and for this reason, the paper deserves publication.   
Decision: Accept (Poster)