Adaptive Gradient Descent without Descent

Introduction

Since the early days of optimization it was evident that there is a need for algorithms that are as independent from the user as possible. First-order methods have proven to be versatile and efficient in a wide range of applications, but one drawback has been present all that time: the stepsize. Despite certain success stories, line search procedures and adaptive online methods have not removed the need to manually tune the optimization parameters. Even in smooth convex optimization, which is often believed to be much simpler than the nonconvex counterpart, robust rules for stepsize selection have been elusive. The purpose of this work is to remedy this deficiency.

The problem formulation that we consider is the basic unconstrained optimization problem

The simplest and most known approach to this problem is the gradient descent method (GD), whose origin can be traced back to Cauchy . Although it is probably the oldest optimization method, it continues to play a central role in modern algorithmic theory and applications. Its definition can be written in a mere one line,

one can show that GD with $\lambda\in(0,\frac{2}{L})$ converges to an optimal solution . Moreover, with $\lambda=\frac{1}{L}$ the convergence rate is

where $x^{*}$ is any solution of (1). Note that this bound is not improvable .

We identify four important challenges that limit the applications of gradient descent even in the convex case:

GD is not general: many functions do not satisfy (3) globally.

GD is not a free lunch: one needs to guess $\lambda$, potentially trying many values before a success.

GD is not robust: failing to provide $\lambda<\frac{2}{L}$ may lead to divergence.

GD is slow: even if $L$ is finite, it might be arbitrarily larger than local smoothness.

Certain ways to address some of the issues above already exist in the literature. They include line search, adaptive Polyak’s stepsize, mirror descent, dual preconditioning, and stepsize estimation for subgradient methods. We discuss them one by one below, in a process reminiscent of cutting off Hydra’s limbs: if one issue is fixed, two others take its place.

The most practical and generic solution to the aforementioned issues is known as line search (or backtracking). This direction of research started from the seminal works and and continues to attract attention, see and references therein. In general, at each iteration the line search executes another subroutine with additional evaluations of $\nabla f$ and/or $f$ until some condition is met. Obviously, this makes each iteration more expensive.

At the same time, the famous Polyak’s stepsize stands out as a very fast alternative to gradient descent. Furthermore, it does not depend on the global smoothness constant and uses the current gradient to estimate the geometry. The formula might look deceitfully simple, $\lambda_{k}=\frac{f(x^{k})-f_{*}}{\|\nabla f(x^{k})\|^{2}}$, but there is a catch: it is rarely possible to know $f_{*}$. This method, again, requires the user to guess $f_{*}$. What is more, with $\lambda$ it was fine to underestimate it by a factor of 10, but the guess for $f_{*}$ must be tight, otherwise it has to be reestimated later .

Seemingly no issue is present in the Barzilai-Borwein stepsize. Motivated by the quasi-Newton schemes, suggested using steps

Alas, the convergence results regarding this choice of $\lambda_{k}$ are very limited and the only known case where it provably works is quadratic problems . In general it may not work even for smooth strongly convex functions, see the counterexample in .

Other more interesting ways to deal with non-Lipschitzness of $\nabla f$ use the problem structure. The first method, proposed in and further developed in , shows that the mirror descent method , which is another extension of GD, can be used with a fixed stepsize, whenever $f$ satisfies a certain generalization of (3). In addition, proposed the dual preconditioning method—another refined version of GD. Similarly to the former technique, it also goes beyond the standard smoothness assumption of $f$, but in a different way. Unfortunately, these two simple and elegant approaches cannot resolve all issues yet. First, not many functions fulfill respective generalized conditions. And secondly, both methods still get us back to the problem of not knowing the allowed range of stepsizes.

A whole branch of optimization considers adaptive extensions of GD that deal with functions whose (sub)gradients are bounded. Probably the earliest work in that direction was written by . He showed that the method

where $g^{k}\in\partial f(x^{k})$ is a subgradient, converges for properly chosen sequences $(\lambda_{k})$, see, e.g., Section 3.2.3 in . Moreover, $\lambda_{k}$ requires no knowledge about the function whatsoever.

Similar methods that work in online setting such as Adagrad received a lot of attention in recent years and remain an active topic of research . Methods similar to Adagrad—Adam , RMSprop and Adadelta —remain state-of-the-art for training neural networks. The corresponding objective is usually neither smooth nor convex, and the theory often assumes Lipschitzness of the function rather than of the gradients. Therefore, this direction of research is mostly orthogonal to ours, although we do compare with some of these methods in our neural networks experiment.

We also note that without momentum Adam and RMSprop reduce to signSGD , which is known to be non-convergent for arbitrary stepsizes on a simple quadratic problem .

In a close relation to ours is the recent work , where there was proposed an adaptive golden ratio algorithm for monotone variational inequalities. As it solves a more general problem, it does not exploit the structure of (1) and, as most variational inequality methods, has a more conservative update. Although the method estimates the smoothness, it still requires an upper bound on the stepsize as input.

We propose a new version of GD that at no cost resolves all aforementioned issues. The idea is simple, and it is surprising that it has not been yet discovered. In each iteration we choose $\lambda_{k}$ as a certain approximation of the inverse local Lipschitz constant. With such a choice, we prove that convexity and local smoothness of $f$ are sufficient for convergence of iterates with the complexity $\mathcal{O}(1/k)$ for $f(x^{k})-f_{*}$ in the worst case.

Let us now briefly discuss why we believe that proofs based on monotonicity and global smoothness lead to slower methods.

Gradient descent is by far not a recent method, so there have been obtained optimal rates of convergence. However, we argue that adaptive methods require rethinking optimality of the stepsizes. Take as an example a simple quadratic problem, $f(x,y)=\frac{1}{2}x^{2}+\frac{\delta}{2}y^{2}$, where $\delta\ll 1$. Clearly, the smoothness constant of this problem is equal to $L=1$ and the strong convexity one is $\mu=\delta$. If we run GD from an arbitrary point $(x^{0},y^{0})$ with the “optimal” stepsize $\lambda=\frac{1}{L}=1$, then one iteration of GD gives us $(x^{1},y^{1})=(0,(1-\delta)y^{0})$, and similarly $(x^{k},y^{k})=(0,(1-\delta)^{k}y^{0})$. Evidently for $\delta$ small enough it will take a long time to converge to the solution $(0,0)$. Instead GD would converge in two iterations if it adjusts its step after the first iteration to $\lambda=\frac{1}{\delta}$.

Nevertheless, all existing analyses of the gradient descent with $L$-smooth $f$ use stepsizes bounded by $2/L$. Besides, functional analysis gives

from which $1/L$ can be seen as the “optimal” stepsize. Alternatively, we can assume that $f$ is $\mu$-strongly convex, and the analysis in norms gives

whence the “optimal” step is $\frac{2}{L+\mu}$.

Finally, line search procedures use some certain type of monotonicity, for instance ensuring that $f(x^{k+1})\leq f(x^{k})-c\|\nabla f(x^{k})\|^{2}$ for some $c>0$. We break with this tradition and merely ask for convergence in the end.

Main part

Recall that a mapping is locally Lipschitz if it is Lipschitz over any compact set of its domain. A function $f$ with (locally) Lipschitz gradient $\nabla f$ is called (locally) smooth. It is natural to ask whether some interesting functions are smooth locally, but not globally.

independently of the properties of $f$ (apart from convexity), we can show that the iterates $(x^{k})$ remain bounded. Here and everywhere else we use the convention $1/0=+\infty$, so if $\nabla f(x^{k})-\nabla f(x^{k-1})=0$, the second inequality can be ignored. In the first iteration it might happen that $\lambda_{1}=\min\{+\infty\}$, in this case we suppose that any choice of $\lambda_{1}>0$ is possible.

Although Algorithm 1 needs $x^{0}$ and $\lambda_{0}$ as input, this is not an issue as one can simply fix $x^{0}=0$ and $\lambda_{0}=10^{-10}$. Equipped with a tiny $\lambda_{0}$, we ensure that $x^{1}$ will be close enough to $x^{0}$ and likely will give a good estimate for $\lambda_{1}$. Otherwise, this has no influence on further steps.

2 Analysis without descent

It is now time to show our main contribution, the new analysis technique. The tools that we are going to use are the well-known Cauchy-Schwarz and convexity inequalities. In addition, our methods are related to potential functions , which is a powerful tool for producing tight bounds for GD.

Another divergence from the common practice is that our main lemma includes not only $x^{k+1}$ and $x^{k}$, but also $x^{k-1}$. This can be seen as a two-step analysis, while the majority of optimization methods have one-step bounds. However, as we want to adapt to the local geometry of our objective, it is rather natural to have two terms to capture the change in the gradients.

Now, it is time to derive a characteristic inequality for a specific Lyapunov energy.

Let $k\geq 1$. We start from the standard way of analyzing GD:

As usually, we bound the scalar product by convexity of $f$:

These two steps have been repeated thousands of times, but now we continue in a completely different manner. We have precisely one “bad” term in (7), which is $\|x^{k+1}-x^{k}\|^{2}$. We will bound it using the difference of gradients:

Let us estimate the first two terms in the right-hand side above. First, definition of $\lambda_{k}$, followed by Cauchy-Schwarz and Young’s inequalities, yields

Plugging (2.2) and (2.2) in (2.2), we obtain

Finally, using the produced estimate for $\|x^{k+1}-x^{k}\|^{2}$ in (7), we deduce the desired inequality (5). ∎

The above lemma already might give a good hint why our method works. From inequality (5) together with condition $\lambda_{k}^{2}\leq(1+\theta_{k-1})\lambda_{k-1}^{2}$, we obtain that the Lyapunov energy—the left-hand side of (5)—is decreasing. This gives us boundedness of $(x^{k})$, which is often the key ingredient for proving convergence. In the next theorem we formally state our result.

and $D$ is a constant that explicitly depends on the initial data and the solution set, see (11).

Our proof will consist of two parts. The first one is a straightforward application of Lemma 1, from which we derive boundedness of $(x^{k})$ and complexity result. Due to its conciseness, we provide it directly after this remark. In the second part, we prove that the whole sequence $(x^{k})$ converges to a solution. Surprisingly, this part is a bit more technical than expected, and thus we postpone it to the appendix.

Fix any $x^{*}$ from the solution set of eq. 1. Telescoping inequality (5), we deduce

Note that by definition of $\lambda_{k}$, the second line above is always nonnegative. Thus, the sequence $(x^{k})$ is bounded. Since $\nabla f$ is locally Lipschitz, it is Lipschitz continuous on bounded sets. It means that for the set $\mathcal{C}=\operatorname{\overline{conv}}\{x^{*},x^{0},x^{1},\dots\}$, which is bounded as the convex hull of bounded points, there exists $L>0$ such that

Clearly, $\lambda_{1}=\frac{\|x^{1}-x^{0}\|}{2\|\nabla f(x^{1})-\nabla f(x^{0})\|}\geq\frac{1}{2L}$, thus, by induction one can prove that $\lambda_{k}\geq\frac{1}{2L}$, in other words, the sequence $(\lambda_{k})$ is separated from zero.

Now we want to apply the Jensen’s inequality for the sum of all terms $f(x^{i})-f_{*}$ in the left-hand side of (11). Notice, that the total sum of coefficients at these terms is

where $\hat{x}^{k}$ is given in the statement of the theorem. By this, the first part of the proof is complete. Convergence of $(x^{k})$ to a solution is provided in the appendix. ∎

As we have shown that $\lambda_{i}\geq\frac{1}{2L}$ for all $i$, we have a theoretical upper bound $f(\hat{x}^{k})-f_{*}\leq\frac{DL}{k}$. Note that in practice, however, $(\lambda_{k})$ might be much larger than the pessimistic lower bound $\frac{1}{2L}$, which we observe in our experiments together with a faster convergence.

3 f𝑓f is locally strongly convex

Since one of our goals is to make optimization easy to use, we believe that a good method should have state-of-the-art guarantees in various scenarios. For strongly convex functions, this means that we want to see linear convergence, which is not covered by normalized GD or online methods. In section 2.1 we have shown that Algorithm 1 matches the $\mathcal{O}(1/\varepsilon)$ complexity of GD on convex problems. Now we show that it also matches $\mathcal{O}(\frac{L}{\mu}\log\frac{1}{\varepsilon})$ complexity of GD when $f$ is locally strongly convex. Similarly to local smoothness, we call $f$ locally strongly convex if it is strongly convex over any compact set of its domain.

For proof simplicity, instead of using bound $\lambda_{k}\leq\sqrt{1+\theta_{k-1}}\lambda_{k-1}$ as in step 4 of Algorithm 1 we will use a more conservative bound $\lambda_{k}\leq\sqrt{1+\frac{\theta_{k-1}}{2}}\lambda_{k-1}$ (otherwise the derivation would be too technical). It is clear that with such a change Theorem 1 still holds true, so the sequence is bounded and we can rely on local smoothness and local strong convexity.

We want to highlight that in our rate $\kappa$ depends on the local Lipschitz and strong convexity constants $L$ and $\mu$, which is meaningful even when these properties are not satisfied globally. Similarly, if $f$ is globally smooth and strongly convex, our rate is still faster as it depends on the smaller local constants.

Heuristics

In this section, we describe several extensions of our method. We do not have a full theory for them, but believe that they are of interest in applications.

Suppose that $f$ is $\mu$-strongly convex. One version of the accelerated gradient method proposed by Nesterov is

where $\beta=\frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L}+\sqrt{\mu}}$. Adaptive gradient descent for strongly convex $f$ efficiently estimated $\frac{1}{2L}$ by

where $p^{k}$ and $p^{k-1}$ are some elements of the dual space and $\Theta_{k}=\frac{\Lambda_{k}}{\Lambda_{k-1}}$. A natural choice then is $p^{k}=\nabla f(x^{k})$ since it is an element of the dual space that we use. What is its value? It is well known that $\nabla f^{*}(\nabla f(x))=x$, so we come up with the update rule

and hence we can estimate $\beta$ by $\beta_{k}=\frac{\sqrt{1/\lambda_{k}}-\sqrt{\Lambda_{k}}}{\sqrt{1/\lambda_{k}}+\sqrt{\Lambda_{k}}}$.

We summarize our arguments in Algorithm 2. Unfortunately, we do not have any theoretical guarantees for it.

Estimating strong convexity parameter $\mu$ is important in practice. Most common approaches rely on restarting technique proposed by , see also and references therein. Unlike Algorithm 2, these works have theoretical guarantees, however, the methods themselves are more complicated and still require tuning of other unknown parameters.

2 Uniting our steps with stochastic gradients

Here we would like to discuss applications of our method to the problem

where $f_{\xi}$ is almost surely $L$-smooth and $\mu$-strongly convex. Assume that at each iteration we get sample $\xi^{k}$ to make a stochastic gradient step,

Then, we have two ways of incorporating our stepsize into SGD. The first is to reuse $\nabla f_{\xi^{k}}(x^{k})$ to estimate $L_{k}=\frac{\|\nabla f_{\xi^{k}}(x^{k})-\nabla f_{\xi^{k}}(x^{k-1})\|}{\|x^{k}-x^{k-1}\|}$, but this would make $\lambda_{k}\nabla f_{\xi^{k}}(x^{k})$ biased. Alternatively, one can use an extra sample to estimate $L_{k}$, but this is less intuitive since our goal is to estimate the curvature of the function used in the update.

We give a full description in Algorithm 3. We remark that the option with a biased estimate performed much better in our experiments with neural networks. The theorem below provides convergence guarantees for both cases, but with different assumptions.

Note that in both cases we match the known dependency on $\varepsilon$ up to logarithmic terms, but we get an extra $\kappa$ as the price for adaptive estimation of the stepsize.

Another potential application of our techniques is estimation of decreasing stepsizes in SGD. The best known rates for SGD , are obtained using $\lambda_{k}$ that evolves as $\mathcal{O}\left(\frac{1}{L+\mu k}\right)$. This requires estimates of both smoothness and strong convexity, which can be borrowed from the previous discussion. We leave rigorous proof of such schemes for future work.

Experiments

In the experimentsSee https://github.com/ymalitsky/adaptive_gd, we compare our approach with the two most related methods: GD and Nesterov’s accelerated method for convex functions . Additionally, we consider line search, Polyak step, and Barzilai-Borwein method. For neural networks we also include a comparison with SGD, SGDm and Adam.

In Figure 4 (left) we see that the Barzilai-Borwein method can indeed be very fast. However, as we said before, it lacks a theoretical basis and Figure 4 (middle) illustrates this quite well. Just changing one dataset to another makes both versions of this method to diverge on a strongly convex and smooth problem. Polyak’s method consistently performs well (see Figure 4 (left and middle)), however, only after it was fed with $f_{*}$ that we found by running another method. Unfortunately, for logistic regression there is no way to guess this value beforehand.

Finally, line search for GD (Armijo version) and Nesterov GD (implemented as in ) eliminates the need to know the stepsize, but this comes with a higher price per iteration as Figure 4 (right) shows. Actually in all our experiments for logistic regression with different datasets one iteration of Armijo line search was approximately 2 times more expensive than AdGD, while line search for Nesterov GD was 4 times more expensive. We note that these observations are consistent with the theoretical derivations in .

We use standard ResNet-18 and DenseNet-121 architectures implemented in PyTorch and train them to classify images from the Cifar10 dataset with cross-entropy loss.

We use batch size 128 for all methods. For our method, we observed that $\frac{1}{L_{k}}$ works better than $\frac{1}{2L_{k}}$. We ran it with $\sqrt{1+\gamma\theta_{k}}$ in the other factor with values of $\gamma$ from $\{1,0.1,0.05,0.02,\\ 0.01\}$ and $\gamma=0.02$ performed the best. For reference, we provide the result for the theoretical estimate as well and value $\gamma=0.1$ in the plot with estimated stepsizes. The results are depicted in Figures 5 and 6 and other details are provided in section 9.

We can see that, surprisingly, our method achieves better test accuracy than SGD despite having the same train loss. At the same time, our method is significantly slower at the early stage and the results are quite noisy for the first 75 epochs. Another observation is that the smoothness estimates are very non-uniform and $\lambda_{k}$ plummets once train loss becomes small.

Perspectives

We briefly provide a few directions which we personally consider to be important and challenging.

Nonconvex case. A great challenge for us is to obtain theoretical guarantees of the proposed method in the nonconvex settings. We are not aware of any generic first-order method for nonconvex optimization that does not rely on the descent lemma (or its generalization), see, e.g., .

Performance estimation. In our experiments we often observed much better performance of Algorithm 1, than GD or AGD. However, the theoretical rate we can show coincides with that of GD. The challenge here is to bridge this gap and we hope that the approach pioneered by and further developed in has a potential to do that.

Composite minimization. In classical first-order methods, the transition from smooth to composite minimization is rather straightforward. Unfortunately, the proposed proof of Algorithm 1 does not seem to provide any route for generalization and we hope there is some way of resolving this issue.

Stochastic optimization. The derived bounds for the stochastic case are not satisfactory and have a suboptimal dependency on $\kappa$. However, it is not clear to us whether one can extend the techniques from the deterministic analysis to improve the rate.

Heuristics. Finally, we want to have some solid ground in understanding the performance of the proposed heuristics.

Yura Malitsky wishes to thank Roman Cheplyaka for his interest in optimization that partly inspired the current work. Yura Malitsky was supported by the ONRG project N62909-17-1-2111 and HASLER project N16066.

References

Appendix:

Recall that in the proof of Theorem 1 we only showed boundedness of the iterates and complexity for minimizing $f(x)$. It remains to show that sequence $(x^{k})$ converges to a solution. For this, we need some variation of the Opial lemma.

Then $(x^{k})$ converges to some element in $\mathcal{X}$.

Let $\bar{x}_{1}$, $\bar{x}_{2}$ be any cluster points of $(x^{k})$. Thus, there exist two subsequences $(x^{k_{i}})$ and $(x^{k_{j}})$ such that $x^{k_{i}}\to\bar{x}_{1}$ and $x^{k_{j}}\to\bar{x}_{2}$. Since $\|x^{k}-x\|^{2}+a_{k}$ is nonnegative and bounded, $\lim_{k\to\infty}(\|x^{k}-x\|^{2}+a_{k})$ exists for any $x\in\mathcal{X}$. Let $x=\bar{x}_{1}$. This yields

Hence, $\lim_{i\to\infty}a_{k_{i}}=\lim_{j\to\infty}a_{k_{j}}+\|\bar{x}_{1}-\bar{x}_{2}\|^{2}$. Doing the same with $x=\bar{x}_{2}$ instead of $x=\bar{x}_{1}$, yields $\lim_{j\to\infty}a_{k_{j}}=\lim_{i\to\infty}a_{k_{i}}+\|\bar{x}_{1}-\bar{x}_{2}\|^{2}$. Thus, we obtain that $\bar{x}_{1}=\bar{x}_{2}$, which finishes the proof. ∎

Another statement that we need here is the following tightening of the convexity property.

Note that in the first part we have already proved that $(x^{k})$ is bounded and that $\nabla f$ is $L$-Lipschitz on $\mathcal{C}=\operatorname{\overline{conv}}\{x^{*},x^{0},x^{1},\dots\}$. Invoking Lemma 3, we deduce that

This indicates that instead of using inequality (6) in the proof of Lemma 1, we could use a better estimate (14). However, we want to emphasize that we did not assume that $\nabla f$ is globally Lipschitz, but rather obtained Lipschitzness on $\mathcal{C}$ as an artifact of our analysis. Clearly, in the end this improvement gives us an additional term $\frac{\lambda_{k}}{L}\|\nabla f(x^{k})\|^{2}$ in the left-hand side of (5), that is

Thus, telescoping (15), one obtains that $\sum_{i=1}^{k}\frac{\lambda_{k}}{L}\|\nabla f(x^{k})\|^{2}\leq D$. As $\lambda_{k}\geq\frac{1}{2L}$, one has that $\nabla f(x^{k})\to 0$. Now we might conclude that all cluster points of $(x^{k})$ are solutions of (1).

Let $\mathcal{X}$ be the solution set of (1) and $a_{k}=\frac{1}{2}\|x^{k}-x^{k-1}\|^{2}+2\lambda_{k}\theta_{k}(f(x^{k-1})-f_{*})$. We want to finish the proof applying Lemma 2. To this end, notice that inequality (5) yields (12), since $\lambda_{k+1}\theta_{k+1}\leq(1+\theta_{k})\lambda_{k}$. This completes the proof. ∎

First of all, we note that using the stricter inequality $\lambda_{k}\leq\sqrt{1+\frac{\theta_{k-1}}{2}}\lambda_{k-1}$ does not change the statement of Theorem 1. Hence, $x^{k}\to x^{*}$ and there exist $\mu,L>0$ such that $f$ is $\mu$-strongly convex and $\nabla f$ is $L$-Lipschitz on $\mathcal{C}=\operatorname{\overline{conv}}\{x^{*},x^{0},x^{1},\dots\}$. Secondly, due to local strong convexity, $\|\nabla f(x^{k})-\nabla f(x^{k-1})\|\geq\mu\|x^{k}-x^{k-1}\|$, and hence $\lambda_{k}\leq\frac{1}{2\mu}$ for $k\geq 1$.

Now we tighten some steps in the analysis to improve bound (6). By strong convexity,

By $L$-smoothness and bound $\lambda_{k}\leq\frac{1}{2\mu}$,

We keep inequality (2.2) and the rest of the proof as is. Then the strengthen analog of (5) will be

where in the last inequality we used our new condition on $\lambda_{k}$. Under the new update we have contraction in every term: $1-\frac{\lambda_{k}\mu}{2}$ in the first, $\frac{1}{1+2\mu/L}=1-\frac{2\mu}{L+2\mu}$ in the second and $\frac{1+\theta_{k-1}/2}{1+\theta_{k-1}}=1-\frac{\theta_{k-1}}{2(1+\theta_{k-1})}$ in the last one.

Using simple bounds $\frac{\lambda_{k}\mu}{2}\geq\frac{1}{4\kappa}$, $\frac{2\mu}{L+2\mu}=\frac{2}{\kappa+2}\geq\frac{1}{4\kappa}$, and $\frac{1}{2(\kappa+1)}\geq\frac{1}{4\kappa}$, we obtain $\Psi^{k+1}\leq(1-\frac{1}{4\kappa})\Psi^{k}$ for $k>2$. This gives $\mathcal{O}\left(\kappa\log\frac{1}{\varepsilon}\right)$ convergence rate. ∎

Extensions

One may wonder how flexible the update for $\lambda_{k}$ in Algorithm 1 is? For example, is it necessary to upper bound the stepsize with $\sqrt{1+\theta_{k}}\lambda_{k-1}$ and put $2$ in the denominator of $\frac{\|x^{k}-x^{k-1}\|}{2\|\nabla f(x^{k})-\nabla f(x^{k-1})\|}$? Algorithm 4 that we present here partially answers this question.

Obviously, Algorithm 1 is a particular case of Algorithm 4 with $\alpha=\frac{1}{2}$ and $\beta=1$.

and $D$ is a constant that explicitly depends on the initial data and the solution set.

Let $x^{*}$ be arbitrary solution of (1). We note that equations (7) and (2.2) hold for any variant of GD, independently of $\lambda_{k}$, $\alpha$, $\beta$. With the new rule for $\lambda_{k}$, from (2.2) it follows

which, after multiplication by $\beta$ and reshuffling the terms, becomes

Adding (7) and the latter inequality gives us

Notice that by $\beta=\frac{1}{2(1-\alpha)}$, we have $2\beta-\alpha\beta-1=\alpha\beta$ and hence,

As a sanity check, we can see that with $\alpha=\frac{1}{2}$ and $\beta=1$, the above inequality coincides with (5).

Note that because of the way we defined stepsize, $\lambda_{i}(1+\theta_{i}\beta)-\lambda_{i+1}\theta_{i+1}\beta\geq 0$. Thus, the sequence $(x^{k})$ is bounded. Since $\nabla f$ is locally Lipschitz, it is Lipschitz continuous on bounded sets. Let $L$ be a Lipschitz constant of $\nabla f$ on a bounded set $\mathcal{C}=\operatorname{\overline{conv}}\{x^{*},x^{1},x^{2},\dots\}$.

If $\alpha\leq\frac{1}{2}$, then $\frac{1}{\beta}>1$ and similarly to Theorem 1 we might conclude that $\lambda_{k}\geq\frac{\alpha}{L}$ for all $k$. However, for the case $\alpha>\frac{1}{2}$ we cannot do this. Instead, we prove that $\lambda_{k}\geq\frac{2\alpha(1-\alpha)}{L}$, which suffices for our purposes.

Let us prove that $\lambda_{k},\dotsc,\lambda_{k+j-1}\geq\frac{2\alpha(1-\alpha)}{L}$. The definition of $j$ yields $\theta_{k+i}=\sqrt{\frac{1}{\beta}+\theta_{k+i-1}}$ for all $i=0,\dots,j-1$. Recall that $\beta>1$, and thus,

for all $i<j$. Now it remains to notice that for any $i<j$

and hence $\lambda_{k+i}\geq 2(1-\alpha)\lambda_{k-1}\geq\frac{2\alpha(1-\alpha)}{L}$. If $j\leq m+n$, then at $(k+j)$-th iteration the second bound is active, i.e., $\lambda_{k+j}\geq\frac{\alpha}{L}$, and we are done with the other claim as well. Otherwise, note

so $\theta_{k+m}=\sqrt{\frac{1}{\beta}+\theta_{k+m-1}}\geq\sqrt{\frac{1}{\beta}+1-\frac{1}{2\beta}}=\sqrt{1+\frac{1}{2\beta}}$ and for any $i\in[m,j-2]$ we have $\theta_{k+i+1}=\sqrt{\frac{1}{\beta}+\theta_{k+i}}\geq\sqrt{\frac{1}{\beta}+1}$. Thus,

To conclude, in both cases $\alpha\leq\frac{1}{2}$ and $\alpha>\frac{1}{2}$, we have $S_{k}=\Omega(k)$.

Applying the Jensen inequality for the sum of all terms $f(x^{i})-f_{*}$ in the left-hand side of (7.1), we obtain

where $\hat{x}^{k}$ is defined in the statement of the theorem. Finally, convergence of $(x^{k})$ can be proved in a similar way as Theorem 1. ∎

2 f𝑓f is L𝐿L-smooth

Often, it is known that $f$ is smooth and even some estimate for the Lipschitz constant $L$ of $\nabla f$ is available. In this case, we can use slightly larger steps, since instead of just convexity the stronger inequality in Lemma 3 holds. To take advantage of it, we present a modified version of Algorithm 1 in Algorithm 5. Note that we have chosen to modify Algorithm 1 and not its more general variant Algorithm 4 only for simplicity.

Let $f$ be convex and $L$-smooth. Then for $(x^{k})$ generated by Algorithm 5 inequality (5) holds. As a corollary, it holds for some ergodic vector $\hat{x}^{k}$ that $f(\hat{x}^{k})-f_{*}=\mathcal{O}\left(\frac{1}{k}\right)$.

Proceeding similarly as in Lemma 1, we have

Again, instead of using merely convexity of $f$, we combine it with Lemma 3. This gives

Since now we have two additional terms $\frac{1}{\lambda_{k}L}\|x^{k+1}-x^{k}\|^{2}$ and $\frac{\lambda_{k}\theta_{k}}{L}\|\nabla f(x^{k})-\nabla f(x^{k-1})\|^{2}$, we can do better than (2.2). But first we need a simple, yet a bit tedious fact. By our choice of $\lambda_{k}$, in every iteration $\lambda_{k}\leq\frac{1}{\lambda_{k-1}L^{2}}+\frac{1}{2L_{k}}$ with $L_{k}=\frac{\|\nabla f(x^{k})-\nabla f(x^{k-1})\|}{\|x^{k}-x^{k-1}\|}$. We want to show that it implies

which is equivalent to $\lambda_{k}-\frac{\sqrt{\lambda_{k}}}{\sqrt{\lambda_{k-1}}L}-\frac{1}{2L_{k}}\leq 0$. Nonnegative solutions of the quadratic inequality $t^{2}-\frac{t}{\sqrt{\lambda_{k-1}}L}-\frac{1}{2L_{k}}\leq 0$ are

Let us prove that $\sqrt{\frac{1}{\lambda_{k-1}L^{2}}+\frac{1}{2L_{k}}}$ falls into this segment and, hence, $\sqrt{\lambda_{k}}$ does as well. Using a simple inequality $4+a\leq(1+\sqrt{1+a})^{2}$, for $a>0$, we obtain

This confirms that (22) is true. Thus, by Cauchy-Schwarz and Young’s inequalities, one has

Combining everything together, we obtain the statement of the theorem. ∎

Stochastic analysis

Consider the following version of SGD, in which we have two samples at each iteration, $\xi^{k}$ and $\zeta^{k}$ to compute

As before, we assume that $\theta_{0}=+\infty$, so $\lambda_{1}=\frac{\alpha\|x^{1}-x^{0}\|}{\|\nabla f_{\zeta^{1}}(x^{1})-\nabla f_{\zeta^{1}}(x^{0})\|}$.

Let $f_{\xi}$ be $L$-smooth $\mu$-strongly convex almost surely. It holds for $\lambda_{k}$ produced by the rule above

Let us start with the upper bound. Strong convexity of $f_{\zeta^{k}}$ implies that $\|x-y\|\leq\frac{1}{\mu}\|\nabla f_{\zeta^{k}}(x)-\nabla f_{\zeta^{k}}(y)\|$ for any $x,y$. Therefore, $\lambda_{k}\leq\min\left\{\sqrt{1+\theta_{k}}\lambda_{k-1},\alpha/\mu\right\}\leq\alpha/\mu$ a.s.

On the other hand, $L$-smoothness gives $\lambda_{k}\geq\min\left\{\sqrt{1+\theta_{k}}\lambda_{k-1},\alpha/L\right\}\geq\min\left\{\lambda_{k-1},\alpha/L\right\}$ a.s. Iterating this inequality, we obtain the stated lower bound. ∎

Another fact that we will use is a strong convexity bound, which states for any $x,y$

Let $f_{\xi}$ be $L$-smooth and $\mu$-strongly convex almost surely. If we choose some $\alpha\leq\frac{\mu}{2L}$, then

Therefore, if we subtract $\alpha\frac{\sigma^{2}}{\mu^{2}}$ from both sides, we obtain

2 Same sample: overparameterized models

Assume additionally that the model is overparameterized, i.e., $\nabla f_{\xi}(x^{*})=0$ with probability one. In that case, we can prove that one can use the same stochastic sample to compute the stepsize and to move the iterate. The update becomes

Let $f_{\xi}$ be $L$-smooth, $\mu$-strongly convex and satisfy $\nabla f_{\xi}(x^{*})=0$ with probability one. If we choose $\alpha\leq\frac{\mu}{L}$, then

Now $\lambda_{k}$ depends on $\xi^{k}$, so we do not have an unbiased update anymore. However, under the new assumption, $\nabla f_{\xi^{k}}(x^{*})=0$, so we can write

In addition, $L$-smoothness and convexity of $f_{\xi^{k}}$ give

Since our choice of $\alpha$ implies $\lambda_{k}\leq\frac{1}{L}$, we conclude that

Experiments details

Here we provide some omitted details of the experiments with neural networks. We took the implementation of neural networks from a publicly available repositoryhttps://github.com/kuangliu/pytorch-cifar/blob/master/models/resnet.py. All methods were run with standard data augmentation and no weight decay. The confidence intervals for ResNet-18 are obtained from 5 different random seeds and for DenseNet-121 from 3 seeds.

In our ResNet-18 experiments, we used the default parameters for Adam. SGD was used with a stepsize divided by 10 at epochs 120 and 160 when the loss plateaus. Log grid search with a factor of 2 was used to tune the initial stepsize of SGD and the best initial value was 0.2. Tuning was done by running SGD 3 times and comparing the average of test accuracies over the runs at epoch 200. For the momentum version (SGDm) we used the standard values of momentum and initial stepsize for training residual networks, 0.9 and 0.1 correspondingly. We used the same parameters for DenseNet-121 without extra tuning.

For our method we used the variant of SGD $x^{k+1}=x^{k}-\lambda_{k}\nabla f_{\xi^{k}}(x^{k})$ with $\lambda_{k}$ computed using $\xi^{k}$ as well (biased option). We did not test stepsizes that use values other than $\frac{1}{L_{k}}$ and $\frac{1}{2L_{k}}$, so it is possible that other options will perform better. Moreover, the coefficient before $\theta_{k-1}$ might be suboptimal too.