Gradient Descent Maximizes the Margin of Homogeneous Neural Networks

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 ${\bm{w}}$, and the class prediction for any data point ${\bm{x}}$ is determined by the sign of ${\bm{w}}^{\top}{\bm{x}}$. Therefore, only the direction ${\bm{w}}/\|{\bm{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 ${\bm{w}}$ converges to the direction that maximizes the $L^{2}$-margin while the norm of ${\bm{w}}$ diverges to $+\infty$, if we train ${\bm{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 $\{{\bm{w}}_{t}\}$ such that every ${\bm{w}}_{t}$ is a global minimum of the $L^{2}$-regularized loss $\mathcal{L}({\bm{w}})+\frac{\lambda_{t}}{2}\|{\bm{w}}\|_{2}^{2}$ with $\lambda_{t}\to 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 $\Phi$ is said to be (positively) homogeneous if there is a number $L>0$ (called the order) such that the network output $\Phi({\bm{\theta}};{\bm{x}})$, where ${\bm{\theta}}$ stands for the parameter and ${\bm{x}}$ stands for the input, satisfies the following:

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).

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:

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.

Separability. The neural network can separate the training data during training (i.e., the neural network can achieve $100\%$ training accuracy)Note that this does NOT mean the training loss is 0..

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 ${\bm{\theta}}$ is important for making predictions, and one can see that the margin $\gamma({\bm{\theta}})$ scales linearly with $\|{\bm{\theta}}\|_{2}^{L}$, when fixing the direction of ${\bm{\theta}}$. To compare margins among ${\bm{\theta}}$ in different directions, it makes sense to study the normalized margin, $\bar{\gamma}({\bm{\theta}}):=\gamma({\bm{\theta}})/\|{\bm{\theta}}\|_{2}^{L}$.

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.

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 $\{{\bm{\theta}}(t)/\left\|{\bm{\theta}}(t)\right\|_{2}:t>0\}$ is along the direction of a KKT point of the max-margin 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.

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.Code available: https://github.com/vfleaking/max-margin 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).

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). Subsequent works extended this result in several ways: Nacson et al. (2019c) extended the results to the case of stochastic gradient descent; Gunasekar et al. (2018a) considered other optimization methods; Nacson et al. (2019b) considered other loss functions including those with poly-exponential tails; Ji & Telgarsky (2018; 2019c) characterized the convergence of weight direction without assuming separability; Ji & Telgarsky (2019b) proved a tighter convergence rate for the weight direction.

Those results on linear logistic regression have been generalized to deep linear networks. Ji & 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; Rudin et al., 2004; 2007; Schapire & Freund, 2012; Shalev-Shwartz & Singer, 2010; Telgarsky, 2013) and Normalized Perceptron (Ramdas & Pena, 2016).

Implicit Bias in 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.

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 , 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 direction 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). , while we prove that KKT conditions hold for all limit points of $\{{\bm{\theta}}(t)/\|{\bm{\theta}}(t)\|_{2}:t>0\}$, without requiring any convergence assumption; (3) They assume the convergence of the direction of losses (the direction of the vector whose entries are loss values 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).

Preliminaries

Gradient Descent. We consider the process of training this neural network $\Phi$ with either gradient descent or gradient flow. For gradient descent, we assume the training loss $\mathcal{L}({\bm{\theta}})$ is $\mathcal{C}^{2}$-smooth and describe the gradient descnet process as ${\bm{\theta}}(t+1)={\bm{\theta}}(t)-\eta(t)\nabla\mathcal{L}({\bm{\theta}}(t))$, where $\eta(t)$ is the learning rate at time $t$ and $\nabla\mathcal{L}({\bm{\theta}}(t))$ is the gradient of $\mathcal{L}$ at ${\bm{\theta}}(t)$.

Gradient Descent / Gradient Flow on Homogeneous Model

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

(Regularity). For any fixed ${\bm{x}}$, $\Phi(\,\cdot\,;{\bm{x}})$ is locally Lipschitz and admits a chain rule;

(Homogeneity). There exists $L>0$ such that $\forall\alpha>0:\Phi(\alpha{\bm{\theta}};{\bm{x}})=\alpha^{L}\Phi({\bm{\theta}};{\bm{x}})$;

(Separability). There exists a time $t_{0}$ such that $\mathcal{L}({\bm{\theta}}(t_{0}))<1$.

(A1) is a technical assumption about the regularity of the network output. As shown in (Davis et al., 2020), the output of almost every neural network admits a chain rule (as long as the neural network is composed by definable pieces in an o-minimal structure, e.g., ReLU, sigmoid, LeakyReLU).

Gradient Descent. For gradient descent, we assume (A2), (A3), (A4) similarly as for gradient flow, and the following two assumptions (S1) and (S5).

2 Main Theorem: Monotonicity of Normalized Margins

The margin for a single data point $({\bm{x}}_{n},y_{n})$ is defined to be $q_{n}({\bm{\theta}}):=y_{n}\Phi({\bm{\theta}};{\bm{x}}_{n})$, and the margin for the entire dataset is defined to be $q_{\min}({\bm{\theta}}):=\min_{n\in[N]}q_{n}({\bm{\theta}})$. By homogenity, the margin $q_{\min}({\bm{\theta}})$ scales linearly with $\|{\bm{\theta}}\|_{2}^{L}$ for any fixed direction since $q_{\min}(c{\bm{\theta}})=c^{L}q_{\min}({\bm{\theta}})$. So we consider the normalized margin defined as below:

We say $f$ is an $\epsilon$-additive approximation for the normalized margin if $\bar{\gamma}-\epsilon\leq f\leq\bar{\gamma}$, and $c$-multiplicative approximation if $c\bar{\gamma}\leq f\leq\bar{\gamma}$.

Gradient Flow. Our first result is on the overall trend of the normalized margin $\bar{\gamma}({\bm{\theta}}(t))$. For both gradient flow and gradient descent, we identify a smoothed version of the normalized margin, and show that it is non-decreasing during training. More specifically, we have the following theorem for gradient flow.

Gradient Descent. For gradient descent, Theorem 4.1 holds similarly with a slightly different function $\hat{\gamma}({\bm{\theta}})$ that approximates $\bar{\gamma}({\bm{\theta}})$ multiplicatively rather than additively.

Under assumptions (S1), (A2) - (A4), (S5), there exists an $(1-O(1/(\log\frac{1}{\mathcal{L}})))$-multiplicative approximation function $\hat{\gamma}({\bm{\theta}})$ for the normalized margin such that the following statements are true for gradient descent:

For all $t>t_{0}$, $\hat{\gamma}({\bm{\theta}}(t+1))\geq\hat{\gamma}({\bm{\theta}}(t))$;

For all $t>t_{0}$, either $\hat{\gamma}({\bm{\theta}}(t+1))>\hat{\gamma}({\bm{\theta}}(t))$ or $\frac{{\bm{\theta}}(t+1)}{\|{\bm{\theta}}(t+1)\|_{2}}=\frac{{\bm{\theta}}(t)}{\|{\bm{\theta}}(t)\|_{2}}$;

$\mathcal{L}({\bm{\theta}}(t))\to 0$ and $\|{\bm{\theta}}(t)\|_{2}\to\infty$ as $t\to+\infty$; therefore, $\lvert\bar{\gamma}({\bm{\theta}}(t))-\hat{\gamma}({\bm{\theta}}(t))\rvert\to 0$.

Due to the discreteness of gradient descent, the explicit formula for $\hat{\gamma}({\bm{\theta}})$ is somewhat technical, and we refer the readers to Appendix E for full details.

It is shown in Theorem 4.1, 4.2 that $\mathcal{L}({\bm{\theta}}(t))\to 0$ and $\|{\bm{\theta}}(t)\|_{2}\to\infty$. In fact, with a more refined analysis, we can prove tight loss convergence and weight growth rates using the monotonicity of normalized margins.

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:

where $T=t$ for gradient flow and $T=\sum_{\tau=t_{0}}^{t-1}\eta(\tau)$ for gradient descent.

3 Main Theorem: Convergence to KKT Points

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 ${\bm{\theta}}(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.

For gradient flow under assumptions (A1) - (A4) or gradient descent under assumptions (S1), (A2) - (A4), (S5), any limit point $\bar{{\bm{\theta}}}$ of $\left\{\frac{{\bm{\theta}}(t)}{\|{\bm{\theta}}(t)\|_{2}}:t\geq 0\right\}$ is along the direction of a KKT point of the following constrained optimization problem (P):

That is, for any limit point $\bar{{\bm{\theta}}}$, there exists a scaling factor $\alpha>0$ such that $\alpha\bar{{\bm{\theta}}}$ 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 ${\bm{\theta}}$ with $q_{\min}({\bm{\theta}})>0$. For a fixed ${\bm{\theta}}$, $\alpha{\bm{\theta}}$ is a feasible point of (P) iff $\alpha\geq q_{\min}({\bm{\theta}})^{-1/L}$. Thus, the minimum objective value over all feasible points of (P) in the direction of ${\bm{\theta}}$ is $\frac{1}{2}\|{\bm{\theta}}/q_{\min}({\bm{\theta}})^{1/L}\|_{2}^{2}=\frac{1}{2}\bar{\gamma}({\bm{\theta}})^{-2/L}$. Taking minimum over all possible directions, we can conclude that if the maximum normalized margin is $\bar{\gamma}_{*}$, then the minimum objective of (P) is $\frac{1}{2}\bar{\gamma}_{*}^{-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}({\bm{\theta}})$ 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}({\bm{\theta}})$, 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.

Assume (S1). Then for gradient flow under assumptions (A2) - (A4) or gradient descent under assumptions (A2) - (A4), (S5), any limit point $\bar{{\bm{\theta}}}$ of $\{{\bm{\theta}}(t)/\|{\bm{\theta}}(t)\|_{2}:t\geq 0\}$ is along the max-margin direction for the hard-margin SVM with kernel $K_{\bar{{\bm{\theta}}}}({\bm{x}},{\bm{x}}^{\prime})=\left<\nabla\Phi_{{\bm{x}}}(\bar{{\bm{\theta}}}),\nabla\Phi_{{\bm{x}}^{\prime}}(\bar{{\bm{\theta}}})\right>$, where $\Phi_{{\bm{x}}}({\bm{\theta}}):=\Phi({\bm{\theta}};{\bm{x}})$. That is, for some $\alpha>0$, $\alpha\bar{{\bm{\theta}}}$ is the optimal solution for the following constrained optimization problem:

If we assume (A1) instead of (S1) for gradient flow, then there exists a mapping ${\bm{h}}({\bm{x}})\in\partial^{\circ}\Phi_{{\bm{x}}}(\bar{{\bm{\theta}}})$ such that the same conclusion holds for $K_{\bar{{\bm{\theta}}}}({\bm{x}},{\bm{x}}^{\prime})=\left<{\bm{h}}({\bm{x}}),{\bm{h}}({\bm{x}}^{\prime})\right>$.

4 Other Main Results

The above results can be extended to other settings as shown below.

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\in[N]}q_{n}$ and the normalized margin $\bar{\gamma}({\bm{\theta}}):=\frac{q_{\min}({\bm{\theta}})}{\|{\bm{\theta}}\|_{2}^{L}}$ 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 $\Phi({\bm{\theta}};{\bm{x}})$ with ${\bm{\theta}}=({\bm{w}}_{1},\dots,{\bm{w}}_{m})$ is $(k_{1},\dots,k_{m})$-homogeneous if for any ${\bm{x}}$ and any $c_{1},\dots,c_{m}>0$, we have $\Phi(c_{1}{\bm{w}}_{1},\dots,c_{m}{\bm{w}}_{m};{\bm{x}})=\prod_{i=1}^{m}c_{i}^{k_{i}}\cdot\Phi({\bm{w}}_{1},\dots,{\bm{w}}_{m};{\bm{x}})$. In the previous example, an $L$-layer CNN with layer weights ${\bm{\theta}}=({\bm{w}}_{1},\dots,{\bm{w}}_{L})$ is $(1,\dots,1)$-homogeneous.

One can easily see that that $(k_{1},\dots,k_{m})$-homogeneity implies $L$-homogeneity, where $L=\sum_{i=1}^{m}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

In this case, the smoothed approximation of $\bar{\gamma}$ for general binary classification loss (under some conditions) can be similarly defined for gradient flow:

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.

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 ${\bm{\theta}}$ respectively. We will give a proof sketch for this later in this section. We believe that this lemma is of independent interest.

For ease of presentation, we ignore the regularity issues of taking derivatives in this proof sketch. We start from the equation $\frac{d\mathcal{L}}{dt}=-\left<\partial^{\circ}\mathcal{L}({\bm{\theta}}(t)),\frac{d{\bm{\theta}}}{dt}\right>=-\left\|\frac{d{\bm{\theta}}}{dt}\right\|_{2}^{2}$ which follows from the chain rule (see also Lemma I.3). Then we note that $\frac{d{\bm{\theta}}}{dt}$ can be decomposed into two parts: the radial component ${\bm{v}}:=\hat{{\bm{\theta}}}\hat{{\bm{\theta}}}^{\top}\frac{d{\bm{\theta}}}{dt}$ and the tangent component ${\bm{u}}:=({\bm{I}}-\hat{{\bm{\theta}}}\hat{{\bm{\theta}}}^{\top})\frac{d{\bm{\theta}}}{dt}$.

The radial component is easier to analyze. By the chain rule, $\|{\bm{v}}\|_{2}=\hat{{\bm{\theta}}}^{\top}\frac{d{\bm{\theta}}}{dt}=\frac{1}{\rho}\left<{\bm{\theta}},\frac{d{\bm{\theta}}}{dt}\right>=\frac{1}{\rho}\cdot\frac{1}{2}\frac{d\rho^{2}}{dt}$. For $\frac{1}{2}\frac{d\rho^{2}}{dt}$, we have an exact formula:

The last equality is due to $\left<\partial^{\circ}q_{n},{\bm{\theta}}\right>=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{\bm{\theta}})=c^{L}q_{n}({\bm{\theta}})$ and letting $c=1$.

With (6), we can lower bound $\frac{1}{2}\frac{d\rho^{2}}{dt}$ by

where the last inequality uses the fact that $e^{-q_{\min}}\leq\mathcal{L}$. (7) also implies that $\frac{1}{2}\frac{d\rho^{2}}{dt}>0$ for $t>t_{0}$ since $\mathcal{L}(t_{0})<1$ and $\mathcal{L}$ is non-increasing. As $\frac{d}{dt}\log\rho=\frac{1}{2\rho^{2}}\frac{d\rho^{2}}{dt}$, this also proves the first inequality of Lemma 5.1.

Now, we have $\left\|{\bm{v}}\right\|_{2}^{2}=\frac{1}{\rho^{2}}\left(\frac{1}{2}\frac{d\rho^{2}}{dt}\right)^{2}=\frac{1}{2}\frac{d\rho^{2}}{dt}\cdot\frac{d}{dt}\log\rho$ on the one hand; on the other hand, by the chain rule we have $\frac{d\hat{{\bm{\theta}}}}{dt}=\frac{1}{\rho^{2}}(\rho\frac{d{\bm{\theta}}}{dt}-\frac{d\rho}{dt}{\bm{\theta}})=\frac{1}{\rho^{2}}(\rho\frac{d{\bm{\theta}}}{dt}-(\hat{{\bm{\theta}}}^{\top}\frac{d{\bm{\theta}}}{dt}){\bm{\theta}})=\frac{{\bm{u}}}{\rho}$. So we have

Dividing $\frac{1}{2}\frac{d\rho^{2}}{dt}$ on the leftmost and rightmost sides, we have

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 non-smooth 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.

Acknowledgments

The research is supported in part by the National Natural Science Foundation of China Grant 61822203, 61772297, 61632016, 61761146003, and the Zhongguancun Haihua Institute for Frontier Information Technology and Turing AI Institute of Nanjing. We thank Liwei Wang for helpful suggestions on the connection between margin and robustness. We thank Sanjeev Arora, Tianle Cai, Simon Du, Jason D. Lee, Zhiyuan Li, Tengyu Ma, Ruosong Wang for helpful discussions.

References

Appendix A Results for General Loss

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:

(Regularity). For any fixed ${\bm{x}}$, $\Phi(\,\cdot\,;{\bm{x}})$ is locally Lipschitz and admits a chain rule;

(Homogeneity). There exists $L>0$ such that $\forall\alpha>0:\Phi(\alpha{\bm{\theta}};{\bm{x}})=\alpha^{L}\Phi({\bm{\theta}};{\bm{x}})$;

There exists $b_{f}\geq 0$ such that $f^{\prime}(q)q$ is non-decreasing for $q\in(b_{f},+\infty)$, and $f^{\prime}(q)q\to+\infty$ as $q\to+\infty$.

Let $g:[f(b_{f}),+\infty)\to[b_{f},+\infty)$ be the inverse function of $f$ on the domain $[b_{f},+\infty)$. There exists $b_{g}\geq\max\{2f(b_{f}),f(2b_{f})\},K\geq 1$ such that $g^{\prime}(x)\leq Kg^{\prime}(\theta x)$ and $f^{\prime}(y)\leq Kf^{\prime}(\theta y)$ for all $x\in(b_{g},+\infty),y\in(g(b_{g}),+\infty)$ and $\theta\in[1/2,1)$.

We summarize the corresponding $f,g$ and $b_{f}$ for exponential loss and logistic loss below:

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

By simple calculations, the formulas for $f(q),f^{\prime}(q),g(q),g^{\prime}(q)$ are correct. (B3.1) is trivial. $f^{\prime}(q)=\frac{e^{-q}}{(1+e^{-q})\log(1+e^{-q})}>0$, so (B3.2) is satisfied. For (B3.3), note that $f^{\prime}(q)q=\frac{q}{(1+e^{q})\log(1+e^{-q})}$. The denominator is a decreasing function since

A.2 Smoothed Normalized Margin

Assuming (B3)Indeed, (B3.4) is not needed for showing Lemma A.5 and Theorem A.7., we have the following properties about the margin:

$f(q_{\min})-\log N\leq\log\frac{1}{\mathcal{L}}\leq f(q_{\min})$.

If $\log\frac{1}{\mathcal{L}}>f(b_{f})$, then there exists $\xi\in(f(q_{\min})-\log N,f(q_{\min}))\cap(b_{f},+\infty)$ such that

(a) can be easily deduced from $e^{-f(q_{\min})}\leq\mathcal{L}\leq Ne^{-f(q_{\min})}$. Combining (a) and the monotonicity of $g(\cdot)$, we further have $g(s)\leq g(\log\frac{1}{\mathcal{L}})\leq q_{\min}$ for $s:=\max\{f(b_{f}),f(q_{\min})-\log N\}$. By the mean value Theorem, there exists $\xi\in(s,f(q_{\min}))$ such that $g(s)=g(f(q_{\min}))-g^{\prime}(\xi)(f(q_{\min})-s)\geq q_{\min}-g^{\prime}(\xi)\log N$. Dividing $\rho^{L}$ on each side of $q_{\min}-g^{\prime}(\xi)\log N\leq g(\log\frac{1}{\mathcal{L}})\leq q_{\min}$ proves (b).

Now we prove (c). Without loss of generality, we assume $\log\frac{1}{\mathcal{L}({\bm{\theta}}_{m})}>f(b_{f})$ for all ${\bm{\theta}}_{m}$. It follows from (b) that for every ${\bm{\theta}}_{m}$ there exists $\xi_{m}\in(f(q_{\min}({\bm{\theta}}_{m}))-\log N,f(q_{\min}({\bm{\theta}}_{m})))\cap(b_{f},+\infty)$ such that

Note that $\xi_{m}\geq f(q_{\min}({\bm{\theta}}_{m}))-\log N\geq\log\frac{1}{\mathcal{L}({\bm{\theta}}_{m})}-\log N\to+\infty$. So $\frac{g(\xi_{m})}{g^{\prime}(\xi_{m})}=f^{\prime}(g(\xi_{m}))g(\xi_{m})\to+\infty$ by (B3.3). Also note that there exists a constant $B_{0}$ such that $\bar{\gamma}({\bm{\theta}}_{m})\leq B_{0}$ for all $m$ since $\bar{\gamma}$ is continuous on the unit sphere $\mathcal{S}^{d-1}$. So we have

A.3 Theorems

Now we state our main theorems. For the monotonicity of the normalized margin, we have the following theorem. The proof is provided in Appendix B.

Under assumptions (A1), (A2), (B3), (B4), the following statements are true for gradient flow:

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:

First, we show the directional convergence of ${\bm{\theta}}(t)$ to a KKT point of (P).

Consider gradient flow under assumptions (A1), (A2), (B3), (B4). For every limit point $\bar{{\bm{\theta}}}$ of $\left\{\hat{{\bm{\theta}}}(t):t\geq 0\right\}$, $\bar{{\bm{\theta}}}/q_{\min}(\bar{{\bm{\theta}}})^{1/L}$ is a KKT point of (P).

Second, we show that after finite time, gradient flow can pass through an approximate KKT point.

Consider gradient flow under assumptions (A1), (A2), (B3), (B4). For any $\epsilon,\delta>0$, there exists $r:=\Theta(\log\delta^{-1})$ and $\Delta:=\Theta(\epsilon^{-2})$ such that ${\bm{\theta}}/q_{\min}({\bm{\theta}})^{1/L}$ is an $(\epsilon,\delta)$-KKT point at some time $t_{*}$ satisfying $\log\|{\bm{\theta}}(t_{*})\|_{2}\in(r,r+\Delta)$.

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.

Under assumptions (A1), (A2), (B3), (B4), we have the following tight rates for loss convergence and weight growth:

Applying Theorem A.10 to exponential loss and logistic loss, in which $g(x)=\Theta(x)$, we have the following corollary:

Appendix 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 $\rho:=\|{\bm{\theta}}\|_{2}$ and $\hat{{\bm{\theta}}}:=\frac{{\bm{\theta}}}{\|{\bm{\theta}}\|_{2}}\in\mathcal{S}^{d-1}$, and sometimes we view the functions of ${\bm{\theta}}$ as functions of $t$.

To prove the first two propositions, we generalize our key lemma (Lemma 5.1) to general loss.

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:

That is, $\partial^{\circ}F(\alpha x)=\{\alpha^{k-1}{\bm{h}}:{\bm{h}}\in\partial^{\circ}F(x)\}$.

That is, $\left<{\bm{x}},{\bm{h}}\right>=k\cdot F({\bm{x}})$ for all ${\bm{h}}\in\partial^{\circ}F({\bm{x}})$.

Let $D$ be the set of points ${\bm{x}}$ such that $F$ is differentiable at ${\bm{x}}$. According to the definition of Clarke’s subdifferential, for proving (a), it is sufficient to show that

Taking limits ${\bm{y}}\to{\bm{x}}_{k}$ on both sides, we know that the LHS converges to iff the RHS converges to . Then by definition of differetiability and gradient, $F$ is differentiable at $\alpha{\bm{x}}_{k}$ iff it is differentiable at ${\bm{x}}_{k}$, and $\nabla F(\alpha{\bm{x}}_{k})=\alpha^{k-1}{\bm{h}}$ iff $\nabla F({\bm{x}}_{k})={\bm{h}}$. This proves (10).

holds for a.e. $\alpha>0$. Pick an arbitrary $\alpha>0$ making (11) hold. Then by (a), (11) is equivalent to $\forall{\bm{h}}\in\partial^{\circ}F({\bm{x}}):\left<{\bm{x}},\alpha^{k-1}{\bm{h}}\right>=k\alpha^{k-1}F({\bm{x}})$, which proves (b). ∎

Applying Theorem B.2 to homogeneous neural networks, we have the following corollary:

where $\Phi_{{\bm{x}}}({\bm{\theta}})=\Phi({\bm{\theta}};{\bm{x}})$ is the network output for a fixed input ${\bm{x}}$.

Corollary B.3 can be used to derive an exact formula for the weight growth during training.

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\mapsto\rho^{2}=\left\|{\bm{\theta}}\right\|_{2}^{2}$ yields $\frac{1}{2}\frac{d\rho^{2}}{dt}=-\left<{\bm{\theta}},{\bm{h}}\right>$ for all ${\bm{h}}\in\partial^{\circ}\mathcal{L}$ and a.e.$~{}t>0$. Then applying the chain rule on ${\bm{\theta}}\mapsto\mathcal{L}$, we have

By Corollary B.3, $\left<{\bm{\theta}},{\bm{h}}_{n}\right>=Lq_{n}$, and thus $\frac{1}{2}\frac{d\rho^{2}}{dt}=L\sum_{n=1}^{N}e^{-f(q_{n})}f^{\prime}(q_{n})q_{n}$. ∎

For convenience, we define $\nu(t):=\sum_{n=1}^{N}e^{-f(q_{n})}f^{\prime}(q_{n})q_{n}$ for all $t\geq 0$. Then Theorem B.4 can be rephrased as $\frac{1}{2}\frac{d\rho^{2}}{dt}=L\nu(t)$ for a.e. $t\geq 0$.

By Lemma A.5, $q_{n}\geq g(\log\frac{1}{\mathcal{L}})$ for all $n\in[N]$. Then by Assumption (B3),

Combining this with the definitions of $\nu(t)$ and $\mathcal{L}$ gives

On the one hand, $-\frac{d\mathcal{L}}{dt}=\left\|\frac{d{\bm{\theta}}}{dt}\right\|_{2}^{2}$ for a.e. $t>0$ by Lemma I.3; on the other hand, $L\nu(t)=\left<{\bm{\theta}},\frac{d{\bm{\theta}}}{dt}\right>$ by Theorem B.4. Combining these together yields

By the chain rule, $\frac{d\hat{{\bm{\theta}}}}{dt}=\frac{1}{\rho}({\bm{I}}-\hat{{\bm{\theta}}}\hat{{\bm{\theta}}}^{\top})\frac{d{\bm{\theta}}}{dt}$ for a.e. $t>0$. So we have

B.2 Proof for Proposition 3

Therefore, $\mathcal{L}(t)\to 0$ and $\rho(t)\to+\infty$ as $t\to\infty$.

Integrating on both sides from $t_{0}$ to $t$, we can conclude that

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

To make $\mathcal{L}\to 0$, $q_{\min}$ must converge to $+\infty$. So $\rho\to+\infty$. ∎

Appendix C Convergence to the Max-margin Solution

In this section, we analyze the convergent direction of ${\bm{\theta}}$ 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 $\rho:=\|{\bm{\theta}}\|_{2}$ and $\hat{{\bm{\theta}}}:=\frac{{\bm{\theta}}}{\|{\bm{\theta}}\|_{2}}\in\mathcal{S}^{d-1}$, and sometimes we view the functions of ${\bm{\theta}}$ as functions of $t$.

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

A feasible point ${\bm{x}}$ of (P) is a KKT point if ${\bm{x}}$ satisfies KKT conditions: there exists $\lambda_{1},\dots,\lambda_{N}\geq 0$ such that

$0\in\partial^{\circ}f({\bm{x}})+\sum_{n\in[N]}\lambda_{n}\partial^{\circ}g_{n}({\bm{x}})$;

$\forall n\in[N]:\lambda_{n}g_{n}({\bm{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)):

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 $\epsilon$-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 ${\bm{x}}$, so our definition is slightly stronger; (2) Second, their paper fixes $\delta=\epsilon^{2}$, but in our definition we make them independent.

For $\epsilon,\delta>0$, a feasible point ${\bm{x}}$ of (P) is an $(\epsilon,\delta)$-KKT point if there exists $\lambda_{n}\geq 0,{\bm{k}}\in\partial^{\circ}f({\bm{x}}),{\bm{h}}_{n}\in\partial^{\circ}g_{n}({\bm{x}})$ for all $n\in[N]$ such that

$\left\|{\bm{k}}+\sum_{n\in[N]}\lambda_{n}{\bm{h}}_{n}({\bm{x}})\right\|_{2}\leq\epsilon$;

$\forall n\in[N]:\lambda_{n}g_{n}({\bm{x}})\geq-\delta$.

As shown in (Dutta et al., 2013), $(\epsilon,\delta)$-KKT point is an approximate version of KKT point in the sense that a series of $(\epsilon,\delta)$-KKT points can converge to a KKT point. We restate their theorem in our setting:

C.2 KKT Conditions for (P)

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

Using the terminologies and notations in Appendix C.1, the objective and constraints are $f({\bm{x}})=\frac{1}{2}\|{\bm{x}}\|_{2}^{2}$ and $g_{n}({\bm{x}})=1-q_{n}({\bm{x}})$. The KKT points and approximate KKT points for (P) are defined as follows:

A feasible point ${\bm{\theta}}$ of (P) is a KKT point if there exist $\lambda_{1},\dots,\lambda_{N}\geq 0$ such that

${\bm{\theta}}-\sum_{n=1}^{N}\lambda_{n}{\bm{h}}_{n}={\bm{0}}$ for some ${\bm{h}}_{1},\dots,{\bm{h}}_{N}$ satisfying ${\bm{h}}_{n}\in\partial^{\circ}q_{n}({\bm{\theta}})$;

$\forall n\in[N]:\lambda_{n}(q_{n}({\bm{\theta}})-1)=0$.

A feasible point ${\bm{\theta}}$ of (P) is an $(\epsilon,\delta)$-KKT point of (P) if there exists $\lambda_{1},\dots,\lambda_{N}\geq 0$ such that

$\left\|{\bm{\theta}}-\sum_{n=1}^{N}\lambda_{n}{\bm{h}}_{n}\right\|_{2}\leq\epsilon$ for some ${\bm{h}}_{1},\dots,{\bm{h}}_{N}$ satisfying ${\bm{h}}_{n}\in\partial^{\circ}q_{n}({\bm{\theta}})$;

$\forall n\in[N]:\lambda_{n}(q_{n}({\bm{\theta}})-1)\leq\delta$.

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.

(P) satisfies MFCQ at every feasible point ${\bm{\theta}}$.

Take ${\bm{v}}:={\bm{\theta}}$. For all $n\in[N]$ satisfying $q_{n}=1$, by homogeneity of $q_{n}$,

holds for any ${\bm{h}}\in-\partial^{\circ}q_{n}({\bm{\theta}})=\partial^{\circ}(1-q_{n}({\bm{\theta}}))$. ∎

C.3 Key Lemmas

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 ${\bm{\theta}}$ is along the direction of an approximate KKT point, we only need to show $\beta\rightarrow 1$ (which makes $\epsilon\rightarrow 0$) and $\mathcal{L}\rightarrow 0$ (which makes $\delta\rightarrow 0$).

Let $C_{1},C_{2}$ be two constants defined as

Proof for (13).

Note that $\left\|{\bm{h}}\right\|_{2}\geq\left<{\bm{h}},\hat{{\bm{\theta}}}\right>=L\nu/\rho$. By Lemma B.5 and Lemma D.1, we have

By Theorem A.7, we have already known that $\mathcal{L}\to 0$. So it remains to bound $\beta(t)$. For this, we first prove the following lemma to bound the integral of $\beta(t)$.

By Lemma B.4, $\frac{d}{dt}\log\rho=\frac{1}{2\rho^{2}}\frac{d\rho^{2}}{dt}=\frac{L\nu}{\rho^{2}}$ for a.e. $t>0$. By Lemma B.1, for a.e. $t\in(t_{1},t_{2})$,

By the chain rule, $\frac{d\hat{{\bm{\theta}}}}{dt}=\frac{1}{\rho}({\bm{I}}-\hat{{\bm{\theta}}}\hat{{\bm{\theta}}}^{\top})\frac{d{\bm{\theta}}}{dt}$. So we have

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

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 $\beta^{2}-1$ within a time interval:

For all $t_{2}>t_{1}\geq t_{0}$, then there exists $t_{*}\in(t_{1},t_{2})$ such that

Denote the RHS as $C$. Assume to the contrary that $\beta(\tau)^{-2}-1>C$ for a.e. $\tau\in(t_{1},t_{2})$. By Lemma B.1, $\log\rho(\tau)>0$ for a.e. $\tau\in(t_{1},t_{2})$. Then by Lemma C.9, we have

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 $\beta(t)$.

C.4 Asymptotic Analysis

We first prove an auxiliary lemma which gives an upper bound for the change of $\hat{{\bm{\theta}}}$.

Note that every summand is positive. By Lemma A.5, $q_{n}$ is lower-bounded by $q_{n}\geq q_{\min}\geq g(\log\frac{1}{\mathcal{L}})$, so we can replace $q_{n}$ with $g(\log\frac{1}{\mathcal{L}})$ in the above inequality. Combining with the fact that $\sum_{n\in[N]}e^{-f(q_{n})}f^{\prime}(q_{n})q_{n}$ is just $\nu$, we have

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

Let $s^{\prime}_{m}>s_{m}$ be a time such that $\log\rho(s^{\prime}_{m})=\log\rho(s_{m})+\epsilon_{m}$. According to Theorem A.7, $\log\rho\to+\infty$, so $s^{\prime}_{m}$ must exist. We construct $t_{m}\in(s_{m},s^{\prime}_{m})$ to be a time that $\beta(t_{m})^{-2}-1\leq\epsilon_{m}^{2}$, where the existence can be shown by Corollary C.10.

Now we show that this construction meets our requirement. It follows from $\beta(t_{m})^{-2}-1\leq\epsilon_{m}^{2}$ that $\beta(t_{m})\geq 1/\sqrt{1+\epsilon_{m}^{2}}\to 1$. By Lemma C.11, we also know that

C.5 Non-asymptotic Analysis

C.6 Proof for Corollary 4.5

By the homogeneity of $q_{n}$, we can characterize KKT points using kernel SVM.

If ${\bm{\theta}}_{*}$ is KKT point of (P), then there exists ${\bm{h}}_{n}\in\partial^{\circ}\Phi_{{\bm{x}}_{n}}({\bm{\theta}}_{*})$ for $n\in[N]$ such that $\frac{1}{L}{\bm{\theta}}_{*}$ is an optimal solution for the following constrained optimization problem (Q):

It is easy to see that (Q) is a convex optimization problem. For ${\bm{\theta}}=\frac{2}{L}{\bm{\theta}}_{*}$, from Theorem B.2, we can see that $y_{n}\left<{\bm{\theta}},{\bm{h}}_{n}\right>=2q_{n}({\bm{\theta}}_{*})\geq 2>1$, which implies Slater’s condition. Thus, we only need to show that $\frac{1}{L}{\bm{\theta}}_{*}$ satisfies KKT conditions for (Q).

By the KKT conditions for (P), we can construct ${\bm{h}}_{n}\in\partial^{\circ}q_{n}({\bm{\theta}}_{*})$ for $n\in[N]$ such that ${\bm{\theta}}_{*}-\sum_{n=1}^{N}\lambda_{n}y_{n}{\bm{h}}_{n}={\bm{0}}$ for some $\lambda_{1},\dots,\lambda_{N}\geq 0$ and $\lambda_{n}(q_{n}({\bm{\theta}}_{*})-1)=0$. Thus, $\frac{1}{L}{\bm{\theta}}_{*}$ satisfies

$\frac{1}{L}{\bm{\theta}}_{*}-\sum_{n=1}^{N}\frac{1}{L}\lambda_{n}y_{n}{\bm{h}}_{n}={\bm{0}}$;

$\frac{1}{L}\lambda_{n}\left(y_{n}\left<\frac{1}{L}{\bm{\theta}}_{*},{\bm{h}}_{n}\right>-1\right)=\frac{1}{L}\lambda_{n}\left(q_{n}({\bm{\theta}})-1\right)\geq 0$.

So $\frac{1}{L}{\bm{\theta}}_{*}$ satisfies KKT conditions for (Q). ∎

Now we prove Corollary 4.5 in Section 4.3.

By Theorem A.8, every limit point $\bar{{\bm{\theta}}}$ is along the direction of a KKT point of (P). Combining this with Lemma C.13, we know that every limit point $\bar{{\bm{\theta}}}$ is also along the max-margin direction of (Q).

For smooth models, ${\bm{h}}_{n}$ in (Q) is exactly the gradient $\nabla\Phi_{{\bm{x}}_{n}}(\bar{{\bm{\theta}}})$. So, (Q) is the optimization problem for SVM with kernel $K_{\bar{{\bm{\theta}}}}({\bm{x}},{\bm{x}}^{\prime})=\left<\nabla\Phi_{{\bm{x}}}(\bar{{\bm{\theta}}}),\nabla\Phi_{{\bm{x}}^{\prime}}(\bar{{\bm{\theta}}})\right>$. For non-smooth models, we can construct an arbitrary function ${\bm{h}}({\bm{x}})\in\partial^{\circ}\Phi_{{\bm{x}}}(\bar{{\bm{\theta}}})$ that ensures ${\bm{h}}({\bm{x}}_{n})={\bm{h}}_{n}$. Then, (Q) is the optimization problem for SVM with kernel $K_{\bar{{\bm{\theta}}}}({\bm{x}},{\bm{x}}^{\prime})=\left<{\bm{h}}({\bm{x}}),{\bm{h}}({\bm{x}}^{\prime})\right>$. ∎

Appendix 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).

Before proving Theorem A.10, we show some consequences of (B3.4).

For all $x\in[b_{g},+\infty)$, $\frac{g(x)}{g^{\prime}(x)}\in[\frac{1}{2K}x,2Kx]$;

For all $y\in[g(b_{g}),+\infty)$, $\frac{f(y)}{f^{\prime}(y)}\in[\frac{1}{2K}y,2Ky]$.

Thus, $g(x)=\Theta(xg^{\prime}(x)),f(y)=\Theta(yf^{\prime}(y))$.

To prove Item 1, it is sufficient to show that

To prove Item 2, we only need to notice that Item 1 implies $yf^{\prime}(y)=\frac{g(f(y))}{g^{\prime}(f(y))}\in[\frac{1}{2K}f(y),2Kf(y)]$ for all $y\in[g(b_{g}),+\infty)$. ∎

Recall that (B3.4) directly implies that $f^{\prime}(\Theta(x))=\Theta(f^{\prime}(x))$ and $g^{\prime}(\Theta(x))=\Theta(g^{\prime}(x))$. Combining this with Lemma D.1, we have the following corollary:

$f(\Theta(x))=\Theta(f(x))$ and $g(\Theta(x))=\Theta(g(x))$.

Also, note that Lemma D.1 essentially shows that $(\log f(x))^{\prime}=\Theta(1/x)$ and $(\log g(x))^{\prime}=\Theta(1/x)$. So $\log f(x)=\Theta(\log x)$ and $\log g(x)=\Theta(\log x)$, which means that $f$ and $g$ grow at most polynomially.

$f(x)=x^{\Theta(1)}$ and $g(x)=x^{\Theta(1)}$.

D.2 Proof for Theorem A.10

We follow the notations in Section 5 to define $\rho:=\|{\bm{\theta}}\|_{2}$ and $\hat{{\bm{\theta}}}:=\frac{{\bm{\theta}}}{\|{\bm{\theta}}\|_{2}}\in\mathcal{S}^{d-1}$, and sometimes we view the functions of ${\bm{\theta}}$ 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 $\mathcal{L}(t)$ is bounded from above by $\frac{1}{G^{-1}(\Omega(t))}$. So upper bounding $\mathcal{L}(t)$ reduces to lower bounding $G^{-1}$. In the following lemma, we obtain tight asymptotic bounds for $G(\cdot)$ and $G^{-1}(\cdot)$:

For function $G(\cdot)$ defined in Lemma B.6 and its inverse function $G^{-1}(\cdot)$, we have the following bounds:

We first prove the bounds for $G(x)$, and then prove the bounds for $G^{-1}(y)$.

Let $C_{G}=\int_{1/\mathcal{L}(t_{0})}^{\exp(b_{g})}\frac{g^{\prime}(\log u)^{2}}{g(\log u)^{2-2/L}}du$. For $x\geq\exp(b_{g})$,

On the other hand, for $x\geq\exp(2b_{g})$, we have

Let $x=G^{-1}(y)$ for $y\geq 0$. $G(x)$ always has a finite value whenever $x$ is finite. So $x\to+\infty$ when $y\to+\infty$. According to the first part of the proof, we know that $y=\Theta\left(\frac{g(\log x)^{2/L}}{(\log x)^{2}}x\right)$. Taking logarithm on both sides and using Corollary D.3, we have $\log y=\Theta(\log x)$. By Corollary D.2, $g(\log y)=g(\Theta(\log x))=\Theta(g(\log x))$. Therefore,

This implies that $x=\Theta\left(\frac{(\log y)^{2}}{g(\log y)^{2/L}}y\right)$. ∎

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

We first prove the upper bound for $\mathcal{L}$. Then we derive lower and upper bounds for $\rho$ in terms of $\mathcal{L}$, and use these bounds to give a lower bound for $\mathcal{L}$. Finally, we plug in the tight bounds for $\mathcal{L}$ to obtain the lower and upper bounds for $\rho$ in terms of $t$.

Upper Bounding ℒℒ\mathcal{L}.

By Lemma B.6, we have $\frac{1}{\mathcal{L}}\geq G^{-1}\left(\Omega(t)\right)$. Using Lemma D.4, we have $\frac{1}{\mathcal{L}}=\Omega\left(\frac{(\log t)^{2}}{g(\log t)^{2/L}}t\right)$, which completes the proof.

Bounding ρ𝜌\rho in Terms of ℒℒ\mathcal{L}.

Lower Bounding ℒℒ\mathcal{L}.

Let ${\bm{h}}_{1},\dots,{\bm{h}}_{N}$ be a set of vectors such that ${\bm{h}}_{n}\in\frac{\partial q_{n}}{\partial{\bm{\theta}}}$ and

By (17) and Corollary D.2, $f^{\prime}(q_{n})=f^{\prime}(O(\rho^{L}))=f^{\prime}(O(g(\log\frac{1}{\mathcal{L}})))=O(f^{\prime}(g(\log\frac{1}{\mathcal{L}})))=O(1/g^{\prime}(\log\frac{1}{\mathcal{L}}))$. Again by (17), we have $\left\|{\bm{h}}_{n}\right\|_{2}\leq B_{1}\rho^{L-1}=O(g(\log\frac{1}{\mathcal{L}})^{1-1/L})$. Combining these two bounds together, it follows from Corollary D.2 that

By definition of $G(\cdot)$, this implies that there exists a constant $c$ such that $\frac{d}{dt}G(\frac{1}{\mathcal{L}})\leq c$ for any $\mathcal{L}$ that is small enough. We can complete our proof by applying Lemma D.4.

Bounding ρ𝜌\rho in Terms of t𝑡t.

By (17) and the tight bound for $\mathcal{L}(t)$, $\rho^{L}=\Theta(g(\log\frac{1}{\mathcal{L}}))=\Theta(g(\Theta(\log t)))$. Using Corollary D.2, we can conclude that $\rho^{L}=\Theta(g(\log t))$. ∎

Appendix 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

Here $\eta(t)$ is the learning rate, and $\nabla\mathcal{L}(t):=\nabla\mathcal{L}({\bm{\theta}}(t))$ is the gradient of $\mathcal{L}$ at ${\bm{\theta}}(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).

Technically, recall that $\frac{d\mathcal{L}}{dt}=-\|\nabla\mathcal{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

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

(Homogeneity). There exists $L>0$ such that $\forall\alpha>0:\Phi(\alpha{\bm{\theta}};{\bm{x}})=\alpha^{L}\Phi({\bm{\theta}};{\bm{x}})$;

(Separability). There exists a time $t_{0}$ such that $\mathcal{L}({\bm{\theta}}(t_{0}))<1$.