Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates

Introduction

Stochastic gradient descent (SGD) and its variants are the preferred optimization methods in modern machine learning. They only require the gradient for one training example (or a small “mini-batch” of examples) in each iteration and thus can be used with large datasets. These first-order methods have been particularly successful for training highly-expressive, over-parameterized models such as non-parametric regression and deep neural networks . However, the practical efficiency of stochastic gradient methods is adversely affected by two challenges: (i) their performance heavily relies on the choice of the step-size (“learning rate”) and (ii) their slow convergence compared to methods that compute the full gradient (over all training examples) in each iteration .

Variance-reduction (VR) methods are relatively new variants of SGD that improve its slow convergence rate. These methods exploit the finite-sum structure of typical loss functions arising in machine learning, achieving both the low iteration cost of SGD and the fast convergence rate of deterministic methods that compute the full-gradient in each iteration. Moreover, VR makes setting the learning rate easier and there has been work exploring the use of line-search techniques for automatically setting the step-size for these methods . These methods have resulted in impressive performance on a variety of problems. However, the improved performance comes at the cost of additional memory or computational overheads, making these methods less appealing when training high-dimensional models on large datasets. Moreover, in practice VR methods do not tend to converge faster than SGD on over-parameterized models .

Indeed, recent works have shown that when training over-parameterized models, classic SGD with a constant step-size and without VR can achieve the convergence rates of full-batch gradient descent. These works assume that the model is expressive enough to interpolate the data. The interpolation condition is satisfied for models such as non-parametric regression , over-parametrized deep neural networks , boosting , and for linear classifiers on separable data. However, the good performance of SGD in this setting relies on using the proposed constant step-size, which depends on problem-specific quantities not known in practice. On the other hand, there has been a long line of research on techniques to automatically set the step-size for classic SGD. These techniques include using meta-learning procedures to modify the main stochastic algorithm , heuristics to adjust the learning rate on the fly , and recent adaptive methods inspired by online learning . However, none of these techniques have been proved to achieve the fast convergence rates that we now know are possible in the over-parametrized setting.

In this work, we use classical line-search methods to automatically set the step-size for SGD when training over-parametrized models. Line-search is a standard technique to adaptively set the step-size for deterministic methods that evaluate the full gradient in each iteration. These methods make use of additional function/gradient evaluations to characterize the function around the current iterate and adjust the magnitude of the descent step. The additional noise in SGD complicates the use of line-searches in the general stochastic setting and there have only been a few attempts to address this. Mahsereci et al. define a Gaussian process model over probabilistic Wolfe conditions and use it to derive a termination criterion for the line-search. The convergence rate of this procedure is not known, and experimentally we found that our proposed line-search technique is simpler to implement and more robust. Other authors use a line-search termination criteria that requires function/gradient evaluations averaged over multiple samples. However, in order to achieve convergence, the number of samples required per iteration (the “batch-size”) increases progressively, losing the low per iteration cost of SGD. Other work exploring trust-region methods assume that the model is sufficiently accurate, which is not guaranteed in the general stochastic setting. In contrast to these works, our line-search procedure does not consider the general stochastic setting and is designed for models that satisfy interpolation; it achieves fast rates in the over-parameterized regime without the need to manually choose a step-size or increase the batch size.

We make the following contributions: in Section 3 we prove that, under interpolation, SGD with a stochastic variant of the Armijo line-search attains the convergence rates of full-batch gradient descent in both the convex and strongly-convex settings. We achieve these rates under weaker assumptions than the prior work and without the explicit knowledge of problem specific constants. We then consider minimizing non-convex functions satisfying interpolation . Previous work proves that constant step-size SGD achieves a linear rate for non-convex functions satisfying the PL inequality . SGD is further known to achieve deterministic rates for general non-convex functions under a stronger assumption on the growth of the stochastic gradients . Under this assumption and an upper bound (that requires knowledge of the “Lipschitz” constant) on the maximum step size, we prove that SGD with Armijo line-search can achieve the deterministic rate for general non-convex functions (Section 4). Note that these are the first convergence rates for SGD with line-search in the interpolation setting for both convex and non-convex functions.

Moving beyond SGD, in Section 5 we consider the stochastic extra-gradient (SEG) method used to solve general variational inequalities . These problems encompass both convex minimization and saddle point problems arising in robust supervised learning and learning with non-separable losses or regularizers . In the interpolation setting, we show that a variant of SEG with a “Lipschitz” line-search convergences linearly when minimizing an important class of non-convex functions satisfying the restricted secant inequality (RSI). Moreover, in Appendix E, we prove that the same algorithm results in linear convergence for both strongly convex-concave and bilinear saddle point problems satisfying interpolation.

In Section 6, we give heuristics to use large step-sizes and integrate acceleration with our line-search techniques, which improves practical performance of the proposed methods. We compare our algorithms against numerous optimizers on a synthetic matrix factorization problem (Section 7.2), convex binary-classification problems using radial basis function (RBF) kernels (Section 7.3), and non-convex multi-class classification problems with deep neural networks (Section 7.4). We observe that when interpolation is (approximately) satisfied, the proposed methods are robust and have competitive performance across models and datasets. Moreover, SGD with Armijo line-search results in both faster convergence and better generalization performance for classification using deep networks. Finally, in Appendix H.1, we evaluate SEG with line-search for synthetic bilinear saddle point problems. The code to reproduce our results can be found at https://github.com/IssamLaradji/sls.

One of the most important special cases where interpolation is often satisfied is training deep neural networks. The work of Paul Tseng is the earliest work that we are aware of that considers training neural networks with SGD and a line search. Tseng further shows convergence and convergence rates for SGD in an interpolation setting, but his method was never widely-adopted and is more complicated than the simple stochastic Armijo method analyzed in this work. Several recent works have evaluated the empirical performance of using Armijo-style line-searches in an SGD setting for training deep neural networks, including exploring combinations with momentum/acceleration and quasi-Newton methods . The work of Truong and Nguyen in particular shows strong empirical performance for several benchmark deep learning problems, but their theory only considers deterministic settings and does not apply to SGD.

In concurrent work to ours, Berrada et al. propose adaptive step-sizes for SGD on convex, finite-sum loss functions under an $\epsilon$-interpolation condition. Unlike our approach, $\epsilon$-interpolation requires knowledge of a lower bound on the global minimum and only guarantees approximate convergence to a stationary point. Moreover, in order to obtain linear convergence rates, they assume $\mu$-strong-convexity of each individual function. This assumption with $\epsilon$-interpolation reduces the finite-sum optimization to minimization of any single function in the finite sum.

Assumptions

We aim to minimize a differentiable function $f$ assuming access to noisy stochastic gradients of the function. We focus on the common machine learning setting where the function $f$ has a finite-sum structure meaning that $f(w)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(w)$. Here $n$ is equal to the number of points in the training set and the function $f_{i}$ is the loss function for the training point $i$. Depending on the model, $f$ can either be strongly-convex, convex, or non-convex. We assume that $f$ is lower-bounded by some value $f^{*}$ and that $f$ is $L$-smooth implying that the gradient $\nabla f$ is $L$-Lipschitz continuous.

We assume that the model is able to interpolate the data and use this property to derive convergence rates. Formally, interpolation requires that the gradient with respect to each point converges to zero at the optimum, implying that if the function $f$ is minimized at $w^{*}$ and thus $\nabla f(w^{*})=0$, then for all functions $f_{i}$ we have that $\nabla f_{i}(w^{*})=0$. For example, interpolation is exactly satisfied when using a linear model with the squared hinge loss for binary classification on linearly separable data.

Stochastic Gradient Descent for Convex Functions

Armijo line-search is a standard method for setting the step-size for gradient descent in the deterministic setting . We adapt it to the stochastic case as follows: at iteration $k$, the Armijo line-search selects a step-size satisfying the following condition:

Here, $c>0$ is a hyper-parameter. Note that the above line-search condition uses the function and gradient values of the mini-batch at the current iterate $w_{k}$. Thus, compared to SGD, checking this condition only makes use of additional mini-batch function (and not gradient) evaluations. In the context of deep neural networks, this corresponds to extra forward passes on the mini-batch.

In our theoretical results, we assume that there is a maximum step-size $\eta_{\text{max}}$ from which the line-search starts in each iteration $k$ and that we choose the largest step-size $\eta_{k}$ (less than or equal to $\eta_{\text{max}}$) satisfying (1). In practice, backtracking line-search is a common way to ensure that Equation 1 is satisfied. Starting from $\eta_{\text{max}}$, backtracking iteratively decreases the step-size by a constant factor $\beta$ until the line-search succeeds (see Algorithm 1). Suitable strategies for resetting the step-size can avoid backtracking in the majority of iterations and make the step-size selection procedure efficient. We describe such strategies in Section 6. With resetting, we required (on average) only one additional forward pass on the mini-batch per iteration when training a standard deep network model (Section 7.4). Empirically, we observe that the algorithm is robust to the choice of both $c$ and $\eta_{\text{max}}$; setting $c$ to a small constant and $\eta_{\text{max}}$ to a large value consistently results in good performance.

We bound the chosen step-size in terms of the properties of the function(s) selected in iteration $k$.

The step-size $\eta_{k}$ returned by the Armijo line-search and constrained to lie in the $(0,\eta_{\text{max}}]$ range satisfies the following inequality,

where $L_{ik}$ is the Lipschitz constant of $\nabla f_{i_{k}}$.

The proof is in Appendix A and follows the deterministic case . Note that Equation (1) holds for all smooth functions (for small-enough $\eta_{k}$), does not require convexity, and guarantees backtracking line-search will terminate at a non-zero step-size. The parameter $c$ controls the “aggressiveness” of the algorithm; small $c$ values encourage a larger step-size. For a sufficiently large $\eta_{\text{max}}$ and $c\leq 1/2$, the step-size is at least as large as $1/L_{ik}$, which is the constant step-size used in the interpolation setting . In practice, we expect these larger step-sizes to result in improved performance. In Appendix A, we also give upper bounds on $\eta_{k}$ if the function $f_{i_{k}}$ satisfies the Polyak-Lojasiewicz (PL) inequality with constant $\mu_{ik}$. PL is a weaker condition than strong-convexity and does not require convexity. In this case, $\eta_{k}$ is upper-bounded by the minimum of $\eta_{\text{max}}$ and $1/(2c\cdot\mu_{ik})$. If we use a backtracking line-search that multiplies the step-size by $\beta$ until (1) holds, the step-size will be smaller by at most a factor of $\beta$ (we do not include this dependence in our results).

2 Convergence rates

In this section, we characterize the convergence rate of SGD with Armijo line-search in the strongly-convex and convex cases. The theorems below are proved in Appendix B and Appendix C respectively.

Assuming (a) interpolation, (b) $L_{i}$-smoothness, (c) convexity of $f_{i}$’s, and (d) $\mu$ strong-convexity of $f$, SGD with Armijo line-search with $c=\nicefrac{{1}}{{2}}$ in Eq. 1 achieves the rate:

Here $\bar{\mu}=\sum_{i=1}^{n}\mu_{i}/n$ is the average strong-convexity of the finite sum and $L_{max}=\max_{i}L_{i}$ is the maximum smoothness constant in the $f_{i}$’s.

In contrast to the previous results that depend on $\mu$, the above linear rate depends on $\bar{\mu}\leq\mu$. Note that unlike Berrada et al. , we do not require that each $f_{i}$ is strongly convex, but for $\bar{\mu}$ to be non-zero we still require that at least one of the $f_{i}$’s is strongly-convex.

Assuming (a) interpolation, (b) $L_{i}$-smoothness and (c) convexity of $f_{i}$’s, SGD with Armijo line-search for all $c>1/2$ in Equation 1 and iterate averaging achieves the rate:

Here, $\bar{w}_{T}=\frac{\left[\sum_{i=1}^{T}w_{i}\right]}{T}$ is the averaged iterate after $T$ iterations and $L_{\text{max}}=\max_{i}L_{i}$.

Stochastic Gradient Descent for Non-convex Functions

Assuming (a) the SGC with constant $\rho$ and (b) $L_{i}$-smoothness of $f_{i}$’s, SGD with Armijo line-search in Equation 1 with $c>1-\frac{L_{\text{max}}}{\rho L}$ and setting $\eta_{\text{max}}<\frac{2}{\rho L}$ achieves the rate:

where $\delta=\left(\eta_{\text{max}}+\frac{2(1-c)}{L_{\text{max}}}\right)-\rho\left(\eta_{\text{max}}-\frac{2(1-c)}{L_{\text{max}}}+L\eta_{\text{max}}^{2}\right)$.

We prove Theorem 3 in Appendix D. The result requires knowledge of $\rho\;L_{\text{max}}$ to bound the maximum step-size, which is less practically appealing. It is not immediately clear how to relax this condition and we leave it for future work. In Appendix F, we show that SGD with the Armijo line-search obtains a similar $O(1/T)$ rate with slightly relaxed conditions on $c$ and $\eta_{\text{max}}$ when $(\eta_{k})$ are non-increasing or the Armijo condition holds on a mini-batch which is independent of $\nabla f_{ik}(w_{k})$. Moreover, in the next section, we show that if the non-convex function satisfies a specific curvature condition, a modified stochastic extra-gradient algorithm can achieve a linear rate under interpolation without additional assumptions or knowledge of the Lipschitz constant.

Stochastic Extra-Gradient Method

In this section, we use a modified stochastic extra-gradient (SEG) method for convex and non-convex minimization. For finite-sum minimization, stochastic extra-gradient (SEG) has the following update:

It computes the gradient at an extrapolated point $w^{\prime}_{k}$ and uses it in the update from the current iterate $w_{k}$. Note that using the same sample $i_{k}$ and step-size $\eta_{k}$ for both steps is important for the subsequent theoretical results. We now describe a “Lipschitz” line-search strategy in order to automatically set the step-size for SEG.

The “Lipschitz” line-search has been used by previous work in the deterministic and the variance reduced settings . It selects a step-size $\eta_{k}$ that satisfies the following condition:

As before, we use backtracking line-search starting from the maximum value of $\eta_{\text{max}}$ to ensure that the chosen step-size satisfies the above condition. If the function $f_{ik}$ is $L_{ik}$-smooth, the step-size returned by the Lipschitz line-search satisfies $\eta_{k}\geq\min\left\{\nicefrac{{c}}{{L_{ik}}},\eta_{\text{max}}\right\}$. Like the Armijo line-search in Section 3, the Lipschitz line-search does not require knowledge of the Lipschitz constant. Unlike the line-search strategy in the previous sections, checking condition (4) requires computing the gradient at a prospective extrapolation point. We now prove convergence rates for SEG with Lipschitz line-search for both convex and a special class of non-convex problems.

2 Convergence rates for minimization

For the next result, we assume that each function $f_{i}(\cdot)$ satisfies the restricted secant inequality (RSI) with constant $\mu_{i}$, implying that for all $w$, $\langle\nabla f_{i}(w),w-w^{*}\rangle\geq\mu_{i}\left\|w-w^{*}\right\|\kern-1.00006pt{}^{2}$. RSI is a weaker condition than strong-convexity. With additional assumptions, RSI is satisfied by important non-convex models such as single hidden-layer neural networks , matrix completion and phase retrieval . Under interpolation, we show SEG results in linear convergence for functions satisfying RSI. In particular, we obtain the following guarantee:

Assuming (a) interpolation, (b) $L_{i}$-smoothness, and (c) $\mu_{i}$-RSI of $f_{i}$’s, SEG with Lipschitz line-search in Eq. 4 with $c=\nicefrac{{1}}{{4}}$ and $\eta_{\text{max}}\leq\min_{i}1/4\mu_{i}$ achieves the rate:

where $\bar{\mu}=\frac{\sum_{i=1}^{n}\mu_{i}}{n}$ is the average RSI constant of the finite sum and $\mathcal{X}^{*}$ is the non-empty set of optimal solutions. The operation $\mathcal{P}_{\mathcal{X}^{*}}[w]$ denotes the projection of $w$ onto $\mathcal{X}^{*}$.

See Appendix E.2 for proof. Similar to the result of Theorem 1, the rate depends on the average RSI constant. Note that we do not require explicit knowledge of the Lipschitz constant to achieve the above rate. The constraint on the maximum step-size is mild since the minimum $\mu_{i}$ is typically small, thus allowing for large step-sizes. Moreover, Theorem 4 improves upon the $\left(1-\mu^{2}/L^{2}\right)$ rate obtained using constant step-size SGD . In Appendix E.2, we show that the same rate can be attained by SEG with a constant step-size. In Appendix E.3, we show that under interpolation, SEG with Lipschitz line-search also achieves the desired $O(1/T)$ rate for convex functions.

3 Convergence rates for saddle point problems

In Appendix E.4, we use SEG with Lipschitz line-search for a class of saddle point problems of the form $\min_{u\in{U}}\max_{v\in\mathcal{V}}\phi(u,v)$. Here $\mathcal{U}$ and $\mathcal{V}$ are the constraint sets for the variables $u$ and $v$ respectively. In Theorem 6 in Appendix E.4, we show that under interpolation, SEG with Lipschitz line-search results in linear convergence for functions $\phi(u,v)$ that are strongly-convex in $u$ and strongly-concave in $v$. The required conditions are satisfied for robust optimization with expressive models capable of interpolating the data. Furthermore, the interpolation property can be used to improve the convergence for a bilinear saddle-point problem . In Theorem 7 in Appendix E.5, we show that SEG with Lipschitz line-search results in linear convergence under interpolation. We empirically validate this claim with simple synthetic experiments in Appendix H.1.

Practical Considerations

In this section, we give heuristics to use larger step-sizes across iterations and discuss ways to use common acceleration schemes with our line-search techniques.

Recall that our theoretical analysis assumes that the line-search in each iteration starts from a global maximum step-size $\eta_{\text{max}}$. However, in practice this strategy increases the amount of backtracking and consequently the algorithm’s runtime. A simple alternative is to initialize the line-search in each iteration to the step-size selected in the previous iteration, $\eta_{\text{max}}=\eta_{k-1}$. Unfortunately, with this strategy the step-size can not increase and convergence is slowed in practice (it takes smaller steps than necessary).

There are a variety of strategies available that can increase the initial step-size $\eta_{\text{max}}$ between iterations to improve the practical performance of line-search methods [61, Chapter 3]. We consider increasing the step-size across iterations by initializing the backtracking at iteration $k$ with $\eta_{k-1}\cdot{\gamma}^{b/n}$, where $b$ is the size of the mini-batch and $\gamma>1$ is a tunable parameter. These heuristics correspond to the options used in Algorithm 2. This approach has previously been used in the context of VR-SGD methods , and several related stochastic methods have also appeared in the recent literature .

We also consider the Goldstein line-search that uses additional function evaluations to check the curvature condition $f_{ik}\left(w_{k}-\eta_{k}\nabla f_{ik}(w_{k})\right)\geq f_{ik}(w_{k})-(1-c)\cdot\eta_{k}\left\|\nabla f_{ik}(w_{k})\right\|\kern-1.00006pt{}^{2}$ and increases the step-size if it is not satisfied. Here, $c$ is the constant in Equation 1. The resulting method decreases the step-size if the Armijo condition is not satisfied and increases it if the curvature condition does not hold. Algorithm 3 in Appendix I gives pseudo-code for SGD with the Goldstein line-search.

2 Acceleration

In practice, augmenting stochastic methods with some form of momentum or acceleration often results in faster convergence . Related work in this context includes algorithms specifically designed to achieve an accelerated rate of convergence in the stochastic setting . Unlike these works, our experiments considered simple ways of using either Polyak or Nesterov acceleration with the proposed line-search techniques.Similar methods have also been explored empirically in prior work . In both cases, similar to adaptive methods using momentum , we use SGD with Armijo line-search to determine $\eta_{k}$ and then use it directly within the acceleration scheme. When using Polyak momentum, the effective update can be given as: $w_{k+1}=w_{k}-\eta_{k}\nabla f_{ik}(w_{k})+\alpha(w_{k}-w_{k-1})$, where $\alpha$ is the momentum factor. This update rule has been used with a constant step-size and proven to obtain linear convergence rates on the generalization error for quadratic functions under an interpolation condition . For Nesterov acceleration, we use the variant for the convex case (which has no additional hyper-parameters) with our line-search. The pseudo-code for using these methods with the Armijo line-search is given in Appendix I.

Experiments

We describe the experimental setup in Section 7.1. In Section 7.2, we present synthetic experiments to show the benefits of over-parametrization. In Sections 7.3 and 7.4, we showcase the convergence and generalization performance of our methods for kernel experiments and deep networks, respectively.

We benchmark five configurations of the proposed line-search methods: SGD with (1) Armijo line-search with resetting the initial step-size (Algorithm 1 using option $2$ in Algorithm 2), (2) Goldstein line-search (Algorithm 3), (3) Polyak momentum (Algorithm 5), (4) Nesterov acceleration (Algorithm 6), and (5) SEG with Lipschitz line-search (Algorithm 4) with option $2$ to reset the step-size. Appendix F gives additional details on our experimental setup and the default hyper-parameters used for the proposed line-search methods. We compare our methods against Adam , which is the most common adaptive method, and other methods that report better performance than Adam: coin-betting , L4L4 applied to momentum SGD (L4 Mom) in https://github.com/iovdin/l4-pytorch was unstable in our experiments and we omit it from the main paper. , and Adabound . We use the default learning rates for the competing methods. Unless stated otherwise, our results are averaged across $5$ independent runs.

2 Synthetic experiment

We make the following observations: (i) for $k=4$ (where interpolation does not hold) the proposed methods converge quicker than other optimizers but all methods reach an artificial optimization floor, (ii) using $k=10$ yields an over-parametrized model where SGD with both Armijo and Goldstein line-search converge linearly to machine precision, (iii) SEG with Lipschitz line-search obtains fast convergence according to Theorem 4, and (iv) adaptive-gradient methods stagnate in all cases. These observations validate our theoretical results and show that over-parameterization and line-search can allow for fast, “painless” optimization using SGD and SEG.

3 Binary classification with kernels

We consider convex binary classification using RBF kernels without regularization. We experiment with four standard datasets: mushrooms, rcv1, ijcnn, and w8a from LIBSVM . The mushrooms dataset satisfies the interpolation condition with the selected kernel bandwidths, while ijcnn, rcv1, and w8a do not. For these experiments we also compare against a standard VR method (SVRG) and probabilistic line-search (PLS) .PLS is impractical for deep networks since it requires the second moment of the mini-batch gradients and needs GP model inference for every line-search evaluation. Figure 3 shows the training loss and test accuracy on mushrooms and ijcnn for the different optimizers with softmax loss. Results for rcv1 and w8a are given in Appendix H.2. We make the following observations: (i) SGD + Armijo, Nesterov + Armijo, and SEG + Lipschitz perform the best and are comparable to hand-tuned SVRG. (ii) The proposed line-search methods perform well on ijcnn even though it is not separable in kernel space. This demonstrates some robustness to violations of the interpolation condition.

4 Multi-class classification using deep networks

We benchmark the convergence rate and generalization performance of our line-search methods on standard deep learning experiments. We consider non-convex minimization for multi-class classification using deep network models on the MNIST, CIFAR10, and CIFAR100 datasets. Our experimental choices follow the setup in Luo et al. . For MNIST, we use a $1$ hidden-layer multi-layer perceptron (MLP) of width $1000$. For CIFAR10 and CIFAR100, we experiment with the standard image-classification architectures: ResNet-34 and DenseNet-121 . We note that promising empirical results for a variety of line-search methods related to those used in our experiments have previously been reported for the CIFAR10 and CIFAR100 datasets for a variety of architectures . We also compare to the best performing constant step-size SGD with the step-size selected by grid search.

From Figure 4, we observe that: (i) SGD with Armijo line-search consistently leads to the best performance in terms of both the training loss and test accuracy. It also converges to a good solution much faster when compared to the other methods. (ii) The performance of SGD with line-search and Polyak momentum is always better than “tuned” constant step-size SGD and Adam, whereas that of SGD with Goldstein line-search is competitive across datasets. We omit Nesterov + Armijo as it is unstable and diverges and omit SEG since it resulted in slower convergence and worse performance.

We also verify that our line-search methods do not lead to excessive backtracking and function evaluations. Figure 5 (right) shows the cost per iteration for the above experiments. Our line-searches methods are only marginally slower than Adam and converge much faster. In practice, we observed SGD+Armijo uses only one additional function evaluation on average. Figure 5 (left) shows the evolution of step-sizes for SGD+Armijo in our experiments. For deep neural networks, SGD+Armijo automatically finds a step-size schedule resembling cosine-annealing . In Appendix H.0.1, we evaluate and compare the hyper-parameter sensitivity of Adam, constant step-size SGD, and SGD with Armijo line-search on CIFAR10 with ResNet-34. While SGD is sensitive to the choice of the step-size, the performance of SGD with Armijo line-search is robust to the value of $c$ in the ${[0.1,0.5}]$ range. There is virtually no effect of $\eta_{\text{max}}$, since the correct range of step-sizes is found in early iterations.

Conclusion

We showed that under the interpolation condition satisfied by modern over-parametrized models, simple line-search techniques for classic SGD and SEG lead to fast convergence in both theory and practice. For future work, we hope to strengthen our results for non-convex minimization using SGD with line-search and study stochastic momentum techniques under interpolation. More generally, we hope to utilize the rich literature on line-search and trust-region methods to improve stochastic optimization for machine learning.

We would like to thank Yifan Sun and Nicolas Le Roux for insightful discussions and Nicolas Loizou and Frederik Kunstner for their help with the proofs. AM is supported by the NSERC CGS M award. IL is funded by the UBC Four-Year Doctoral Fellowships (4YF), This research was also partially supported by the Canada CIFAR AI Chair Program, the CIFAR LMB Program, by a Google Focused Research award, by an IVADO postdoctoral scholarship (for SV), by a Borealis AI fellowship (for GG), by the Canada Excellence Research Chair in "Data Science for Realtime Decision-making" and by the NSERC Discovery Grants RGPIN-2017-06936 and 2015-06068.

References

Appendix A Proof of Lemma 1

Appendix B Proof for Theorem 1

Appendix C Proof for Theorem 2

Appendix D Proof for Theorem 3

Let $\Delta_{k}=f(w_{k+1})-f(w_{k})$. Starting from $L$-smoothness of $f$:

It remains to show that $\delta>0$ holds. Our analysis proceeds in cases.

Case 1: $\eta_{\text{max}}\leq\frac{2(1-c)}{L_{\text{max}}}$. Then $\eta_{\text{min}}=\eta_{\text{max}}$ and

Case 2: $\eta_{\text{max}}>\frac{2(1-c)}{L_{\text{max}}}$. Then $\eta_{\text{min}}=\frac{2(1-c)}{L_{\text{max}}}$ and

To avoid contradiction with the case assumption $\frac{2(1-c)}{L_{\text{max}}}<\eta_{\text{max}}$, we require

The line-search requires $c\in\left(0,1\right)$. Noting that $\rho\geq 1$ by definition, we have $\frac{L_{\text{max}}}{\rho L}>0$ as long as $L,L_{\text{max}}>0$. The Lipschitz constants are strictly positive when $f$ is bounded-below and non-zero. We obtain the non-empty constraint set

Substituting the maximum value for $c$ into the upper-bound on $\eta_{\text{max}}$ yields a similar requirement,

Putting the two cases together gives the final constraints on $c$ and $\eta_{\text{max}}$ as

We note that the upper and lower bounds on $\eta_{k}$ are consistent since

where the last inequality follows from the bound on $\eta_{\text{max}}$. In particular, taking $c\rightarrow 1$ and $\eta_{\text{max}}\rightarrow\frac{2}{\rho L}$ yields an adaptive step-size $\eta_{k}\in(0,\frac{2}{\rho L}).$

Appendix E Proofs for SEG

We denote $\left\|u-v\right\|^{2}$ as $\Delta(u,v)=\Delta(v,u)$. We first prove the following lemma that will be useful in the subsequent analysis.

For any set of vectors $a,b,c,d$, if $a=b+c$, then,

E.2 Proof for Theorem 4

We start from Lemma 2 with $a=w_{k+1}=w_{k}-\eta_{k}\nabla f_{ik}(w^{\prime}_{k})$ and $d=w^{*}$:

Now we consider using a constant step-size as well as the Lipschitz line-search.

E.2.2 Using the line-search

E.3 Proof of SEG for convex minimization

Assuming the interpolation property and under $L$-smoothness and convexity of $f$, SEG with Lipschitz line-search with $c=1/\sqrt{2}$ in Equation 4 and iterate averaging achieves the following rate:

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

E.4 SEG for general strongly monotone operators

Let $F(\cdot)$ be a Lipschitz (strongly)-monotone operator. $F$ satisfies the following inequalities for all $u$, $v$,

Here, $\mu$ is the strong-monotonicity constant and $L$ is the Lipschitz constant. Note that $\mu=0$ for monotone operators. We seek the solution $w^{*}$ to the following optimization problem: $\sup_{w}\langle F(w^{*}),w^{*}-w\rangle\leq 0$.

Note that for strongly-convex minimization where $w^{*}=\operatorname*{arg\,min}f(w)$, $F$ is equal to the gradient operator and $\mu$ and $L$ are the strong-convexity and smoothness constants in the previous sections.

SEG is a common method for optimizing stochastic variational inequalities and results in an $O(1/\sqrt{T})$ rate for monotone operators and an $O(1/T)$ rate for strongly-monotone operators . For strongly-monotone operators, the convergence can be improved to obtain a linear rate by using variance-reduction methods exploiting the finite-sum structure in $F$. In this setting, $F(w)=\frac{1}{n}\sum_{i=1}^{n}F_{i}(w)$. To the best of our knowledge, the interpolation condition has not been studied in the context of general strongly monontone operators. In this case, the interpolation condition implies that $F_{i}(w^{*})=0$ for all operators $F_{i}$ in the finite sum.

Assuming (a) interpolation, (b) $L$-smoothness and (c) $\mu$-strong monotonocity of $F$, SEG using Lipschitz line-search with $c=1/4$ in Equation 4 and setting $\eta_{\text{max}}\leq\min_{i}\frac{1}{4\mu_{i}}$ has the rate:

From here on, the theorem follows the same proof as that for Theorem 4 above with the $F_{ik}($) instead of $\nabla f_{ik}($) and the strong-convexity constant being replaced with the constant for strong-monotonicity. ∎

Like in the RSI case, the above result can also be obtained using a constant step-size $\eta\leq\frac{1}{4\;L_{\text{max}}}$.

E.5 SEG for bilinear saddle point problems

Let us consider the bilinear saddle-point problem of the form $\min_{x}\max_{y}x^{\top}Ay-x^{\top}b-y^{\top}c$, where $A$ is the “coupling” matrix and where both $b$ and $c$ are vectors . In this case, the (monotone) operator $F(x,y)=\left[Ax-b,\,-A^{\top}y+c\right]$ and we assume the finite sum formulation as:

We show that the interpolation condition enables SEG with Lipschitz line-search achieve a linear rate of convergence. In every iteration, the SEG algorithm samples rows $A_{i}$ (resp. columns $A_{j}$) of the matrix $A$ and the respective coefficient $b_{i}$ (resp. $c_{j}$). If $x_{k}$ and $y_{k}$ correspond to the iterates for the minimization and maximization problem respectively, then the update rules for SEG can be written as:

We now prove that SEG attains the following linear rate of convergence.

Assuming the (a) interpolation property and for the (b) bilinear saddle point problem, SEG with Lipschitz line-search with $c=1/\sqrt{2}$ in Equation 4 achieves the following rate:

If $(x^{*},y^{*})$ is the solution to the above saddle point problem, then interpolation hypothesis implies that

In the following, without loss of generality, we will assume that $b=c=0$.

The line-search hypothesis can be simplified as,

Noting that $L_{\text{max}}=\left[\max_{i}\sigma_{\text{max}}(A_{i}A_{i}^{\top})\right]^{1/2}$, we obtain $\eta_{k}\geq\min\left\{\left[2\max_{i}\sigma_{\text{max}}(A_{i}A_{i}^{\top})\right]^{-1/2},\eta_{\text{max}}\right\}$ from the Lipschitz line-search. Taking the expectation with respect to $i_{k}$ gives,

Applying this inequality recursively and taking expectations yields the final result. ∎

Observe that the rate depends on the minimum and maximum singular values of the matrix formed using the mini-batch of examples selected in the SEG iterations. Note that these are the first results for bilinear min-max problems in the stochastic, interpolation setting.

Appendix F Additional Non-Convex Proofs

We can prove additional convergence results for non-convex functions satisfying the SGC by (1) enforcing independence between $\eta_{k}$ and the stochastic gradient $\nabla f_{ik}(w_{k})$ or (2) enforcing that the sequence of step-sizes $(\eta_{k})$ is non-increasing.

To enforce independence of the step-size and stochastic gradient, we perform a backtracking line-search at the current iterate $w_{k}$ using a mini-batch of examples that is independent of the mini-batch on which $\nabla f_{ik}(w_{k})$ is evaluated. This equates to evaluating the Armijo condition in Equation 1 using stochastic estimates $f_{jk}(w_{k})$ and $\nabla f_{jk}(w_{k})$ that are independent of $\nabla f_{ik}(w_{k})$, which is used in the gradient update. In practice, the mini-batch at previous iteration can be re-used for the line-search. A similar technique has recently been used to prove convergence of SGD with the AdaGrad step-size . Alternatively, the current mini-batch can be divided, with one set of examples used to evaluate the stochastic Armijo condtion and the other to compute the gradient-step. In this setting, we prove the following convergence rate for SGD with the Armijo line-search.

Assuming (a) the SGC with constant $\rho$, (b) $L_{i}$-smoothness of $f_{i}$’s, and (c) independence of $\eta_{k}$ and the stochastic gradient $\nabla f_{ik}(w_{k})$ at every iteration $k$, SGD with the Armijo line-search in Equation 1 with $c=1/2$ and setting $\eta_{\text{max}}=\nicefrac{{1}}{{\rho L}}$ achieves the rate:

We can extend this result to obtain a linear convergence rate when $f$ satisfies the Polyak-Łojasiewicz inequality with constant $\mu$. This is formalized in the following theorem.

Assuming (a) the SGC with constant $\rho$, (b) $L_{i}$-smoothness of $f_{i}$’s, (c) $f$ is $\mu$-PL, and (d) independence of $\eta_{k}$ and the stochastic gradient $\nabla f_{ik}(w_{k})$ at every iteration $k$, SGD with the Armijo line-search in Equation 1 with $c=1/2$ and setting $\eta_{\text{max}}=\nicefrac{{1}}{{\rho L}}$ achieves the rate:

Starting from Equation 11 and applying the PL-inequality:

F.2 Non-increasing Step-sizes

An alternative approach is to assume that the sequence of step-sizes $(\eta_{k})$ is non-increasing. That is, $\eta_{k}\leq\eta_{k-1}$ for all $k$. This holds, for example, when using reset option 0 in Algorithm 2. In this case, we prove a $O(1/T)$ convergence result for SGD with the stochastic Armijo line-search. Our result assumes that the iterates $(w_{k})$ are contained in a bounded set $\mathcal{X}$ centered on $w^{*}$ and depends on the diameter of this set,

Assuming (a) the SGC with constant $\rho$, (b) $L_{i}$-smoothness of $f_{i}$’s, (c) $\eta_{k}$ are non-increasing, and (d) $\left\|w_{k}-w^{*}\right\|\leq D$ for all $k$, SGD with the Armijo line-search in Equation 1 with $c=1/2$ and setting $\eta_{\text{max}}=\nicefrac{{1}}{{\rho L}}$ achieves the rate:

where $C=\max\left\{f(w_{k}):k=0,\dots,T-1\right\}$

Appendix G Additional Experimental Details

In this section we give details for all experiments in the main paper and the additional results given in Appendix H. In all experiments, we used the default learning rates provided in the implementation for the methods we compare against. For the proposed line-search methods and for all experiments in this paper, we set the initial step-size $\eta_{\text{max}}=1$ and use back-tracking line-search where we reduce the step-size by a factor of $0.9$ if the line-search is not satisfied. We used $c=0.1$ for all our experiments with both Armijo and Goldstein line-search procedures, $c=0.9$ for SEG with Lipschitz line-search, and $c=0.5$ when using Nesterov acceleration Note that these choices are inspired by the theory. For Polyak acceleration, we use $c=0.1$ in our experiments with deep neural networks and $c=0.5$ otherwise. For our non-convex experiments, we always constrain the step-size to be less than $10$ to prevent it from becoming unbounded. Note that we conduct a robustness study to quantify the influence of the $c$ and $\eta_{\text{max}}$ parameter in Section H.0.1. For the heuristic in , we set the step-size increase factor to $\gamma=1.5$ for convex minimization and use $\gamma=2$ for non-convex minimization. Similarly, when using Polyak momentum we set the momentum factor to the highest value that does not lead to divergence. It is set to $\beta=0.8$ in the convex case and $\beta=0.6$ in the non-convex case We hope to use method such as to automatically set the momentum parameter in the future..

G.2 Binary Classification using Kernel Methods

We give additional details for the experiments on binary classification with RBF kernels in Section 7.3. For all datasets, we used only the training sets available in the LIBSVM library and used an 80:20 split of it. The 80 percent split of the data was used as a training set and 20 percent split as the test set. The bandwidth parameters for the RBF kernel were selected by grid search using 10-fold cross-validation on the training splits. The grid of kernel bandwidth parameters that were considered is [0.05, 0.1, 0.25, 0.5, 1, 2.5, 5, 10, 15, 20]. For the cross-validation, we used batch L-BFGS to minimize both objectives on the rcv1 and mushrooms datasets, while we used the Coin-Betting algorithm on the larger w8a and ijcnn datasets with mini-batches of 100 examples. In both cases, we ran the optimizers for 100 epochs on each fold. The bandwidth parameters that maximized cross-validated accuracy were selected for our final experiments. The final kernel parameters are given in Table 1, along with additional details for each dataset.

We used the default hyper-parameters for all baseline optimizers used in our other experiments. For PLS, we used the exponential exploration strategy and its default hyper-parameters. Fixed step-size SVRG requires that the step-size parameter to be well-tuned in order to obtain a fair comparison with adaptive methods. To do so, we selected step-sizes by grid search. For each step-size, a 3-fold cross-validation experiment was run on each dataset’s training set. On each fold, SVRG was run with mini-batches of size $100$ for $50$ epochs. Final step-sizes were selected by maximizing convergence rate on the cross-validated loss. The grid of possible step-sizes was expanded whenever the best step-size found was the largest or smallest step-size in the considered grid. We found that the mushrooms, ijcnn, and rcv1 datasets admitted very large step-sizes; in this case, we terminated our grid-search when increasing the step-size further gave only marginal improvement. The final step-sizes selected by this procedure are given in Table 1.

Each optimizer was run with five different random seeds in the final experiment. All optimizers used mini-batches of $100$ examples and were run for $35$ epochs. Experiment figures display shaded error bars of one standard-deviation from the mean. Note that we did not use a bias parameter in these experiments.

G.3 Multi-class Classification using Deep Networks

For mutliclass-classification with deep networks, we considered the MNIST and CIFAR10 datasets, each with $10$ classes. For MNIST, we used the standard training set consisting of $60$k examples and a test set of $10$k examples; whereas for CIFAR10, this split was $50$k training examples and $10$k examples in the test set. As in the kernel experiments, we evaluated the optimizers using the softmax. All optimizers were used with their default learning rates and without any weight decay. We used the experimental setup proposed in and used a batch-size of $128$ for all methods and datasets. As before, each optimizer was run with five different random seeds in the final experiment. The optimizers were run until the performance of most methods saturated; $100$ epochs for MNIST and $200$ epochs for the models on the CIFAR10 dataset. We compare against a tuned SGD method, that uses a constant step-size selected according to a search on the ${[1e-1,1e-5]}$ grid and picking the variant that led to the best convergence in the training loss. This procedure resulted in choosing a step-size of $0.01$ for the MLP on MNIST and $0.1$ for both models on CIFAR10.

Appendix H Additional Results

In this experiment, we compare the robustness and computational complexity between the three best performing methods across datasets: Adam, constant step-size and SGD with Armijo line-search. For both Adam and constant step-size SGD, we vary the step-size in the $[10^{-1},10^{-5}]$ range; whereas for the SGD with line-search, we vary the parameter $c$ in the $[0.1,0.5]$ range and vary $\eta_{max}\in[1,10^{3}]$ range. We observe that although the performance of constant step-size SGD is sensitive to its step-size; SGD with Armijo line-search is robust with respect to the $c$ parameter. Similarly, we find that Adam is quite robust with respect to its initial learning rate.

H.1 Min-max optimization for bilinear games

Chavdarova et al. propose a challenging stochastic bilinear game as follows:

Standard methods such as stochastic extragradient fail to converge on this example. We compare Adam, ExtraAdam , SEG with backtracking line-search using Equation 4 with $c=1/\sqrt{2}$ and $p$-SVRE . The latter combines restart, extrapolation and variance reduction for finite sum. It exhibits linear convergence rate but requires the tuning of the restart parameter $p$ and do not have any convergence guarantees on such bilinear problem. ExtraAdam combines extrapolation and Adam has good performances on GANs although it fails to converge on this simple stochastic bilinear example.

In our synthetic experiment, we consider two variants of this bilinear game; one where interpolation condition is satisfied, and the other when it is not. As predicted by the theory, SEG + Lipschitz results in linear convergence where interpolation is satisfied and does not converge to the solution when it is not. When interpolation is satisfied, empirical convergence rate is faster than SVRE, the best variance reduced method. Note that SVRE does well even in the absence of interpolation, and the both variants of Adam fail to converge on either example.

H.2 Synthetic Experiment and Binary Classification with Kernels

We provide additional results for binary classification with RBF kernels on the rcv1 and w8a datasets. As before, we do not use regularization. We compare against L4 Mom as well as the original baselines introduced in Section 7.1. For fairness, we reproduce the results for mushrooms and ijcnn with L4 Mom included. Figure 8 shows the training loss and test accuracy for the methods considered, while Figure 10 shows the evolution of step-sizes for SGD+Armijo on all four kernel datasets.

The proposed line-search methods perform well on both rcv1 and w8a although neither dataset satisfies the interpolation condition with the selected kernel bandwidths. Furthermore, all of the proposed line-search methods converge quickly and remain at the global minimum for the w8a dataset, which is particularly ill-conditioned. In contrast, adaptive optimizers, such as Adam, fail to converge. Unlike other methods, PLS uses a separate mini-batch for each step of the line-search procedure. Accordingly, we plot the number of iterations accepted by the probabilistic Wolfe conditions, which may correspond to several mini-batches of information. Despite this, PLS converges slowly. In practice, we observed that the initial step-size was accepted at most iterations of the PLS line-search.

Figure 10 provides an additional comparison against L4 Mom on the synthetic matrix factorization problem from Section 7.2. We observe that L4 Mom is unstable when used for stochastic optimization of this problem, especially when interpolation is not satisfied. The method converges slowly when interpolation is satisfied.

Appendix I Algorithm Pseudo-Code