Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent

Introduction

For prediction problems, we want to find a function $f_{\theta}(x)$ with parameter $\theta$ to predict the value of the outcome variable $y$ given an observed vector $x$. Typically, the problem is formulated as an optimization problem:

where $t$ is the number of data points, $\theta_{t}^{*}$ is the parameter that minimize the empirical cost, $(x_{i},y_{i})$ are the $i^{th}$ training example, $L(s,y)$ is a loss function which gives small value if $s$ is a good prediction for $y$, and $R(\theta)$ is a regularization function for $\theta$ which typically gives small value for small $\theta$. Some commonly used $L$ are: $\max(0,1-ys)$ for support vector machine (SVM), $\frac{1}{2}(\max(0,1-ys))^{2}$ for L2 SVM, and $\frac{1}{2}(y-s)^{2}$ for linear regression. Some commonly used regularization functions are: L2 regularization $\frac{\lambda}{2}\|\theta\|^{2}$, and L1 regularization $\lambda\|\theta\|_{1}$.

For large scale machine learning problems, we need to deal with optimization problems with millions or even billions of training samples. The classical optimization techniques such as interior point methods or conjugate gradient descent have to go through all data points to just evaluate the objective once. Not to say that they need to go through the whole data set many times in order to find the best $\theta$.

On the other hand, stochastic gradient descent (SGD) has been shown to have great promise for large scale learning (Zhang, 2004; Hazan et al., 2006; Shalev-Shwartz et al., 2007; Bottou and Bousquet, 2008; Shalev-Shwartz and Tewari, 2009; Langford et al., 2009). Let $d=(x,y)$ be one data sample, $l(\theta,d)=L(f_{\theta}(x),y)+R(\theta)$ be the cost of $\theta$ for $d$, $g(\theta,\xi)=\frac{\partial l(\theta,d)}{\partial\theta}$ be the gradient function, and $D_{t}=(d_{1},\cdots,d_{t})$ be all the training samples at $t^{th}$ step. The SGD method updates $\theta$ according to its stochastic gradient:

where $\gamma_{t}$ is learning rate at the $t^{th}$ step. $\gamma_{t}$ can be either a scalar or a matrix. Let the expected loss of $\theta$ over test data be $\mathcal{E}(\theta)=E_{d}(l(\theta,d))$, the optimal parameter be $\theta^{*}=\arg\min_{\theta}\mathcal{E}(\theta)$, and the Hessian be $H=\left.\frac{\partial^{2}\mathcal{E}(\theta)}{\partial\theta\partial\theta^{T}}\right|_{\theta=\theta^{*}}$. Note that $\theta_{t}$ and $\theta_{t}^{*}$ are random variables depending on $D_{t}$. Hence both $\mathcal{E}(\theta_{t})$ and $\mathcal{E}(\theta_{t}^{*})$ are random variables depending on $D_{t}$. If $\gamma_{t}$ is a scalar, the best asymptotic convergence for the expected excess loss $E_{D_{t}}(\mathcal{E}(\theta_{t}))-\mathcal{E}(\theta^{*})$ is $O(t^{-1})$, which is obtained by using $\gamma_{t}=\gamma_{0}(1+\gamma_{0}\lambda_{0}t)^{-1}$, where $\lambda_{0}$ is the smallest eigenvalue of $H$ and $\gamma_{0}$ is some constant. The asymptotic convergence rate of SGD can be potentially benefit from using second order information (Bottou and Bousquet, 2008; Schraudolph et al., 2007; Amari et al., 2000). The optimal asymptotic convergence rate is achieved by using matrix valued learning rate $\gamma_{t}=\frac{1}{t}H^{-1}$. If this optimal matrix step size is used, then asymptotically second order SGD is as good as explicitly optimizing the empirical loss. More precisely, this means that both $tE_{D_{t}}(\mathcal{E}(\theta_{t})-\mathcal{E}(\theta^{*}))$ and $tE_{D_{t}}(\mathcal{E}(\theta_{t}^{*})-\mathcal{E}(\theta^{*}))$ converge to a same positive constant.

Since $H$ is unknown in advance, methods for adaptively estimating $H$ is proposed (Bottou and LeCun, 2005; Amari et al., 2000). However, for high dimensional data sets, maintaining a full matrix $H$ is too computationally expensive. Hence various methods for approximating $H$ have been proposed (LeCun et al., 1998; Schraudolph et al., 2007; Roux et al., 2008; Bordes et al., 2009). However, with the approximated $H$, the optimal convergence cannot be guaranteed. It is worth to point out that most of the existing analysis for second order SGD is asymptotic, namely, that they do not tell how much data is needed for the algorithm to reach their asymptotic region.

In order to accelerate the convergence speed of SGD, averaged stochastic gradient (ASGD) was proposed in Polyak and Juditsky (1992). For ASGD, the running average $\bar{\theta}_{t}=\frac{1}{t}\sum_{j=1}^{t}\theta_{j}$ of the parameters obtained by SGD is used as the estimator for $\theta^{*}$. Polyak and Juditsky (1992) showed a very nice result that $\bar{\theta}_{t}$ converges to $\theta^{*}$ as good as full second order SGD, which means that if there are enough training samples, ASGD can obtain the parameter as good as the empirical optimal parameter $\theta_{t}^{*}$ in just one pass of data. And another advantage of ASGD is that, unlike second order SGD, ASGD is extremely easy to implement. Zhang (2004); Nemirovski et al. (2009) gave some nice non-asymptotic analysis for ASGD with a fixed learning rate. However, the convergence bounds obtained by Zhang (2004); Nemirovski et al. (2009) are far less appealing than that of Polyak and Juditsky (1992).

Despite its nice properties, ASGD receives little attention in recent research for online large scale learning. The reason for the lack of interest in ASGD might be that its potential good convergence has not been realized by researchers in real applications. Our analysis shows the cause of this may due to the fact the ASGD needs a prohibitively large amount of data to reach asymptotics if learning rate is chosen arbitrarily.

A typical choice for the learning rate $\gamma_{t}$ is to make it decease as fast as $\Theta(t^{-c})$ for some constant $c$. In this paper, we assume a particular form of learning rate schedule which satisfies this condition,

where $\gamma_{0}$, $a$ and $c$ are some constants. Based on this form of learning rate schedule, we provide non-asymptotic analysis of ASGD. Our analysis shows that $\gamma_{0}$ and $a$ should to be properly set according to the curvature of the expected cost function. $c$ should be a problem independent constant. With our recipe for setting the learning rate, we show that ASGD outperforms SGD if the data size is large enough for SGD to reach its asymptotic region.

To demonstrate the effectiveness of ASGD with the proposed learning rate schedule, we apply ASGD for training linear classification and regression models. We compare ASGD with other prominent large scale SVM solvers on several benchmark tasks. Our experimental results show the clear advantage of ASGD.

In the rest of the paper, for matrices $X$ and $Y$, $X\leq Y$ means $Y-X$ is positive semi-definite, $\|x\|_{A}$ is defined as $\sqrt{x^{T}Ax}$. We will assume $\gamma_{t}=\gamma_{0}(1+a\gamma_{0}t)^{-c}$ for some constant $\gamma_{0}>0$, $a>0$ and $0\leq c\leq 1$ in all the theorems and lemmas. Through out this paper we denote $\Delta_{t}=\theta_{t}-\theta^{*}$ and $\bar{\Delta}_{t}=\bar{\theta}_{t}-\theta^{*}$. To help the reader focus on the main idea, we put most proofs to the Appendix.

The paper is organized as follows: Section 2 establish some results on stochastic linear equation; Section 3 extends the result to ASGD for quadratic loss functions; Section 4 works on general non-quadratic loss functions; Section 5 discusses some implementation issues; Section 6 shows experimental results; Section 7 concludes the paper; and Appendix includes all the proofs.

Stochastic Linear Equation

To motivate the problem, we first take a close look at the SGD update (2). Let $\bar{g}(\theta)=E(g(\theta,d))$ and the first order Taylor expansion of $\bar{g}(\theta)$ around $\theta^{*}$ be $A\theta-b$, where $A=\left.\frac{\partial\bar{g}(\theta)}{\partial\theta}\right|_{\theta=\theta^{*}}$ and $b=A\theta^{*}-\bar{g}(\theta^{*})=A\theta^{*}$. Then $g(\theta_{t-1},d)$ can be decomposed as:

where $\xi_{t}^{(1)}=g(\theta^{*},d_{t})$, $\xi_{t}^{(2)}=g(\theta_{t-1},d_{t})-g(\theta^{*},d_{t})-\bar{g}(\theta_{t-1})$ and $\xi_{t}^{(3)}=\bar{g}(\theta_{t-1})-A\theta_{t-1}+b$. So the SGD update (2) can be re-written as

It is easy to see that $\xi_{t}^{(1)}$ is martingale with respect to $d_{t}$, i.e., $E(\xi_{t}^{(1)}|d_{1},\cdots,d_{t-1})=0$, and has identical distribution for different $t$. $\xi_{t}^{(2)}$ is also martingale with respect to $d_{t}$. However, as we will see in later section, its magnitude depends on $\theta_{t-1}-\theta^{*}$. If $g(\theta,d)$ is smooth, we have $\xi_{t}^{(2)}=O(\|\theta_{t-1}-\theta^{*}\|)$. For smooth $\bar{g}(\theta)$, we have $\xi_{t}^{(3)}=o(\|\theta_{t-1}-\theta^{*}\|)$. Both $\xi_{t}^{(2)}$ and $\xi_{t}^{(3)}$ are asymptotically negligible if suitable conditions are met. We also note that $\xi_{t}^{(3)}=0$ for quadratic $l(\theta,\xi)$.

By the above analysis, we first consider the following simple stochastic approximation procedure which ignores $\xi_{t}^{(2)}$ and $\xi_{t}^{(3)}$:

where $A$ is a positive definite matrix with the smallest eigenvalue $\lambda_{0}$ and the largest eigenvalue $\lambda_{1}$, $\xi_{t}$ is martingale difference process, i.e., $E(\xi_{t}|\xi_{1},\cdots,\xi_{t-1})=0$, the variance of $\xi_{t}$ is $E(\xi_{t}\xi_{t}^{T})=S$. We will see that this algorithm can be used to find the root $\theta^{*}$ of equation $A\theta=b$

If $\gamma_{0}\lambda_{1}\leq 1$ and $(2c-1)a<\lambda_{0}$, then the estimator $\bar{\theta}_{t}$ in (6) satisfies:

The immediate conclusion from Theorem 1 is the asymptotic convergence bound of $\bar{\theta}_{t}$.

The above bound is consistent with Theorem 1 in Polyak and Juditsky (1992) and is the best possible asymptotic convergence rate that can be achieved by any algorithms (Fabian, 1973). However, we are more interested in the non-asymptotic behavior of $\bar{\theta}_{t}$.

If we choose $a=\lambda_{0}$, it takes $t=O((\lambda_{0}\gamma_{0})^{-1})$ samples for $\bar{\theta}_{t}$ in (6) to reach the asymptotic region. And at this point, $\bar{\theta}_{t}$ begins to become better than $\theta_{t}$.

Proof Let $t=\frac{K}{\lambda_{0}\gamma_{0}}$, we have

On the other hand, the best possible convergence for $\theta_{t}$ is obtained with $a=\lambda_{0}$ and $c=1$:

It takes $t=\Omega\left(\left(\frac{a}{\lambda_{0}}\right)^{\frac{c}{1-c}}(\lambda_{0}\gamma_{0})^{-1}\right)$ samples for $\bar{\theta}_{t}$ in (6) to reach the asymptotic region.

By Corollary 4, we should limit $a$ in order to have fast convergence. For the linear problem (5), we should always use $a=0$. If we use some arbitrary value such as 1 for $a$, although $\bar{\theta}_{t}$ still has asymptotic optimal convergence according to Polyak and Juditsky (1992), but it needs much more samples to reach the asymptotic region in situations where $\lambda_{0}$ is very small. For the general SGD update (4), we need to trade-off against the convergence of $\xi^{(2)}$ and $\xi^{(3)}$. Hence $a$ should not be 0. In general, $a$ should be a constant factor times of $\lambda_{0}$.

Regression Problem

In this section, we will analyze the convergence for regression problems. As we noted in section 2, the SGD update can be decomposed as (4), where $\xi_{t}^{(3)}=0$ for quadratic loss of linear regression. As in the proof of Theorem 1, $\bar{\Delta}_{t}$ can be written as:

We already have a bound for $\|I^{(0)}\|_{A}$ and $\|I^{(1)}\|_{A}$ in Theorem 1. Now we work on $I^{(2)}$. We will make two assumptions:

(9) is related to the continuity of $g(\theta,d)$ and the distribution of $y$. (10) is related to the convergence of standard SGD. A bound similar to (10) can be found in section 3.1 of Hazan et al. (2006). Using these assumptions, we can bound $E\|I^{(2)}\|_{A}^{2}$:

With the above lemma, we can obtain the following asymptotic convergence result:

For quadratic loss, with assumption (9) (10), $\bar{\theta}_{t}$ satisfies

The corollary follows by applying (16), (17) and Lemma 5. The best convergence rate is obtained when $c=2/3$. Now we take a close look at the constant factor $c_{1}$ in assumption (9) to have a better understanding of the non-asymptotic behavior of $tE\|I^{(2)}\|_{A}^{2}$.

For ridge regression $l(\theta,d)=\frac{1}{2}(\theta^{T}x-y)^{2}$, if $\|x\|\leq M$, then

Assuming $\|x\|=M$, Lemma 12 in the Appendix shows that $\|\Delta_{t}\|^{2}$ will diverge if learning rate is greater than $\frac{2}{M}$. So $\gamma_{0}\leq\frac{2}{M}$ and $c_{1}\leq\frac{M}{\lambda_{0}}$. Plugging these bounds for $c_{1}$ and $\gamma_{0}$ into Lemma 5, we have the following for $t=\frac{K}{\lambda_{0}\gamma_{0}}$,

Note that the best possible SGD error bound is $\frac{\|\Delta_{0}\|_{A}^{2}}{(1+K)^{2}}+\frac{c_{3}\gamma_{0}}{1+K}$ with $a=\lambda_{0}$ and $c=1$. We see that $E\|I^{(2)}\|_{A}^{2}$ is negligible compared to the error of SGD if $t>O((\lambda_{0}\gamma_{0})^{-1})$. Together with the analysis in Section 2, we conclude that ASGD begins to outperform SGD after $t>O((\lambda_{0}\gamma_{0})^{-1})$. The conclusion we draw in this section applies not only to the case of $y$ with constant norm. Similar conclusion can be drawn if $y$ is normally distributed or if each dimension of $y$ is independently distributed, and/or if L2 regularization is used.

Based on above analysis, for linear regression problems, we propose to use the following values for (3) to calculate the learning rate: $\gamma_{0}=1/M$, $a=\lambda_{0}$, $c=2/3$. We will see that in the next section for general non-quadratic loss, optimal $c$ is different since we need to further consider the convergence of $\xi_{t}^{(3)}$.

Non-quadratic loss

For non-quadratic loss, we need to analyze the contribution of $\xi^{(3)}$ to the error. We need the following two additional assumptions:

Similar to (9), (12) is related to the continuity of $g(\theta,d)$ and the distribution of $x$ and $y$. Similar to (10), (13) is related to the convergence of standard SGD. We note that the asymptotic normality of $\theta_{t}$ (Fabian, 1968) suggests that assumption (13) is reasonable.

With Assumption (9) (10) (12) and (13) , we have

where $\gamma_{1}^{t}=\sum_{s=1}^{t}\gamma_{s}$.

For non-quadratic loss, with assumption (9) (10) (12) and (13), if $c>\frac{1}{2}$, then $\bar{\theta}_{t}$ satisfies

The corollary follows by applying (16), (17), Lemma 5 and Lemma 8. The best convergence rate is obtained when $c=3/4$, which is different from that for quadratic loss.

Implementation

In this section, we discuss how we implement ASGD for linear models $f_{\theta}(x)=\theta^{T}x$ with L2 regularization. The running average can be recursively updated by $\bar{\theta}_{t}=(1-\frac{1}{t})\bar{\theta}_{t-1}+\frac{1}{t}\theta_{t}$, which is very easy to implement. However, for sparse data sets, this can be very costly compared to SGD since $\theta_{t}$ is typically a dense vector. Consider the following average procedure:

where $\lambda$ is the L2 regularization coefficient, $g_{t}=\frac{\partial L(\theta_{t-1}^{T}x_{t},y_{t})}{\partial\theta_{t_{1}}}=L_{s}(\theta_{t-1}^{T}x_{t},y_{t})x_{t}$, and $\eta_{t}$ is the rate of averaging. Hence $g_{t}$ is sparse when $x_{t}$ is sparse. We want to take the advantage of the sparsity of $x_{t}$ for updating $\theta_{t}$ and $\bar{\theta}_{t}$. Let

After some manipulation, we get the following:

Now define $\tau_{t}=\sum_{i=1}^{t}\frac{\eta_{i}\beta_{i}}{\alpha_{i}}$ and $\hat{u}_{t}=\hat{u}_{t-1}+\tau_{t-1}\alpha_{t}\gamma_{t}g_{t}$ with $\hat{u}_{0}=\bar{u}_{0}$, we get

Hence we obtain the following efficient algorithm for updating $\bar{\theta}_{t}$:

At any step of the algorithm, $\bar{\theta}_{t}$ can be obtained by $\bar{\theta}_{t}=\frac{\bar{u}_{t}}{\beta_{t}}=\frac{\tau_{t}u_{t}+\hat{u}_{t}}{\beta_{t}}$. Note that in Algorithm 1, none of the operations involves two dense vectors. Thus the number of operations per sample is $O(Z)$, where $Z$ is the number of non-zero elements in $x$.

Experiments

In this section, we provide 3 sets of experiments. The first experiment illustrate the importance of learning rate scheduling for ASGD. The second experiment illustrates the asymptotic optimal convergence of ASGD. In the third set of experiments, we apply ASGD on many public benchmark data sets and compare it with several state of the art algorithms.

Our first experiment is used to show how different learning rate schedule affects the convergence of ASGD using a synthetic problem. The exemplar optimization problem is $\min_{\theta}E_{x}((\theta-x)^{T}A(\theta-x))$, where $A$ is a symmetric 100x100 matrix with eigenvalues $[1,1,1,0.02\cdots 0.02]$ and $x$ follows normal distribution with zero mean and unit covariance. It can be shown that the optimal $\theta$ is $\theta^{*}=0$. Figure 1 shows the excess risk $\mathcal{E}(\theta_{t})-\mathcal{E}(\theta^{*})$ of the solution vs. number of training samples $t$. We note that in this particular example the excess risk is simply $\theta_{t}^{T}A\theta_{t}$. For the good example of ASGD (ASGD in the figure), we use our proposed learning rate schedule $\gamma_{t}=(1+0.02t)^{-2/3}$ according to Section 3. For a bad example of ASGD (ASGD_BAD in the figure), we use $\gamma_{t}=(1+t)^{-1/2}$, which looks simple and also has optimal asymptotic convergence according to Corollary 2. Figure 1 also shows the performance of standard SGD using learning rate schedule $\gamma_{t}=(1+0.02t)^{-1}$ and batch method $\theta_{t}=\frac{1}{t}\sum_{j=1}^{t}x_{t}$. We see that both ASGD and ASGD_BAD eventually outperforms SGD and come close to the batch method. However, it takes only a few thousands example for ASGD to get to the asymptotic region, while it takes hundreds of thousands of examples for ASGD_BAD. This huge difference illustrates the significant role of learning rate scheduling for ASGD.

2 Asymptotic optimal convergence

3 Experiments on benchmark data sets

In the third set of experiments, we compare ASGD with several other algorithms for training large scale linear models: online limited-memory BFGS (oLBFGS) of Schraudolph et al. (2007), stochastic gradient descent (SGD2) of Bottou (2007), dual coordinate descent (LIBLINEAR) of Fan et al. (2008), Pegasos of Shalev-Shwartz et al. (2007) and SGDQN of Bordes et al. (2009). We performed extensive evaluation of ASGD on many data sets. Due to space limit, we only show detailed results on four tasks in this paper. COVTYPE is the detection of class 2 among 7 forest cover types (Blackard et al). All dimensions are normalized between 0 and 1. DELTA is a synthetic data set from the PASCAL Large Scale Challenge (Sonnenburg et al., 2008). We use the default data preprocessing provided by the challenge organizers. RCV1 is the classification of documents belonging to class CCAT in RCV1 text data set (Lewis et al., 2004). We use the same preprocessing as provided in Bottou (2007). MNIST9 is the classification of digit 9 against all other digits in MNIST digit image data set (LeCun et al., 1998). For this task, we generate our own image feature vectors for recognition. The experiments for these four tasks use squared hinge loss $L(s,y)=\frac{1}{2}(\max(0,1-ys))^{2}$ with $L2$ regularization $R(\theta)=\frac{\lambda}{2}\|\theta\|_{2}^{2}$. Since $\lambda_{0}$ is unknown, we use the regularization coefficient $\lambda$ as $\lambda_{0}$, which is a lower bound for true $\lambda_{0}$. Table 1 summarizes the data sets, where $M$ is the $\max\|x\|^{2}$ calculated from 1000 samples, $t_{0}$ is the point where average begins (See Section 5). Figure 3 shows the test error rate (left), elapsed time (middle) and test cost (right) at different points within first two passes of training data.

We also include more experimental results on data sets from Pascal Large Scale Challenge. However, to save space, we only show figures for test error rate. All experiments use the default data preprocessing provided by the challenge organizers. Table 2 summarize the data sets. Figure 4 and Figure 5 shows result for L2 SVM, logistic regression and SVM. LIBLINEAR is not included in the figures for logistic regression because the dual coordinate descent method used by LIBLINEAR cannot solve logistic regression. Although the theory of ASGD only applies to smooth cost functions, we also include the results of SVM to satisfy the possible curiosity of some readers.

As we can see from the figures, ASGD clearly outperforms all other 5 algorithms in terms accuracy in most of the data sets. In fact, for most of the data sets, ASGD reaches good performance with only one pass of data, while many other algorithms still perform poorly at that point. The only exception is the beta data set, where all methods performs equally bad because the two classes in this data set are not linearly separable. Moreover, the performance of the other 5 methods tend to be more volatile, while performance of ASGD is more robust due to average. In terms of time spent on one pass of data, ASGD is similar to the other methods except oLBFGS, which means that ASGD needs less time to reach similar test performance compared to the other methods. Another interesting point is that although the current theory of ASGD is based on the assumption that cost function is smooth, as shown in the figures, ASGD also works pretty well with non-smooth loss such as hinge loss.

Conclusion

ASGD is relatively easy to implement compared to other algorithms. And as demonstrated on both synthetic and real data sets, with our proposed learning rate schedule, ASGD performs better than other more complicated algorithms for large scale learning problems. In this paper, we only apply ASGD to linear models with convex loss, which has unique local optimum. It would be more interesting to see how ASGD can be applied to more complicated models such as conditional random fields (CRF) or models with multiple local optimums such as neural networks.

The author would like to thank Leon Bottou for the insightful discussions, Antoine Bordes for providing source code of SGDQN, SGD2 and oLBFGS, and Yi Zhang for the suggestions to improve the exposition of this paper.

References

A Proofs

Let $\kappa=1-\max(0,2c-1)\frac{a}{\lambda_{0}}$. If $\gamma_{0}\lambda_{1}\leq 1$, then

Proof For $0<c\leq 0.5$, let $f(x)=(x^{c}-(x-1)^{c})x^{c}$, where $x=k+\frac{1}{a\gamma_{0}}$. We only need to show $f^{\prime}(x)\leq 0$

where we used the fact $x^{c}\leq(x-1)^{c}+c(x-1)^{c-1}$ for $0\leq c\leq 1$.

For $c>0.5$, let $f(x)=\log((x^{c}-(x-1)^{c})x^{c})$, where $x=k+\frac{1}{a\gamma_{0}}$. We only need to show

By mean value theorem, there exists some $y:x\leq y\leq x+1$ s.t. $f(x+1)-f(x)=f^{\prime}(y)$. Hence

The following is a key lemma which is used several times in this paper.

If $\gamma_{0}\lambda_{1}\leq 1$ and $(2c-1)a<\lambda_{0}$, then we have the following bound for $\bar{X}_{j}^{t}$.

where $c_{0}$ is the same as in Theorem 1.

Proof It is easy to verify the following relation by induction on $t$,

Now we calculate the difference between $\bar{X}_{j}^{t}$ and $\sum_{i=j}^{t}\gamma_{i}X_{j}^{i-1}$.

It is clear that from the first line of above equation that $\bar{X}_{j}^{t}-\sum_{i=j}^{t}\gamma_{i}X_{j}^{i-1}>0$. Hence we obtain the first inequality of the lemma. We have

Define $Y_{j}^{k}$ as $Y_{j}^{k}=\prod_{i=j}^{k}(I-\kappa\gamma_{i}A)$. Since $0<\kappa\leq 1$, we have $(X_{j}^{k})^{\kappa}\leq Y_{j}^{k}$. Hence

Now plugging (14) into above inequality, we obtain the claim of the lemma. With Lemma 11, we can now prove Theorem 1.

where $\bar{X}_{j}^{t}$ is defined in Lemma 11. Hence

And we have $E((I^{(0)})^{T}AI^{(1)})=0$ since $E(\xi_{j})=0$.

Proof (Lemma 7) Let $\Sigma_{x}=E(xx^{T})$. We have the following:

For linear regression problem $l(\theta,x,y)=\frac{1}{2}(\theta^{T}x-y)^{2}$, assuming all $\|x\|^{2}$ are $M$, then (2) will diverge if learning rate is greater than $\frac{2}{M}$.

Proof Let $X_{i}^{t}$ be defined as in Lemma 11. We obtain the following from (2),

Let $A_{t}=x_{t}x_{t}^{T}$, $b_{t}=x_{t}y_{t}$, $A=E(A_{t})$, $b=E(b_{t})$. Taking expectation with respect to $x_{t},y_{t}$, noticing that $A\theta^{*}=b$, we get

where $S=E((A_{t}\theta^{*}-b_{t})(A_{t}\theta^{*}-b_{t})^{T})$, $u=E(A_{t}A_{t}\theta^{*}-A_{t}b_{t})$. Hence

If $\gamma_{t}>=\frac{2}{M}+\delta>\frac{2}{M}$, then

Noticing that $X_{1}^{t-1}\rightarrow 0$ as $t\rightarrow\infty$, we conclude that $E(\|\Delta_{t}\|^{2})$ is diverging if $\gamma_{t}\geq\frac{2}{M}$.

Proof (Lemma 8) Let $\gamma_{i}^{t}=\sum_{j=i}^{t}\gamma_{j}$,