Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

Introduction

Modern machine learning models are typically trained with iterative stochastic first-order methods . Stochastic gradient descent (SGD) and related methods such as Adagrad or Adam compute the gradient with respect to one or a mini-batch of training examples in each iteration and take a descent step using this gradient. Since these methods use only a small part of the data in each iteration, they are the preferred way for training models on large datasets. However, in order to converge to the solution, these methods require the step-size to decay to zero in terms of the number of iterations. This implies that the gradient descent procedure takes smaller steps as the training progresses. Consequently, these methods result in slow sub-linear rates of convergence. Specifically, if $k$ is the number of iterations, then SGD-like methods achieve a convergence rate of $O(1/k)$ and $O(1/\sqrt{k})$ for strongly-convex and convex functions respectively . In practice, these methods are augmented with some form of momentum or acceleration that results in faster empirical convergence . Recently, there has been some theoretical analysis for the use of such acceleration in the stochastic setting . Other related work includes algorithms specifically designed to achieve an accelerated rate of convergence in the stochastic setting .

Another recent trend in the literature has been to use variance-reduction techniques that exploit the finite-sum structure of the loss function in machine-learning applications. These methods do not require the step-size to decay to zero and are able to achieve the optimal rate of convergence. However, they require additional bookkeeping or need to compute the full gradient periodically , both of which are difficult in the context of training complex models on large datasets.

In this paper, we take further advantage of the optimization properties specific to modern machine learning models. In particular, we make use of the fact that models such as non-parametric regression or over-parameterized deep neural networks are expressive enough to fit or interpolate the training dataset completely . For an SGD-like algorithm, this implies that the gradient with respect to each training example converges to zero at the optimal solution. This property of interpolation is also true for boosting and for simple linear classifiers on separable data. For example, the perceptron algorithm was first shown to converge to the optimal solution under a linear separability assumption on the data . This assumption implies that the linear perceptron is able to fit the complete dataset without errors.

In contrast to the above mentioned work, we first show that the strong growth condition (SGC) implies that SGD with a constant step-size and Nesterov momentum achieves the accelerated convergence rate of the deterministic setting for both strongly-convex and convex functions (Section 3). Our result gives some theoretical justification behind the empirical success of using Nesterov acceleration with SGD . Further, in Section 4 we consider non-convex objectives and prove under the SGC that constant step-size SGD is able to find a first-order stationary point as efficiently as deterministic gradient descent. To the best of our knowledge, this is the first work to study accelerated and non-convex rates under the SGC.

After the release of the first version of this work, Liu et al. also considered minimizing strongly-convex loss functions using a variant of Nesterov acceleration assuming interpolation. In this setting they show accelerated rates for the squared loss, and under additional assumptions give accelerated rates for general strongly-convex functions. However, it is not clear if these additional assumptions are satisfied by common loss functions. Indeed, these additional assumptions imply the SGC (see Section 6.1) so the result presented in Section 3 is more widely-applicable. Similarly, the work of Jain et al. uses tail-averaging to obtain accelerated rates but only for the special case of the squared loss under interpolation. Furthermore, unlike these works, we show accelerated rates for convex functions (that are not strongly-convex) under the SGC.

Another work appearing after the release of the initial version of this work is Bassily et al. , who considered minimizing non-convex functions satisfying the Polyak-Lojasiewicz (PL) inequality (a generalization of strong-convexity) under the interpolation condition. This is a much stronger assumption than we make in Section 4 to analyze non-convex functions (since it implies all local optima are global optima), but under this condition they show that SGD can achieve a linear convergence rate. However, the step-size needed to achieve this rate is proportional to the PL constant which is typically extremely small (and is often is both unknown and difficult to estimate). By exploiting the stronger SGC, in this version of the paper we have added a result under the PL inequality (Section 4) that achieves a faster rate by using a step-size that depends only on the smoothness properties of the functions.

In this work, we also relax the strong growth condition to a more practical weak growth condition (WGC). In Section 5, we prove that the weak growth condition is sufficient to obtain the optimal convergence of constant step-size SGD for smooth strongly-convex and convex functions. To demonstrate the applicability of our growth conditions in practice, we first show that for models interpolating the data, the WGC is satisfied for all smooth and convex loss functions with a finite-sum structure (Section 6.1). Furthermore, we prove that functions satisfying the WGC and the PL condition also satisfy the SGC. Under additional assumptions, we show that it is also satisfied for the squared-hinge loss. This result enables us to prove an $O(1/k^{2})$ mistake bound for $k$ iterations of an accelerated stochastic perceptron algorithm using the squared-hinge loss (Section 7). Finally, in Section 8, we evaluate our claims with experiments on synthetic and real datasets.

Background

While most of our results apply for general SGD methods, a subset of our results rely on the function $f(w)$ having a finite-sum structure meaning that $f(w)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(w)$. In the context of supervised machine learning, given a training dataset of $n$ points, the term $f_{i}(w)$ corresponds to the loss function for the point $(x_{i},y_{i})$ when the model parameters are equal to $w$. Here $x_{i}$ and $y_{i}$ refer to the feature vector and label for point $i$ respectively. Common choices of the loss function include the squared loss where $f_{i}(w)=\frac{1}{2}\left(w^{\mathsf{\scriptscriptstyle T}}x_{i}-y_{i}\right)^{2}$, the hinge loss where $f_{i}(w)=\max(0,1-y_{i}w^{\mathsf{\scriptscriptstyle T}}x_{i})$ or the squared-hinge loss where $f_{i}(w)=\max\left(0,1-y_{i}w^{\mathsf{\scriptscriptstyle T}}x_{i}\right)^{2}$. The finite sum setting includes both simple models such as logistic regression or least squares and more complex models like non-parametric regression and deep neural networks.

In order to derive convergence rates, we need to make additional assumptions about the function $f$ . Beyond differentiability, our results assume that the function $f(\cdot)$ satisfies some or all of the following common assumptions. For all points $w$, $v$ and for constants $f^{*}$, $\mu$, and $L$;

Note that some of our results in Section 6 rely on the finite-sum structure and we explicitly state when we need this additional assumption.

In this paper, we consider the case where the model is able to interpolate or fit the labelled training data completely. This is true for expressive models such as non-parametric regression and over-parametrized deep neural networks. For common loss functions that are lower-bounded by zero, interpolating the data results in zero training loss. Interpolation also implies that the gradient with respect to each point converges to zero at the optimum. Formally, in the finite-sum setting, if the function $f(\cdot)$ is minimized at $w^{*}$, i.e., if $\nabla f(w^{*})=0$, then for all functions $f_{i}(\cdot)$, $\nabla f_{i}(w^{*})=0$.

The strong growth condition (SGC) used connects the rates at which the stochastic gradients shrink relative to the full gradient. Formally, for any point $w$ and the noise random variable $z$, the function $f$ satisfies the strong growth condition with constant $\rho$ if,

For this inequality to hold, if $\nabla f(w)=0$, then $\nabla f_{i}(w)=0$ for all $i$. Thus, functions satisfying the SGC necessarily satisfy the above interpolation property. Schmidt and Le Roux’s work derives optimal convergence rates for constant step-size SGD under the above condition for both convex and strongly-convex functions. In the next section, we show that the SGC implies the accelerated rate of convergence for constant step-size SGD with Nesterov momentum.

SGD with Nesterov acceleration under the SGC

We first describe constant step-size SGD with Nesterov acceleration. The algorithm consists of three sequences ($w_{k},\zeta_{k},v_{k}$) updated in each iteration . Specifically, it consists of the following update rules:

Here, $\eta$ is the constant step-size for the SGD step and $\alpha_{k}$, $\beta_{k}$, $\gamma_{k}$ are tunable parameters to be set according to the properties of $f$.

In order to derive a convergence rate for the above algorithm under the SGC, we first observe that a form of the SGC is satisfied in the case of coordinate descent . In this case, we choose a coordinate (typically at random) and perform a gradient descent step with respect to that coordinate. The notion of a coordinate in this case is analogous to that of an individual loss function in the finite sum case. For coordinate descent, a zero gradient at the optimal solution implies that the partial derivative with respect to each coordinate is also equal to zero. This is analogous to the SGC in the finite-sum case, although we note the results in this section do not require the finite-sum assumption.

We use this analogy formally in order to extend the proof of Nesterov’s accelerated coordinate descent to derive convergence rates for the above algorithm when using the SGC. This enables us to prove the following theorems (with proofs in Appendices B.1.1 and B.1.3) in both the strongly-convex and convex settings.

Under $L$-smoothness and $\mu$ strong-convexity, if $f$ satisfies the SGC with constant $\rho$, then SGD with Nesterov acceleration with the following choice of parameters,

results in the following convergence rate:

Under $L$-smoothness and convexity, if $f$ satisfies the SGC with constant $\rho$, then SGD with Nesterov acceleration with the following choice of parameters,

results in the following convergence rate:

The above theorems show that constant step-size SGD with Nesterov momentum achieves the accelerated rate of convergence up to a $\rho^{2}$ factor for both strongly-convex and convex functions.

SGD for non-convex functions satisfying the SGC

In this section, we show that the SGC results in an improvement over the $O\left(1/\sqrt{k}\right)$ rate for SGD in the non-convex setting . In particular, we show that under the strong growth condition, constant step-size SGD is able to find a first-order stationary point as efficiently as deterministic gradient descent. We prove the following theorem (with the proof in Appendix B.2),

Under $L$-smoothness, if $f$ satisfies SGC with constant $\rho$, then SGD with a constant step-size $\eta=\frac{1}{\rho L}$ attains the following convergence rate:

The above theorem shows that under the SGC, SGD with a constant step-size can attain the optimal $O(1/k)$ rate for non-convex functions. To the best of our knowledge, this is the first result for non-convex functions under interpolation-like conditions. Under these conditions, constant step-size SGD has a better convergence rate than algorithms which have recently been proposed to improve on SGD . Note that the above theorem applies to neural networks with a sigmoid activation function under the assumption that the strong-growth condition is satisfied. Hence, our results also provide some theoretical justification for the effectiveness of SGD for non-convex over-parameterized models like deep neural networks.

Under the additional assumption that the function satisfies the Polyak- Lojasiewicz condition (a generalization of strong-convexity), we show that SGD can obtain linear convergence. Specifically, we prove the following theorem (with the proof in Appendix B.3),

Under $L$-smoothness, if $f$ satisfies SGC with constant $\rho$ and the Polyak- Lojasiewicz inequality with constant $\mu$, then SGD with a constant step-size $\eta=\frac{1}{\rho L}$ attains the following convergence rate:

Note that the PL condition or a related notion of restricted strong-convexity (RSI) is satisfied by numerous non-convex optimization problems of interest. These include neural networks , matrix completion and phase retrieval . Under the additional SGC assumption, the above theorem implies fast rates of convergence for SGD on these problems. In contrast, Bassily et al. do not assume the SGC and achieve a rate of $\left(1-\frac{\mu^{2}}{L^{2}}\right)^{k}$ using a much smaller step-size $\eta=\frac{\mu}{L^{2}}$.

Weak growth condition

In this section, we relax the strong growth condition to a more practical condition which we refer to as the weak growth condition (WGC). Formally, if the function $f(\cdot)$ is $L$-smooth and has a minima at $w^{*}$, then it satisfies the WGC with constant $\rho$, if for all points $w$ and noise random variable $z$,

In the above condition, notice that if $w=w^{*}$, then $\nabla f_{i}(w^{*})=0$ for all points $i$. Thus, the WGC implies the interpolation property explained in Section 2.

In this section, we relate the two growth conditions. We first prove that SGC implies WGC with the same $\rho$ without any additional assumptions, formally showing that the WGC is indeed weaker than the corresponding SGC. For the converse, a function satisfying the WGC satisfies the SGC with a worse constant if it also satisfies the Polyak- Lojasiewicz (PL) inequality . The above relations are captured by the following proposition, proved in Appendix B.6

If $f(\cdot)$ is $L$-smooth, satisfies the WGC with constant $\rho$ and the PL inequality with constant $\mu$, then it satisfies the SGC with constant $\frac{\rho L}{\mu}$.

Conversely, if $f(\cdot)$ is $L$-smooth, convex and satisfies the SGC with constant $\rho$, then it also satisfies the WGC with the same constant $\rho$.

2 SGD under the weak growth condition

Using the WGC, we obtain the following convergence rates for SGD with a constant step-size.

Under $L$-smoothness and $\mu$ strong-convexity, if $f$ satisfies the WGC with constant $\rho$, then SGD with a constant step-size $\eta=\frac{1}{\rho L}$ achieves the following rate:

Under $L$-smoothness and convexity, if $f$ satisfies the WGC with constant $\rho$, then SGD with a constant step-size $\eta=\frac{1}{4\rho L}$ and iterate averaging achieves the following rate:

Here, $\bar{w}_{k}=\frac{\left[\sum_{i=1}^{k}w_{i}\right]}{k}$ is the averaged iterate after $k$ iterations.

The proofs for Theorems 5 and 6 are deferred to Appendices B.4 and B.5 respectively. In these cases, the WGC is sufficient to show that constant step-size SGD can attain the deterministic rates up to a factor of $\rho$. Since this condition is weaker than the corresponding strong growth condition, our results subsume the SGC results . Note that an alternative way to obtain the result in Theorem 5 would be to observe that the WGC and strong convexity imply the SGC (with a constant $\frac{\rho L}{\mu}$) (Proposition 1) and then use the result by Schmidt et al. . This would result in an additional dependence on $\frac{\mu}{\rho L}$ which is worse than the rate in Theorem 5.

In the next section, we characterize the functions satisfying the growth conditions in practice.

Growth conditions in practice

In this section, we give examples of functions that satisfy the weak and strong growth conditions. In Section 6.1, we first show that for models interpolating the data, the WGC is satisfied by all smooth functions with a finite-sum structure. In section 6.2, we show that the SGC is satisfied by the squared-hinge loss under additional assumptions.

To characterize the functions satisfying the WGC, we first prove the following proposition (with the proof in Appendix B.7):

If the function $f(\cdot)$ is convex and has a finite-sum structure for a model that interpolates the data and $L_{\max}$ is the maximum smoothness constant amongst the functions $f_{i}(\cdot)$, then for all $w$,

Comparing the above equation to Equation 7, we see that any smooth finite-sum problem under interpolation satisfies the WGC with $\rho=\frac{L_{max}}{L}$. The WGC is thus satisfied by common loss functions such as the squared and squared-hinge loss. For these loss functions, if $L_{i}=L$ for all $i$, then Theorem 5 implies that SGD with $\eta=\frac{1}{L}$ results in linear convergence for strongly-convex functions. This matches the recently proved result of Ma et al. , whereas Theorem 6 allows us to generalize their result beyond strongly-convex functions.

2 Functions satisfying SGC

We now show that under additional assumptions on the data, the squared-hinge loss also satisfies the SGC. We first assume that the data is linearly separable with a margin equal to $\tau$, implying that for all $x$, $\tau=\max_{|w|=1}\inf_{x\in\mathcal{S}}w^{\top}x$. Here, $\mathcal{S}$ is the support of the distribution of the features $x$. Note that the above assumption implies the existence of a classifier $w^{*}$ such that $||w^{*}||=\frac{1}{\tau}$. In addition to this, we assume that the features have a finite support, meaning that the set $\mathcal{S}$ is finite and has a cardinality equal to $c$. Under these assumptions, we prove the following lemma in Appendix B.8,

For linearly separable data with margin $\tau$ and a finite support of size $c$, the squared-hinge loss satisfies the SGC with the constant $\rho=\frac{c}{\tau^{2}}$.

In the next section, we use the above lemma to prove a mistake bound for the perceptron algorithm using the squared-hinge loss.

Implication for Faster Perceptron

In this section, we use the strong growth property of the squared-hinge function in order to prove a bound on the number of mistakes made by the perceptron algorithm using a squared-hinge loss. The perceptron algorithm is used for training a linear classifier for binary classification and is guaranteed to converge for linearly separable data . It can be considered as stochastic gradient descent on the loss $f_{i}(w)=\max\{0,y_{i}x_{i}^{\top}w\}$.

In this paper, we consider a modified perceptron algorithm using the squared-hinge function as the loss. Note that since we assume the data to be linearly separable, a linear classifier is able to fit all the training data. Since the squared-hinge loss function is smooth, the conditions of Proposition 2 are satisfied, which implies that it satisfies the WGC with $\rho=\frac{L_{max}}{L}$. Also observe that since we assume that $||x||=1$, $L_{max}=L=1$. Using these facts with Theorem 6 and assuming that we start the optimization with $w_{0}=\mathbf{0}$, we obtain the following convergence rate using SGD with $\eta=1/4$,

To see this, recall that $||w^{*}||=\frac{1}{\tau}$ and the loss is equal to zero at the optima, implying that $f(w^{*})=0$.

The above result gives us a bound on the training loss. We use the following lemma (proved using the Markov inequality in Appendix B.9) to relate the mistake bound to the training loss.

If $f(w,x,y)$ represents the loss on the point $(x,y)$, then

Combining the above results, we obtain a mistake bound of $O\left(\frac{1}{\tau^{2}k}\right)$ when using the squared-hinge loss on linearly separable data. We thus recover the standard results for the stochastic perceptron.

Note that for a finite amount of data (when the expectation is with respect to a discrete distribution), if we use batch accelerated gradient descent (which is not one of the stochastic gradient algorithms studied in this paper, and for which no growth condition is needed), we obtain a mistake bound that decreases as $1/k^{2}$. This improves on existing mistake bounds that scale as $1/k$ . Note that both sets of algorithms have the same dependence on the margin $\tau$, but this deterministic accelerated method would require evaluating $n$ gradients on each iteration.

From Lemma B.9, we know that the squared-hinge loss satisfies the SGC with $\rho=\frac{c}{\tau^{2}}$. Under the same conditions as above, this lemma along with the result of Theorem 2 gives us the following bound:

Using the result from Lemma 2, this results in a mistake bound of the order $O\left(\frac{1}{\tau^{6}k^{2}}\right)$ while only requiring one gradient per iteration. Hence, the use of acceleration leads to an improved novel dependence of $O(1/k^{2})$, but requires the additional assumptions of Lemma B.9 and has a worse dependence on the margin $\tau$.

Experiments

In this section, we empirically validate our theoretical results. For the first set of experiments (Figures 1(a)-1(d)), we generate a synthetic binary classification dataset with $n=8000$ and the dimension $d=100$. We ensure that the data is linearly separable with a margin $\tau$, thus satisfying the interpolation property for training a linear classifier. We seek to minimize the finite-sum squared-hinge loss, $f(w)=\sum_{i=1}^{n}\max\left(0,1-y_{i}x_{i}^{\mathsf{\scriptscriptstyle T}}w\right)^{2}$. In Figure 1, we vary the margin $\tau$ and plot the logarithm of the loss with the number of effective passes (one pass is equal to $n$ iterations of SGD) over the data. In all of our experiments, we estimate the value of the smoothness parameter $L$ as the maximum eigenvalue of the Gram matrix $X^{T}X$.

We evaluate the performance of constant step-size SGD with and without acceleration. Since the squared-hinge loss satisfies the WGC with $\rho=\frac{L_{max}}{L}$ (Proposition 2), we use SGD with a constant step-size $\eta=1/L_{max}$Note that using $\eta=1/L_{max}$ lead to consistently better results as compared to using $\eta=1/4L_{max}$ as suggested by Theorem 6. (denoted as SGD in the plots). For using Nesterov acceleration, we experimented with the dependence of the margin $\tau$ on the constant $\rho$ in the SGC. We found that setting $\rho=1/\tau$ results in consistently stable but fast convergence across different choices of $\tau$. We thus use a step-size $\eta=\tau/L$ and set the tunable parameters in the update Equations 3-5 as specified by Theorem 2. We denote this variant of accelerated SGD as Acc-SGD in the subsequent plots. In Appendix C, we propose a line-search heuristic to dynamically estimate the value of $\rho$.

In each of the Figures 1(a)-1(d), we make the following observations: (i) SGD results in reasonably slow convergence. This observation is in line with other SGD methods using $1/L$ as the step-size . (ii) Acc-SGD with $\eta=\tau/L$ is consistently stable and as suggested by the theory, it results in faster convergence as compared to using SGD. (iii) For larger values of $\tau$ (Figures 1(a)- 1(b)), the training loss becomes equal to zero, verifying the interpolation property.

The next set of experiments (Figure 2) considers binary classification on the CovTypehttp://osmot.cs.cornell.edu/kddcup and Proteinhttp://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets datasets. For this, we train a linear classifer using the radial basis (non-parametric) features. Non-parametric regression models of this form are capable of interpolating the data and thus satisfy our assumptions. We subsample $n=8000$ random points from the datasets and use the squared-hinge loss as above. In this case, we perform a grid-search to obtain a good estimate of $\rho$. We choose $\rho=1$ for the CovType dataset and equal to $0.1$ for the Protein dataset.

From Figures 2(a) and 2(b), we make the following observations: (i) In Figure 2(a), both variants have similar performance. (ii) In Figure 2(b), the Acc-SGD leads to considerably faster convergence as compared to SGD. These experiments show that in cases where the interpolation property is satisfied, both SGD and accelerated SGD with a constant step-size can result in good empirical performance.

Conclusion

In this paper, we showed that under interpolation, the stochastic gradients of common loss functions satisfy specific growth conditions. Under these conditions, we proved that it is possible for constant step-size SGD (with and without Nesterov acceleration) to achieve the convergence rates of the corresponding deterministic settings. These are the first results achieving optimal rates in the accelerated and non-convex settings under interpolation-like conditions. We used these results to demonstrate the fast convergence of the stochastic perceptron algorithm employing the squared-hinge loss. We showed that both SGD and accelerated SGD with a constant step-size can lead to good empirical performance when the interpolation property is satisfied. As opposed to determining the step-size and the schedule for annealing it for current SGD-like methods, our results imply that under interpolation, we only need to automatically determine the constant step-size for SGD. In the future, we hope to develop line-search techniques for automatically determining this step-size for both the accelerated and non-accelerated variants.

Acknowledgements

We acknowledge support from the European Research Council (grant SEQUOIA 724063) and the CIFAR program on Learning with Machines and Brains. We also thank Nicolas Flammarion, Reza Babanezhad and Adrien Taylor for discussions related to this work. We also thank Kevin Scaman for discussions and insights on using acceleration with multiplicative noise.

References

Appendix A Incorporating additive error for Nesterov acceleration

For this section, we assume an additive error in the the strong growth condition implying that the following equation is satisfied for all $w$, $z$.

In this case, we have the counterparts of Theorems 1 and 2 as follows:

Under $L$-smoothness and $\mu$ strongly-convexity, if $f$ satisfies SGC with constant $\rho$ and an additive error $\sigma$, then SGD with Nesterov acceleration with the following choice of parameters,

results in the following convergence rate:

Under $L$-smoothness and convexity, if $f$ satisfies SGC with constant $\rho$ and an additive error $\sigma$, then SGD with Nesterov acceleration with the following choice of parameters,

results in the following convergence rate:

The above theorems are proved in appendices B.1.1 and B.1.3

Appendix B Proofs

Recall the update equations for SGD with Nesterov acceleration as follows:

We now prove the following lemma assuming that the function $f(\cdot)$ is $L$-smooth and $\mu$ strongly-convex.

Assume that the function is $L$-smooth and $\mu$ strongly-convex and satisfies the strong-growth condition in Equation 11. Then, using the updates in Equation 3-5 and setting the parameters according to Equations 12- 16, if $\eta\leq\frac{1}{\rho L}$, then the following relation holds:

Under the parameter setting according to Equations 12- 16, the following relation is true:

We now consider the strongly-convex case,

B.1.2 Proof of Theorem 1

B.1.3 Convex case

We now use the above lemmas to first prove the convergence rate in the convex case. In this case, $\mu=0$ and the result of Lemma 4 can be written as:

B.1.4 Proof of Theorem 2

B.2 Proof of Theorem 3

Recall the stochastic gradient descent update,

B.3 Proof of Theorem 4

Similar to the proof of Theorem 3, we can use the SGD update and Lipschitz continuity of the gradient to obtain the following equation for the stepsize $\eta\leq\frac{1}{\rho L}$:

B.4 Proof of Theorem 5

B.5 Proof of Theorem 6

B.6 Proof for Proposition 1

B.7 Proof for Proposition 2

B.8 Proof for Lemma 1

Let $a=y\cdot x$. For the squared-hinge loss, the strong growth condition is equivalent to

B.9 Proof for Lemma 2

Appendix C Additional experimental results

In this section, we propose to use a line-search heuristic for both constant step-size SGD and its accelerated variant. For SGD, we use the line-search proposed in SAG : start with an initial estimate $\hat{L}=1$ and in each iteration, we double the estimate when the condition $f_{k}\left(w_{k}-\frac{1}{\hat{L}}\nabla f_{k}(w_{k})\right)\leq f_{k}(w_{k})-\frac{1}{2\hat{L}}\left\|\nabla f_{k}(w_{k})\right\|^{2}$ is not satisfied. We denote this variant as SGD(LS) and the corresponding variant that uses a $1/L$ step-size as SGD(T). For the accelerated case, we use the same line-search procedure as above, but search for an appropriate value of $\rho L$. We denote the accelerated variant with and without line-search as Acc-SGD(LS) and Acc-SGD(T) respectively.

We make the following observations: (i) Accelerated SGD in conjunction with our line-search heuristic is stable across datasets. (ii) Acc-SGD(LS) either matches or outperforms Acc-SGD(T). (iii) In some cases, SGD(LS) can result in faster empirical convergence as compared to the accelerated variants. We plan to investigate better line-search methods for both SGD and Acc-SGD in the future.