Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
Authors: Kaifeng Lyu
Jian Li
Venue:  (2020)
Keywords: margin
homogeneous
gradient descent

Abstract: In this paper, we study the implicit regularization of the gradient descent algorithm in homogeneous neural networks, including fully-connected and convolutional neural networks with ReLU or LeakyReLU activations. In particular, we study the gradient descent or gradient flow (i.e., gradient descent with infinitesimal step size) optimizing the logistic loss or cross-entropy loss of any homogeneous model (possibly non-smooth), and show that if the training loss decreases below a certain threshold, then we can define a smoothed version of the normalized margin which increases over time. We also formulate a natural constrained optimization problem related to margin maximization, and prove that both the normalized margin and its smoothed version converge to the objective value at a KKT point of the optimization problem. Our results generalize the previous results for logistic regression with one-layer or multi-layer linear networks, and provide more quantitative convergence results with weaker assumptions than previous results for homogeneous smooth neural networks. We conduct several experiments to justify our theoretical finding on MNIST and CIFAR-10 datasets. Finally, as margin is closely related to robustness, we discuss potential benefits of training longer for improving the robustness of the model.

Published as a conference paper at ICLR 2020
GRADIENT DESCENT MAXIMIZES THE MARGIN OF HOMOGENEOUS NEURAL NETWORKS
Kaifeng Lyu & Jian Li Institute for Interdisciplinary Information Sciences Tsinghua University Beijing, China vf vfleaking@gmail com, liji 8 30ma wtw.ll..ssingauaecce. en
ABSTRACT
In this paper, we study the implicit regularization of the gradient descent algorithm homogeneous neural networks, including fully-connected and convolutional neural networks with ReLU LeakyReLU activations. In particular, study the gradient descent or gradient flow (i.c., gradient descent with infinitesimal step size) optimizing the logistic loss cross-entropy loss of any homogencous model (possibly non-smooth), and show that if the training loss decreases below a certain threshold, then increases over time. We also formulate a natural constrained optimization problem related to margin maximization, and prove that both the normalized margin and its smoothed version converge to the objective value at a KKT point of the optimiza- tion problem. Our results generalize the previous results for logistic regression with one-layer or multi-layer linear networks, and provide more quantitative con- vergence results with weaker assumptions than previous results for homogeneous smooth neural networks. We conduct several experiments to justify our theoretical finding on MNIST and CIFAR-10 datasets. Finally, as margin is closely related to robustness, we discuss potential benefits of training longer for improving the robustness of the model.
define smoothed version of the normalized margin which
INTRODUCTION
major open question deep learning is why gradient descent or its variants, are biased towards solutions with good generalization performance on the test set. To achieve better understanding, previous works have studied the implicit bias of gradient descent in different settings. One simple but insightful setting is linear logistic regression on linearly separable data. In this setting, the model is parameterized by weight vector w, and the class prediction for any data point æ is determined by the sign of w² Soudry et al. 201 Sa b); Ji & Telgarsky (2018) 9c); Nacson et al. (2019c) investigated this prob- lem and proved that the direction of converges the direction that maximizes the T.2-margin while the norm of w diverges to +00, we train uo with (stochastic) gradient descent on logistic loss. Interestingly, this convergent direction is the same as that of any regularization path: any se- quence of weight vectors {w,} such that every W. is a global minimum of the L'-regularized loss [(w) + 2t || with A + 0 (Rosset et al. 2004). Indeed, the trajectory of gradient descent is also pointwise close regularization path (Suggala et al. 2018).
Therefore, only the direction w/ // [|2 is important for making prediction.
The aforementioned linear logistic regression can be viewed as a single-layer neural network. A nat- ural and important question is to what extent gradient descent has similiar implicit bias for modern deep neural networks. For theoretical analysis, a natural candidate is to consider homogeneous neu- ral networks. Here a neural network & is said to be (positively) homogeneous if there is a number L >> 0 (called the order) such that the network output (00; x)) where 0 stands for the parameter and æ stands for the input, satisfies the following:
Ve > 0: (cc0; x) = c (0; .:) for all f and æc
important to note that many neural networks are homogeneous (Neyshabur et al. 2015a Du al. 2018). For example, deep fully-connected neural networks deep CNNs with ReL. or

---

Published as a conference paper at ICLR 2020
LeakyReLU activations can be made homogeneous if we remove all the bias terms, and the order L is exactly equal to the number of layers.
In (Wei al. 2019), it is shown that the regularization path does converge to the max-margin di- rection for homogeneous neural networks with cross-entropy or logistic loss. This result suggests that gradient descent gradient flow may also converges the max-margin direction by assuming homogeneity, and this is indeed true for some sub-classes of homogeneous neural networks. For gra- dient flow, this convergent direction is proven for linear fully-connected networks (Ji & Telgarsky, 2019a). For gradient descent on linear fully-connected and convolutional networks, (Gunasekar al., 2018b) formulate a constrained optimization problem related to margin maximization and prove that gradient descent converges to the direction of KKT point or even the max- max-margin di- rection, under various assumptions including the convergence of loss and gradient directions. In an independent work, (Nacson et al. (019a) generalize the result in (Gunasekar et al. 2018b) to smooth homogeneous models (we will discuss this work in more details in Section 2).
1.1 MAIN RESULTS
In this paper, we identify a minimal set of assumptions for proving our theoretical results for ho- mogeneous neural networks on classification tasks. Besides homogeneity, we make two additional assumptions:
1. Exponential-type Loss Function. We require the loss function to have certain exponential tail (see Appendix for the details). This assumption is not restrictive it includes the most popular classfication losses: exponential loss, logistic loss and cross-entropy loss.
2. Separability. The neural network can separate the training data during training (i.e., the neural network can achieve 100% training accuracy
While the first assumption is natural, the second requires some explanation. In fact, we assume that at some time to. the training loss is smaller than a threshold, and the threshold here is chosen be so small that the training accuracy is guaranteed cross-entropy loss, the threshold can be set to In 2). Empirically, state-of-the-art CNNs for image classification can even fit randomly labeled data easily (Zhang et al. (017). Recent theoretical work on over over-varamens wver-prameterized neural networks (Allen-Zhu et 2019 et al. 2018) show that gradient descent can fit the training data the width is large enough. Furthermore, in order to study the margin, ensuring the training data can be separated is inevitable; otherwise, there is no positive margin between the data and decision boundary.
be 100% (e.g.. for the logistic loss and
Our Contribution. Similar to linear models, for homogeneous models, only the direction of parameter 0 is important for making predictions, and one can see that the margin (00) scales linearly with ||@l| when fixing the direction of 0. To compare margins among 0 in different directions, it makes sense to study the normalized margin, (0) = (0)
In this paper, we focus the training dynamics of the network after to (recall that to is time that the training loss is less than the threshold). Our theoretical results can answer the following questions regarding the normalized margin.
First, how does the normalized margin change during training? The answer may seem complicated since
easily come up with examples in which increases decreases in a short time interval. However, we can show that the overall trend of the normalized margin is to increase in the following sense: there exists a smoothed version of the normalized margin, denoted as 5. such that (1) - 51 + 0 as t + oc; and (2) Fy is non-decreasing for t >>>> to
Second, how large is the normalized margin at convergence? ? To answer this question, we formulate a natural constrained optimization problem which aims to directly maximize the margin. We show that every limit point of (0(t)/ (t)]l, :t > 0} along the direction of a KKT point of the max- margin problem. This indicates that gradient descent/gradieet flow performs margin maximization implicitly in deep homogeneous networks. This result can be seen as a significant generalization of previous works (Soudry et al. 2018a b) & Telgarsky 2019a Gunasekar et al. 2018b) from linear classifiers to homogeneous classifiers.
Note that this does NOT mean the training loss is
2

---

Published as a conference paper at ICLR 2020
romaited margin
1.50 2014
Tomsittesmarpi margin
10
1.00 10
1.20x 30
00
20
0.00 10
10
1.20x1007
+0 50 K00
30
x0.0xx00-
10"
10
Pepochs 13600
0cpochs
sopochs
@spachs
(a)
(b)
Figure 1: (a) Training CNNs with and without bias on MNIST, using SGD with learning rate 0.01. The training loss (left) decreases over time, and the normalized margin (right) keeps increasing after the model fitted, but the growth rate is slow (= 1.8 x 10-4 after 10000 epochs). (b) Training CNNs with and without bias on MNIST, using SGD with the loss-based learning rate scheduler. The training loss (left) decreases exponentially over time (< 10-800 after 9000 epochs), and the normal- ized margin (right) increases rapidly after the model is fitted (= 1.2 x 10-3 after 10000 epochs, 10x larger than that of SGD with learning rate 0.01). Experimental details are in Appendix K
As by-products of the above results, we derive tight asymptotic convergence/growthh rates of the loss and weights. is shown in (Soudry et al. 2018a] b Ji & Telgarsky 2018 2019c) that the loss de- creases at the rate of (1/()), the weight norm grows as O(log L) for linear logistic regression. In this work, we generalize the result by showing that the loss decreases at the rate of (11 (1(log/)2-22/1) ()2-2/1)) and the weight norm grows as O(log t) ) for homogeneous neural networks with exponential loss, logistic loss, or cross-entropy loss.
The main practical implication of our theoretical result is that training longer can enlarge the normalized margin. To justify this claim empiricaly, we train CNNs on MNIST and CIFAR-10 with SGD (see Section K.I. Results on MNIST are presented in Figure I For constant step size, we can see that the normalized margin keeps increasing, but the growth rate is rather slow (because the gradient gets smaller and smaller). Inspired by our convergence results for gradient descent, we use a learning rate scheduling method which enlarges the learning rate according to the current training loss, then the training loss decreases exponentially faster and the normalized margin increases significantly faster as well.
Experiments
For feedforward neural networks with ReLU activation, the normalized margin on a training sample is closely related to the L L'-robustness (the L'-distance from the training sample to the decision boundary). Indeed, the former divided by Lipschitz constant is a lower bound for the latter. For example, the normalized margin is a lower bound for the - 222robustness on fully-connected networks with ReLU activation (see, e.g., Theorem 4 (Sokolic et al., 2017)). This fact suggests that training longer may have potential benefits on improving the robustness of the model. In our experiments, we observe noticeable improvements of Lla-robustness on both training and test sets (see Section K.2p.
2 RELATED WORK
Implicit Bias in Training Linear Classifiers. For linear logistic regression on linearly separable (Sudry et al. (2018a b) showed that full-batch gradient descent converges in the direction of the max m.a-margin solution of the corresponding hard-margin Support Vector Machine (SVM). Subse- quent works extended this result in several ways: Nacson al. (2019c) extended the results to the case of stochastic gradient descent:/Gnnasehe Gunasekar et al. (201 8a) considered other optimization methods; Nacson et al. (2019b) considered other loss functions including those with poly-exponential tails; Ji & Telgarsky (2018; 2019c) characterized the convergence of weight direction without assuming separability;; Ji Telgarsky (2019b) proved a tighter convergence rate for the weight direction.
Those results on linear logistic regression have been generalized to deep linear networks, Ji & Tel- garsky (2019) showed that the product of weights in deep linear network with strictly decreasing loss converges in the direction of the max 1,2 margin solution. Gunasekar et al. (2018b) showed
"Code available: httpps://githubbccm//fffll/
3

---

Published as a conference paper at ICLR 2020
more general results for gradient descent on linear fully-connected and convolutional networks with exponential loss, under various assumptions on the convergence of the loss and gradient direction.
Margin maximization phenomenon is also studied for boosting methods (Schapire et al. 1998 Schapire & Freund 2012, Shalev-Shwartz & Singer 2010 Telgarsky 2013) and Normalized Per-
ceptron (Ramdas & Pena 2016).
Implicit Bias in Training Nonlinear Classifiers. Soudry et al. (2018a) analyzed the case where there is only trainable layer of a ReLU network. Xu et al. (201 8) characterized the implicit bias for the model consisting of one single ReLU unit. Our work is closely related to a recent independent work by (Nacson al. 2019a) which discuss in details below.
Comparison with (Nasson et al. 2019a). Very recently, (Nacson et al.) 2019a) analyzed gradient descent for smooth homogeneous models and proved the convergence parameter direction KKT point of the aforementioned max- max-margin problem. Compared with their work, our work adopt much weaker assumptions: (1) They assume the training loss converges to 0, but in our work we only require that the training loss is lower than a small threshold value at some time to (and we prove the exact convergence rate of the loss after lo): (2) They assume the convergence of parameter directior while we prove that KKT conditions hold for all limit points of (0())/])((())))
0), without requiring any convergence assumption; (3) They assume the convergence of the direction of losses (the direction of the vector whose entries are loss values every data point) and Linear Independence Constraint Qualification (LICQ) for the max-margin problem, while we do not need such assumptions. Besides the above differences in assumptions, also prove the monotonicity of the normalized margin and provide tight convergence rate for training loss. We believe both results interesting in their own right.
Another technical difference is that their work analyzes discrete gradient descent on smooth homo- geneous models (which fails capture ReLU networks). In work, we analyze both gradient descent on smooth homogeneous models and also gradient flow on homogencous models which could be non-smooth.
Other Works on Implicit Bias. Banburski et al. (2019) also studied the dynamics of gradient flow and among other things, provided mathematical insights to the implicit bias towards max margin solution for homogeneous networks. We note that their analysis of gradient flow decomposes the dynamics to the tangent component and radial component, which is similar our proof of Theo- : linear least-square problem gradient-
rem 4.1 in spirit. Wilson et al. (2177;; Ali et al. (2019); Gunasekar et al. (2018a) showed that for the methods converge to the unique global minimum that closest to the initialization in L distance. [u et al. (2019); Jacot et al. (2018); Lee et al. (2019); Arora et al. (2019b) showed that over- wee-parraeteriized neural networks of sufficient width (or infinite linear models with Neural Tangent Kernel (NTK) with proper initialization and gradient descent converges linearly to a global minimum near the initial point. Other related works
width) behave
include (Ma et al. [2099] Gidel et al. 2019 Arora et al. 2019a Suggala et al. 2018 Blane al.
2019
Neyshabur et al. 2015b a).
3 PRELIMINARIES
Basic Notations. For any N E N, let [V] = (1,...,N N). ||lla denotes the - -orm of a vector v. The default base of log is e. For function f: Rdd + IR ff(x) stands for the gradient at if it exists. A function f: X -> IRd C*-smooth if f is times continuously differentiable. A function f: X + R is locally Lipschitz if for every X there exists neighborhood U of x such that the restriction of f on U is Lipschitz continuous.
Non-smooth Analysis. For a locally Lipschitz function ʃ X R, the Clarke's subdifferential (Clarke 1975 Clarke et al. 2008 Davis et al. 2020) at x E X is the convex set
8 fx)()) = conv
lim (((x)) a - x. f is differentiable at 2c k-+00
Assuming the convergence of the parameter direction may seem quite reasonable, however, the problem here can be quite subtle in theory. In Appendix [ we present smooth homogeneuous function f. based on the Mexican hat function (Absil et (2005). such that even the direction of the parameter does not converge along gradient flow (it moves around cirle when increases).
4

---

Published as a conference paper at ICLR 2020
For brevity, we say that function & I R the interval is are if z is absolutely continuous for any compact sub-interval of I. For an are 2, x' xt) (or dz (t)) stands for the derivative at t if exists. Following the terminology in (Davis et al. 2020 di
say that locally Lipschitz function f: Rd + R. admits a chain rule if for any are 2 ::: 4.0) + Té vh E O f(=(t)) x))(() (h, z' (1) holds for a.e. t > 0 (see also Appendix
Binary Classification. Let & be a neural network, assumed to be parameterized by 9. The output of & on an input [R a real number (0;; æt), and the sign of (0;; x)) stands for the classification result. A dataset is denoted by D = { Vn) n2 E [M]] where 2n E IR stands for a data input and yo E {=1} stands for the corresponding label. For a loss function l I + R, we define the
training loss & on the dataset to be ( == Σm= ( x.)).
Gradient Descent. We consider the process of training this neural network O with either gradient descent or gradient flow. For gradient descent, we assume the training loss (()) is C²-smooth and describe the gradient descnet process as ( + rate at time and V (t)()) is the gradient of L at (().
((t) - -nnnn(((((())) where (7t)) is the learning
Gradient Flow. For gradient flow, we do assume the differentibility but only some regu- larity assumptions including locally Lipschitz. Gradient flow can be seen as gradient descent with infinitesimal step size. In this model, 0 changes continuously with time, and the trajectory of param- eter O during training is an are 0 : [0, +oo) + R + (t) that satisfies the differential inclusion do(1) E - (()(t)) for a.e. t 2 The Clarke's 's subdifferential 8 C is natural generalization of the usual differential non-differentiable functions. If C(0) is actually C²-smooth function, the d010) VC(((t)) for all 2 0, which corresponds to the
above differential inclusion reduces to de gradient flow with differential in the usual sense.
GRADIENT DESCENT / GRADIENT FLOW ON HOMOGENEOUS MODEL
In this section, we first state our results for gradient flow and gradient descent on homogeneous models with exponential loss E(q) := e for simplicity of presentation. Due to space limit, we defer the more general results which hold for large family of loss functions (including logistic loss and cross-entropy loss) to Appendix A and G
4.1 ASSUMPTIONS
Gradient Flow. For gradient flow, we assume the following:
(A1). (Regularity). For any fixed æ. + (z))) is locally Lipschitz. and admits a chain rule;
(A2). (Homogeneity). There exists I, > 0 such that Vo > 0: :(<af;; x) = = (0;
(A3). (Exponential Loss). E(g) = 9;
(A4). (Separability). There exists a time ln such that L(0(1))) <
(A1) a technical assumption about the regularity the network output. As shown in (Davis al.) 2020), the output of almost every neural network admits chain rule (as long as the neural network is composed by definable picces in an o-minimal structure, c.g., ReLU, sigmoid, LeakyReLU).
(A2) assumes the homogeneity, the main property we assume in this work. (A3), (A4) correspond to the two conditions introduced in Section[] [ The exponential loss in (A3) is main focus of this section.
(A4) is separability assumption: the condition L(O(t))) < 1 ensures that f(y,, & (0((t)) xx)) for all n E [N], and thus yn. (((())) a.,)) > O, meaning that classifies every s,, correctly.
Gradient Descent. For gradient descent, we assume (A2), (A3), (A4) similarly for gradient flow, and the following two assumptions (S1) and (S5).
(SI). (Smoothness). For any fixed æ, & (((::))) is Cm-soooth on Rd {0).
(S5). (Learning rate condition, Informal). ntt) = ?/o for sufficiently small constant Ji.- fact, 7tt is even allowed to be as large as ((C(t) (C(C(t))'ollyoo)) ""polylop z(zz). See Appendix E. for the details.
5

---

Published as a conference paper at ICLR 2020
(S5) is natural since deep neural networks usually trained with constant learning rates. (S1) ensures the smoothness of Q. which often assumed in the optimization literature in order to analyze gradient descent. While (S1) does not hold for neural networks with RcLU, it does hold for neural networks with smooth homogeneous activation such as the quadratic activation Φ(x) == x²² (Li
2018h
Du & Lee 2018) powers of ReLU ((x) (e)U(x;)) for > (Zhong et al. 2017 Klusowski & Barron
2018 Li et al. 2019).
4.2
MAIN THEOREM: MONOTONICITY OF NORMALIZED MARGINS
The margin for single data point (Ztn; ) is defined to be yn (0) yn (0; ær,), and the margin for the entire dataset is defined to be Jmin (0) == min 4n (0) By homogenity, the margin Jmin (f)
scales linearly with 001/2 for any fixed direction since Juin (cf) = c² qmin (0). So we consider the normalized margin defined as below:
0
Amin 0
70)) = Amin
(2)
|101|2
1012
We say is e-additive approximation for the normalized margin if 7 - S S 7, and multiplicative approximation if c S 5.
Gradient Flow. Our first result on the overall trend of the normalized margin 50(()). For both gradient flow and gradient descent, we identify smoothed version of the normalized margin, and show that is non-decreasing during training. More specifically, we have the following theorem for gradient flow.
Theorem 4.1 (Corollary of Theorem A.7 Under assumptions (A1) (A4), there exists an )-addiiiee upproximation function ((0) the normalized margin such that the following statements are true for gradient flow:
1. For a.e. b to: dt ( 2 0:
d.
2. For a.e. >>> lo, either d
di = > 0 or dt T00
A(t) 0,
3. c(O(t)) + 0 and [[(()]l2 + xo as f - +o0; therefore, 15(((t)) - ((((t)) + 0.
More concretely, the function 70) in Theorem 4.1 is defined as
log e (m
(0) := log 2(0)
(3)
|
101
Note that the only difference between (0) and (0) is that the margin Amin (0) in (0) is placed by log Z(0j = - -... (f)...., (0)), where LSF((r....,. aNy = log (og(exp(a1) + + exp(ax)) ) is the LogSumExp function. This is indeed very natural idea, and previous works on linear models (e.g., (Telgarsky] [2013] Nacson et al., 2019b)) also approximate Jmin with LogSumExp in the analysis margin. It is easy to see why 7(0) is an 0(10112 -addditvve ap- proximation for (0): eamua < E E < Ne holds for Qmax = max(a1..... aN }. so 4max < LSE(aa, .NN) S Umax + log N; combining this with the definition of 50) gives 70) | llo < (00 (0)).
Gradient Descent. For gradient descent, Theorem 4.1 holds similarly with a slightly different function (0) that approximates (0) multiplicatively rather than additively.
Theorem 4.2 (Corollary of Theorem E.2). Under assumptions (SI), (A2) (A4), (S5), there exists an (1 ((1/(log -)))muultplicaative approximation function (0) for the normalized margin such that the following statements are true for gradient descent:
1. For all t >> to. A(0(t 1)) (((()))
2. For all f. t> lg, either (0(t + 1)) > (0())) or
O(t+1) 0(t)
T0(+1))2 [0(0)]2"
3. ((O())) - 0 and [[0(t]]2 + xo as t + +oo; therefore, (5(()t) - 1 (0())) +
Due to the discreteness of gradient descent, the explicit formula for (0)) is somewhat technical, and refer the readers to Appendix E for full details.

---

hope for in our setting, and it is Published as a conference paper at ICLR 2020
Convergence Rates. is shown in Theorem 4.1
4.2 that (((())) - 0 and ||@(t]]2 + In fact, with a more refined analysis, we can prove tight loss convergence and weight growth rates using the monotonicity of normalized margins.
Theorem 4.3 (Corollary of Theorem A.10 and E.5
For gradient flow under assumptions (AI) (A4) or gradient descent under assumptions (SI), (A2) - (A4), (S5), we have the following tight bounds for training loss and weight norm:
[(((1)) =
and
- [0(()l22 - (log (10))))
T(lo 2)2-2/1 2/1
where T for gradient flow and T Er ( gradient descent.
4.3 MAIN THEOREM: CONVERGENCE TO KKT POINTS
For gradient flow, 7 is upper-bounded by ア < 7 S sup(gn (0) : = 1}. Combining this with Theorem 4.1 and the monotone convergence theorem, it is not hard to see that lim,-++o (0())) and lim (())) exist and equal to the same value. Using a similar argument, we can draw the same conclusion for gradient descent.
To understand the implicit regularization effect, a natural question arises: what optimality property does the limit of normalized margin have? To this end, we identify a natural constrained optimization problem related to margin maximization, and prove that (()) directionally converges to its KKT points, shown below. We note that can extend this result the finite time case, and show that gradient flow or gradient descent passes through an approximate KKT point after a certain amount of time. See Theorem A.9 in Appendix [ and Theorem E.4 in Appendix [E] the details. We will briefly review the definition of KKT points and approximate KKT points for a constraint optimization problem in Appendix C.T
Theorem 4.4 (Corollary of Theorem A.8 and E.3). For gradient flow under assumptions (Al) (A4)
or gradient descent under assumptions (SI), (A2) (A4), (S5), any limit point 0 of Tocee]l 2 0)
0())
is along the direction of a KKT point of the following constrained optimization problem (P):
min
Ja (0)
Vn
[N]
That is. for any limit point O, there exists a factor a > such that at satisfies Carush-KKuhi Tucker (KKT) conditions (P).
Minimizing (P) over its feasible region is equivalent to maximizing the normalized margin over all possible directions. The proof is as follows. Note that we only need to consider all feasible points with guin (0) > For fixed 0, af is a feasible point of (P) iff a 2 qmin (0)-1/L, Thus, the minimum objective value over all feasible points of (P) in the direction of is } 10/ 9m/i (0)1/1113 (0) 2/L, Taking minimum over all possible directions, we can conclude that the maximum normalized margin 7,, then the minimum objective of (P) //-2//2
It can be proved that (P) satisfies the Mangasarian Fromovvitz Constraint Qualification (MFCQ) (See Lemma C.7). Thus, KKT conditions are first-order necessary conditions for global optimality. For linear models, KKT conditions are also sufficient for ensuring global optimality; however, for deep homogeneous networks, 9n. (0) can be highly non-convex. Indeed, as gradient descent a first-order optimization method, if we do not make further assumptions qn (0), then it is easy to construct examples that gradient descent does not lead to a normalized margin that is globally optimal. Thus, proving the convergence KKT points is perhaps the best an interesting future work to prove stronger convergence results with further natural assumptions.
Moreover, can prove the following corollary, which characterizes the optimality of the normal- ized margin using SVM with Neural Tangent Kernel (NTK, introduced in (Jacot et al. 2018)) defined at limit points. The proof is deferred Appendix C.6
Corollary 4.5 (Corollary of Theorem 4.4 Assume (S1). Then for gradient flow under assump- tions (A2)- (A4) or gradient descent under assumptions (A2) (A4), (S5), any limit point of (0()) i. Z 0} is along the max-margin direction for the hard-margin SVM with kernel
7

---

Published as a conference paper at ICLR 2020
Kg(xx (V (0)). where (x) (66; x)) That is, for some 0, af is the optimal solution for the following constrained optimization problem:
S.t. Un (0. V x. (0)) 21
Vn E [N]
If we assume (AI) instead of (SI) for gradient flow, then there exists mapping h(x) E (0) such that the same conclusion holds for K Ko(æ. (z. x²) (h(x), h(x'))
4.4 OTHER MAIN RESULTS
The above results can be extended other settings as shown below.
Other Binary Classification Loss. The results on exponential loss can be generalized to a much
broader class of binary classification loss. The class includes the logistic loss which is one of the most popular loss functions, L(g) = log(1 + 99). The function class also includes other losses with exponential tail. e.g., f(g) e- {(g) = log(1 "-""). For all those loss functions, its inverse function { to define the smoothed normalized margin as follows
(0) - (C(O))
11011/
Then all our results for gradient flow continue hold (Appendix A). Using a similar modification, we can also extend to gradient descent (Appendix F
Cross-entropy Loss. In multi-class classification, the classification score for the true label and the maximum score for the other labels, then the margin
define On be the difference between
Imin(() can be similarly defined as before. Umin := mill [ 2n and the normalized margin 7(0) [
In Appendix G we define the smoothed normalized margin for cross-entropy loss to be the same as that for logistic loss (See Remark A.4). Then we show that Theorem 4.1 and Theorem 4.4 still hold
(but with a slightly different definition of (P)) for gradient flow, and we also extend the results to gradient descent.
Multe-homogeneous Models. Some neural networks indeed possess a stronger property than homogeneity, which call malti-homogeneity.. For example, the output of CNN (without bias terms) is 1-homogeneous with respect to the weights of each layer. In general, we say that a neu- ral network (0; æ) with = [w.....; Wm) is (k1,..., h.....,,mm)--o hhomoggneess if for any æ and any C1..... Cm we have ((c, Cm Wm x) II C. example, an L-layer CNN with layer weights 0 (WI.... WL) is (1...., 1) homogennuuss
Wm: σ). the previous
One can easily see that that (ki...., km -ho.mmmmoooeiitt implies L-homogeneity, where Σm ks, so our previous analysis for homogeneous models still applies to multi-homogenen mod- els. But it would be better to define the normalized margin for multi-homogeneous model as
w
Wm
Imin
7 7( wm) == 9min
(4)
| 2
Wm 2
In this case, the smoothed approximation of 7 for general binary classification loss (under some conditions) can be similarly defined for gradient flow:
(C)
7( ( Wm))
I |. 11
It can be shown that 7 is also non-decreasing during training when the loss is small enough (Ap- pendix H). In the case of cross-entropy loss, we can still define & by (5) while f(-) is set to the logistic loss in the formula.
5 PROOF SKETCH: GRADIENT FLOW ON HOMOGENEOUS MODEL WITH EXPONENTIAL LOss
In this section, present a proof sketch in the of gradient flow homogeneous model with exponential loss to illustrate our proof ideas. Due to space limit, the proof for the main theorems on gradient flow and gradient descent in Section 4 are deferred to Appendix A and respectively.
8

---

Published as a conference paper at ICLR 2020
For convenience, we introduce few more notations for L-homogeneous neural network ( a).. Let 5t {0
E R ||01|2 = } be the set of no-nomlllee parameters. Define p := |0| and : 0 E su-1 to be the length and direction of 0. For both gradient descent and Tellz
also view the functions of 0, in- cluding [(O), 9n (0). Imin (0). as functions of t. So we can write L(() = L(O(1)), 9m = qn (t)), qmin (t) == qmin (0())).
gradient flow, 0 is function of time I. For convenience,
Lemma 5.1 below is the key lemma in our proof. It decomposes the growth of the smoothed normal- ized margin into the ratio of two quantities related the radial and tangential velocity components of 0 respectively. We will give a proof sketch for this later in this section. We believe that this lemma is of independent interest.
Lemma 5.1 (Corollary of Lemma B.1 For a.e. t to.
2
d0
log 0 and dt
log 7 2 L
log
dt
dt
dt
be directly proved. For the third claim, we make use of the monotonicity of the margin to lower bound the gradient, and then show - 0 and p + +00. Recall that 7 is an O(p "-aaditivee approximation for 5. So this proves the third claim. We defer the detailed proof to Appendix B
Using Lemma 5.1 the first two claims in Theorem 4.1
To show Theorem lo So the second inequality in Lemma 5.1 can be rewritten as P
we first change the time measure to log p. i.e., now we t function of d'log 2 Iill Zl
db 13 Integrating
on both sides and noting that 7 is upper- bounded, we know that there must be many instant log such that || 2 is small. By analyzing the landscape of training loss, we show that these points are "approximate" KKT points. Then we show that every convergent sub-sequence of (Ō(t) : 0} can be modified to be a sequence of "approximate" KKT points which converges to the same limit. Then we conclude the proof by applying theorem from (Dutta al.) 2013) show that the limit of this convergent sequence of "approximate" KKT points is a KKT point. We defer the detailed proof to Appendix C
Now we give proof sketch for Lemma 5.1 in which we derive the formula of 7 step by step. In the proof, we obtain several clean close form formulas for several relevant quantities, by using the chain rule and Euler's 's theorem for homogeneous functions extensively.
Proof Sketch of Lemma 5.7 For ease of presentation, we ignore the regularity issues of taking dc derivatives in this proof sketch. We start from the equation dr - (0 ((O(t), de) - at
d0
which follows from the chain rule (see also Lemma I.3). Then we note that 40 ai can be decomposed
into two parts: the radial component v δ de and the tangent component u = (I 00 di dt
The radial component is easier to analyze. By the chain rule, ||l|2 Ô do
(0,
d0 1. do²
dt
p de
do² For 2 dr we have an exact formula:
1 dp²
d0 dt
0
Σ
E
2n 80
Σ In Qu-
(6)
2 dt
The last equality is due to (Ø qm. 0) Lqn, by homogeneity of qu- This is sometimes called Euler's s theorem for homogeneous functions (see Theorem|B.] B.2p) For differentiable gn. it can be easily proved by taking the derivative over on both sides of on (c0) cf (0) and letting = 1.
With (6) we can lower bound
I dp²
by
2 dt
1 dp2
N
=
4a qn
2 e an Jmin 2 L L..Llop Loog
2 dt
L
n=1
n=1
where the last inequality uses the fact that e -umin since L(to) 1 and L is non-increasing. As log p
L. 7 also implies that 2 de² for L to do² this also proves the first inequality
2p
of Lemma 5.1

---

Published as a conference paper at ICLR 2020
Now, have ||el12
1
1 do²
do²
d
log p the one hand; on the other hand, by the
p²
2
de
chain rule we have
(p
de
de
# (p dt
(Ø
de 0)
So we have
de
P
dl
d0 2
1 dp²
d
d0
|1012 + ||ea|
log p + p²
dt
dt
2 dt
dt
dt
Dividing ! de dr on the leftmost and rightmost sides, we have
dc (1 dp² -1 d 2 dt =
d log
d0
log
dt
dt
dt
dt
By dt 2 0 and 7 the LHS is no greater than
dc
(L .l..ooo// 2
& log log Z. Thus we
dt
have log log L di log p 2 at
d
lo
where the LHS exactly d log
DISCUSSION AND FUTURE DIRECTIONS
In this paper, we analyze the dynamics of gradient flow/descent of homogeneous neural networks under minimal set of assumptions. The main technical contribution of our work to prove rigor- ously that for gradient flow/descent, the normalized margin is increasing and converges to a KKT point of a natural max-margin problem. Our results leads to some natural further questions:
Can we generalize our results for gradient descent on smooth neural networks to non- smooth ones? In the smooth case, we can lower bound the decrement of training loss by the gradient norm squared, multiplied by factor related learning rate. However, in non-smooth case, no such inequality is known in the optimization literature.
Can we make structural assumptions the neural network prove stronger results? In this work, we use minimal set of assumptions to show that the convergent direction of parameters is KKT point. potential research direction is identify more key properties of modern neural networks and show that the normalized margin at convergence is locally or globally optimal (in terms of optimizing (P)).
Can we extend our results to neural networks with bias terms? In our experiments, the normalized margin of the CNN with bias also increases during training despite that its output is non-homogeneous. It is very interesting (and technically challenging) to provide a rigorous proof for this fact.
ACKNOWLEDGMENTS
The research is supported in part by the National Natural Science Foundation of China Grant 61822203, 61772297, 61632016, 61761 146003and the Zhongguancun Haihua Institute for Fron- tier Information Technology and Turing AI Institute of Nanjing. We thank Liwei Wang for helpful suggestions on the connection between margin and robustness. We thank Sanjeev Arora, Tianle Cai, Simon Du, Jason D. Lee, Zhiyuan Li, Tengyu Ma, Ruosong Wang for helpful discussions.
REFERENCES
Pierre-Antoing Absil, Robert Mahony, and Benjamin Andrews. Convergence of the iterates of de- scent methods for analytic cost functions. SIAM Journal on Optimization, 16(2):531-547, 2005.
Alnur Ali, J. Zico Kolter, and Ryan J. Tibshirani. A continuous view early stopping for least squares regression. In Kamalika Chaudhuri and Masashi Sugiyama (eds.). Proceedings of Machine Learning Research, volume 89 Proceedings of Machine Learning Research, pp- 1370-1378. PMLR, 16-18 Apr 2019.
10

---

Published as a conference paper at ICLR 2020
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 242-252, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In Ka- malika Chaudhuri and Ruslan Salakbutdinov (eds.). Proceedings of the 36th International Con- ference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp- 291-301, Long Beach, California, USA, 09-15 Jun 2019. PMIR.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix fac- torization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems 32, pp. 7411-7422. Curran Asso- ciates, Inc., 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Buc, Systems 32, pp. 113-8148. Curran Associates, Inc., 2019b.
Fox, and Garnett (eds.), Advances in Neural Information Processing
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of secu- rity: Circumventing defenses to adversarial examples. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pp. 273,283, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Andrzej Banburski, Qianli Liao, Brando Miranda, Tomaso Poggio, Lorenzo Rosasco, and Jack Hidary. Theory III: Dynamics and generalization in deep networks. CBMM Memo No: 090, version 20, 2019.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normaaized normalized margin bounds for neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6240-6249. Curran Associates, Inc., 2017.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný (eds.), Machine Learning and Knowledge Discovery in Databases, pp. 387-402, Berlin, Heidelberg. 2013. Springer Berlin Hei- delberg.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an -usteennuuleenbeck like process, arXiv preprint arXiv: (00::99040000000 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 37, May 2017. doi: 10. 10.1109/SP.2017.4
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parse- val networks: Improving robustness to adversarial examples. Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pp. 863, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Francis H. Clarke, Yuri S. Ledyaev, Ronald Stern, and Peter R. Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science & Business Media, 2008.
Frank H. Clarke. Generalized gradients and applications. Transactions of the American Mathemat- ical Society, 205:247-262, 1975.
Frank H Clarke, Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathe- matics, 1990. doi: 1111117771977111119999
Michel Coste, An Introduction to O O-minimal Geometry. 2002.
11

---

Published as a conference paper at ICLR 2020
Haskell B Curry. The method of steepest descent for non-linear minimization problems. Quarterly of Applied Mathematics, (99:258-261. 1944.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D. Lee. Stochastic subgradient method converges tame functions. Foundations of Computational Mathematics, 20(1):119- 154, Feb 2020.
Dmitriy Drusvyatskiy, Alexander D Ioffe, and Adrian S Lewis. Curves of descent. SIAM Journal on Control and Optimization, 53(1):114-138 2015.
Simon Du and Jason Lee. On the power of over pwrmpearamtiiiiatoonn in neural networks with quadratic activation. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. volume of Proceedings of Machine Learning Research, pp- 1329-1338, Stockholmsmässann Stockholm Sweden, 10-15 Jul 2018. PMLR.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Pro- ceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Simon S. Du. Wei Hu, and Jason D. Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Resa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 382-393. Curran Associates, Inc., 2018.
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. Approximate KKT points and a proximity measure for termination. Journal of Global Optimization, 56(4):1463-14
2013.
Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp- 3196-3206. Curran Associates, Inc., 2019.
Giorgio Giorgi, Angelo Guerraggio, and Jörg Thierfelder. Chapter IV Nonsmooth Optimization Problems. Mathematics of Optimization, pp. 359 457. Elsevier Science, Amsterdam, 2004. ISBN 978-0-444-50550-7.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 297-299. PMLR, 06 Jul 2018
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1832-1841, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018a. PMLR.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 9482- 9491. Curran Associates, Inc., 2018b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification. In The IEEE International Conference on Computer Vision (ICCV), December 2015.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kemnl:: Convergence and gen- eralization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8571- 8580. Curran Associates, Inc., 2018.
12

---

Published as a conference paper at ICLR 2020
Ziwei and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300, 2018.
Ziwei and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference Learning Representations, 2019a.
Ziwei Ji and Matus Telgarsky. A refined primal-dual analysis of the implicit bias. arXiv preprint arXiv:/906. 04540, 2019b.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Alina Beygelzimer and Daniel Hsu (eds.). Proceedings of the Thirry-Second Conference on Learn- ing Theory, volume of Proceedings of Machine Learning Research, pp. 1772 1798,, Phoenix, USA, 25 28 Jun 2019c. PMLR.
Jason M Klusowski and Andrew Barron. Approximation by combinations of relu and squared relu ridge functions with e! and e controls. IEEE Transactions on Information Theory, 64 (1):: 7649-7656, 2018.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 3570-8581. Curran Associates, Inc., 2019.
Bo Li, Shanshan Tang, and Haijun Yu. Better approximations of high dimensional smooth functions by deep neural networks with rectified power units. arXiv preprint arXiv:1903.0585. 2019.
Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao. On tighter generalization bound for deep neural networks: CNNs, ResNets, and beyond. arXiv preprint arXiv: 159, 2018a.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in perepparameteiizedd matrix sensing and neural networks with quadratic activations. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 2-47. PMLR, 06-09 Jul 2018b.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statis- tical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations of Computational Mathematics, Aug 2019.
Mor Shpigel Nacson, Suriya Gunasckar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4683-4692, Long Beach, California, USA, 09-15 Jun 2019a. PMLR.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent separable data. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 3420-3428. PMLR, 16-18 Apr 2019b.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent separa- ble data: Exact convergence with a fixed learning rate. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings Machine Learning Research, volume 89 of Proceedings of Ma- chine Learning Research, pp. 3051-3059, PMLR, 16-18 Apr 2019c.
Behnam Neyshabur, Ruslan R Salakhutdinov, and Nati Srebro. Path-SGD: Path-normalized opti- mization in deep neural networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 2422-242222222 2230. Curran Associates, Inc., 2015a.
13

---

Published as a conference paper at ICLR 2020
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015b.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally-normalized margin bounds for neural networks. In International Conference on Learn- ing Representations, 2018.
J Jr Palis and Welington De Melo. Geometric theory of dynamical systems: introduction. Springer Science & Business Media, 2012.
Aaditya Ramdas and Javier Pena. Towards deeper geometric, analytic and algorithmic understand- ing of margins. Optimization Methods and Software, 31(2):777-391, 2016.
Saharon Rosset, Ji Zhu, and Trevor J. Hastie. Margin maximizing loss functions. S. Thrun, L. K. Saul, and B. Schölkopf (eds.), Advances in Neural Information Processing Systems 16, pp. 1237-1244. MIT Press, 2004.
Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. The MIT Press, 2012.
ISBN 0262017180, 9780262017183.
Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. Ann. Statist., 1615):6 10 1998. doi: 10. /4.1214/00/10224613332
Shai Shalev-Shwartz and Yoram Singer. On the equivalence of weak learnability and linear sepa- rability: New relaxations and efficient boosting algorithms. Machine learning, 80(2-3):141-16 2010.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues. Robust large margin deep neural networks. IEEE Trans. Signal Processing, 65(16))4265 42800 2017. doi: 10.1 TSP.2017.2708033
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70): 1-57, 2018a.
Daniel Soudry, Elad Hoffer, and Nathan Srebro. The implicit bias of gradient descent on separable data. In International Conference Learning Representations, 201 8b.
Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar. Connecting optimization and regulariza- and R. Gamett
tion paths. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. (eds.), Advances in Neural Information Processing Systems 31, pp. 10608-10619, Curran Asso- ciates, Inc., 2018
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2013.
Matus Telgarsky. Margins, shrinkage, and boosting. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 307-315, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Lou van den Dries and Chris Miller. Geometric categories and o-minimal structures. Duke Mathe- matical Journal, 84(2)497-540, 1996.
Colin Wei and Tengyu Ma. Improved sample complexities for deep neural networks and robust classification via an all-layer margin. In International Conference on Learning Representations, 2020.
14

---

Published as a conference paper at ICLR 2020
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kemnel. H. Wallach, H. Larochelle. A. Beygelz- imer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 9709-9721. Curran Associates, Inc., 2019.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stem, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 4148 4158. Curran Associates, Inc., 2017.
Tengyu Xu, Yi Zhou, Kaiyi Ji, and Yingbin Liang. When will gradient methods converge to max- margin classifier under relu models? arXiv preprint arXiv:1806. Stt.:::8800003399. 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations, 2017.
Hongyi Zhang, Yann N. Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization. In International Conference on Learning Representations, 2019.
Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one-hidden-layer neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 4140, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888, 2018
Guus Zoutendijk. Mathematical programming methods. 1976.
15

---

Published as a conference paper at ICLR 2020
A RESULTS FOR GENERAL LOss
In this section, we state our results for a broad class of binary classification loss. A major con- sequence of this generalization is that the logistic loss, one of the most popular loss functions, E(g) = log(1 + e 9) is included. The function class also includes other losses with exponential tail, e.g., {()) = =e- ((g) log(1 + +
A.1 ASSUMPTIONS
We first focus on gradient flow. We assume (A1), (A2) as we do for exponential loss. For (A3), (A4), replace them with two weaker assumptions (B3), (B4). All the assumptions are listed below:
(A1). (Regularity). For any fixed æ; ( is locally Lipschitz and admits a chain rule;
(A2). (Homogeneity). There exists L > such that Va > 0 : $(a0; x) = a (0:(((0)))
(B3). The loss function {(g) can be expressed as E(g) = e -f()) such that (B3.1). f: + R is Cm-smooth. (B3.2). fl(2) > 0 for all q E R.
(B3.3). There exists bj 2 0 such that f'(4)q non-decreasing for q E (by, +00), and f'(g)q + to0 as q + +00.
(B3.4). Let g : [[(by), +xx) + +x)) be the inverse function of f on the domain (6y.+0o). There exists by 2 max(2f(br) f(b)))) ((2)2 2 such that g'(x) s
Kg'(0z) and f2()) (0y) for all x (6g. +00), E (g(6)),+t0) and
0 E 1).
(B4). (Separability). There exists a time to such that L(to) < e f(bp) = e(bs).
(AI) and (A2) remain unchanged. (B3) is satisfied by exponential loss {(g) = - (with f(g) 4) and logistic loss (() = log(1 + e-) (with f(2) = - llgg log(1 + e)))). (B4) are essentially the same as (A4) but (B4) uses a threshold value that depends on the loss function. Assuming (B3),
easy to see that (B4) ensures the separability of data since ((gn) < e(bp) implies On > by 2 0. For logistic loss, we can set by = 0 (see Remark A.2). So the corresponding threshold value in (B4) ((0) = 2.
Now we discuss each of the assumptions in (B3). (B3.1) is a natural assumption on smoothness. (B3.2) requires E(.) to be monotone decreasing, which is also natural since E(.) used for binary classification. The rest of two assumptions in (B3) characterize the properties of e ('(q) when is large enough. (B3.3) is an assumption that appears naturally from the proof. For exponential loss, ('(2) q is always non-decreasing, so we can set by = 0. In (B3.4), the inverse function y is defined. It is guaranteed by (B3.1) and (B3.2) that always exists and g is also C² -m-ooohth. Though (B3.4) looks very complicated, essentially says that (e)) = as 9 + co. (B3.4) is indeed a technical assumption that enables us to asymptotically compare the loss or the length gradient at different data points. It is possible to base our results on weaker assumptions than (B3.4), but we use (B3.4) for simplicity since it has already been satisfied by many loss functions such as the aforementioned examples.
O(g' (4))
We summarize the corresponding f.g and by for exponential loss and logistic loss below: Remark A.1. Exponential loss E(q) = e satisfies (B3) with
f(g)= = f'(g) = g(q) = q
g'(g) = 1
by
E(by)) 1.
Remark A.2. Logistic loss f(4) log(1 + 9) satisfies (B3) with
f(g) = log log(1 + - = O(4)
f'(1) = (1+e log + +e = (1)
g'(g) = 7
9(4) = - - -1)=
-- -
by = 0
E(by) log 2.
The proof for Remark A.1 is trivial, For Remark
A.2 we give proof below.
16

---

Published as a conference paper at ICLR 2020
Proof for RemarkAL A.2 By simple calculations, the formulas for f(q), (4)) ((9), of g'(q) correct. (B3.1) is trivial.
0, so (B3.2) is satisfied. For (B3.3), note that The denominator is decreasing function since
(((4) (1+69] 1+e-oy
((1 +
+e ))) = e² log 1 + e-)) - - 0.
dq
Thus, fl(4)q is strietly increasing function on R. As by is required to be non-negative, we set by 0. For proving that fl(4)q + +o0 and (B4), we only need to notice that f (g) I-e and (((x) = 1/f()(())~11 ~1
A.2 SMOOTHED NORMALIZED MARGIN
For loss function {()) satistying (B3), it is easy to see from (B3.2) that its inverse function (-) must exist. For this kind of loss functions, define the smoothed normalized margin as follows:
Definition A.3. For a loss function {()) satisfying (B3), the smoothed normalized margin 7(0) of defined as
g(log 2) 9 (- ph.
1 e (-(()((0))
(2) ph
7(0) -00==----
ph
where e- (-) is the inverse function of ((-) and p: 10||
Remark A.4. For logistic loss Elg) = log + +e= 7(0) log exp(C)-Ti for exponential loss
((g) - 5(0) = p log +. which is the same as 3
Now we give some insights how well 7(0) approximates (0) using similar argument in Section 4.2 Using the LogSumExp function, the smoothed normalized margin 5(0) can also be written
(0) g(-LSE((f(())...... -f(x=((().......((x))) -((x))))
LSE is a (log adddiive approximation for max. So we can roughly approximate (0) by
-(.)))....... (()) g max{
((f(qmin)) 5(0).
p²
ph
Note that (B3.3) is crucial to make the above approximation reasonable. Similar to exponential loss, we can show the following lemma asserting that & is good approximation of 7.
Lemma A.5. Assuming (B3 | we have the following properties about the margin:
(a) (Tmin) - log N < log & S f(fmin).
(b) Iflog > f(by), then there exists E (f(qu))) - log N, f(f(ii))) n +oo) such that
(E) log N
5 53.
ph
(c) For a seugnce of parameters (0m E Rd m E N}, if ((0m) - then (5.)..) -((mm) 0.
Proof. (a) can be easily deduced from f(gmm))) < < Ne -(-m()mm)) Combining (a) and the
monotonicity of g(-), we further have g()) g(log 1 < Imin for = max(f(b;). ((gmin
No. . By the mean value Theorem, there exists & E (s, (quin) such that g(s) g (f (f((i))) 2 Juin g ({) log N. Dividing p" on each side of Jmin g((() log N S
( g(log 2) I Jmin proves (b).
Now we prove (c), Without loss of generality, we assume log E(OmJ > f(by) for all On. It follows from (b) that for every O., there exists &m (f(mii (0m)) log N. {(miuu (0... 1)) (by, +00) such that
(0m.. (Em) log N)/ p < (00m) < (0m).
Indeed, (B3.4) is needed for showing Lemma A.5 and Thenrem A.7
17

---

Published as a conference paper at ICLR 2020
Note that 5m 2 (9min log N 2
log 2(0m) log N + to0. So gl6m)
g'(Em)
(l(o(Em))g(Em) too by (B3.3), Also note that there exists a constant Bo such that ((0m) S Bo for all since 7 continuous on the unit sphere Sd-1, So we have
gEmm) (((mm) g(Em) gE(mm) Amin (0m. g((mm 7(mm)
((Em) B g(Em)
p(0m) g(Sm) p(0m) g(Sm) p(0m) g(Em)
where the first inequality follows since Em S (0 Together with 70m)) 0.
we have (7(mm
0
Remark A.6. For exponential loss, we have already shown in Section 4.2 that 50) is an O(p 4)-
additive approximation for (0). For logistic loss, follows easily from g' (4) ((1) and (b) of Lemma A.5 that ((0) is an O(p "(p="---dditin approximation for (0) if C is sufficiently small.
A.3 THEOREMS
Now we state our main theorems. For the monotonicity of the normalized margin, we have the following theorem. The proof is provided in Appendix B
Theorem A.7. Under assumptions (AI), (A2), (B3)*, (B4), the following statements are true for gradient flow:
1. For a.e. > to. de =(((())) 2 0;
2. For a.e. 1> la, either _ =(((())) > 0 or dt Te
0()) 0,
3. ((O(t)) + 0 and [[(())l2 co as too; therefore, (5(()t) - ((0(t)) +
For the normalized margin at convergence, have two theorems, one for infinite-time limiting case, and the other being a finite-time quantitative result. Their proofs can be found in Appendix C As in the exponential loss case, define the constrained optimization problem (P) follows:
min 2
|012
s.t. (0) 21 vn E [N]
First, we show the directional convergence of (()) to a KKT point of (P).
Theorem A.8. Consider gradient flow under assumptions (AI), (A2), (B3), (B4). For every limit point 0 of { (()) 2 0). 0/ (0//mmin001//// (0)1/L is KKT point of (P).
Second, we show that after finite time, gradient flow can pass through an approximate KKT point. Theorem A.9. Consider gradient flow under assumptions (AI), (A2), (B3), (B4). For any e, O, there exists := (log 5-1) and A == ((c-2) such that 0 0/qmiu (0) // is an (c,5)-KKT) KKT point at some time t, satisfying log (t..) ll (r, r A).
For the definitions for KKT points and approximate KKT points, we refer the readers to Ap- pendix C. for more details.
With a refined analysis, we can also provide tight rates for loss convergence and weight growth. The proof given in Appendix [
Theorem A.10. Under assumptions (AI), (A2), (B3), (B4), we huve the following tight rates for loss convergence and weight growth:
(9log t)2/z
L(((t)) @
(
and |10(0)]2 = (lo((oo)))/))
1(log l)2
Applying Theorem A.10 exponential loss and logistic loss, in which g(x) O(z), we have the following corollary:
Corollary A.11. If ((.) is the exponential logistic loss, then.
((((1)) = ((
( 2/2 and [10(t)]22 = ((logt)
18

---

Published as a conference paper at ICLR 2020
B MARGIN MONOTONICITY FOR GENERAL LOSS
In this section, we consider gradient flow and prove Theorem A.7
We assume (AI), (A2), (B3),
(B4) mentioned in Appendix A
We follow the notations in Section define p = ||0||2 and 0 10 we view the functions of 0 as functions
E Sd-1, and sometimes
B.1 PROOF FOR PROPOSITION AND 2
To prove the first two propositions, generalize our key lemma (Lemma Lemma B.1. For ýy defined in Definition A.3 the following holds for all to.
5.1
to general loss.
d log 2
-1
d0
log p > and dt
log P
dt
dt
dt
Before proving Lemma B.1 we review two important properties of homogeneous functions. Note that these two properties are usually shown for smooth functions. By considering Clarke's subdif- ferential, generalize
locally Lipschitz functions that admit chain rules:
Theorem B.2. Let Rd + IR be a locally Lipschitz function that admits a chain rule. If F is k-homogeneous, then
(a) For all x E Rd and a > O,
8 =
That is, F(ax)))= = fa-- E F(x))
(b) (Euler's Theorem for Homogeneous Functions), For all a E Rd,
(xr08 F())) = k F(x)
That is, (xx, h) k- F(x) all 8 F(x).
Proof. Let D be the set of points such that F is differentiable at According to the definition of Clarke's subdifferential, for proving (a), it sufficient to show that
lim V(((x))): ag + x, oæ D} k-1 lim VF(xx) æ x. Th D3 t0000
(10)
A
Fix 2b D. Let U be neighborhood of ag.- By definition of homogeneity, for any Idd and any y E U {
F(ay) F(axx) (ay - aook k 11) k-1 F(y) - F(xx) - (y xz, h))
lay az l
y
x3 ll
Taking limits y + æ on both sides, we know that the LHS converges iff the RHS converges to O. Then by definition of differetiability and gradient. F is differentiable at axg iff it is differentiable Øg, and V F(aak) = k h iff F((x)) h. This proves (10).
To prove (b), we fix x E Rd. Let [0, +00) + Rd a + oz be an arc. By definition of homogeneity, (F 2) = a F(x) ( for > Taking derivative with respect to a on both sides (for differentiable points), we have
Yh 8 F(ax): (x, h) = kaa-1F(x
(1I)
holds for a.e. > O. Pick an arbitrary > 0 making (II) hold. Then by (a), is equivalent to wh F(x) a-11) ka F F(x), which proves (b).
Applying Theorem B.2 to homogeneous neural networks, have the following corollary:
Corollary B.3. Under the assumptions (AI) and (A2), for any E Rd and x E Rd,
0. L t (0),
where Th (0) =0(0; x)) is the nefwork output for fixed input
19

---

Published as a conference paper at ICLR 2020
Corollary B.3 can be used to derive exact formula for the weight growth during training. Theorem B.4. For a.e. & 2 O,
1 dp² Σ e
Nan)
2 di
Proof. The proof idea is to Corollary B.3 and chain rules (See Appendix || for chain rules in Clarke's sense). Applying the chain rule on 1 + p² 100 yields 1 dp²
h 8 L and a.e. / > 0. Then applying the chain rule on 0 L, we have 2 or (0, h) for all
- c Σ flan) I (g)) 4m
flan) (lau)) hn d ou
By Corollary B.3 (0, hen) Lan. and thus 1/2 do²
L LE
N e flan)))
For convenience, we define v(t) = En (faw) (l for all t 0. Then Theorem B.4 can be rephrased as 1 dg² 2 dt = Lv(t) for a.c. t t2
Lemma B.S. For all i to.
v(t) 2 g(log 1 L.
g' (log 2)
Proof. By Lemma A.5 In 2 g(lg 2) for all n E [N]] Then by Assumption (B3),
fg (g ) g(log 2 I' o'logg t
g(log 2
Combining this with the definitions of v(t) and L gives
f' f' 2 Σ e (lan) glog 2) = g(log 2 I' 5'log Z)
N
((t) = Σ - ((ma)
L.
g' o'(log 2)
n=1
n=1
Proof for Lemma B.1 Note that d
ds log 2p dt = I, 21 by Theorem B.4 Then it simply
1 do²
B.5 that de log > 0 for a.c. t >> to. For the second incquality, we first prove log (g(log b)/p²) exists for all 2 to. L(t) is non-increasing with t. So C(t) e f(br) for all t 2 to. This implies that (1) log is always in the domain of g; (2) p > (otherwise f 2 Ne -e-f(o f(0) > e-f(),, contradicting (B4)). Therefore, 7 == g(log 1)pp exists and is always positive for all 2 to, which proves the existence of log 7.
follows from Lemma
that log 7 = log (L- (2)
By the chain rule and Lemma B.5 we have
d (logg g(log 2)) d log di
I ('log 2)
1
dL
1,2 P() P
log
g(log 2))
dt
d.
v(t)
I
v(t)
dt
d.
L²²(t)2
v(t)
dt
On the one hand, dc = by Theorem B.4 Combining these together yields
de delle for a.e. > O by Lemma
=1
I.3 on the other hand, Lu(t) = (0, d0
di
d
log 2 v(t)
d0
0
d0
))
2
1
[I
② d0
dt
dt
v(t)
dt
20

---

Published as a conference paper at ICLR 2020
By the chain rule, de dt
(I
)
di
de
for
>>
O. So have
p
p
d0
d0
log 7 2
L
log p
dl
(1)
di
dl
di
B.2 PROOF FOR PROPOSITION
To prove the third proposition, prove the following lemma show that C + 0 by giving upper bound for L. Since L can never be 0 for bounded C + O directly implies p + +o0. For showing - 1- - we only need to apply (c) Lemma A.5 which shows this when -
Lemma B.6. For all >> lo.
for G(x) = -
o' g'loo u)²
G(I/((0)) 2 (1o) 2/ (a)
Jayechs) gllo 2-2-2/E du.
Therefore, L(t) - 0 and ptt) to0
Proof for Lemma B.6 By Lemmal
I.3
and Theorem
B.4
dC
d0
2
d0
2
v(t)2
_
dt
dt
di
p²
2
B.5 to lower bound v and replacing P with (o(log - 1/L
Using Lemma we have
by the definition of 7
dL
(9llog 2) 2 I??
2
(
7())
2/L.
g(log 2 2
g'oog (
1) (1((00
1.77(to)21L
g oloog 22² C,
dt
g(og t)
where the last inequality the monotonicity of 5. So the following holds for ae. 2 to.
g'(log +) d L2)((t) g(log 2)2-2/1.
dt L
Integrating on both sides from to to f, we can conclude that
G(1/C) (2) 2/ to)-
Note that L/C is non-decreasing. If 1/C does not grow to +oo, then neither does G(1/C). But the RHS grows to +oo, which leads to a contradiction. So -
To make L + 0, Jmin must converge to +00. So p +0c.
C CONVERGENCE TO THE MAX-MARGIN SOLUTION
In this section, we analyze the convergent direction of and prove Theorem A.8 and A.9 (A1), (A2), (B3), (B4) mentioned in Section A
assuming
We follow the notations in Section define p = ||0||2 and 0 we view the functions of 0 as functions of
[|0]|2 E Sd-1 and sometimes
C. PRELIMINARIES FOR KKT CONDITIONS
We first review the definition of Karush-Kuhn Tucker (KKT) conditions for non-smooth optimiza- tion problems following from (Dutta al. 2013).
Consider the following optimization problem (P) for x E Rd. min f(x)
In (x: 50
Vn [N]
where f. gi....... In Rdd + R are locally Lipschitz functions. We say that æ E Rdd is a feasible point of (P) if satisfies 9n (m:) & 0 for all n E [N].
21

---

Published as a conference paper at ICLR 2020
Definition C.1 (KKT Point). A feasible point of is KKT point if æ satisfies KKT conditions: there exists Ag...., AN 2 such that
1. 1.0E0S EnE(Ny An On (a));
2. Vn [N] (n) O.
is important to note that a global minimum (P) may not be a KKT point, but under some regularity assumptions, the KKT conditions become necessary condition for global optimality. The regularity condition we shall use this paper is the non-smooth version of Mangasarian-Fronn Fromovviz Constraint Qualification (MFCQ) (see, c.g., the constraint qualification (C.Q.5) in (Giorgi et al. 2004
Definition C.2 (MFCQ). For a feasible point a of (P), (P) said to satisfy MFCQ at æ if there exists F such that for all n E [N] with On (x) = O,
vh E 0 (x) (h, v) 0.
Following from (Dutta et al. 2013), we define an approximate version of KKT point, shown below. Note that this definition essentially the modified <-KKT point defined their paper, but these two definitions differ in the following two ways: (1) First, in their paper, the subdifferential is allowed to be evaluated a neighborhood of æ, so our definition is slightly stronger; (2) Second, their paper fixes 8 = e², but in our definition make them independent.
Definition C.3 (Approximate KKT Point). For e, 8 > 0, feasible point of (P) is an (c, 8K-KKT point if there exists An 2 0, & E 0. f(x), hn E 8 gn (x) for all [N] such that
1. le EmE(N] )nhn(ar) Se:
2. Vn E [N] Angn(()) (x) 2 -5
As shown in (Dutta et al., 2013), 5KK point an approximate version of KKT point in the sense that a series of (c, TKT points can converge to a KKT point. We restate their theorem in our setting:
Theorem C.4 (Corollary of Theorem 3.6 in (Dutta et al. 2013 Let {ax E Rd : Ný be sequence of feasible points of (P), {ek > 0: k NJ and (On > O k E N} be two sequences. ap is
an (ek, 0g) KKKT point for every k;, and ex 8z If xx + as k too and MFCQ holds at I, then x is KKT point of (P).
C.2 KKT CONDITIONS FOR (P)
Recall that for homogeneous neural network, the optimization problem (P) is defined as follows:
min ク/ 1
s.t. gn (0) 2
Vn E [N]
Using the terminologies and notations in Appendix C.1 the objective and constraints are f(x)
|| and (x) = gn (x). The KKT points and approximate KKT points for (P) are defined as follows:
Definition C.5 (KKT Point of (P)). feasible point 0 of (P) is KKT point if there exist A1
AN such that
0 MN' A, for some hy...., by satisfying h E (0);;
2. Vn E [N] (n.
O.
Definition C.6 (Approximate KKT Point of (P)). A feasible point 0 of (P) is an (e, 8)K point of (P) if there exists Ai...., Av 2 0 such that
0 En An Antin
<e c for some hi,..., by satisfying hn 3 g.))n())
22

---

Published as a conference paper at ICLR 2020
2. Vn [N] An (g) 8.
By the homogeneity of it is easy to see that (P) satisfies MFCQ, and thus KKT conditions are first-order necessary condition for global optimality.
Lemma C.7. (P) satisfies MFCQ at every feasible point O.
Proof. Take v = 0. For all n E [N] satisfying 9n = 1, by homogeneity of In.
(v. h) Lq, (0 L 0
holds for any h E (0) 00 9n (0)).
C.3 KEY LEMMAS
Define ((t) = 40
0 dt to be the cosine of the angle between and d0 Here B(t) is only dt
defined for a.e. > 0. Since On is locally Lipschitz, it can be shown that on is (globally) Lipschitz on the compact set 8d-1 which the unit sphere Rd. Define
In pr
O Rd {101]
B. sup
[n 0 E s <0.
= ssu
|1
B = sup
Rd (0). h E 0 ga, n E [N]
pb-1
sup { [1/]11 0 E E 8 qn n E [N]] <0.
For showing Theorem A.8 and Theorem A.9
we first prove Lemma C.8 In light of this lemma,
aim to show that 0 is along the direction of approximate KKT point, only need show 3 + 1 (which makes - 0) and L 0 (which makes 5 - 0).
Lemma C.8. Let C1, C2 be two constants defined as
V2
2eNK2 L7(10)2/L
B1
log, K
C
C2
VL
(to)
where K, by are constants specified in (B3.4). Iflog 1/2 2 by at time t > to then 0 = 0//min (0)2/L is an (e, -KKKT point of (P), where = Ci vI B and 5 = C2/ 1
Proof. Let h(1) = di (1) for ae. 1 1> O. By the chain rule, there exist hI...., hv such that hn E 0mqn and h EnEin e ((9)) f'(g,) Let hn hn An/91-1/L4 0% (0) (Recall that = 0/ gmin (0) Construct An == Umnn 1-2/1
p p.e -1an) (q [|hll2- Now we only need to show
N
hn
5
(1-3)
(12)
52/6
n=1
2
2eNK2
B
log, K
An (q.
1)
(13)
TAPTL
f(5p2))
Then Ō can be shown to be an (e, 0KK point by the monotonicity 7(t) 2 7(to) for t to.
Proof of
From construction, ΣN Snh,
Immn
-1/E
ph/ ||h||g So
0
An
Amin
2/L
p²
0
[hl/2
h
9min
2/
22 2,8) 5 7
2
(1 B),
where the last equality is by Lemma
A.5
23

---

Published as a conference paper at ICLR 2020
Proof for 13
According to our construction,
N
2
N
Σ
(0) - = Imin
[(a)) f (4n) amin).
h
n=1
n=1
Note that | 2 h, 0) = Lv/p. p. By Lemma B.5 and Lemma D.1 we have
g(og 2),
log L
1
L> ((ipt) ((mmm))
1 2K
g g'(log tt)
2K
where the last inequality uses 1(5x²)) - =log 2 and L 2 e- ((1mm))) Combining these gives
(0) 1) 2mi Lf(5pb)
2/L 2 qmin P
e (lmin))-laa) flan) (gnn)( 9min).
n=1
On > Amin= then by the mean value theorem there exists En E (Amin 4n) such that f(4x) ('mmi)) = f('(E) (Qmin). ). By Assumption (B3.4), we know that I ('(x) I K (llogalom/Sw) ('((n)
Note that [log2(9n/ /5m) logg(2Bip /qmin) S logz (2B1 Then have
Σ Am (0) 11)
2K Umi
2/ p²
K (2..2(2B.19))
Σ
C-I'(S)(en-- (min) ((sn)))) qmin)
Lf(3p')
9n Amiin
2K5-2/11 Lf(5p²))
K (281/12 Ne
where the second inequality uses Ymin p² S 5- by Lemma A.5 and the fact that the function
2/L
2xx (0, +00) attains the maximum value at x 1.
By Theorem A.7 we have already known that C + 0. So it remains to bound B(t). For this, we first prove the following lemma to bound the integral of (().
Lemma C.9. For all to > 2 to.
12 (6(7)-2 -1) log p(T) dr S I log 5(22)
dr
5(t1)
Proof. By Lemma B.4
d
log
1 de² 20² dt
Lu r
for a.e. <> 0. By Lemma B.1 for / E (41,
de
d
p² d0
log 2 L.
log
(14)
di
Tv dt
dt
By the chain rule,
de dt
= (I T
de di
So we have
p² dē
Iu(1) -11-00 00T)
d0
40
d0 2t
0
3-2
1
(15)
Lu di
where the last equality follows from the definition of B. Combining 14 and
15 we have
dt log 9 I. (B-2 1) log p.
Integrating on both sides from & to t2 proves the lemma.
direct corollary Lemma C.9 the upper bound for the minimum 3 within a time interval: Corollary C.10. For all t2 t to. then there exists E (t,, 12) such that
1 log (t2) - 7t1))
- L log p(t2) log p(t1)
24

---

Published as a conference paper at ICLR 2020
Proof. Denote the RHS as C. Assume to the contrary that 8(r) C' for a.e. (21, By
Lemma B.1 ((T) > 0 for a.c. T E (f1,t2). Then by Lemma C.9 we have
1
(t22 (61)
f
d dr
log p(T) dr C. (log log p(t))) log (t22)
1
log
C.
L
L 7(11)
which leads contradiction.
In the rest of this section, we present both asymptotic and non-asymptotic analyses for the directional convergence by using Corollary C.10 to bound (().
C.4 ASYMPTOTIC ANALYSIS
We first prove an auxiliary lemma which gives an upper bound for the change of O.
Lemma C.11. For a.e. t > to.
d6
B1
d
log
dt
L
dt
2
Proof. Observe that
db
(I
00
do
2 - d0 It is sufficient to bound || de 01l By
de
2
de
the chain rule, there exists h hN [0, +oo) + RRd satisfying that for a.c. > 0, h. (t) E qr
and de = EnnENN) - ((a)) (1 hn (l). By definition of Bi, || 122 B1ph-1 for a.e. So
we have
d0
f(aa) f'(yx) 1/
di
1 -ipt-1
On
nE[N]
Note that every summand is positive. By Lemma A.S On is lower-bounded by qn 2 qmin g(log 2). so we can replace In with g(log 2t in the above inequality. Combining with the fact that EneiN e -f(a) ('(gn) is just v, we have
d0
V
Biph-1
B₁ 7p
(16)
dt
glog 2
So we have
AP Zf
B
L
B LA
log
dt
To prove Theorem
we consider each limit point 0 0/qmin (0) and construct series of ap- proximate KKT points converging to it. Then 0/qmin (0) can be shown to be a KKT point by Theorem C.4 The following lemma ensures that such construction exists.
A.8
Lemma C.12. For every limit point 0 of (t))) :t 2 o). there exists sequence of {tm : m N) such that fm t +00, (t.m. + 0, and ((tm) + 1.
Proof. Let {em > 0: N) be an arbitrary sequence with em + 0. Now construct {tm) by induction. Suppose t < t2 < ... < tm-1 have already been constructed. Since a limit point and (t) 1 7oo (recall that 700 = lim, 20 (t)), there exists 8m > fm such that
[0(mm) 0|13 S <m and
1
7o0 < 6m
log (8m) I.
Let s'm Sm be time such that log p(s log p(sm) + cm- According Theorem A.7 log, + +00, so s',, must exist. We construct f., E (sm, s'm) ) to time that (t...) S c
where the existence can be shown by Corollary C.10
25

---

Published as a conference paper at ICLR 2020
Now show that this construction meets requirement. It follows from ((tm) - 1 2n that 3(tm) 1/v + 2n By Lemma C.11 also know that
|(((.) 0 < ((mm) - ((sm)) (smm)] + 0((mm)) - 0 S
B1 (F((t)
6m +em - 0.
This completes the proof.
Proof of Theorem A.8 Let 0 0/gmin (0) for short. Let (lm E N) be the sequence
structed as in Lemma C.12 For each lms define e (lm) and o(4m) as in Lemma C.8 Then we know that (tmm)) quainnntnntnn 1/L is an (c(fmm), (((tm))((tm))) ((fK)) point and (t (ffm)/ol //mn) (fm 177 0 (tm) +
5(mm) By Lemma C.7 (P) satisfies MFCQ. Applying Theorem C.4 proves the theorem.
C.5 NON-ASYMPTONIC ANALYSIS
30e Proof of Theorem A.9 Let Co 1 log 5[6]]
Without loss of generality, assume < LG Ci
and C2/f(by)
Let be the time such that log p(1) 1 log a(C28-') Ollog 0-1) and l2 be the time such that
7(ta)
log p(12) - log p(4) = CoCCf = ( 2). By Corollary C.10 there exists L, E (41, (2) such that ((t.)= 15 CT
Now we argue that ((t.) an (K point. By Lemma C.8 we only need to show C-vI- 3(1.) S e and C2/I((((4)p(())))) < 8. For the first inequality, by assumption < /6 we know that ((t.)= - < 3, which implies 18(t.)] 3/2 Then we have 1 B(t.) I s(t.)²
2 C1,
20² 1+3(1.] I 3C0 Therefore, C1 CIVI 3(t.) S holds. For the second inequality, ((t.)p(t.)+ 2 5(t.). a(Co5-1 1(C25-t), Therefore, C2/S(((()))(()))) s 8 holds.
7(ta)
C.6 PROOF FOR COROLLARY 4.5
By the homogeneity of qn. we can characterize KKT points using kernel SVM.
Lemma C.13. O, is KKT point of (P), then there exists h. E Q ( (0.) for n E [N] such that 0. is optimal solution for the following constrained optimizution problem (Q):
min 1
s.l. yn (0, hm) 21
Vn E [N]
Proof. is easy to see that (Q) is a convex optimization problem. For 0 = 20.. from Theorem B.2 that yn (0, h,) 2q, (0.) 2 1, which implies Slater's condition. Thus, we only need to show that 0. satisfies KKT conditions for (Q).
By the KKT conditions for (P), we can construct hn E 00 for n e [N] such that 0. EN Anyn hn for some λ1 AI. AN 2 O and An (0.) - 1) = Thus, 1. 0, satisfies
1. 1 - - I, An. = 0:
2. + (yn (0,, hmn) 1) = An (0) - 2 O.
So 0.. satisfies KKT conditions for (Q).
Now we prove Corollary 4.5 Section
Proof. By Theorem A.8
every limit point 0 is along the direction of a KKT point of (P). Combining we know that every limit point 0 also along the max-margin direction
this with Lemma C.13 of (Q).
26

---

Published as a conference paper at ICLR 2020
For smooth models, h, in (Q) is exactly the gradient V4 (0). So, (Q) is the optimization problem for SVM with kernel Kg (a x²) ( (n)) ~. (0)). For non-smooth models, we can construct an arbitrary function h(x)) E 0 (0) that ensures h( hn Then, (Q) is the optimization problem for SVM with kernel ( x²) = (h(z), h(x)))
D TIGHT BOUNDS FOR LOSS CONVERGENCE AND WEIGHT GROWTH
In this section, we give proof for Theorem A.10 which gives tight bounds for loss convergence and weight growth under Assumption (AI), (A2), (B3), (B4).
D.1 CONSEQUENCES OF (B3.4)
Before proving Theorem A.10 we show some consequences of (B3.4).
Lemma D.1. For f()) and g(-). we have
1. For all +00), a(x) (((x)
2Kr];
2. For all y E (o(bb), +20),
flv)
DK V, 2Ky) v).
Thus, g(x) (xzg((())) f(v) = Ou)
Proof. To prove Item 1, it is sufficient to show that
g(x) = b, + Sr g'(u)du 2 (" {(u)du
x/2
g(xx)
2 (x/2)
=xg((r) (x).
xg
K
2K
x x= f(b/) '
f'(((z))
g'(u)du
s(b,)
K
flata)/2)
((((())
g(x)
= (g(x)/2))
K
2K
g'(x)
To prove Item 2, we only need to notice that Item iiplliss (f for all y E (g(b,), +oo).
(((r())
o((())
E
| f f()) 2K f())
Recall that (B3.4) directly implies that ('()(z)) = e()'(x) and ('(O(x)) = (z)() Combin- ing this with Lemma D.I we have the following corollary:
Corollary D.2. (z)) = (z)()) and g(O(z)) = (g)(z))
Also, note that Lemma D.I essentially shows that (log f(x))' = (1/z) and (logg(z)) 0(1/x) So log fxx = Olog z) and log (=) = O(loga), x), which means that f and g grow at most polyno- mially.
Corollary D.3. f(x) 0(1) and g(x) 0(1)
D.2 PROOF FOR THEOREM A.
8d-1, and sometimes we view the functions of 0 as functions of And we use the notations Bo B₁ from Appendix C.3
We follow the notations in Section define p = ||0||2 and Ô T0l
The key idea to prove Theorem Theorem/A.10ia to utilize Lemma B.6 in which C(t) is bounded from above by δ ((()). So upper bounding C(t) reduces to lower bounding G-1, In the following lemma, we obtain tight asymptotic bounds for G(-) and C-)(
27

---

Published as a conference paper at ICLR 2020
Lemma D.4. For function G(-) defined in Lemma B.6 and its inverse function G (-), we have the following bounds:
G(x)= - (9(10gz))/4 and G (y) = (log (logr))² x:)2
(
(log y)²
( ((
Proof.
We first prove the bounds for G(z), and then prove the bounds for G G
Bounding for G(x)). Let Co = papp(hg) of (log
11/((t)) atlox a)² du. For x 2 exp(bg):
G(x) = Ca -
g' d'(oguu) u)
(esp(es) gllog 1)2-2/t du
( g'(log u) log glog u)
(log u/a/L du, (log u)²
CG
eexp(ba)
By Lemma D.1
f eep((b.) (logu)² du
[g(log x/22 (log (logx)²
((z) 4K g
On the other hand, for cxxp(2b)) have
g(log u) 2/2
(log u)² du > g((log ((log.x//2)//b
(log u)² du Ω g(log 22) (log 22)2 v
G(x) 2 4K2
4K2
Bounding for G Gy). Let G for y 2 0. G(x) always has finite value whenever finite. So x to0 when y + too. According to the first part of the proof. we know
that y θ glogg=)2/4
Taking logarithm both sides and using Corollary D.3 have log y O (log x). By Corollary D.2 g(logy) g(O(log x)) O(g(logx)) Therefore.
(log ()og 20)
(log y)
(log x)² g(og [[(log))//()) = O(z).
e
g(log y) 2)
This implies that θ
(log v)² gllog 1
For other bounds, we derive them as follows. We first show that glog () equivalence, we derive upper bound for the gradient at each time & in terms of L. and take an integration to bound C(t) from below. Now we have both lower and upper bounds for C(t). Plugging these two bounds to g(og }) O gives the lower and upper bounds for p(t).
0(p²). With this
Proof for Theorem A.10 We first prove the upper bound for L. Then we derive lower and upper bounds for p in terms of C, and these bounds to give a lower bound for L. Finally, plug in the tight bounds for L to obtain the lower and upper bounds for in terms of t.
Upper Bounding L. By Lemma B.6 we have & 2 G-1 (S()).. Using Lemma D.4 we have = Ω
1)og g(og t)
) which completes the proof.
Bounding p in Terms of C. 7(t) 2 7(to). so p² 3 g(ogg( +) = Ogg(log f)). On the other hand, g(lg 2)) S Jmin I Bopt. So pt S(g(log 11). Therefore, have the following relationship between p² and g(oog 1):
o² O 1 )).
(17)
28

---

Published as a conference paper at ICLR 2020
Lower Bounding L.
Let h hy be set of vectors such that h,
0ga. and
d0
f(an) (ggn))..
dt
By (17) and Corollary D.2 (ga) )(((p))) M'OO Ł))) (g Ł)))
( (log 2)). Again by (7),, we have |lhnl22 _ B1ph-1 = Ogg(log - Combining
these two bounds together, follows from Corollary D.2 that
[[(log t) ) 1111//
=0 0 ( log +
(gn) |1all2 =0
g' g'(log ))
g 2
Thus,
d.
d0
Σ - faam (gn))en
dt
dt
(log 1)²
Σ
((mm).
((aaa))lanl [E(N]
5²² 0
(g 1/2/z
By definition of G()), this implies that there exists constant e such that 4 (G for any L that is small enough. We can complete our proof by applying Lemma D.4
Bounding P in Terms of t. By (ggOOlo 1))). Using Corollary D.2 we can conclude that p² = O(g(log
and the tight bound for C(t), p² (gg(lo k)
E GRADIENT DESCENT: SMOOTH HOMOGENEOUS MODELS WITH EXPONENTIAL Loss
In this section, we discretize our proof to prove similar results for gradient descent on smooth ho- mogeneous models. As usual, the update rule of gradient descent is defined
0(l + 1) = (()) - ((()V
(18)
Here (t) is the learning rate, and V CC(t) (()(t)) is the gradient of L at O(t).
We first focus on the exponential loss. At the end this section (Appendix F). we discuss how to extend the proof general loss functions with similar assumption as (B3).
The main difficulty for discretizing our previous analysis comes from the fact that the original ver- sion of the smoothed normalized margin 7(0) p llog & becomes less smooth when p +oo. Thus, if we take a Taylor expansion for 70(( + 1)) from the point (()), although one can show that the first-order term is positive in the gradient flow analysis, the second-order term is unlikely to be bounded during gradient descent with a constant step size. To get smoothed version of the normalized margin that is monotone increasing, we need to define another one that is even smoother than 7.
Technically, recall that de -/V does not hold exactly for gradient descent. However, the smoothness can be bounded by s(t), then it is well-known that
L(t + c(t) < (1) ((()))))))))))
By analyzing the landscape of L, one can easily find that the smoothness is bounded locally by O polylog( 2)). Thus, if we set 77t) to constant or set it appropriately according to the loss, then this discretization enror becomes negligible. Using this insight, define the new smoothed normalized margin f in a way that increases slightly slower than ř during training to cancel the effect of discretization error.
29

---

Construct the first-order derivative of Published as a conference paper at ICLR 2020
E. ASSUMPTIONS
As stated in Section 4.1 we assume (A2), (A3), (A4) similarly as for gradient flow, and two addi- tional assumptions (ST) and (S5).
(S1). (Smoothness). For any fixed æ, 4 ( (x) is -mooth on R (0).
(A2). (Homogeneity). There exists L > 0 such that Va > 0: #(a0:z) = a 2(0x);;
(A3), (Exponential Loss). {(g) = e=;
(A4). (Separability). There exists time to such that (()(())) <.
(85). (Learing rate condition). E1zo (tt) too and 17(1) - H(C(0())).
Here HCC) is function of the current training loss. The explicit formula of H is given below:
((xx) θ
1
H(x) == C₂,(2))
(1log 3)3-2/1.
where C is constant, and x(x), ((x)) are two non-decreasing functions. For constant learning rate (4) = loo (S5) is satisfied when Yoo if sufficiently small.
Roughly speaking, (2)(()) is upper bound for the smoothness of L in neighborhood of 0 when (()). And we set the learning rate ntt) to be the inverse of the smoothness multiplied by
factor µ(z)) o(1). In our analysis, u(x) can be any non-decreasing function that maps (0, C(t))]
to (0, 1/2] and makes the integral Jo /1/ p(x)dr exist. But for simplicity, we define μ(() as
log Z(1o
u(x) = 2 log 1
log
The value of Cn will be specified later. The definition of k(x) depends on L. For 0 < L S 1, we define x(x)
1
2-2/L
<(x)= loo
For L > 1, we define x(r) as
(log 2) 2-2- Amax
a E (0, 2/L-2
x(x)
a E (62/L
where Fmax == (2-2//)(t((222/1D))) The specific meaning of C, M(x) and p(z) will become clear in our analysis.
E.2
SMOOTHED NORMALIZED MARGIN
Now define the smoothed normalized margins. As usual, define 7(0) log time, we also define
At the same p
el(2)
(0) = ph
Here ò (0, ((to) + (0, +oo) is constructed as follows. ((x) as
1 + 2(1 + X(w)/L)a(w) ww E [x, 2(to))
d'(x) = sup
w wlog i
where A(x) = (log 1 11 And then we set ((z) to be
=)-1,
d(x) log log - 1' (d'(w) w log
dw.
can be verified that d(x) is well-defined and (x(x) is indeed the first-order derivative of 6(x). Moreover, have the following relationship among 4, 7 and
30

---

Published as a conference paper at ICLR 2020
Lemma E.1. ((0) is well-defined for L(0) I [tto and has the following properties:
(a) If ( [(to), then (0) (0) S (())
(b) Let (0m R m E NJ be sequence of parameters. If [(0m) 0, then
5(0m) = 1 - -0 ((10s [(0m.
- 1.
7(
Proof. First verify that y is well-defined. To see this, we only need verify that
((x)= :0)==/ 1- [d((w))+
+ log dw
exists for all E (0, ((to),, then it is trivial to see that (w) indeed the derivative of ((w) by ('(x) (x)) log
Note that [xx) exists for all x E (0, [(t)) long as [(x) exists for small enough > 0. By definition, is easy to verify that r(w) == 142(1+ 1 (L)y)))) is decreasing when w is small enough.
log
Thus, for small enough > 0, we have
1 + 2(1 + 7, (log +1
-
log 20rel log
2 (1 + + - log Z(To)
1
-d(ww)= r(w)
w log
w log
(log )
So we have the following for small enough x:
((x) = L/- log 1
c(1)) (1 1. (log 1) w(log )
dw log [(to)
log I
1 })² 2L
w
log 1
(19)
[(to)
log 2L 1)²
This proves the existence of (x).
Now prove (a). By Lemma A.5 70) (0). we only need prove that (()) (0).
To see this, note that for all w (to)), r(w) > log r. So we have - (w) > wlog T. and this
implies (xx) < 0 for all x < Ltto). Then holds for all with C(0) S (too that
(0))
((C())
log log ziol +I(C(0))
((C(O)) < 0.
(20)
log Z(O)
Jog log ziv)
To prove (b), we combine
19 and 20), then for small enough C(Om). we have
(0)
(0)
(0)
70)
70)
70)
log 2
exp
log C(to)
log c(D.))
2L c(o...)
Jmin (0..)
log Z(O...
exp
log Z(0m)
log Z(0m)) + 0(11)
1 (108 L(7m)
So 500)
- 0 ((dmm + 1.
500
31

---

Published as a conference paper at ICLR 2020
Now specify the value of Cy- By (S1) and (S2), we can define Bu, B1, B2 follows:
Bu sup {9r- 0 s n E [N]]
B == sup Vll E S ,n [V]]
B2 = sup V 4m 0 80-1," .nE [M]]
Then set CG :- (B} + p(t)))=B1)) min
( 2+2/L Bo 2+2/L
E.3 THEOREMS
Now we state our main theorems for the monotonicity of the normalized margin and the convergence to KKT points. We will prove Theorem E.2 in Appendix E.4 and prove Theorem E.3 and E.4 in Appendix E.5
Theorem E.2. Under assumptions (SI), (A2) (A4), (85), the following true for gradient de- scent:
1. For all t 2 to, 7(t + 1) 2 (t)):
2. For all t 2 to. either 7tt + 1) (t) 0ct + Ō(t);
3. C(t) 0 and p(t) + xc as + too; therefore, 15(() -(() + 0.
Theorem E.3. Consider gradient flow under assumptions (SI), (A2) (A4), (S5). For every limit
point 0 of ( :t 2 0). 0/ 9quin((0) 1T. is a KKT point of (P).
Theorem E.4. Consider gradient descent under assumptions (SI), (A2) (A4), (S5). For any e, > there exists y := Olog 5 5-1) and A = O(c=²) such that 0 8/qmin (0) 1/T. is an (c, (KK point at some time satisfying log p(l.) (r,r+: A).
With a refined analysis, we can also derive tight rates for loss convergence and weight growth. We defer the proof Appendix E.6
Theorem E.S. Under assumptions (SI), (A2) (A4), (S5), have the following tight rates for training loss and weight norm:
L(1) θ
T(log 2/1 and p(() O((lg 2)
where T Ei=1 T(T).
E.4 PROOF FOR THEOREM E.2
We define v(t) = DN (t01 (t) as we do for gradient flow. Then we can get closed form for (0(1), VL)) easily from Corollary B.3 Also, we can get a lower bound for v(t) using Lemma B.5 for exponential loss directly.
Corollary E.6. (0(t). VC(t)) Lv(t). C(t) 1, then v(t) 2
(() X(OO
As analyzing gradient descent, the norm of VL and V appear naturally in discretization emror terms. To bound them, we have the following lemma when (0) and p(0) have lower bounds:
Lemma E.7. For any 0, if (0) 2 ((to), 2 p(to), then
(2()) N (CC) and | 22C,)(((0)).
32

---

Published as a conference paper at ICLR 2020
Proof. By the chain rule and the definitions of B1, B2, we have
N
S SLpt-1B B1
n=1
2
| -
Σ
(n Van - (2qn)
N
Σ
4n (B}p21-0 + BBp S Lp2 (B} + -Be).
Note that ²( < 5pt < log 2 S Bopt So f(1))) log 2 S pt S Bo log z.2 Combining all these formulas together gives
| & BJ min { -442/L, Bo 2 C2 Bo0 1)) 2-2/2
S 220g1o(D)C
C)
2-2/1.
| = (B² + + min { (f(60)-2+112 2+2/L, BB 2
c.
log 2
S (C,
which completes the proof.
For proving the first two propositions in Theorem E.2 we only need to prove Lemma
E.8
(
a lower bound for 7. (P2) gives both lower and upper bounds for the weight growth using v(t). (P3) gives a lower bound for the decrement of training loss. Finally, (P4) shows the monotonicity of f and it is trivial to deduce the first two propositions in Theorem E.2 from (P4).
Lemma E.8. For all t to, to + l...., we interpolate between O(t) and O(t + 1) by defining Ol a) = O(() ((()) for E (0,1). 1). Then for all integer t 2 to. vl) 0, and the following holds for all a E [0, 1]:
(PI). 7(1 + > (ln).
(P2). 2Lon(t)u(t) S p(t + -00++))2-p())) p(t) s (Lan(t)v(t) (1+ MCCO)a(c())
(P3). C(t + - L(t) S -an(t)(1 - ((C(E))
-() La(p ( (T- V log p(t-a)
(P4). log (tt + a) -lg (t) 2
p())
To prove Lemma E.8 we only need to prove the following lemma and then use an induction:
Lemma E.9. Fix an integer T 2 to- Suppose that (PI), (P2), (P3), (P4) hold for any t + a S T. Then if (P1) holds for (t, a.) E {T' [O, for some E (0, 1], then all of (P1), (P2), (P3), (P4)
hold (t) E (T) x A).
Proof for Lemma E.8 We prove this lemma by induction. For t = tu, a = 0, v(t) > 0 by (S4) and
Corollary E.6 (P2).
(P3), (P4) hold trivially since log f(t + a) = log (t), L(t + a) L(t) and
log (t + +a)= = log ((). By Lemma E. (P1) also holds trivially.
Now we fix an integer T 2 In and assume that (P1), (P2), (P3), (P4) hold for any L + < T (where
t 2 4o is an integer and a E [0, I).. By (P3), L(t) S L(()) < 1, so v(I) > 0. We only need to show that (P1), (P2), (P3), (P4) hold for = T and a E [0, 1].
Let A = ia E [0, a = or (P1) does not hold for (T, a)). If A = 0, then (PI) holds for (T, A) since (PI) holds for (T 1, 1); if A > 0, we can also know that (PI) holds for (T, by
Lemma E.9 Suppose that A < 1. Then by the continuity of (T + a) (with respect to a). we know
that there exists A' A such that 5T + a) > (tt) for all a E [A, which contradicts to the definition of A. Therefore, A = 1. Using Lemma E.9 again, we can conclude that (PI), (P2), (P3),
(P4) hold for = T and a E [0, 1).
33

---

Published as a conference paper at ICLR 2020
Now turn to prove Lemma E.9
Proof for Lemma E. 9
Applying (P3) on (t, at) E {to...., T 1 x 1, we have [(t) < [(to) < 1.
Then by Corollary E.6
we have v(t) O. Applying (P2) on (t, E {lu..... - X 1, we can
get p(t) 2 p(to).
Fix T. By (P2) with a (0, and the continuity of % we have 7(t + A) 2 (to)). Thus, 7t + a) 2 f(to) for all a E A].
Proof for (P2). By definition, p((+a)}2 [(()) ((0 (V
20m(() (0()). VL()). By Corollary R.6 we have
pll + a)² p(1)² (2) +lamm)))
2Lom())v(().
So p(t + a²² p(t)2 (L)n(t)v(t). For the other direction, we have the following using Corol-
lary E.6 and Lemma E.7
p(t + a)² - p(t) = 2Lan(t)u(t)
1+
2Lv(t)
C71"(C())=~ (C
I 2Lan(()u(1)
1
2LL())C()))
= 2Lan(t)u((t) (1 M((())
Proof for (P3). (P3) holds trivially for 0 or VL(() 0. So now we assume that a * 0 and
VL(() * 0. By the update rule (18) and Taylor expansion, there exists & E (0, such that
C(t + a) [(t) (0(t + a) VL()) (0 -()) () 0()))
1 ク 2 (1)) [ (11((1))))
[(t) on(()) [()(
C(t) an)( (1 (1- an(t)) V C(t + 5)1b) |V((())
By Lemma
R.7
1 + 1)122 s 20, <(((t + E)), so we have C(t + a) - C(t) an (1 aC,, aCnm(())(((tttttee.aa) + ()) (V
(21)
Now we only need to show that L(t a) L(t) for all E (0. Assuming this, we can have k(C(t + E)) S x(((t)) by the monotonicity of k, and thus
C(t + a) s C(t) an)(t) (1 (C())) - L()) - anl(1) (1 --((()()))))))))))))))))((())()) IV((0) [V
< C(() for a E A). Assume to the contrary that ag == inl E A0 A) L(l + a') > [(I)) exists. If af = 0. let p: [0, + R + L(l a), then p0) limajo ((++a)-((() 2 but it contradicts to p0() =-n(t) [VC(t)] < op > 0,
Now we show that C(t + a)
a then by the monotonicity of k we have k(L(t {)) < x(((t) for all & ao), and thus
C(t a) < C(t) an(() (1 ((C(t))) [I (V((((()))) C(t).
which leads to contradiction.
Proof for (P4). define v(t) ((t))()) and u(t) (I ([-())(((T)(--vc() similarly as in the analysis for gradient flow. For v(t), we have
1 ||x())] p(t) (t(t) -((t) p(t) Lv(t).
34

---

Published as a conference paper at ICLR 2020
Decompose [[((()) || + ||u(()]1 Then by (P3), we have
C(t+ C(t) - (1n(t) m((((t)) ( 1
((t))> -
+ +12112]
Multiplying 4+MCC)))(CCO)) on both sides, we have (1-M(C(0)))(()
1 + X(C(O))(C(0))) (1 (MM((()))U(t)
sam(() (1+ A(C(O))(C(O)) E.6 we can bound v(t) by v(t) 2 ((t)/M((()) By (P2), we have the inequality
L'v(1)) o(t)2
|
L
v(t)
By Corollary
(1)(()(1 (1+ A p((+a)² -p(t)) So we further have
2L
1 + X(C(E))(CCO)) (C(++a)-((t) - (1 ((CO))C()XXC))
p(1)2 0(1)2 ( (
1
2 2Tx(1)2 11u11
p(t)
From the definition o. it is easy to see that -o'(L(t)) 2 14NC11)0C0001 Let = log x.
then v (z) Combining these together gives
(((()) + ((1) + + (o000))))((++ p(1)3) (4 + p(t)2
(Tv(()2 | 20
Then by convexity of Φ and vb we have
-(((() ({(())) + log p(t + ax) And by definition of ?, this be re- re-written as
log
1
(t) l1ue13 2 0
p(t)²
p(t)3
lt + a) loog (t) (Ø(C(t + a)) ((L(t))) + L log p(t+a) log 1
p(t)
1og p(l + az)2
log 1
(tv ||ua12
p(t)2
p(t)2
p(1)
p(t + a)
Lu(t)2 ||ul12 log
p(t)
Proof for (PI). By (P4), log (t + a) 2 log (t) 2 log (to). Note that ((x) 2 log log 4. So we have
7(t + a) > (t + aa) 2 (to).
which completes the proof.
For showing the third proposition in Theorem E.2
use (PI) to give lower bound for [[t]())
and use (P3) to show the speed of loss decreasing. Then it can be seen that L(t) + and p(t) + +o0. By Lemma E. we then have 1 31 0.
Lemma E. Let Eg L(to) 2(10) 2--211
2/1, Then for all > to.
E(C(t) 2 } L ( 2/L Σ T(T) 2
1
1-1
for E(x) = [
C(to)
du.
min(u?(log 2/2, Fng]
r=to
Therefore, L(t) + 0 and p(t) + to0 as +
00. 00.
Proof. For any integer t 2 to. ((((t)) < and VL(t)l, 2 ||u())]l2 Combining these with (P3),
we have
C(t+1) - L(t) < (t) [10 n20) - 122((1)2
1
p(t)²
35

---

Published as a conference paper at ICLR 2020
By (PI), p s ((to)2// (log [(0)
-2/L By Corollary E.6 v(t)2 2 L(t) (log zto)
Thus
have
2 2-2/L
(1++1) - n1(1) (24((1))/1 log
[(t)
easy see that
w=[log 2/² 27E is unimodal in (0, 1), Ex(x) is non-decreasing and E(x) is
convex. So we have
E(C(t + 1)) - B(((t)) (C(()) (C(++ L(t))
2-2/L
L(t) log 2(0)
2 20(0) 127(()))/LL.
min Z(T) 12-2/L, Eσ}
2 220(0) 127((1))11
which proves E(C(t)) 2 [tt 2/ (T). Note that L is non-decreasing. If L does not decreases to 0, then neither does EL)). But the RHS grows to -00, which leads to a contradiction. So C O. To make + Jmin must converge to +oc. So p + +00.
E.5 PROOF FOR THEOREM
E.3 AND E,4
The proofs for Theorem E.3 and E.4 are similar as those for Theorem A.8 and A.9 in Appendix
C
Define ((t) I
0, 10-VL(9 v(t) as do in Appendix C It is easy to that Lemma C.8
still holds if we replace (to) with (to). So only need to show L 0 and 8 - 1 for proving
convergence to KKT points. L + can be followed from Theorem E.2 Similar as the proof for
Lemma C.9
it follows from Lemma and (15) that for all tt f to.
(3(t)-2 1) log p(l +(1+1) 1 log (12) p(t)
S
(22)
L {(1))
Now we prove Theorem E.4
Proof for Theorem E.4 We make the following changes in the proof for Theorem A.9 First, we
replace ((o) with (to), since 7(t) (t 2 to) is lower bounded by (to) rather than (to)) Second, when choosing ( and f2, we make log p(t1) and log p(t2) equal the chosen values approximately with an additive error o(1), rather than make them equal exactly. This is possible because it can be shown from (P2) in Lemma E.8 that the following holds:
ptt + 1)² p(t)² = O(n(t)v(t)
p(t)²
= ((0)()))))--0)000)))000000 = (log z(()) 22-2/T
=(p(1)
Dividing p1) on the leftmost and rightmost sides, we have
p(t + 1)/p(t) = = 1 =(((())))+=))+++)
which implies that log p(t + 1) - log p(t) = o(1). Therefore, for any R, we can always find the
minimum time such that log p(t) > R, and it holds for sure that log p(t) R O R + too. Li
For proving Theorem E.3 we also need the following lemma as a variant of Lemma C.I1
Lemma E.11. For all 2 to.
|[ - -6(0 S
B [T(t)
p(t pt++1)
+1) log
p(t + 1)
p(t)
p(t)
36

---

Published as a conference paper at ICLR 2020
Proof. According to the update rule, have
Oct O +1 p(t 1)
1))+)))0())))
O(t)
p(l +
p(()
1
(10(C+1) - 0(1)112 + +|| ( +
-1 0c01))
p(t)
1(t+1)
p(t)
(())
[VC(()]l2 + (1 p(t +11
p(()
plt 1)
By 16 [V((()]2 <
Bra((t) 7(8)ptt)
So we can bound the first term as
(t()
B1 n(t)((t)
B1
Alt + -
p(t 1)) |[[(tt]12 - 7(t)
p(t + 1)p(t)
7(t)
2Lp(t + 1)p(t)
Bi pll + 1)2 p(1)2
p(l p(l +1)
21²(t)
p(t + 1)2
p(t)
B₁
1(t+1)
p(t + 1)
log
LR(1)
p(1)
p(()
where the last inequality uses the inequality a-b S log(a/b). Using this inequality again, we can bound the second term by
1 p(t)
p( +
S log
1) [ [(t 1) 6(t) 1
p(t)
Combining these together gives
p(++1) +1) log p(t) (G(() p(t)
B p(++1)
Now we are ready to prove Theorem
Proof Theorem E.3 As discussed above, we only need to show a variant of Lemma C.12 for
gradient descent: for every limit point of {((t) t 2 0 0). there exists sequence of {tm m N)
such that t.. 1 + (f.m. + 0, and (tmm) + 1.
We only need change the choices of sms s'm tm in the proof for Lemma C.12 fm-1 to be a time such that
We choose s.,.
lim
(tt)
[((mm)
81 cm and I log
+00
(sm)
Then we let s',, > 8m be the minimum time such that log p(s log ((mm) + Cm- According to Theorem E.2 8m and s'n, must exist. Finally, we construct t. {sm:.... s'm - -1} to be time that (lm)
2 where the existence can be shown by (22).
To see that this construction meets our requirement, note that B(tm,) 2
5 2 - and
((mm) - 01, < [(())) - (smm) ||- + [(sm) - 0 s [T((to)
B1
6m +1) cm + 6m + 0,
where the last inequality is by Lemma E.11
E.6 PROOF FOR THEOREM E.S
Proof. By similar analysis as Lemma D.4 we have
f(to)
1
du f/le θ
(log ()=22))-//1 (110 du
E(x)=
θ
uz u2og 2/2-2/1
2/T.
l//ctt))
I[log 1 1
37

---

Published as a conference paper at ICLR 2020
We can also bound the inverse function E (y) by g (1ogg))2-27 similar analysis Theorem AA. to prove Theorem E.5
With these, we can use a
First, using a similar proof as for (17), we have p (log t) So we only need to show C(t) =
O Tllog T1lg71)--77) With similar analysis as for (P3) in Lemma E.9 we have the following bound
for C(T [(T):
[ ? By Lemma E.7 (11-)--1)22--00---(((110
Using the fact that μ - 1/2, we have L(T [T + [(T) 2 ()((7)
[VL(T))le S (C)x((()))((T). Using similar proof as for Lemma E. can show that E(C(t)) & O(T). Combining this with Lemma E.10 we have E(C(t) (T). Therefore, [(t) O
F GRADIENT DESCENT: GENERAL Loss FUNCTIONS
It is worth that the above analysis be extended to other loss functions. For this, need to replace (B3) with strong assumption (S3), which takes into account the second-order derivatives of f.
(S3). The loss function {(g) be expressed {(g) -f(()) such that (S3.1). f: R is C²-ssoothh
(S3.2). f'(a) for all g E
(S3.3). There exists by 2 0 such that f'(g)q is non-decreasing for g E (by, +o0), and f'(4)q + to0 q + too.
(S3.4). Let g [s(by), +o)) + [b +oo) be the inverse function of f on the domain [by, to0). There exists 2 0 such that for all x > f(by),y by.
(x)x) g (x)
(" P f'()
and
y
It can be verified that (S3) is satisfied by exponential loss and logistic loss. Now we explain each of the assumptions in (S3). (S3.2) and (S3.3) are essentially the same as (B3.2) and (B3.3). (S3.1) and (B3.1) are the same except that (S3.1) assumes is C²-smooth rather than C'-smooth.
(S3.4) can also be written the following form:
d log f'()) dy
d log y.
log (x) S p-
log x and
S p-
(23)
dx
de
dy
That is, log (x: and log ('( grow no faster than O(lg x) and O(log y). respectively. In fact, (B3.4) can be deduced from (S3.4). Recall that (B3.4) ensures that O (x:) (O(z) and (v) = (O(()) Thus, (S3.4) also gives us the interchangeability between f',g and O Lemma F.I. (S3.4) implies (B3.4) with by = m2x
and K PP
Proof. Fix x E (by, +o0), E (g(b,), +o0) and 0 e [1/2, 1). Integrating 23 on both sides of the inequalities from fr and fy to y. have
blog (x) - logg'' (0x) < log 0 and [log ('v) - log ('00)) S log Ø
Therefore, have g (x) < p~ (0x)) s Kg (fx) and f'()) < 0 - K K
To extend results to general loss functions, need to redefine k<x), A(z), ((x) C.p H(x) in order. For x(x) and X(x), we redefine them as follows:
wloo 1 2/2-
X(x) = g' (log 1
x(x) = sup
w E (0,z)
g'(log 1
g(log !)
38

---

Published as a conference paper at ICLR 2020
By Lemma D.1
wollog 1/222/2 = O (w[log //-
10/22/1/99/ /g(log =) + O. So k(x) is well-defined.
g'oo 11²
Using A(z), we can define 6(x) and (0) as follows.
(ww)
(((x) sup
(1 + 2(1 + X(w)/L)
[xx, [(to)]]
w
<(x) = log g(log ))
/ (d(ww) + X(w) dw
((0) = c(((
pt
Using a similar argument in Lemma E. we can show that -()) is well-defined and ((0) <
(0) == g(log 2) I (0). When (
O, we also have (00)/((0)
For Cy. we define it to be the following.
C = 1 B1 ((FRe))
Bo
B1 + 2
(pB1 + BB) ( (2(6)) min { (5(to)-2+22) 222/L BB 2-22/
)
?
log E(to)
Finally, the definitions for pax)) (log zToo 1/ log )) and H(x) u(x)/(C,n(<x) in (S5) remain unchanged except that n(x) and C. now use the new definitions.
Similar as gradient flow, we define v(() == Σx e f' (1)) (t). The key idea behind the above definitions is that we can prove similar bounds for vtt,, C12,, 2 as Corollary E.6 and Lemma HV
Lemma F.2. (0(t). VV((t) = Lu(t). If) < e f(b)) then v(t)
and X(C(t) has the X((()
c(t)
lower bound X(C(t)) S 2 (log 2007)
Proof. It can be easily proved by combining Theorem B.4 Lemma B.5 and Lemma D. together.
Lemma E.3. For any 0, if (() < C(to), 2 (to). then
12) < (C)) and
|' S (C,xx((()))
Proof. Note that direct corollary of 23 is that (m(m)) ('( for x2 by. So we have
f'(gn) 8 ((l0g)) 2)) (
(g t)) )= g' o'oog +)
In
R
g gloog L)²
where R: = (Bo/ Applying (S3.4), we can also deduce that
pR [f"())] < P -. f((n)) S g(log (log 2)
In
Now bound || /Vl12 and || | g- By the chain rule, have
N
SB.. Lp g'loog t)
Σ
é [gn) f' Vqn)
N
|
Σ
(m))
((f'gg)² f" Van V - f' V2 qm))))
n=1
2
f(am)
R2 1)² (( g(log 2g 2)
(
pR
BR 21-2
R
Bap B2p"~2
g' (log 1)
C 2-
(R+ (R+))(L)) B² + g (log 2)
B2 R. ph
g (log 1)²²
39

---

Published as a conference paper at ICLR 2020
For p have (tu)p' log 2 1 Bup", ;
bound 2 by p2r--2 2 (log 2) 2 log + S
where M min ( By -242/L1 }. By Lemma F.2 we have X(C) I 2
f.
get1 and also gloog +) X(C) -7 log ZTt0l
2 B1 Combining all these formulas together gives
log 21507
p²:
L
2-2/L
|VCI2 - BRR²M
log C
S (Cn
g'Olog 2
|| < ((R+
p2
2 B1 B2
C g' g'loog 2)²
1 L
2-2/1 S 2(
B² +
RM
log
log L(ta)
log
2(to)
which completes the proof.
With Corollary E.6 and Lemma E.7 we can prove Lemma E.8 with exactly the same argument.
Then Theorem
can also be proved similarly. For Theorem E..5 we can follow the
argument for gradient flow to show that it holds with slightly different tight bounds:
Theorem F.4. Under assumptions (SI), (A2), (S3), (A4), (S5), we have the following tight rates for training loss and weight norm:
((logT))/1
C(t) -
and p(t) Ogg 1)),
T'logTyy
where T Ei=t nTT).
G EXTENSION: MULTI-CLASS CLASSIFICATION
In this section, we generalize our results multi-class classification with cross-entropy loss. This part of analysis is inspired by Theorem in (Zhang et al. 2019), which gives lower bound for the gradient in terms the loss L.
Since now neural network has multiple outputs, we need to redefine our notations. Let C' be the number of classes. The output of a neural network & is a vector $(0:x) x): E RRC We use by x0;x) E R to denote the j-th output of & on the input D ( Vn J.N {< (k) E [N]], where Hn E Id is a data input and y,. E [C] is the corresponding label. The loss function of on the dataset D is defined as
R A dataset is denoted by
N
NN (0:m.)
((0)
log
Σラ (0
The margin for single data point (æn, yn) is defined be qn (0) Ty (0; a:.) max (0, p,)}, and the margin for the entire dataset is defined to be Jmin (0) = min (0). We define the normalized margin to be 5(0) = (0) Quin (0)/p", where p= p::110m p= and 0 = 0/p p E 1 as usual.
Let ((g) log( le be the logistic loss. Recall that E(g) satisfies (B3). Let f(q) log [og((g)
log log + e )). Let g be the inverse function of f. So g(g) log(e"
1).
The cross-entropy loss can be rewritten in other ways. Let Snj = o (0: - (0; Let
Th = -SE((1 : + Bnr) =
log (Eftm e e~ans)
Then
N
N Σ
N
N
((0) =
log 1 + Σ
Ans
e
Sns
log(1 + 9m)
Σ
((ām) = Σ e
f(e.)
n=1
J
n=1
n=1
n=1
Gradient Flow.
For gradient flow, assume the following:
(MI), (Regularity). For any fixed x and j E [C]. Φ3( a:) is locally Lipschitz and admits a chain
rule;
40

---

Published as a conference paper at ICLR 2020
(M2). (Homogeneity). There exists L such that Vj [C]. Va Φ,(00;x) a
(M3). (Cross-entropy Loss). L()) is defined as the cross-entropy loss the training set;
(M4). (Separability). There exists time to such that [(ta) < log
If < log 2, then Ejpn, eny 1 for all [MV, and thus snj > 0 for all n E [M], [C]. So (M4) ensures the separability of training data.
Definition G.I. For cross-entropy loss, the smoothed normalized margin 5(0) of 0 is defined
7(0) = (C) log(e -1)
pt
pl
where (-) is the inverse function of the logistic loss E(-).
Theorem 4.1 and 4.4 still hold.
Here we redefine the optimization problem (P) to be
1
min
2 10112
s.t. 8ny
(n) 21
Vn E [N].Vj E [C] \ {un}
Most of our proofs are very similar as before. Here only show the proof for the generalized version of Lemma[5.1
Lemma G.2. Lemma 5.1 is also true for the smoothed normalized margin Ý defined in Defini-
tion G.7
Proof. Define vtt) by the following formula:
N
Σ $g
e 883888)
((t)
=
R=1 i4yn
e Ra3
Using similar argument as in Theorem B.4 it can be proved that
do² dt
Lu(() for t > 0.
ollog t
It can be shown that Lemma B.5 which asserts that v()) 2
d'llog 2) L. still holds for this new
definition of v(t). By definition, Snj On for j + Un. Also note that a- So snj 9n 2 Zn. Then we have
Ejtyo
v(t)
Σ
Tn
On
f' ("n)
f(ān)
Eejton E 0ng
4n
n=1
n=1
Note that L Dm c- (lan), Then using Lemma B.5 for logistic loss conclude that v(t) 2
g(log 2) C.
g' (log 2)
The rest of the proof for this lemma is exactly the same as that for Lemma 5.1
Gradient Descent. For gradient descent, we only need to replace (MI) with (SI) and make assumption (S5) on the learning rate.
(S1). (Smoothness). For any fixed and E [C), (,(+))) is C²-smooth;
(S5). (Learing rate condition). Σizo n(t) too and 1y(t) < H(C(O(t)).
Here (x)) == /(x)//( (C,,t(()) defined to be the same as in Appendix (when E(-) is set to another C, which will be specified later.
logistic loss) except that
We only need to show that Lemma F2 and Lemmal F3 continue to hold. Using the same argument do for gradient flow, show that (() and ((x) do satisfy the propositions in Lemma R2
41

---

Published as a conference paper at ICLR 2020
For Lemma + first note the original definition of C, involves Bo, B1, B2, which are undefined the multi-class setting. So now we redefine them as
Bo == sup { Sny : 0 E S n [N]jE [C]],
B1 = sup /|Vanll 212 0 E Westti [M] E [C]}
B2 == sup ( [
0 E s [M].j E [C]]
By the property of LSE, we can use Bo, B1, B2 to bound on, Vân: Va
In - 4n
Bop
12
Vönj
V Vonj 12 S Biph-1,
1=1 e Emn
Bmb
5=1
k=
8nj
e 20n5
(V2 - Vang Vons)
V8ng V
k==
e 8nk
( Aim e-onk
S B22 2 + BBRp21--2
Using these bounds, we can prove with the constant C, defined as follows:
C == (6==(((()))) (((6)) )
1 Bo
p2p+1
B2
2B )
( (((tt) ) M,
Bn
B + (2log
log Z(to]
p(t)))
where M == min (((t))- -2+2/L BB 1422/L
H EXTENSION: MULTI-HOMOGENEOUS MODELS
In this section, extend results to multi- multi-homoggeneus models. For this, the main difference from the proof for homogeneous models that now we have to separate the norm of each homo- geneous parts of the parameter, rather than consider them whole. So only small part to proof needs to be changed. We focus on gradient flow, but it is worth to note that following the same argument, it is not hard extend the results to gradient descent.
Let (Ww1,.... wm: x) be (Ra,..., km) hoooogeneouu.... Let p: = ||w:ll2 and W =
w. The
||w
smoothed normalized margin defined in (5) can be rewritten as follows:
Definition H.I. For a multi hottonnoomge model with loss function ((-) satisfying (B3), the smoothed normalized margin (0) of is defined as
(0)) = g(log L)
(2((
I P.
I P.
We only prove the generalized version of Lemma 5.1 here. The other proofs are almost the same. Lemma H.2. For all t > to
d
m
drē; ||
lo > 0 for all i E [m]] and log 2 di
ki
log Pi
(24)
dl
di
1=1
Proof. Note that d log P: de
1 del kz(l) by Theorem B.4 It simply follows from Lemma B.5
20
that z log for a.e. & to. And it easy that log 7 log (g(log b1/p²) exists for all
42

---

Published as a conference paper at ICLR 2020
t 2 to. By the chain rule and Lemma B.3 have
d d log (ollog 2))
g (log
1
(-
dC
kPv(t)
log =
Kg log
Σ
dt dt
g(log 2))
L
dt
dl
kEv(1)
v(t)
dt
P
im
dC
k vt)2
v(t)
dt
P
On the one hand,
dc
by Lemma Combining these together yields
172
dw.
for a.e. 1.
I.3 on the other hand, (()(()
ar
(w dt ) by Theorem B.4
))
dw;
dw:
dww;
log 2
wi. dl
(1
dl
v(()
di
(()
dl
By the chain rule,
1) for
a.e. >> So we have
di
P1
dw
dei;
log
7
2
log Pi
dt
v(t)
dt
dt
dt
1=1
For cross-entropy loss, combine the proofs in Appendix G show that Lemma H.2 holds if we use the following definition of the smoothed normalized margin: Definition H.3. For muuliihommggeeeuu model with cross-entropy, the smoothed normalized mar- gin (0) of 0 is defined as
(C)
loog(e -1)
Il. P.
where (-) is the inverse function of the logistic loss E(.).
The only place need change in the proof for Lemma that instead of using Lemma B.5
gilog +) C in similar way as in Lemma G.2 The other parts of the proof
need to prove v(() 2
s' (logg 2) are exactly the same as before.
CHAIN RULES FOR NON-DIFFERENTIABLE FUNCTIONS
In this section, we provide some background the chain rule for non-differentiable functions. The ordinary chain rule for differentiable functions a very useful formula for computing derivatives in calculus. However, for non-differentiaale functions, it is difficult find natural definition of subdifferential so that the chain rule equation holds exactly. To solve this issue, Clarke proposed Clarke's 's subdifferential (Clarke) 1975] 1990 Clarke al.] (0088] for locally Lipschitz functions, for which the chain rule holds as an inclusion rather than an equation:
Theorem I.1 (Theorem 2.3.9 and 2.3.10 of (Clarke 1990)). Let 21, Zn Rd R and f
IR + R be locally sipschitzfunctton Let (f z (x) f21(2))..... 2.. (x)) be the composition
of f and Then,
( o 2x) C conv La : a a (ffee
822((0)
For analyzing gradient flow, the chain rule crucial. For differentiable loss function L(O), can see from the chain rule that the function value keeps decreasing along the gradient flow d0(
dt
vL)((()) dL(O(t)) VL((())), dt
d0(t) dt
1
d0(t)) dt 2
(25)
43

---

Published as a conference paper at ICLR 2020
But for locally Lipschitz functions which could be non-differentiable, 225 may not hold in general since Theorem [.1 only holds for an inclusion.
Following (Davis al. 2020 Drusvyatskiy et al. 2015), consider the functions that admit chain rule for any arc. Definition 1.2 (Chain Rule). A locally Lipschitz function f Fd + R admits chain rule if for any are 2 [0, +000 + -24
vh E 8 ((=()) (foz) = (h, = 2()))
(26)
holds for a.e. t >> O.
It is shown in (Davis et al. 2020 for such functions:
Drusvyatskiy et al. 2015) that generalized version of
25 holds
Lemma 1.3 (Lemma 5.2 Davis et al.
2020 Let L : Rd - be a locally fiischitz,fuuction that be the gradient flow on L:
admits chain rule. Let 0 [0, +00)
(t E 0 ((O(t))
for a.e. t 2 0,
dt
Then
dC((e(t)
dd(tt dt
min ( h 8 c(O(t)))
12
holds for a.e.
We can see that -smsoooth functions admit chain rules. As shown in (Davis et al. 2020). if locally Lipschitz function is subdifferentiablly regular Whitney C'-stratifiable, then it admits chain rule. The latter one includes a large family of functions, e.g., semi-algebree functions, semi- analytic functions, and definable functions in o-minimal structure (Coste 2002 van den Dries & Miller 1996).
It is worth noting that the class of functions that admits chain rules is closed under composition. This is indeed a simple corollary of Theorem I.I
Theorem 1.4. Let 21,..., Rd - TR and f: RR" R be locally Lipschitz functions functions and assume all of them admit chain rules. Let (f o 2))x)) f() 2,( Then f also admits chain rule.
be the composition of f and
Proof. We can see that f is locally Lipschitz. Let [0, +00) + Rd, x(() be an arc. First, we show that z x [0, +20) + Rd, 8 + (xx(t) also an arc. For any closed sub-interval I, xxx(I)) must be contained in compact set U. Then it can be shown that the locally Lipschitz continuous function is (globally) Lipschitz continuous on U. By the fact that the composition of Lipschitz continuous and absolutely continuous function is absolutely continuous, z is absolutely continuous on 7, and thus it is an arc.
Since and admit chain rules
and respectively, the following holds for >> 0,
Ya E 0 (()) (f (z))2()))(
= (a, (2 x) Vh; E 02 (x(())) (z,z))(() = (h;
Combining these we obtain that for a.e. >> 0,
(fozoz)(() = Σ a (h, x (t))
for all a E 0 f=(x((() and for all h; (z)(((t)). The RHS can be rewritten as (Ein ash; (t)). By Theorem I.I every & E 8 (z) can be written as a convex combi-
nation of a finite set of points in the form of Σi= arh. So (f 1oxox)(t = (k, a'(t)) holds for a.e. > 0.
44

---

Published as a conference paper at ICLR 2020
J MEXICAN HAT
In this section, we give an example to illustrate that gradient flow does not necessarily converge in direction, even for -mooth homogeneous models.
known that gradient flow (or gradient descent) may not converge to any point even when opti- mizing C function (Curry) 1944, Zoutendijk 1976. Palis & De Melo 2011 2, Absil al. 2005
One famous counterexample is the "Mexican Hat" function described in (Absil et al. 2005):
(1-)(r) sin (p 1-
1
fu, f(r cos p,, rin
r21 1
where Crr)
4p (1- E [0, 1]. It can be shown that f is -smooh on R but not analytic.
See Figure 2 for plot for f(u, r))
0.8
0.6
0.0
0.5
0.0
-0.5
0.5
-0.5
-1.0
Figure 2: A plot for the Mexican Hat function f(u, v).
However, the Maxican Hat function not homogeneous, and Absil al. (2005) did consider the directional convergence, either. To make it homogeneous, we introduce an extra variable and normalize the parameter before evaluate f. In particular, we fix I. > O and define
h()) h(x,, y, = p² (u, where u =/ e y/p. p= ==Vx2+ 12
We can show the following theorem.
Theorem J.1. Consider gradient flow on (()) = E 20)) where (0) = h()) for all pr [N]. Suppose the polar representation of (u, v) is (r c v). < and
0(t) does not converge to any point, and the limit points of 1- holds at time t = 0, then [10(t)]]2
(()) |o(t))la t>> 0} form a circle {(x. v, E S x² + y2 1, 1 00.
Proof. Define vb = 1-p2- Our proof consists of two parts, following from the idea in (Absil Then we can infer that s for all f 12 O. Next, we show that r + 1 as t - +oo. Using tb = 0. we know that the polar angle - too +oc. Therefore, (u, v) circles around {(u, v) u2 + 2 1}, and thus it does not converge.
al. 2005). First, we show that de as long as dt
as
Proof for de = O. For convenience, we use w to denote 2/ p. By simple calculation, we have the following formulas for partial derivatives:
dz p² --1
[u((1 - /) - (1 - u u2) ur
de
0f
0f
0f
Lo(l - f) + uv 01
02) af
7
8
By
30
01 v
Øh
[w(1 -f uw 81 ww 81
de
dr
45

---

Published as a conference paper at ICLR 2020
For gradient flow, we have
d0 dl
Ne
"Vh
du 1
dx
dy
dz
-(1 u²) 05
os
(1- 112
Ne pb-
ut
ual
+ uu
dt P
dt
dt
dt
du
du
du 1
(1- x²2) dy dx
vw dz
NN pp - 2²)) 0f
+ 0f
(1
un
dt p
dt
dt
dt
Ov
du
By writing down the movement
of (u, u) in the polar coordinate system, we have
dr
du r dl + r dl
u du
Ne N p
05
+ u(1 - x3) 05
un11 12)
r
Ou
0v
0f
Neh
Ne h 0l--(( 211 12)
Òr
de
du
dv
di
,2
y2
Ne ph1-2
0f 0f
1'
x2
Du
Ov
= p 1
0f
,2 0y
For r = 0, the partial derivatives of f with respect to and yp can be evaluated as follows:
0f
d
e - (r() sin w - ((r) cos 1b
Dr
dr
Dr
d
-
+e + C(r)
1
dr
dr 1- p22
(1 22) (1 - C(r))e 1-
2r
0f
I- ((r) cos qi-
06
T- C(r). C(r).
So if da 0, then
de 0 by the direct calculation below:
dbb
de d
dr
dt
dt
dr
1 p2
dt
1 O
2r
0f
Ne h p L-2
+
,2 Oip
(1 -1-120 22 dr
2
2
Ne pl 22
+
12 + (1 r2)4
C(r)
(1-r2)4) 0.
Proof for + 1. Let (ū, be convergent point of {uu, v) : t > 0}. Define F = //2² + v.h It is easy to see that r S from the normalization of in the definition. According to Theorem 4.4 know that (ū, ū) is stationary point of {u(()), v(t)) 1 ((((t),,(t)) If F 0, then
f(ū, 6) > (u((), v()), which contradicts to the monotonicity of 7()) = 7() = (1=f(((),, f < 1, then v = (defined as & for (ū, 8)). So
Øf
Or --- (1 - C(r))e - # 0, which
again leads to a contradiction. Therefore, F = 1, and thus r - 1.
K EXPERIMENTS
To validate theoretical results, conduct several experiments. We mainly focus MNIST dataset. We trained two models with Tensorflow. The first one (called the CNN with bias) is a stan- dard 4-yyyer CNN with exactly the same architecture as that used in MNIST Adversarial Examples
46

---

Published as a conference paper at ICLR 2020
The layers of this model can be described as conv-32 with filter size 5 5, max-pool, conv-64 with filter size 3 x 3, max-pool, fc-1024, fc-10 in order. Notice that this model has bias terms in each layer, and thus does not satisfy homogeneity. To make its outputs homogeneous to its parameters, we also trained this model after removing all the bias terms except those in the first layer (the modified model is called the CNN without bias). Note that keeping the bias terms in the first layer prevents the model to be homogeneous in the imput data while retains the homogeneity in parameters. We initialize all layer weights by He normal initializer (He al. 2015) and all bias terms by zero. In training the models. we use SGD with batch size 100 without momentum. We normalize all the images to [0, 1] 1]32x32 by dividing 255 for each pixel.
Challenge [
K.1 EVALUATION FOR NORMALIZED MARGIN
In the first part of our experiments, we evaluate the normalized margin every few epochs to see how it changes over time. From on, view the bias term in the first layer part of the weight in the first layer for convenience, Observe that the CNN without bias is multi-homogeneous in layer weights (see (4) in Section (444). So for the CNN without bias,
define the normalized margin 7 as the margin divided by the product of the L2-norm of all layer weights. Here we compute the L2-norm of a layer weight parameter after flattening into a one-dimensional vector. For the CNN with bias, we still compute the smoothed normalized margin in this way. When computing the I norm of every layer weight, we simply ignore the bias terms if they are not in the first layer. For completeness, we include the plots for the normalized margin using the original definition 2 in Figure 3 4
0r=0.01, w/ blas
0r=0011, bias
100%
10-5
training accuracy
99%
norm normalzzed alized margin
0.20 10
97%
0.00 1000>
96%
-0.20 x x0
95%
-0.40 x 10-5
50
100
10a
10:
10
10a
10
#epochs
#epochs
Figure 3: Training CNNs with and without bias on MNIST, using SGD with learning rate 0.01. The training accuracy (left) increases to 100% after about 100 epochs, and the normalized margin with the original definition (right) keeps increasing after the model is fitted.
loss ass-basee blas
loss-based blas
100%
100
training accuracy
nomall Zed margin
4.00 10
99%
10-2
3.00 10-3
98%
10-4
10-4
2.00 10-9
97%
10-7
0.00 10"
15
2500
7500 10000
2500 7500 10000 #epochs
#epochs
#epochs
Figure 4: Training CNNs with and without bias on MNIST, using SGD with the loss-based learning rate scheduler. The training accuracy (left) increases to 100% after about 20 epochs, and the nor- malized margin with the original definition (middle) increases rapidly after the model is fitted. The right figure shows the change of the relative learning rate at)) (see (27) for its definition) during training.
11enge
47

---

Published as a conference paper at ICLR 2020
SGD with Constant Learning Rate. We first train the CNNs using SGD with constant learning rate 0.01. After about 100 epochs, both CNNs have fitted the training set. After that, we can see that the normalized margins of both CNNs increase. However, the growth rate of the normalized margin rather slow. The results are shown in Figure T in Section other than 0.01, and similar phenomena be observed.
| We also tried other learning rates
SGD with Loss-based Learning Rate. Indeed, we can speed up the training by using a proper scheduling of learning rates for SGD. We propose a heuristic learning rate scheduling method, called the loss-based learning rate scheduling. The basic idea is to find the maximum possible learning rate each epoch based on the current training loss (in a similar way as the line search method). See Appendix[L.l [.1 for the details. As shown in Figure SGD with boss-based learning rate schedul- ing decreases the training loss exponentially faster than SGD with constant learning rate. Also, rapid growth of normalized margin is observed for both CNNss Note that with this scheduling the training loss can as small as 10 10-800, which may lead to numerical issues. To address such is- sues, applied some re- parammtterizationn tricks and numerical tricks in our implementation. See Appendix L.2 for the details.
Experiments on CIFAR-10. To verify whether the normalized margin is increasing in practice, also conduct experiments on CIFAR-10. We use a modified version of VGGNet-16. The layers of this model can be described as conv-64 x2, max-pool conv-128 x2, max-pool, conv-256 x3, max-pool, conv-512 x3, max-pool, conv-512 x3, max-pool, fc-10 in order, where each conv has filter size x We train two networks:
is exactly the same the VGGNet we described, and the other one is the VGGNet without any bias terms except those in the first layer (similar in the experiments on MNIST). The experiment results are shown in Figure and 6 We can see that the normalize margin is increasing over time.
1== w/ bias
1r=0.1, w/o bias
10
normallizd margin
0.00 10
training lss
-0
10-5
-0.20 X 10-17
10-7
x0.30
10-17
100
10
102
10a
10*
10a
10.
10?
10a
10f
#epochs
#epochs
Figure 5: Training VGGNet with and without bias on CIFAR-10, using SGD with learning rate 0.1.
loss-based Ir, w/ bias
loss-based w/o bias
10P
normalizee margin
5.00 10
10-2006
4.00
10-17
training
10 4000
2.00 10-17
1.00 10
10 2000
10
1250 2500
3750 #epochs
5000
1250 2500
3750 5000 #epochs
Figure 6: Training VGGNet with and without bias on CIFAR-10, using SGD with the loss-based learning rate scheduler.
Test Accuracy. Previous works on margin-based generalization bounds (Neyshabur et al., 2018
Bartlett al. 2017 Golowich et al. 2018 Li et al. 2018a Wei al.) 2019: Banburski et al.
48

---

Published as a conference paper at ICLR 2020
2019) usually suggest that larger margin implies a better generalization bound. To whether the generalization error also gets smaller in practice, we plot train and test accuracy for both MNIST and CIFAR-10. 10. As shown in Figure 7 the test accuracy changes only slightly after training with loss- based learning rate scheduling for 10000 epochs, although the normalized margin does increase a lot. We leave it future work study this interesting gap between margin-hased generalization bound and generalization error. Concurrent to this work, Wei & Ma Ma (2020) proposed a generalization bound based on a new notion of margin called all-layer margin, and showed via experiments that enlarging all- all-layer margin can indeed improve generalization. It would be an interesting research direction to study how different definitions of margin may lead different generalization abilities.
train
test
1.000
1.00
accuracy (MNIST)
D. 0.995
ac accuracy (CIFAR-10) 10)
0.95
0.990
0.985
0.980
0.85
0.975
0.970
0.80
2000
4000 6000 8000 8000 10000 #epochs
2000 4000 6000 8000 100000000 #epochs
Figure 7: (Left). Training and test accuracy during training CNNs without bias on MNIST, using SGD with the loss-based learning rate scheduler. Every number is averaged over 10 runs. (Right). Training and test accuracy during training VGGNet without bias on CIFAR-10 10, using SGD with the loss-based learning rate scheduler. Every number is averaged over 3 runs.
K.2 EVALUATION FOR ROBUSTNESS
Recently, robustness of deep learning has received considerable attention (Szegedy et al. 2013 Big- gio et al., 2013, Athalyy al., 2018), since most state-of-the-arts deep neural networks are found to be very vulnerable against small but adversarial perturbations of the input points. In our experi- ments, found that enlarging the normalized margin can improve the robustness. In particular, by simply training the neural network for a longer time with our loss-based learning rate, we observe noticeable improvements of L'brouustssss on both the training set and test set.
We first elaborate the relationship between the normalized margin and the robustness from a theo- retical perspective. For a data point = (æz y). we can define the robustness (with respect some norm []) of neural network & for z to be
Ro(z) = inf {1| x' (æ', y) is misclassified).
ø'e
where X is the data domain (which is [0, 322x33 for MNIST). It is well-known that the normalized margin is a lower bound of T,2-robustness for fully-connected networks (See, e.g., Theorem 4 in (Sokolic al. 2017)). Indeed, general relationship between those two quantities shown. Note that data point is correctly classified iff the margin for z, denoted as qo (z). is larger than O. For homogeneous models, the margin (0(z) and the normalized margin (g(z) for have the same sign. If (-(-)) d + R is S-Lipschitz (with respect to some norm || - []]. then it is easy to see that (z(z) 2 4g (=)/3. This suggests that improving the normalize margin on the training set can improve the robustness on the training set. Therefore, our theoretical analysis suggests that training longer can improve the robustness of the model on the training set.
be easily
This observation does match with our experiment results. In the experiments, we measure the -²_ robustness of the CNN without bias for the first time its loss decreases below 10 10 10-15 10 120 (labelled as model-1 to model-4 respectively). We also measure the L Lo-robustness for the final model after training for 10000 epochs (labelled model-5), whose training loss is about 10 882, The normalized margin of each model is monotone increasing with respect to the number of epochs, shown in Table
49

---

Published as a conference paper at ICLR 2020
model-1
model-2 -2
model-3
model:4
model-5
100%
100%
accuracy (train)
98%
80%
96%
60%
94%
40%
20%
90%
100%
100%
accuracy (test)
98%
96%
60%
94%
40%
92%
20%
90%
0.0
0.2
0.6
4
6
Figure 8: Li²rrobustness of the models of CNNs without bias trained for different number of epochs (see Table for the statistics each model). Figures on the first row show the robust accuracy on the training set, and figures the second row show that the test set. On every row, the left figure and the right figure plot the same curves but they are in different scales. From model 1-1 to mode -4, noticeable robust accuracy improvements can be observed. The improvement of model-5 upon model-4 is marginal or nonexistent for some e, but the improvement upon model is always significant.
Table 1: Statistics of the CNN without bias after training for different number of epochs.
model name
number of epochs
train loss
normalized margin
train acc
test acc
model-1
38
10 10.04
5.65 x 10
100%
99.3%
model-2
75
10 15.12
15.12
9.50 x 5
100%
99.3%
model-3
107
10-20.07
1.30 x 10-4
100%
99.3%
model-4 935
10- 10-120.01
4.61 x 10-4
100%
99.2%
model-5 10000
10 10-88 881.51
1.18 x 10-3
100%
99.1%
We use the standard method for evaluating I,2-robustness in (Carlini & Wagner 2017 and the source code from the authors with default hyperparameter. We plot the robust accuracy (the percentage of data with robustness > <) for the training set in the figures on the first row of Figure X It can be seen from the figures that for small (e.g.. 6 << 0.3), the relative order of robust accuracy is just the order of model-1 to model-5. For relatively large (e.g., 0.3), the improvement of model-5 upon model- -2 to model- becomes marginal or nonexistent in certain intervals of e, but model-1 to model-4 44 still have an increasing order of robust accuracy and the improvement of model 1-5 upon model-1 is always significant. This shows that training longer can help to improve the L 2robuttt accuracy the training set.
We also evaluate the robustness on the test set, in which a misclassified test sample is considered to have robustness and plot the robust accuracy in the figures the second row of Figure g It can seen from the figures that for small (e.g.. c < 0.2), the curves of the robust accuracy of model-1 to model are almost indistinguishable. However, for relatively large (e.g., 0.2), again, model to model-4 have an increasing order of robust accuracy and the improvement of
50

---

Published as a conference paper at ICLR 2020
model-5 upon model-1 is always significant. This shows that training longer can also help to improve the -r-buttst accuracy on the test set.
We tried various different settings of hyperparameters for the evaluation method (including different learning rates, different binary search steps, etc.) and we observed that the shapes and relative positions of the curves in Figure are stable across different hyperparameter settings.
is worth to note that the normalized margin and robustness do not grow in the same speed in our experiments, although the theory suggests Rz(z) 2 (z) This may be because the Lipschitz constant 3 (if defined locally) is also changing during training. Combining training longer with
existing techniques for constraining Lipschitz number (Anil et al.) 2019 Cisse al. 2017) could potentially alleviate this issue, and we leave it as future work.
L ADDITIONAL EXPERIMENTAL DETAILS
In this section, we provide additional details of our experiments.
L.1 LOss- LOSS-BASED LEARNING RATE SCHEDULING
The intuition of the loss-based learning rate scheduling is follows. If the training loss is a- smooth, then optimization theory suggests that we should set the learning rate to roughly 1/a. For homogeneous model with cross-entropy loss, if the training accuracy is 100% O. then simple calculation can show that the smoothness (the 1,2-norm of the Hessian matrix) at A is ((--poly(p)) where L is the average training loss and poly(p) is some polynomial. Motivated by this fact, parameterize the learning rate 17()) at epoch t as
a(t)
rt()) 1)
(27)
where Σ(t - 1) the average training loss at epoch - 1, and (xt) is a relative learning rate to be tuned (Similar parameterization has been considiered in (Nacson et al. (019h) for linear model). The loss-based learning rate scheduling is indeed a variant line search. In particular, we initialize (0) by some value, and do the following at each epoch f:
Step 1. Initially (xt)) < a(t - 1); Let G(t - 1) be the training loss at the end of the last epoch;
Step 2. Run SGD through the whole training set with learning rate 1y(t) == (tt/ 1);
Step 3. Evaluate the training loss C(t) the whole training set;
Step 4. If E(I) < Z(L - 1), (l)) + (t)) Ta and end this epoch; otherwise, a(l) +- a(l)/ra and go Step 2.
In all our experiments, set (0)) 0.1, 21/5 1.149, r. = 21/10 1.072. This specific choice of those hyperparameters is not important; other choices can only affact the computational efficiency, but not the overall tendency of normalized margin.
L.2 ADDRESSING NUMERICAL ISSUES
Since we are dealing with extremely small loss (as small as 10-500), the current Tensorflow imple- mentation would run into numerical issues. To address the issues, we work as follows. Let L (0) be the (average) training loss within a batch B S [N]. We use the notations C, 4n In from Appendix G We only need to show how to perform forward and backward passes for (
Forward Pass. Suppose we have good estimate FFr for log (B( in the sense that
R₂ = Lm
1 B
Σ log 1+
Σ
(0)
(28)
is in the range of f1cat64. RB be thought of relative training loss with respect to F. Instead of evaluating the training loss C (0) directly, we turn to evaluate this relative training loss in numerically stable way:
51

---

Published as a conference paper at ICLR 2020
Step 1. Perform forward pass to compute the values of Saj with float32, and convert them into f1oat64;
Step 2. Let Q == -30 If gn (0) Q for all n B, then we compute
RB(0)=
1
Σ
(0())(0)++))
B
nEB
where (0) = -LSE({ Snnj : * vnt) 1o--log log (Eiton e=
evaluated a
numerically stable way; otherwise, we compute
RB(
1 loglp
Σ
sm)(()) c- j
Σ
B
nEB
where log]p(x:) is numerical stable implementation of log(1 + x.).
This algorithm can be explained as follows. Step 1 is numerically stable because we observe from the experiments that the layer weights and layer outputs grow slowly. Now we consider Step If on (0) < Q for some
[B], then (0) Q)) is in the range of float 64, we can compute Ra ) by (28) directly except that we need to use numerical stable implementation of log(1 z². For qn (0) Q, arithmetic underflow
occur. By Taylor expansion of log x)), know that when is small enough log(1 + x) Ra x in the sense that the relative error [log(1+x)-rt log(1+=)
O(r). Thus, we can do the following approximation
log 1+
Σ j7
(n)
c Fx e
Ee
Σ s7Um
(0)
(29)
for 9n (0) Q. and only introduce relative error of Q(Ce=Q) (recall that C is the number of classes). Using a numerical stable implementation of LSE, we can compute On easily. Then the RHS of (29) can be rewritten e (0)+ Note that computing (0))() does not have underflow overflow problems if F is good approximation for log (0))
Backward Pass. To perform backward pass, we build a computation graph in Tensorflow for the above forward pass for the relative training loss and use the automatic differentiation. We parame- terize the learning rate as 1) = f). e Then it is easy to see that taking a step of gradient descent for (0) with learning rate 7 equivalent to taking step for (0) with 7). Thus, as long as i can fit into float 64, we can perform gradient descent on RB 0)) to ensure numerical stability.
The Choice of F. The only question remains is how to choose F. In our experiments, we set F(I)= = log E(L 1) to be the training loss at the end of the last epoch, since the training loss cannot change lot within one single epoch. For this, we need to maintain log C(t) during training. This can be done follows: after evaluating the relative training loss R(t) on the whole training set, we can obtain log C(t) by adding F(t) and log R(t) together.
is worth noting that with this choice of F. fi(t) = a<t) the loss-based learning rate scheduling. As shown in the right figure of Figure 4 (t) is always between 10-9 and 10", which ensures the numerical stability of backward pass.
52


Reviews:
[{"review_id": "rJegO1tfKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 implicit regularization phenomenon. More precisely, given separable data the authors ask whether homogenous functions (including neural networks) trained by gradient flow/descent converge to the max-margin solution.  The authors show that the limit points of gradient descent are KKT points of a constrained optimization problem.\n\n-I think that the topic is important and the authors clearly made some interesting insights.\n-The main results of this paper (Theorem 4.1 and Theorem 4.4) require that assumption (A4) is satisfied. Assumption (A4) essentially means, that gradient flow/descent is able to reach weights, such that every data x_n is classified correctly. To me this seems to be a quit restrictive assumption as due to the nonconvexity of the neural net there is a priori no reason to assume that such a point is reached. In this sense, the paper only studies the latter part of the training process. \n\nI feel that Assumption (A4) clearly weakens the strength of the main results. However, because the topic studied by the paper is interesting and the authors have obtained some interesting insights, I decided to rate the paper as a weak accept.\n\nTypos:\n-p. 4: \"Very Recently\"\n-p. 7 and p. 9: \"homogenuous\" (instead of \"homogeneous\")\n\n----------\n\nI want to thank the authors for their response. However, I will stand by me evaluation and will not change it.\nI agree though that assumption (A4) is indeed reasonable, although of course very strong.  \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SJgkPWhoYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "The goal of the paper is to formally prove that gradient flow / gradient descent performed on homogeneous neural network models maximizes the margin of the learnt function; assuming gradient flow/descent manages to separate the data. This is proved in two steps:\n  1. Assuming that gradient descent manages to find a set of network parameters that separate the data, thereafter gradient flow/descent monotonically increases the normalized margin (rather an approximation of it).\n  2. The limit points of optimization are KKT points of the margin maximization optimization problem.\nWhile the main body of the paper presents a restricted set of results, the appendix generalizes this much further applying it to various kinds of loss functions (logistic/cross-entropy, exponential), to multi-class classification and to multi-homogeneous models. There seem to be many subtleties in the proofs and the paper seems to be quite thorough. (I must say that I'm not expert enough to assess the technical novelty of this paper over prior works.)\n\nRecommendation:\nI recommend \"acceptance\". The paper takes a significant step by unifying existing results on margin maximization and going beyond them. \n\nTechnical comments:\n- It is clear that in order to define margin meaningfully, some form of normalization is necessary. But a priori, $\\|\\theta\\|_2^L$ is not the *only* choice; $\\|\\theta\\|^L$ could also work for any norm $\\|\\cdot\\|$. But perhaps the choice of $\\|\\cdot\\|_2$ is special (as Thm 4.4 suggests). It will be nice to have some insights/comments on why this choice of $\\|\\cdot\\|_2$ based normalization is the right one.\n- The paper argues that having a larger margin helps in obtaining better robustness to adversarial perturbations (within $\\|\\cdot\\|$ balls for some choice of $\\|\\cdot\\|$). However note that the notion of \"margin\" is not just a function of the decision boundary, but instead depends on the specific function computed by the neural network --- this is unlike margin maximization in linear models, where \"margin\" in determined entirely by the decision boundary. As the paper argues, if we have an upper bound on the Lipschitz constant w.r.t. $\\|\\cdot\\|$ norm, then we get a lower bound on required adversarial perturbations for any training point. However, this does not mean that training longer is necessarily better because by doing so, we might end up with a larger Lipschitz constant (even after normalizing). So even if the \"margin\" is larger, the actual adversarial perturbations (in $\\|\\cdot\\|$ norm) allowed might get smaller. So I'm not sure how relevant this result is for adversarial robustness.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BylrCxVAFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 is a strong deep learning theory paper, and I recommend to accept.\n\nThis paper studies the trajectory induced by applying gradient descent/gradient flow for optimizing a homogeneous model with exponential tail loss functions, including logistic and cross-entropy loss in particular. This is an important direction in recent theoretical studies on deep learning as we need to understand which global minimizer the training algorithm picks to analyze the generalization behavior. \n\nThis paper makes a significant contribution to this direction. This paper rigorously proves gradient descent / gradient flow can maximize the L2 margin of homogeneous models. Existing works mostly focus on linear models or deep linear networks, and comparing with Nascon et al., 2019a, the assumptions in this paper are significantly weaker. Furthermore, this paper provides convergence rates, which seem to be the first work of this kind for non-linear models.\n\nI really like Lemma 5.1. This is not only a technical lemma for proving the main theorem. Lemma 5.1 itself has a nice geometric interpretation. It naturally decomposes the dynamics of the smoothed version into a radial component and a tangential velocity component. I believe this lemma can be useful in other settings as well.\n\n\nComments:\nThe bibliography should be fixed. Some papers are already published, so they should not be cited as the arXiv version, and author lists in some papers have \"et al.\"\n\n-----------------------------------------------------\nI have read the rebuttal and I maintain my score.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the implicit regularization of the gradient descent in homogeneous and shows that when the training loss falls below a threshold, then the smoothed. This study generalizes some of the earlier related works by relying on weaker assumptions. Experiments on MNIST and CIFAR-10 are provided to backup the theoretical findings of the paper. 
R2 had some concern about one of the assumptions in this work (A4). While authors admitted that (A4) may not hold for all neural networks and all datasets, they stressed that this assumptions is reasonable when the network is overparameterized and can perfectly fit the training data. Overall, all reviewers are very positive about this submission and find a valuable step toward understanding implicit regularization.

Decision: Accept (Talk)