The Implicit Bias of Gradient Descent on Separable Data

Introduction

It is becoming increasingly clear that implicit biases introduced by the optimization algorithm play a crucial role in deep learning and in the generalization ability of the learned models (Neyshabur et al., 2014, 2015; Zhang et al., 2017; Keskar et al., 2017; Neyshabur et al., 2017; Wilson et al., 2017). In particular, minimizing the training error, without explicit regularization, over models with more parameters and capacity than the number of training examples, often yields good generalization. This is despite the fact that the empirical optimization problem being highly underdetermined. That is, there are many global minima of the training objective, most of which will not generalize well, but the optimization algorithm (e.g. gradient descent) biases us toward a particular minimum that does generalize well. Unfortunately, we still do not have a good understanding of the biases introduced by different optimization algorithms in different situations.

We do have an understanding of the implicit regularization introduced by early stopping of stochastic methods or, at an extreme, of one-pass (no repetition) stochastic gradient descent (Hardt et al., 2016). However, as discussed above, in deep learning we often benefit from implicit bias even when optimizing the training error to convergence (without early stopping) using stochastic or batch methods. For loss functions with attainable, finite minimizers, such as the squared loss, we have some understanding of this: in particular, when minimizing an underdetermined least squares problem using gradient descent starting from the origin, it can be shown that we will converge to the minimum Euclidean norm solution. However, the logistic loss, and its generalization the cross-entropy loss which is often used in deep learning, do not admit finite minimizers on separable problems. Instead, to drive the loss toward zero and thus minimize it, the norm of the predictor must diverge toward infinity.

Do we still benefit from implicit regularization when minimizing the logistic loss on separable data? Clearly the norm of the predictor itself is not minimized, since it grows to infinity. However, for prediction, only the direction of the predictor, i.e. the normalized $\mathbf{w}(t)/\left\lVert{\mathbf{w}(t)}\right\rVert$, is important. How does $\mathbf{w}(t)/\left\lVert{\mathbf{w}(t)}\right\rVert$ behave as $t\rightarrow\infty$ when we minimize the logistic (or similar) loss using gradient descent on separable data, i.e., when it is possible to get zero misclassification error and thus drive the loss to zero?

In this paper, we show that even without any explicit regularization, for all linearly separable datasets, when minimizing logistic regression problems using gradient descent, we have that $\mathbf{w}(t)/\left\lVert{\mathbf{w}(t)}\right\rVert$ converges to the $L_{2}$ maximum margin separator, i.e. to the solution of the hard margin SVM for homogeneous linear predictors. This happens even though neither the norm $\left\lVert\mathbf{w}\right\rVert$, nor the margin constraint, are part of the objective or explicitly introduced into optimization. More generally, we show the same behavior for generalized linear problems with any smooth, monotone strictly decreasing, lower bounded loss with an exponential tail. Furthermore, we characterize the rate of this convergence, and show that it is rather slow, wherein for almost all datasets, the distance to the max-margin predictor decreasing only as ${O}(1/\log(t))$, and in some degenerate datasets, the rate further slows down to ${O}(\log\log(t)/\log(t))$. This explains why the predictor continues to improve even when the training loss is already extremely small. We emphasize that this bias is specific to gradient descent, and changing the optimization algorithm, e.g. using adaptive learning rate methods such as ADAM (Kingma and Ba, 2015), changes this implicit bias.

Main Results

We are particularly interested in problems that are linearly separable, and the loss is smooth strictly decreasing and non-negative:

The dataset is linearly separable: $\exists\mathbf{w}_{*}$ such that $\forall n:\,\mathbf{w}_{*}^{\top}\mathbf{x}_{n}>0$ .

Under these conditions, the infimum of the optimization problem is zero, but it is not attained at any finite $\mathbf{w}$. Furthermore, no finite critical point $\mathbf{w}$ exists. We consider minimizing eq. 1 using Gradient Descent (GD) with a fixed learning rate $\eta$, i.e., with steps of the form:

We do not require convexity. Under Assumptions 1 and 2, gradient descent converges to the global minimum (i.e. to zero loss) even without it:

Let $\mathbf{w}\left(t\right)$ be the iterates of gradient descent (eq. 2) with \eta<2\beta^{-1}\sigma_{\max}^{-2}\left(\text{\mathbf{X}}\right) and any starting point $\mathbf{w}(0)$. Under Assumptions 1 and 1, we have: (1) $\lim_{t\rightarrow\infty}\mathcal{L}\left(\mathbf{w}\left(t\right)\right)=0$, (2) $\lim_{t\rightarrow\infty}\left\|\mathbf{w}\left(t\right)\right\|=\infty$, and (3) $\forall n:\,\lim_{t\rightarrow\infty}\mathbf{w}\left(t\right)^{\top}\mathbf{x}_{n}=\infty$.

Proof Since the data is linearly separable, $\exists\mathbf{w}_{*}$ which linearly separates the data, and therefore

In order to analyze this limit, we will need to make a further assumption on the tail of the loss function:

A function $f\left(u\right)$ has a “tight exponential tail”, if there exist positive constants $c,a,\mu_{+},\mu_{-},u_{+}$ and $u_{-}$ such that

We are now ready to state our main result: {thmR}[]

For any dataset which is linearly separable (Assumption 1), any $\beta$-smooth decreasing loss function (Assumption 1) with an exponential tail (Assumption 3), any stepsize \eta<2\beta^{-1}\sigma_{\max}^{-2}\left(\text{\mathbf{X}}\right) and any starting point $\mathbf{w}(0)$, the gradient descent iterates (as in eq. 2) will behave as:

where $\hat{\mathbf{w}}$ is the $L_{2}$ max margin vector (the solution to the hard margin SVM):

and the residual grows at most as $\left\lVert{\boldsymbol{\rho}\left(t\right)}\right\rVert=O(\log\log(t))$, and so

Furthermore, for almost all data sets (all except measure zero), the residual $\rho(t)$ is bounded.

These are precisely the KKT conditions for the SVM problem (eq. 4) and we can conclude that $\hat{\mathbf{w}}$ is indeed its solution and $\mathbf{w}_{\infty}$ is thus proportional to it.

To prove Theorem 2 rigorously, we need to show that $\mathbf{w}\left(t\right)/\left\|\mathbf{w}\left(t\right)\right\|$ has a limit, , that $\forall n:\mathbf{w}_{\infty}^{\top}\mathbf{x}_{n}>0$, that $g\left(t\right)=\log\left(t\right)$, and to bound the effect of various residual errors, such as gradients of non-support vectors and the fact that the loss is only approximately exponential. To do so, we substitute eq. 3 into the gradient descent dynamics (eq. 2), with $\mathbf{w}_{\infty}=\hat{\mathbf{w}}$ being the max margin vector and $g(t)=\log t$. We then show that, except when certain degeneracies occur, the increment in the norm of $\boldsymbol{\rho}\left(t\right)$ is bounded by $C_{1}t^{-\nu}$ for some $C_{1}>0$ and $\nu>1$, which is a converging series. This happens because the increment in the max margin term, $\hat{\mathbf{w}}\left[\log\left(t+1\right)-\log\left(t\right)\right]\approx\hat{\mathbf{w}}t^{-1}$, cancels out the dominant $t^{-1}$ term in the gradient $-\nabla\mathcal{L}\left(\mathbf{w}\left(t\right)\right)$ (eq. 5 with $g\left(t\right)=\log\left(t\right)$ and $\mathbf{w}_{\infty}^{\top}\mathbf{x}_{n}=1$).

An earlier conference version of this paper (Soudry et al., 2018) included a partial version of Theorem 2, which only applies to almost all data sets, in which case we can ensure the residual $\rho(t)$ is bounded. This partial statement (for almost all data sets) is restated and proved as Theorem A in Appendix A. It applies, e.g. with probability one for data sampled from any absolutely continuous distribution. It does not apply in “degenerate” cases where some of the support vectors $\mathbf{x}_{n}$ (for which $\hat{\mathbf{w}}^{\top}\mathbf{x}_{n}=1$) are associated with dual variables that are zero ($\alpha_{n}=0$) in the dual optimum of 4. As we show in Appendix B, this only happens on measure zero data sets. Here, we prove the more general result which applies for all data sets, including degenerate data sets. To do so, in Theorem 4 in Appendix C we provide a more complete characterization of the iterates $\mathbf{w}(t)$ that explicitly specifies all unbounded components even in the degenerate case. We then prove the Theorem by plugging in this more complete characterization and showing that the residual is bounded, thus also establishing Theorem 2.

Following the publication of our initial version, and while preparing this revised version for publication, we learned of parallel work by Ziwei Ji and Matus Telgarsky that also closes this gap. Ji and Telgarsky (2018) provide an analysis of the degenerate case, establishing converges to the max margin predictor by showing that $\left\lVert{\frac{\mathbf{w}(t)}{\left\lVert{\mathbf{w}(t)}\right\rVert}-\frac{\hat{\mathbf{w}}}{\left\lVert{\hat{\mathbf{w}}}\right\rVert}}\right\rVert=O\left(\sqrt{\frac{\log\log t}{\log t}}\right)$. Our analysis provides a more precise characterization of the iterates, and also shows the convergence is actually quadratically faster (see Section 3). However, Ji and Telgarsky go even further and provide a characterization also when the data is non-separable but $\mathbf{w}(t)$ still goes to infinity.

Perhaps most similar to our study is the line of work on understanding AdaBoost in terms its implicit bias toward large $L_{1}$-margin solutions, starting with the seminal work of Schapire et al. (1998). Since AdaBoost can be viewed as coordinate descent on the exponential loss of a linear model, these results can be interpreted as analyzing the bias of coordinate descent, rather then gradient descent, on a monotone decreasing loss with an exact exponential tail. Indeed, with small enough step sizes, such a coordinate descent procedure does converge precisely to the maximum $L_{1}$-margin solution (Zhang et al., 2005; Telgarsky, 2013). In fact, Telgarsky (2013) also generalizes these results to other losses with tight exponential tails, similar to the class of losses we consider here.

Also related is the work of Rosset et al. (2004). They considered the regularization path $\mathbf{w}_{\lambda}=\arg\min\mathcal{L}(\mathbf{w})+\lambda\left\lVert{\mathbf{w}}\right\rVert_{p}^{p}$ for similar loss functions as we do, and showed that $\lim_{\lambda\rightarrow 0}\mathbf{w}_{\lambda}/\left\lVert{\mathbf{w}_{\lambda}}\right\rVert_{p}$ is proportional to the maximum $L_{p}$ margin solution. That is, they showed how adding infinitesimal $L_{p}$ (e.g. $L_{1}$ and $L_{2}$) regularization to logistic-type losses gives rise to the corresponding max-margin predictor.In contrast, with non-vanishing regularization (i.e., $\lambda>0$), $\arg\min_{\mathbf{w}}\mathcal{L}(\mathbf{w})+\lambda\left\lVert{\mathbf{w}}\right\rVert_{p}^{p}$ is generally not a max margin solution. However, Rosset et al. do not consider the effect of the optimization algorithm, and instead add explicit regularization. Here we are specifically interested in the bias implied by the algorithm not by adding (even infinitesimal) explicit regularization. We see that coordinate descent gives rise to the max $L_{1}$ margin predictor, while gradient descent gives rise to the max $L_{2}$ norm predictor. In Section 4.3 and in follow-up work (Gunasekar et al., 2018) we discuss also other optimization algorithms, and their implied biases.

In this paper we focused on homogeneous linear predictors of the form $\mathbf{w}^{\top}\mathbf{x}$, similarly to previous works (e.g., Rosset et al. (2004); Telgarsky (2013)). Specifically, we did not have the common intercept term: $\mathbf{w}^{\top}\mathbf{x}+b$. One may be tempted to introduce the intercept in the usual way, i.e., by extending all the input vectors $\mathbf{x}_{n}$ with an additional ${}^{\prime}1^{\prime}$ component. In this extended input space, naturally, all our results hold. Therefore, we converge in direction to the $L_{2}$ max margin solution (eq. 4) in the extended space. However, if we translate this solution to the original $\mathbf{x}$ space we obtain

which is not the $L_{2}$ max margin (SVM) solution

where we do not have a $b^{2}$ penalty in the objective.

Implications: Rates of convergence

The solution in eq. 3 implies that $\mathbf{w}\left(t\right)/\left\|\mathbf{w}\left(t\right)\right\|$ converges to the normalized max margin vector $\hat{\mathbf{w}}/\left\|\hat{\mathbf{w}}\right\|.$ Moreover, this convergence is very slow— logarithmic in the number of iterations. Specifically, our results imply the following tight rates of convergence: {thmR}[] Under the conditions and notation of Theorem 2, for any linearly separable data set, the normalized weight vector converges to the normalized max margin vector in $L_{2}$ norm

with this rate improving to $O(1/\log(t))$ for almost every dataset; and in angle

with this rate improving to $O(1/\log^{2}(t))$ for almost every dataset; and the margin converges as

On the other hand, the loss itself decreases as

All the rates in the above Theorem are a direct consequence of Theorem 2, except for avoiding the $\log\log t$ factor for the degenerate cases in eq. 10 and eq. 11 (i.e., establishing that the rates $1/\log t$ and $1/t$ always hold)—this additional improvement is a consequence of the more complete characterization of Theorem 4. Full details are provided in Appendix D. In this appendix, we also provide a simple construction showing all the rates in Theorem 3 are tight (except possibly for the $\log\log t$ factors).

The sharp contrast between the tight logarithmic and $1/t$ rates in Theorem 3 implies that the convergence of $\mathbf{w}(t)$ to the max-margin $\hat{\mathbf{w}}$ can be logarithmic in the loss itself, and we might need to wait until the loss is exponentially small in order to be close to the max-margin solution. This can help explain why continuing to optimize the training loss, even after the training error is zero and the training loss is extremely small, still improves generalization performance—our results suggests that the margin could still be improving significantly in this regime.

A numerical illustration of the convergence is depicted in Figure 1. As predicted by the theory, the norm $\left\|\mathbf{w}(t)\right\|$ grows logarithmically (note the semi-log scaling), and $\mathbf{w}(t)$ converges to the max-margin separator, but only logarithmically, while the loss itself decreases very rapidly (note the log-log scaling).

That is, the population loss increases logarithmically while the margin and the population misclassification error improve. Roughly speaking, the improvement in misclassification does not out-weight the increase in the loss of those points still misclassified.

This behavior might cause us to think we are over-fitting or otherwise encourage us to stop the optimization. However, this increase does not actually represent the model getting worse, merely $\left\lVert{\mathbf{w}(t)}\right\rVert$ getting larger, and in fact the model might be getting better (increasing the margin and possibly decreasing the error rate).

Extensions

So far, we have discussed the problem of binary classification, but in many practical situations we have more then two classes. For multi-class problems, the labels are the class indices $y_{n}\in[K]\triangleq\left\{1,\dots,K\right\}$ and we learn a predictor $\mathbf{w}_{k}$ for each class $k\in[K]$. A common loss function in multi-class classification is the following cross-entropy loss with a softmax output, which is a generalization of the logistic loss:

What do the linear predictors $\mathbf{w}_{k}(t)$ converge to if we minimize the cross-entropy loss by gradient descent on the predictors? In Appendix E we analyze this problem for separable data, and show that again, the predictors diverge to infinity and the loss converges to zero. Furthermore, we prove the following Theorem: {thmR}[] For almost all multiclass datasets (i.e., except for a measure zero) which are linearly separable (i.e. the constraints in eq. 15 below are feasible), any starting point $\mathbf{w}(0)$ and any small enough stepsize, the iterates of gradient descent on 13 will behave as:

where the residual $\boldsymbol{\rho}_{k}(t)$ is bounded and $\hat{\mathbf{w}}_{k}$ is the solution of the K-class SVM:

2 Deep networks

So far we have only considered linear prediction. Naturally, it is desirable to generalize our results also to non-linear models and especially multi-layer neural networks.

Even without a formal extension and description of the precise bias, our results already shed light on how minimizing the cross-entropy loss with gradient descent can have a margin maximizing effect, how the margin might improve only logarithmically slow, and why it might continue to improve even as the validation loss increases. These effects are demonstrated in Figure 2 and Table 1 which portray typical training of a convolutional neural network using unregularized gradient descentCode available here: https://github.com/paper-submissions/MaxMargin. As can be seen, the norm of the weight increases, but the validation error continues decreasing, albeit very slowly (as predicted by the theory), even after the training error is zero and the training loss is extremely small. We can now understand how even though the loss is already extremely small, some sort of margin might be gradually improving as we continue optimizing. We can also observe how the validation loss increases despite the validation error decreasing, as discussed in Section 3.

As an initial advance toward tackling deep network, we can point out that for several special cases, our results may be directly applied to multi-layered networks. First, somewhat trivially, our results may be applied directly to the last weight layer of a neural network if the last hidden layer becomes fixed and linearly separable after a certain number of iterations. This can become true, either approximately, if the input to the last hidden layer is normalized (e.g., using batch norm), or exactly, if the last hidden layer is quantized (Hubara et al., 2018).

Second, as we show next, our results may be applied exactly on deep networks if only a single weight layer is being optimized, and, furthermore, after a sufficient number of iterations, the activation units stop switching and the training error goes to zero.

We examine a multilayer neural network with component-wise ReLU functions $f\left(z\right)=\max\left[z,0\right]$, and weights $\left\{\mathbf{W}_{l}\right\}_{l=1}^{L}$. Given input $\mathbf{x}_{n}$ and target $y_{n}\in\left\{-1,1\right\}$, the DNN produces a scalar output

Proof We examine the output of the network given a single input $\mathbf{x}_{n}$, for $t>t_{0}$. Since the ReLU inputs do not switch signs, we can write $\mathbf{v}_{l}$, the output of layer $l$, as

where we defined $\mathbf{A}_{l,n}$ for $l<L$ as a diagonal 0-1 matrix, which diagonal is the ReLU slopes at layer $l$, sample $n$, and $\mathbf{A}_{L,n}=1$. Additionally, we define

Importantly, this case is non-convex, unless we are optimizing the last layer. Note we assumed ReLU functions for simplicity, but this proof can be easily generalized for any other piecewise linear constant activation functions (e.g., leaky ReLU, max-pooling).

Lastly, in a follow-up work (Gunasekar et al., 2018b), given a few additional assumptions, extended our results to linear predictors which can be written as a homogeneous polynomial in the parameters. These results seem to indicate that, in many cases, GD operating on exp-tailed loss with positively homogeneous predictors aims to a specific direction. This is the direction of the max margin predictor minimizing the $L_{2}$ norm in the parameter space. It is not yet clear how to generally translate such an implicit bias in the parameter space to the implicit bias in the predictor space — except in special cases, such as deep linear neural nets, as we have shown in (Gunasekar et al., 2018b). Moreover, in non-linear neural nets, there are many equivalent max-margin solutions which minimize the $L_{2}$ norm of the parameters. Therefore, it is natural to expect that GD would have additional implicit biases, which select a specific subset of these solutions.

3 Other optimization methods

In this paper we examined the implicit bias of gradient descent. Different optimization algorithms exhibit different biases, and understanding these biases and how they differ is crucial to understanding and constructing learning methods attuned to the inductive biases we expect. Can we characterize the implicit bias and convergence rate in other optimization methods?

In Figure 1 we see that adding momentum does not qualitatively affect the bias induced by gradient descent. In Figure 4 in Appendix F we also repeat the experiment using stochastic gradient descent, and observe a similar asymptotic bias (this was later proved in Nacson et al. (2018)). This is consistent with the fact that momentum, acceleration and stochasticity do not change the bias when using gradient descent to optimize an under determined least squares problem. It would be beneficial, though, to rigorously understand how much we can generalize our result to gradient descent variants, and how the convergence rates might change in these cases.

On the other hand, as an example of how changing the optimization algorithm does change the bias, consider adaptive methods, such as AdaGrad (Duchi et al., 2011) and ADAM (Kingma and Ba, 2015). In Figure 3 we show the predictors obtained by ADAM and by gradient descent on a simple data set. Both methods converge to zero training error solutions. But although gradient descent converges to the $L_{2}$ max margin predictor, as predicted by our theory, ADAM does not. The implicit bias of adaptive methods has in fact been a recent topic of interest, with Hoffer et al. (2017) and Wilson et al. (2017) suggesting they lead to worse generalization, and Wilson et al. (2017) providing examples of the differences in the bias for linear regression problems with the squared loss. Can we characterize the bias of adaptive methods for logistic regression problems? Can we characterize the bias of other optimization methods, providing a general understanding linking optimization algorithms with their biases?

In a follow-up paper (Gunasekar et al., 2018) provided initial answers to these questions. Gunasekar et al. (2018) derived a precise characterization of the limit direction of steepest descent for general norms when optimizing the exp-loss, and show that for adaptive methods such as Adagrad the limit direction can depend on the initial point and step size and is thus not as predictable and robust as with non-adaptive methods.

4 Other loss functions

In this work we focused on loss functions with exponential tail and observed a very slow, logarithmic convergence of the normalized weight vector to the $L_{2}$ max margin direction. A natural question that follows is how does this behavior change with types of loss function tails. Specifically, does the normalized weight vector always converge to the $L_{2}$ max margin solution? How is the convergence rate affected? Can we improve the convergence rate beyond the logarithmic rate found in this work?

5 Matrix Factorization

With multi-layered neural networks in mind, Gunasekar et al. (2017) recently embarked on a study of the implicit bias of under-determined matrix factorization problems, where the squared loss of the linear observation of a matrix is minimized by gradient descent on its factorization. Since a matrix factorization can be viewed as a two-layer network with linear activations, this is perhaps the simplest deep model one can study in full, and can thus provide insight and direction to studying more complex neural networks. Gunasekar et al. conjectured, and provided theoretical and empirical evidence, that gradient descent on the factorization for an under-determined problem converges to the minimum nuclear norm solution, but only if the initialization is infinitesimally close to zero and the step-sizes are infinitesimally small. With finite step-sizes or finite initialization, Gunasekar et al. could not characterize the bias.

The follow-up paper (Gunasekar et al., 2018) studied this same problem with exponential loss instead of squared loss. Under additional assumptions on the asymptotic convergence of update directions and gradient directions, they were able to relate the direction of gradient descent iterates on the factorized parameterization asymptotically to the maximum margin solution with unit nuclear norm. Unlike the case of squared loss, the result for exponential loss are independent of initialization and with only mild conditions on the step size. Here again, we see the asymptotic nature of exponential loss on separable data nullifying the initialization effects thereby making the analysis simpler compared to squared loss.

Summary

We characterized the implicit bias induced by gradient descent on homogeneous linear predictors when minimizing smooth monotone loss functions with an exponential tail. This is the type of loss commonly being minimized in deep learning. We can now rigorously understand:

How gradient descent, without early stopping, induces implicit $L_{2}$ regularization and converges to the maximum $L_{2}$ margin solution, when minimizing for binary classification with logistic loss, exp-loss, or other exponential tailed monotone decreasing loss, as well as for multi-class classification with cross-entropy loss. Notably, even though the logistic loss and the exp-loss behave very different on non-separable problems, they exhibit the same behaviour for separable problems. This implies that the non-tail part does not affect the bias. The bias is also independent of the step-size used (as long as it is small enough to ensure convergence) and is also independent on the initialization (unlike for least square problems).

The convergence of the direction of gradient descent updates to the maximum $L_{2}$ margin solution, however is very slow compared to the convergence of training loss, which explains why it is worthwhile continuing to optimize long after we have zero training error, and even when the loss itself is already extremely small.

We should not rely on plateauing of the training loss or on the loss (logistic or exp or cross-entropy) evaluated on a validation data, as measures to decide when to stop. Instead, we should look at the –$1$ error on the validation dataset. We might improve the validation and test errors even when when the decrease in the training loss is tiny and even when the validation loss itself increases.

Perhaps that gradient descent leads to a max $L_{2}$ margin solution is not a big surprise to those for whom the connection between $L_{2}$ regularization and gradient descent is natural. Nevertheless, we are not familiar with any prior study or mention of this fact, let alone a rigorous analysis and study of how this bias is exact and independent of the initial point and the step-size. Furthermore, we also analyze the rate at which this happens, leading to the novel observations discussed above. Even more importantly, we hope that our analysis can open the door to further analysis of different optimization methods or in different models, including deep networks, where implicit regularization is not well understood even for least square problems, or where we do not have such a natural guess as for gradient descent on linear problems. Analyzing gradient descent on logistic/cross-entropy loss is not only arguably more relevant than the least square loss, but might also be technically easier.

Acknowledgments

The authors are grateful to J. Lee, and C. Zeno for helpful comments on the manuscript. The research of DS was supported by the Israel Science Foundation (grant No. 31/1031), by the Taub foundation and of NS by the National Science Foundation.

Appendix

In the following sub-sections we first prove Theorem A below, which is a version of Theorem 2, specialized for almost every dataset. We then prove Theorem 2 (which is already stated for almost every dataset).

For almost every dataset which is linearly separable (Assumption 1), any $\beta$-smooth decreasing loss function (Assumption 1) with an exponential tail (Assumption 3), any stepsize \eta<2\beta^{-1}\sigma_{\max}^{-2}\left(\text{\mathbf{X}}\right) and any starting point $\mathbf{w}(0)$, the gradient descent iterates (as in eq. 2) will behave as:

where $\hat{\mathbf{w}}$ is the $L_{2}$ max margin vector

the residual $\rho(t)$ is bounded, and so

In the following proofs, for any solution $\mathbf{w}\left(t\right)$, we define

We furthermore denote the minimum margin to a non-support vector as:

The proof in this case is rather short and self-contained (i.e., does not rely on any previous results), and so it helps to clarify the main ideas of the general (more complicated) proof which we will give in the next sections.

Substituting eq. 23 and 24 into eq. 22 and integrating, we obtain, that $\exists C,C^{\prime}$ such that

since $\theta>1$ (eq. 19). Thus, we showed that $\mathbf{r}(t)$ is bounded, which completes the proof for the special case. $\blacksquare$

A.2 Complete proof of Theorem A

Next, we give the proof for the general case (non-infinitesimal step size, and exponentially-tailed functions). Though it is based on a similar analysis as in the special case we examined in the previous section, it is somewhat more involved since we have to bound additional terms.

First, we state two auxiliary lemmata, that are proven below in appendix sections A.4 and A.5:

Let $\mathcal{L}\left(\mathbf{w}\right)$ be a $\beta$-smooth non-negative objective. If $\eta<2\beta^{-1}$, then, for any $\mathbf{w}(0)$, with the GD sequence

we have that $\sum_{u=0}^{\infty}\left\|\nabla\mathcal{L}\left(\mathbf{w}\left(u\right)\right)\right\|^{2}<\infty$ and therefore $\lim_{t\rightarrow\infty}\left\|\nabla\mathcal{L}\left(\mathbf{w}\left(t\right)\right)\right\|^{2}=0.$

Additionally, $\forall\epsilon_{1}>0\,$, $\exists C_{2},t_{2}$, such that $\forall t>t_{2}$, if

First, we note that first term in this equation can be upper-bounded by

where in $\left(1\right)$ we used eq. 20, in $\left(2\right)$ we used eq. 2, and in $\left(3\right)$ we used $\forall x>0:\,x\geq\log\left(1+x\right)>0$, and also that

Substituting eq. 32 into eq. 30, and recalling that a $t^{-\nu}$ power series converges for any $\nu>1$, we can find $C_{0}$ such that

Note that this equation also implies that $\forall\epsilon_{0}$

Next, we would like to bound the second term in eq. 29. From eq. 26 in Lemma A.2, we can find $t_{1},C_{1}$ such that $\forall t>t_{1}$:

Thus, by combining eqs. 35 and 33 into eq. 29, we find

which is a bounded, since $\theta>1$ (eq. 19) and $\mu_{-},\mu_{+}>0$ (Definition 2). Therefore, $\left\|\mathbf{r}\left(t\right)\right\|$ is bounded. $\blacksquare$

A.3 Proof of Theorem 2

By contradiction, we assume that the complementary set is not finite,

Additionally, the set $\mathcal{T}$ is not finite: if it were finite, it would have had a finite maximal point $t_{\max}\in\mathcal{T}$, and then, combining eqs. 28, 29, and 33, we would find that $\forall t>t_{\max}$

which is impossible since $\left\|\mathbf{r}\left(t\right)\right\|^{2}\geq 0$. Furthermore, eq. 33 implies that

where $h\left(t\right)$ is a positive monotone function decreasing to zero. Let $t_{3},t$ be any two points such that $t_{3}<t$, $\left\{t_{3},t_{3}+1,\dots t\right\}\subset\bar{\mathcal{T}}$, and $\left(t_{3}-1\right)\in\mathcal{T}$. For all such $t_{3}$ and $t$, we have

Also, recall that $t_{3}>t_{0}$, so from eq. 34, we have that $\left|\left\|\mathbf{r}\left(t_{3}\right)\right\|-\left\|\mathbf{r}\left(t_{3}-1\right)\right\|\right|<\epsilon_{0}$. Since $\left\|\mathbf{r}\left(t_{3}-1\right)\right\|<\epsilon_{1}$ (from $\mathcal{T}$ definition), we conclude that $\left\|\mathbf{r}\left(t_{3}\right)\right\|\leq\epsilon_{1}+\epsilon_{0}$. Moreover, since $\mathcal{\bar{\mathcal{T}}}$ is an infinite set, we can choose $t_{3}$ as large as we want. This implies that $\forall\epsilon_{2}>0$ we can find $t_{3}$ such that $\epsilon_{2}>h\left(t_{3}\right)$, since $h\left(t\right)$ is a monotonically decreasing function. Therefore, from eq. 36, $\forall\epsilon_{1},\epsilon_{0},\epsilon_{2}$, $\exists t_{3}\in\bar{\mathcal{T}}$ such that

This implies that $\left\|\mathbf{r}\left(t\right)\right\|\rightarrow 0$.

A.4 Proof of Lemma A.2

This proof is a slightly modified version of the proof of Theorem 2 in (Ganti, 2015). Recall a well-known property of $\beta$-smooth functions:

From the $\beta$-smoothness of $\mathcal{L}\left(\mathbf{w}\right)$

The right hand side is upper bounded by a finite constant, since $L\left(\mathbf{w}\left(0\right)\right)<\infty$ and $0\leq\mathcal{L}\left(\mathbf{w}\left(t+1\right)\right)$. This implies

and therefore $\left\|\nabla\mathcal{L}\left(\mathbf{w}\left(t\right)\right)\right\|^{2}\rightarrow 0$. $\blacksquare$

A.5 Proof of Lemma A.2

where in last line we used eqs. 6 and 7 to obtain

We examine the three terms in eq. 40. The first term can be upper bounded by

where in $\left(1\right)$ we used that $\bar{\mathbf{P}}_{1}\hat{\mathbf{w}}=\bar{\mathbf{P}}_{1}\mathbf{X}_{\mathcal{S}}\boldsymbol{\alpha}=0$ from eq. 6, and in $\left(2\right)$ we used that $\hat{\mathbf{w}}^{\top}\mathbf{r}\left(t\right)=o\left(t\right)$, since

where in the last line we used that $\nabla\mathcal{L}\left(\mathbf{w}\left(t\right)\right)=o\left(1\right)$, from Lemma A.2.

Next, we upper bound the second term in eq. 40. From eq. 38 $\exists t_{+}^{\prime}$, such that $\forall>t_{0}>t_{+}^{\prime}$,

Lastly, we will bound the sum in the third term in eq. 40

We examine each term $n$ in this sum, and divide into two cases, depending on the sign of $\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)$.

First, if $\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\geq 0$, then term $n$ in eq. 44 can be upper bounded $\forall t>t_{+}$, using eq. 38, by

If $\left|\mathbf{x}_{n}^{\top}\mathbf{r}(t)\right|\leq C_{0}t^{-0.5\mu_{+}}$, then we can upper bound eq. 45 with

If $\left|\mathbf{x}_{n}^{\top}\mathbf{r}(t)\right|>C_{0}t^{-0.5\mu_{+}}$, then we can find $t_{+}^{\prime\prime}>t_{+}^{\prime}$ to upper bound eq. 45 $\forall t>t_{+}^{\prime\prime}$:

where in $\left(1\right)$ we used the fact that $e^{-x}\leq 1-x+x^{2}$ for $x\geq 0$ and in $\left(2\right)$ we defined $t_{+}^{\prime\prime}$ so that the previous expression is negative — since $t^{-0.5\mu_{+}}$ decreases slower than $t^{-\mu_{+}}$.

This implies that $\forall t>t_{+}^{\prime\prime\prime}$ we can upper bound eq. 45 by

Second, if $\mathbf{x}_{n}^{\top}\mathbf{r}(t)<0$, we again further divide into cases:

If $\left|\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right|>C_{0}t^{-0.5\mu_{-}}$ , then, using eq. 39 we upper bound term $n$ in eq. 44 with

Furthermore, if $\exists t>t_{M}$ such that $\exp\left(\mathbf{r}\left(t\right)^{\top}\mathbf{x}_{n}\right)<M$, then

since $\left|\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right|>C_{0}t^{-0.5\mu_{-}}$, $\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)<0$ and $e^{x}\geq 1+x$. In this case last line is strictly larger than $1$ for sufficiently large $t$. Therefore, after we substitute eqs. 51 and 52 into 50, we find that $\exists t_{-}^{\prime}>t_{M}>t_{-}$ such that $\forall t>t_{-}^{\prime}$, term $k$ in eq. 44 is strictly negative

If $\left|\mathbf{x}_{k}^{\top}\mathbf{r}(t)\right|\geq\epsilon_{2}$ , which is a special case of the previous case ($\left|\mathbf{x}_{k}^{\top}\mathbf{r}\left(t\right)\right|>C_{0}t^{-0.5\mu_{-}}$) then $\forall t>t_{-}^{\prime}$, either eq. 51 or 52 holds. Furthermore, in this case, $\exists t_{-}^{\prime\prime}>t_{-}^{\prime}$ and $M^{\prime\prime}>1$ such that $\forall t>t_{-}^{\prime\prime}$ eq. 52 can be lower bounded by

Substituting this, together with eq. 51, into eq. 50, we can find $C_{0}^{\prime}>0$ such we can upper bound term $k$ in eq. 44 with

To conclude, we choose $t_{0}=\max\left[t_{+}^{\prime\prime\prime},t_{-}^{\prime\prime}\right]$:

If $\left\|\mathbf{P}_{1}\mathbf{r}\left(t\right)\right\|\geq\epsilon_{1}$ (as in Eq. 27), we have that

This implies that $\exists C_{2}<C_{0}^{\prime\prime}$ and $\exists t_{2}>t_{0}$ such that eq. 28 holds. This implies also that eq. 26 holds for $\left\|\mathbf{P}_{1}\mathbf{r}\left(t\right)\right\|\geq\epsilon_{1}$.

Otherwise, if $\left\|\mathbf{P}_{1}\mathbf{r}\left(t\right)\right\|<\epsilon_{1}$, we find that $\forall t>t_{0}$ , each term in eq. 44 can be upper bounded by either zero (eqs. 47 and 53), or terms proportional to $t^{-1-1.5\mu_{+}}$ (eq. 46) or $t^{-1-0.5\mu_{-}}$, (eq. 49). Combining this together with eqs. 41, 43 into eq. 40 we obtain (for some positive constants $C_{3}$, $C_{4}$, $C_{5}$, and $C_{6}$)

Therefore, $\exists t_{1}>t_{0}$ and $C_{1}$ such that eq. 26 holds. $\blacksquare$

B Generic solutions of the KKT conditions in eq. 6

For almost all datasets there is a unique $\boldsymbol{\alpha}$ which satisfies the KKT conditions (eq. 6):

Furthermore, in this solution $\alpha_{n}\neq 0$ if $\hat{\mathbf{w}}^{\top}\mathbf{x}_{n}=1$, i.e., $\mathbf{x}_{n}$ is a support vector ($n\in\mathcal{S}$), and there are at most $d$ such support vectors.

For almost every set $\mathbf{X}$, no more than $d$ points $\mathbf{x}_{n}$ can be on the same hyperplane. Therefore, since all support vectors must lie on the same hyperplane, there can be at most $d$ support vectors, for almost every $\mathbf{X}$.

Given the set of support vectors, $\mathcal{S}$, the KKT conditions of eq. 6 entail that $\alpha_{n}=0$ if $n\notin\mathcal{S}$ and

This implies that $\forall n\in\mathcal{S}$, $\alpha_{n}$ is equal to a rational function in the components of $\mathbf{X}_{S}$, i.e., $\alpha_{n}=p_{n}\left(\text{{X}}_{\mathcal{S}}\right)/q_{n}\left(\text{{X}}_{\mathcal{S}}\right)$, where $p_{n}$ and $q_{n}$ are polynomials in the components of $\mathbf{X}_{S}$. Therefore, if $\alpha_{n}=0$, then $p_{n}\left(\text{{X}}_{\mathcal{S}}\right)=0$, so the components of $\mathbf{X}_{\mathcal{S}}$ must be at a root of the polynomial $p_{n}$. The roots of the polynomial $p_{n}$ have measure zero, unless $\forall\mathbf{X}_{\mathcal{S}}:\,\,p_{n}\left(\text{{X}}_{\mathcal{S}}\right)=0$. However, $p_{n}$ cannot be identically equal to zero, since, for example, if $\mathbf{X}_{\mathcal{S}}^{\top}=\left[\mathbf{I}_{\left|\mathcal{S}\right|\times\left|\mathcal{S}\right|},\boldsymbol{0}_{\left|\mathcal{S}\right|\times\left(d-\left|\mathcal{S}\right|\right)}\right]$, then $\mathbf{X}_{\mathcal{S}}^{\top}\mathbf{X}_{\mathcal{S}}=\mathbf{I}_{\left|\mathcal{S}\right|\times\left|\mathcal{S}\right|}$, and so in this case $\forall n\in\mathcal{S}$, $\alpha_{n}=1\neq 0$, from eq. 57.

Therefore, for a given $\mathcal{S}$, the event that "eq. 56 has a solution with a zero component" has a zero measure. Moreover, the union of these events, for all possible $\mathcal{S}$, also has zero measure, as a finite union of zero measures sets (there are only finitely many possible sets $\mathcal{S}\subset\left\{1,\dots,N\right\}$ ). This implies that, for almost all datasets $\mathbf{X}$, $\alpha_{n}=0$ only if $n\notin\mathcal{S}$. Furthermore, for almost all datasets the solution $\boldsymbol{\alpha}$ is unique: for each dataset, $\mathcal{S}$ is uniquely determined, and given $\mathcal{S}$ , the solution eq. 56 is uniquely given by eq. 57. $\blacksquare$

C Completing the proof of Theorem 2 for zero measure cases

In the preceding Appendices, we established Theorem 2, which only applied when all support vectors are associated with non-zero coefficients. This characterizes almost all data sets, i.e. all except for measure zero. We now turn to presenting and proving a more complete characterization of the limit behaviour of gradient descent, which covers all data sets, including those degenerate data sets not covered by Theorem 2, thus establishing Theorem 2.

In order to do so, we first have to introduce additional notation and a recursive treatment of the data set. We will define a sequence of data sets $\bar{\mathbf{P}}_{m}\mathbf{X}_{\bar{\mathcal{S}}_{m}}$ obtained by considering only a subset $\bar{\mathcal{S}}_{m}$ of the points, and projecting them using the projection matrix $\bar{\mathbf{P}}_{m}$. We start, for $m=0$, with the full original data set, i.e. $\bar{\mathcal{S}}_{0}=\{1,\ldots,N\}$ and $\bar{\mathbf{P}}_{0}=\mathbf{I}_{d\times d}$. We then define $\hat{\mathbf{w}}_{m}$ as the max margin predictor for $\bar{\mathbf{P}}_{m-1}\mathbf{X}_{\bar{\mathcal{S}}_{m-1}}$, i.e.:

In particular, $\hat{\mathbf{w}}_{1}$ is the max margin predictor for the original data set. We then denote $\mathcal{S}_{m}^{+}$ the indices of non-support vectors for 58, $\mathcal{S}_{m}$ the indices of support vector of 58 with non-zero coefficients for the dual variables corresponding to the margin constraints (for some dual solution), and $\bar{\mathcal{S}}_{m}$ the set of support vector with zero coefficients. That is:

The problematic degenerate case, not covered by the analysis of Theorem 2, is when there are support vectors with zero coefficients, i.e., when $\bar{\mathcal{S}}_{m}\neq\emptyset$. In this case we recurse on these zero-coefficient support vectors (i.e., on $\bar{\mathcal{S}}_{m}$), but only consider their components orthogonal to the non-zero-coefficient support vectors (i.e., not spanned by points in $\mathcal{S}_{m}$). That is, we project using:

where we denoted $\mathbf{A}^{\dagger}$ as the Moore-Penrose pseudo-inverse of $\mathbf{A}$. We also denote $\mathbf{P}_{m}=\mathbf{I}_{d}-\bar{\mathbf{P}}_{m}$.

This recursive treatment continues as long as $\bar{\mathcal{S}}_{m}\neq\emptyset$, defining a sequence $\hat{\mathbf{w}}_{m}$ of max margin predictors, for smaller and lower dimensional data sets $\bar{\mathbf{P}}_{m-1}\mathbf{X}_{\bar{\mathcal{S}}_{m-1}}$. We stop when $\bar{\mathcal{S}}_{m}=\emptyset$ and denote the stopping stage $M$—that is, $M$ is the minimal $m$ such that $\bar{\mathcal{S}}_{m}=\emptyset$. Our characterization will be in terms of the sequence $\hat{\mathbf{w}}_{1},\ldots,\hat{\mathbf{w}}_{M}$. As established in Lemma 3 of Appendix B, for almost all data sets we will not have support vectors with non-zero coefficients, and so we will have $M=1$, and so the characterization only depends on the max margin predictor $\hat{\mathbf{w}}_{1}$ of the original data set. But, even for the measure zero of data sets in which $M>1$, we provide the following more complete characterization:

For all datasets which are linearly separable (Assumption 1) and given a $\beta$-smooth loss function (Assumption 1) with an exponential tail (Assumption 3), gradient descent (as in eq. 2) with step size \eta<2\beta^{-1}\sigma_{\max}^{-2}\left(\text{\mathbf{X}}\right) and any starting point $\mathbf{w}(0)$, the iterates of gradient descent can be written as:

Lastly, we define, $\forall m>k\geq 1$, $\check{\mathbf{w}}_{k,m}$ as the solution of

The existence and uniqueness of the solution $\check{\mathbf{w}}_{k,m}$ are proved in appendix section C.5.

Together, eqs. 62-65 entail the existence of a unique decomposition, $\forall m\geq 1:$

given the constraints in eqs. 63 and 65 hold.

C.2 Proof of Theorem 4

In the following proofs, for any solution $\mathbf{w}(t)$, we define

First, we note that $\exists t_{0}$ such that $\forall t>t_{0}$ the first term in this equation can be upper bounded by

Substituting eq. 71 into eq. 69, and recalling that $t^{-\nu_{1}}\log^{-\nu_{2}}\left(t\right)$ converges for any $\nu_{1}>1$ and any $\nu_{2}$, and so

Also, in the next subsection we will prove that

Let $\kappa_{1}\left(t\right)$ and $\kappa_{2}\left(t\right)$ be functions in $L_{1}$, then

Thus, by combining eqs. 73 and 72 into eq. 68, we find

On this result we apply the following lemma (with $\phi\left(t\right)=\|\mathbf{r}(t)\|$, $h\left(t\right)=2\kappa_{1}\left(t\right)$, and $z\left(t\right)=\kappa_{0}\left(t\right)+2\kappa_{2}\left(t\right)$), which we prove in appendix C.6:

since we assumed that $\forall i=0,1,2:\,\kappa_{i}\left(t\right)\in L_{1}$. This completes our proof. $\blacksquare$

C.3 Proof of Lemma C.2

Before we prove Lemma C.2, we prove the following auxilary Lemma: {lemR}[] Consider the function $f(t)=t^{-\nu_{1}}(\log(t))^{-\nu_{2}}(\log\log(t))^{-\nu_{3}}\ldots(\log^{\circ M}(t))^{-\nu_{M+1}}$. If $\exists m_{0}\leq M+1$ such that $\nu_{m_{0}}>1$ and for all $m^{\prime}<m_{0}$,$\nu_{m^{\prime}}=1$, then $f(t)\in L_{1}$.

Proof To prove Lemma C.3, we will show that the improper integeral $\int_{t_{1}}^{\infty}f(t)dt$ for any $t_{1}>0$ is bounded, i.e., $\forall t_{1}>0,\int_{t_{1}}^{\infty}f(t)dt<C$. Using the integeral test for convergence (or Maclaurin–Cauchy test) this in turn implies that $\forall t_{1}>0,\sum_{t_{1}}^{\infty}f(t)<C$, and thus $f(t)\in L_{1}$.

First, if $m_{0}>1$, then $\nu_{1}=\nu_{2}\ldots=\nu_{m_{0}-1}=1$ and $\nu_{m_{0}}=1+\epsilon$ for some $\epsilon>0$. Using change of variables $y=\log^{\circ(m_{0}-1)}(t)$, we have

Additionally, we define $C_{h},C_{h}^{\prime}$ so that

where in $\left(1\right)$ we used eq. 78 and in $\left(2\right)$ we used the definition of GD in eq. 2. We can bound the second term using Cauchy-Shwartz inequality and eq. 81:

Next, we examine the second term in eq. 85

where in $(1)$ recall from eq. C that $\mathcal{S}_{m},\mathcal{S}_{m}^{+}$ are mutually exclusive and $\cup_{m=1}^{M}\mathcal{S}_{m}\cup\mathcal{S}_{m}^{+}=[N]$.

Next we upper bound the three terms in eq. 86.

To bound the first term in eq. 86 we use Cauchy-Shartz, and eq. 84.

where in $\left(1\right)$ we used eqs. 78 and 79, in $\left(2\right)$ we used that $\forall x:xe^{-x}\leq 1$ and $\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\geq 0$, $\left(3\right)$ we used eq. 83 and in $\left(4\right)$ we denoted $\theta_{m}=\min_{n\in\mathcal{S}_{m}^{+}}\hat{\mathbf{w}}_{m}^{\top}\mathbf{x}_{n}>1$ and the last line is integrable based on Lemma C.3.

Next, we bound the last term in eq. 86. For exponential tailed losses (Assumption 3), since $\mathbf{w}(t)^{\top}\mathbf{x}_{n}\to\infty$, we have positive constants $\mu_{-},\mu_{+}>0$, $t_{-}$ and $t_{+}$ such that $\forall n$

From this result, we have the following set of inequalities:

where in $\left(1\right)$ we used eqs. 78 and 79, and in $\left(2\right)$ we used $\mathbf{P}_{k-1}\check{\mathbf{w}}_{k,m}=0$ from eq. 65 (so $\mathbf{x}_{n}^{\top}\check{\mathbf{w}}_{k,l}=0$ if $m<k$) and in $\left(3\right)$ defined

Note $\exists t_{\psi}$ such that $\forall t>t_{\psi}$, we can bound $\psi_{m}\left(t\right)$ by

where $(1)$ follows from the bound in eq. 91.

$\forall t>t_{1}>t_{\psi}$, where we will determine $t_{1}$ later. We have the following for all $m\in[M]$

where we set $t_{1}>0$ such that $\forall t>t_{1}$ the term in the square bracket is positive and

in $\left(1\right)$ we used that since $e^{-x}\geq 1-x$, and also from using $e^{-x}x\leq 1$ and in $\left(2\right)$ we use that $\forall x\geq-1$ we have that $e^{-x}\leq 1-x+x^{2}$ and $\psi_{m}\left(t\right)\leq 1$ from eq. 93.

We examine the second term in eq. 94 using the decomposition of $\hat{\mathbf{w}}_{m}$ from eq. 66

where in $\left(1\right)$ we used eq. 66, in $\left(2\right)$ we re-arranged the order of summation in the last term, and in $(3)$ we just use a change of variables.

Next, we examine $\Gamma_{m,n}(t)$ for each $m$ and $n\in\mathcal{S}_{m}$ in eq. 96. Note that, $\exists t_{2}>t_{\psi}$ such that $\forall t>t_{2}$ we have

where in $\left(1\right)$ follows from the definition of $t_{2}$, wherein

First, if $\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)>0$, then $\gamma_{n}(t)=(1+\exp(-\mu_{+}\mathbf{w}(t)^{\top}\mathbf{x}_{n}))>0$.

We further divide into two cases. In the following $C_{0},C_{1}$ are some constants independent of $t$.

If $\left|\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right|>C_{0}t^{-0.5\mu_{+}}$, then we have the following

where in $(1)$, we use $\psi_{m}(t)\leq 1$ from eq. 93 and using eq. 78, in $(2)$ we used bound on $\mathbf{h}_{m}$ from eq. 83, in $(3)$ for some large enough $t_{+}^{\prime}>t_{+}$, we have $\frac{\exp(\mu_{+}C_{h}\left\lVert{\mathbf{x}_{n}}\right\rVert)}{\left(\prod_{r=1}^{m-1}\log^{\circ r}\left(t\right)\right)^{\mu_{+}}}\leq C_{1}$, and for the second term we used the inequality $e^{-x}\leq 1-x+0.5x^{2}$ for $x>0$, and $(4)$ holds asymptotically for $t>t_{+}^{\prime\prime}$ for large enough $t_{+}^{\prime\prime}>t_{+}^{\prime}$ as $C_{0}t^{-0.5\mu_{+}}$ converges slower than $0.5C_{0}^{2}t^{-\mu_{+}}$ to 0.

Thus, using eq. 98 in eq. 97, $\forall t>\max{(t_{2},t_{+}^{\prime\prime})}$, we have

If $0<\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)<C_{0}t^{-0.5\mu_{+}}$, then we have the following: $\psi_{m}(t)\leq 1$ from eq. 93, $\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)\leq 1$ as $\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)>0$, and since $\mathbf{w}(t)^{\top}\mathbf{x}_{n}\to\infty$, for large enough $t>t_{+}^{\prime\prime\prime}$, $\gamma_{n}(t)=\left(1+\exp\left(-\mu_{+}\mathbf{w}(t)^{\top}\mathbf{x}_{n}\right)\right)\leq 2$

This gives us, $\left(\gamma_{n}(t)\psi_{m}(t)\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)-1\right)\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\leq\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\leq C_{0}t^{-0.5\mu_{+}}$, and using this in eq. 97, $\forall t>\max{(t_{2},t_{+}^{\prime})}$

Second, if $\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\leq 0$, then $\gamma_{n}(t)=(1-\exp(-\mu_{-}\mathbf{w}(t)^{\top}\mathbf{x}_{n}))\in(0,1)$. We again divide into following special cases.

If $\psi_{m}\left(t\right)\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)<1,$ then, from eq. 93

In this case, since $\gamma_{n}(t)=1-\exp(-\mathbf{w}(t)^{\top}\mathbf{x}_{n})<1$, we also have $\gamma_{n}(t)\psi_{m}\left(t\right)\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)<1$, and hence $\left(\gamma_{n}(t)\psi_{m}\left(t\right)\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)-1\right)\mathbf{x}_{n}^{\top}\mathbf{r}(t)>0$. Thus, $\forall t>t_{2}$, in 97, $\kappa_{n}(t)=1.5$, and we have

where $(1)$ follows from $\left(1-\gamma_{n}(t)\psi_{m}\left(t\right)\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)\right)<1$ and the bound on $|\mathbf{x}_{n}^{\top}\mathbf{r}(t)|=-\mathbf{x}_{n}^{\top}\mathbf{r}(t)$ from eq. 99.

Since, $\mathbf{x}_{n}^{\top}\mathbf{w}(t)\to\infty$ and $\psi_{m}(t)\to 1$ from eq. 92, for large enough $t_{-}^{\prime}>t_{-}$, we have $\forall t>t_{-}^{\prime}$, $\psi_{m}(t)>0.5$ and $\gamma_{n}(t)=(1-\exp(-\mu_{-}\mathbf{x}_{n}^{\top}\mathbf{w}(t)))>0.5$. Let $\tau>\max{(4,t_{-}^{\prime})}$ be an arbitrarily large constant. For all $t>\tau$, if $\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)>\tau\geq 4$, then $\gamma_{n}(t)\psi_{m}(t)\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)>0.25\tau\geq 1$.

On the other hand, if there exists $t>\tau\geq 4$, such that $\exp\left(-\mathbf{x}_{n}^{\top}\mathbf{r}\left(t\right)\right)<\tau$, then for some constants $C_{1},C_{2}$ we have the following

$\psi_{m}(t)\geq\exp\left(-C_{1}\left(\log^{\circ(m-1)}(t)\right)^{-1}\right)\geq\left(1-C_{1}\left(\log^{\circ(m-1)}(t)\right)^{-1}\right)$ from eq. 93 and again using $e^{x}>1+x$ for all $x$,

where the last inequality follows as for large enough $t_{-}^{\prime\prime}>t_{-}^{\prime}$, we have $\frac{\exp(-C_{h}\|x_{n}\|)\tau}{t\prod_{r=1}^{m-2}\log^{\circ r}(t)}\leq C_{2}$.

Finally, using eq. 100 in eq. 97, we have for all $t>\max{(t_{2},\tau,t_{\psi},t_{-}^{\prime\prime\prime})}$

Collecting all the terms from the above special cases, and substituting back into eq. 85, we note that all terms are either negative, in $L_{1}$, or of the form $f\left(t\right)\left\|\mathbf{r}\left(t\right)\right\|$, where $f\left(t\right)\in L_{1}$, thus proving the lemma.

C.4 Proof of the existence and uniqueness of the solution to eqs. 62-63

we have a unique solution. From eq. 103, we can modify eq. 102 to

In other words, $\mathbf{u}_{1}$ is in the direction of $\mathbf{\hat{\mathbf{w}}}_{1}$, $\left[\mathbf{u}_{1},\dots,\mathbf{u}_{K}\right]$ are in the space spanned by the columns of $\mathbf{X}_{\mathcal{S}_{1}}$, and $\left[\mathbf{u}_{K+1},\dots,\mathbf{u}_{d}\right]$ are orthogonal to the columns of $\mathbf{X}_{\mathcal{S}_{1}}$.

Multiplying by $\mathbf{U}^{\top}$ from the left, we obtain

Since $\mathbf{u}_{1}=\mathbf{\hat{\mathbf{w}}}_{1}/\left\|\mathbf{\hat{\mathbf{w}}}_{1}\right\|$, we have that

We recall that $v_{1,n}=\hat{\mathbf{w}}_{1}^{\top}\mathbf{x}_{n}/\left\|\mathbf{\hat{\mathbf{w}}}_{1}\right\|=1/\left\|\mathbf{\hat{\mathbf{w}}}_{1}\right\|,$ $\forall n\in\mathcal{S}_{1}$. Given $\left\{s_{j}\right\}_{j=2}^{K}$, we examine eq. 108 for $i=1$,

This equation always has the unique solution

given $\left\{s_{j}\right\}_{j=2}^{K}$. Next, we similarly examine eq. 108 for $2\leq i\leq K$ as a function of $s_{i}$

multiplying by $\exp\left(s_{1}/\left\|\mathbf{\hat{\mathbf{w}}}_{1}\right\|\right)$ we obtain

Therefore, any critical point of $E\left(s_{2},\dots,s_{K}\right)$ would be a solution of eq. 110 for $2\leq i\leq K$, and substituting this solution into eq. 109 we obtain $s_{1}$. Since $\beta_{n}>0$, $E\left(s_{2},\dots,s_{K}\right)$ is a convex function, as positive linear combination of convex function (exponential). Therefore, any finite critical point is a global minimum. All that remains is to show that a finite minimum exists and that it is unique.

Therefore, $\forall\left(s_{2,}\dots,s_{K}\right)\neq\mathbf{0}$ we have that

Recall, from eq. 105 that $\forall\left(s_{2,}\dots,s_{K}\right)\neq\mathbf{0},\exists n\in\mathcal{S}_{1}:\,\sum_{j=2}^{K}s_{j}v_{j,n}\neq 0$, and that $\alpha_{n}>0$. Therefore, eq. 112 implies that $\exists n\in\mathcal{S}_{1}$ such that $\sum_{j=2}^{K}s_{j}v_{j,n}>0$ and also $\exists m\in\mathcal{S}_{1}$ such that $\sum_{j=2}^{K}s_{j}v_{j,m}<0$.

Thus, in any direction we take a limit in which $\left|s_{i}\right|\rightarrow\infty$ $\forall 2\leq i\leq K$, we obtain that $E\left(s_{2},\dots,s_{K}\right)\rightarrow\infty$, since at least one exponent in the sum diverge. Since $E\left(s_{2},\dots,s_{K}\right)$, is a continuous function, it implies it has a finite global minimum. This proves the existence of a finite solution. To prove uniqueness we will show the function is strictly convex, since the hessian is (strictly) positive definite, i.e., that the following expression is strictly positive:

C.5 Proof of the existence and uniqueness of the solution to eqs. 64-65

have a unique solution $\check{\mathbf{w}}_{k,m}$.

Proof For this proof we denote $\mathbf{X}_{\mathcal{S}_{k}}$ as the matrix which columns are $\left\{\mathbf{x}_{n}|n\in\mathcal{S}_{k}\right\}$, the orthogonal projection matrix $\mathbf{Q}_{k}=\mathbf{P}_{k}\bar{\mathbf{P}}_{k-1}$where $\mathbf{Q}_{k}\mathbf{Q}_{m}=0$ $\forall k\neq m$, $\mathbf{Q}_{k}\bar{\mathbf{P}}_{m}=0$ $\forall k<m$, and

Next, we prove the existence and uniqueness of the solution $\check{\mathbf{w}}_{k,m}$ for each $k=1,\dots,m$ separately. We multiply eq. 113 from the left by the identity matrix, decomposed to orthogonal projection matrices as in eq. 115. Since each matrix projects to an orthogonal subspace, we can solve each product separately.

The product with $\bar{\mathbf{P}}_{m}$ is equal to zero for both sides of the equation. The product with $\mathbf{Q}_{k}$ is equal to

Substituting eq. 116, and multiplying by $\mathbf{W}_{k,m}^{\top}$ from the right, we obtain

where in $\left(1\right)$ we used that $\mathbf{E}_{k}$ is diagonal and non-zero, and in $\left(2\right)$ we used eq. 117. This implies that the $d_{k}\times d_{k}$ matrix in eq. 119 is full rank, and so eq. 118 has a unique solution $\mathbf{u}_{k,m}$. Therefore, there exists a unique solution $\check{\mathbf{w}}_{k,m}$.

C.6 Proof of Lemma C.2

Proof We define $\psi\left(t\right)=z\left(t\right)+h\left(t\right)$, and start from eq. 74

we keep iterating eq. 74, until we obtain

Therefore, the Lemma holds with $C_{2}=\left(\phi\left(1\right)+C\right)\exp\left(C\right)$ and $C_{3}=\exp\left(C\right)$.

D Calculation of convergence rates

In this section we calculate the various rates mentioned in section 3.

From Theorems 2 and 4, we can write $\mathbf{w}\left(t\right)=\hat{\mathbf{w}}\log t+\boldsymbol{\rho}\left(t\right)$, where $\boldsymbol{\rho}\left(t\right)$ has a bounded norm for almost all datasets, while in zero measure case $\boldsymbol{\rho}\left(t\right)$ contains additional $O(\log\log(t))$ components which are orthogonal to the support vectors in $\mathcal{S}_{1}$, and, asymptotically, have a positive angle with the other support vectors. In this section we first calculate the various convergence rates for the non-degenerate case of Theorem 2, and then write the correction in the zero measure cases, if there is such a correction.

First, we calculated of the normalized weight vector (eq. 8), for almost every dataset:

where to obtain eq. 120 we used $\frac{1}{\sqrt{1+x}}=1-\frac{1}{2}x+\frac{3}{4}x^{2}+O\left(x^{3}\right)$, and in the last line we used the fact that $\boldsymbol{\rho}\left(t\right)$ has a bounded norm for almost every dataset. Thus, in this case

Next, we use eq. 120 to calculate the angle (eq. 9)

for almost every dataset. Thus, in this case

Repeating the same calculation for the measure zero case, we have instead

Calculation of the training loss (eq. 11):

Thus, for all datasets $\mathcal{L}\left(\mathbf{w}\left(t\right)\right)=O(t^{-1})$. Note that the zero measure case has the same behavior, since after a sufficient number of iterations, the $O(\log\log(t))$ correction has a non-negative angle with all the support vectors.

We can analytically integrate these equations to obtain

Using this example with $w_{2}\left(0\right)>0$, it is easy to see that the above upper bounds are strict in the non-degenerate case. $\blacksquare$