Title: GRADIENT DESCENT MAXIMIZES THE MARGIN OF HOMOGENEOUS NEURAL NETWORKS

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.

1. INTRODUCTION:

A major open question in deep learning is why gradient descent or its variants, are biased towards solutions with good generalization performance on the test set. To achieve a 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 a weight vector w, and the class prediction for any data point x is determined by the sign of w x. Therefore, only the direction w/ w 2 is important for making prediction. Soudry et al. (2018a; b) ; Ji & Telgarsky (2018; 2019c) ; Nacson et al. (2019c) investigated this problem and proved that the direction of w converges to the direction that maximizes the L 2 -margin while the norm of w diverges to +∞, if we train w with (stochastic) gradient descent on logistic loss. Interestingly, this convergent direction is the same as that of any regularization path: any sequence of weight vectors {w t } such that every w t is a global minimum of the L 2 -regularized loss L(w) + λt 2 w 2 2 with λ t → 0 (Rosset et al., 2004) . Indeed, the trajectory of gradient descent is also pointwise close to a regularization path (Suggala et al., 2018) .

The aforementioned linear logistic regression can be viewed as a single-layer neural network. A natural 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 neural 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 Φ(θ; x), where θ stands for the parameter and x stands for the input, satisfies the following: ∀c > 0 : Φ(cθ; x) = c L Φ(θ; x) for all θ and x.

(1)

It is important to note that many neural networks are homogeneous (Neyshabur et al., 2015a; Du et al., 2018) . For example, deep fully-connected neural networks or deep CNNs with ReLU or 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 et al., 2019) , it is shown that the regularization path does converge to the max-margin direction for homogeneous neural networks with cross-entropy or logistic loss. This result suggests that gradient descent or gradient flow may also converges to the max-margin direction by assuming homogeneity, and this is indeed true for some sub-classes of homogeneous neural networks. For gradient 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 et al., 2018b) formulate a constrained optimization problem related to margin maximization and prove that gradient descent converges to the direction of a KKT point or even the max-margin direction, under various assumptions including the convergence of loss and gradient directions. In an independent work, (Nacson et al., 2019a) 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 homogeneous 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 A for the details). This assumption is not restrictive as 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)1 .

While the first assumption is natural, the second requires some explanation. In fact, we assume that at some time t 0 , the training loss is smaller than a threshold, and the threshold here is chosen to be so small that the training accuracy is guaranteed to be 100% (e.g., for the logistic loss and cross-entropy loss, the threshold can be set to ln 2). Empirically, state-of-the-art CNNs for image classification can even fit randomly labeled data easily (Zhang et al., 2017) . Recent theoretical work on over-parameterized neural networks (Allen-Zhu et al., 2019; Zou et al., 2018) show that gradient descent can fit the training data if 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.

Our Contribution. Similar to linear models, for homogeneous models, only the direction of parameter θ is important for making predictions, and one can see that the margin γ(θ) scales linearly with θ L 2 , when fixing the direction of θ. To compare margins among θ in different directions, it makes sense to study the normalized margin, γ(θ) := γ(θ)/ θ L 2 . In this paper, we focus on the training dynamics of the network after t 0 (recall that t 0 is a 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 one can easily come up with examples in which γ increases or 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 γ, such that (1) |γ -γ| → 0 as t → ∞; and (2) γ is non-decreasing for t > t 0 .

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 {θ(t)/ θ(t) 2 : t > 0} is along the direction of a KKT point of the maxmargin problem. This indicates that gradient descent/gradient 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; Ji & Telgarsky, 2019a; Gunasekar et al., 2018b) from linear classifiers to homogeneous classifiers. 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 normalized margin (right) increases rapidly after the model is fitted (≈ 1.2 × 10 -3 after 10000 epochs, 10× 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/growth rates of the loss and weights. It is shown in (Soudry et al., 2018a; b; Ji & Telgarsky, 2018; 2019c ) that the loss decreases at the rate of O(1/t), the weight norm grows as O(log t) for linear logistic regression. In this work, we generalize the result by showing that the loss decreases at the rate of O(1/(t(log t)2-2/L )) and the weight norm grows as O((log t) 1/L ) for homogeneous neural networks with exponential loss, logistic loss, or cross-entropy loss.

Experiments. 2 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.1). Results on MNIST are presented in Figure 1 . 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.

For feedforward neural networks with ReLU activation, the normalized margin on a training sample is closely related to the L 2 -robustness (the L 2 -distance from the training sample to the decision boundary). Indeed, the former divided by a Lipschitz constant is a lower bound for the latter. For example, the normalized margin is a lower bound for the L 2 -robustness on fully-connected networks with ReLU activation (see, e.g., Theorem 4 in (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 L 2 -robustness on both training and test sets (see Section K.2).

2. RELATED WORK:

Implicit Bias in Training Linear Classifiers. For linear logistic regression on linearly separable data, Soudry et al. (2018a; b) showed that full-batch gradient descent converges in the direction of the max L 2 -margin solution of the corresponding hard-margin Support Vector Machine (SVM 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 & Telgarsky (2019a) showed that the product of weights in a deep linear network with strictly decreasing loss converges in the direction of the max L 2 -margin solution. Gunasekar et al. (2018b) showed 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 Perceptron (Ramdas & Pena, 2016) . Comparison with (Nacson et al., 2019a) . Very recently, (Nacson et al., 2019a) analyzed gradient descent for smooth homogeneous models and proved the convergence of parameter direction to a KKT point of the aforementioned 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 t 0 (and we prove the exact convergence rate of the loss after t 0 ); (2) They assume the convergence of parameter direction3 , while we prove that KKT conditions hold for all limit points of {θ(t)/ θ(t) 2 : t > 0}, without requiring any convergence assumption;

Implicit Bias in:

(3) They assume the convergence of the direction of losses (the direction of the vector whose entries are loss values on 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, we also prove the monotonicity of the normalized margin and provide tight convergence rate for training loss. We believe both results are interesting in their own right.

Another technical difference is that their work analyzes discrete gradient descent on smooth homogeneous models (which fails to capture ReLU networks). In our work, we analyze both gradient descent on smooth homogeneous models and also gradient flow on homogeneous 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 to our proof of Theorem 4.1 in spirit. Wilson et al. (2017) ; Ali et al. (2019) ; Gunasekar et al. (2018a) showed that for the linear least-square problem gradient-based methods converge to the unique global minimum that is closest to the initialization in L 2 distance. Du et al. (2019) ; Jacot et al. (2018) ; Lee et al. (2019) ; Arora et al. (2019b) showed that over-parameterized neural networks of sufficient width (or infinite width) behave as 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 include (Ma et al., 2019; Gidel et al., 2019; Arora et al., 2019a; Suggala et al., 2018; Blanc et al., 2019; Neyshabur et al., 2015b; a) .

3. PRELIMINARIES:

Basic Notations. For any

N ∈ N, let [N ] = {1, . . . , N }. v 2 denotes the L 2 -norm of a vector v. The default base of log is e. For a function f : R d → R, ∇f (x) stands for the gradient at x if it exists. A function f : X → R d is C k -smooth if f is k times continuously differentiable. A function f : X → R is locally Lipschitz if for every x ∈ X there exists a neighborhood U of x such that the restriction of f on U is Lipschitz continuous.

Non-smooth Analysis. For a locally Lipschitz function f : X → R, the Clarke's subdifferential (Clarke, 1975; Clarke et al., 2008; Davis et al., 2020) at x ∈ X is the convex set

∂ • f (x) := conv lim k→∞ ∇f (x k ) : x k → x, f is differentiable at x k .

For brevity, we say that a function z : I → R d on the interval I is an arc if z is absolutely continuous for any compact sub-interval of I. For an arc z, z (t) (or dz dt (t)) stands for the derivative at t if it exists. Following the terminology in (Davis et al., 2020) , we say that a locally Lipschitz function f : R d → R admits a chain rule if for any arc z :

[0, +∞) → R d , ∀h ∈ ∂ • f (z(t)) : (f • z) (t) = h, z (t) holds for a.e. t > 0 (see also Appendix I).

Binary Classification. Let Φ be a neural network, assumed to be parameterized by θ. The output of Φ on an input x ∈ R dx is a real number Φ(θ; x), and the sign of Φ(θ; x) stands for the classification result. A dataset is denoted by D = {(x n , y n ) : n ∈ [N ]}, where x n ∈ R dx stands for a data input and y n ∈ {±1} stands for the corresponding label. For a loss function : R → R, we define the training loss of Φ on the dataset D to be L(θ) := N n=1 (y n Φ(θ; x n )). Gradient Descent. We consider the process of training this neural network Φ with either gradient descent or gradient flow. For gradient descent, we assume the training loss L(θ) is C 2 -smooth and describe the gradient descnet process as θ(t + 1) = θ(t) -η(t)∇L(θ(t)), where η(t) is the learning rate at time t and ∇L(θ(t)) is the gradient of L at θ(t).

Gradient Flow. For gradient flow, we do not assume the differentibility but only some regularity assumptions including locally Lipschitz. Gradient flow can be seen as gradient descent with infinitesimal step size. In this model, θ changes continuously with time, and the trajectory of parameter θ during training is an arc θ : [0, +∞) → R d , t → θ(t) that satisfies the differential inclusion

dθ(t) dt ∈ -∂ • L(θ(t)) for a.e. t ≥ 0. The Clarke's subdifferential ∂ • L is a natural generalization of the usual differential to non-differentiable functions. If L(θ) is actually a C 1 -smooth function, the above differential inclusion reduces to dθ(t) dt = -∇L(θ(t)

) for all t ≥ 0, which corresponds to the gradient flow with differential in the usual sense.

(S5) is natural since deep neural networks are usually trained with constant learning rates. (S1) ensures the smoothness of Φ, which is often assumed in the optimization literature in order to analyze gradient descent. While (S1) does not hold for neural networks with ReLU, it does hold for neural networks with smooth homogeneous activation such as the quadratic activation φ(x) := x 2 (Li et al., 2018b; Du & Lee, 2018) or powers of ReLU φ(x) := ReLU(x) α for α > 2 (Zhong et al., 2017; Klusowski & Barron, 2018; Li et al., 2019) .

4.2. MAIN THEOREM: MONOTONICITY OF NORMALIZED MARGINS:

The margin for a single data point (x n , y n ) is defined to be q n (θ) := y n Φ(θ; x n ), and the margin for the entire dataset is defined to be q min (θ) := min n∈[N ] q n (θ). By homogenity, the margin q min (θ) scales linearly with θ L 2 for any fixed direction since q min (cθ) = c L q min (θ). So we consider the normalized margin defined as below:

EQUATION

)

We say f is an -additive approximation for the normalized margin if γ -≤ f ≤ γ, and c-

multiplicative approximation if cγ ≤ f ≤ γ.

Gradient Flow. Our first result is on the overall trend of the normalized margin γ(θ(t) More concretely, the function γ(θ) in Theorem 4.1 is defined as

EQUATION

Note that the only difference between γ(θ) and γ(θ) is that the margin q min (θ) in γ(θ) is replaced by log 1 L(θ) = -LSE(-q 1 (θ), . . . , -q N (θ)), where LSE(a 1 , . . . , a N ) = log(exp(a 1 ) + • • • + exp(a N )) is the LogSumExp function. This is indeed a very natural idea, and previous works on linear models (e.g., (Telgarsky, 2013; Nacson et al., 2019b) ) also approximate q min with LogSumExp in the analysis of margin. It is easy to see why γ(θ) is an O( θ -L

2 )-additive approximation for γ(θ): e amax ≤ N n=1 e an ≤ N e amax holds for a max = max{a 1 , . . . , a N }, so a max ≤ LSE(a 1 , . . . , a N ) ≤ a max + log N ; combining this with the definition of γ(θ) gives γ(θ) -θ -L 2 log N ≤ γ(θ) ≤ γ(θ). Gradient Descent. For gradient descent, Theorem 4.1 holds similarly with a slightly different function γ(θ) that approximates γ(θ) multiplicatively rather than additively. Theorem 4.2 (Corollary of Theorem E.2). Under assumptions (S1), (A2) -(A4), (S5), there exists an (1 -O(1/(log 1 L )))-multiplicative approximation function γ(θ) for the normalized margin such that the following statements are true for gradient descent:

1. For all t > t 0 , γ(θ(t + 1)) ≥ γ(θ(t));

2. For all t > t 0 , either γ(θ(t + 1)) > γ(θ(t)) or θ(t+1) θ(t+1) 2 = θ(t) θ(t) 2 ;

3. L(θ(t)) → 0 and θ(t) 2 → ∞ as t → +∞; therefore, |γ(θ(t)) -γ(θ(t))| → 0.

Due to the discreteness of gradient descent, the explicit formula for γ(θ) is somewhat technical, and we refer the readers to Appendix E for full details.

Convergence Rates. It is shown in Theorem 4.1, 4.2 that L(θ(t)) → 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 (A1) -(A4) or gradient descent under assumptions (S1), (A2) -(A4), (S5), we have the following tight bounds for training loss and weight norm:

L(θ(t)) = Θ 1 T (log T ) 2-2/L and θ(t) 2 = Θ (log T ) 1/L ,

where T = t for gradient flow and T = t-1 τ =t0 η(τ ) for gradient descent.

4.3. MAIN THEOREM: CONVERGENCE TO KKT POINTS:

For gradient flow, γ is upper-bounded by γ ≤ γ ≤ sup{q n (θ) : θ 2 = 1}. Combining this with Theorem 4.1 and the monotone convergence theorem, it is not hard to see that lim t→+∞ γ(θ(t)) and lim t→+∞ γ(θ(t)) 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 θ(t) directionally converges to its KKT points, as shown below. We note that we can extend this result to 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 A and Theorem E.4 in Appendix E for the details.

We will briefly review the definition of KKT points and approximate KKT points for a constraint optimization problem in Appendix C.1. Theorem 4.4 (Corollary of Theorem A.8 and E.3). For gradient flow under assumptions (A1) -(A4) or gradient descent under assumptions (S1), (A2) -(A4), (S5), any limit point θ of θ(t) θ(t) 2 : t ≥ 0 is along the direction of a KKT point of the following constrained optimization problem (P):

min 1 2 θ 2 2 s.t. q n (θ) ≥ 1 ∀n ∈ [N ]

That is, for any limit point θ, there exists a scaling factor α > 0 such that α θ satisfies Karush-Kuhn-Tucker (KKT) conditions of (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 q min (θ) > 0. For a fixed θ, αθ is a feasible point of (P) iff α ≥ q min (θ) -1/L . Thus, the minimum objective value over all feasible points of (P) in the direction of θ is 1 2 θ/q min (θ) 1/L 2 2 = 1 2 γ(θ) -2/L . Taking minimum over all possible directions, we can conclude that if the maximum normalized margin is γ * , then the minimum objective of (P) is

1 2 γ-2/L * .

It can be proved that (P) satisfies the Mangasarian-Fromovitz 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, q n (θ) can be highly non-convex. Indeed, as gradient descent is a first-order optimization method, if we do not make further assumptions on q n (θ), 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 to KKT points is perhaps the best we can hope for in our setting, and it is an interesting future work to prove stronger convergence results with further natural assumptions.

Moreover, we can prove the following corollary, which characterizes the optimality of the normalized margin using SVM with Neural Tangent Kernel (NTK, introduced in (Jacot et al., 2018 )) defined at limit points. The proof is deferred to Appendix C.6. Corollary 4.5 (Corollary of Theorem 4.4). Assume (S1). Then for gradient flow under assumptions (A2) -(A4) or gradient descent under assumptions (A2) -(A4), (S5), any limit point θ of {θ(t)/ θ(t) 2 : t ≥ 0} is along the max-margin direction for the hard-margin SVM with kernel Published as a conference paper at ICLR 2020

K θ (x, x ) = ∇Φ x ( θ), ∇Φ x ( θ)

, where Φ x (θ) := Φ(θ; x). That is, for some α > 0, α θ is the optimal solution for the following constrained optimization problem:

min 1 2 θ 2 2 s.t. y n θ, ∇Φ xn ( θ) ≥ 1 ∀n ∈ [N ]

If we assume (A1) instead of (S1) for gradient flow, then there exists a mapping h(x) ∈ ∂ • Φ x ( θ) such that the same conclusion holds for K θ (x, x ) = h(x), h(x ) .

4.4. OTHER MAIN RESULTS:

The above results can be extended to 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, (q) = log(1 + e -q ). The function class also includes other losses with exponential tail, e.g., (q) = e -q 3 , (q) = log(1 + e -q 3 ). For all those loss functions, we can use its inverse function -1 to define the smoothed normalized margin as follows

γ(θ) = -1 (L(θ)) θ L 2 .

Then all our results for gradient flow continue to hold (Appendix A). Using a similar modification, we can also extend it to gradient descent (Appendix F).

Cross-entropy Loss. In multi-class classification, we can define q n to be the difference between the classification score for the true label and the maximum score for the other labels, then the margin q min := min n∈[N ] q n and the normalized margin γ(θ) := qmin(θ)

θ L 2 can be similarly defined as before. 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.

Multi-homogeneous Models. Some neural networks indeed possess a stronger property than homogeneity, which we call multi-homogeneity. For example, the output of a CNN (without bias terms) is 1-homogeneous with respect to the weights of each layer. In general, we say that a neural network Φ(θ; x) with θ = (w 1 , . . . , w m ) is (k 1 , . . . , k m )-homogeneous if for any x and any c 1 , . . . , c m > 0, we have Φ(c 1 w 1 , . . . , c m w m ; x) = m i=1 c ki i • Φ(w 1 , . . . , w m ; x). In the previous example, an L-layer CNN with layer weights θ = (w 1 , . . . , w L ) is (1, . . . , 1)-homogeneous.

One can easily see that that (k 1 , . . . , k m )-homogeneity implies L-homogeneity, where L = m i=1 k i , so our previous analysis for homogeneous models still applies to multi-homogeneous models. But it would be better to define the normalized margin for multi-homogeneous model as

EQUATION

)

In this case, the smoothed approximation of γ for general binary classification loss (under some conditions) can be similarly defined for gradient flow:

EQUATION

It can be shown that γ is also non-decreasing during training when the loss is small enough (Appendix H). In the case of cross-entropy loss, we can still define γ by (5) while (•) is set to the logistic loss in the formula.

5. PROOF SKETCH: GRADIENT FLOW ON HOMOGENEOUS MODEL WITH EXPONENTIAL LOSS:

In this section, we present a proof sketch in the case of gradient flow on 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 E respectively.

For convenience, we introduce a few more notations for a L-homogeneous neural network Φ(θ; x). Let S d-1 = {θ ∈ R d : θ 2 = 1} be the set of L 2 -normalized parameters. Define ρ := θ 2 and θ := θ θ 2 ∈ S d-1 to be the length and direction of θ. For both gradient descent and gradient flow, θ is a function of time t. For convenience, we also view the functions of θ, including L(θ), q n (θ), q min (θ), as functions of t. So we can write L(t) := L(θ(t)), q n (t) := q n (θ(t)), q min (t) := q min (θ(t)).

Lemma 5.1 below is the key lemma in our proof. It decomposes the growth of the smoothed normalized margin into the ratio of two quantities related to the radial and tangential velocity components of θ 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 > t 0 ,

d dt log ρ > 0 and d dt log γ ≥ L d dt log ρ -1 d θ dt 2 2 .

Using Lemma 5.1, the first two claims in Theorem 4.1 can be directly proved. For the third claim, we make use of the monotonicity of the margin to lower bound the gradient, and then show L → 0 and ρ → +∞. Recall that γ is an O(ρ -L )-additive approximation for γ. So this proves the third claim. We defer the detailed proof to Appendix B.

To show Theorem 4.4, we first change the time measure to log ρ, i.e., now we see t as a function of log ρ. So the second inequality in Lemma 5.1 can be rewritten as

d log γ d log ρ ≥ L d θ d log ρ 2 2 .

Integrating on both sides and noting that γ is upper-bounded, we know that there must be many instant log ρ such that d θ d log ρ 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) : 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 a theorem from (Dutta et al., 2013) to 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 a proof sketch for Lemma 5.1, in which we derive the formula of γ 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 theorem for homogeneous functions extensively.

Proof Sketch of Lemma 5.1. For ease of presentation, we ignore the regularity issues of taking derivatives in this proof sketch. We start from the equation

dL dt = -∂ • L(θ(t)), dθ dt = -dθ dt 2 2

which follows from the chain rule (see also Lemma I.3). Then we note that dθ dt can be decomposed into two parts: the radial component v := θ θ dθ dt and the tangent component u := (I -θ θ ) dθ dt .

The radial component is easier to analyze. By the chain rule,

v 2 = θ dθ dt = 1 ρ θ, dθ dt = 1 ρ • 1 2 dρ 2 dt . For 1 2 dρ 2

dt , we have an exact formula:

1 2

EQUATION

The last equality is due to ∂ • q n , θ = Lq n by homogeneity of q n . This is sometimes called Euler's theorem for homogeneous functions (see Theorem B.2). For differentiable q n , it can be easily proved by taking the derivative over c on both sides of q n (cθ) = c L q n (θ) and letting c = 1.

With (6), we can lower bound 1 2 dρ 2

dt by 1 2

EQUATION

where the last inequality uses the fact that e -qmin ≤ L. (7) also implies that 1 2

dρ 2 dt > 0 for t > t 0 since L(t 0 ) < 1 and L is non-increasing. As d dt log ρ = 1 2ρ 2 dρ 2

dt , this also proves the first inequality of Lemma 5.1.

Now, we have:

v 2 2 = 1 ρ 2 1 2 dρ 2 dt 2 = 1 2 dρ 2 dt • d

dt log ρ on the one hand; on the other hand, by the chain rule we have

d θ dt = 1 ρ 2 (ρ dθ dt -dρ dt θ) = 1 ρ 2 (ρ dθ dt -( θ dθ dt )θ) = u ρ . So we have - dL dt = dθ dt 2 2 = v 2 2 + u 2 2 = 1 2 dρ 2 dt • d dt log ρ + ρ 2 d θ dt 2 2 Dividing 1 2 dρ 2

dt on the leftmost and rightmost sides, we have

- dL dt • 1 2 dρ 2 dt -1 = d dt log ρ + d dt log ρ -1 d θ dt 2 2

.

By -dL dt ≥ 0 and ( 7), the LHS is no greater than

-dL dt • L • L log 1 L -1 = 1 L log log 1 L . Thus we have d dt log log 1 L -L d dt log ρ ≥ L d dt log ρ -1 d θ dt 2 2

, where the LHS is exactly d dt log γ.

6. DISCUSSION AND FUTURE DIRECTIONS:

In this paper, we analyze the dynamics of gradient flow/descent of homogeneous neural networks under a minimal set of assumptions. The main technical contribution of our work is to prove rigorously 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 nonsmooth ones? In the smooth case, we can lower bound the decrement of training loss by the gradient norm squared, multiplied by a factor related to learning rate. However, in the non-smooth case, no such inequality is known in the optimization literature.

• Can we make more structural assumptions on the neural network to prove stronger results?

In this work, we use a minimal set of assumptions to show that the convergent direction of parameters is a KKT point. A potential research direction is to 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. 

A RESULTS FOR GENERAL LOSS:

In this section, we state our results for a broad class of binary classification loss. A major consequence of this generalization is that the logistic loss, one of the most popular loss functions, (q) = log(1 + e -q ) is included. The function class also includes other losses with exponential tail, e.g., (q) = e -q 3 , (q) = log(1 + e -q 3 ).

A.1 ASSUMPTIONS:

We first focus on gradient flow. We assume (A1), (A2) as we do for exponential loss. For (A3), (A4), we replace them with two weaker assumptions (B3), (B4). All the assumptions are listed below:

(A1). (Regularity). For any fixed x, Φ( • ; x) is locally Lipschitz and admits a chain rule; (A2). (Homogeneity). There exists L > 0 such that ∀α > 0 : Φ(αθ; x) = α L Φ(θ; x); (B3). The loss function (q) can be expressed as (q) = e -f (q) such that

(B3.1). f : R → R is C 1 -smooth. (B3.2). f (q) > 0 for all q ∈ R. (B3.

3). There exists b f ≥ 0 such that f (q)q is non-decreasing for q ∈ (b f , +∞), and f (q)q → +∞ as q → +∞.

(B3.4). Let g : [f (b f ), +∞) → [b f , +∞) be the inverse function of f on the domain [b f , +∞). There exists b g ≥ max{2f (b f ), f (2b f )}, K ≥ 1 such that g (x) ≤ Kg (θx) and f (y) ≤ Kf (θy) for all x ∈ (b g , +∞), y ∈ (g(b g ), +∞) and θ ∈ [1/2, 1).

(B4). (Separability):

. There exists a time t 0 such that

L(t 0 ) < e -f (b f ) = (b f ).

(A1) and (A2) remain unchanged. ( B3) is satisfied by exponential loss (q) = e -q (with f (q) = q) and logistic loss (q) = log(1 + e -q ) (with f (q) = -log log(1 + e -q )). (B4) are essentially the same as (A4) but (B4) uses a threshold value that depends on the loss function. Assuming (B3), it is easy to see that (B4) ensures the separability of data since

(q n ) < e -f (b f ) implies q n > b f ≥ 0.

For logistic loss, we can set b f = 0 (see Remark A.2). So the corresponding threshold value in (B4) is (0) = log 2.

Now we discuss each of the assumptions in (B3). (B3.1) is a natural assumption on smoothness. (B3.2) requires (•) to be monotone decreasing, which is also natural since (•) is used for binary classification. The rest of two assumptions in (B3) characterize the properties of (q) when q is large enough. (B3.3) is an assumption that appears naturally from the proof. For exponential loss, f (q)q = q is always non-decreasing, so we can set b f = 0. In (B3.4), the inverse function g is defined. It is guaranteed by (B3.1) and (B3.2) that g always exists and g is also C 1 -smooth. Though (B3.4) looks very complicated, it essentially says that f (Θ(q)) = Θ(f (q)), g (Θ(q)) = Θ(g (q)) as q → ∞. (B3.4) is indeed a technical assumption that enables us to asymptotically compare the loss or the length of 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.

We summarize the corresponding f, g and b f for exponential loss and logistic loss below: Remark A.1. Exponential loss (q) = e -q satisfies (B3) with

f (q) = q f (q) = 1 g(q) = q g (q) = 1 b f = 0 (b f ) = 1.

Remark A.2. Logistic loss (q) = log(1 + e -q ) satisfies (B3) with

f (q) = -log log(1 + e -q ) = Θ(q) f (q) = e -q (1 + e -q ) log(1 + e -q ) = Θ(1)

g(q) = -log(e e -q -1) = Θ(q) g (q) = e -q e e -q -1 = Θ(1)

b f = 0 (b f ) = log 2.

The proof for Remark A.1 is trivial. For Remark A.2, we give a proof below.

Proof for Remark A.2. By simple calculations, the formulas for f (q), f (q), g(q), g (q) are correct. (B3.1) is trivial. f (q) = e -q (1+e -q ) log(1+e -q ) > 0, so (B3.2) is satisfied. For (B3.3), note that f (q)q = q (1+e q ) log(1+e -q ) . The denominator is a decreasing function since d dq (1 + e q ) log(1 + e -q ) = e q log(1 + e -q ) -1 < e q • e -q -1 = 0.

Thus, f (q)q is a strictly increasing function on R. As b f is required to be non-negative, we set b f = 0. For proving that f (q)q → +∞ and (B4), we only need to notice that f (q) ∼ e -q 1•e -q = 1 and g (x) = 1/f (g(x)) ∼ 1.

A.2 SMOOTHED NORMALIZED MARGIN:

For a loss function (•) satisfying (B3), it is easy to see from (B3.2) that its inverse function -1 (•) must exist. For this kind of loss functions, we define the smoothed normalized margin as follows: Definition A.3. For a loss function (•) satisfying (B3), the smoothed normalized margin γ(θ) of θ is defined as

γ(θ) := -1 (L) ρ L = g(log 1 L ) ρ L = g -log N n=1 e -f (qn(θ)) ρ L ,

where -1 (•) is the inverse function of (•) and ρ := θ 2 . Remark A.4. For logistic loss (q) = log(1 + e -q ), γ(θ) = ρ -L log 1 exp(L)-1 ; for exponential loss (q) = e -q , γ(θ) = ρ -L log 1 L , which is the same as (3). Now we give some insights on how well γ(θ) approximates γ(θ) using a similar argument as in Section 4.2. Using the LogSumExp function, the smoothed normalized margin γ(θ) can also be written as

γ(θ) = g(-LSE(-f (q 1 ), . . . , -f (q N ))) ρ L .

LSE is a (log N )-additive approximation for max. So we can roughly approximate γ(θ) by

γ(θ) ≈ g(-max{-f (q 1 ), . . . , -f (q N )}) ρ L = g(f (q min )) ρ L = γ(θ).

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 a good approximation of γ. Lemma A.5. Assuming (B3)4 , we have the following properties about the margin:

(a) f (q min ) -log N ≤ log 1 L ≤ f (q min ). (b) If log 1 L > f (b f ), then there exists ξ ∈ (f (q min ) -log N, f (q min )) ∩ (b f , +∞) such that γ - g (ξ) log N ρ L ≤ γ ≤ γ. (c) For a seuqnce of parameters {θ m ∈ R d : m ∈ N}, if L(θ m ) → 0, then |γ(θ m ) -γ(θ m )| → 0.

Proof. (a) can be easily deduced from e -f (qmin) ≤ L ≤ N e -f (qmin) . Combining (a) and the monotonicity of g(•), we further have g(s) ≤ g(log 1 L ) ≤ q min for s := max{f (b f ), f (q min )log N }. By the mean value Theorem, there exists ξ ∈ (s, f (q min )) such that g(s) = g(f (q min ))g (ξ)(f (q min ) -s) ≥ q min -g (ξ) log N . Dividing ρ L on each side of q min -g (ξ) log N ≤ g(log 1 L ) ≤ q min proves (b). Now we prove (c). Without loss of generality, we assume log 1 L(θm) > f (b f ) for all θ m . It follows from (b) that for every θ m there exists

ξ m ∈ (f (q min (θ m )) -log N, f (q min (θ m ))) ∩ (b f , +∞) such that γ(θ m ) -(g (ξ m ) log N )/ρ(θ m ) L ≤ γ(θ m ) ≤ γ(θ m ). (8) Note that ξ m ≥ f (q min (θ m )) -log N ≥ log 1 L(θm) -log N → +∞. So g(ξm) g (ξm) = f (g(ξ m ))g(ξ m ) → +∞ by (B3.

3). Also note that there exists a constant B 0 such that γ(θ m ) ≤ B 0 for all m since γ is continuous on the unit sphere S d-1 . So we have

g (ξ m ) ρ(θ m ) L = g (ξ m ) g(ξ m ) g(ξ m ) ρ(θ m ) L ≤ g (ξ m ) g(ξ m ) q min (θ m ) ρ(θ m ) L = g (ξ m ) g(ξ m ) • γ(θ m ) ≤ g (ξ m ) g(ξ m ) • B → 0,

where the first inequality follows since ξ m ≤ f (q min (θ m )). Together with (8), we have |γ(θ m )γ(θ m )| → 0.

Remark A.6. For exponential loss, we have already shown in Section 4.2 that γ(θ) is an O(ρ -L )additive approximation for γ(θ). For logistic loss, it follows easily from g (q) = Θ(1) and (b) of Lemma A.5 that γ(θ) is an O(ρ 

θ(t) θ(t) 2 = 0; 3. L(θ(t)) → 0 and θ(t) 2 → ∞ as t → +∞; therefore, |γ(θ(t)) -γ(θ(t))| → 0.

For the normalized margin at convergence, we 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, we define the constrained optimization problem (P) as follows:

min 1 2 θ 2 2 s.t. q n (θ) ≥ 1 ∀n ∈ [N ]

First, we show the directional convergence of θ(t) to a KKT point of (P). Theorem A.8. Consider gradient flow under assumptions (A1), (A2), (B3), (B4). For every limit point θ of θ(t) : t ≥ 0 , θ/q min ( θ) 1/L is a 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 (A1), (A2), (B3), (B4). For any , δ > 0, there exists r := Θ(log δ -1 ) and ∆ := Θ( -2 ) such that θ/q min (θ) 1/L is an ( , δ)-KKT point at some time t * satisfying log θ(t * ) 2 ∈ (r, r + ∆).

For the definitions for KKT points and approximate KKT points, we refer the readers to Appendix C.1 for more details.

With a refined analysis, we can also provide tight rates for loss convergence and weight growth. The proof is given in Appendix D. Theorem A.10. Under assumptions (A1), (A2), (B3), (B4), we have the following tight rates for loss convergence and weight growth:

L(θ(t)) = Θ g(log t) 2/L t(log t) 2 and θ(t) 2 = Θ(g(log t) 1/L ).

Applying Theorem A.10 to exponential loss and logistic loss, in which g(x) = Θ(x), we have the following corollary: Corollary A.11. If (•) is the exponential or logistic loss, then,

L(θ(t)) = Θ 1 t(log t) 2-2/L

and θ(t) 2 = Θ((log t) 1/L ).

B MARGIN MONOTONICITY FOR GENERAL LOSS:

In this section, we consider gradient flow and prove Theorem A.7. We assume (A1), (A2), (B3), (B4) as mentioned in Appendix A.

We follow the notations in Section 5 to define ρ := θ 2 and θ := θ θ 2 ∈ S d-1 , and sometimes we view the functions of θ as functions of t.

B.1 PROOF FOR PROPOSITION 1 AND 2:

To prove the first two propositions, we generalize our key lemma (Lemma 5.1) to general loss. Lemma B.1. For γ defined in Definition A.3, the following holds for all t > t 0 ,

EQUATION

)

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 subdifferential, we can generalize it to locally Lipschitz functions that admit chain rules:

Theorem B.2. Let F : R d → R be a locally Lipschitz function that admits a chain rule. If F is k-homogeneous, then (a) For all x ∈ R d and α > 0, ∂ • F (αx) = α k-1 ∂ • F (x) That is, ∂ • F (αx) = {α k-1 h : h ∈ ∂ • F (x)}. (b) (Euler's Theorem for Homogeneous Functions). For all x ∈ R d , x, ∂ • F (x) = k • F (x) That is, x, h = k • F (x) for all h ∈ ∂ • F (x).

Proof. Let D be the set of points x such that F is differentiable at x. According to the definition of Clarke's subdifferential, for proving (a), it is sufficient to show that

{ lim k→∞ ∇F (αx k ) : x k → x, αx k ∈ D} = {α k-1 lim k→∞ ∇F (x k ) : x k → x, x k ∈ D} (10) Fix x k ∈ D.

Let U be a neighborhood of x k . By definition of homogeneity, for any h ∈ R d and any y ∈ U \ {x k },

F (αy) -F (αx k ) -αy -αx k , α k-1 h αy -αx k 2 = α k-1 • F (y) -F (x k ) -y -x k , h y -x k 2 .

Taking limits y → x k on both sides, we know that the LHS converges to 0 iff the RHS converges to 0. Then by definition of differetiability and gradient, F is differentiable at αx k iff it is differentiable at x k , and

∇F (αx k ) = α k-1 h iff ∇F (x k ) = h. This proves (10). To prove (b), we fix x ∈ R d . Let z : [0, +∞) → R d , α → αx be an arc. By definition of homogeneity, (F • z)(α) = α k F (x) for α > 0.

Taking derivative with respect to α on both sides (for differentiable points), we have

EQUATION

holds for a.e. α > 0. Pick an arbitrary α > 0 making (11) hold. Then by (a), (11

) is equivalent to ∀h ∈ ∂ • F (x) : x, α k-1 h = kα k-1 F (x), which proves (b).

Applying Theorem B.2 to homogeneous neural networks, we have the following corollary: Corollary B.3. Under the assumptions (A1) and (A2), for any

θ ∈ R d and x ∈ R dx , θ, ∂ • Φ x (θ) = L • Φ x (θ),

where Φ x (θ) = Φ(θ; x) is the network output for a fixed input x. 

dρ 2 dt = L N n=1 e -f (qn) f (q n )q n .

Proof. The proof idea is to use Corollary B.3 and chain rules (See Appendix I for chain rules in Clarke's sense). Applying the chain rule on t → ρ 2 = θ 2 2 yields 1 2 dρ 2 dt = -θ, h for all h ∈ ∂ • L and a.e. t > 0. Then applying the chain rule on θ → L, we have

-∂ • L ⊆ N n=1 e -f (qn) f (q n )∂ • q n = N n=1 e -f (qn) f (q n )h n : h n ∈ ∂ • q n .

By Corollary B.3, θ, h n = Lq n , and thus 1 2

dρ 2 dt = L N n=1 e -f (qn) f (q n )q n .

For convenience, we define ν(t) := N n=1 e -f (qn) f (q n )q n for all t ≥ 0. Then Theorem B.4 can be rephrased as 1 2 dρ 2 dt = Lν(t) for a.e. t ≥ 0. Lemma B.5. For all t > t 0 ,

ν(t) ≥ g(log 1 L ) g (log 1 L ) L.

Proof. By Lemma A.5,

q n ≥ g(log 1 L ) for all n ∈ [N ].

Then by Assumption (B3),

f (q n )q n ≥ f (g(log 1 L )) • g(log 1 L ) = g(log 1 L ) g (log 1 L )

.

Combining this with the definitions of ν(t) and L gives

ν(t) = N n=1 e -f (qn) f (q n )q n ≥ N n=1 e -f (qn) g(log 1 L ) g (log 1 L ) = g(log 1 L ) g (log 1 L ) L. Proof for Lemma B.1. Note that d dt log ρ = 1 2ρ 2 dρ 2 dt = L ν(t)

ρ 2 by Theorem B.4. Then it simply follows from Lemma B.5 that d dt log ρ > 0 for a.e. t > t 0 . For the second inequality, we first prove that log γ = log -1 (L)/ρ L = log g(log 1 L )/ρ L exists for all t ≥ t 0 . L(t) is non-increasing with t. So L(t) < e -f (b f ) for all t ≥ t 0 . This implies that (1) log 1 L is always in the domain of g;

(2) ρ > 0 (otherwise L ≥ N e -f (0) > e -f (b f ) , contradicting (B4)). Therefore, γ := g(log 1

L )/ρ L exists and is always positive for all t ≥ t 0 , which proves the existence of log γ.

By the chain rule and Lemma B.5, we have

d dt log γ = d dt log g(log 1 L ) -L log ρ = g (log 1 L ) g(log 1 L ) • 1 L • - dL dt -L 2 • ν(t) ρ 2 ≥ 1 ν(t) • - dL dt -L 2 • ν(t) ρ 2 ≥ 1 ν(t) • - dL dt - L 2 ν(t) 2 ρ 2 .

On the one hand, -dL dt = dθ 

d dt log γ ≥ 1 ν(t) dθ dt 2 2 -θ, dθ dt 2 = 1 ν(t) (I -θ θ ) dθ dt 2 2

.

By the chain rule, d θ dt = 1 ρ (I -θ θ ) dθ dt for a.e. t > 0. So we have

d dt log γ ≥ ρ 2 ν(t) d θ dt 2 2 = L d dt log ρ -1 d θ dt 2 2 .

B.2 PROOF FOR PROPOSITION 3:

To prove the third proposition, we prove the following lemma to show that L → 0 by giving an upper bound for L. Since L can never be 0 for bounded ρ, L → 0 directly implies ρ → +∞. For showing |γ -γ| → 0, we only need to apply (c) in Lemma A.5, which shows this when L → 0. Lemma B.6. For all t > t 0 ,

G(1/L(t)) ≥ L 2 γ(t 0 ) 2/L (t -t 0 ) for G(x) := x 1/L(t0) g (log u) 2 g(log u) 2-2/L du.

Therefore, L(t) → 0 and ρ(t) → +∞ as t → ∞.

Proof for Lemma B.6. By Lemma I.3 and Theorem B.4,

- dL dt = dθ dt 2 2 ≥ θ, dθ dt 2 = L 2 • ν(t) 2 ρ 2

Using Lemma B.5 to lower bound ν and replacing ρ with g(log 1 L )/γ 1/L by the definition of γ, we have

- dL dt ≥ L 2 • g(log 1 L ) g (log 1 L ) L 2 • γ(t) g(log 1 L ) 2/L ≥ L 2 γ(t 0 ) 2/L • g(log 1 L ) 2-2/L g (log 1

L ) 2 L, where the last inequality uses the monotonicity of γ. So the following holds for a.e. t ≥ t 0 ,

g (log 1 L ) 2 g(log 1 L ) 2-2/L • d dt 1 L ≥ L 2 γ(t 0 ) 2/L .

Integrating on both sides from t 0 to t, we can conclude that

G(1/L) ≥ L 2 γ(t 0 ) 2/L (t -t 0 ).

Note that 1/L is non-decreasing. If 1/L does not grow to +∞, then neither does G(1/L). But the RHS grows to +∞, which leads to a contradiction. So L → 0.

To make L → 0, q min must converge to +∞. So ρ → +∞.

C CONVERGENCE TO THE MAX-MARGIN SOLUTION:

In this section, we analyze the convergent direction of θ and prove Theorem A.8 and A.9, assuming (A1), (A2), (B3), (B4) as mentioned in Section A.

We follow the notations in Section 5 to define ρ := θ 2 and θ := θ θ 2 ∈ S d-1 , and sometimes we view the functions of θ as functions of t.

C.1 PRELIMINARIES FOR KKT CONDITIONS:

We first review the definition of Karush-Kuhn-Tucker (KKT) conditions for non-smooth optimization problems following from (Dutta et al., 2013) .

Consider the following optimization problem (P) for x ∈ R d :

min f (x) s.t. g n (x) ≤ 0 ∀n ∈ [N ]

where f, g 1 , . . . , g n : R d → R are locally Lipschitz functions. We say that x ∈ R d is a feasible point of (P) if x satisfies g n (x) ≤ 0 for all n ∈ [N ].

Definition C.1 (KKT Point). A feasible point x of (P) is a KKT point if x satisfies KKT conditions: there exists λ 1 , . . . , λ N ≥ 0 such that

1. 0 ∈ ∂ • f (x) + n∈[N ] λ n ∂ • g n (x); 2. ∀n ∈ [N ] : λ n g n (x) = 0.

It is important to note that a global minimum of (P) may not be a KKT point, but under some regularity assumptions, the KKT conditions become a necessary condition for global optimality. The regularity condition we shall use in this paper is the non-smooth version of Mangasarian-Fromovitz Constraint Qualification (MFCQ) (see, e.g., the constraint qualification (C.Q.5) in (Giorgi et al., 2004) ): Definition C.2 (MFCQ). For a feasible point x of (P), (P) is said to satisfy MFCQ at

x if there exists v ∈ R d such that for all n ∈ [N ] with g n (x) = 0, ∀h ∈ ∂ • g n (x) : h, v > 0.

Following from (Dutta et al., 2013) , we define an approximate version of KKT point, as shown below. Note that this definition is essentially the modified -KKT point defined in their paper, but these two definitions differ in the following two ways: (1) First, in their paper, the subdifferential is allowed to be evaluated in a neighborhood of x, so our definition is slightly stronger; (2) Second, their paper fixes δ = 2 , but in our definition we make them independent. Definition C.3 (Approximate KKT Point). For , δ > 0, a feasible point x of (P) is an ( , δ)-KKT point if there exists

λ n ≥ 0, k ∈ ∂ • f (x), h n ∈ ∂ • g n (x) for all n ∈ [N ] such that 1. k + n∈[N ] λ n h n (x) 2 ≤ ; 2. ∀n ∈ [N ] : λ n g n (x) ≥ -δ.

As shown in (Dutta et al., 2013) , ( , δ)-KKT point is an approximate version of KKT point in the sense that a series of ( , δ)-KKT 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 {x k ∈ R d : k ∈ N} be a sequence of feasible points of (P), { k > 0 : k ∈ N} and {δ k > 0 : k ∈ N} be two sequences. x k is an ( k , δ k )-KKT point for every k, and k → 0, δ k → 0. If x k → x as k → +∞ and MFCQ holds at x, then x is a KKT point of (P).

C.2 KKT CONDITIONS FOR (P):

Recall that for a homogeneous neural network, the optimization problem (P) is defined as follows:

min 1 2 θ 2 2 s.t. q n (θ) ≥ 1 ∀n ∈ [N ]

Using the terminologies and notations in Appendix C.1, the objective and constraints are f (x) = 1 2 x 2 2 and g n (x) = 1 -q n (x). The KKT points and approximate KKT points for (P) are defined as follows: Definition C.5 (KKT Point of (P)). A feasible point θ of (P) is a KKT point if there exist λ 1 , . . . , λ N ≥ 0 such that

1. θ - N n=1 λ n h n = 0 for some h 1 , . . . , h N satisfying h n ∈ ∂ • q n (θ); 2. ∀n ∈ [N ] : λ n (q n (θ) -1) = 0.

Definition C.6 (Approximate KKT Point of (P)). A feasible point θ of (P) is an ( , δ)-KKT point of (P) if there exists λ 1 , . . . , λ N ≥ 0 such that

1. θ - N n=1 λ n h n 2 ≤ for some h 1 , . . . , h N satisfying h n ∈ ∂ • q n (θ); 2. ∀n ∈ [N ] : λ n (q n (θ) -1) ≤ δ.

By the homogeneity of q n , 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 θ.

Proof. Take v := θ. For all n ∈ [N ] satisfying q n = 1, by homogeneity of

q n , v, h = Lq n (θ) = L > 0 holds for any h ∈ -∂ • q n (θ) = ∂ • (1 -q n (θ)). C.3 KEY LEMMAS Define β(t) := 1 dθ dt 2 θ, dθ dt

to be the cosine of the angle between θ and dθ dt . Here β(t) is only defined for a.e. t > 0. Since q n is locally Lipschitz, it can be shown that q n is (globally) Lipschitz on the compact set S d-1 , which is the unit sphere in R d . Define

B 0 := sup q n ρ L : θ ∈ R d \ {0} = sup q n : θ ∈ S d-1 < ∞. B 1 := sup h 2 ρ L-1 : θ ∈ R d \ {0}, h ∈ ∂ • q n , n ∈ [N ] = sup h 2 : θ ∈ S d-1 , h ∈ ∂ • q n , n ∈ [N ] < ∞.

For showing Theorem A.8 and Theorem A.9, we first prove Lemma C.8. In light of this lemma, if we aim to show that θ is along the direction of an approximate KKT point, we only need to show β → 1 (which makes → 0) and L → 0 (which makes δ → 0). Lemma C.8. Let C 1 , C 2 be two constants defined as

C 1 := √ 2 γ(t 0 ) 1/L , C 2 := 2eN K 2 Lγ(t 0 ) 2/L B 1 γ(t 0 ) log 2 K

, where K, b g are constants specified in (B3.4). If log 1 L ≥ b g at time t > t 0 , then θ := θ/q min (θ) 1/L is an ( , δ)-KKT point of (P), where

:= C 1 √ 1 -β and δ := C 2 /(log 1 L ).

Proof. Let h(t) := dθ dt (t) for a.e. t > 0. By the chain rule, there exist h 1 , . . . , h N such that

EQUATION

)

Then θ can be shown to be an ( , δ)-KKT point by the monotonicity γ(t) ≥ γ(t 0 ) for t > t 0 .

Proof of (12). From our construction,

N n=1 λ n hn = q -1/L min ρh/ h 2 . So θ - N n=1 λ n hn 2 2 = q -2/L min ρ 2 θ - h h 2 2 2 = q -2/L min ρ 2 (2 -2β) ≤ 2 γ2/L (1 -β),

where the last equality is by Lemma A.5.

Proof for (13). According to our construction,:

N n=1 λ n (q n ( θ) -1) = q -2/L min ρ h 2 N n=1

e -f (qn) f (q n )(q n -q min ).

Note that h 2 ≥ h, θ = Lν/ρ. By Lemma B.5 and Lemma D.1, we have qmin) ,

ν ≥ g(log 1 L ) g (log 1 L ) L ≥ 1 2K log 1 L • L ≥ 1 2K f (γρ L )e -f (

where the last inequality uses f (γρ L ) = log 1 L and L ≥ e -f (qmin) . Combining these gives

N n=1 λ n (q n ( θ) -1) ≤ 2Kq -2/L min ρ 2 Lf (γρ L ) N n=1

e f (qmin)-f (qn) f (q n )(q n -q min ).

If q n > q min , then by the mean value theorem there exists ξ n ∈ (q min , q n ) such that f (q n )f (q min ) = f (ξ n )(q n -q min ). By Assumption (B3.4), we know that f

(q n ) ≤ K log 2 (qn/ξn) f (ξ n ). Note that log 2 (q n /ξ n ) ≤ log 2 (2B 1 ρ L /q min ) ≤ log 2 (2B 1 /γ). Then we have N n=1 λ n (q n ( θ) -1) ≤ 2Kq -2/L min ρ 2 Lf (γρ L ) K log 2 (2B1/γ) n: qn =qmin e -f (ξn)(qn-qmin) f (ξ n )(q n -q min ) ≤ 2K γ-2/L ρ 2 Lf (γρ L ) K log 2 (2B1/γ) • N e

where the second inequality uses q -2/L min ρ 2 ≤ γ-2/L by Lemma A.5 and the fact that the function x → e -x x on (0, +∞) attains the maximum value e at x = 1. By Theorem A.7, we have already known that L → 0. So it remains to bound β(t). For this, we first prove the following lemma to bound the integral of β(t). Lemma C.9. For all t 2 > t 1 ≥ t 0 , 

t2 t1 β(τ ) -2 -1 • d dτ log ρ(τ ) • dτ ≤ 1 L log γ(t 2 ) γ(

EQUATION

By the chain rule,

EQUATION

)

where the last equality follows from the definition of β. Combining 14 and 15, we have

d dt log γ ≥ L β -2 -1 • d dt log ρ.

Integrating on both sides from t 1 to t 2 proves the lemma.

A direct corollary of Lemma C.9 is the upper bound for the minimum β 2 -1 within a time interval: Corollary C.10. For all t 2 > t 1 ≥ t 0 , then there exists t * ∈ (t 1 , t 2 ) such that

β(t * ) -2 -1 ≤ 1 L • log γ(t 2 ) -log γ(t 1 ) log ρ(t 2 ) -log ρ(t 1 ) .

Proof. Denote the RHS as C. Assume to the contrary that β(τ ) -2 -1 > C for a.e. τ ∈ (t 1 , t 2 ). By Lemma B.1, log ρ(τ ) > 0 for a.e. τ ∈ (t 1 , t 2 ). Then by Lemma C.9, we have

1 L log γ(t 2 ) γ(t 1 ) > t2 t1 C • d dτ log ρ(τ ) • dτ = C • (log ρ(t 2 ) -log ρ(t 1 )) = 1 L log γ(t 2 ) γ(t 1 ) ,

which leads to a 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 β(t).

C.4 ASYMPTOTIC ANALYSIS:

We first prove an auxiliary lemma which gives an upper bound for the change of θ.

Lemma C.11. For a.e. t > t 0 , d θ

dt 2 ≤ B 1 Lγ • d dt log ρ. Proof. Observe that d θ dt 2 = 1 ρ (I -θ θ ) dθ dt 2 ≤ 1 ρ dθ dt 2 .

It is sufficient to bound dθ dt 2 . By the chain rule, there exists h 1 , . . . ,

h N : [0, +∞) → R d satisfying that for a.e. t > 0, h n (t) ∈ ∂ • q n and dθ dt = n∈[N ] e -f (qn) f (q n )h n (t). By definition of B 1 , h n 2 ≤ B 1 ρ L-1 for a.e. t > 0. So we have dθ dt 2 ≤ n∈[N ] e -f (qn) f (q n ) h n 2 ≤ n∈[N ] e -f (qn) f (q n )q n • 1 q n • B 1 ρ L-1 .

Note that every summand is positive. By Lemma A.5, q n is lower-bounded by q n ≥ q min ≥ g(log 1 L ), so we can replace q n with g(log 1 L ) in the above inequality. Combining with the fact that n∈[N ] e -f (qn) f (q n )q n is just ν, we have

EQUATION

) So we have d θ dt 2 ≤ 1 ρ dθ dt 2 ≤ B1 Lγ • Lν ρ 2 = B1 Lγ • d dt log ρ.

To prove Theorem A.8, we consider each limit point θ/q min ( θ) 1/L , and construct a series of approximate KKT points converging to it. Then θ/q min ( θ) 1/L can be shown to be a KKT point by Theorem C.4. The following lemma ensures that such construction exists.

Lemma C.12. For every limit point θ of θ(t) : t ≥ 0 , there exists a sequence of {t m : m ∈ N} such that t m ↑ +∞, θ(t m ) → θ, and β(t m ) → 1.

Proof. Let { m > 0 : m ∈ N} be an arbitrary sequence with m → 0. Now we construct {t m } by induction. Suppose t 1 < t 2 < • • • < t m-1 have already been constructed. Since θ is a limit point and γ(t) ↑ γ∞ (recall that γ∞ := lim t→+∞ γ(t)), there exists s m > t m-1 such that

θ(s m ) -θ 2 ≤ m and 1 L log γ∞ γ(s m ) ≤ 3 m .

Let s m > s m be a time such that log ρ(s m ) = log ρ(s m ) + m . According to Theorem A.7, log ρ → +∞, so s m must exist. We construct t m ∈ (s m , s m ) to be a time that β(t m ) -2 -1 ≤ 2 m , where the existence can be shown by Corollary C.10. Now we show that this construction meets our requirement. It follows from

β(t m ) -2 -1 ≤ 2 m that β(t m ) ≥ 1/ 1 + 2 m → 1. By Lemma C.11, we also know that θ(t m ) -θ 2 ≤ θ(t m ) -θ(s m ) 2 + θ(s m ) -θ 2 ≤ B 1 Lγ(t 0 ) • m + m → 0.

This completes the proof.

Proof of Theorem A.8. Let θ := θ/q min ( θ) 1/L for short. Let {t m : m ∈ N} be the sequence constructed as in Lemma C.12. For each t m , define (t m ) and δ(t m ) as in Lemma C.8. Then we know that θ(t m )/q min (t m ) 1/L is an ( (t m ), δ(t m ))-KKT point and θ(t m )/q min (t m ) 1/L → θ, (t m ) → 0, δ(t m ) → 0. By Lemma C.7, (P) satisfies MFCQ. Applying Theorem C.4 proves the theorem.

C.5 NON-ASYMPTOTIC ANALYSIS:

Proof of Theorem A.9. Let C 0 := 1 L log γ∞ γ(t0) . Without loss of generality, we assume

< √ 6 2 C 1 and δ < C 2 /f (b f ). Let t 1 be the time such that log ρ(t 1 ) = 1 L log g(C2δ -1 ) γ(t0)

= Θ(log δ -1 ) and t 2 be the time such that

log ρ(t 2 ) -log ρ(t 1 ) = 1 2 C 0 C 2 1 -2 = Θ( -2 ). By Corollary C.10, there exists t * ∈ (t 1 , t 2 ) such that β(t * ) -2 -1 ≤ 2 2 C -2

1 . Now we argue that θ(t * ) is an ( , δ)-KKT point. By Lemma C.8, we only need to show

C 1 1 -β(t * ) ≤ and C 2 /f (γ(t * )ρ(t * ) L ) ≤ δ. For the first inequality, by assumption < √ 6 2 C 1 , we know that β(t * ) -2 -1 < 3, which implies |β(t * )| < 1 2 . Then we have 1 -β(t * ) ≤ 2 2 C -2 1 • β(t * ) 2 1+β(t * ) ≤ 2 C -2 1 . Therefore, C 1 1 -β(t * ) ≤ holds. For the second inequality, γ(t * )ρ(t * ) L ≥ γ(t * ) • g(C2δ -1 ) γ(t0) ≥ g(C 2 δ -1 ). Therefore, C 2 /f (γ(t * )ρ(t * ) L ) ≤ δ holds. C.6 PROOF FOR COROLLARY 4.5

By the homogeneity of q n , we can characterize KKT points using kernel SVM. Lemma C.13. If θ * is KKT point of (P), then there exists

h n ∈ ∂ • Φ xn (θ * ) for n ∈ [N ] such that So 1 L θ * satisfies KKT conditions for (Q).

Now we prove Corollary 4.5 in Section 4.3.

Proof. By Theorem A.8, every limit point θ is along the direction of a KKT point of (P). Combining this with Lemma C.13, we know that every limit point θ is also along the max-margin direction of (Q).

For smooth models, h n in (Q) is exactly the gradient ∇Φ xn ( θ). So, (Q) is the optimization problem for SVM with kernel K θ (x, x ) = ∇Φ x ( θ), ∇Φ x ( θ) . For non-smooth models, we can construct an arbitrary function h(x) ∈ ∂ • Φ x ( θ) that ensures h(x n ) = h n . Then, (Q) is the optimization problem for SVM with kernel K θ (x, x ) = h(x), 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 (A1), (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 x ∈ [b g , +∞), g(x) g (x) ∈ [ 1 2K x, 2Kx]; 2. For all y ∈ [g(b g ), +∞), f (y) f (y) ∈ [ 1 2K y, 2Ky]. Thus, g(x) = Θ(xg (x)), f (y) = Θ(yf (y)).

Proof. To prove Item 1, it is sufficient to show that

g(x) = b f + x f (b f ) g (u)du ≥ x x/2 g (u)du ≥ (x/2) • g (x) K = 1 2K • xg (x). x = f (b f ) + x f (b f ) g (u)f (g(u))du ≥ f (g(x)) K x f (g(x)/2) g (u)du = (g(x)/2) • f (g(x)) K = 1 2K • g(x) g (x)

.

To prove Item 2, we only need to notice that Item 1 implies yf (y) = g(f (y))

g (f (y)) ∈ [ 1 2K f (y), 2Kf (y)] for all y ∈ [g(b g ), +∞).

Recall that (B3.4) directly implies that f (Θ(x)) = Θ(f (x)) and g (Θ(x)) = Θ(g (x)). Combining this with Lemma D.1, we have the following corollary:

Corollary D.2. f (Θ(x)) = Θ(f (x)) and g(Θ(x)) = Θ(g(x)).

Also, note that Lemma D.1 essentially shows that (log f (x)) = Θ(1/x) and (log g(x)) = Θ(1/x). So log f (x) = Θ(log x) and log g(x) = Θ(log x), which means that f and g grow at most polynomially.

Corollary D.3. f (x) = x Θ(1) and g(x) = x Θ(1) .

D.2 PROOF FOR THEOREM A.10:

We follow the notations in Section 5 to define ρ := θ 2 and θ := θ θ 2 ∈ S d-1 , and sometimes we view the functions of θ as functions of t. And we use the notations B 0 , B 1 from Appendix C.3.

The key idea to prove Theorem A.10 is to utilize Lemma B.6, in which L(t) is bounded from above by 1 G -1 (Ω(t)) . So upper bounding L(t) reduces to lower bounding G -1 . In the following lemma, we obtain tight asymptotic bounds for G(•) and G -1 (•): Lemma D.4. For function G(•) defined in Lemma B.6 and its inverse function G -1 (•), we have the following bounds:

G(x) = Θ g(log x) 2/L (log x) 2 x and G -1 (y) = Θ (log y) 2 g(log y) 2/L y .

Proof. We first prove the bounds for G(x), and then prove the bounds for G -1 (y).

Bounding for G(x). Let C G = exp(bg) 1/L(t0) g (log u) 2 g(log u) 2-2/L du. For x ≥ exp(b g ), G(x) = C G + x exp(bg) g (log u) 2 g(log u) 2-2/L du = C G + x exp(bg) g (log u) log u g(log u) 2 g(log u) 2/L (log u) 2 du, By Lemma D.1, G(x) ≤ C G + 4K 2 g(log x) 2/L x exp(bg) 1 (log u) 2 du = O g(log x) 2/L (log x) 2 x .

On the other hand, for x ≥ exp(2b g ), we have

G(x) ≥ 1 4K 2 x √ x g(log u) 2/L (log u) 2 du ≥ g((log x)/2) 2/L 4K 2 x √ x 1 (log u) 2 du = Ω g(log x) 2/L (log x) 2 x .

Bounding for G -1 (y). Let x = G -1 (y) for y ≥ 0. G(x) always has a finite value whenever x is finite. So x → +∞ when y → +∞. According to the first part of the proof, we know that y = Θ g(log x) 2/L (log x) 2 x . Taking logarithm on both sides and using Corollary D.3, we have log y = Θ(log x). By Corollary D.2, g(log y) = g(Θ(log x)) = Θ(g(log x)). Therefore, (log y) 2 g(log y) 2/L y = Θ (log x) 2 g(log x) 2/L y = Θ(x).

This implies that x = Θ (log y) 2 g(log y) 2/L y .

For other bounds, we derive them as follows. We first show that g(log 1 L ) = Θ(ρ L ). With this equivalence, we derive an upper bound for the gradient at each time t in terms of L, and take an integration to bound L(t) from below. Now we have both lower and upper bounds for L(t). Plugging these two bounds to g(log 1 L ) = Θ(ρ L ) gives the lower and upper bounds for ρ(t).

Proof for Theorem A.10. We first prove the upper bound for L. Then we derive lower and upper bounds for ρ in terms of L, and use these bounds to give a lower bound for L. Finally, we 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 1 L ≥ G -1 (Ω(t)). Using Lemma D.4, we have

1 L = Ω (log t) 2

g(log t) 2/L t , which completes the proof.

Bounding ρ in Terms of L. γ(t) ≥ γ(t 0 ), so ρ L ≤ 1 γ(t0) g(log 1 L ) = O(g(log 1 L )). On the other hand, g(log 1 L ) ≤ q min ≤ B 0 ρ L . So ρ L = Ω(g(log 1 L ))

. Therefore, we have the following relationship between ρ L and g(log 1 L ):

EQUATION

)

Lower Bounding L. Let h 1 , . . . , h N be a set of vectors such that h n ∈ ∂qn ∂θ and

dθ dt = N n=1 e -f (qn) f (q n )h n .

By ( 17) and Corollary D.2,

f (q n ) = f (O(ρ L )) = f (O(g(log 1 L ))) = O(f (g(log 1 L ))) = O(1/g (log 1 L )).

Again by ( 17), we have

h n 2 ≤ B 1 ρ L-1 = O(g(log 1 L ) 1-1/L ).

Combining these two bounds together, it follows from Corollary D.2 that

f (q n ) h n 2 = O g(log 1 L ) 1-1/L g (log 1 L ) = O log 1 L g(log 1 L ) 1/L .

Thus,

- dL dt = dθ dt 2 2 = N n=1 e -f (qn) f (q n )h n 2 2 ≤ N n=1 e -f (qn) • max n∈[N ] {f (q n ) h n 2 } 2 ≤ L 2 • O (log 1 L ) 2 g(log 1 L ) 2/L .

By definition of G(•), this implies that there exists a constant c such that d dt G( 1 L ) ≤ c for any L that is small enough. We can complete our proof by applying Lemma D.4.

Bounding ρ in Terms of t. By ( 17) and the tight bound for L(t), ρ L = Θ(g(log 1

L )) = Θ(g(Θ(log t))). Using Corollary D.2, we can conclude that ρ L = Θ(g(log t)).

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 homogeneous models. As usual, the update rule of gradient descent is defined as

EQUATION

Here η(t) is the learning rate, and ∇L(t) := ∇L(θ(t)) is the gradient of L at θ(t).

We first focus on the exponential loss. At the end of this section (Appendix F), we discuss how to extend the proof to general loss functions with a similar assumption as (B3).

The main difficulty for discretizing our previous analysis comes from the fact that the original version of the smoothed normalized margin γ(θ) := ρ -L log 1 L becomes less smooth when ρ → +∞. Thus, if we take a Taylor expansion for γ(θ(t + 1)) from the point θ(t), although one can show that the first-order term is positive as in the gradient flow analysis, the second-order term is unlikely to be bounded during gradient descent with a constant step size. To get a smoothed version of the normalized margin that is monotone increasing, we need to define another one that is even smoother than γ.

Technically, recall that dL dt = -∇L 2 2 does not hold exactly for gradient descent. However, if the smoothness can be bounded by s(t), then it is well-known that

L(t + 1) -L(t) ≤ -η(t)(1 -s(t)η(t)) ∇L 2 2 .

By analyzing the landscape of L, one can easily find that the smoothness is bounded locally by O(L • polylog( 1 L )). Thus, if we set η(t) to a constant or set it appropriately according to the loss, then this discretization error becomes negligible. Using this insight, we define the new smoothed normalized margin γ in a way that it increases slightly slower than γ during training to cancel the effect of discretization error.

E.1 ASSUMPTIONS:

As stated in Section 4.1, we assume (A2), (A3), (A4) similarly as for gradient flow, and two additional assumptions (S1) and (S5).

(S1). (Smoothness). For any fixed x, Φ( • ; x) is C 2 -smooth on R d \ {0}. (A2). (Homogeneity). There exists L > 0 such that ∀α > 0 : Φ(αθ; x) = α L Φ(θ; x); (A3). (Exponential Loss). (q) = e -q ; (A4). (Separability). There exists a time t 0 such that L(θ(t 0 )) < 1. (S5). (Learing rate condition). t≥0 η(t) = +∞ and η(t) ≤ H(L(θ(t))).

Here H(L) is a function of the current training loss. The explicit formula of H(L) is given below:

H(x) := µ(x) C η κ(x) = Θ 1 x(log 1 x ) 3-2/L

, where C η is a constant, and κ(x), µ(x) are two non-decreasing functions. For constant learning rate η(t) = η 0 , (S5) is satisfied when η 0 if sufficiently small. Roughly speaking, C η κ(x) is an upper bound for the smoothness of L in a neighborhood of θ when x = L(θ). And we set the learning rate η(t) to be the inverse of the smoothness multiplied by a factor µ(x) = o(1). In our analysis, µ(x) can be any non-decreasing function that maps (0, L(t 0 )] to (0, 1/2] and makes the integral 1/2 0 µ(x)dx exist. But for simplicity, we define µ(x) as

µ(x) := log 1 L(t0) 2 log 1 x = Θ 1 log 1 x .

The value of C η will be specified later. The definition of κ(x) depends on L. For 0 < L ≤ 1, we define κ(x) as

κ(x) := x log 1 x 2-2/L

For L > 1, we define κ(x) as

κ(x) := x log 1 x 2-2/L

x ∈ (0, e 2/L-2 ] κ max

x ∈ (e 2/L-2 , 1)

where κ max := e (2-2/L)(ln(2-2/L)-1) . The specific meaning of C η , κ(x) and µ(x) will become clear in our analysis.

E.2 SMOOTHED NORMALIZED MARGIN:

Now we define the smoothed normalized margins. As usual, we define γ(θ) :=

log 1 L ρ L .

At the same time, we also define

γ(θ) := e φ(L) ρ L .

Here φ : (0, L(t 0 )] → (0, +∞) is constructed as follows. Construct the first-order derivative of φ(x) as

φ (x) = -sup 1 + 2(1 + λ(w)/L)µ(w) w log 1 w : w ∈ [x, L(t 0 )] ,

where λ(x) := (log 1 x ) -1 . And then we set φ(x) to be

φ(x) = log log 1 x + x 0 φ (w) + 1 w log 1 w dw.

It can be verified that φ(x) is well-defined and φ (x) is indeed the first-order derivative of φ(x). Moreover, we have the following relationship among γ, γ and γ.

Lemma E.1. γ(θ) is well-defined for L(θ) ≤ L(t 0 ) and has the following properties:

(a) If L(θ) ≤ L(t 0 ), then γ(θ) < γ(θ) ≤ γ(θ). (b) Let {θ m ∈ R d : m ∈ N} be a sequence of parameters. If L(θ m ) → 0, then γ(θ m ) γ(θ m ) = 1 -O log 1 L(θ m ) -1 → 1.

Proof. First we verify that γ is well-defined. To see this, we only need to verify that

I(x) := x 0 φ (w) + 1 w log 1 w dw exists for all x ∈ (0, L(t 0 )], then it is trivial to see that φ (w) is indeed the derivative of φ(w) by I (x) = φ (x) + 1 x log 1 x .

Note that I(x) exists for all x ∈ (0, L(t 0 )] as long as I(x) exists for a small enough x > 0. By definition, it is easy to verify that r(w) := 1+2(1+λ(w)/L)µ(w) w log 1 w is decreasing when w is small enough. Thus, for a small enough w > 0, we have

-φ (w) = r(w) = 1 + 2(1 + 1 L (log 1 w ) -1 ) log 1 L(t 0 ) 2 log 1 w w log 1 w = 1 w log 1 w + log 1 L(t0) (1 + 1 L (log 1 w ) -1 ) w(log 1 w ) 2 .

So we have the following for small enough x:

EQUATION

)

This proves the existence of I(x).

Now we prove (a):

. By Lemma A.5, γ(θ) ≤ γ(θ), so we only need to prove that γ(θ) < γ(θ).

To see this, note that for all w ≤ L(t 0 ), r(w) >

1 w log 1 w . So we have -φ (w) > 1 w log 1 w

, and this implies I(x) < 0 for all x ≤ L(t 0 ). Then it holds for all θ with L(θ) ≤ L(t 0 ) that

EQUATION

)

To prove (b), we combine ( 19) and ( 20), then for small enough L(θ m ), we have

γ(θ) γ(θ) = γ(θ) γ(θ) • γ(θ) γ(θ) = exp -log 1 L(t 0 ) 1 log 1 L(θm) + 1 2L(log 1 L(θm) ) 2 • log 1 L(θm) q min (θ m ) = exp -O 1 log 1 L(θm) • log 1 L(θm) log 1 L(θm) + O(1) = 1 -O log 1 L(θ m ) -1 . So γ(θ) γ(θ) = 1 -O (log 1 L(θm) ) -1 → 1.

Proof. By the chain rule and the definitions of B 1 , B 2 , we have

∇L 2 = - N n=1 e -qn ∇q n 2 ≤ Lρ L-1 B 1 ∇ 2 L 2 = N n=1 e -qn (∇q n ∇q n -∇ 2 q n ) 2 ≤ N n=1 e -qn B 2 1 ρ 2L-2 + B 2 ρ L-2 ≤ Lρ 2L-2 B 2 1 + ρ -L B 2 . Note that γ(t 0 )ρ L ≤ γρ L ≤ log 1 L ≤ B 0 ρ L . So γ(t 0 ) -1 log 1 L ≤ ρ L ≤ B -1 0 log 1 L .

Combining all these formulas together gives

∇L 2 2 ≤ B 2 1 min γ(t 0 ) -2+2/L , B -2+2/L 0 L 2 • log 1 L 2-2/L ≤ 2C η κ(L)L ∇ 2 L 2 ≤ B 2 1 + ρ -L B 2 min γ(t 0 ) -2+2/L , B -2+2/L 0 L • log 1 L 2-2/L ≤ 2C η κ(L),

which completes the proof.

For proving the first two propositions in Theorem E.2, we only need to prove Lemma E.8. (P1) gives a lower bound for γ. (P2) gives both lower and upper bounds for the weight growth using ν(t). (P3) gives a lower bound for the decrement of training loss. Finally, (P4) shows the monotonicity of γ, and it is trivial to deduce the first two propositions in Theorem E.2 from (P4). Lemma E.8. For all t = t 0 , t 0 + 1, . . . , we interpolate between θ(t) and θ(t + 1) by defining θ(t + α) = θ(t) -αη(t)∇L(t) for α ∈ (0, 1). Then for all integer t ≥ t 0 , ν(t) > 0, and the following holds for all α ∈ [0, 1]:

(P1). γ(t + α) > γ(t 0 ). (P2). 2Lαη(t)ν(t) ≤ ρ(t + α) 2 -ρ(t) 2 ≤ 2Lαη(t)ν(t) 1 + λ(L(t))µ(L(t)) L . (P3). L(t + α) -L(t) ≤ -αη(t)(1 -µ(L(t))) ∇L(t) 2 2 . (P4). log γ(t + α) -log γ(t) ≥ ρ(t) 2 Lν(t) 2 I -θ(t) θ(t) ∇L(t) 2 2

• log ρ(t+α) ρ(t) .

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 ≥ t 0 . Suppose that (P1), (P2), (P3), (P4) hold for any t + α ≤ T . Then if (P1) holds for (t, α) ∈ {T } × [0, A) for some A ∈ (0, 1], then all of (P1), (P2), (P3), (P4) hold for

(t, α) ∈ {T } × [0, A].

Proof for Lemma E.8. We prove this lemma by induction. For t = t 0 , α = 0, ν(t) > 0 by (S4) and Corollary E.6. (P2), (P3), (P4) hold trivially since log γ(t + α) = log γ(t), L(t + α) = L(t) and log γ(t + α) = log γ(t). By Lemma E.1, (P1) also holds trivially.

Now we fix an integer T ≥ t 0 and assume that (P1), (P2), (P3), (P4) hold for any t + α ≤ T (where t ≥ t 0 is an integer and α ∈ [0, 1]). By (P3), L(t) ≤ L(t 0 ) < 1, so ν(t) > 0. We only need to show that (P1), (P2), (P3), (P4) hold for t = T and α ∈ [0, 1].

Let A := inf{α ∈ [0, 1] : α = 1 or (P1) does not hold for (T, α)}. If A = 0, then (P1) holds for (T, A) since (P1) holds for (T -1, 1); if A > 0, we can also know that (P1) holds for (T, A) by Lemma E.9. Suppose that A < 1. Then by the continuity of γ(T + α) (with respect to α), we know that there exists A > A such that γ(T + α) > γ(t 0 ) for all α ∈ [A, A ], which contradicts to the definition of A. Therefore, A = 1. Using Lemma E.9 again, we can conclude that (P1), (P2), (P3), (P4) hold for t = T and α ∈ [0, 1].

Now we turn to prove Lemma E.9.

Proof for Lemma E.9. Applying (P3) on (t, α) ∈ {t 0 , . . . , T -1} × 1, we have L(t) ≤ L(t 0 ) < 1.

Then by Corollary E.6, we have ν(t) > 0. Applying (P2) on (t, α) ∈ {t 0 , . . . , T -1} × 1, we can get ρ(t) ≥ ρ(t 0 ).

Fix t = T . By (P2) with α ∈ [0, A) and the continuity of γ, we have γ(t + A) ≥ γ(t 0 ). Thus,

γ(t + α) ≥ γ(t 0 ) for all α ∈ [0, A].

Proof for (P2). By definition, ρ(t+α

) 2 = θ(t) -αη(t)∇L(t) 2 2 = ρ(t) 2 +α 2 η(t) 2 ∇L(t) 2 2 - 2αη(t) θ(t), ∇L(t)

. By Corollary E.6, we have

ρ(t + α) 2 -ρ(t) 2 = α 2 η(t) 2 ∇L(t) 2 2 + 2Lαη(t)ν(t). So ρ(t + α) 2 -ρ(t) 2 ≥ 2Lαη(t)ν(t).

For the other direction, we have the following using Corollary E.6 and Lemma E.7,

ρ(t + α) 2 -ρ(t) 2 = 2Lαη(t)ν(t) 1 + αη(t) ∇L(t) 2 2 2Lν(t) ≤ 2Lαη(t)ν(t) 1 + C -1 η κ(L(t)) -1 µ(L(t)) • 2C η κ(L(t))L(t) 2LL(t)λ(L(t)) -1 = 2Lαη(t)ν(t) (1 + λ(L(t))µ(L(t))/L) .

Proof for (P3). (P3) holds trivially for α = 0 or ∇L(t) = 0. So now we assume that α = 0 and ∇L(t) = 0. By the update rule (18) and Taylor expansion, there exists ξ ∈ (0, α) such that

L(t + α) = L(t) + (θ(t + α) -θ(t)) ∇L(t) + 1 2 (θ(t + α) -θ(t)) ∇ 2 L(t + ξ)(θ(t + α) -θ(t)) ≤ L(t) -αη(t) ∇L(t) 2 2 + 1 2 α 2 η(t) 2 ∇ 2 L(t + ξ) 2 ∇L(t) 2 2 = L(t) -αη(t) 1 - 1 2 αη(t) ∇ 2 L(t + ξ) 2 ∇L(t) 2 2 .

By Lemma E.7, ∇ 2 L(t + ξ) 2 ≤ 2C η • κ(L(t + ξ)), so we have

EQUATION

Now we only need to show that L(t + α) < L(t) for all α ∈ (0, A]. Assuming this, we can have κ(L(t + ξ)) ≤ κ(L(t)) by the monotonicity of κ, and thus

L(t + α) ≤ L(t) -αη(t) (1 -αC η η(t)κ(L(t))) ∇L(t) 2 2 ≤ L(t) -αη(t) (1 -µ(L(t))) ∇L(t) 2 2 .

Now we show that L(t + α) < L(t) for all α ∈ (0, A]. Assume to the contrary that α 0 := inf{α ∈ (0, A] :

L(t + α ) ≥ L(t)} exists. If α 0 = 0, let p : [0, 1] → R, α → L(t + α), then p (0) = lim α↓0 L(t+α)-L(t) α ≥ 0, but it contradicts to p (0) = -η(t) ∇L(t) 2 2 < 0. If α 0 > 0,

then by the monotonicity of κ we have κ(L(t + ξ)) < κ(L(t)) for all ξ ∈ (0, α 0 ), and thus

L(t + α) ≤ L(t) -αη(t) (1 -µ(L(t))) ∇L(t) 2 2 < L(t),

which leads to a contradiction.

Proof for (P4). We define v(t) := θ(t) θ(t) (-∇L(t)) and u(t) := Iθ(t) θ(t) (-∇L(t))

similarly as in the analysis for gradient flow. For v(t), we have

v(t) 2 = 1 ρ(t) θ(t), -L(t) = 1 ρ(t)

• Lν(t).

Decompose ∇L(t)

2 2 = v(t) 2 2 + u(t) 2 2 .

Then by (P3), we have

L(t + α) -L(t) ≤ -αη(t)(1 -µ(L(t))) 1 ρ(t) 2 • L 2 ν(t) 2 + u 2 2 . Multiplying 1+λ(L(t))µ(L(t))/L (1-µ(L(t)))ν(t)

on both sides, we have

1 + λ(L(t))µ(L(t))/L (1 -µ(L(t)))ν(t) (L(t + α) -L(t)) ≤ -αη(t) 1 + λ(L(t))µ(L(t)) L L 2 ν(t) ρ(t) 2 + u 2 2 ν(t)

By Corollary E.6, we can bound ν(t) by ν(t) ≥ L(t)/λ(L(t)). By (P2), we have the inequality

αη(t)ν(t) 1 + λ(L(t))µ(L(t)) L ≥ ρ(t+α) 2 -ρ(t) 2 2L

. So we further have

1 + λ(L(t))µ(L(t))/L (1 -µ(L(t)))L(t)/λ(L(t)) (L(t+α)-L(t)) ≤ - 1 ρ(t) 2 (ρ(t+α) 2 -ρ(t) 2 ) L 2 + ρ(t) 2 2Lν(t) 2 u 2 2

From the definition φ, it is easy to see that -φ

(L(t)) ≥ 1+λ(L(t))µ(L(t))/L (1-µ(L(t)))L(t)/λ(L(t)) . Let ψ(x) = -log x, then ψ (x) = -1

x . Combining these together gives

φ (L(t))(L(t + α) -L(t)) + ψ (ρ(t) 2 )(ρ(t + α) 2 -ρ(t) 2 ) L 2 + ρ(t) 2 2Lν(t) 2 u 2 2 ≥ 0

Then by convexity of φ and ψ, we have

(φ(L(t + α)) -φ(L(t))) + log 1 ρ(t + α) 2 -log 1 ρ(t) 2 L 2 + ρ(t) 2 2Lν(t) 2 u 2 2 ≥ 0

And by definition of γ, this can be re-written as

log γ(t + α) -log γ(t) = (φ(L(t + α)) -φ(L(t))) + L log 1 ρ(t + α) -log 1 ρ(t) ≥ -log 1 ρ(t + α) 2 -log 1 ρ(t) 2 ρ(t) 2 2Lν(t) 2 u 2 2 = ρ(t) 2 Lν(t) 2 u 2 2 • log ρ(t + α) ρ(t) .

Proof for (P1). By (P4), log γ(t + α) ≥ log γ(t) ≥ log γ(t 0 ). Note that φ(x) ≥ log log 1

x . So we have γ(t + α) > γ(t + α) ≥ γ(t 0 ), which completes the proof.

For showing the third proposition in Theorem E.2, we use (P1) to give a lower bound for ∇L(t) 2 , and use (P3) to show the speed of loss decreasing. Then it can be seen that L(t) → 0 and ρ(t) → +∞. By Lemma E.1, we then have |γ -γ| → 0.

Lemma E.10.

Let E 0 := L(t 0 ) 2 (log 1 L(t0) ) 2-2/L . Then for all t > t 0 , E(L(t)) ≥ 1 2 L 2 γ(t 0 ) 2/L t-1 τ =t0 η(τ ) for E(x) := L(t0) x 1 min{u 2 (log 1 u ) 2-2/L , E 0 } du.

Therefore, L(t) → 0 and ρ(t) → +∞ as t → ∞.

Proof. For any integer t ≥ t 0 , µ(L(t)) ≤ 1 2 and ∇L(t) 2 ≥ v(t) 2 . Combining these with (P3), we have

L(t + 1) -L(t) ≤ - 1 2 η(t) v(t) 2 2 = - 1 2 η(t) L 2 ν(t) 2 ρ(t) 2 .

Proof. According to the update rule, we have

θ(t + 1) -θ(t) 2 = 1 ρ(t + 1) θ(t + 1) - ρ(t + 1) ρ(t) θ(t) 2 ≤ 1 ρ(t + 1) θ(t + 1) -θ(t) 2 + ρ(t + 1) ρ(t) -1 θ(t) 2 = η(t) ρ(t + 1) ∇L(t) 2 + 1 - ρ(t) ρ(t + 1)

.

By ( 16), ∇L(t) 2 ≤ B1ν(t) γ(t)ρ(t) . So we can bound the first term as

η(t) ρ(t + 1) ∇L(t) 2 ≤ B 1 γ(t) • η(t)ν(t) ρ(t + 1)ρ(t) ≤ B 1 γ(t) • ρ(t + 1) 2 -ρ(t) 2 2Lρ(t + 1)ρ(t) = B 1 2Lγ(t) • ρ(t + 1) 2 -ρ(t) 2 ρ(t + 1) 2 • ρ(t + 1) ρ(t) ≤ B 1 Lγ(t) • ρ(t + 1) ρ(t) log ρ(t + 1) ρ(t)

where the last inequality uses the inequality a-b a ≤ log(a/b). Using this inequality again, we can bound the second term by

1 - ρ(t) ρ(t + 1) ≤ log ρ(t + 1) ρ(t) .

Combining these together gives θ(t + 1) -θ(t)

2 ≤ B1 Lγ(t) • ρ(t+1) ρ(t) + 1 log ρ(t+1) ρ(t) .

Now we are ready to prove Theorem E.3.

Proof for 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 ≥ 0 , there exists a sequence of {t m : m ∈ N} such that t m ↑ +∞, θ(t m ) → θ, and β(t m ) → 1.

We only need to change the choices of s m , s m , t m in the proof for Lemma C.12. We choose s m > t m-1 to be a time such that

θ(s m ) -θ 2 ≤ m and 1 L log   lim t→+∞ γ(t) γ(s m )   ≤ 3 m .

Then we let s m > s m be the minimum time such that log ρ(s m ) ≥ log ρ(s m ) + m . According to Theorem E.2, s m and s m must exist. Finally, we construct t m ∈ {s m , . . . , s m -1} to be a time that

β(t m ) -2 -1 ≤ 2 m ,

where the existence can be shown by ( 22). To see that this construction meets our requirement, note that

β(t m ) -2 -1 ≤ 2 m → 0 and θ(t m ) -θ 2 ≤ θ(t m ) -θ(s m ) 2 + θ(s m ) -θ 2 ≤ B 1 Lγ(t 0 ) e m + 1 • m + m → 0,

where the last inequality is by Lemma E.11.

E.6 PROOF FOR THEOREM E.5

Proof. By a similar analysis as Lemma D.4, we have

E(x) = L(t0) x Θ 1 u 2 (log 1 u ) 2-2/L du = 1/x 1/L(t0) Θ 1 (log u) 2-2/L du = Θ 1 x(log 1 x ) 2-2/L .

We can also bound the inverse function E -1 (y) by Θ 1 y(log y) 2-2/L . With these, we can use a similar analysis as Theorem A.10 to prove Theorem E.5.

First, using a similar proof as for (17), we have ρ L = Θ(log 1 L ). So we only need to show L(t) = Θ( 1 T (log T ) 2-2/L ). With a similar analysis as for (P3) in Lemma E.9, we have the following bound for L(τ + 1) -L(τ ):

L(τ + 1) -L(τ ) ≥ -η(τ )(1 + µ(L(τ ))) ∇L(τ ) 2 2 .

Using the fact that µ ≤ 1/2, we have L(τ + 1) -L(τ ) ≥ -3 2 η(τ ) ∇L(τ ) 2 2 . By Lemma E.7, ∇L(τ ) 2 ≤ 2C η κ(L(τ ))L(τ ). Using a similar proof as for Lemma E.10, we can show that E(L(t)) ≤ O(T ). Combining this with Lemma E.10, we have E(L(t)) = Θ(T ). Therefore,

L(t) = Θ( 1 T (log T ) 2-2/L ).

F GRADIENT DESCENT: GENERAL LOSS FUNCTIONS:

It is worth to note that the above analysis can be extended to other loss functions. For this, we need to replace (B3) with a strong assumption (S3), which takes into account the second-order derivatives of f . (S3). The loss function (q) can be expressed as (q) = e -f (q) such that (S3.1). f : R → R is C 2 -smooth. (S3.2). f (q) > 0 for all q ∈ R. (S3.3). There exists b f ≥ 0 such that f (q)q is non-decreasing for q ∈ (b f , +∞), and f (q)q → +∞ as q → +∞.

(S3.4). Let g : [f (b f ), +∞) → [b f , +∞) be the inverse function of f on the domain [b f , +∞). There exists p ≥ 0 such that for all x > f (b f ), y > b f , g (x) g (x) ≤ p x and f (y) f (y) ≤ p 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 f is C 2 -smooth rather than C 1 -smooth.

(S3.4) can also be written in the following form:

EQUATION

That is, log g (x) and log f (y) grow no faster than O(log x) and O(log y), respectively. In fact, (B3.4) can be deduced from (S3.4). Recall that (B3.4) ensures that Θ(g (x)) = g (Θ(x)) and Θ(f (y)) = f (Θ(y)). Thus, (S3.4) also gives us the interchangeability between f , g and Θ.

Lemma Therefore, we have g (x) ≤ θ -p g (θx) ≤ Kg (θx) and f (y) ≤ θ -p f (θy) ≤ Kf (θx).

To extend our results to general loss functions, we need to redefine κ(x), λ(x), φ(x), C η , H(x) in order. For κ(x) and λ(x), we redefine them as follows:

κ(x) := sup w(log 1 w ) 2-2/L g (log 1 w ) 2 : w ∈ (0, x] λ(x) := g (log 1 x ) g(log 1

x )

.

By Lemma D.1,

w(log 1 w ) 2-2/L g (log 1 w ) 2

= O w(log 1 w ) 4-2/L /g(log 1 w ) 2 → 0. So κ(x) is well-defined. Using λ(x), we can define φ(x) and γ(θ) as follows.

φ (x) := -sup λ(w) w (1 + 2(1 + λ(w)/L)µ(w)) : w ∈ [x, L(t 0 )] φ(x) := log g(log 1 x ) + x 0 φ (w) + λ(w) w dw γ(θ) := e φ(L(θ)) ρ L .

Using a similar argument as in Lemma E.1, we can show that γ(θ) is well-defined and γ(θ) < γ(θ) := g(log 1 L )/ρ L ≤ γ(θ). When L(θ) → 0, we also have γ(θ)/γ(θ) → 1. For C η , we define it to be the following.

C η := 1 2 B 1 B 0 γ(t 0 ) p B 1 + 2 p+1 log 1 L(t0) (pB 1 + B 2 ) B 0 γ(t 0 ) p min γ(t 0 ) -2+2/L , B -2+2/L 0 .

Finally, the definitions for µ(x) := (log 1 L(t0) )/(2 log 1 x ) and H(x) := µ(x)/(C η κ(x)) in (S5) remain unchanged except that κ(x) and C η now use the new definitions.

Similar as gradient flow, we define ν(t) := N n=1 e -f (qn(t)) f (q n (t))q n (t). The key idea behind the above definitions is that we can prove similar bounds for ν(t), ∇L 2 , ∇ 2 L 2 as Corollary E.6 and Lemma E.7. Proof. Note that a direct corollary of ( 23) is that f

Lemma F.2. θ(t), -∇L(t) = Lν(t). If L(t) < e -f (b f ) , then ν(t) ≥ L(t) λ(L(t))

(x 1 ) ≤ f (x 2 )(x 1 /x 2 ) p for x 1 ≥ x 2 > b f . So we have f (q n ) ≤ f g(log 1 L ) q n g(log 1 L ) p = 1 g (log 1 L ) q n /ρ L γ p ≤ R g (log 1 L )

,

where R := (B 0 /γ(t 0 )) p . Applying (S3.4), we can also deduce that

|f (q n )| ≤ p q n • f (q n ) ≤ pR g(log 1 L )g (log 1 L )

. Now we bound ∇L 2 and ∇ 2 L 2 . By the chain rule, we have

∇L 2 = - N n=1 e -f (qn) f (q n )∇q n 2 ≤ B 1 R • Lρ L-1 g (log 1 L ) ∇ 2 L 2 = N n=1 e -f (qn) (f (q n ) 2 -f (q n ))∇q n ∇q n -f (q n )∇ 2 q n 2 ≤ N n=1 e -f (qn) R 2 g (log 1 L ) 2 + pR g(log 1 L )g (log 1 L ) B 2 1 ρ 2L-2 + R g (log 1 L ) B 2 ρ L-2 ≤ Lρ 2L-2 g (log 1 L ) 2 (R + pλ(L)) B 2 1 + g (log 1 L ) ρ L B 2 R.

For ρ we have γ(t 0 )ρ L ≤ log 1 L ≤ B 0 ρ L , so we can bound ρ 2L-2 by ρ 2L-2 ≤ M (log 1 L ) 2L-2 , where M := min γ(t 0 ) -2+2/L , B

-2+2/L 0 . By Lemma F.2, we have λ(L) ≤ 2 p+1 1 log 1 L ≤ 2 p+1 log 1 L(t 0 )

, and also

g (log 1 L ) ρ L = λ(L) • γ ≤ 2 p+1 B1 log 1 L(t 0 )

. Combining all these formulas together gives

∇L 2 2 ≤ B 2 1 R 2 M L 2 g (log 1 L ) 2 log 1 L 2-2/L ≤ 2C η κ(L)L ∇ 2 L 2 ≤ R + p2 p+1 log 1 L(t0) B 2 1 + 2 p+1 B 1 B 2 log 1 L(t0) RM L g (log 1 L ) 2 log 1 L 2-2/L ≤ 2C η κ(L),

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 E.2, E.3, E.4 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 (S1), (A2), ( S3), (A4), (S5), we have the following tight rates for training loss and weight norm:

L(t) = Θ g(log T ) 2/L T (log T ) 2 and ρ(t) = Θ(g(log T ) 1/L ),

where

T = t-1 τ =t0 η(τ ).

G EXTENSION: MULTI-CLASS CLASSIFICATION:

In this section, we generalize our results to multi-class classification with cross-entropy loss. This part of analysis is inspired by Theorem 1 in (Zhang et al., 2019) , which gives a lower bound for the gradient in terms of the loss L.

Since now a 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 Φ(θ; x) ∈ R C . We use Φ j (θ; .

The margin for a single data point (x n , y n ) is defined to be q n (θ) := Φ yn (θ; x n )max j =yn {Φ j (θ; x n )}, and the margin for the entire dataset is defined to be q min (θ) = min n∈[N ] q n (θ). We define the normalized margin to be γ(θ) := q min ( θ) = q min (θ)/ρ L , where ρ := θ 2 and θ := θ/ρ ∈ S d-1 as usual.

Let (q) := log(1+e -q ) be the logistic loss. Recall that (q) satisfies (B3). Let f (q) = -log (q) = -log log(1 + e -q ). Let g be the inverse function of f . So g(q) = -log(e e -q -1).

The cross-entropy loss can be rewritten in other ways. Let s nj := Φ yn (θ; x n ) -Φ j (θ; x n ). Let qn := -LSE({-s nj : j = y n }) = -log j =yn e -snj . Then qn) .

L(θ) := N n=1 log   1 + j =yn e -snj   = N n=1 log(1 + e -qn ) = N n=1 (q n ) = N n=1 e -f (

Gradient Flow. For gradient flow, we assume the following:

(M1). (Regularity). For any fixed x and j ∈ [C], Φ j ( • ; x) is locally Lipschitz and admits a chain rule;

(M2). (Homogeneity). There exists L > 0 such that ∀j ∈ [C], ∀α > 0 : Φ j (αθ; x) = α L Φ j (θ; x);

(M3). (Cross-entropy Loss). L(θ) is defined as the cross-entropy loss on the training set;

(M4). (Separability). There exists a time t 0 such that L(t 0 ) < log 2.

If L < log 2, then j =yn e -snj < 1 for all n ∈ [N ], and thus s nj > 0 for all n ∈ [N ], j ∈ [C]. So (M4) ensures the separability of training data.

Definition G.1. For cross-entropy loss, the smoothed normalized margin γ(θ) of θ is defined as

γ(θ) := -1 (L) ρ L = -log(e L -1) ρ L ,

where -1 (•) is the inverse function of the logistic loss (•). It can be shown that Lemma B.5, which asserts that ν(t) ≥ g(log 1 L ) g (log 1 L ) L, still holds for this new definition of ν(t). By definition, s nj ≥ q n for j = y n . Also note that e -qn ≥ e -qn . So s nj ≥ q n ≥ qn . Then we have qn) . Then using Lemma B.5 for logistic loss can conclude that ν(t) ≥

ν(t) ≥ N n=1 j =yn e -snj 1 + j =yn e -snj • qn = N n=1 e -qn 1 + e -qn • qn = N n=1 e -f (qn) f (q n )q n . Note that L = N n=1 e -f (

g(log 1 L ) g (log 1 L ) L.

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 (M1) with (S1) and make the assumption (S5) on the learning rate.

(S1). (Smoothness). For any fixed x and j ∈

[C], Φ j ( • ; x) is C 2 -smooth;

(S5). (Learing rate condition). t≥0 η(t) = +∞ and η(t) ≤ H(L(θ(t))).

Here H(x) := µ(x)/(C η κ(x)) is defined to be the same as in Appendix F (when (•) is set to logistic loss) except that we use another C η which will be specified later.

We only need to show that Lemma F.2 and Lemma F.3 continue to hold. Using the same argument as we do for gradient flow, we can show that γ(t) and λ(x) do satisfy the propositions in Lemma F.2. For Lemma F.3, we first note the original definition of C η involves B 0 , B 1 , B 2 , which are undefined in the multi-class setting. So now we redefine them as

B 0 := sup s nj : θ ∈ S d-1 , n ∈ [N ], j ∈ [C] , B 1 := sup ∇s nj 2 : θ ∈ S d-1 , n ∈ [N ], j ∈ [C] , B 2 := sup ∇ 2 s nj 2 : θ ∈ S d-1 , n ∈ [N ], j ∈ [C] .

By the property of LSE, we can use B 0 , B 1 , B 2 to bound qn , ∇q n , ∇ 2 qn .

qn ≤ q n ≤ B 0 ρ L , ∇q n 2 = C j=1 e -snj C k=1 e -s nk ∇s nj 2 ≤ C j=1 e -snj C k=1 e -s nk ∇s nj 2 ≤ B 1 ρ L-1 , ∇ 2 qn 2 = C j=1    e -snj C k=1 e -s nk (∇ 2 s nj -∇s nj ∇s nj ) + e -2snj C k=1 e -s nk 2 ∇s nj ∇s nj    2 ≤ B 2 ρ L-2 + 2B 2 1 ρ 2L-2 .

Using these bounds, we can prove with the constant C η defined as follows:

C η := 1 2 B 0 γ(t 0 ) p + p2 p+1 log 1 L(t0) B 2 1 + (2 log 2) B 2 ρ(t 0 ) L + 2B 2 1 B 0 γ(t 0 ) p M, where M := min γ(t 0 ) -2+2/L , B -2+2/L 0 .

H EXTENSION: MULTI-HOMOGENEOUS MODELS:

In this section, we extend our results to multi-homogeneous models. For this, the main difference from the proof for homogeneous models is that now we have to separate the norm of each homogeneous parts of the parameter, rather than consider them as a whole. So only a 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 to extend the results to gradient descent.

Let Φ(w 1 , . . . , w m ; x) be (k 1 , . . . , k m )-homogeneous. Let ρ i = w i 2 and ŵi = wi wi 2 . The smoothed normalized margin defined in (5) can be rewritten as follows:

Definition H.1. For a multi-homogeneous model with loss function (•) satisfying (B3), the smoothed normalized margin γ(θ) of θ is defined as

γ(θ) := g(log 1 L ) m i=1 ρ ki i = -1 (L) m i=1 ρ ki i .

We only prove the generalized version of Lemma 5.1 here. The other proofs are almost the same.

Lemma H.2. For all t > t 0 ,

EQUATION

)

Proof. Note that 

d dt log γ = d dt log g(log 1 L ) - m i=1 k i log ρ i = g (log 1 L ) g(log 1 L ) • 1 L • - dL dt - m i=1 k 2 i ν(t) ρ 2 i ≥ 1 ν(t) • - dL dt - m i=1 k 2 i ν(t) ρ 2 i ≥ 1 ν(t) • - dL dt - m i=1 k 2 i ν(t) 2 ρ 2 i .

On 

d dt log γ ≥ 1 ν(t) m i=1 dw i dt 2 2 -ŵi , dw i dt 2 = 1 ν(t) (I -ŵi ŵ i ) dw i dt 2 2

.

By the chain rule,

d ŵi dt = 1 ρi (I -ŵi ŵi ) dwi dt for a.e. t > 0. So we have d dt log γ ≥ m i=1 ρ 2 i ν(t) d ŵi dt 2 2 = m i=1 k i d dt log ρ i -1 d ŵi dt 2 2 .

For cross-entropy loss, we can combine the proofs in Appendix G to show that Lemma H.2 holds if we use the following definition of the smoothed normalized margin: Definition H.3. For a multi-homogeneous model with cross-entropy, the smoothed normalized margin γ(θ) of θ is defined as

γ = -1 (L) m i=1 ρ ki i = -log(e L -1) m i=1 ρ ki i .

where -1 (•) is the inverse function of the logistic loss (•).

The only place we need to change in the proof for Lemma H.2 is that instead of using Lemma B.5, we need to prove ν(t) ≥ g(log 1 L ) g (log 1 L ) L in a similar way as in Lemma G.2. The other parts of the proof are exactly the same as before.

I CHAIN RULES FOR NON-DIFFERENTIABLE FUNCTIONS:

In this section, we provide some background on the chain rule for non-differentiable functions. The ordinary chain rule for differentiable functions is a very useful formula for computing derivatives in calculus. However, for non-differentiable functions, it is difficult to find a natural definition of subdifferential so that the chain rule equation holds exactly. To solve this issue, Clarke proposed Clarke's subdifferential (Clarke, 1975; 1990; Clarke et al., 2008) 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 z 1 , . . . , z n : R d → R and f : R n → R be locally Lipschitz functions. Let (f • z)(x) = f (z 1 (x), . . . , z n (x)) be the composition of f and z. Then,

∂ • (f • z)(x) ⊆ conv n i=1 α i h i : α ∈ ∂ • f (z 1 (x), . . . , z n (x)), h i ∈ ∂ • z i (x) .

For analyzing gradient flow, the chain rule is crucial. For a differentiable loss function L(θ), we can see from the chain rule that the function value keeps decreasing along the gradient flow dθ(t) dt = -∇L(θ(t)) :

EQUATION

)

For gradient flow, we have

dθ dt = N e -h ∇h du dt = 1 ρ (1 -u 2 ) dx dt -uv dy dt -uw dz dt = N e -h ρ L-2 -(1 -u 2 ) ∂f ∂u + uv ∂f ∂v dv dt = 1 ρ (1 -v 2 ) dy dt -uv dx dt -vw dz dt = N e -h ρ L-2 -(1 -v 2 ) ∂f ∂v

+ uv ∂f ∂u By writing down the movement of (u, v) in the polar coordinate system, we have

dr dt = u r • du dt + v r • dv dt = - N e -h ρ L-2 r u(1 -r 2 ) ∂f ∂u + v(1 -r 2 ) ∂f ∂v = -N e -h ρ L-2 (1 -r 2 ) ∂f ∂r dϕ dt = - v r 2 • du dt + u r 2 • dv dt = N e -h ρ L-2 r 2 v ∂f ∂u -u ∂f ∂v = -N e -h ρ L-2 1 r 2 •

∂f ∂ϕ For ψ = 0, the partial derivatives of f with respect to r and ϕ can be evaluated as follows:

∂f ∂r = d dr e -1 1-r 2 -e -1 1-r 2 C (r) sin ψ -e -1 1-r 2 C(r) cos ψ • ∂ψ ∂r = d dr e -1 1-r 2 + e -1 1-r 2 C(r) d dr 1 1 -r 2 = - 2r (1 -r 2 ) 2 (1 -C(r))e -1 1-r 2 . ∂f ∂ϕ = -e -1 1-r 2 C(r) cos ψ • ∂ψ ∂ϕ = -e -1 1-r 2 C(r). So if ψ = 0, then dψ dt = 0 by the direct calculation below: dψ dt = dϕ dt - d dr 1 1 -r 2 • dr dt = N e -h ρ L-2 - 1 r 2 ∂f ∂ϕ + 2r (1 -r 2 ) 2 ∂f ∂r = N e -h ρ L-2 e -1 1-r 2 1 r 2 + 4r 2 (1 -r 2 ) 4 C(r) - 4r 2 (1 -r 2 ) 4 = 0. Proof for r → 1. Let (ū, v) be a convergent point of {(u, v) : t ≥ 0}. Define r = √ u 2 + v 2 .

It is easy to see that r ≤ 1 from the normalization of θ in the definition. According to Theorem 4.4, we know that (ū, v) is a stationary point of γ

EQUATION

1-r 2 = 0, which again leads to a contradiction. Therefore, r = 1, and thus r → 1.

K EXPERIMENTS:

To validate our theoretical results, we conduct several experiments. We mainly focus on MNIST dataset. We trained two models with Tensorflow. The first one (called the CNN with bias) is a standard 4-layer CNN with exactly the same architecture as that used in MNIST Adversarial Examples Challenge5 . The layers of this model can be described as conv-32 with filter size 5×5, max-pool, conv-64 with filter size 3 × 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 input data while retains the homogeneity in parameters. We initialize all layer weights by He normal initializer (He et 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] 32×32 by dividing 255 for each pixel.

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 now on, we view the bias term in the first layer as a 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 4.4). So for the CNN without bias, we define the normalized margin γ as the margin divided by the product of the L 2 -norm of all layer weights. Here we compute the L 2 -norm of a layer weight parameter after flattening it into a one-dimensional vector. For the CNN with bias, we still compute the smoothed normalized margin in this way. When computing the L 2norm 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 and 4 . 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 is rather slow. The results are shown in Figure 1 in Section 1. We also tried other learning rates other than 0.01, and similar phenomena can be observed.

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 at each epoch based on the current training loss (in a similar way as the line search method). See Appendix L.1 for the details. As shown in Figure 1 , SGD with loss-based learning rate scheduling decreases the training loss exponentially faster than SGD with constant learning rate. Also, a rapid growth of normalized margin is observed for both CNNs. Note that with this scheduling the training loss can be as small as 10 -800 , which may lead to numerical issues. To address such issues, we applied some re-parameterization 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, we 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 ×2, max-pool, conv-128 ×2, max-pool, conv-256 ×3, max-pool, conv-512 ×3, max-pool, conv-512 ×3, max-pool, fc-10 in order, where each conv has filter size 3 × 3. We train two networks: one is exactly the same as the VGGNet we described, and the other one is the VGGNet without any bias terms except those in the first layer (similar as in the experiments on MNIST). The experiment results are shown in Figure 5 and 6. We can see that the normalize margin is increasing over time. Test Accuracy. Previous works on margin-based generalization bounds (Neyshabur et al., 2018; Bartlett et al., 2017; Golowich et al., 2018; Li et al., 2018a; Wei et al., 2019; Banburski et We use the standard method for evaluating L 2 -robustness in (Carlini & Wagner, 2017) and the source code from the authors with default hyperparameters6 . We plot the robust accuracy (the percentage of data with robustness > ) for the training set in the figures on the first row of Figure 8 . It can be seen from the figures that for small (e.g., < 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-4 becomes marginal or nonexistent in certain intervals of , but model-1 to model-4 still have an increasing order of robust accuracy and the improvement of model-5 upon model-1 is always significant. This shows that training longer can help to improve the L 2 -robust accuracy on the training set.

We also evaluate the robustness on the test set, in which a misclassified test sample is considered have robustness 0, and plot the robust accuracy in the figures on the second row of Figure 8 . It can be seen from the figures that for small (e.g., < 0.2), the curves of the robust accuracy of model-1 to model-5 are almost indistinguishable. However, for relatively large (e.g., > 0.2), again, model-1 to model-4 have an increasing order of robust accuracy and the improvement of   e -F , where log1p(x) is a 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 2. If q n (θ) ≤ Q for some n ∈ [B], then LB (θ) = Ω(e -Q ) is in the range of float64, so we can compute R B (θ) by ( 28) directly except that we need to use a numerical stable implementation of log(1 + x). For q n (θ) > Q, arithmetic underflow can occur. By Taylor expansion of log(1 + x), we know that when x is small enough log(1 + x) ≈ x in the sense that the relative error |log(1+x)-x| log(1+x) = O(x). Thus, we can do the following approximation for q n (θ) > Q, and only introduce a relative error of O(Ce -Q ) (recall that C is the number of classes). Using a numerical stable implementation of LSE, we can compute qn easily. Then the RHS of (29) can be rewritten as e -(qn(θ)+ F ) . Note that computing e -(qn(θ)+ F ) does not have underflow or overflow problems if F is a good approximation for log LB (θ).

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 parameterize the learning rate as η = η • e F . Then it is easy to see that taking a step of gradient descent for L B (θ) with learning rate η is equivalent to taking a step for R B (θ) with η. Thus, as long as η can fit into float64, we can perform gradient descent on R B (θ) to ensure numerical stability.

The Choice of F. The only question remains is how to choose F. In our experiments, we set F(t) := log L(t -1) to be the training loss at the end of the last epoch, since the training loss cannot change a lot within one single epoch. For this, we need to maintain log L(t) during training. This can be done as follows: after evaluating the relative training loss R(t) on the whole training set, we can obtain log L(t) by adding F(t) and log R(t) together.

It is worth noting that with this choice of F, η(t) = α(t) in the loss-based learning rate scheduling.

As shown in the right figure of Figure 4 , α(t) is always between 10 -9 and 10 0 , which ensures the numerical stability of backward pass.

:

Note that this does NOT mean the training loss is 0.

Code available: https://github.com/vfleaking/max-margin

Assuming the convergence of the parameter direction may seem quite reasonable, however, the problem here can be quite subtle in theory. In Appendix J, we present a smooth homogeneuous function f , based on the Mexican hat function(Absil et al. (2005)), such that even the direction of the parameter does not converge along gradient flow (it moves around a cirle when t increases).

Indeed, (B3.4) is not needed for showing Lemma A.5 and Theorem A.7.

https://github.com/MadryLab/mnist_challenge

https://github.com/carlini/nn_robust_attacks

Figures and Tables:

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 is fitted, but the growth rate is slow (≈ 1.8 × 10 -4 after 10000 epochs). (b) TrainingCNNs 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 normalized margin (right) increases rapidly after the model is fitted (≈ 1.2 × 10 -3 after 10000 epochs, 10× larger than that of SGD with learning rate 0.01). Experimental details are in Appendix K.

Training Nonlinear Classifiers. Soudry et al. (2018a) analyzed the case where there is only one trainable layer of a ReLU network. Xu et al. (2018) 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 et al., 2019a) which we discuss in details below.

Corollary B.3 can be used to derive an exact formula for the weight growth during training. Theorem B.4. For a.e. t ≥ 0, 1 2

for a.e. t > 0 by Lemma I.3; on the other hand, Lν(t) = θ, dθ dt by Theorem B.4. Combining these together yields

F.1. (S3.4) implies (B3.4) with b g = max{2f (b f ), f (2b f )} and K = 2 p . Proof. Fix x ∈ (b g , +∞), y ∈ (g(b g ), +∞) and θ ∈ [1/2, 1). Integrating (23) on both sides of the inequalities from θx to x and θy to y, we have|log g (x) -log g (θx)| ≤ p • log 1 θ and |log f (y) -log f (θy)| ≤ p • log 1 θ .

and λ(L(t)) has the lower bound λ(L(t)) ≤ 2 p+1 log 1 It can be easily proved by combining Theorem B.4, Lemma B.5 and Lemma D.1 together. Lemma F.3. For any θ, if L(θ) ≤ L(t 0 ), γ(θ) ≥ γ(t 0 ), then ∇L(θ) 2 2 ≤ 2C η κ(L(θ))L(θ) and ∇ 2 L(θ) 2 ≤ 2C η κ(L(θ)).

x) ∈ R to denote the j-th output of Φ on the input x ∈ R dx . A dataset is denoted byD = {x n , y n } N n=1 = {(x n , y n ) : n ∈ [N ]},where x n ∈ R dx is a data input and y n ∈ [C] is the corresponding label. The loss function of Φ on the dataset D is defined as L(θ) := N n=1 -log e Φy n (θ;xn)C j=1 eΦj (θ;xn)

. s nj (θ) ≥ 1 ∀n ∈ [N ], ∀j ∈ [C] \ {y n }Most of our proofs are very similar as before. Here we 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 Definition G.1.Proof. Define ν(t) by the following formula: =yn e -snj s nj 1 + j =yn e -snj .Using a similar argument as in Theorem B.4, it can be proved that 1 2 dρ 2 dt = Lν(t) for a.e. t > 0.

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.

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 normalized margin with the original definition (middle) increases rapidly after the model is fitted. The right figure shows the change of the relative learning rate α(t) (see (27) for its definition) during training.

Figure 5: Training VGGNet with and without bias on CIFAR-10, using SGD with learning rate 0.1.

Perform forward pass to compute the values of s nj with float32, and convert them into float64;Step 2. Let Q := 30. If q n (θ) > Q for all n ∈ B, then we computeR B (θ) = 1 B n∈B e -(qn(θ)+ F ) ,where qn (θ) := -LSE({-s nj : j = y n }) = -log j =yn e -snj is evaluated in a numerically stable way; otherwise, we compute R B

Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel. 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. 9709-9721. Curran Associates, Inc., 2019. Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, 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 maxmargin classifier under relu models? arXiv preprint arXiv:1806.04339, 2018. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. Hongyi Zhang, Yann N. Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization. In International Conference on Learning Representations, 2019.

Table content: <table/>

-L )-additive approximation for γ(θ) if L is sufficiently small.A.3 THEOREMSNow we state our main theorems. For the monotonicity of the normalized margin, we have the following theorem. The proof is provided in Appendix B.

Table content: <table/>

t 1 ) .

Table content: <table><tr><td>Proof. By Lemma B.4, d dt log ρ = 1 2ρ 2</td><td>dρ 2</td></tr></table>

≥ t 0 . By the chain rule and Lemma B.5, we have

Table content: <table><tr><td>d dt log ρ i = 1 2ρ 2 i</td><td>dρ 2 i dt = kiν(t) ρ 2</td></tr></table>

the one hand, -dL dt =

Table content: <table><tr><td>w i , dwi dt</td><td>m i=1 by Theorem B.4. Combining these together yields dwi dt 2 2 for a.e. t &gt; 0 by Lemma I.3; on the other hand, k i ν(t) =</td></tr></table>

al., Figure 8: L 2 -robustness of the models of CNNs without bias trained for different number of epochs (see Table 1 for the statistics of each model). Figures on the first row show the robust accuracy on the training set, and figures on the second row show that on 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 to model-4, noticeable robust accuracy improvements can be observed. The improvement of model-5 upon model-4 is marginal or nonexistent for some , but the improvement upon model-1 is always significant. 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

Table content: <table><tr><td/><td/><td/><td>model-1</td><td>model-2</td><td colspan="3">model-3</td><td colspan="2">model-4</td><td colspan="2">model-5</td></tr><tr><td colspan="2">100%</td><td/><td/><td/><td/><td>100%</td><td/><td/><td/><td/></tr><tr><td>accuracy (train)</td><td>92% 94% 96% 98%</td><td/><td/><td/><td/><td>20% 40% 60% 80%</td><td/><td/><td/><td/></tr><tr><td/><td>90%</td><td>0.0</td><td>0.2</td><td>0.4</td><td>0.6</td><td>0%</td><td>0</td><td>2</td><td>4</td><td>6</td><td>8</td></tr><tr><td colspan="2">100%</td><td/><td/><td/><td/><td>100%</td><td/><td/><td/><td/></tr><tr><td>accuracy (test)</td><td>92% 94% 96% 98%</td><td/><td/><td/><td/><td>20% 40% 60% 80%</td><td/><td/><td/><td/></tr><tr><td/><td>90%</td><td>0.0</td><td>0.2</td><td>0.4</td><td>0.6</td><td>0%</td><td>0</td><td>2</td><td>4</td><td>6</td><td>8</td></tr><tr><td colspan="3">model-1</td><td>38</td><td/><td>10 -10.04</td><td/><td colspan="2">5.65 × 10 -5</td><td/><td>100%</td><td>99.3%</td></tr><tr><td colspan="3">model-2</td><td>75</td><td/><td>10 -15.12</td><td/><td colspan="2">9.50 × 10 -5</td><td/><td>100%</td><td>99.3%</td></tr><tr><td colspan="3">model-3</td><td>107</td><td/><td>10 -20.07</td><td/><td colspan="2">1.30 × 10 -4</td><td/><td>100%</td><td>99.3%</td></tr><tr><td colspan="3">model-4</td><td>935</td><td colspan="2">10 -120.01</td><td/><td colspan="2">4.61 × 10 -4</td><td/><td>100%</td><td>99.2%</td></tr><tr><td colspan="3">model-5</td><td>10000</td><td colspan="2">10 -881.51</td><td/><td colspan="2">1.18 × 10 -3</td><td/><td>100%</td><td>99.1%</td></tr></table>

Peer review (iclr2020):
This is a strong deep learning theory paper, and I recommend to accept. This 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. This 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. I 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. Comments: The 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.* ----------------------------------------------------- I have read the rebuttal and I maintain my score.