New Convergence Aspects of Stochastic Gradient Algorithms

Introduction

We are interested in solving the following stochastic optimization problem

where $\xi$ is a random variable obeying some distribution.

In the case of empirical risk minimization with a training set $\{(x_{i},y_{i})\}_{i=1}^{n}$, $\xi_{i}$ is a random variable that is defined by a single random sample $(x,y)$ pulled uniformly from the training set. Then, by defining $f_{i}(w):=f(w;\xi_{i})$, empirical risk minimization reduces to

To apply SGD to the general form (1) one needs to assume existence of unbiased gradient estimators. This is usually defined as follows:

for any fixed $w$. Here we make an important observation: if we view (1) not as a general stochastic problem but as the expected risk minimization problem, where $\xi$ corresponds to a random data sample pulled from a distribution, then (1) has an additional key property: for each realization of the random variable $\xi$, $f(w;\xi)$ is a convex function with Lipschitz continuous gradients. Notice that traditional analysis of SGD for general stochastic problem of the form (1) does not make any assumptions on individual function realizations. In this paper we derive convergence properties for SGD applied to (1) with these additional assumptions on $f(w;\xi)$ and also extend to the case when $f(w;\xi)$ are not necessarily convex.

Regardless of the properties of $f(w;\xi)$ we assume that $F$ in (1) is strongly convex. We define the (unique) optimal solution of $F$ as $w_{*}$.

It is well-known in literature Nesterov (2004); Bottou et al. (2018) that Assumption 1 implies

The classical theoretical analysis of SGD assumes that the stochastic gradients are uniformly bounded, i.e. there exists a finite (fixed) constant $\sigma<\infty$, such that

On the other hand strong convexity and $\nabla F(w_{*})=0$ imply

The last two inequalities are clearly in contradiction with each other for sufficiently large $\|w-w_{*}\|^{2}$.

In Recht et al. (2011), an asynchronous stochastic optimization method called Hogwild! was proposed. Hogwild! algorithm is a parallel version of SGD, where each processor applies SGD steps independently of the other processors to the solution $w$ which is shared by all processors. Thus, each processor computes a stochastic gradient and updates $w$ without "locking" the memory containing $w$, meaning that multiple processors are able to update $w$ at the same time. This approach leads to much better scaling of parallel SGD algorithm than a synchoronous version, but the analysis of this method is more complex. In Recht et al. (2011); Mania et al. (2017); De Sa et al. (2015) various variants of Hogwild! with a fixed step size are analyzed under the assumption that the gradients are bounded as in (5). In this paper, we extend our analysis of SGD to provide analysis of Hogwild! with diminishing step sizes and without the assumption on bounded gradients.

In a recent technical report Leblond et al. (2018) Hogwild! with fixed step size is analyzed without the bounded gradient assumption. We note that SGD with fixed step size only converges to a neighborhood of the optimal solution, while by analyzing the diminishing step size variant we are able to show convergence to the optimal solution with probability one. Both in Leblond et al. (2018) and in this paper, the version of Hogwild! with inconsistent reads and writes is considered.

It is well-known that SGD will converge if a sequence of learning rates $\{\eta_{t}\}$ satisfies the following conditions (1) $\sum_{t=0}^{\infty}\eta_{t}\rightarrow\infty$ and (2) $\sum_{t=0}^{\infty}\eta^{2}_{t}<\infty$. As an important contribution of this paper, we show the convergence of SGD for strongly convex objective function without using bounded gradient assumption when $\{\eta_{t}\}$ is a diminishing sequence and $\sum_{t=0}^{\infty}\eta_{t}\rightarrow\infty$. In Moulines and Bach (2011), the authors also proved the convergence of SGD for $\{\eta_{t}=\operatorname{\mathcal{O}}(1/t^{q})\},0<q\leq 1,$ without using bounded gradient assumption and the second condition. Compared to Moulines and Bach (2011), we prove the convergence of SGD for $\{\eta_{t}=\operatorname{\mathcal{O}}(1/t^{q})\}$ which is $1/\mu$ times larger and our proposed class of learning rates satisfying the convergence of SGD is larger. Our proposed class of learning rates satisfying the convergence of SGD is larger than the current state-of-the art one.

We would like to highlight that this paper is originally from Nguyen et al. (2018) (Proceedings of the 35th International Conference on Machine Learning, 2018) but it presents a substantial extension by providing many new results for SGD and Hogwild!.

We provide a new framework for the analysis of stochastic gradient algorithms in the strongly convex case under the condition of Lipschitz continuity of the individual function realizations, but without requiring any bounds on the stochastic gradients. Within this framework we have the following contributions:

We prove the almost sure (w.p.1) convergence of SGD with diminishing step size. Our analysis provides a larger bound on the possible initial step size when compared to any previous analysis of convergence in expectation for SGD.

We introduce a general recurrence for vector updates which has as its special cases (a) the Hogwild! algorithm with diminishing step sizes, where each update involves all non-zero entries of the computed gradient, and (b) a position-based updating algorithm where each update corresponds to only one uniformly selected non-zero entry of the computed gradient.

We analyze this general recurrence under inconsistent vector reads from and vector writes to shared memory (where individual vector entry reads and writes are atomic in that they cannot be interrupted by writes to the same entry) assuming that there exists a delay $\tau$ such that during the $(t+1)$-th iteration a gradient of a read vector $w$ is computed which includes the aggregate of all the updates up to and including those made during the $(t-\tau)$-th iteration. In other words, $\tau$ controls to what extent past updates influence the shared memory.

Our upper bound for the expected convergence rate is $O(1/t)$, and its precise expression allows comparison of algorithms (a) and (b) described above.

For SGD we can improve this upper bound by a factor of 2 and also show that its initial step size can be larger.

We show that $\tau$ can be a function of $t$ as large as $\sqrt{(t/lnt)(1-1/lnt)}$ without affecting the asymptotic behavior of the upper bound; we also determine a constant $T_{0}$ with the property that, for $t\geq T_{0}$, higher order terms containing parameter $\tau$ are smaller than the leading $O(1/t)$ term. We give intuition explaining why the expected convergence rate is not more affected by $\tau$. Our experiments confirm our analysis.

We determine a constant $T_{1}$ with the property that, for $t\geq T_{1}$, the higher order term containing parameter $\|w_{0}-w_{*}\|^{2}$ is smaller than the leading $O(1/t)$ term.

All the above contributions generalize to the setting where we do not need to assume that the component functions $f(w;\xi)$ are convex in $w$.

Compared to Nguyen et al. (2018), we have following new results:

We prove the almost sure (w.p.1) convergence of Hogwild! with a diminishing sequence of learning rates $\{\eta_{t}\}$.

We prove the convergence of SGD for diminishing sequences of learning rates $\{\eta_{t}\}$ with condition $\sum_{t=0}^{\infty}\eta_{t}\rightarrow\infty$. In other words, we extend the current state-of-the-art class of learning rates satisfying the convergence of SGD.

We prove the convergence of SGD for our extended class of learning rates in batch model.

2 Organization

We analyse the convergence rate of SGD in Section 2 and introduce the general recursion and its analysis in Section 3. Section 4 studies the convergence of SGD for our extended class of learning rates. Experiments are reported in Section 5.

New Framework for Convergence Analysis of SGD

We introduce SGD algorithm in Algorithm 1.

The sequence of random variables $\{\xi_{t}\}_{t\geq 0}$ is assumed to be i.i.d.Independent and identically distributed. Let us introduce our key assumption that each realization $\nabla f(w;\xi)$ is an $L$-smooth function.

The following additional convexity assumption can be made, as it holds for many problems arising in machine learning.

We first derive our analysis under Assumptions 2, and 3 and then we derive weaker results under only Assumption 2.

Using Lemma 1 and Super Martingale Convergence Theorem Bertsekas (2011) (Lemma 5 in Appendix A), we can provide the sufficient condition for almost sure convergence of Algorithm 1 in the strongly convex case without assuming any bounded gradients.

Let Assumptions 1, 2 and 3 hold. Consider Algorithm 1 with a stepsize sequence such that

Then, the following holds w.p.1 (almost surely)

Note that the classical SGD proposed in Robbins and Monro (1951) has learning rate satisfying conditions

However, the original analysis is performed under the bounded gradient assumption, as in (5). In Theorem 1, on the other hand, we do not use this assumption, but instead assume Lipschitz smoothness and convexity of the function realizations, which does not contradict the strong convexity of $F(w)$.

The following result establishes a sublinear convergence rate of SGD.

Let Assumptions 1, 2 and 3 hold. Let $E=\frac{2\alpha L}{\mu}$ with $\alpha=2$. Consider Algorithm 1 with a stepsize sequence such that $\eta_{t}=\frac{\alpha}{\mu(t+E)}\leq\eta_{0}=\frac{1}{2L}$. Then,

2 Convergence Analysis without Convexity

In this section, we provide the analysis of Algorithm 1 without using Assumption 3, that is, $f(w;\xi)$ is not necessarily convex. We still do not need to impose the bounded stochastic gradient assumption, since we can derive an analogue of Lemma 1, albeit with worse constant in the bound.

Based on the proofs of Theorems 1 and 2, we can easily have the following two results (Theorems 3 and 4).

Let Assumptions 1 and 2 hold. Then, we can conclude the statement of Theorem 1 with the definition of the step size replaced by $0<\eta_{t}\leq\frac{1}{2L\kappa}$ with $\kappa=\frac{L}{\mu}$.

Let Assumptions 1 and 2 hold. Then, we can conclude the statement of Theorem 2 with the definition of the step size replaced by $\eta_{t}=\frac{\alpha}{\mu(t+E)}\leq\eta_{0}=\frac{1}{2L\kappa}$ with $\kappa=\frac{L}{\mu}$ and $\alpha=2$, and all other occurrences of $L$ in $E$ and $T$ replaced by $L\kappa$.

By introducing Assumption 2, which holds for many ML problems, we are able to provide the values of $M$ and $N$. Recall that under Assumption 3, our initial learning rate is $\eta_{0}=\frac{1}{2L}$ (in Theorem 2). Thus Assumption 3 provides an improvement of the conditions on the learning rate.

Asynchronous Stochastic Optimization aka Hogwild!

Hogwild! Recht et al. (2011) is an asynchronous stochastic optimization method where writes to and reads from vector positions in shared memory can be inconsistent (this corresponds to (13) as we shall see). However, as mentioned in Mania et al. (2017), for the purpose of analysis the method in Recht et al. (2011) performs single vector entry updates that are randomly selected from the non-zero entries of the computed gradient as in (12) (explained later) and requires the assumption of consistent vector reads together with the bounded gradient assumption to prove convergence. Both Mania et al. (2017) and De Sa et al. (2015) prove the same result for fixed step size based on the assumption of bounded stochastic gradients in the strongly convex case but now without assuming consistent vector reads and writes. In these works the fixed step size $\eta$ must depend on $\sigma$ from the bounded gradient assumption, however, one does not usually know $\sigma$ and thus, we cannot compute a suitable $\eta$ a-priori.

As claimed by the authors in Mania et al. (2017), they can eliminate the bounded gradient assumption in their analysis of Hogwild!, which however was only mentioned as a remark without proof. On the other hand, the authors of recent unpublished work Leblond et al. (2018) formulate and prove, without the bounded gradient assumption, a precise theorem about the convergence rate of Hogwild! of the form

where $\rho$ is a function of several parameters but independent of the fixed chosen step size $\eta$ and where $b$ is a function of several parameters and has a linear dependency with respect to the fixed step size, i.e., $b=O(\eta)$.

We first formulate a general recursion for $w_{t}$ to which our analysis applies, next we will explain how the different variables in the recursion interact and describe two special cases, and finally we present pseudo code of the algorithm using the recursion.

The recursion explains which positions in $w_{t}$ should be updated in order to compute $w_{t+1}$. Since $w_{t}$ is stored in shared memory and is being updated in a possibly non-consistent way by multiple cores who each perform recursions, the shared memory will contain a vector $w$ whose entries represent a mix of updates. That is, before performing the computation of a recursion, a core will first read $w$ from shared memory, however, while reading $w$ from shared memory, the entries in $w$ are being updated out of order. The final vector $\hat{w}_{t}$ read by the core represents an aggregate of a mix of updates in previous iterations.

The general recursion is defined as follows: For $t\geq 0$,

$\hat{w}_{t}$ represents the vector used in computing the gradient $\nabla f(\hat{w}_{t};\xi_{t})$ and whose entries have been read (one by one) from an aggregate of a mix of previous updates that led to $w_{j}$, $j\leq t$, and

the $S^{\xi_{t}}_{u_{t}}$ are diagonal 0/1-matrices with the property that there exist real numbers $d_{\xi}$ satisfying

where the expectation is taken over $u$ and $D_{\xi}$ is the diagonal 0/1 matrix whose $1$-entries correspond to the non-zero positions in $\nabla f(w;\xi)$ in the following sense: The $i$-th entry of $D_{\xi}$’s diagonal is equal to 1 if and only if there exists a $w$ such that the $i$-th position of $\nabla f(w;\xi)$ is non-zero.

The role of matrix $S^{\xi_{t}}_{u_{t}}$ is that it filters which positions of gradient $\nabla f(\hat{w}_{t};\xi_{t})$ play a role in (10) and need to be computed. Notice that $D_{\xi}$ represents the support of $\nabla f(w;\xi)$; by $|D_{\xi}|$ we denote the number of 1s in $D_{\xi}$, i.e., $|D_{\xi}|$ equals the size of the support of $\nabla f(w;\xi)$.

We will restrict ourselves to choosing (i.e., fixing a-priori) non-empty matrices $S^{\xi}_{u}$ that “partition” $D_{\xi}$ in $D$ approximately “equally sized” $S^{\xi}_{u}$:

where each matrix $S^{\xi}_{u}$ has either $\lfloor|D_{\xi}|/D\rfloor$ or $\lceil|D_{\xi}|/D\rceil$ ones on its diagonal. We uniformly choose one of the matrices $S^{\xi_{t}}_{u_{t}}$ in (10), hence, $d_{\xi}$ equals the number of matrices $S^{\xi}_{u}$, see (11).

In other to explain recursion (10) we first consider two special cases. For $D=\bar{\Delta}$, where

where $[\nabla f(\hat{w}_{t};\xi_{t})]_{u_{t}}$ denotes the $u_{t}$-th position of $\nabla f(\hat{w}_{t};\xi_{t})$ and where $u_{t}$ is a uniformly selected position that corresponds to a non-zero entry in $\nabla f(\hat{w}_{t};\xi_{t})$.

At the other extreme, for $D=1$, we have exactly one matrix $S^{\xi}_{1}=D_{\xi}$ for each $\xi$, and we have $d_{\xi}=1$. This gives the recursion

Recursion (13) represents Hogwild!. In a single-core setting where updates are done in a consistent way and $\hat{w}_{t}=w_{t}$ yields SGD.

Algorithm 2 gives the pseudo code corresponding to recursion (10) with our choice of sets $S^{\xi}_{u}$ (for parameter $D$).

2 Analysis

Besides Assumptions 1, 2, and for now 3, we assume the following assumption regarding a parameter $\tau$, called the delay, which indicates which updates in previous iterations have certainly made their way into shared memory $w$.

We say that shared memory is consistent with delay $\tau$ with respect to recursion (10) if, for all $t$, vector $\hat{w}_{t}$ includes the aggregate of the updates up to and including those made during the $(t-\tau)$-th iteration (where (10) defines the $(t+1)$-st iteration). Each position read from shared memory is atomic and each position update to shared memory is atomic (in that these cannot be interrupted by another update to the same position).

In other words in the $(t+1)$-th iteration, $\hat{w}_{t}$ equals $w_{t-\tau}$ plus some subset of position updates made during iterations $t-\tau,t-\tau+1,\ldots,t-1$. We assume that there exists a constant delay $\tau$ satisfying Assumption 4.

3 Convergence With Probability One

Appendix D.5 proves the following theorem

Let Assumptions 1, 2, 3 and 4 hold. Consider Hogwild! method described in Algorithm 2 with a stepsize sequence such that

Then, the following holds w.p.1 (almost surely)

4 Convergence in Expectation

Appendix D.2 proves the following theorem where

Suppose Assumptions 1, 2, 3 and 4 and consider Algorithm 2 for sets $S^{\xi}_{u}$ with parameter $D$. Let $\eta_{t}=\frac{\alpha_{t}}{\mu(t+E)}$ with $4\leq\alpha_{t}\leq\alpha$ and $E=\max\{2\tau,\frac{4L\alpha D}{\mu}\}$. Then, the expected number of single vector entry updates after $t$ iterations is equal to

with $\alpha_{SGD}=2$ as opposed to $\alpha\geq 4$.

With respect to parallelism, SGD assumes a single core, while (13) and (12) allow multiple cores. Notice that recursion (12) allows us to partition the position of the shared memory among the different processor cores in such a way that each partition can only be updated by its assigned core and where partitions can be read by all cores. This allows optimal resource sharing and could make up for the difference between $\bar{\Delta}_{D}$ for (12) and (13). We hypothesize that, for a parallel implementation, $D$ equal to a fraction of $\bar{\Delta}$ will lead to best performance.

Surprisingly, the leading term of the upper bound on the convergence rate is independent of delay $\tau$. On one hand, one would expect that a more recent read which contains more of the updates done during the last $\tau$ iterations will lead to better convergence. When inspecting the second order term in the proof in Appendix D.2, we do see that a smaller $\tau$ (and/or smaller sparsity) makes the convergence rate smaller. That is, asymptotically $t$ should be large enough as a function of $\tau$ (and other parameters) in order for the leading term to dominate.

Nevertheless, in asymptotic terms (for larger $t$) the dependence on $\tau$ is not noticeable. In fact, Appendix D.4 shows that we may allow $\tau$ to be a monotonic increasing function of $t$ with

where $L(t)=\frac{1}{\ln t}-\frac{1}{(\ln t)^{2}}$ (this will make $E=\max\{2\tau(t),\frac{4L\alpha D}{\mu}\}$ also a function of $t$). The leading term of the convergence rate does not change while the second order terms increase to $O(\frac{1}{t\ln t})$. We show that, for

Our intuition behind this phenomenon is that for large $\tau$, all the last $\tau$ iterations before the $t$-th iteration use vectors $\hat{w}_{j}$ with entries that are dominated by the aggregate of updates that happened till iteration $t-\tau$. Since the average sum of the updates during the last $\tau$ iterations is equal to

and all $\hat{w}_{j}$ look alike in that they mainly represent learned information before the $(t-\tau)$-th iteration, (14) becomes an estimate of the expectation of (14), i.e.,

This looks like GD which in the strong convex case has convergence rate $\leq c^{-t}$ for some constant $c>1$. This already shows that larger $\tau$ could help convergence as well. However, estimate (14) has estimation noise with respect to (15) which explains why in this thought experiment we cannot attain $c^{-t}$ but can only reach a much smaller convergence rate of e.g. $O(1/t)$ as in Theorem 6.

Experiments in Section 5 confirm our analysis.

The higher order terms in the proof in Appendix D.2 show that, as in Theorem 2, the expected convergence rate in Theorem 6 depends on $\|w_{0}-w_{*}\|^{2}$. The proof shows that, for

the higher order term that contains $\|w_{0}-w_{*}\|^{2}$ is at most the leading term. This is comparable to $T$ in Theorem 2 for SGD.

Step size $\eta_{t}=\frac{\alpha_{t}}{\mu(t+E)}$ with $4\leq\alpha_{t}\leq\alpha$ can be chosen to be fixed during periods whose ranges exponentially increase. For $t+E\in[2^{h},2^{h+1})$ we define $\alpha_{t}=\frac{4(t+E)}{2^{h}}$. Notice that $4\leq\alpha_{t}<8$ which satisfies the conditions of Theorem 6 for $\alpha=8$. This means that we can choose

as step size for $t+E\in[2^{h},2^{h+1})$. This choice for $\eta_{t}$ allows changes in $\eta_{t}$ to be easily synchronized between cores since these changes only happen when $t+E=2^{h}$ for some integer $h$. That is, if each core is processing iterations at the same speed, then each core on its own may reliably assume that after having processed $(2^{h}-E)/P$ iterations the aggregate of all $P$ cores has approximately processed $2^{h}-E$ iterations. So, after $(2^{h}-E)/P$ iterations a core will increment its version of $h$ to $h+1$. This will introduce some noise as the different cores will not increment their $h$ versions at exactly the same time, but this only happens during a small interval around every $t+E=2^{h}$. This will occur rarely for larger $h$.

5 Convergence Analysis without Convexity

In Appendix D.3, we also show that the proof of Theorem 6 can easily be modified such that Theorem 6 with $E\geq\frac{4L\kappa\alpha D}{\mu}$ also holds in the non-convex case of the component functions, i.e., we do not need Assumption 3. Note that this case is not analyzed in Leblond et al. (2018).

Let Assumptions 1 and 2 hold. Then, we can conclude the statement of Theorem 6 with $E\geq\frac{4L\kappa\alpha D}{\mu}$ for $\kappa=\frac{L}{\mu}$.

Let Assumptions 1 and 2 hold. Then, we can conclude the statement of Theorem 5 with the definition of the step size replaced by $0<\eta_{t}=\frac{1}{LD\kappa(2+\beta)(k+t)}$ with $\kappa=\frac{L}{\mu}$.

Convergence of Large Stepsizes

In Robbins and Monro (1951), the authors proved the convergence of SGD for step size sequences $\{\eta_{t}\}$ satisfying conditions

In Moulines and Bach (2011), the authors studied the expected convergence rates for another class of step sizes of $\mathcal{O}(1/t^{p})$ where $0<p\leq 1$. This class has many large step sizes in comparison with Robbins and Monro (1951). For example $\eta_{t}=\mathcal{O}(1/t^{p})$ does not satisfy the second condition (i.e., $\sum_{t=0}^{\infty}\eta^{2}_{t}\rightarrow\infty$) where $0<p<1/2$. In this section, we prove that SGD will converge without using bounded gradient assumption if $\{\eta_{t}\}$ is a diminishing sequence and $\sum_{t=0}^{\infty}\eta_{t}\rightarrow\infty$. Compared to Moulines and Bach (2011), we prove the convergence of SGD for step sizes $\eta_{t}=\operatorname{\mathcal{O}}(1/t^{q})$ which is $1/\mu$ times larger. Our proposed class is much larger than the classes in Robbins and Monro (1951) and Moulines and Bach (2011).

The proofs of all theorems and lemmas in this subsection are provided in Appendix D.6.

Let Assumptions 1, 2, and 3 hold. Consider Algorithm 1 with a step size sequence such that: $\eta_{t}\leq\frac{1}{2L}$, $\eta_{t}\rightarrow 0$, $\frac{d}{dt}\eta_{t}\leq 0$ and $\sum_{t=0}^{\infty}\eta_{t}\rightarrow\infty$. Then,

Theorem 9 only discusses about the convergence of SGD for the given step size sequence $\{\eta_{t}\}$ above. The expected convergence rate of SGD with the setup in Theorem 9 is analysed in Theorem 10.

Let Assumptions 1, 2, and 3 hold. Consider Algorithm 1 with a step size sequence such that $\eta_{t}\leq\frac{1}{2L}$, $\eta_{t}\rightarrow 0$, $\frac{d}{dt}\eta_{t}\leq 0$, and $\sum_{t=0}^{\infty}\eta_{t}\rightarrow\infty$. Then,

where $n(t)=\mu\eta_{t}$ and $M(t)=\int_{x=0}^{t}n(x)dx$.

As shown in (53) (see also Appendix D.6), we have

where $A$ and $B$ are constants and $C(t)$ is defined in (16) below. We show that an alternative proof for the convergence of SGD with the setup above based on the study of $C(t)$ can be developed.

where $\frac{d}{dx}M(x)=n(x)$ with function $n(x)$ satisfying the following conditions:

Then, there is a moment $T$ such that for all $t>T$, $C(t)>n(t)$.

Proof We take the derivative of $C(t)$, i.e.,

Initially $C(0)=0$ and $n(0)>0$, hence, $C(t)$ starts increasing from $t\geq 0$. Since $n(t)$ decreases for all $t\geq 0$, we know that there must exist a first cross over point $x$:

There exists a value $x$ such that $C(t)$ increases for $0\leq t<x$, and

$C(x)=n(x)$ with derivative $dC(t)/dt|_{t=x}=0$.

Since $n(x)$ has a derivative $<0$, we know that $C(t)>n(t)$ immediately after $x$. Suppose that $C(y)=n(y)$ for some $y>x$ with $C(t)>n(t)$ for $x<t<y$. This implies that $dC(t)/dt|_{t=y}=0$ and since $dC(t)/dt$ is continuous

Since $dn(t)/dt|_{t=y}<0$, we know that there exists an $\epsilon$ small enough (close to 0) such that

This contradicts $C(t)>n(t)$ for $x<t<y$. We conclude that there does not exist a $y>x$ such that $C(y)=n(y)$:

For $t>x$, $C(t)>n(t)$ and $C(t)$ is strictly decreasing.

We conclude that for any given $n(t)$, there exists a time $T$ such that $C(t)<n(t)$ for all $t\in[0,T)$, $C(T)=n(T)$ after which $C(t)>n(t)$ when $t\in(T,\infty]$. Note that $C(t)$ is always bigger then zero.

Among all stepsizes $\eta_{q,t}=1/(K+t)^{q}$ where $q>0$, $K$ is a constant such that $\eta_{q,t}\leq\frac{1}{2L}$, SGD algorithm enjoys the fastest convergence with stepsize $\eta_{1,t}=1/(2L+t)$.

2 Convergence of Large Stepsizes in Batch Mode

We consider the following general algorithm with the following gradient updating rule:

where $f(w_{t};\xi^{\prime}_{t})=\frac{1}{k_{t}}\sum_{i=1}^{k_{t}}f(w_{t};\xi_{t,i})$.

Let Assumptions 1, 2 and 3 hold, $\{\eta_{t}\}$ is a diminishing sequence with conditions $\sum_{t=0}^{\infty}\eta_{t}\rightarrow\infty$ and $0<\eta_{t}\leq\frac{1}{2LD}$ for all $t\geq 0$. Then, the sequence $\{w_{t}\}$ converges to $w_{*}$ where

The proof of Theorem 12 is provided in Appendix D.7.

Numerical Experiments

where the penalty parameter $\lambda$ is set to $1/n$, a widely-used value in literature Le Roux et al. (2012).

We conducted experiments on a single core for Algorithm 2 on two popular datasets ijcnn1 ($n=91,701$ training data) and covtype ($n=406,709$ training data) from the LIBSVMhttp://www.csie.ntu.edu.tw/$\sim$cjlin/libsvmtools/datasets/ website. Since we are interested in the expected convergence rate with respect to the number of iterations, respectively number of single position vector updates, we do not need a parallelized multi-core simulation to confirm our analysis. The impact of efficient resource scheduling over multiple cores leads to a performance improvement complementary to our analysis of (10) (which, as discussed, lends itself for an efficient parallelized implementation). We experimented with 10 runs and reported the average results. We choose the step size based on Theorem 6, i.e, $\eta_{t}=\frac{4}{\mu(t+E)}$ and $E=\max\{2\tau,\frac{16LD}{\mu}\}$. For each fraction $v\in\{1,3/4,2/3,1/2,1/3,1/4\}$ we performed the following experiment: In Algorithm 2 we choose each “filter” matrix $S^{\xi_{t}}_{u_{t}}$ to correspond with a random subset of size $v|D_{\xi_{t}}|$ of the non-zero positions of $D_{\xi_{t}}$ (i.e., the support of the gradient corresponding to $\xi_{t}$). In addition we use $\tau=10$. For the two datasets,

Figures 1 and 3 plot the training loss for each fraction with $\tau=10$. The top plots have $t^{\prime}$, the number of coordinate updates, for the horizontal axis. The bottom plots have the number of epochs, each epoch counting $n$ iterations, for the horizontal axis. The results show that each fraction shows a sublinear expected convergence rate of $O(1/t^{\prime})$; the smaller fractions exhibit larger deviations but do seem to converge faster to the minimum solution.

In Figures 2 and 4, we show experiments with different values of $\tau\in\{1,10,100\}$ where we use the whole non-zero set of gradient positions (i.e., $v=1$) for the update. Our analysis states that, for $t=50$ epochs times $n$ iterations per epoch, $\tau$ can be as large as $\sqrt{t\cdot L(t)}=524$ for ijcnn1 and $1058$ for covtype. The experiments indeed show that $\tau\leq 100$ has little effect on the expected convergence rate.

Conclusion

We have provided the analysis of stochastic gradient algorithms with diminishing step size in the strongly convex case under the condition of Lipschitz continuity of the individual function realizations, but without requiring any bounds on the stochastic gradients. We showed almost sure convergence of SGD and provided sublinear upper bounds for the expected convergence rate of a general recursion which includes Hogwild! for inconsistent reads and writes as a special case. We also provided new intuition which will help understanding convergence as observed in practice.

Acknowledgement

Phuong Ha Nguyen and Marten van Dijk were supported in part by AFOSR MURI under award number FA9550-14-1-0351. Katya Scheinberg was partially supported by NSF Grants CCF 16-18717 and CCF 17-40796. Martin Takáč was partially supported by the NSF Grant CCF-1618717, CMMI-1663256 and CCF-1740796.

References

A Review of Useful Theorems

where $\xi$ is a random variable, and $w_{*}=\arg\min_{w}F(w)$.

Let $Y_{k}$, $Z_{k}$, and $W_{k}$, $k=0,1,\dots$, be three sequences of random variables and let $\{\mathcal{F}_{k}\}_{k\geq 0}$ be a filtration, that is, $\sigma$-algebras such that $\mathcal{F}_{k}\subset\mathcal{F}_{k+1}$ for all $k$. Suppose that:

The random variables $Y_{k}$, $Z_{k}$, and $W_{k}$ are nonnegative, and $\mathcal{F}_{k}$-measurable.

B Proofs of Lemmas 1 and 2

B.2 Proof of Lemma 2

Proof Analogous to the proof of Lemma 1, we have

C Analysis for Algorithm 1

In this Section, we provide the analysis of Algorithm 1 under Assumptions 1, 2, and 3.

Theorem 1 (Sufficient condition for almost sure convergence). Let Assumptions 1, 2 and 3 hold. Consider Algorithm 1 with a stepsize sequence such that

Then, the following holds w.p.1 (almost surely)

The last inequality follows since $0<\eta_{t}\leq\frac{1}{2L}$. Therefore,

Since $\sum_{t=0}^{\infty}\eta_{t}^{2}N<\infty$, we could apply Lemma 5. Then, we have w.p.1,

We want to show that $\|w_{t}-w_{*}\|^{2}\to 0$, w.p.1. Proving by contradiction, we assume that there exist $\epsilon>0$ and $t_{0}$, s.t. $\|w_{t}-w_{*}\|^{2}\geq\epsilon$ for $\forall t\geq t_{0}$. Hence,

This is a contradiction. Therefore, $\|w_{t}-w_{*}\|^{2}\to 0$ w.p.1.

Theorem 2. Let Assumptions 1, 2 and 3 hold. Let $E=\frac{2\alpha L}{\mu}$ with $\alpha=2$. Consider Algorithm 1 with a stepsize sequence such that $\eta_{t}=\frac{\alpha}{\mu(t+E)}\leq\eta_{0}=\frac{1}{2L}$. Then,

Proof Using the beginning of the proof of Theorem 1, taking the expectation to (24), with $0<\eta_{t}\leq\frac{1}{2L}$, we have

We use mathematical induction to prove (25) (this trick is based on the idea from Bottou et al. (2018)). Let $t=0$, we have

which is obviously true since $G\geq\frac{E\mu^{2}}{N}\|w_{0}-w_{*}\|^{2}.$

Suppose it is true for $t$, we need to show that it is also true for $t+1$. We have

Since $G\geq\frac{\alpha^{2}}{\alpha-1},$

Notice that the induction proof of (25) holds more generally for $E\geq\frac{2\alpha L}{\mu}$ with $\alpha>1$ (this is sufficient for showing $\eta_{t}\leq\frac{1}{2L}$. In this more general interpretation we can see that the convergence rate is minimized for $I$ minimal, i.e., $E=\frac{2\alpha L}{\mu}$ and for this reason we have fixed $E$ as such in the theorem statement.

We choose $\alpha=2$ such that $\eta_{t}$ only depends on known parameters $\mu$ and $L$. For this $\alpha$ we obtain

Applying (25)with $w_{T}$ as starting point rather than $w_{0}$ gives, for $t\geq\max\{T,0\}$,

which equals $4$, see (26). For any given $w_{0}$, we prove the theorem.

D Analysis for Algorithm 2

We introduce the following notation: For each $\xi$, we define $D_{\xi}\subseteq\{1,\ldots,d\}$ as the set of possible non-zero positions in a vector of the form $\nabla f(w;\xi)$ for some $w$. We consider a fixed mapping from $u\in U$ to subsets $S^{\xi}_{u}\subseteq D_{\xi}$ for each possible $\xi$. In our notation we also let $D_{\xi}$ represent the diagonal $d\times d$ matrix with ones exactly at the positions corresponding to $D_{\xi}$ and with zeroes elsewhere. Similarly, $S^{\xi}_{u}$ also denotes a diagonal matrix with ones at the positions corresponding to $D_{\xi}$.

We will use a probability distribution $p_{\xi}(u)$ to indicate how to randomly select a matrix $S^{\xi}_{u}$. We choose the matrices $S^{\xi}_{u}$ and distribution $p_{\xi}(u)$ so that there exist $d_{\xi}$ such that

where the expectation is over $p_{\xi}(u)$.

We will restrict ourselves to choosing non-empty sets $S^{\xi}_{u}$ that partition $D_{\xi}$ in $D$ approximately equally sized sets together with uniform distributions $p_{\xi}(u)$ for some fixed $D$. So, if $D\leq|D_{\xi}|$, then sets have sizes $\lfloor|D_{\xi}|/D\rfloor$ and $\lceil|D_{\xi}|/D\rceil$. For the special case $D>|D_{\xi}|$ we have exactly $|D_{\xi}|$ singleton sets of size $1$ (in our definition we only use non-empty sets).

where the expectation is over $\xi$. We use $\bar{\Delta}_{D}$ in the leading asymptotic term for the convergence rate in our main theorem. We observe that

and $\bar{\Delta}_{D}\leq\bar{\Delta}$ with equality for $D=\bar{\Delta}$.

Let us remark, that $\Delta\in(0,1]$ measures the probability of collision. Small $\Delta$ means that there is a small chance that the support of two random realizations of $\nabla f(w;\xi)$ will have an intersection. On the other hand, $\Delta=1$ means that almost surely, the support of two stochastic gradients will have non-empty intersection.

With this definition of $\Delta$ it is an easy exercise to show that for iid $\xi_{1}$ and $\xi_{2}$ in a finite-sum setting (i.e., $\xi_{i}$ and $\xi_{2}$ can only take on a finite set of possible values) we have

(see Proposition 10 in Leblond et al. (2018)). We notice that in the non-finite sum setting we can use the property that for any two vectors $a$ and $b$, $\langle a,b\rangle\leq(\|a\|^{2}+\|b\|^{2})/2$ and this proves (28) with $\Delta$ set to $\Delta=1$. In our asymptotic analysis of the convergence rate, we will show how $\Delta$ plays a role in non-leading terms – this, with respect to the leading term, it will not matter whether we use $\Delta=1$ or $\Delta$ equal the probability of collision (in the finite sum case).

where $\hat{w}_{t}$ represents the vector used in computing the gradient $\nabla f(\hat{w}_{t};\xi_{t})$ and whose entries have been read (one by one) from an aggregate of a mix of previous updates that led to $w_{j}$, $j\leq t$. Here, we assume that

updating/writing to vector positions is atomic, reading vector positions is atomic, and

there exists a “delay” $\tau$ such that, for all $t$, vector $\hat{w}_{t}$ includes all the updates up to and including those made during the $(t-\tau)$-th iteration (where (29) defines the $(t+1)$-st iteration).

Notice that we do not assume consistent reads and writes of vector positions. We only assume that up to a “delay” $\tau$ all writes/updates are included in the values of positions that are being read.

According to our definition of $\tau$, in (29) vector $\hat{w}_{t}$ represents an inconsistent read with entries that contain all of the updates made during the $1$st to $(t-\tau)$-th iteration. Furthermore each entry in $\hat{w}_{t}$ includes some of the updates made during the $(t-\tau+1)$-th iteration up to $t$-th iteration. Each entry includes its own subset of updates because writes are inconsistent. We model this by “masks” $\Sigma_{t,j}$ for $t-\tau\leq j\leq t-1$. A mask $\Sigma_{t,j}$ is a diagonal 0/1-matrix with the 1s expressing which of the entry updates made in the $(j+1)$-th iteration are included in $\hat{w}_{t}$. That is,

where $I$ represents the identity matrix.

D.2 Main Analysis

We first derive a couple lemmas which will help us deriving our main bounds. In what follows let Assumptions 1, 2, 3 and 4 hold for all lemmas. We define

When we subtract $\tau$ from, for example, $t$ and write $t-\tau$, we will actually mean $\max\{t-\tau,0\}$.

Proof For the first bound, if we take the expectation of $\|d_{\xi_{t}}S^{\xi_{t}}_{u_{t}}\nabla f(\hat{w}_{t};\xi_{t})\|^{2}$ with respect to $u_{t}$, then we have (for vectors $x$ we denote the value if its $i$-th position by $[x]_{i}$)

where the transition to the second line follows from (27).

For the second bound, if we take the expectation of $d_{\xi_{t}}S^{\xi_{t}}_{u_{t}}\nabla f(\hat{w}_{t};\xi_{t})$ wrt $u_{t}$, then we have:

As a consequence of this lemma we derive a bound on the expectation of $\|w_{t}-\hat{w}_{t}\|^{2}$.

The expectation of $\|w_{t}-\hat{w}_{t}\|^{2}$ is at most

This can be used to derive an expression for the square of its norm: $\|w_{t}-\hat{w}_{t}\|^{2}$

Applying (28) to the inner products implies

Now, we can apply Lemma 15: We first take the expectation over $u_{j}$ and this shows

and by $L$-smoothness, see Equation 7 with $\nabla F(w_{*})=0$,

Combining the above inequalities proves the lemma.

Together with the next lemma we will be able to start deriving a recursive inequality from which we will be able to derive a bound on the convergence rate.

Let $0<\eta_{t}\leq\frac{1}{4LD}$ for all $t\geq 0$. Then,

Proof Since $w_{t+1}=w_{t}-\eta_{t}d_{\xi_{t}}S^{\xi_{t}}_{u_{t}}\nabla f(\hat{w}_{t};\xi_{t})$, we have

We now take expectations over $u_{t}$ and $\xi_{t}$ and use Lemma 15:

and together with (36) and (37) we obtain

Plugging this into the previous derivation yields

Since $\eta_{t}\leq\frac{1}{4LD}$, $-2\eta_{t}(1-4L\eta_{t}D)[F(w_{t})-F(w_{*})]\leq 0$ (we can get a negative upper bound by applying strong convexity but this will not improve the asymptotic behavior of the convergence rate in our main result although it would improve the constant of the leading term making the final bound applied to SGD closer to the bound of Theorem 2 for SGD),

Assume $0<\eta_{t}\leq\frac{1}{4LD}$ for all $t\geq 0$. Then, after taking the full expectation of the inequality in Lemma 8, we can plug Lemma 7 into it which yields the recurrence

This can be solved by using the next lemma. For completeness, we follow the convention that an empty product is equal to 1 and an empty sum is equal to 0, i.e.,

Let $Y_{t},\beta_{t}$ and $\gamma_{t}$ be sequences such that $Y_{t+1}\leq\beta_{t}Y_{t}+\gamma_{t}$, for all $t\geq 0$. Then,

Proof We prove the lemma by using induction. It is obvious that (40) is true for $t=0$ because $Y_{1}\leq\beta_{1}Y_{0}+\gamma_{1}$. Assume as induction hypothesis that (40) is true for $t-1$. Since $Y_{t+1}\leq\beta_{t}Y_{t}+\gamma_{t}$,

Applying the above lemma to (38) will yield the following bound.

Let $\eta_{t}=\frac{\alpha_{t}}{\mu(t+E)}$ with $4\leq\alpha_{t}\leq\alpha$ and $E=\max\{2\tau,\frac{4L\alpha D}{\mu}\}$. Then,

where $a_{i}=(L+\mu)\eta_{i}+2L^{2}\eta_{i}^{2}D$.

Since $E\geq 2\tau$, $\frac{1}{t-\tau+E}\leq\frac{2}{t+E}$. Hence, together with $\eta_{t-\tau}=\frac{\alpha_{t-\tau}}{\mu(t-\tau+E)}\leq\frac{\alpha}{\mu(t-\tau+E)}$ we have

In order to analyze this formula, since $\eta_{j}=\frac{\alpha_{j}}{\mu(j+E)}$ with $\alpha_{j}\geq 4$, we have

Hence (we can also use $1-x\leq e^{-x}$ which leads to similar results and can be used to show that our choice for $\eta_{t}$ leads to the tightest convergence rates in our framework),

Now, we substitute $\eta_{i}\leq\frac{\alpha}{\mu(i+E)}$ in $\gamma_{i}$ and compute

Substituting this in (42) proves the lemma.

where the last inequality follows from (41), and

Even if we assume a constant $Z\geq Z_{0}\geq Z_{1}\geq Z_{2}\geq\ldots$, we can get a first bound on the convergence rate of vectors $\hat{w}^{t}$: Substituting $Z$ gives

Since $a_{i}=(L+\mu)\eta_{i}+2L^{2}\eta_{i}^{2}D$ and $\eta_{i}\leq\frac{\alpha}{\mu(i+E)}$, we have

where the last inequality is a property of the harmonic sequence $\sum_{i=1}^{t}\frac{1}{i}\leq 1+\ln t$ and $\sum_{i=1}^{t}\frac{1}{i^{2}}\leq\sum_{i=1}^{\infty}\frac{1}{i^{2}}=\frac{\pi^{2}}{6}$.

Substituting (46) in (45) and collecting terms yields

Notice that the asymptotic behavior in $t$ is dominated by the term

If we define $Z_{t+1}$ to be the right hand side of (47) and observe that this $Z_{t+1}$ is decreasing and a constant $Z$ exists (since the terms with $Z$ decrease much faster in $t$ compared to the dominating term), then this $Z_{t+1}$ satisfies the derivations done above and a proof by induction can be completed.

Our derivations prove our main result: The expected convergence rate of read vectors is

We remind the reader, that in the $(t+1)$-th iteration at most $\leq\lceil|D_{\xi_{t}}|/D\rceil$ vector positions are updated. Therefore the expected number of single vector entry updates is at most $\bar{\Delta}_{D}/D$.

Theorem 6. Suppose Assumptions 1, 2, 3 and 4 and consider Algorithm 2. Let $\eta_{t}=\frac{\alpha_{t}}{\mu(t+E)}$ with $4\leq\alpha_{t}\leq\alpha$ and $E=\max\{2\tau,\frac{4L\alpha D}{\mu}\}$. Then, $t^{\prime}=t\bar{\Delta}_{D}/D$ is the expected number of single vector entry updates after $t$ iterations and

D.3 Convergence without Convexity of Component Functions

For the non-convex case of the component functions, $L$ in (33) must be replaced by $L\kappa$ and as a result $L^{2}$ in Lemma 7 must be replaced by $L^{2}\kappa$. Also $L$ in (37) must be replaced by $L\kappa$. We now require that $\eta_{t}\leq\frac{1}{4L\kappa D}$ so that $-2\eta_{t}(1-4L\kappa\eta_{t}D)[F(w_{t})-F(w_{*})]\leq 0$. This leads to Lemma 8 where no changes are needed except requiring $\eta_{t}\leq\frac{1}{4L\kappa D}$. The changes in Lemmas 7 and 8 lead to a Lemma 10 where we require $E\geq\frac{4L\kappa\alpha D}{\mu}$ and where in the bound of the expectation $L^{2}$ must be replaced by $L^{2}\kappa$. This perculates through to inequality (47) with a similar change finally leading to Theorem 7, i.e., Theorem 6 where we only need to strengthen the condition on $E$ to $E\geq\frac{4L\kappa\alpha D}{\mu}$ in order to remove Assumption 3.

D.4 Sensitivity to τ𝜏\tau

What about the upper bound’s sensitivity with respect to $\tau$? Suppose $\tau$ is not a constant but an increasing function of $t$, which also makes $E$ a function of $t$:

In order to obtain a similar theorem we increase the lower bound on $\alpha_{t}$ to

This allows us to modify the proof of Lemma 10 where we analyse the product

Since $\alpha_{j}\geq 12$ and $E(j)=2\tau(j)\leq 2j$,

The remaining part of the proof of Lemma 10 continues as before where constant $E$ in the proof is replaced by $1$. This yields instead of (42)

We again substitute $\eta_{i}\leq\frac{\alpha}{\mu(i+E(i))}$ in $\gamma_{i}$, realize that $\frac{(i+1)}{(i+E(i))}\leq 1$, and compute

Assume $\frac{2L\alpha D}{\mu}\leq\tau(t)\leq t$ with $\tau(t)$ monotonic increasing. Let $\eta_{t}=\frac{\alpha_{t}}{\mu(t+E(t))}$ with $12\leq\alpha_{t}\leq\alpha$ and $E(t)=2\tau(t)$. Then,

where $a_{i}=(L+\mu)\eta_{i}+2L^{2}\eta_{i}^{2}D$.

Now we can continue the same analysis that led to Theorem 6 and conclude that there exists a constant $Z$ such that, see (45),

which has the property that the derivative of $t/(\ln t)$ is equal to $L(t)$. Now we observe

Again we define $Z_{t+1}$ as the right hand side of this inequality. Notice that $Z_{t}=O(1/t)$, since the above derivation proves

Summarizing we have the following main lemma:

Let Assumptions 1, 2, 3 and 4 hold and consider Algorithm 2. Assume $\frac{2L\alpha D}{\mu}\leq\tau(t)\leq\sqrt{t\cdot L(t)}$ with $\tau(t)$ monotonic increasing. Let $\eta_{t}=\frac{\alpha_{t}}{\mu(t+2\tau(t))}$ with $12\leq\alpha_{t}\leq\alpha$. Then, the expected convergence rate of read vectors is

Notice that we can plug $Z_{t}=O(1/t)$ back into an equivalent of (44) where we may bound $Z_{i-\tau(i)}=O(1/(i-\tau(i))$ which replaces $Z$ in the second line of (45). On careful examination this leads to a new upper bound (50) where the $2L^{2}Z$ terms gets absorped in a higher order term. This can be used to show that, for

the higher order terms that contain $\tau(t)$ (as defined above) are at most the leading term as given in Lemma 12.

the higher order term that contains $\|w_{0}-w_{*}\|^{2}$ is at most the leading term.

D.5 Convergence of Hogwild! with probability 1

Let us consider the sequence $w_{0},w_{1},w_{2},\dotsc,w_{t},\dotsc,w_{n}$ generated by (29):

where $d_{\xi_{t}}\leq D$ for all $\xi_{t}$.

for any $i\in[n]$ and $t$. Using the triangular inequality, we obtain

Moreover, the result above implies $m_{t+1}\leq(1+LD\eta_{t})m_{t}$ and unrolling $m_{t}$ yields

For all $x\geq 0$, it is always true that $1+x\leq\exp(x)$. Hence, we have

Theorem 5 (Sufficient conditions for almost sure convergence for Hogwild!) Let Assumptions 1, 2, 3 and 4 hold. Consider Hogwild! method described in Algorithm 2 with a stepsize sequence such that

Then, the following holds w.p.1 (almost surely)

Proof As shown in Lemma 8, for $0<\eta_{t}\leq\frac{1}{4LD}$, we have

If we can show that $\sum_{t=0}^{\infty}[(L+\mu)\eta_{t}+2L^{2}\eta_{t}^{2}D]\|\hat{w}_{t}-w_{t}\|^{2}$ is finite, then it is straight forward to apply the proof technique from Theorem 1 to show that $\|w_{t}-w_{*}\|^{2}\rightarrow 0$ w.p.1. From the proof of Lemma 7, we know $\|w_{t}-\hat{w}_{t}\|^{2}$ is at most

Since $\eta_{t-\tau}=(1-\frac{\tau}{k+t-\tau})\eta_{t}<\frac{1}{2}\eta_{t}$ when $k\geq 3\tau$ for all $t\geq 0$, it yields $\|w_{t}-\hat{w}_{t}\|^{2}<(1+\sqrt{\Delta}\tau)D^{2}\tau\frac{1}{4}\eta^{2}_{t}m^{2}_{t}$. Hence $\sum_{t=0}^{\infty}[(L+\mu)\eta_{t}+2L^{2}\eta_{t}^{2}D]\|\hat{w}_{t}-w_{t}\|^{2}$ is at most

Combining $m_{t}\leq m_{0}\exp(LD\sum_{i=0}^{t}\eta_{i})$ (see (51)) and $\eta_{i}=\frac{1}{LD(2+\beta)(k+i)}$ yields

The second inequality is a property of harmonic number $H_{t}=\sum_{i=1}^{t}\frac{1}{i}\leq 1+\ln t$. Hence,

where $\rho=\frac{\beta}{2+\beta}$. Due to the property of over-harmonic series, $\sum_{t=1}^{\infty}\frac{1}{t^{1+\rho}}$ converges for any $\rho>0$. In other words, $\sum_{t=0}^{\infty}(\eta_{t}m_{t})^{2}$ is finite or $\sum_{t=0}^{\infty}[(L+\mu)\eta_{t}+2L^{2}\eta_{t}^{2}D]\|\hat{w}_{t}-w_{t}\|^{2}$ is finite.

D.6 Convergence of Large Stepsizes

Theorem 9 Let Assumptions 1, 2, and 3 hold. Consider Algorithm 1 with a stepsize sequence such that $\eta_{t}\leq\frac{1}{2L}$, $\eta_{t}\rightarrow 0$, $\frac{d}{dt}\eta_{t}\leq 0$ and $\sum_{t=0}^{\infty}\eta_{t}\rightarrow\infty$. Then,

Since $1-x\leq\exp(-x)$ for all $x\geq 0$,

Furthermore, since $n(j)$ is decreasing in $j$, we have

These two inequalities can be used to derive

We know that $\exp(M(x+1))$ increases and $n(x)^{2}$ decreases, hence, in the most general case either their product first decreases and then starts to increase or their product keeps on increasing. We first discuss the decreasing and increasing case. Let $a(x)=\exp(M(x+1))n(x)^{2}$ denote this product and let integer $j\geq 0$ be such that $a(0)\geq a(1)\geq\ldots\geq a(j)$ and $a(j)\leq a(j+1)\leq a(j+2)\leq\ldots$ (notice that $j=0$ expresses the situation where $a(i)$ only increases). Function $a(x)$ for $x\geq 0$ is minimized for some value $h$ in $[j,j+1)$. For $1\leq i\leq j$, $a(i)\leq\int_{x=i-1}^{i}a(x)dx$, and for $j+1\leq i$, $a(i)\leq\int_{x=i}^{i+1}a(x)dx$. This yields the upper bound