Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate

INTRODUCTION

Deep neural networks (DNNs) are commonly trained using stochastic gradient descent (SGD), or one of its variants. During training, the learning rate is typically decreased according to some schedule (e.g., every $T$ epochs we multiply the learning rate by some $\alpha<1$). Determining the learning rate schedule, and its dependency on other factors, such as the minibatch size, has been the subject of a rapidly increasing number of recent empirical works (Hoffer et al. (2017); Goyal et al. (2017); Jastrzebski et al. (2017); Smith et al. (2018) are a few examples). Therefore, it is desirable to improve our understanding of such issues. However, somewhat surprisingly, we observe that we do not have even a satisfying answer to the basic question

Why do we need to decrease the learning rate during training?

At first, it may seem that this question has already been answered. Many previous works have analyzed SGD theoretically (e.g., see Robbins and Monro (1951); Bertsekas (1999); Geary and Bertsekas (2001); Bach and Moulines (2011); Ben-David and Shalev-Shwartz (2014); Ghadimi et al. (2013); Bubeck (2015); Bottou et al. (2016); Ma et al. (2017) and references therein), under various assumptions. In all previous works, to the best of our knowledge, one must assume a vanishing learning rate schedule, averaging of the SGD iterates, partial strong convexity (i.e., strong convexity in some subspace), or the Polyak-Lojasiewicz (PL) condition (Bassily et al., 2018) — so that the SGD increments or the loss (in the convex case) will converge to zero for generic datasets. However, even near its global minima, a neural network loss is not partially strongly convex, and the PL condition does not hold. Therefore, without a vanishing learning rate or iterate averaging, the gradients are only guaranteed to decrease below some constant value, proportional to the learning rate. Thus, in this case, we may fluctuate near a critical point, but never converge to it.

Consequently it may seem that in neural networks we should always decrease the learning rate in SGD or average the weights, to enable the convergence of the weights to a critical point, and to decrease the loss. However, this reasoning does not hold empirically. In many datasets, even with a fixed learning rate and without averaging, we observe that the training loss can converge to zero. For example, we examine the learning dynamics of a ResNet-18 trained on CIFAR10 in Figure 1. Even though the learning rate is fixed, the training loss converges to zero (and so does the classification error).

Notably, we do not observe any convergence issues, as we may have suspected from previous theoretical results. In fact, if we decrease the learning rate at any point, this only decreases the convergence rate of the training loss to zero. The main benefit of decreasing the learning rate is that it typically improves generalization performance. Such contradiction between existing theoretical and empirical results may indicate a significant gap in our understanding. We are therefore interested in closing this gap.

To do so, we first examine the network dynamics in Figure 1. Since the training error has reached zero after a certain number of iterations, by then the last hidden layer must have become linearly separable. Since the network is trained using the monotone cross-entropy loss (with softmax outputs), by increasing the norm of the weights we decrease the loss. Therefore, if the loss is minimized then the weights would tend to diverge to infinity — as indeed happens. This weight divergence does not affect the scale-insensitive validation (classification) error, which continues to decrease during training. In contrast, the validation loss starts to increase.

To explain this behavior, Soudry et al. (2018b, a) focused on the dynamics of the last layer, for a fixed separable input and no bias. For Gradient Descent (GD) dynamics, Soudry et al. (2018b, a) proved that the training loss converges to zero as $1/t$, the direction of the weight vector converges to the max margin as $1/\log(t)$, and the validation loss increase as $\log(t)$. This had similar dynamics to those observed in Figure 1. However, the dynamics of GD are simpler than those of SGD. Notably, it is well known that on smooth functions, for the iterates of GD, the gradient converges to zero even with a fixed learning rate — just as long as this learning rate is below some fixed threshold (which depends on the smoothness of the function).

In this paper we examine SGD optimization of homogeneous linear classifiers with smooth monotone loss functions, where the data is sampled either with replacement (the sampling regime typically examined in theory), or without replacement (the sampling regime typically used in practice). For simplicity, we focus on binary classification (e.g., logistic regression). First, we prove three basic results:

The norm of the weights diverges to infinity for any learning rate.

For a sufficiently small fixed learning rate, the loss and gradients converge to zero.

This upper bound we derived for the maximal learning rate is proportional to the minibatch size, when the data in SGD is sampled with replacement.

Similar behavior to the last property is also observed in deep networks (Goyal et al., 2017; Smith et al., 2018). Next, given an additional assumption that the loss function has an exponential tail (e.g., logistic regression), we prove that for almost all linearly separable datasets (i.e., except for measure zero cases):

The direction of the weight vector converges to that of the $L_{2}$ max margin solution.

The margin converges as $O(1/\log(t))$, while the training loss converges as $O(1/t)$.

These conclusions for SGD are the same as for GD (Soudry et al., 2018b) — the only difference is the value of the maximal learning rate, which depends on the minibatch size. Therefore, we believe our SGD results might be similarly extended, as GD, to multi-class (Soudry et al., 2018a), other loss functions (Nacson et al., 2019), other optimization methods (Gunasekar et al., 2018b), linear convolutional neural networks (Gunasekar et al., 2018a), and hopefully to nonlinear deep networks.

Finally, under the assumption that the SVM support vectors span the dataset, we further characterize SGD iterate asymptotic behavior. Specifically, we show that, if we keep the learning rate proportional to the minibatch size, then:

The minibatch size does not affect the asymptotic convergence rate of SGD, in terms of epochs.

In terms of SGD iterations, the fastest asymptotic convergence rate, is obtained at full batch size, i.e. GD.

These results suggest the large potential of parallelism in separable problems, as observed in deep networks (Goyal et al., 2017; Smith et al., 2018).

PRELIMINARIES

Consider a dataset $\left\{\mathbf{x}_{n},y_{n}\right\}_{n=1}^{N}$, with binary labels $y_{n}\in\left\{-1,1\right\}$ . We analyze learning by minimizing an empirical loss of homogeneous linear predictors (i.e., without bias), of the form

We are particularly interested in problems that are linearly separable and with a smooth strictly decreasing and non-negative loss function. Therefore, we assume:

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

Given that the data is linearly separable, the maximal $L_{2}$ margin is strictly positive

Many common loss functions, including the logistic and probit losses, follow Assumption 1. Assumption 1 also straightforwardly implies that $\mathcal{L}\left(\mathbf{w}\right)$ is a $\beta\sigma_{\max}^{2}$-smooth function, where the columns of $\mathbf{X}$ are all samples, and $\sigma_{\max}$ is the maximal singular value of $\mathbf{X}$.

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 Stochastic Gradient Descent (SGD) with a fixed learning rate $\eta$, i.e., with steps of the form:

where $\mathcal{B}\left(t\right)\subset\left\{1,\dots,N\right\}$ is a minibatch of $B$ distinct indices, chosen so $K=N/B$ is an integer, and that it satisfies one of the following assumptions. The first option is the assumption of random sampling with replacement:

[Random sampling with replacement] At each iteration $t$ we randomly and uniformly sample a minibatch $\mathcal{B}(t)$ of $B$ distinct indices, i.e. so each sample has an identical probability to be selected.

For example, this assumption holds if at each iteration we uniformly sample the indices without replacement from $\left\{1,\dots,N\right\}$, or uniformly sample $k\in\{1,\dots,K\}$ and select $\mathcal{B}\left(t\right)=\mathcal{B}_{k}$, where $\{\mathcal{B}_{k}\}_{k=0}^{K-1}$ is some fixed partition of the data indices, i.e.,

This assumption is rather common in theoretical analysis, but less common in practice. The next alternative sampling method is more common in practice:

At each epoch, the minibatches partition the data:

This way, each sample is chosen exactly once at each epoch, and SGD completes balanced passes over the data. An important special case of this assumption is random sampling without replacement, which is the practically common method. Other special cases are periodic sampling (round-robin), and even adversarial selection of the order of the samples.

MAIN RESULT 1: THE LOSS CONVERGES TO A GLOBAL INFIMUM

The weight norm always diverges to infinity, for any learning rate, as we prove next.

Given assumptions 1 and 1, and any starting point $\mathbf{w}(0)$, the iterates of SGD on $\mathcal{L}\left(\mathbf{w}\right)$ (eq. 3), with either sampling regimes (Assumption 3a or 3b), diverge to infinity, i.e. $\left\|\mathbf{w}\left(t\right)\right\|\rightarrow\infty$.

Since the data is linearly separable, $\exists\mathbf{w}_{*}$ such that $\forall n:\,\mathbf{w}_{*}\mathbf{x}_{n}>0$. We examine the dot product of $\mathbf{w}^{*}$ with the iterates of SGD

Combing both cases, we prove the theorem. ∎

As the weights go to infinity, we wish to understand the asymptotic behavior of the loss. As the next theorem shows, if the fixed learning rate $\eta$ is sufficiently small, then we get that the loss converges to zero.

Let $\mathbf{w}\left(t\right)$ be the iterates of SGD (eq. 3) from any starting point $\mathbf{w}(0)$, where samples are either (case 1) selected randomly with replacement (Assumption 3a)) and with learning rate

or (case 2) sampled without replacement (Assumption 3b)) and with learning rate

For linearly separable data (Assumption 1), and smooth-monotone loss function (Assumption 1), we have the following, almost surely (with probability $1$) in the first case, and surely in the second case:

All samples are correctly classified, given sufficiently long time:

The complete proof of this theorem is given in section A in the appendix. The proof relies on the following key lemma

The $L_{2}$ max margin lower bounds the minimal “non-negative right eigenvalue” of $\mathbf{X}$

In this proof we define $\mathbf{v^{*}}$ as the minimizer of the right hand side of eq. 6, and $\mathbf{w}_{*}$ as the maximizer of the optimization problem on the left hand side of the same equation. On the one hand

where in $\left(1\right)$ we used Cauchy-Shwartz inequality, and in $\left(2\right)$ we used the definition of $\mathbf{v}^{*}$, and that $\left\|\mathbf{w}_{*}\right\|=1$. On the other hand,

This Lemma is useful since the SGD weight increments in eq. 3 have the form $\mathbf{Xv}$, where $\mathbf{v}$ is some vector with non-negative components. This enables us to bound the norm of the SGD updates using the norm of the full gradient, which allows us to use similar analysis as for GD. Additionally, we note the regime we analyze in Theorem 1 is somewhat unusual, as the weight vector goes to infinity. In many previous works it is assumed that there exists a finite critical point, or that the weights are bounded within a compact domain.

In both sampling regimes, we obtained that a fixed (non-vanishing) learning rate results in convergence to zero error. In the case of random sampling with replacement (Assumption 3a) we got a better upper bound on the learning rate (eq. 4), which does not depend on $K$. Interestingly, this bound matches the empirical findings of Goyal et al. (2017); Smith et al. (2018), which observed that in a large range $\eta\propto B$. Interestingly, in our case the relation $\eta\propto B$ holds exactly for all $B$ in the maximum learning rate (eq. 4). In contrast, for linear regression, the relation becomes sub-linear for large $B$ (Ma et al., 2017).

We also considered here the case when the datapoints are sampled without replacement (Assumption 3b). This is in contrast to most theoretical SGD results, which typically assume sampling with replacement (which is less common in practice). There are a few notable exceptions (Geary and Bertsekas (2001); Bertsekas (2011); Shamir (2016), and references therein). Perhaps the most similar previous result is the classical result of (Proposition 2.1 in Geary and Bertsekas (2001)), which has a similar sampling schedule, and in which the weights can go to infinity. However, in this result the learning rate must go to zero for the SGD iterates to converge. In our case, we are able to relax this assumption since we focus on linear classification with a monotone loss and separable data.

When assuming sampling without replacement (Assumption 3b) the learning rate bound (eq. 5) becomes significantly lower — roughly proportional to $1/K$. This is because such a sampling assumption is very pessimistic (e.g., the samples can be selected by an adversary). Therefore, a small (yet non vanishing) learning rate is required to guarantee convergence. Such a dependence on $K$ is expected, since in this case we need to use a incremental gradient method type of proof, where such low learning rates are common. For example, in Bertsekas (2011) Proposition 3.2b, to get a low final error we must have a learning rate $\eta\ll 1/K^{2}$.

MAIN RESULT 2: THE WEIGHT VECTOR DIRECTION CONVERGES TO THE MAX MARGIN

Next, we focus on a special case of monotone loss functions:

A function $f(u)$ has a “tight exponential tail", if there exist positive constants $\mu_{+},\mu_{-}$, and $\bar{u}$ such that $\forall u>\bar{u}$:

Specifically, this applies to the logistic loss function. Given this additional assumption, we prove that SGD converges to the $L_{2}$ max margin solution.

where $\hat{\mathbf{w}}$ is the following $L_{2}$ max margin separator:

and the residual $\|\boldsymbol{\rho}(t)\|$ is bounded almost surely in the first case of Theorem 1 (random sampling with replacement), or surely in the second case (sampling without replacement).

Thus, from Theorem 2, for almost any linearly separable data set (e.g., with probability 1 if the data is sampled from an absolutely continuous distribution) , the normalized weight vector converges to the normalized max margin vector, i.e.,

with rate $1/\log(t)$, identically to GD (Soudry et al., 2018b). Interestingly, the number of minibatches per epoch $K$ affects only the constants. Intuitively, this is reasonable, since if we rescale the time units, then the log term in eq. 9 will only add a constant to the residual $\rho(t)$.

The theorem is proved in appendix section B.1. The proof builds on the results of Soudry et al. (2018b) for GD: as the weights diverge, the loss converges to zero, and only the gradients of the support vector remain significant. This implies that the gradient direction, as a positive linear combination of support vectors converges to the direction of the max margin. The main difficulty in extending the proof to the case of SGD is that at each iteration, ${\mathbf{w}}(t)$ is updated using only a subset of the data points. This could potentially lead to large difference from the GD solution. However, conceptually, we show that this difference of $\mathbf{w}(t)$ from the GD dynamics solution is $O(1)$ in $t$. The main novel idea here is that in order to calculate this $O(1)$ difference at time $t$, we use information on sampling selections made in the future, i.e. at times larger than $t$.

Theorem 2 directly implies the same convergence rates as in GD (Soudry et al., 2018b). Specifically, in the $L_{2}$ distance

On the other hand, the loss itself decreases as

Under the conditions and notation of Theorem 3, SGD iterate will behave as:

From the corollary, we expect the same asymptotic convergence rates for all batch sizes $B$ as long as we scale the learning rate linearly with the batch size, i.e., keep $\eta\propto B$. This is exactly the behavior we observe in Figure 3. Since changing the number of minibatches is equivalent to linearly re-scaling the time units, smaller $K$ implies faster asymptotic convergence assuming full parallelization capabilities (i.e. the minibatch size does not affect the iterate time). Additionally, note that the corollary only guarantees the same asymptotic behavior. Particularly, different initializations and datasets can exhibit different behavior initially. It remains an interesting direction for future work to understand $\rho(t)$ dependence on $\eta$ and $B$, in the case when the support vectors do not span the dataset.

Lastly, for logistic regression loss, the validation loss (calculated on an independent validation set $\mathcal{V}$) increases as

Notably, as was observed in Soudry et al. (2018b), these asymptotic rates also match what we observe numerically for the convnet in Figure 1: the training loss decreases as $1/t$, the validation loss increases as $\log(t)$, and the validation (classification) improves very slowly, similarly to the logarithmic decay of the angle gap (so the convnet might have a similarly slow decay to its respective implicit bias).

DISCUSSION AND RELATED WORKS

In Theorem 1 we proved that for monotone smooth loss functions on linearly separable data, the iterates of SGD with a sufficiently small (but non-vanishing) learning rate converge to zero loss. In contrast to typical convergence to finite critical points, in this case, the "noise" inherent in SGD vanishes asymptotically. Therefore, we do not need to decrease the learning rate, or average the SGD iterates, to ensure exact convergence. Decaying the learning rate during training will only decrease the convergence speed of the loss.

To the best of our knowledge, such exact convergence result previously required that either (1) the loss function is partially strongly convex, i.e. strongly convex except on some subspace (where the dynamics are frozen), as shown in (Ma et al., 2017) for the case of over-parameterized linear regression (with more parameters then samples); or (2) that the Polyak-Lojasiewicz (PL) condition applies (Bassily et al., 2018). However, in this paper we do not require such conditions, which does not hold for deep networks, even in the vicinity of the (finite or infinite) critical points. Moreover, the dependence of the learning rate on the minibatch size is different, as we discuss next.

We proved Theorem 1 both for random sampling with replacement (Assumption 3a) and for sampling without replacement (Assumption 3b). In the first case, eq. 4 implies that, to guarantee convergence, we need to increase the learning rate proportionally to the minibatch size. In the second case (sampling without replacement) the learning rate bound (eq. 5) is more pessimistic, since our assumption is more general (e.g., it includes adversarial sampling).

In Theorem 2, we proved, given the additional assumption of an exponential tail (e.g., as in logistic regression), that for almost all datasets the weight vector converges to the $L_{2}$ max margin in direction as $1/\log(t)$, and that the training loss converges to zero as $1/t$. We believe these results could be extended for every dataset, using the techniques of Soudry et al. (2018a). Again, decaying the learning rate will only degrade the convergence speed to the max margin direction. In fact, the results of Nacson et al. (2019) indicate that we may need to increase the learning rate to improve convergence: For GD, Nacson et al. (2019) proved that this can drastically improve the convergence rate from $1/\log(t)$ to $\log(t)/\sqrt{t}$. It is yet to be seen if such results might also be applied to deep networks.

In Theorem 3 we further characterized the weights asymptotic behaviour under the additional assumption that the SVM support vectors span the dataset. Combining the results from Theorem 2 and Theorem 3 we obtain Corollary 1. This corollary states that, under linear scaling of the learning rate with the batch size, the asymptotic convergence rate of SGD, in terms of epochs, is not affected by the mini-batch size.

Thus, we have shown that exact linear scaling of the learning rate with the minibatch size ($\eta\propto B$) is beneficial in two ways: (a) in Theorem 1 for the upper bound of the learning rate in the case of of random sampling with replacement (b) in Corollary 1 for the asymptotic behaviour of the weights assuming tight exponential loss function and that the SVM support vectors span the data. This exact linear scaling, stands in contrast to previous theoretical results with exact convergence (Ma et al., 2017), in which there exists a "saturation limit". Above this limit we should not increase the learning rate linearly with the minibatch size, or the convergence rate will be degraded, and eventually we will loose the convergence guarantee. As predicted by Corollary 1, in Figure 3 we observe that with a linear scaling $\eta\propto B$, the convergence plots exactly match: as we can see, there is almost no asymptotic difference between different minibatch sizes. Therefore, in contrast to Ma et al. (2017), there is no "optimal" minibatch size. In this case, to minimize the number of SGD iterations we should use the largest minibatch possible. This will speed up convergence in wall clock time (as was done in Goyal et al. (2017); Smith et al. (2018)) if it is possible to parallelize the calculation of a minibatch — so one SGD update with a minibatch of size $MB$ takes less time then $M$ updates of SGD with minibatch of size $B$.

An early version of this manuscript previously appeared on arxiv. However, it had only the results in the case of sampling without replacement, and no Theorem 3. Two other related SGD results appeared on arXiv in parallel (with less than a week difference).

CONCLUSIONS

We found that for logistic regression with no bias on separable data, SGD behaves similarly to GD in terms of the implicit bias and convergence rate. The only difference is the maximum possible learning rate should change proportionally to the minibatch size. It remains to be seen if this also holds for deep networks.

The authors are grateful to C. Zeno, and I. Golan for helpful comments on the manuscript. This research was supported by the Israel Science foundation (grant No. 31/1031), and by the Taub foundation. A Titan Xp used for this research was donated by the NVIDIA Corporation. NS was partially supported by NSF awards IIS-1302662 and IIS-1764032.

References

Appendix

For simplicity of notation, in the appendix we absorb the constant $1/B$ in the SGD dynamics into the learning rate dynamics:

In the main paper, we modify the results proven in the appendix to fit the SGD dynamics in eq. 3.

Next, we will rely on this key fact to prove our results for each case.

Combining this equation with equation 19, and taking the limit of $c$ to $\infty$, we obtain

Therefore, with probability 1, we have $\forall n:$ $\mathbf{w}\left(t\right)^{\top}\mathbf{x}_{n}\rightarrow\infty$, which implies $\mathcal{L}\left(\mathbf{w}\left(t\right)\right)\rightarrow 0$. Moreover,

where in $\left(1\right)$ we used eq. 17, and $\left(2\right)$ is true with probability 1 from eq. 20.

A.2 Case 2: Sampling without replacement

Linear separability enforces a lower bound on the norm of these increments (eq. 17, which follows form Lemma 2). This bound enables us to bound the SGD increments, and other related quantities, in terms of the norm of the full gradient (Lemma 3 below).

where in $\left(1\right)$ we used eq. 21 and the first two equations in Lemma 3, in $\left(2\right)$ we recall we assumed that $\eta<1/(2K\beta\sigma_{\max}^{2})$ in eq. 5, and in $(3)$ we denoted $q=2\beta\sigma_{\max}^{3}\gamma^{-1}\left(K+\gamma^{-1}\sigma_{\max}\right)$. Recall we assumed $\eta q<1$ in eq. 5. Summing $t$ over $0,K,2K,\dots,$we obtain

since $\mathcal{L}\left(\mathbf{w}\right)\geq 0$ and $\eta q<1$ according to our assumption on $\eta$.

Next, we consider general time $t$ (i.e., not only first iteration at epochs, as we assumed until now). We note that, for any $k$ such that $t+k-1$ is in the same epoch as $t$, we have that

where we used the last equation in Lemma 3. Thus, combining the last two equations we obtain

which also implies that $\left\|\nabla\mathcal{L}\left(\mathbf{w}\left(t\right)\right)\right\|\rightarrow 0$. Next, we recall eq. 17 to obtain

Combining eq. 23 and 22 we obtain that $\sum_{t=0}^{\infty}\left\|\mathbf{w}\left(t+1\right)-\mathbf{w}\left(t\right)\right\|^{2}<\infty\,.$ $\blacksquare$

A.3 Proof of Lemma 3

First, we prove the following technical Lemma.

Let $\epsilon$ and $\gamma$ be two positive constants. If $\delta_{k}\leq\theta+\epsilon\sum_{u=0}^{k-1}\delta_{u},$ then

Also, from the first and last lines in the above equation, we have

With this result in hand, we complete the proof by direct calculation

where in $(1)$ we added and subtracted the same term, in $(2)$ we used the triangle inequality, and in $\left(3\right)$ we used eq. 26 and also eq. 17 to obtain

Next, we apply eq. 24 from Lemma 4 on eq. 27, with $\delta_{k}=\left\|\mathbf{w}\left(t+k\right)-\mathbf{w}\left(t\right)\right\|,$ $\epsilon=\eta\beta\sigma_{\max}^{2}$, and $\theta=\eta\left(\sigma_{\max}/\gamma\right)\left\|\nabla\mathcal{L}\left(\mathbf{w}\left(t\right)\right)\right\|$ to obtain

Combining eqs. 26, 29, with eq. 25 implies

Finally, using eq. 29 we can directly prove the last part of the Lemma

Thus, we proved the Lemma, from the last equation, together with eqs. 29 and 31. $\blacksquare$

Appendix B Proof of Theorems 2 and 3

In our proof we will use two auxiliary lemmata.

The following holds almost surely (with probability $1$) for random sampling with replacement, and surely for sampling without replacement:

where $\mathcal{S}$ is the set of indices of support vectors index, $\alpha_{n}$ are the SVM dual variables (so $\hat{\mathbf{w}}=\sum_{n\in\mathcal{S}}\alpha_{n}{\mathbf{x}_{n}}$), $\check{\mathbf{w}}$ is some finite vector which is constant in $t$ (but can depend on the sample indices selected in the future), and $\forall$$\epsilon>0$, $\mathbf{m}_{1}(t)$ is some vector such that $\left\|\mathbf{m}_{1}\left(t\right)\right\|=o\left(t^{-0.5+\epsilon}\right)$, and $\left\|\mathbf{m}_{1}\left(t+1\right)-\mathbf{m}_{1}\left(t\right)\right\|=O\left(t^{-1}\right).$

This Lemma is proved in section B.4. We define

Such a solution exists for almost every dataset, as a consequence of Lemma 12 in Soudry et al. (2018a). We denote the minimum margin to a non-support vector as:

and since $\forall\epsilon>0\ :\ \left\lVert\mathbf{m}_{1}(t)\right\rVert=o\left(t^{-1+\epsilon}\right)$, using the triangle inequality we can write

Our goal is to show that $\left\|\mathbf{r}\left(t\right)\right\|$ is bounded, and therefore $\boldsymbol{\rho}\left(t\right)$ is bounded.

Since $\left\|\mathbf{m}_{1}\left(t+1\right)-\mathbf{m}_{1}\left(t\right)\right\|=O\left(t^{-1}\right)$ and $\forall t>0\ :\ \log(1+t^{-1})\leq t^{-1}$ we can write

where in (1) we used Cauchy–Schwarz inequality, and in (2) we used eq. 40.

We take the limit $T\to\infty$ . Using the fact that $\forall v>1:\ \sum_{t=1}^{\infty}t^{-v}<\infty$ and $\sum_{t=1}^{\infty}\left\lVert{\mathbf{w}}(t+1)-{\mathbf{w}}(t)\right\rVert^{2}<\infty$ from Theorem 1, we have that $\exists C_{0}$ such that

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

Combining eqs. 36, 39 and 41, and using the fact that $\forall v>1:\ \sum_{t=1}^{\infty}t^{-v}<\infty$ we obtain

and therefore ${\mathbf{r}}(t)$ is bounded. $\blacksquare$

B.2 Theorem 3 Proof

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. 38, 39, and 41, we would find that $\forall t>t_{\max}$

which is impossible since $\left\|\mathbf{r}\left(t\right)\right\|^{2}\geq 0$. Furthermore, eq. 41 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. 42, 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. 43, $\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$.

B.3 Proof of Lemma 6

See 6 We focus on functions with exponential tail (definition 1):

Eq. 33 (${\mathbf{r}}(t)$ definition) implies that

Using this definition, the second term in eq. 46 is

Using the last equation, eq. 44 and the fact that $\forall x\leq 1\ :\ e^{x}\leq 1+x+x^{2}$, eq. 49 can be upper bounded by

If $\mathbf{x}_{k}^{\top}{\mathbf{r}}(t)\geq\epsilon_{2}$ then $\exists t^{\prime}+\geq t_{+}$ so that

where we defined $C_{+}^{\prime\prime}=\min_{n}\alpha_{n}K\left(1-\exp\left(-0.5\epsilon_{2}\right)\right)\epsilon_{2}$.

We will now show that this equation is negative for sufficiently large $t$. We need to show that

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

If $|\mathbf{x}_{k}^{\top}{\mathbf{r}}(t)|>\epsilon_{2}$ and $\mathbf{x}_{n}^{\top}{\mathbf{r}}(t)<0$ then $\exists t^{\prime}_{-}\geq t_{-},M^{\prime\prime}>1$ so that

and thus eq. 49 can be upper bounded $\forall t\geq t_{-}^{\prime}$ by

where we defined $C_{-}^{\prime\prime}=\min_{n}\alpha_{n}K\left(M^{\prime\prime}-1\right)\epsilon_{2}$.

In conclusion, $\forall t\geq\max\left(t_{+}^{\prime},t_{-}^{\prime},t_{3}\right)$

If, in addition, $\left\lVert\mathbf{P}{\mathbf{r}}\left(t\right)\right\rVert\geq\epsilon_{1}$ (eq. 37), we have that

This implies that $\exists C_{4},\bar{t}_{2}\geq\max\left(t_{+}^{\prime},t_{-}^{\prime},t_{3}\right)$ so that $\forall t\geq\bar{t}_{2}$ we have

B.4 Proof of Lemma 5

We define $z_{t,n}$ as the random variable equal to $1$ if sample $n$ is selected at iteration $t$, and otherwise. Using this variable, we can write

where $\gamma$ is the Euler-Mascheroni constant. Next, we bound the remaining terms. We examine the value of the infinite sum for all $n$:

we have, by the Hoeffding inequality, that $\forall c$

Taking $T$ and $c$ to infinity and using $\sum_{k=1}^{\infty}\frac{1}{k^{2}}=\frac{\pi^{2}}{6}$ we get that this sum is convergent with probability $1$, i.e.

and therefore, by the Hoeffding inequality,

Taking $c$ to infinity we obtain that, with probability $1$, $\forall\epsilon>0$

Recalling that $\hat{\mathbf{w}}=\sum_{n\in\mathcal{S}}\alpha_{n}{\mathbf{x}_{n}}$, and denoting

we combine this with eq. 56, 55, 54 into eq. 53. This proves the Lemma since $\check{\mathbf{w}}$ is a finite constant with probability 1, and $\mathbf{m}_{1}(t)=o\left(t^{-0.5+\epsilon}\right)$ and $\mathbf{m}_{1}(t+1)-\mathbf{m}_{1}(t)=O\left(t^{-1}\right)$. $\square$

where in the last line we recall we defined $u_{n,k}$ as the index of the $n$’th example minibatch in the $k$’th epoch and therefore $1\leq u_{n,k}\leq K$, and use the fact that we can write the second term as $\mathbf{m}_{1}\left(t\right)$ since it is $O\left(t^{-1}\right)$ and is also is difference (i.e., $\mathbf{m}_{1}(t+1)-\mathbf{m}_{1}(t)=O\left(t^{-1}\right)$) — it is a finite sum of $Cu^{-1}$ terms where $u\geq t$-2. Next, we examine the remaining term for a given $n$:

where in the last line we used the relations

where $\gamma$ is the Euler-Mascheroni constant. We examine the remaining sum in eq. 58. Since $1\leq u_{n,k}\leq K,$ each term in the sum is $\Theta\left(k^{-2}\right)$, which implies that this sum is convergent, and we can write it as

Recalling that $\hat{\mathbf{w}}=\sum_{n\in\mathcal{S}}\alpha_{n}{\mathbf{x}_{n}}$, defining

and combining this into eq. 57, using eq. 58, we prove the Lemma. $\square$

Appendix C Additional empirical results