Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity

## Abstract

Abstract Due to the non-smoothness of optimization problems in Machine Learning, generalized smoothness assumptions have gained much attention in recent years. One of the most popular assumptions of this type is ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -smoothness ( Zhang et al., 2020b, ) . In this paper, we focus on the class of (strongly) convex ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -smooth functions and derive new convergence guarantees for several existing methods. In particular, we derive improved convergence rates for Gradient Descent with (Smoothed) Gradient Clipping and for Gradient Descent with Polyak Stepsizes. In contrast to the existing results, our rates do not rely on the standard smoothness assumption and do not suffer from the exponential dependency from the initial distance to the solution. We also extend these results to the stochastic case under the over-parameterization assumption, propose a new accelerated method for convex ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -smooth optimization, and derive new convergence rates for Adaptive Gradient Descent (Malitsky and Mishchenko,, 2020 ) .

## 1 Introduction

Modern optimization problems arising in Machine Learning (ML) and Deep Learning (DL) are typically non-smooth, i.e., the gradient of the objective function is not necessarily Lipschitz continuous. In particular, the gradient of the standard $\ell_{2}$-regression loss computed for simple networks is not Lipschitz continuous (). Moreover, the methods that are designed to benefit from the smoothness of the objective often perform poorly in Deep Learning, where problems are non-smooth. For example, variance-reduced methods are known to be faster in theory (for finite sums of smooth functions) but are outperformed by slower theoretically non-variance-reduced methods (Defazio and Bottou,, ). All of these reasons motivate researchers to consider different assumptions to replace the standard smoothness assumption.

One such assumption is *$(L_{0},L_{1})$-smoothness* originally introduced by for twice differentiable functions. This assumption allows the norm of the Hessian of the objective to increase linearly with the growth of the norm of the gradient. In particular, $(L_{0},L_{1})$-smoothness can hold even for functions with polynomially growing gradients – a typical behavior for DL problems. Moreover, the notion of $(L_{0},L_{1})$-smoothness can also be extended to the class of differentiable but not necessarily twice differentiable functions (Chen et al.,, ).

Although focus on the non-convex problems as well as more recent works such as (; Zhao et al.,, ; Faw et al.,, ; Wang et al.,, ; ; Chen et al.,, ; Hübler et al.,, ), the class of $(L_{0},L_{1})$-smooth *convex*(^1^11Although many existing problems are not convex, it is useful to understand methods behavior under the convexity assumption as well due to several reasons. First of all, since the class of non-convex functions is too broad, the existing results for this class are quite pessimistic. In particular, among first-order methods, Gradient Descent is the best first-order method if only smoothness is assumed (Carmon et al.,, ). In contrast, while accelerated/momentum methods do not have theoretical advantages over Gradient Descent for non-convex problems and shine in theory only under convexity-like assumptions, they work better in practice even when the problems are not convex (Sutskever et al.,, ). Last but not least, several recent works show that some problems appearing in Deep Learning, Optimal Control, and Reinforcement Learning have properties akin to (strongly) convex functions (Liu et al.,, ) and are even hiddenly convex (Fatkhullin et al.,, ).) function is much weaker explored. In particular, the existing convergence results for the methods such as Gradient Descent with Clipping (Pascanu et al.,, ) and Gradient Descent with Polyak Stepsizes (Polyak,, ) applied to $(L_{0},L_{1})$-smooth convex problems either rely on additional smoothness assumption (Koloskova et al.,, ; Takezawa et al.,, ) or require (potentially) small stepsizes to ensure that the method stays in the compact set where the gradient is bounded and, as a consequence of $(L_{0},L_{1})$-smoothness of the objective, Lipschitz continuous (). This leads us to the following natural question:

$$ How the convergence bounds for different versions of Gradient Descent depend on $L_{0}$ and $L_{1}$ when the objective function is convex, $(L_{0},L_{1})$ -smooth but not necessarily $L$ -smooth? $$

In this paper, we address the above question for Gradient Descent with Smoothed Gradient Clipping, Polyak Stepsizes, Similar Triangles Method (Gasnikov and Nesterov,, ), and Adaptive Gradient Descent (Malitsky and Mishchenko,, ): *for each of the mentioned methods, we either improve the existing convergence results or derive the first convergence results under $(L_{0},L_{1})$-smoothness. We also derive new results for the stochastic versions of Gradient Descent with Smoothed Gradient Clipping and Polyak Stepsizes.*

### 1.1 Problem Setup

Before we continue the discussion of the related work and our results, we need to formalize the problem setup. That is, we consider the unconstrained minimization problem

$$ $\min\limits_{x\in\mathbb{R}^{d}}f(x),$ (1) $$

where $f:\mathbb{R}^{d}\to\mathbb{R}$ is a (strongly) convex differentiable function.

###### Assumption 1.1 (Convexity) .

Function $f:\mathbb{R}^{d}\to\mathbb{R}$ is $\mu$-strongly convex with(^2^22In this paper, we consider standard $\ell_{2}$-norm for vectors and spectral norm for matrices.) $\mu\geqslant 0$:

$$ $f(y)\geqslant f(x)+\langle\nabla f(x),y-x\rangle+\frac{\mu}{2}\|x-y\|^{2}, \quad\forall x,y\in\mathbb{R}^{d}.$ (2) $$

As we already mentioned earlier, in addition to convexity, we assume that the objective function is $(L_{0},L_{1})$-smooth. Following Chen et al., (), we consider two types of $(L_{0},L_{1})$-smoothness.

###### Assumption 1.2 (Asymmetric $(L_{0},L_{1})$ -smoothness) .

Function $f:\mathbb{R}^{d}\to\mathbb{R}$ is asymmetrically $(L_{0},L_{1})$-smooth ($f\in{\cal L}_{\text{asym}}(L_{0},L_{1})$), i.e., for all $x,y\in\mathbb{R}^{d}$ we have

$$ $\|\nabla f(x)-\nabla f(y)\|\leqslant\left(L_{0}+L_{1}\|\nabla f(y)\|\right)\|x -y\|.$ (3) $$

###### Assumption 1.3 (Symmetric $(L_{0},L_{1})$ -smoothness) .

Function $f:\mathbb{R}^{d}\to\mathbb{R}$ is symmetrically $(L_{0},L_{1})$-smooth ($f\in{\cal L}_{\text{sym}}(L_{0},L_{1})$), i.e., for all $x,y\in\mathbb{R}^{d}$ we have

$$ $\|\nabla f(x)-\nabla f(y)\|\leqslant\left(L_{0}+L_{1}\sup\limits_{u\in[x,y]}\| \nabla f(u)\|\right)\|x-y\|.$ (4) $$

Clearly, Assumption 1.3 is more general than Assumtpion 1.2. Due to this reason, we will mostly focus on Assumption 1.3, and by $(L_{0},L_{1})$-smooth functions, we will mean functions satisfying Assumption 1.3 if the opposite is not specified. Nevertheless, it is worth mentioning that asymmetric $(L_{0},L_{1})$-smoothness (under some extra assumptions) is satisfied for a certain problem formulation appearing in Distributionally Robust Optimization (Jin et al.,, ). Chen et al., () also show that exponential function satisfies (4), and, more generally, for twice differentiable functions Assumption 1.3 is equivalent to

$$ $\|\nabla^{2}f(x)\|_{2}\leqslant L_{0}+L_{1}\|\nabla f(x)\|,\quad\forall x\in \mathbb{R}^{d}.$ (5) $$

Moreover, below, we provide some examples of functions satisfying Assumption 1.3 but either not satisfying standard $L$-smoothness, i.e., (4) with $L_{1}=0$, or satisfying $L$-smoothness with larger constants than $L_{0}$ and $L_{1}$ respectively. For the detailed proofs for these examples, we refer the reader to Appendix A.

###### Example 1.4 (Power of Norm) .

Let $f(x)=\|x\|^{2n}$, where $n$ is a positive integer. Then, $f(x)$ is convex and $(2n,2n-1)$-smooth. Moreover, $f(x)$ is not $L$-smooth for $n\geqslant 2$ and any $L\geqslant 0$.

###### Example 1.5 (Exponent of the Inner Product) .

Function $f(x)=\exp(a^{\top}x)$ for some $a\in\mathbb{R}^{d}$ is convex, $(0,\|a\|)$-smooth, but not $L$-smooth for $a\neq 0$ and any $L\geqslant 0$.

These two examples illustrate that $(L_{0},L_{1})$-smoothness is quite a mild assumption, and it is strictly weaker than $L$-smoothness. However, the next example shows that even when $L$-smoothness holds, it makes sense to consider $(L_{0},L_{1})$-smoothness as well.

###### Example 1.6 (Logistic Function) .

Consider logistic function with $\ell_{2}$-regularization: $f(x)=\log\left(1+\exp(-a^{\top}x)\right)$, where $a\in\mathbb{R}^{d}$ is some vector. It is known that this function is $L$-smooth and convex with $L=\|a\|^{2}$. However, one can show that $f$ is also $(L_{0},L_{1})$-smooth with $L_{0}=0$ and $L_{1}=\|a\|$. For $\|a\|\gg 1$, both $L_{0}$ and $L_{1}$ are much smaller than $L$.

It is worth noticing that in contrast to $L$-smooth case, the sum of two $(L_{0},L_{1})$-smooth functions is not necessarily $(2L_{0},2L_{1})$-smooth and depends on the structure of the functions.

###### Assumption 1.1 (Convexity) .

###### Assumption 1.2 (Asymmetric ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -smoothness) .

###### Assumption 1.3 (Symmetric ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -smoothness) .

###### Example 1.4 (Power of Norm) .

###### Example 1.5 (Exponent of the Inner Product) .

###### Example 1.6 (Logistic Function) .

### 1.2 Related Works

#### Results in the non-convex case.

introduce $(L_{0},L_{1})$-smoothness in the form (5) and show that Clipped Gradient Descent (Clip-GD) has iteration complexity ${\cal O}\left(\max\left\{\nicefrac{{L_{0}\Delta}}{{\varepsilon^{2}}},\nicefrac
{{(1+L_{1}^{2})\Delta}}{{L_{0}}}\right\}\right)$ with $\Delta:=f(x^{0})-\inf_{x\in\mathbb{R}^{d}}f(x)$ for finding $\varepsilon$-approximate first-order stationary point of $(L_{0},L_{1})$-smooth function. The asymptotically dominant term in this complexity ${\cal O}\left(\nicefrac{{L_{0}\Delta}}{{\varepsilon^{2}}}\right)$ is independent of $L_{1}$, and thus, this term can be much smaller than ${\cal O}\left(\nicefrac{{L\Delta}}{{\varepsilon^{2}}}\right)$, where $L$ is a Lipschitz constant of the gradient (if finite). Under the assumption that $M:=\sup\{\|\nabla f(x)\|\mid x\in\mathbb{R}^{d}\text{ such that }f(x)\leqslant
f
(x^{0})\}<+\infty$ also show that GD with stepsize $\Theta\left(\nicefrac{{1}}{{(L_{0}+ML_{1})}}\right)$ has complexity ${\cal O}\left(\nicefrac{{(L_{0}+ML_{1})\Delta}}{{\varepsilon^{2}}}\right)$, which is natural to expect since on $\{x\in\mathbb{R}^{d}\mid f(x)\leqslant f(x^{0})\}$ the norm of the Hessian is bounded as $L_{0}+ML_{1}$ (see (5)), i.e., function is $(L_{0}+ML_{1})$-smooth. generalize the results from () to the method with heavy-ball momentum (Polyak,, ) and clipping of both momentum and gradient. Similar results are derived for Normalized GD (Zhao et al.,, ; Chen et al.,, ), SignGD (Crawshaw et al.,, ), AdaGrad-Norm/AdaGrad (Faw et al.,, ; Wang et al.,, ), Adam (Wang et al.,, ; ), and Normalized GD with Momentum (Hübler et al.,, ). It is also worth mentioning that all of the mentioned papers in this paragraph consider stochastic versions of the methods as well.

#### Results in the convex case.

To the best of our knowledge, convex $(L_{0},L_{1})$-smooth optimization is studied in three papers (Koloskova et al.,, ; Takezawa et al.,, ; ). In particular, under convexity, $L$-smoothness, and $(L_{0},L_{1})$-smoothness, Koloskova et al., () show that Clip-GD with clipping level $c$ has ${\cal O}\left(\max\left\{\nicefrac{{(L_{0}+cL_{1})R_{0}^{2}}}{{\varepsilon}},
\sqrt{\nicefrac{{R_{0}^{4}L(L_{0}+cL_{1})^{2}}}{{c^{2}\varepsilon}}}\right\}\right)$ complexity of finding $\varepsilon$-solution, i.e., $x$ such that $f(x)-f(x^{*})\leqslant\varepsilon$, where $x^{*}\in\arg\min_{x\in\mathbb{R}^{d}}f(x)$ and $R_{0}:=\|x^{0}-x^{*}\|$. In particular, if $c\sim\nicefrac{{L_{0}}}{{L_{1}}}$, then the asymptotically dominant term in the complexity is ${\cal O}\left(\nicefrac{{L_{0}R_{0}^{2}}}{{\varepsilon}}\right)$, i.e., it is independent of $L_{1}$ and $L$, which can be significantly better than the complexity of GD of ${\cal O}\left(\nicefrac{{LR_{0}^{2}}}{{\varepsilon}}\right)$ for convex $L$-smooth functions. In the same setting, Takezawa et al., () prove ${\cal O}\left(\max\left\{\nicefrac{{L_{0}R_{0}^{2}}}{{\varepsilon}},\sqrt{
\nicefrac{{R_{0}^{4}LL_{1}^{2}}}{{\varepsilon}}}\right\}\right)$ complexity bound for GD with Polyak Stepsizes (GD-PS). Finally, under convexity and $(L_{0},L_{1})$-smoothness show that for sufficiently small stepsizes standard GD and Nesterov’s method (NAG) (Nesterov,, ) have complexities ${\cal O}\left(\nicefrac{{\ell R_{0}^{2}}}{{\varepsilon}}\right)$ and ${\cal O}\left(\sqrt{\nicefrac{{\ell R_{0}^{2}}}{{\varepsilon}}}\right)$ respectively, where $\ell:=L_{0}+L_{1}G$ and $G$ is some constant depending on $L_{0},L_{1},R_{0},\|\nabla f(x^{0})\|$, and $f(x^{0})-f(x^{*})$. In particular, constant $G$ and stepsizes are chosen in such a way that it is possible to show via induction that in all points generated by GD/NAG and where $(L_{0},L_{1})$-smoothness is used the norm of the gradient is bounded by $G$. However, these results have a common limitation: constants $L$ (if finite) and $\ell$ can be much larger than $L_{0}$ and $L_{1}$. Moreover, for Clip-GD and GD-PS, these results lead to a natural question of whether it is possible to achieve ${\cal O}\left(\nicefrac{{LR_{0}^{2}}}{{\varepsilon}}\right)$ complexity without $L$-smoothness non-asymptotically.

#### Gradient clipping.

As follows from the above discussion, gradient clipping is a useful tool for handling possible non-smoothness of the objective, which is also confirmed in practice (Goodfellow et al.,, ). However, it is worth mentioning that clipping has also other applications. In particular, gradient clipping is used to handle heavy-tailed noise (; Gorbunov et al.,, ; Cutkosky and Mehta,, ), to achieve differentiable privacy (Abadi et al.,, ; Chen et al.,, ), and also to tolerate Byzantine attacks (Karimireddy et al.,, ; Malinovsky et al.,, ).

#### Polyak Stepsizes.

GD with Polyak Stepsizes (GD-PS) is a celebrated approach for making GD parameter-free (under the assumption that $f(x^{*})$ is known) (Polyak,, ). In particular, Hazan and Kakade, () show that GD-PS achieves the same rate as GD with optimally chosen constant stepsize (up to a constant factor) for convex Lipschitz functions, convex smooth functions, and strongly convex smooth functions. Moreover, some recent works (Loizou et al.,, ; Galli et al.,, ; Berrada et al.,, ; Horváth et al.,, ; Abdukhakimov et al.,, ) also consider different stochastic extensions of GD-PS.

#### Other notions of generalized smoothness.

$(L_{0},L_{1})$-smoothness belongs to the class of assumptions on so-called generalized smoothness. Classical assumptions of this type include Hölder continuity of the gradient (Nemirovski and Yudin,, ; Nemirovskii and Nesterov,, ), relative smoothness (Bauschke et al.,, ), and local smoothness, i.e., Lipschitzness of the gradient on any compact (Malitsky and Mishchenko,, ; Patel and Berahas,, ; Patel et al.,, ; Gorbunov et al.,, ; Sadiev et al.,, ). Although these assumptions are quite broad (e.g., for local smoothness, it is sufficient to assume just continuity of the gradient), they do not relate the growth of non-smoothness/local Lipschitz constant of the gradient with the growth of the gradient or distance to the solution. From this perspective, assumptions such as polynomial growth of the gradient norm (Mai and Johansson,, ), $\alpha$-symmetric $(L_{0},L_{1})$-smoothness (Chen et al.,, ), and $(r,\ell)$-smoothness () are closer to Assumption 1.3 than local Lipschitz/Hölder continuity of the gradient and relative smoothness.

### 1.3 Our Contribution

- •
Tighter rates for Gradient Descent with (Smoothed) Clipping. We prove that Gradient Descent with (Smoothed) Clipping, which we call $(L_{0},L_{1})$-GD, has ${\cal O}\left(\max\left\{\nicefrac{{L_{0}R_{0}^{2}}}{{\varepsilon}},L_{1}^{2}R
_{0}^{2}\right\}\right)$ worst-case complexity of finding $\varepsilon$-solution for convex $(L_{0},L_{1})$-smooth functions. In contrast to the previous results (Koloskova et al.,, ; ), our bound is derived without $L$-smoothness assumption and does not depend on any bound for $\|\nabla f(x^{k})\|$. To achieve this, we prove that $(L_{0},L_{1})$-GD has non-increasing gradient norm and show that the method’s behavior consists of two phases: initial (and finite) phase when $\|\nabla f(x^{k})\|\geqslant\nicefrac{{L_{0}}}{{L_{1}}}$ (large gradient), and final phase when $\|\nabla f(x^{k})\|<\nicefrac{{L_{0}}}{{L_{1}}}$ and the method behaves similarly to GD applied to $2L_{0}$-smooth problem. We also extend the result to the strongly convex case and to the stochastic convex case.
- •
Tighter rates for Gradient Descent with Polyak Stepsizes. For GD-PS, we also derive ${\cal O}\left(\max\left\{\nicefrac{{L_{0}R_{0}^{2}}}{{\varepsilon}},L_{1}^{2}R
_{0}^{2}\right\}\right)$ worst-case complexity of finding $\varepsilon$-solution for convex $(L_{0},L_{1})$-smooth functions. In contrast to the existing result (Takezawa et al.,, ), our bound is derived without $L$-smoothness assumption. We also extend the result to the strongly convex case and to the stochastic convex case.
- •
New accelerated method: $(L_{0},L_{1})$-Similar Triangles Method. We propose a version of Similar Triangles Method (Gasnikov and Nesterov,, ) for convex $(L_{0},L_{1})$-smooth optimization, and prove ${\cal O}\left(\sqrt{\nicefrac{{L_{0}(1+L_{1}R_{0}\exp(L_{1}R_{0}))R_{0}^{2}}}{
{\varepsilon}}}\right)$ complexity of finding $\varepsilon$-solution for convex $(L_{0},L_{1})$-smooth functions. In contrast to the accelerated result from (), our bound is derived without the usage of stepsizes depending on $R_{0}$ and $f(x^{0})-f(x^{*})$.
- •
New convergence results for Adaptive Gradient Descent. We also show new convergence result for Adaptive Gradient Descent (Malitsky and Mishchenko,, ) for convex $(L_{0},L_{1})$-smooth problems: we prove ${\cal O}\left(\max\left\{\nicefrac{{L_{0}\exp(L_{1}D)D^{2}}}{{\varepsilon}},m^
{2}L_{1}^{2}\exp(L_{1}D)D^{2}\right\}\right)$ complexity of finding $\varepsilon$-solution, where $D$ is a constant depending on initial suboptimality of the starting point, and $m$ is a logarithmic factor depending on $L_{1}$ and $D$. We also extend the result to the strongly convex case.
- •
New technical results for $(L_{0},L_{1})$-smooth functions. We derive several useful inequalities for the class of (convex) $(L_{0},L_{1})$-smooth functions.

## 2 Technical Lemmas

In this section, we provide some useful facts about $(L_{0},L_{1})$-smooth functions. We start with the following result from (Chen et al.,, ).

###### Lemma 2.1 (Proposition 3.2 from (Chen et al.,, 2023 ) ) .

Assumption 1.3 holds if and only if for

$$ $\|\nabla f(x)-\nabla f(y)\|\leqslant\left(L_{0}+L_{1}\|\nabla f(y)\|\right) \exp\left(L_{1}\|x-y\|\right)\|x-y\|,\quad\forall x,y\in\mathbb{R}^{d}.$ (6) $$

Moreover, Assumption 1.3 implies for all $x,y\in\mathbb{R}^{d}$

$$ $f(y)\leqslant f(x)+\langle\nabla f(x),y-x\rangle+\frac{L_{0}+L_{1}\|\nabla f(x )\|}{2}\exp(L_{1}\|x-y\|)\|x-y\|^{2}.$ (7) $$

Inequality (6) removes the supremum from (4), but the price for this is a factor of $\exp(L_{1}\|x-y\|)$. When $\|x-y\|\leqslant\nicefrac{{1}}{{L_{1}}}$, this factor is upper-bounded as $e$. However, in general, it cannot be removed since (6) is equivalent to (4). Inequality (7) can be seen as a generalization of standard quadratic upper-bound for $L$-smooth functions (Nesterov,, ) to the class of $(L_{0},L_{1})$-smooth functions.

Using the above lemma, we derive several useful inequalities that we actively use throughout our proofs. Most of these inequalities can be further simplified in the case of Assumption 1.2.

###### Lemma 2.2 .

Let Assumption 1.3 hold and $\nu$ satisfy(^3^33One can check numerically that $0.56<\nu<0.57$.) $\nu=e^{-\nu}$. Then, the following statements hold.

- 1.
For $f_{*}:=\inf_{x\in\mathbb{R}^{d}}f(x)$ and arbitrary $x\in\mathbb{R}^{d}$, we have
$\frac{\nu\|\nabla f(x)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(x)\|)}\leqslant f(x)-f_{
*}.$
(8)
- 2.
If additionally Assumption 1.1 holds with $\mu=0$, then for any $x,y\in\mathbb{R}^{d}$ such that
$L_{1}\|x-y\|\exp{\left(L_{1}\|x-y\|\right)}\leqslant 1,$
(9)
we have
$\frac{\nu\|\nabla f(x)-\nabla f(y)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(y)\|)}
\leqslant f(y)-f(x)-\langle\nabla f(x),y-x\rangle,$
(10)
and
$\frac{\nu\|\nabla f(x)-\nabla f(y)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(y)\|)}+\frac
{\nu\|\nabla f(x)-\nabla f(y)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(x)\|)}\leqslant
\langle\nabla f(x)-\nabla f(y),x-y\rangle.$
(11)

This lemma provides us with a set of useful inequalities that can be viewed as generalizations of analogous inequalities that hold for smooth (convex) functions. We provide the complete proof in Appendix B. Moreover, when Assumption 1.2 holds, all inequalities from Lemma 2.2 hold with $\nu=1$, and requirement (9) is not needed for (10) and (11) to hold. An analog of (8) for a local version of $(L_{0},L_{1})$-smoothness can be found in (Koloskova et al.,, ). We also refer to () for an analog of inequality (11) for $(r,\ell)$-smooth functions.

###### Lemma 2.1 (Proposition 3.2 from (Chen et al.,, 2023 ) ) .

###### Lemma 2.2 .

## 3 Smoothed Gradient Clipping

The first method that we consider is closely related to Clip-GD and can be seen as a smoothed version(^4^44Indeed, when $\|\nabla f(x^{k})\|<\nicefrac{{L_{0}}}{{L_{1}}}$, the denominator of the stepsize in $(L_{0},L_{1})$-GD lies in $[L_{0},2L_{0}]$, and when $\|\nabla f(x^{k})\|\geqslant\nicefrac{{L_{0}}}{{L_{1}}}$, this denominator lies in $[L_{1}\|\nabla f(x^{k})\|,2L_{1}\|\nabla f(x^{k})\|]$. Such a behavior is very similar to the behavior of Clip-GD with clipping level $\nicefrac{{L_{0}}}{{L_{1}}}$ and stepsize $\nicefrac{{\eta}}{{L_{0}}}$.) of it – see Algorithm 1. Alternatively, this method can be seen as a version of Gradient Descent designed for $(L_{0},L_{1})$-smooth functions. Therefore, we call this algorithm $(L_{0},L_{1})$-GD.

Figure: Algorithm 1 $(L_{0},L_{1})$-Gradient Descent ($(L_{0},L_{1})$-GD)

Similarly to standard GD, $(L_{0},L_{1})$-GD satisfies two useful properties, summarized below.

###### Lemma 3.1 (Monotonicity of function value) .

Let Assumption 1.3 hold. Then, for all $k\geqslant 0$ the iterates generated by $(L_{0},L_{1})$-GD with $\eta\leqslant\nu$, $\nu=e^{-\nu}$ satisfy

$$ $f(x^{k+1})\leqslant f(x^{k})-\frac{\eta\|\nabla f(x^{k})\|^{2}}{2(L_{0}+L_{1} \|\nabla f(x^{k})\|)}\leqslant f(x^{k}).$ (12) $$

###### Proof sketch.

The inequality follows from (7) applied to $y=x^{k+1}$ and $x=x^{k}$, see the complete proof in Appendix C.
∎

###### Lemma 3.2 (Monotonicity of gradient norm) .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. Then, for all $k\geqslant 0$ the iterates generated by $(L_{0},L_{1})$-GD with $\eta\leqslant\nu$, $\nu=e^{-\nu}$ satisfy

$$ $\|\nabla f(x^{k+1})\|\leqslant\|\nabla f(x^{k})\|.$ (13) $$

###### Proof sketch.

The inequality follows from (11) applied to $x=x^{k+1}$ and $y=x^{k}$, see the complete proof in Appendix C.
∎

We notice that a similar result to Lemma 3.2 is shown in () for GD with sufficiently small stepsize. With these lemmas in hand, we derive the convergence result for $(L_{0},L_{1})$-GD.

###### Theorem 3.3 .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. Then, the iterates generated by $(L_{0},L_{1})$-GD with $0<\eta\leqslant\frac{\nu}{2}$, $\nu=e^{-\nu}$
satisfy the following implication:

$$ $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}\;\Longrightarrow\;k\leqslant \frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu\eta}-1~{}~{}\text{and}~{}~{}\|x^{k+1} -x^{*}\|^{2}\leqslant\|x^{k}-x^{*}\|^{2}-\frac{\nu\eta}{8L_{1}^{2}}.$ (14) $$

Moreover, the output after $N>\frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\eta}-1$ iterations satisfies

$$ $f(x^{N})-f(x^{*})\leqslant\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N+1-T)}-\frac{ \nu L_{0}T}{4L_{1}^{2}(N+1-T)}\leqslant\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N +1)},$ (15) $$

where $T:=|{\cal T}|$ for the set ${\cal T}:=\{k\in\{0,1,\ldots N-1\}\mid\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}
{L_{1}}\}$.
In addition, if $\mu>0$ and $N>\frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\eta}-1$, then

$$ $\|x^{N}-x^{*}\|^{2}\leqslant\left(1-\frac{\mu\eta}{4L_{0}}\right)^{N-T}\left( \|x^{0}-x^{*}\|^{2}-\frac{\nu\eta T}{8L_{1}^{2}}\right)\leqslant\left(1-\frac{ \mu\eta}{4L_{0}}\right)^{N-T}\|x^{0}-x^{*}\|^{2}.$ (16) $$

###### Proof sketch.

Similarly to the proofs from (Koloskova et al.,, ; Takezawa et al.,, ), our proof is based on careful consideration of two possible situations: either $\|\nabla f(x^{k})\|\geqslant\nicefrac{{L_{0}}}{{L_{1}}}$ or $\|\nabla f(x^{k})\|<\nicefrac{{L_{0}}}{{L_{1}}}$. When the first situation happens, the squared distance to the solution decreases by $\nicefrac{{\eta}}{{8L_{1}^{2}}}$. Since the squared distance is non-negative and non-increasing, this cannot happen more than $\nicefrac{{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}}{{\nu\eta}}$ times, which gives the first part of the result. Next, when $\|\nabla f(x^{k})\|<\nicefrac{{L_{0}}}{{L_{1}}}$, the method behaves as GD on convex $2L_{0}$-smooth problem and the analysis is also similar. Together with Lemmas 3.1 and 3.2, this gives the second part of the proof; see the complete proof in Appendix C.
∎

In the convex case ($\mu=0$), bound (15) implies that $(L_{0},L_{1})$-GD with $\eta=\nicefrac{{\nu}}{{2}}$ satisfies $f(x^{N})-f(x^{*})\leqslant\varepsilon$ after $N={\cal O}\left(\max\left\{\nicefrac{{L_{0}R_{0}^{2}}}{{\varepsilon}},L_{1}^{2
}R_{0}^{2}\right\}\right)$ iterations. In contrast, Koloskova et al., (); Takezawa et al., () derive ${\cal O}\left(\max\left\{\nicefrac{{L_{0}R_{0}^{2}}}{{\varepsilon}},\sqrt{
\nicefrac{{R_{0}^{4}LL_{1}^{2}}}{{\varepsilon}}}\right\}\right)$ complexity bound that depends on the smoothness constant $L$, which can be much larger than $L_{0}$ and $L_{1}$. For example, when $f(x)=\|x\|^{4}$ constant $L$ depends on the starting point (since it defines a compact set, where the method stays) as $L_{0}+L_{1}\|\nabla f(x^{0})\|={\cal O}(1+\|x^{0}\|^{3})$ (see Appendix A), while $L_{0}=4$ and $L_{1}=3$. This means that by moving $x^{0}$ away from the solution, one can make our bound arbitrarily better than the previous one, even for this simple example. Moreover, unlike the result from () for GD with small enough stepsize, our bound depends neither on $f(x^{0})-f(x^{*})$ nor on $\|\nabla f(x^{0})\|$ that can be significantly larger than $R_{0}$ (according to Lemma 2.1 – exponentially larger). Finally, we highlight that our analysis shows that $(L_{0},L_{1})$-GD exhibits a two-stage behavior: during the first stage, the gradient is large (this stage can be empty), and the squared distance to the solution decreases by a constant, and during the second stage, the method behaves as standard GD. This observation is novel on its own and gives a better understanding of the method’s behavior. In the strongly convex case, our convergence bound implies that $(L_{0},L_{1})$-GD with $\eta=\nicefrac{{\nu}}{{2}}$ satisfies $\|x^{N}-x^{*}\|^{2}\leqslant\varepsilon$ after $N={\cal O}\left(\max\left\{\nicefrac{{L_{0}\log(\nicefrac{{R_{0}^{2}}}{{
\varepsilon}})}}{{\mu}},L_{1}^{2}R_{0}^{2}\right\}\right)$ iterations, while the complexity of Clip-GD derived by Koloskova et al., () is ${\cal O}\left(\max\left\{\nicefrac{{L_{0}\log(\nicefrac{{R_{0}^{2}}}{{
\varepsilon}})}}{{\mu}},L_{0}R_{0}\min\left\{\sqrt{\nicefrac{{L}}{{\mu}}},LR_{
0}\right\}\right\}\right)$, which again can be arbitrarily worse than our bound due to the dependence on $L$.

###### Lemma 3.1 (Monotonicity of function value) .

###### Proof sketch.

###### Lemma 3.2 (Monotonicity of gradient norm) .

###### Proof sketch.

###### Theorem 3.3 .

###### Proof sketch.

## 4 Gradient Descent with Polyak Stepsizes

Next, we provide an improved analysis under $(L_{0},L_{1})$-smoothness for celebrated Gradient Descent with Polyak Stepsizes (GD-PS, Algorithm 2).

Figure: Algorithm 2 Gradient Descent with Polyak Stepsizes (GD-PS)

###### Theorem 4.1 .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. Then, the iterates generated by GD-PS satisfy the following implication:

$$ $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}\;\Longrightarrow\;\|x^{k+1}-x^ {*}\|^{2}\leqslant\|x^{k}-x^{*}\|^{2}-\frac{\nu^{2}}{16L_{1}^{2}}.$ (17) $$

Moreover, the output after $N$ steps the iterates satisfy

$$ $\frac{4L_{0}}{\nu}\|x^{N+1}-x^{*}\|^{2}+\sum\limits_{k\in\{0,1,\ldots,N\} \setminus{\cal T}}\left(f(x^{k})-f(x^{*})\right)\leqslant\frac{4L_{0}}{\nu}\|x ^{0}-x^{*}\|^{2}-\frac{\nu L_{0}T}{4L_{1}^{2}},$ (18) $$

where ${\cal T}:=\{k\in\{0,1,\ldots,N\}\mid\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L
_{1}}\}$, $T:=|{\cal T}|$, and if $N>T-1$, it holds that

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{4L_{0}\|x^{0}-x^{*}\|^{2}}{\nu(N-T+1)}- \frac{\nu L_{0}T}{4L_{1}^{2}(N-T+1)}$ (19) $$

where $\hat{x}^{N}\in\{x^{0},x^{1},\ldots,x^{N}\}$ is such that $f(\hat{x}^{N})=\min_{x\in\{x^{0},x^{1},\ldots,x^{N}\}}f(x)$. In particular, for $N>\frac{16L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu^{2}}-1$ inequality $N>T-1$ is guaranteed and

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{4L_{0}\|x^{0}-x^{*}\|^{2}}{\nu(N+1)}.$ (20) $$

In addition, if $\mu>0$ and $N>\frac{16L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu^{2}}-1$, then

$$ $\|x^{N}-x^{*}\|^{2}\leqslant\left(1-\frac{\mu\nu}{8L_{0}}\right)^{N-T}\left(\| x^{0}-x^{*}\|^{2}-\frac{\nu^{2}T}{16L_{1}^{2}}\right)\leqslant\left(1-\frac{ \mu\nu}{8L_{0}}\right)^{N-T}\|x^{0}-x^{*}\|^{2}.$ (21) $$

###### Proof sketch.

The proof is similar to the one for $(L_{0},L_{1})$-GD, see the details in Appendix D.
∎

In other words, the above result shows that GD-PS has the same worst-case complexity as $(L_{0},L_{1})$-GD, and the comparison with the results from (Koloskova et al.,, ; Takezawa et al.,, ; ) that we provied after Theorem 3.3 is valid for GD-PS as well. However, in contrast to $(L_{0},L_{1})$-GD, GD-PS requires to know $f(x^{*})$ only. In some cases, the optimal value is known in advance, e.g., for over-parameterized problems () $f(x^{*})=0$, and in such situations GD-PS can be called parameter-free. The price for this is the potential non-monotonic behavior of GD-PS, which we observed in our preliminary computer-aided analysis using PEPit (Goujaud et al.,, ) even in the case of $L$-smooth functions. Therefore, unlike Theorem 3.3, Theorem 4.1 does not provide last-iterate convergence rates in the convex case and also does not imply that GD-PS has a clear two-stage behavior (although the iterates can be split into two groups based on the norm of the gradient as well).

###### Theorem 4.1 .

###### Proof sketch.

## 5 Acceleration: ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -Similar Triangles Method

In this section, we present an accelerated version of $(L_{0},L_{1})$-GD called $(L_{0},L_{1})$-Similar Triangles Method ($(L_{0},L_{1})$-STM, Algorithm 3). This method can be seen as an adaptation of STM (Gasnikov and Nesterov,, ) to the case of $(L_{0},L_{1})$-smooth functions. The main modification in comparison to the standard STM is in Line 6: stepsize for GD-type step is now proportional to $\nicefrac{{1}}{{G_{k+1}}}$, where $G_{k+1}$ is some upper bound on $L_{0}+L_{1}\|\nabla f(x^{k+1})\|$, while in STM $G_{k+1}$ should be an upper bound for the smoothness constant.

Figure: Algorithm 3 $(L_{0},L_{1})$-Similar Triangles Method ($(L_{0},L_{1})$-STM)

The next lemma is valid for any choice of $G_{k+1}\geqslant L_{0}+L_{1}\|\nabla f(x^{k+1})\|$.

###### Lemma 5.1 .

Let $f$ satisfy Assumptions 1.1 with $\mu=0$ and 1.3. Then, the iterates generated by $(L_{0},L_{1})$-STM with $0<\eta\leqslant\frac{\nu}{2}$, $\nu=e^{-\nu}$ satisfy for all $N\geqslant 0$

$$ $\displaystyle A_{N}\left(f(y^{N})-f(x^{*})\right)+\frac{G_{N}}{2}R_{N}^{2}$ $\displaystyle\leqslant$ $\displaystyle\frac{G_{1}}{2}R_{0}^{2}+\sum\limits_{k=1}^{N-1}\frac{G_{k+1}-G_{ k}}{2}R_{k}^{2}$ (23) $\displaystyle\quad-\sum\limits_{k=0}^{N-1}\frac{\alpha_{k+1}^{2}}{4G_{k+1}}\| \nabla f(x^{k+1})\|^{2},$ $$

where $R_{k}:=\|z^{k}-x^{*}\|$ for all $k\geqslant 0$.

Since $A_{N}\geqslant\frac{\eta N(N+3)}{4}$ (see Lemma E.1) and the term from (23) is non-positive, the above lemma gives an accelerated convergence rate, *if we manage to bound the second sum from (23)*. Unfortunately, in the case of $G_{k+1}=L_{0}+L_{1}\|\nabla f(x^{k+1})\|$, it is unclear whether this sum is bounded due to the well-known non-monotonic behavior (in particular, in terms of the gradient norm) of accelerated methods. Nevertheless, if we enforce $G_{k+1}$ to be non-decreasing as a function of $k$, then from the above lemma one can show that $R_{k}$ remains bounded by $R_{0}$ and all iterates generated by $(L_{0},L_{1})$-STM lie in the ball centered at $x^{*}$ with radius $R_{0}$. This observation is formalized in the theorem below (see the complete proof in Appendix E).

###### Theorem 5.2 .

Let $f$ satisfy Assumptions 1.1 with $\mu=0$ and 1.3. Then, the iterates generated by $(L_{0},L_{1})$-STM with $0<\eta\leqslant\frac{\nu}{2}$, $\nu=e^{-\nu}$, $G_{1}=L_{0}+L_{1}\|\nabla f(x^{0})\|$, and

$$ $G_{k+1}=\max\{G_{k},L_{0}+L_{1}\|\nabla f(x^{k+1})\|\},\quad k\geqslant 0,$ (24) $$

satisfy

$$ $f(y^{N})-f(x^{*})\leqslant\frac{2L_{0}(1+L_{1}\|x^{0}-x^{*}\|\exp(L_{1}\|x^{0} -x^{*}\|))\|x^{0}-x^{*}\|^{2}}{\eta N(N+3)}.$ (25) $$

In the special case of $L_{0}$-smooth functions ($L_{1}=0$), the above result recovers the standard accelerated convergence rate (Gasnikov and Nesterov,, ). In the general $(L_{0},L_{1})$-smooth case, the rate is also accelerated and implies an optimal ${\cal O}\left(\sqrt{\nicefrac{{L_{0}(1+L_{1}R_{0}\exp(L_{1}R_{0}))R_{0}^{2}}}{
{\varepsilon}}}\right)$ in $\varepsilon$ complexity. In the case of $(L_{0},L_{1})$-smooth functions, the complexity ${\cal O}\left(\sqrt{\nicefrac{{\ell R_{0}^{2}}}{{\varepsilon}}}\right)$ from () derived for Nesterov’s method applied to convex $(r,\ell)$-smooth problem coincides with our result in the worst-case. Indeed, in this special case, $\ell=L_{0}+2L_{1}G$, where $G\sim\|\nabla f(x^{0})\|$ (, Theorem 4.4). However, according to Lemma 2.1, $\|\nabla f(x^{0})\|\sim L_{0}R_{0}\exp(L_{1}R_{0})$ in the worst case, implying that $\ell\sim L_{0}(1+2L_{1}R_{0}\exp(L_{1}R_{0}))$ in the worst case. Nevertheless, the derived complexity is clearly not optimal if $L_{1}$ is large, $R_{0}$ is large, and $\varepsilon$ is not too small since $\sqrt{\nicefrac{{L_{0}(1+L_{1}R_{0}\exp(L_{1}R_{0}))R_{0}^{2}}}{{\varepsilon}}}$ can be larger than $\max\left\{\nicefrac{{L_{0}R_{0}^{2}}}{{\varepsilon}},L_{1}^{2}R_{0}^{2}\right\}$, i.e., $(L_{0},L_{1})$-GD and GD-PS can be faster in achieving $\varepsilon$-solutiion for some values of $L_{1},R_{0}$, and $\varepsilon$. Deriving a tight lower bound and optimal method for convex $(L_{0},L_{1})$-smooth optimization remains an open problem.

###### Lemma 5.1 .

###### Theorem 5.2 .

## 6 Adaptive Gradient Descent

In this section, we consider Adaptive Gradient Descent (AdGD, Algorithm 4) proposed by Malitsky and Mishchenko, (). In the original paper, the method is analyzed under the assumption that the gradient of $f$ is locally Lipschitz, i.e., for any compact set ${\cal C}$ gradient of $f$ is assumed to be bounded. Clearly, $(L_{0},L_{1})$-smoothness of $f$ implies that $\nabla f$ is locally Lipschitz, e.g., this can be deduced from (6). In particular, Malitsky and Mishchenko, () prove ${\cal O}(\nicefrac{{LD^{2}}}{{N}})$ convergence rate for AdGD with $\gamma\leqslant\nicefrac{{1}}{{2}}$, where $L$ is smoothness constant on the convex combination of $\{x^{*},x^{0},x^{1},\ldots\}$: this set is bounded since the authors prove that AdGD does not leave ball centered at $x^{*}$ with radius $D>0$ such that $D^{2}:=\lVert x^{1}-x^{*}\rVert^{2}+\frac{1}{2}\lVert x^{1}-x^{0}\rVert^{2}+2
\lambda_{1}\theta_{1}(f(x^{0})-f(x^{*}))$. Moreover, they derive $\|x^{k}-x^{k-1}\|^{2}\leqslant 2D^{2}$ for all $k\geqslant 1$. These results can be extended to the case of $\gamma\leqslant\nicefrac{{1}}{{\sqrt{2}}}$, see (Malitsky and Mishchenko,, ).

Figure: Algorithm 4 Adaptive Gradient Descent (Malitsky and Mishchenko,, , )

In the case of $(L_{0},L_{1})$-smoothness, constant $L$ can be estimated explicitly: in view of the mentioned upper bounds on $\|x^{k}-x^{*}\|$ and $\|x^{k}-x^{k-1}\|$, we have

$$ $\|\nabla f(x^{k})\|\overset{\eqref{eq:symmetric_L0_L1_corollary}}{\leqslant}L_ {0}\exp(L_{1}\|x^{k}-x^{*}\|)\|x^{k}-x^{*}\|\leqslant L_{0}\exp(L_{1}D)D,$ (26) $$

which allows us to lower-bound $\frac{\gamma\lVert x^{k}-x^{k-1}\rVert}{\lVert\nabla f(x^{k})-\nabla f(x^{k-1}
)\rVert}$ and $\lambda_{k}$ as $\frac{\gamma}{L_{0}(1+L_{1}D\exp{\left(L_{1}D\right)})\exp{\left(\sqrt{2}L_{1}
D\right)}}$ for all $k\geqslant 1$. Then, following the proof by Malitsky and Mishchenko, (), we get the following result.

###### Theorem 6.1 .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. For all $N\geqslant 1$ we define point $\hat{x}^{N}:=\frac{1}{S_{N}}\left(\lambda_{N}(1+\theta_{N})+\sum_{k=1}^{N}w_{k
}x^{k}\right)$, where $w_{k}:=\lambda_{k}(1+\theta_{k})-\lambda_{k+1}\theta_{k+1}$, $S_{N}:=\lambda_{1}\theta_{1}+\sum_{k=1}^{N}\lambda_{k}$, and $\{x^{k}\}_{k\geqslant 0}$ are the iterates produced by AdGD with $\gamma=\nicefrac{{1}}{{2}}$. Then, $\hat{x}^{N}$ satisfies

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{L_{0}(1+L_{1}D\exp{\left(L_{1}D\right)}) \exp{\left(\sqrt{2}L_{1}D\right)}D^{2}}{N},$ (27) $$

where $D>0$ and $D^{2}:=\lVert x^{1}-x^{*}\rVert^{2}+\frac{1}{2}\lVert x^{1}-x^{0}\rVert^{2}+2
\lambda_{1}\theta_{1}(f(x^{0})-f(x^{*}))$.

Although this result shows that AdGD has the same *rate* $\nicefrac{{1}}{{N}}$ of convergence for smooth and $(L_{0},L_{1})$-smooth functions, constant $L_{0}(1+L_{1}D\exp{\left(L_{1}D\right)})\exp{\left(\sqrt{2}L_{1}D\right)}$ appearing in the upper bound can be huge. To address this issue, we derive a refined convergence result for AdGD.

###### Theorem 6.2 .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. For all $N\geqslant 1$ we define point $\hat{x}^{N}:=\frac{1}{S_{N}}\left(\lambda_{N}(1+\theta_{N})+\sum_{k=1}^{N}w_{k
}x^{k}\right)$, where $w_{k}:=\lambda_{k}(1+\theta_{k})-\lambda_{k+1}\theta_{k+1}$, $S_{N}:=\lambda_{1}\theta_{1}+\sum_{k=1}^{N}\lambda_{k}$, and $\{x^{k}\}_{k\geqslant 0}$ are the iterates produced by AdGD with $\gamma=\nicefrac{{1}}{{4}}$. Then, for $N>\sqrt{2N}(m+1)L_{1}\exp{(2L_{1}D)}D$ iterate $\hat{x}^{N}$ satisfies

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{2L_{0}\exp(2L_{1}D)D^{2}}{N-\sqrt{2N}(m+ 1)L_{1}\exp(2L_{1}D)D},$ (28) $$

where $D>0$ and $D^{2}:=\lVert x^{1}-x^{*}\rVert^{2}+\frac{3}{4}\lVert x^{1}-x^{0}\rVert^{2}+2
\lambda_{1}\theta_{1}(f(x^{0})-f(x^{*}))$, and $m:=1+\log_{\sqrt{2}}\left\lceil\frac{(1+L_{1}D\exp{\left(2L_{1}D\right)})}{2}\right\rceil$. In particular, for $N\geqslant 8(m+1)^{2}L_{1}^{2}\exp{(4L_{1}D)}D^{2}$, we have

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{4L_{0}\exp{(2L_{1}D)}D^{2}}{N}.$ (29) $$

In addition, if Assumption 1.2 holds, one can formally replace $\exp(2L_{1}D)$ in (28) and (29) with $1$.

The above result states that for sufficiently large $N$, AdGD converges at least $\sim 1+L_{1}D\exp{(L_{1}D)}$ faster than the upper bound from Theorem 6.1. This is a noticeable factor: for example, if $L=1$, $D=10$, it is of the order $2\cdot 10^{5}$. Moreover, in contrast to Theorem 6.1, Theorem 6.2 does not follow from the one given by Malitsky and Mishchenko, (). To achieve it, we use $\gamma=\nicefrac{{1}}{{4}}$ and get a new potential function: $\forall k\geqslant 1$

$$ $\displaystyle\Phi_{k+1}\leqslant\Phi_{k},\quad\text{where}$ $\displaystyle\Phi_{k}:=\lVert x^{k}-x^{*}\rVert^{2}+\frac{1}{4}\lVert x^{k}-x^ {k-1}\rVert^{2}+2\lambda_{k}\theta_{k}(f(x^{k-1})-f(x^{*}))+\frac{1}{2}\sum_{i =0}^{k-1}\|x^{i+1}-x^{i}\|^{2}.$ (30) $$

In contrast, the potential function from (Malitsky and Mishchenko,, ) does not have term $\frac{1}{2}\sum_{i=0}^{k-1}\|x^{i+1}-x^{i}\|^{2}$, which is the key for obtaining a better guarantee under $(L_{0},L_{1})$-smoothness. Nevertheless, it remains unclear whether $\exp{(L_{1}D)}$ can be removed from bound (29): of the main obstacles for showing this is potential non-monotonicity of $\{\|\nabla f(x^{k})\|\}_{k\geqslant 0}$. We notice that the lower bound from (Hübler et al.,, ) for the class of *parameter-agnostic* Generalized Normalized Momentum Methods also has an exponential dependence on $L_{1}$. We also provide the analysis of AdGD under Assumption 1.2 for strongly convex problems in Appendix F.3.

###### Theorem 6.1 .

###### Theorem 6.2 .

## 7 Stochastic Extensions

In this section, we consider the finite-sum minimization problem, i.e., we assume that $f(x):=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$. Problems of this type are typical for ML applications (Shalev-Shwartz and Ben-David,, ), where $f_{i}(x)$ represents the loss function evaluated for $i$-th example in the dataset and $x$ are parameters of the model. Since the size of the dataset $n$ is usually large, stochastic first-order methods such as Stochastic Gradient Descent (Robbins and Monro,, ) are the methods of choice for this class of problems. However, to proceed, we need to impose some assumptions on $\{f_{i}\}_{i=1}^{n}$.

###### Assumption 7.1 .

For all $i=1,\ldots,n$ function $f_{i}$ is convex and symmetrically $(L_{0},L_{1})$-smooth, i.e., inequalities (2) with $\mu=0$ and (4) for function $f_{i}$ as well. Moreover, we assume that there exists $x^{*}\in\mathbb{R}^{d}$ such that $x^{*}\in\arg\min_{x\in\mathbb{R}^{d}}f_{i}(x)$ for all $i=1,\ldots,n$, i.e., functions $\{f_{i}\}_{i=1}^{n}$ have a common minimizer.

The first part of the assumption (convexity and $(L_{0},L_{1})$-smoothness of all $\{f_{i}\}_{i=1}^{n}$) is a natural generalization of convexity and $(L_{0},L_{1})$-smoothness of $f$ to the finite-sum case. Next, the existence of common minimizer $x^{*}$ for all $\{f_{i}\}_{i=1}^{n}$ is a typical assumption for over-parameterized models (Belkin et al.,, ; Liang and Rakhlin,, ; Zhang et al.,, ; Bartlett et al.,, ) and used in several recent works on the analysis of stochastic methods (; ; Loizou et al.,, ; Gower et al.,, ). Although Assumption 7.1 does not cover all possibly interesting stochastic scenarios, it does allow the variance of the stochastic gradients to depend on $x$ and grow with the growth of $\|x-x^{*}\|$, which is typical for DL, unlike the standard bounded variance assumption.

For such problems, we consider a direct extension of $(L_{0},L_{1})$-GD called $(L_{0},L_{1})$-Stochastic Gradient Descent ($(L_{0},L_{1})$-SGD, Algorithm 5).

Figure: Algorithm 5 $(L_{0},L_{1})$-Stochastic Gradient Descent ($(L_{0},L_{1})$-SGD)

Below, we present our main convergence result for $(L_{0},L_{1})$-SGD.

###### Theorem 7.2 .

Let Assumption 7.1 hold. Then, the iterates generated by $(L_{0},L_{1})$-SGD with $0<\eta\leqslant\frac{\nu}{2}$, $\nu=e^{-\nu}$
after $N$ iterations satisfy

$$ $\min\limits_{k=0,\ldots,N}\mathbb{E}\left[\min\left\{\frac{\nu L_{0}}{4nL_{1}^ {2}},f(x^{k})-f(x^{*})\right\}\right]\leqslant\frac{2L_{0}\|x^{0}-x^{*}\|^{2}} {\eta(N+1)}.$ (31) $$

As in the deterministic case, the upper bound is proportional to $L_{0}$ and $\nicefrac{{1}}{{(N+1)}}$ and does not depend on a smoothness constant on some ball around the solution. However, one can notice that the convergence criterion in the above result is quite non-standard: typically, the results are given in terms of $\mathbb{E}\left[f(x^{k})-f(x^{*})\right]$. This happens because although functions $\{f_{i}\}_{i=1}^{n}$ have a common minimizer, we cannot guarantee that for some $k_{0}$ and any $k\geqslant k_{0}$ we have $\|\nabla f_{i}(x^{k})\|\leqslant\nicefrac{{L_{0}}}{{L_{1}}}$ with probability $1$ for all $i\in\{1,\ldots,n\}$, i.e., the method does not have to converge uniformly for all samples. This implies that with some small probability $f(x^{k})-f(x^{*})$ can be larger than $\nicefrac{{\nu L_{0}}}{{(4nL_{1}^{2})}}$ for any $k=0,1,\ldots,N$ and any $N\geqslant 0$. However, in view of (31), this probability has to be smaller than $\frac{8nL_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\eta\nu(N+1)}$, i.e., with probability at least $1-\frac{8nL_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\eta\nu(N+1)}$ for $k(N)$ such that $\mathbb{E}\left[\min\left\{\frac{\nu L_{0}}{4nL_{1}^{2}},f(x^{k(N)})-f(x^{*})
\right\}\right]=\min_{k=0,\ldots,N}\mathbb{E}\left[\min\left\{\frac{\nu L_{0}}
{4nL_{1}^{2}},f(x^{k})-f(x^{*})\right\}\right]$ we have $f(x^{k(N)})-f(x^{*})\leqslant\frac{\nu L_{0}}{4nL_{1}^{2}}$, which is small for large enough $n$.

Figure: Algorithm 6 Stochastic Gradient Descent with Polyak Stepsizes (SGD-PS)

Next, we consider SGD-PS proposed by Loizou et al., () (Algorithm 6). In contrast to the deterministic case, SGD-PS requires to know $\{f_{i}(x^{*})\}_{i=1}^{n}$ in advance. Nevertheless, these values equal 0 0 for some existing over-parameterized models, and thus, the method can be applied in such cases. Under the same assumptions, we also derive a similar result for SGD-PS.

###### Theorem 7.3 .

Let Assumption 7.1 hold. Then, the iterates generated by SGD-PS
after $N$ iterations satisfy

$$ $\min\limits_{k=0,\ldots,N}\mathbb{E}\left[\min\left\{\frac{\nu L_{0}}{4nL_{1}^ {2}},f(x^{k})-f(x^{*})\right\}\right]\leqslant\frac{4L_{0}\|x^{0}-x^{*}\|^{2}} {\nu(N+1)}.$ (32) $$

The result is very similar to the one we derive for $(L_{0},L_{1})$-SGD. Therefore, the discussion provided after Theorem 7.2 (with $\eta=\nicefrac{{\nu}}{{2}}$) is valid for the above result as well.

###### Assumption 7.1 .

###### Theorem 7.2 .

###### Theorem 7.3 .

## 8 Numerical Experiments

Figure: Figure 1: The last iterate discrepancy of algorithms on the one-variable polynomial function.
Refer to caption: x1.png

The existing numerical studies already illustrate the benefits of many methods considered in this paper in solving $(L_{0},L_{1})$-smooth problems. In particular, the results of numerical experiments with Clip-GD, which is closely related to $(L_{0},L_{1})$-GD, GD-PS, and AdGD on training LSTM (Merity et al.,, ) and/or ResNet (He et al.,, ) models are provided in (; Loizou et al.,, ; Malitsky and Mishchenko,, ). Therefore, in our numerical experiments, we focus on a simple $1$-dimensional problem that is convex, $(L_{0},L_{1})$-smooth, and provides additional insights to the ones presented in the literature. In particular, we consider function $f(x)=x^{4}$, which is convex, $(4,3)$-smooth, but not $L$-smooth as illustrated in Example 1.4. We run (i) ${\sf GD}$ with stepsize $\nicefrac{{1}}{{L}}$, $L=12|x^{0}|^{2}$ (which corresponds to the worst-case smoothness constant on the interval $|x|\leqslant|x^{0}|$), (ii) $(L_{0},L_{1})$-GD with $L_{0}=4$, $L_{1}=3$, $\eta=\nicefrac{{\nu}}{{2}}$, (iii) $(L_{0},L_{1})$-STM with $G_{k+1}=L_{0}+L_{1}\|\nabla f(x^{k+1})\|$ (not supported by our theory) and (iv) with $G_{k+1}=\max\{G_{k},L_{0}+L_{1}\|\nabla f(x^{k+1})\|\}$ (called $(L_{0},L_{1})$-STM-max on the plots), (v) GD-PS, and (vi) AdGD for starting points $x^{0}\in\{1,10,100\}$. The results are reported in Figure 1. In all tests, GD-PS and AdGD show the best results among other methods (which is expected since these methods are the only parameter-free methods). Next, standard GD is the slowest among other methods and slow-downs once we move the starting point further from the optimum, which is also expected since $L$ increases and we have to use smaller stepsizes for GD. Finally, let us discuss the behavior of $(L_{0},L_{1})$-GD, $(L_{0},L_{1})$-STM-max, and $(L_{0},L_{1})$-STM. Clearly, it depends on the distance from the starting point to the solution. In particular, when $x^{0}=1$ we have $\|\nabla f(x^{0})\|=4$, meaning that $L=16$. In this case, GD and $(L_{0},L_{1})$-GD behave similarly to each other, and $(L_{0},L_{1})$-STM-max significantly outperforms both of them, which is well-aligned with the derived bounds. However, for $x^{0}=10$ and $x^{0}=100$ we have $\|\nabla f(x^{0})\|=4\cdot 10^{3}$ and $\|\nabla f(x^{0})\|=4\cdot 10^{6}$ leading to a significant slow down in the convergence of GD and $(L_{0},L_{1})$-STM-max. In particular, $(L_{0},L_{1})$-GD achieves a similar optimization error to $(L_{0},L_{1})$-STM-max for $x^{0}=10$ and much better optimization error for $x^{0}=100$. This is also aligned with our theoretical results: when $R_{0}$ is large and number of iterations is not too large, bound (15) derived for $(L_{0},L_{1})$-GD can be better than bound (25) derived for $(L_{0},L_{1})$-STM-max. Moreover, for $x^{0}=100$, Figure 1 illustrates well the two-stages convergence behavior of $(L_{0},L_{1})$-GD described in Theorem 3.3. Finally, although our theory does not provide any guarantees for $(L_{0},L_{1})$-STM with $G_{k+1}=L_{0}+L_{1}\|\nabla f(x^{k+1})\|$, this method converges faster than $(L_{0},L_{1})$-GD for the considered problem but exhibits highly non-monotone behavior.

## 9 Conclusion and Future Work

In this paper, we derive improved convergence rates for $(L_{0},L_{1})$-GD and GD-PS, derive convergence guarantees for the new accelerated method called $(L_{0},L_{1})$-STM, and also derive a new result for AdGD in the case of (strongly) convex $(L_{0},L_{1})$-smooth optimization. Our results for $(L_{0},L_{1})$-GD and GD-PS depend neither on $\|\nabla f(x^{0})\|$ nor on $f(x^{0})-f(x^{*})$ nor on exponential functions of $R_{0}$. We also prove new results for the stochastic extensions of $(L_{0},L_{1})$-GD and GD-PS in the case of finite sums of functions having a common minimizer.

Nevertheless, several important questions remain open. One of these questions is the lower bounds for the class of (strongly) convex $(L_{0},L_{1})$-smooth functions and optimal methods for this class. Next, it is unclear whether the bound (29) derived for AdGD is tight. Finally, it would be interesting to develop stochastic extensions of $(L_{0},L_{1})$-GD and GD-PS with strong theoretical guarantees beyond the case of finite sums with shared minimizer.

## Acknowledgements

We thank Konstantin Mishchenko for useful suggestions for improving the writing.

## Appendix A Examples of ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -Smooth Functions

###### Example A.1 (Power of Norm) .

Let $f(x)=\|x\|^{2n}$, where $n$ is a positive integer. Then, $f(x)$ is convex and $(2n,2n-1)$-smooth. Moreover, $f(x)$ is not $L$-smooth for $n\geqslant 2$.

###### Proof.

Convexity of $f$ follows from convexity and monotonicity of $\varphi(t)=t^{2n}$ for $t\geqslant 0$ and convexity of $h(x)=\|x\|$, since $f(x)=\varphi(h(x))$. To show $(L_{0},L_{1})$-smoothness, we compute gradient and Hessian of $f(x)$:

$$ $\displaystyle\nabla f(x)$ $\displaystyle=$ $\displaystyle 2n\|x\|^{2(n-1)}x,$ $\displaystyle\nabla^{2}f(x)$ $\displaystyle=$ $\displaystyle\begin{cases}2{\bf I},&\text{if }n=1\\ 4n(n-1)\|x\|^{2(n-2)}xx^{\top}+2n\|x\|^{2(n-1)}{\bf I},&\text{if }n>1.\end{cases}$ $$

Therefore,

$$ $\displaystyle\|\nabla f(x)\|$ $\displaystyle=$ $\displaystyle 2n\|x\|^{2n-1},$ $\displaystyle\|\nabla^{2}f(x)\|_{2}$ $\displaystyle=$ $\displaystyle\begin{cases}2,&\text{if }n=1\\ 2n(2n-1)\|x\|^{2(n-1)},&\text{if }n>1\end{cases}$ $\displaystyle=$ $\displaystyle 2n(2n-1)\|x\|^{2n-2},$ $$

which implies

$$ $\displaystyle\|\nabla^{2}f(x)\|_{2}-(2n-1)\|\nabla f(x)\|$ $\displaystyle=$ $\displaystyle 2n(2n-1)\|x\|^{2n-2}(1-\|x\|).$ $$

If $\|x\|\geqslant 1$, then we have $\|\nabla^{2}f(x)\|_{2}\leqslant(2n-1)\|\nabla f(x)\|$. If $\|x\|\leqslant 1$, then

$$ $\|\nabla^{2}f(x)\|_{2}-(2n-1)\|\nabla f(x)\|\leqslant 2n(2n-1)\max_{t\in[0,1]} \psi(t),$ $$

where $\psi(t):=t^{2n-2}(1-t)$. For $n=1$ we have $\max_{t\in[0,1]}\psi(t)=1$ and $\|\nabla^{2}f(x)\|_{2}-(2n-1)\|\nabla f(x)\|\leqslant 2$. For $n>1$ we have $\max_{t\in[0,1]}\psi(t)=\left(\frac{2n-2}{2n-1}\right)^{2n-2}\frac{1}{2n-1}
\leqslant\frac{1}{2n-1}$, which gives $\|\nabla^{2}f(x)\|_{2}-(2n-1)\|\nabla f(x)\|\leqslant 2n$. Putting two cases together, we get

$$ $\|\nabla^{2}f(x)\|_{2}\leqslant 2n+(2n-1)\|\nabla f(x)\|$ $$

that is equivalent to $(2n,2n-1)$-smoothness (Chen et al.,, , Theorem 1). Non-smoothness of $f$ for $n>1$ follows from the unboundedness of $\|\nabla^{2}f(x)\|_{2}$ in this case.
∎

###### Example A.2 (Exponent of the Inner Product) .

Function $f(x)=\exp(a^{\top}x)$ for some $a\in\mathbb{R}^{d}$ is convex, $(0,\|a\|)$-smooth, but not $L$-smooth for any $L\geqslant 0$.

###### Proof.

Let us compute the gradient and Hessian of $f$:

$$ $\nabla f(x)=a\exp(a^{\top}x),\quad\nabla^{2}f(x)=aa^{\top}\exp(a^{\top}x).$ $$

Clearly $\nabla^{2}f(x)\succcurlyeq 0$, meaning that $f(x)$ is convex. Moreover,

$$ $\|\nabla^{2}f(x)\|_{2}=\|a\|^{2}\exp(a^{\top}x)=\|a\|\cdot\|\nabla f(x)\|$ $$

that is equivalent to $(0,\|a\|)$-smoothness (Chen et al.,, , Theorem 1). When $a\neq 0$ function $f$ has unbounded Hessian, i.e., $f$ is not $L$-smooth for any $L\geqslant 0$ in this case.
∎

###### Example A.3 (Logistic Function) .

Consider logistic function: $f(x)=\log\left(1+\exp(-a^{\top}x)\right)$, where $a\in\mathbb{R}^{d}$ is some vector. Function $f$ is $(L_{0},L_{1})$-smooth with $L_{0}=0$ and $L_{1}=\|a\|$.

###### Proof.

The gradient and the Hessian of $f(x)$ equal

$$ $\nabla f(x)=-\frac{a}{1+\exp(a^{\top}x)},\quad\nabla^{2}f(x)=\frac{aa^{\top}}{ \left(\exp\left(-\frac{1}{2}a^{\top}x\right)+\exp\left(\frac{1}{2}a^{\top}x \right)\right)^{2}}.$ $$

Moreover,

$$ $\|\nabla f(x)\|=\frac{\|a\|}{1+\exp(a^{\top}x)},\quad\|\nabla^{2}f(x)\|_{2}= \frac{\|a\|^{2}}{\left(\exp\left(-\frac{1}{2}a^{\top}x\right)+\exp\left(\frac{ 1}{2}a^{\top}x\right)\right)^{2}}.$ $$

This leads to

$$ $\displaystyle\frac{\|\nabla^{2}f(x)\|}{\|\nabla f(x)\|}$ $\displaystyle=$ $\displaystyle\frac{1+\exp(a^{\top}x)}{\left(\exp\left(-\frac{1}{2}a^{\top}x \right)+\exp\left(\frac{1}{2}a^{\top}x\right)\right)^{2}}\|a\|$ $\displaystyle=$ $\displaystyle\frac{1+\exp(a^{\top}x)}{\exp\left(-a^{\top}x\right)\left(1+\exp \left(a^{\top}x\right)\right)^{2}}\|a\|$ $\displaystyle=$ $\displaystyle\frac{1}{1+\exp(-a^{\top}x)}\|a\|\leqslant\|a\|,$ $$

implying that $\|\nabla^{2}f(x)\|\leqslant\|a\|\cdot\|\nabla f(x)\|$ for all $x\in\mathbb{R}^{d}$. This condition is equivalent to $(0,\|a\|)$-smoothness (Chen et al.,, , Theorem 1).
∎

###### Example A.1 (Power of Norm) .

###### Proof.

###### Example A.2 (Exponent of the Inner Product) .

###### Proof.

###### Example A.3 (Logistic Function) .

###### Proof.

## Appendix B Proof of Lemma 2.2

###### Lemma B.1 (Lemma 2.2 ) .

Let Assumption 1.3 hold and $\nu$ satisfy(^5^55One can check numerically that $0.56<\nu<0.57$.) $\nu=e^{-\nu}$. Then, the following statements hold.

- 1.
For $f_{*}:=\inf_{x\in\mathbb{R}^{d}}f(x)$, arbitrary $x\in\mathbb{R}^{d}$, and $\nu$ such that $\nu\exp(\nu)=1$, we have
$\frac{\nu\|\nabla f(x)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(x)\|)}\leqslant f(x)-f_{
*}.$
(33)
- 2.
If additionally Assumption 1.1 with $\mu=0$ holds, then for any $x,y\in\mathbb{R}^{d}$ such that
$L_{1}\|x-y\|\exp{\left(L_{1}\|x-y\|\right)}\leqslant 1,$
(34)
we have
$\frac{\nu\|\nabla f(x)-\nabla f(y)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(y)\|)}
\leqslant f(y)-f(x)-\langle\nabla f(x),y-x\rangle,$
(35)
and
$\frac{\nu\|\nabla f(x)-\nabla f(y)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(y)\|)}+\frac
{\nu\|\nabla f(x)-\nabla f(y)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(x)\|)}\leqslant
\langle\nabla f(x)-\nabla f(y),x-y\rangle.$
(36)

###### Proof.

To prove (33), we apply (7) with $y=x-\frac{\nu}{L_{0}+L_{1}\|\nabla f(x)\|}\nabla f(x)$ for given $x\in\mathbb{R}^{d}$ and $\nu$ such that $\nu\exp(\nu)=1$:

$$ $\displaystyle f_{*}\leqslant f(y)$ $\displaystyle\overset{\eqref{eq:sym_upper_bound}}{\leqslant}$ $\displaystyle f(x)+\langle\nabla f(x),y-x\rangle+\frac{L_{0}+L_{1}\|\nabla f(x )\|}{2}\exp(L_{1}\|x-y\|)\|x-y\|^{2}$ $\displaystyle=$ $\displaystyle f(x)-\frac{\nu\|\nabla f(x)\|^{2}}{L_{0}+L_{1}\|\nabla f(x)\|}$ $\displaystyle\quad+\frac{L_{0}+L_{1}\|\nabla f(x)\|}{2}\cdot\exp\left(\frac{L_ {1}\nu\|\nabla f(x)\|}{L_{0}+L_{1}\|\nabla f(x)\|}\right)\cdot\frac{\nu^{2}\| \nabla f(x)\|^{2}}{(L_{0}+L_{1}\|\nabla f(x))^{2}}$ $\displaystyle\leqslant$ $\displaystyle f(x)-\frac{\nu\|\nabla f(x)\|^{2}}{L_{0}+L_{1}\|\nabla f(x)\|}+ \frac{\nu\|\nabla f(x)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(x))}\cdot\nu\exp(\nu)$ $\displaystyle\overset{\nu=e^{-\nu}}{\leqslant}$ $\displaystyle f(x)-\frac{\nu\|\nabla f(x)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(x)\|)}.$ $$

Rearranging the terms, we get (33).

Next, we will prove (35) and (36) under Assumptions 1.1 and 1.3. The proof follows similar steps to the one that holds for standard $L$-smoothness (i.e., cocoercivity of the gradient) (Nesterov,, ):

$$ $\|\nabla f(x)-\nabla f(y)\|^{2}\leqslant L\langle\nabla f(x)-\nabla f(y),x-y\rangle.$ $$

That is, for given $x$ we consider function $\varphi_{x}(y):=f(y)-\langle\nabla f(x),y\rangle$. This function is differentiable and $\nabla\varphi_{x}(y)=\nabla f(y)-\nabla f(x)$. Moreover, for any $u,y\in\mathbb{R}^{d}$ we have

$$ $\|\nabla\varphi_{x}(u)-\nabla\varphi_{x}(y)\|=\|\nabla f(u)-\nabla f(y)\| \overset{\eqref{eq:symmetric_L0_L1_corollary}}{\leqslant}\left(L_{0}+L_{1}\| \nabla f(u)\|\right)\|u-y\|\exp\left(L_{1}\|u-y\|\right),$ (37) $$

Next, for given $x$ and for any $y,u\in\mathbb{R}^{d}$ we define function $\psi_{x,y,u}(t):\mathbb{R}\to\mathbb{R}$ as $\psi_{x,y,u}(t):=\varphi_{x}(u+t(y-u))$. Then, by definition of $\psi_{x,y,u}$, we have $\varphi_{x}(u)=\psi_{x,y,u}(0)$, $\varphi_{x}(y)=\psi_{x,y,u}(1)$, and $\psi_{x,y,u}^{\prime}(t)=\langle\nabla\varphi_{x}(u+t(y-u)),y-u\rangle$. Therefore, using Newton-Leibniz formula, we derive

$$ $\displaystyle\varphi_{x}(y)-\varphi_{x}(u)$ $\displaystyle=$ $\displaystyle\psi_{x,y,u}(1)-\psi_{x,y,u}(0)=\int\limits_{0}^{1}\psi_{x,y,u}^{ \prime}(t)dt$ $\displaystyle=$ $\displaystyle\int_{0}^{1}\langle\nabla\varphi_{x}(u+t(y-u)),y-u\rangle dt$ $\displaystyle=$ $\displaystyle\langle\nabla\varphi_{x}(u),y-u\rangle+\int_{0}^{1}\langle\nabla \varphi_{x}(u+t(y-u))-\nabla\varphi_{x}(u),y-u\rangle dt$ $\displaystyle\leqslant$ $\displaystyle\langle\nabla\varphi_{x}(u),y-u\rangle+\int_{0}^{1}\|\nabla \varphi_{x}(u+t(y-u))-\nabla\varphi_{x}(u)\|\cdot\|u-y\|dt$ $\displaystyle\overset{\eqref{eq:symmetric_phi}}{\leqslant}$ $\displaystyle\langle\nabla\varphi_{x}(u),y-u\rangle+\int_{0}^{1}\left(L_{0}+L_ {1}\|\nabla f(u)\|\right)\exp\left(tL_{1}\|u-y\|\right)\|u-y\|^{2}tdt$ $\displaystyle\leqslant$ $\displaystyle\langle\nabla\varphi_{x}(u),y-u\rangle+\frac{L_{0}+L_{1}\|\nabla f (u)\|}{2}\exp\left(L_{1}\|u-y\|\right)\|u-y\|^{2}$ $$

that implies $\forall u,y\in\mathbb{R}^{d}$

$$ $\varphi_{x}(y)\leqslant\varphi_{x}(u)+\langle\nabla\varphi_{x}(u),y-u\rangle+ \frac{L_{0}+L_{1}\|\nabla f(u)\|}{2}\exp\left(L_{1}\|u-y\|\right)\|u-y\|^{2}.$ (38) $$

To proceed, we will need the following inequality:

$$ $\displaystyle\nu\exp\left(\nu\frac{L_{1}\|\nabla\varphi_{x}(u)\|}{L_{0}+L_{1} \|\nabla f(u)\|}\right)$ $\displaystyle=$ $\displaystyle\nu\exp\left(\nu\frac{L_{1}\|\nabla f(u)-\nabla f(x)\|}{L_{0}+L_{ 1}\|\nabla f(u)\|}\right)$ (39) $\displaystyle\overset{\eqref{eq:symmetric_L0_L1_corollary}}{\leqslant}$ $\displaystyle\nu\exp\left(\nu\frac{L_{1}\|x-u\|\exp\left(L_{1}\|x-u\|\right) \left({L_{0}+L_{1}\|\nabla f(u)\|}\right)}{L_{0}+L_{1}\|\nabla f(u)\|}\right)$ $\displaystyle=$ $\displaystyle\nu\exp\left(\nu L_{1}\|x-u\|\exp\left(L_{1}\|x-u\|\right)\right)$ $\displaystyle\overset{\eqref{eq:proximity_rule_appendix}}{\leqslant}$ $\displaystyle\nu\exp\left(\nu\right)\overset{\nu=e^{-\nu}}{=}1.$ $$

Using the above bound and (38) with $y=u-\frac{\nu}{L_{0}+L_{1}\|\nabla f(u)\|}\nabla\varphi_{x}(u)$, we derive

$$ $\displaystyle\varphi_{x}\left(u-\frac{\nu}{L_{0}+L_{1}\|\nabla f(u)\|}\nabla \varphi_{x}(u)\right)$ $\displaystyle\overset{\eqref{eq:technical_quadr_upper_bound_sym}}{\leqslant}$ $\displaystyle\varphi_{x}(u)-\nu\frac{\|\nabla\varphi_{x}(u)\|^{2}}{L_{0}+L_{1} \|\nabla f(u)\|}+\frac{\nu^{2}\|\nabla\varphi_{x}(u)\|^{2}}{2(L_{0}+L_{1}\| \nabla f(u)\|)}\exp\left(\nu\frac{L_{1}\|\nabla\varphi_{x}(u)\|}{L_{0}+L_{1}\| \nabla f(u)\|}\right)$ $\displaystyle\overset{\eqref{exp bound}}{\leqslant}$ $\displaystyle\varphi_{x}(u)-\nu\frac{\|\nabla\varphi_{x}(u)\|^{2}}{L_{0}+L_{1} \|\nabla f(u)\|}+\frac{\nu\|\nabla\varphi_{x}(u)\|^{2}}{2(L_{0}+L_{1}\|\nabla f (u)\|)}$ $\displaystyle\leqslant$ $\displaystyle\varphi_{x}(u)-\nu\frac{\|\nabla\varphi_{x}(u)\|^{2}}{2(L_{0}+L_{ 1}\|\nabla f(u)\|)},$ $$

Taking into account that $x$ is an optimum for $\varphi_{x}(u)$ ($\nabla\varphi_{x}(x)=0$) and the definition of $\varphi_{x}(u)$, we get the following inequality from the above one:

$$ $f(x)-\langle\nabla f(x),x\rangle\leqslant f(u)-\langle\nabla f(x),u\rangle- \frac{\nu\|\nabla f(x)-\nabla f(u)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(u)\|)},\quad \forall x,u\in\mathbb{R}^{d},$ $$

which is equivalent to

$$ $\frac{\nu\|\nabla f(x)-\nabla f(y)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(y)\|)} \leqslant f(y)-f(x)-\langle\nabla f(x),y-x\rangle,\quad\forall x,y\in\mathbb{R }^{d}.$ $$

Therefore, we established (35). Moreover, by swapping $x$ and $y$ in the above inequality, we also get

$$ $\frac{\nu\|\nabla f(x)-\nabla f(y)\|^{2}}{2(L_{0}+L_{1}\|\nabla f(y)\|)} \leqslant f(x)-f(y)-\langle\nabla f(y),x-y\rangle,\quad\forall x,y\in\mathbb{R }^{d}.$ $$

To get (36), it remains to sum the above two inequalities.
∎

###### Lemma B.1 (Lemma 2.2 ) .

###### Proof.

## Appendix C Missing Proofs for ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -GD

###### Lemma C.1 (Lemma 3.1 : monotonicity of function value) .

Let Assumption 1.3 hold. Then, for all $k\geqslant 0$ the iterates generated by $(L_{0},L_{1})$-GD with $\eta\leqslant\nu$, $\nu=e^{-\nu}$ satisfy

$$ $f(x^{k+1})\leqslant f(x^{k})-\frac{\eta\|\nabla f(x^{k})\|^{2}}{2(L_{0}+L_{1} \|\nabla f(x^{k})\|)}\leqslant f(x^{k}).$ (40) $$

###### Proof.

Applying (7) with $y=x^{k+1}$ and $x=x^{k}$ and using

$$ $\exp(L_{1}\|x^{k+1}-x^{k}\|)=\exp\left(\eta\frac{L_{1}\|\nabla f(x^{k})\|}{L_{ 0}+L_{1}\|\nabla f(x^{k})\|}\right)\leqslant\exp(\eta)$ (41) $$

we get

$$ $\displaystyle f(x^{k+1})$ $\displaystyle\leqslant$ $\displaystyle f(x^{k})+\langle\nabla f(x^{k}),x^{k+1}-x^{k}\rangle+\frac{L_{0} +L_{1}\|\nabla f(x^{k})\|}{2}\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle=$ $\displaystyle f(x^{k})-\frac{\eta\|\nabla f(x^{k})\|^{2}}{L_{0}+L_{1}\|\nabla f (x^{k})\|}+\frac{\eta^{2}\exp(\eta)\|\nabla f(x^{k})\|^{2}}{2(L_{0}+L_{1}\| \nabla f(x^{k})\|)}$ $\displaystyle=$ $\displaystyle f(x^{k})-\eta\left(1-\frac{\eta\exp(\eta)}{2}\right)\frac{\| \nabla f(x^{k})\|^{2}}{L_{0}+L_{1}\|\nabla f(x^{k})\|}$ $\displaystyle\overset{\eta\leqslant\nu}{\leqslant}$ $\displaystyle f(x^{k})-\eta\left(1-\frac{\nu\exp(\nu)}{2}\right)\frac{\|\nabla f (x^{k})\|^{2}}{L_{0}+L_{1}\|\nabla f(x^{k})\|}$ $\displaystyle\overset{\nu=e^{-\nu}}{=}$ $\displaystyle f(x^{k})-\frac{\eta\|\nabla f(x^{k})\|^{2}}{2(L_{0}+L_{1}\| \nabla f(x^{k})\|)}\leqslant f(x^{k}),$ $$

which finishes the proof.
∎

###### Lemma C.2 (Lemma 3.2 : monotonicity of gradient norm) .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. Then, for all $k\geqslant 0$ the iterates generated by $(L_{0},L_{1})$-GD with $\eta\leqslant\nu$, $\nu=e^{-\nu}$ satisfy

$$ $\|\nabla f(x^{k+1})\|\leqslant\|\nabla f(x^{k})\|.$ (42) $$

###### Proof.

For convenience, we introduce the following notation: $\omega_{k}:=L_{0}+L_{1}\|\nabla f(x^{k})\|$ for all $k\geqslant 0$. Since

$$ $\displaystyle L_{1}\|x^{k+1}-x^{k}\|\exp{\left(L_{1}\|x^{k+1}-x^{k}\|\right)}$ $\displaystyle=$ $\displaystyle\frac{\eta L_{1}\|\nabla f(x^{k})\|}{L_{0}+L_{1}\|\nabla f(x^{k}) \|}\exp{\left(\frac{\eta L_{1}\|\nabla f(x^{k})\|}{L_{0}+L_{1}\|\nabla f(x^{k} )\|}\right)}$ $\displaystyle\leqslant$ $\displaystyle\eta\exp(\eta)~{}~{}\overset{\eta\leqslant\nu}{\leqslant}~{}~{} \nu\exp(\nu)~{}~{}\overset{\nu=e^{-\nu}}{=}1,$ $$

the assumptions for the second part of Lemma 2.2 are satisfied for $x=x^{k+1}$ and $y=x^{k}$, and inequality (11) implies

$$ $\displaystyle\left(\frac{\nu}{2\omega_{k}}+\frac{\nu}{2\omega_{k+1}}\right)\| \nabla f(x^{k+1})-\nabla f(x^{k})\|^{2}$ $\displaystyle\leqslant$ $\displaystyle\langle\nabla f(x^{k+1})-\nabla f(x^{k}),x^{k+1}-x^{k}\rangle$ $\displaystyle=$ $\displaystyle-\frac{\eta}{\omega_{k}}\langle\nabla f(x^{k+1})-\nabla f(x^{k}), \nabla f(x^{k})\rangle,$ $$

where in the second line we use $x^{k+1}=x^{k}-\frac{\eta}{\omega_{k}}\nabla f(x^{k})$. Multiplying both sides by $\nicefrac{{2\omega_{k}}}{{\nu}}$ and rearranging the terms, we get

$$ $\displaystyle\left(1+\frac{\omega_{k}}{\omega_{k+1}}\right)\big{(}\|\nabla f(x ^{k+1})\|^{2}$ $\displaystyle+\|\nabla f(x^{k})\|^{2}-2\langle\nabla f(x^{k+1}),\nabla f(x^{k} )\rangle\big{)}$ $\displaystyle\leqslant-\frac{2\eta}{\nu}\cdot\langle\nabla f(x^{k+1}),\nabla f (x^{k})\rangle+\frac{2\eta}{\nu}\cdot\|\nabla f(x^{k})\|^{2},$ $$

which is equivalent to

$$ $\displaystyle\left(1+\frac{\omega_{k}}{\omega_{k+1}}\right)\|\nabla f(x^{k+1}) \|^{2}$ $\displaystyle\leqslant$ $\displaystyle\left(1+\frac{\omega_{k}}{\omega_{k+1}}\right)\|\nabla f(x^{k})\| ^{2}$ $\displaystyle\quad+2\left(1+\frac{\omega_{k}}{\omega_{k+1}}-\frac{\eta}{\nu} \right)\langle\nabla f(x^{k+1}),\nabla f(x^{k})\rangle$ $\displaystyle\quad-2\left(1+\frac{\omega_{k}}{\omega_{k+1}}-\frac{\eta}{\nu} \right)\|\nabla f(x^{k})\|^{2}$ $\displaystyle=$ $\displaystyle\left(1+\frac{\omega_{k}}{\omega_{k+1}}\right)\|\nabla f(x^{k})\| ^{2}$ $\displaystyle\quad+2\left(1+\frac{\omega_{k}}{\omega_{k+1}}-\frac{\eta}{\nu} \right)\langle\nabla f(x^{k+1})-\nabla f(x^{k}),\nabla f(x^{k})\rangle$ $\displaystyle=$ $\displaystyle\left(1+\frac{\omega_{k}}{\omega_{k+1}}\right)\|\nabla f(x^{k})\| ^{2}$ $\displaystyle\quad-\frac{2\omega_{k}}{\eta}\left(1+\frac{\omega_{k}}{\omega_{k +1}}-\frac{\eta}{\nu}\right)\langle\nabla f(x^{k+1})-\nabla f(x^{k}),x^{k+1}-x ^{k}\rangle.$ $$

We notice that $\frac{2\omega_{k}}{\eta}>0$ and $1+\frac{\omega_{k}}{\omega_{k+1}}-\frac{\eta}{\nu}\geqslant\frac{\omega_{k}}{
\omega_{k+1}}\geqslant 0$ since $0<\frac{\eta}{\nu}\leqslant 1$. Moreover, due to the convexity of $f$ we also have $\langle\nabla f(x^{k+1})-\nabla f(x^{k}),x^{k+1}-x^{k}\rangle\geqslant 0$. Therefore, we have

$$ $-\frac{2\omega_{k}}{\eta}\left(1+\frac{\omega_{k}}{\omega_{k+1}}-\frac{\eta}{ \nu}\right)\langle\nabla f(x^{k+1})-\nabla f(x^{k}),x^{k+1}-x^{k}\rangle \leqslant 0.$ $$

Together with (C), the above inequality implies

$$ $\left(1+\frac{\omega_{k}}{\omega_{k+1}}\right)\|\nabla f(x^{k+1})\|^{2} \leqslant\left(1+\frac{\omega_{k}}{\omega_{k+1}}\right)\|\nabla f(x^{k})\|^{2} ,\quad\forall k\geqslant 0,$ $$

which is equivalent to (42).
∎

###### Theorem C.3 (Theorem 3.3 ) .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. Then, the iterates generated by $(L_{0},L_{1})$-GD with $0<\eta\leqslant\frac{\nu}{2}$, $\nu=e^{-\nu}$
satisfy the following implication:

$$ $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}\;\Longrightarrow\;k\leqslant \frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu\eta}-1~{}~{}\text{and}~{}~{}\|x^{k+1} -x^{*}\|^{2}\leqslant\|x^{k}-x^{*}\|^{2}-\frac{\nu\eta}{8L_{1}^{2}}.$ (44) $$

Moreover, the output after $N>\frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu\eta}-1$ iterations satisfies

$$ $f(x^{N})-f(x^{*})\leqslant\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N+1-T)}-\frac{ \nu L_{0}T}{4L_{1}^{2}(N+1-T)}\leqslant\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N +1)},$ (45) $$

where $T:=|{\cal T}|$ for the set ${\cal T}:=\{k\in\{0,1,\ldots N-1\}\mid\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}
{L_{1}}\}$. In addition, if $\mu>0$ and $N>\frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\eta}-1$, then

$$ $\|x^{N}-x^{*}\|^{2}\leqslant\left(1-\frac{\mu\eta}{4L_{0}}\right)^{N-T}\left( \|x^{0}-x^{*}\|^{2}-\frac{\nu\eta T}{8L_{1}^{2}}\right)\leqslant\left(1-\frac{ \mu\eta}{4L_{0}}\right)^{N-T}\|x^{0}-x^{*}\|^{2}.$ (46) $$

###### Proof.

We start by expanding the squared distance to the solution:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle=$ $\displaystyle\left\|x^{k}-x^{*}-\frac{\eta}{L_{0}+L_{1}\|\nabla f(x^{k})\|} \nabla f(x^{k})\right\|^{2}$ (47) $\displaystyle=$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{2\eta}{L_{0}+L_{1}\|\nabla f(x^{k})\|} \langle x^{k}-x^{*},\nabla f(x^{k})\rangle$ $\displaystyle\quad+\frac{\eta^{2}\|\nabla f(x^{k})\|^{2}}{(L_{0}+L_{1}\|\nabla f (x^{k})\|)^{2}}$ $\displaystyle\overset{\eqref{eq:convexity}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{2\eta}{L_{0}+L_{1}\|\nabla f(x^{k})\|} \left(f(x^{k})-f(x^{*})\right)$ $\displaystyle\quad+\frac{\eta^{2}\|\nabla f(x^{k})\|^{2}}{(L_{0}+L_{1}\|\nabla f (x^{k})\|)^{2}}$ $\displaystyle\overset{\eqref{eq:sym_gradient_bound}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-2\eta\left(1-\frac{\eta}{\nu}\right)\frac{f(x ^{k})-f(x^{*})}{L_{0}+L_{1}\|\nabla f(x^{k})\|}$ $\displaystyle\overset{\eta\leqslant\frac{\nu}{2}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\eta\frac{f(x^{k})-f(x^{*})}{L_{0}+L_{1}\| \nabla f(x^{k})\|}.$ $$

To continue the derivation, we consider two possible cases: $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$ or $\|\nabla f(x^{k})\|<\frac{L_{0}}{L_{1}}$.

Case 1: $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$. In this case, we have

$$ $\displaystyle L_{0}+L_{1}\|\nabla f(x^{k})\|\leqslant 2L_{1}\|\nabla f(x^{k})\|,$ (48) $\displaystyle\frac{\nu\|\nabla f(x^{k})\|}{4L_{1}}\overset{\eqref{eq:case_1_ main_ineq_asym_L0_L1_GD}}{\leqslant}\frac{\nu\|\nabla f(x^{k})\|^{2}}{2(L_{0}+ L_{1}\|\nabla f(x^{k})\|)}\overset{\eqref{eq:sym_gradient_bound}}{\leqslant}f( x^{k})-f(x^{*}).$ (49) $$

Plugging the above inequalities in (47), we continue the derivation as follows:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:descent_inequality_asym_case},\eqref{eq:case_1 _main_ineq_asym_L0_L1_GD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\eta\frac{f(x^{k})-f(x^{*})}{2L_{1}\|\nabla f (x^{k})\|}$ (50) $\displaystyle\overset{\eqref{eq:case_1_grad_bound_asym_L0_L1_GD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu\eta}{8L_{1}^{2}}.$ $$

We notice that if $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$, then, in view of Lemma 3.2, we also have $\|\nabla f(x^{t})\|\geqslant\frac{L_{0}}{L_{1}}$ for all $t=0,1,\ldots,k$. Therefore, (50) implies

$$ $\|x^{k+1}-x^{*}\|^{2}\leqslant\|x^{0}-x^{*}\|^{2}-\frac{\nu\eta}{8L_{1}^{2}}(k +1).$ (51) $$

Since $\|x^{k+1}-x^{*}\|^{2}\geqslant 0$, $k$ should be bounded as $k\leqslant\frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu\eta}-1$, which gives (14). We denote $T:=|{\cal T}|$ for the set ${\cal T}:=\{k\in\{0,1,\ldots N-1\}\mid\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}
{L_{1}}\}$. Therefore, in view of (51) and non-negativity of the squared distance, $T$ is bounded as $T\leqslant\frac{8L^{2}\|x^{0}-x^{*}\|^{2}}{\nu\eta}$.

Case 2: $\|\nabla f(x^{k})\|<\frac{L_{0}}{L_{1}}$. In this case, we have

$$ $\displaystyle L_{0}+L_{1}\|\nabla f(x^{k})\|\leqslant 2L_{0},$ (52) $$

implying that

$$ $\|x^{k+1}-x^{*}\|^{2}\overset{\eqref{eq:descent_inequality_asym_case},\eqref{ eq:case_2_main_ineq_asym_L0_L1_GD}}{\leqslant}\|x^{k}-x^{*}\|^{2}-\frac{\eta}{ 2L_{0}}\left(f(x^{k})-f(x^{*})\right).$ (53) $$

Moreover, since the norm of the gradient is non-increasing along the trajectory of $(L_{0},L_{1})$-GD (Lemma 3.2), $\|\nabla f(x^{k})\|<\frac{L_{0}}{L_{1}}$ implies that $k>T$. Therefore, we can sum up inequalities (53) for $k=T,T+1,\ldots,N$, rearrange the terms, and get

$$ $\displaystyle\frac{1}{N+1-T}\sum\limits_{k=T}^{N}\left(f(x^{k})-f(x^{*})\right)$ $\displaystyle\leqslant$ $\displaystyle\frac{2L_{0}}{\eta(N+1-T)}\sum\limits_{k=T}^{N}\left(\|x^{k}-x^{* }\|^{2}-\|x^{k+1}-x^{*}\|^{2}\right)$ $\displaystyle=$ $\displaystyle\frac{2L_{0}\left(\|x^{T}-x^{*}\|^{2}-\|x^{N+1}-x^{*}\|^{2}\right )}{\eta(N+1-T)}$ $\displaystyle\leqslant$ $\displaystyle\frac{2L_{0}\|x^{T}-x^{*}\|^{2}}{\eta(N-T)}.$ $$

Finally, we take into account that for $k=0,1,\ldots,T-1$, we have $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$:

$$ $\displaystyle\frac{1}{N+1-T}\sum\limits_{k=T}^{N}\left(f(x^{k})-f(x^{*})\right)$ $\displaystyle\overset{\eqref{eq:case_1_sq_distance_decrease_asym_L0_L1_GD}}{\leqslant}$ $\displaystyle\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N+1-T)}-\frac{\nu L_{0}T}{4 L_{1}^{2}(N+1-T)}.$ (54) $$

It remains to notice that Lemma 3.1 implies $f(x^{N})-f(x^{*})\leqslant\frac{1}{N-T}\sum_{k=T+1}^{N}\left(f(x^{k})-f(x^{*})\right)$. Together with the above inequality, it implies the first part (15). To derive the second part of (15), it remains to notice that for $N>\frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu\eta}-1$ the right-hand side of (54) as a function of $T$ attains its maximum at $T=0$. Indeed, the derivative of function

$$ $\displaystyle\varphi(T)$ $\displaystyle:=$ $\displaystyle\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N+1-T)}-\frac{\nu L_{0}T}{4 L_{1}^{2}(N+1-T)}$ $\displaystyle=$ $\displaystyle\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N+1-T)}+\frac{\nu L_{0}}{4L _{1}^{2}}-\frac{\nu L_{0}(N+1)}{4L_{1}^{2}(N-T+1)}$ $$

equals

$$ $\displaystyle\varphi^{\prime}(T)$ $\displaystyle=$ $\displaystyle\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N-T+1)^{2}}-\frac{\nu L_{0} (N+1)}{4L_{1}^{2}(N-T+1)^{2}}.$ $$

Since $N>\frac{8L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu\eta}-1$, we have $\varphi^{\prime}(T)<0$, i.e., $\varphi(T)$ is a decreasing function of $T$, meaning that

$$ $\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N+1-T)}-\frac{\nu L_{0}T}{4L_{1}^{2}(N+1 -T)}\leqslant\frac{2L_{0}\|x^{0}-x^{*}\|^{2}}{\eta(N+1)},$ $$

which gives (45).

To prove (46), we notice that for $\mu>0$ we have $f(x^{k})-f(x^{*})\geqslant\frac{\mu}{2}\|x^{k}-x^{*}\|^{2}$ implying

$$ $\|x^{k+1}-x^{*}\|^{2}\overset{\eqref{eq:case_2_descent_ineq_L0_L1_GD}}{ \leqslant}\left(1-\frac{\mu\eta}{4L_{0}}\right)\|x^{k}-x^{*}\|^{2},$ (55) $$

when $\|\nabla f(x^{k})\|<\frac{L_{0}}{L_{1}}$. Therefore, for $N>T$ we have

$$ $\displaystyle\|x^{N}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:case_2_descent_ineq_L0_L1_GD_str_cvx}}{\leqslant}$ $\displaystyle\left(1-\frac{\mu\eta}{4L_{0}}\right)^{N-T}\|x^{T}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:case_1_sq_distance_decrease_asym_L0_L1_GD}}{\leqslant}$ $\displaystyle\left(1-\frac{\mu\eta}{4L_{0}}\right)^{N-T}\left(\|x^{0}-x^{*}\|^ {2}-\frac{\nu\eta T}{8L_{1}^{2}}\right)$ $\displaystyle\leqslant$ $\displaystyle\left(1-\frac{\mu\eta}{4L_{0}}\right)^{N-T}\|x^{0}-x^{*}\|^{2},$ $$

which gives (46) and concludes the proof.
∎

###### Lemma C.1 (Lemma 3.1 : monotonicity of function value) .

###### Proof.

###### Lemma C.2 (Lemma 3.2 : monotonicity of gradient norm) .

###### Proof.

###### Theorem C.3 (Theorem 3.3 ) .

###### Proof.

## Appendix D Missing Proofs for Gradient Descent with Polyak Stepsizes

###### Theorem D.1 (Theorem 4.1 ) .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. Then, the iterates generated by GD-PS satisfy the following implication:

$$ $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}\;\Longrightarrow\;\|x^{k+1}-x^ {*}\|^{2}\leqslant\|x^{k}-x^{*}\|^{2}-\frac{\nu^{2}}{16L_{1}^{2}}.$ (56) $$

Moreover, the output after $N$ steps the iterates satisfy

$$ $\frac{4L_{0}}{\nu}\|x^{N+1}-x^{*}\|^{2}+\sum\limits_{k\in\{0,1,\ldots,N\} \setminus{\cal T}}\left(f(x^{k})-f(x^{*})\right)\leqslant\frac{4L_{0}}{\nu}\|x ^{0}-x^{*}\|^{2}-\frac{\nu L_{0}T}{4L_{1}^{2}},$ (57) $$

where ${\cal T}:=\{k\in\{0,1,\ldots,N\}\mid\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L
_{1}}\}$, $T:=|{\cal T}|$, and if $N>T-1$, it holds that

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{4L_{0}\|x^{0}-x^{*}\|^{2}}{\nu(N-T+1)}- \frac{\nu L_{0}T}{4L_{1}^{2}(N-T+1)}$ (58) $$

where $\hat{x}^{N}\in\{x^{0},x^{1},\ldots,x^{N}\}$ is such that $f(\hat{x}^{N})=\min_{x\in\{x^{0},x^{1},\ldots,x^{N}\}}f(x)$. In particular, for $N>\frac{16L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu^{2}}-1$ inequality $N>T-1$ is guaranteed and

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{4L_{0}\|x^{0}-x^{*}\|^{2}}{\nu(N+1)}.$ (59) $$

In addition, if $\mu>0$ and $N>\frac{16L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu^{2}}-1$, then

$$ $\|x^{N}-x^{*}\|^{2}\leqslant\left(1-\frac{\mu\nu}{8L_{0}}\right)^{N-T}\left(\| x^{0}-x^{*}\|^{2}-\frac{\nu^{2}T}{16L_{1}^{2}}\right)\leqslant\left(1-\frac{ \mu\nu}{8L_{0}}\right)^{N-T}\|x^{0}-x^{*}\|^{2}.$ (60) $$

###### Proof.

As for $(L_{0},L_{1})$-GD, we start by expanding the squared distance to the solution:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle=$ $\displaystyle\left\|x^{k}-x^{*}-\frac{f(x^{k})-f(x^{*})}{\|\nabla f(x^{k})\|^{ 2}}\nabla f(x^{k})\right\|^{2}$ (61) $\displaystyle=$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{2\left(f(x^{k})-f(x^{*})\right)}{\| \nabla f(x^{k})\|^{2}}\langle x^{k}-x^{*},\nabla f(x^{k})\rangle+\frac{\left(f (x^{k})-f(x^{*})\right)^{2}}{\|\nabla f(x^{k})\|^{2}}$ $\displaystyle\overset{\eqref{eq:convexity}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\left(f(x^{k})-f(x^{*})\right)^{2}}{\| \nabla f(x^{k})\|^{2}}$ $\displaystyle\overset{\eqref{eq:sym_gradient_bound}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu}{2}\cdot\frac{f(x^{k})-f(x^{*})}{L_ {0}+L_{1}\|\nabla f(x^{k})\|}.$ $$

To continue the derivation, we consider two possible cases: $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$ or $\|\nabla f(x^{k})\|<\frac{L_{0}}{L_{1}}$.

Case 1: $\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$. In this case, inequalities (48) and (49) hold and the derivation from (61) can be continued as follows:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:descent_inequality_GD_PS},\eqref{eq:case_1_ main_ineq_asym_L0_L1_GD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu}{2}\cdot\frac{f(x^{k})-f(x^{*})}{2L _{1}\|\nabla f(x^{k})\|}$ (62) $\displaystyle\overset{\eqref{eq:case_1_grad_bound_asym_L0_L1_GD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu^{2}}{16L_{1}^{2}},$ $$

which gives (56).

Case 2: $\|\nabla f(x^{k})\|<\frac{L_{0}}{L_{1}}$. In this case, inequality (52) holds and we have

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:descent_inequality_GD_PS},\eqref{eq:case_2_ main_ineq_asym_L0_L1_GD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu}{2}\cdot\frac{f(x^{k})-f(x^{*})}{2L _{0}}.$ (63) $$

Next, we introduce the set of indices ${\cal T}:=\{k\in\{0,1,\ldots,N\}\mid\|\nabla f(x^{k})\|\geqslant\frac{L_{0}}{L
_{1}}\}$ of size $T:=|{\cal T}|$. In view of the above derivations, if $k\in{\cal T}$, inequality (62) holds, and if $k\in\{0,1,\ldots,N\}\setminus{\cal T}$, inequality (63) is satisfied. Therefore, unrolling the pair of inequalities (62) and (63), we get

$$ $\displaystyle\|x^{N+1}-x^{*}\|^{2}$ $\displaystyle\leqslant$ $\displaystyle\|x^{0}-x^{*}\|^{2}-\frac{\nu^{2}T}{16L_{1}^{2}}-\frac{\nu}{4L_{0 }}\sum\limits_{k\in\{0,1,\ldots,N\}\setminus{\cal T}}\left(f(x^{k})-f(x^{*}) \right),$ $$

which is equivalent to (57). Therefore, if $N>T-1$, set $\{0,1,\ldots,N\}\setminus{\cal T}$ is non-empty and the above inequality implies

$$ $\displaystyle f(\hat{x}^{N})-f(x^{*})$ $\displaystyle\leqslant$ $\displaystyle\frac{1}{N-T+1}\sum\limits_{k\in\{0,1,\ldots,N\}\setminus{\cal T} }\left(f(x^{k})-f(x^{*})\right)$ $\displaystyle\leqslant$ $\displaystyle\frac{4L_{0}\|x^{0}-x^{*}\|^{2}}{\nu(N-T+1)}-\frac{\nu L_{0}T}{4L _{1}^{2}(N-T+1)},$ $$

where $\hat{x}^{N}\in\{x^{0},x^{1},\ldots,x^{N}\}$ is such that $f(\hat{x}^{N})=\min_{x\in\{x^{0},x^{1},\ldots,x^{N}\}}f(x)$. Moreover, since the left-hand side of (57) is non-negative, we have $T\leqslant\frac{16L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu^{2}}$. Therefore, for $N>\frac{16L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu^{2}}-1$ inequality $N>T-1$ is guaranteed as well as (58). Finally, to derive (59), we consider the right-hand side of (58) as a function of $T$:

$$ $\displaystyle\varphi(T)$ $\displaystyle:=$ $\displaystyle\frac{4L_{0}\|x^{0}-x^{*}\|^{2}}{\nu(N-T+1)}-\frac{\nu L_{0}T}{4L _{1}^{2}(N-T+1)}$ $\displaystyle=$ $\displaystyle\frac{4L_{0}\|x^{0}-x^{*}\|^{2}}{\nu(N-T+1)}+\frac{\nu L_{0}}{4L_ {1}^{2}}-\frac{\nu L_{0}(N+1)}{4L_{1}^{2}(N-T+1)}.$ $$

The derivative of this function equals

$$ $\displaystyle\varphi^{\prime}(T)$ $\displaystyle=$ $\displaystyle\frac{4L_{0}\|x^{0}-x^{*}\|^{2}}{\nu(N-T+1)^{2}}-\frac{\nu L_{0}( N+1)}{4L_{1}^{2}(N-T+1)^{2}}.$ $$

Since $N>\frac{16L_{1}^{2}\|x^{0}-x^{*}\|^{2}}{\nu^{2}}-1$, we have $\varphi^{\prime}(T)<0$, i.e., $\varphi(T)$ is a decreasing function of $T$. Therefore, since $T\geqslant 0$, we have that

$$ $\varphi(T)\leqslant\varphi(0)\;\Longleftrightarrow\;\frac{4L_{0}\|x^{0}-x^{*} \|^{2}}{\nu(N-T+1)}-\frac{\nu L_{0}T}{4L_{1}^{2}(N-T+1)}\leqslant\frac{4L_{0} \|x^{0}-x^{*}\|^{2}}{\nu(N+1)}.$ $$

Combining the above inequality with (58), we obtain (59).

To prove (60), we notice that for $\mu>0$ we have $f(x^{k})-f(x^{*})\geqslant\frac{\mu}{2}\|x^{k}-x^{*}\|^{2}$ implying

$$ $\|x^{k+1}-x^{*}\|^{2}\overset{\eqref{eq:case_2_descent_ineq_GD_PS}}{\leqslant} \left(1-\frac{\mu\nu}{8L_{0}}\right)\|x^{k}-x^{*}\|^{2},$ (64) $$

when $\|\nabla f(x^{k})\|<\frac{L_{0}}{L_{1}}$. Unrolling the pair of inequalities (62) and (64), we get for $N>T$

$$ $\displaystyle\|x^{N}-x^{*}\|^{2}\leqslant\left(1-\frac{\mu\nu}{8L_{0}}\right)^ {N-T}\|x^{0}-x^{*}\|^{2}-\frac{\nu^{2}}{16L_{1}^{2}}\sum\limits_{k\in{\cal T}} \left(1-\frac{\mu\nu}{8L_{0}}\right)^{t_{k}},$ $$

where $t_{k}$ is the cardinality of $\{k+1,\ldots,N\}\setminus{\cal T}$. Since $|{\cal T}|=T$ we have that $t_{k}\leqslant N-T$ for all $k\in{\cal T}$. Therefore, we can continue the derivation as follows:

$$ $\displaystyle\|x^{N}-x^{*}\|^{2}$ $\displaystyle\leqslant$ $\displaystyle\left(1-\frac{\mu\nu}{8L_{0}}\right)^{N-T}\left(\|x^{0}-x^{*}\|^{ 2}-\frac{\nu^{2}T}{16L_{1}^{2}}\right)$ $\displaystyle\leqslant$ $\displaystyle\left(1-\frac{\mu\nu}{8L_{0}}\right)^{N-T}\|x^{0}-x^{*}\|^{2},$ $$

which gives (60) and concludes the proof.
∎

###### Theorem D.1 (Theorem 4.1 ) .

###### Proof.

## Appendix E Missing Proofs for ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -Similar Triangles Method

###### Lemma E.1 (Lemma E.1 from (Gorbunov et al.,, 2020 ) ) .

Let sequences $\{\alpha_{k}\}_{k\geqslant 0}$ and $\{A_{k}\}_{k\geqslant 0}$ be defined as follows:

$$ $\alpha_{0}=A_{0}=0,\quad\alpha_{k+1}=\frac{\eta(k+2)}{2},\quad A_{k+1}=A_{k}+ \alpha_{k+1},\quad\forall k\geqslant 0.$ $$

Then, for all $k\geqslant 0$

$$ $\displaystyle A_{k+1}$ $\displaystyle\geqslant$ $\displaystyle\frac{\eta(k+1)(k+4)}{4},$ (65) $\displaystyle A_{k+1}$ $\displaystyle\geqslant$ $\displaystyle\frac{\alpha_{k+1}^{2}}{\eta}.$ (66) $$

###### Lemma E.2 (Lemma 5.1 ) .

Let $f$ satisfy Assumptions 1.1 with $\mu=0$ and 1.3. Then, the iterates generated by $(L_{0},L_{1})$-STM with $0<\eta\leqslant\frac{\nu}{2}$, $\nu=e^{-\nu}$ satisfy for all $N\geqslant 0$

$$ $\displaystyle A_{N}\left(f(y^{N})-f(x^{*})\right)+\frac{G_{N}}{2}R_{N}^{2}$ $\displaystyle\leqslant$ $\displaystyle\frac{G_{1}}{2}R_{0}^{2}+\sum\limits_{k=1}^{N-1}\frac{G_{k+1}-G_{ k}}{2}R_{k}^{2}$ (68) $\displaystyle\quad-\sum\limits_{k=0}^{N-1}\frac{\alpha_{k+1}^{2}}{4G_{k+1}}\| \nabla f(x^{k+1})\|^{2},$ $$

where $R_{k}:=\|z^{k}-x^{*}\|$ for all $k\geqslant 0$.

###### Proof.

The proof follows the one of Lemma F.4 from (Gorbunov et al.,, ).
From the update rule, we have $z^{k+1}=z^{k}-\frac{\alpha_{k+1}}{G_{k+1}}\nabla f(x^{k+1})$ and

$$ $\displaystyle\alpha_{k+1}\langle\nabla f(x^{k+1}),z^{k}-x^{*}\rangle$ $\displaystyle=$ $\displaystyle\alpha_{k+1}\langle\nabla f(x^{k+1}),z^{k}-z^{k+1}\rangle+\alpha_ {k+1}\langle\nabla f(x^{k+1}),z^{k+1}-x^{*}\rangle$ $\displaystyle=$ $\displaystyle\alpha_{k+1}\langle\nabla f(x^{k+1}),z^{k}-z^{k+1}\rangle+G_{k+1} \langle z^{k+1}-z^{k},x^{*}-z^{k+1}\rangle$ $\displaystyle=$ $\displaystyle\alpha_{k+1}\langle\nabla f(x^{k+1}),z^{k}-z^{k+1}\rangle-\frac{G _{k+1}}{2}\|z^{k}-z^{k+1}\|^{2}$ $\displaystyle\quad+\frac{G_{k+1}}{2}\|z^{k}-x^{*}\|^{2}-\frac{G_{k+1}}{2}\|z^{ k+1}-x^{*}\|^{2}.$ $$

The update rules for $y^{k+1}$ and $x^{k+1}$ imply

$$ $A_{k+1}(y^{k+1}-x^{k+1})=\alpha_{k+1}(z^{k+1}-z^{k}).$ (69) $$

Moreover, to proceed, we will need the following upper-bound:

$$ $\displaystyle\exp\left(L_{1}\|x^{k+1}-y^{k+1}\|\right)$ $\displaystyle\overset{\eqref{eq:update_rule_impl_L0_L1_STM}}{=}$ $\displaystyle\exp\left(\frac{L_{1}\alpha_{k+1}\|z^{k+1}-z^{k}\|}{A_{k+1}}\right)$ (70) $\displaystyle=$ $\displaystyle\exp\left(\frac{\alpha_{k+1}^{2}L_{1}\|\nabla f(x^{k+1})\|}{A_{k+ 1}(L_{0}+L_{1}\|\nabla f(x^{k+1})\|)}\right)\leqslant\exp\left(\frac{\alpha_{k +1}^{2}}{A_{k+1}}\right)$ $\displaystyle\overset{\eqref{eq:A_k+1_lower_bound_2_new}}{\leqslant}$ $\displaystyle\exp(\eta)~{}\overset{\eta\leqslant\nu}{\leqslant}~{}\exp(\nu)~{} \overset{\nu=e^{-\nu}}{=}~{}\nu.$ $$

Using these formulas, we continue the derivation as follows:

$$ $\displaystyle\alpha_{k+1}\langle\nabla f(x^{k+1}),z^{k}-x^{*}\rangle$ $\displaystyle=$ $\displaystyle A_{k+1}\langle\nabla f(x^{k+1}),x^{k+1}-y^{k+1}\rangle-\frac{G_{ k+1}}{2}\|z^{k}-z^{k+1}\|^{2}$ (71) $\displaystyle\quad+\frac{G_{k+1}}{2}\|z^{k}-x^{*}\|^{2}-\frac{G_{k+1}}{2}\|z^{ k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:sym_upper_bound}}{\leqslant}$ $\displaystyle A_{k+1}\left(f(x^{k+1})-f(y^{k+1})\right)$ $\displaystyle\quad+\frac{A_{k+1}G_{k+1}\exp\left(L_{1}\|x^{k+1}-y^{k+1}\| \right)}{2}\|x^{k+1}-y^{k+1}\|^{2}$ $\displaystyle\quad-\frac{G_{k+1}}{2}\|z^{k}-z^{k+1}\|^{2}+\frac{G_{k+1}}{2}\|z ^{k}-x^{*}\|^{2}$ $\displaystyle\quad-\frac{G_{k+1}}{2}\|z^{k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:update_rule_impl_L0_L1_STM},\eqref{eq:exponent _bound_STM}}{\leqslant}$ $\displaystyle A_{k+1}\left(f(x^{k+1})-f(y^{k+1})\right)+\frac{G_{k+1}}{2}\cdot \frac{\nu\alpha_{k+1}^{2}}{A_{k+1}}\|z^{k}-z^{k+1}\|^{2}$ $\displaystyle\quad-\frac{G_{k+1}}{2}\|z^{k}-z^{k+1}\|^{2}+\frac{G_{k+1}}{2}\|z ^{k}-x^{*}\|^{2}$ $\displaystyle\quad-\frac{G_{k+1}}{2}\|z^{k+1}-x^{*}\|^{2}$ $\displaystyle=$ $\displaystyle A_{k+1}\left(f(x^{k+1})-f(y^{k+1})\right)$ $\displaystyle\quad+\frac{G_{k+1}}{2}\left(\frac{\nu\alpha_{k+1}^{2}}{A_{k+1}}- 1\right)\|z^{k}-z^{k+1}\|^{2}$ $\displaystyle\quad+\frac{G_{k+1}}{2}\|z^{k}-x^{*}\|^{2}-\frac{G_{k+1}}{2}\|z^{ k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:A_k+1_lower_bound_2_new},\eta\leqslant\frac{ \nu}{2}}{\leqslant}$ $\displaystyle A_{k+1}\left(f(x^{k+1})-f(y^{k+1})\right)-\frac{G_{k+1}}{4}\|z^{ k}-z^{k+1}\|^{2}$ $\displaystyle\quad+\frac{G_{k+1}}{2}\|z^{k}-x^{*}\|^{2}-\frac{G_{k+1}}{2}\|z^{ k+1}-x^{*}\|^{2}.$ $$

Next, using the definition of $x^{k+1}$ and $A_{k+1}=A_{k}+\alpha_{k+1}$, we get

$$ $\alpha_{k+1}(x^{k+1}-z^{k})=A_{k}(y^{k}-x^{k+1}).$ (72) $$

Combining the established inequalities, we obtain

$$ $\displaystyle\alpha_{k+1}\langle\nabla f(x^{k+1}),x^{k+1}-x^{*}\rangle$ $\displaystyle=$ $\displaystyle\alpha_{k+1}\langle\nabla f(x^{k+1}),x^{k+1}-z^{k}\rangle$ $\displaystyle\quad+\alpha_{k+1}\langle\nabla f(x^{k+1}),z^{k}-x^{*}\rangle$ $\displaystyle\overset{\eqref{eq:descent_1_L0_L1_STM},\eqref{eq:update_rule_ impl_L0_L1_STM_1}}{\leqslant}$ $\displaystyle A_{k}\langle\nabla f(x^{k+1}),y^{k}-x^{k+1}\rangle$ $\displaystyle\quad+A_{k+1}\left(f(x^{k+1})-f(y^{k+1})\right)-\frac{G_{k+1}}{4} \|z^{k}-z^{k+1}\|^{2}$ $\displaystyle\quad+\frac{G_{k+1}}{2}\|z^{k}-x^{*}\|^{2}-\frac{G_{k+1}}{2}\|z^{ k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:convexity}}{\leqslant}$ $\displaystyle A_{k}\left(f(y^{k})-f(x^{k+1})\right)+A_{k+1}\left(f(x^{k+1})-f( y^{k+1})\right)$ $\displaystyle\quad-\frac{G_{k+1}}{4}\|z^{k}-z^{k+1}\|^{2}+\frac{G_{k+1}}{2}\|z ^{k}-x^{*}\|^{2}$ $\displaystyle\quad-\frac{G_{k+1}}{2}\|z^{k+1}-x^{*}\|^{2},$ $$

which can be rewritten as

$$ $\displaystyle A_{k+1}f(y^{k+1})-A_{k}f(y^{k})$ $\displaystyle\leqslant$ $\displaystyle\alpha_{k+1}\left(f(x^{k+1})+\langle\nabla f(x^{k+1}),x^{*}-x^{k+ 1}\rangle\right)$ $\displaystyle+\frac{G_{k+1}}{2}\|z^{k}-x^{*}\|^{2}-\frac{G_{k+1}}{2}\|z^{k+1}- x^{*}\|^{2}-\frac{\alpha_{k+1}^{2}}{4G_{k+1}}\|\nabla f(x^{k+1})\|^{2}$ $\displaystyle\overset{\eqref{eq:convexity}}{\leqslant}$ $\displaystyle\alpha_{k+1}f(x^{*})$ $\displaystyle+\frac{G_{k+1}}{2}\|z^{k}-x^{*}\|^{2}-\frac{G_{k+1}}{2}\|z^{k+1}- x^{*}\|^{2}-\frac{\alpha_{k+1}^{2}}{4G_{k+1}}\|\nabla f(x^{k+1})\|^{2}.$ $$

Summing up the above inequality for $k=0,1,\ldots,N-1$ and using $A_{0}=\alpha_{0}=0$, $\sum_{k=0}^{N-1}\alpha_{k+1}=A_{N}$, and new notation $R_{k}:=\|z^{k}-x^{*}\|$, we derive

$$ $\displaystyle A_{N}\left(f(y^{N})-f(x^{*})\right)+\frac{G_{N}}{2}R_{N}^{2}$ $\displaystyle\leqslant$ $\displaystyle\frac{G_{1}}{2}R_{0}^{2}+\sum\limits_{k=1}^{N-1}\frac{G_{k+1}-G_{ k}}{2}R_{k}^{2}-\sum\limits_{k=0}^{N-1}\frac{\alpha_{k+1}^{2}}{4G_{k+1}}\| \nabla f(x^{k+1})\|^{2},$ $$

which finishes the proof.
∎

###### Theorem E.3 (Theorem 5.2 ) .

Let $f$ satisfy Assumptions 1.1 with $\mu=0$ and 1.3. Then, the iterates generated by $(L_{0},L_{1})$-STM with $0<\eta\leqslant\frac{\nu}{2}$, $\nu=e^{-\nu}$, $G_{1}=L_{0}+L_{1}\|\nabla f(x^{0})\|$, and

$$ $G_{k+1}=\max\{G_{k},L_{0}+L_{1}\|\nabla f(x^{k+1})\|\},\quad k\geqslant 0,$ (73) $$

satisfy

$$ $f(y^{N})-f(x^{*})\leqslant\frac{2L_{0}(1+L_{1}\|x^{0}-x^{*}\|\exp(L_{1}\|x^{0} -x^{*}\|))\|x^{0}-x^{*}\|^{2}}{\eta N(N+3)}.$ (74) $$

###### Proof.

Let us prove by induction that $R_{k}\leqslant R_{0}$ for all $k\geqslant 0$. For $k=0$, the statement is trivial. Next, we assume that the statement holds for $k=N$ and derive that it also holds for $k=N+1$. Indeed, from Lemma 5.1 we have

$$ $\displaystyle\frac{G_{N+1}}{2}R_{N+1}^{2}$ $\displaystyle\leqslant$ $\displaystyle A_{N+1}\left(f(y^{N+1})-f(x^{*})\right)+\frac{G_{N+1}}{2}R_{N+1} ^{2}$ (75) $\displaystyle\overset{\eqref{eq:main_inequality_asym_L0_L1_STM}}{\leqslant}$ $\displaystyle\frac{G_{1}}{2}R_{0}^{2}+\sum\limits_{k=1}^{N}\frac{G_{k+1}-G_{k} }{2}R_{k}^{2}$ $\displaystyle\leqslant$ $\displaystyle\frac{G_{1}}{2}R_{0}^{2}+\sum\limits_{k=1}^{N}\frac{G_{k+1}-G_{k} }{2}R_{0}^{2}=\frac{G_{N+1}}{2}R_{0}^{2},$ $$

implying that $R_{N+1}\leqslant R_{0}$. That is, we proved that $R_{k}\leqslant R_{0}$ for all $k\geqslant 0$, i.e., the sequence $\{z^{k}\}_{k\geqslant 0}$ stays in $B_{R_{0}}(x^{*}):=\{x\in\mathbb{R}^{d}\mid\|x-x^{*}\|\leqslant R_{0}\}$. Since $x^{0}=y^{0}=z^{0}$, $x^{k+1}$ is a convex combination of $y^{k}$ and $z^{k}$, $y^{k+1}$ is a convex combination of $y^{k}$ and $z^{k+1}$, we also have that sequences $\{x^{k}\}_{k\geqslant 0}$ and $\{y^{k}\}_{k\geqslant 0}$ stay in $B_{R_{0}}(x^{*})$, which can be formally shown using an induction argument. Therefore, we can upper-bound $G_{k}$ for all $k\geqslant 0$ as follows

$$ $\displaystyle G_{k}$ $\displaystyle=$ $\displaystyle L_{0}+L_{1}\max\limits_{t=0,\ldots,k}\|\nabla f(x^{t})\|\overset {\eqref{eq:symmetric_L0_L1_corollary}}{\leqslant}L_{0}+L_{1}L_{0}\max\limits_{ t=0,\ldots,k}\exp(L_{1}\|x^{t}-x^{*}\|)\|x^{t}-x^{*}\|$ (76) $\displaystyle\leqslant$ $\displaystyle L_{0}\left(1+L_{1}R_{0}\exp(L_{1}R_{0})\right).$ $$

Moreover, from (75) we also have

$$ $\displaystyle f(y^{N})-f(x^{*})$ $\displaystyle\leqslant$ $\displaystyle\frac{G_{N}R_{0}^{2}}{2A_{N}}\overset{\eqref{eq:G_k_upper_bound_ asym},\eqref{eq:A_k+1_lower_bound_1_new}}{\leqslant}\frac{2L_{0}(1+L_{1}R_{0} \exp(L_{1}R_{0}))R_{0}^{2}}{\eta N(N+3)},$ $$

which finishes the proof.
∎

###### Lemma E.1 (Lemma E.1 from (Gorbunov et al.,, 2020 ) ) .

###### Lemma E.2 (Lemma 5.1 ) .

###### Proof.

###### Theorem E.3 (Theorem 5.2 ) .

###### Proof.

## Appendix F Missing Proofs for Adaptive Gradient Descent

### F.1 Proof of Theorem 6.1

The key lemma about the convergence of AdGD holds for any convex function regardless of the smoothness properties.

###### Lemma F.1 (Lemma 1 from Malitsky and Mishchenko, ( 2020 ) ) .

Let Assumption 1.1 with $\mu=0$ hold, and $x^{*}$ be any minimizer of $f$. Then, the iterates generated
by Algorithm 4 with $\gamma=\frac{1}{2}$ satisfy

$$ $\lVert x^{k+1}-x^{*}\rVert^{2}+\frac{1}{2}\lVert x^{k+1}-x^{k}\rVert^{2}+2 \lambda_{k}(1+\theta_{k})(f(x^{k})-f(x^{*}))\\ \leqslant\lVert x^{k}-x^{*}\rVert^{2}+\frac{1}{2}\lVert x^{k}-x^{k-1}\rVert^{2 }+2\lambda_{k}\theta_{k}(f(x^{k-1})-f(x^{*})).$ (77) $$

In particular, the above lemma implies boundedness of $\|x^{k}-x^{*}\|$ and $\|x^{k}-x^{k-1}\|$, which allows us to get the upper bound on the gradient norm (26) and a lower bound for $\lambda_{k}$ as stated in the paragraph before Theorem 6.1. For completeness, we provide the proof of this theorem below.

###### Theorem F.2 (Theorem 6.1 ) .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. For all $N\geqslant 1$ we define point $\hat{x}^{N}:=\frac{1}{S_{N}}\left(\lambda_{N}(1+\theta_{N})+\sum_{k=1}^{N}w_{k
}x^{k}\right)$, where $w_{k}:=\lambda_{k}(1+\theta_{k})-\lambda_{k+1}\theta_{k+1}$, $S_{N}:=\lambda_{1}\theta_{1}+\sum_{k=1}^{N}\lambda_{k}$, and $\{x^{k}\}_{k\geqslant 0}$ are the iterates produced by AdGD with $\gamma=\nicefrac{{1}}{{2}}$. Then, $\hat{x}^{N}$ satisfies

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{L_{0}(1+L_{1}D\exp{\left(L_{1}D\right)}) \exp{\left(\sqrt{2}L_{1}D\right)}D^{2}}{N},$ (78) $$

where $D>0$ and $D^{2}:=\lVert x^{1}-x^{*}\rVert^{2}+\frac{1}{2}\lVert x^{1}-x^{0}\rVert^{2}+2
\lambda_{1}\theta_{1}(f(x^{0})-f(x^{*}))$.

###### Proof.

The proof follows almost the same lines as the proof from (Malitsky and Mishchenko,, ). Telescoping inequality (77), we get

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}+\frac{1}{2}\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle+2\lambda_{k}(1+\theta_{k})(f(x^{k})-f(x^{*}))$ $\displaystyle+2\sum_{i=1}^{k-1}$ $\displaystyle\left[\lambda_{i}(1+\theta_{i})-\lambda_{i+1}\theta_{i+1}\right]( f(x^{i})-f(x^{*}))$ $\displaystyle\leqslant\|x^{1}-x^{*}\|^{2}+\frac{1}{2}\|x^{1}-x^{0}\|^{2}+2 \lambda_{1}\theta_{1}(f(x^{0})-f(x^{*})).$ (79) $$

Since $\lambda_{i}(1+\theta_{i})-\lambda_{i+1}\theta_{i+1}\geqslant 0$ by definition of $\lambda_{i}$, we conclude that the term in the second line of the above inequality is non-negative. Therefore, for any $k\geqslant 1$ we have

$$ $\displaystyle\|x^{k}-x^{*}\|^{2}$ $\displaystyle\leqslant$ $\displaystyle D^{2},$ (80) $\displaystyle\|x^{k}-x^{k-1}\|^{2}$ $\displaystyle\leqslant$ $\displaystyle 2D^{2}.$ (81) $$

Using Jensen’s inequality in (F.1), we derive

$$ $\displaystyle S_{k}(f(\hat{x}^{k})-f(x_{*}))\leqslant\frac{D^{2}}{2},$ $$

where

$$ $\displaystyle\hat{x}^{k}$ $\displaystyle=$ $\displaystyle\frac{\lambda_{k}(1+\theta_{k})x^{k}+\sum_{i=1}^{k-1}w_{i}x^{i}}{ S_{k}},$ (82) $\displaystyle w_{k}$ $\displaystyle=$ $\displaystyle\lambda_{i}(1+\theta_{i})-\lambda_{i+1}\theta_{i+1},$ (83) $\displaystyle S_{k}$ $\displaystyle=$ $\displaystyle\lambda_{1}\theta_{1}+\sum_{i=1}^{k}\lambda_{i}.$ (84) $$

Thus, we have

$$ $f(\hat{x}^{k})-f_{*}\leqslant\frac{D^{2}}{2S_{k}}.$ (85) $$

Next, we notice that for any $k\geqslant 1$

$$ $\displaystyle\frac{\|x^{k}-x^{k-1}\|}{\|\nabla f(x^{k})-\nabla f(x^{k-1})\|}$ $\displaystyle\overset{\eqref{eq:symmetric_L0_L1_corollary}}{\geqslant}$ $\displaystyle\frac{1}{(L_{0}+L_{1}\|\nabla f(x^{k})\|)\exp(L_{1}\|x^{k}-x^{k-1 }\|)}$ $\displaystyle\overset{\eqref{eq:grad_bound_AdGD}}{\geqslant}$ $\displaystyle\frac{1}{L_{0}(1+L_{1}D\exp(L_{1}D))\exp(\sqrt{2}L_{1}D)}.$ $$

Since $\theta_{0}=+\infty$, we have $\lambda_{1}=\frac{\|x^{1}-x^{0}\|}{2\|\nabla f(x^{1})-\nabla f(x^{0})\|}$. Moreover, for $k>1$ we have either $\lambda_{k}\geqslant\lambda_{k-1}$ or $\lambda_{k}=\frac{\|x^{k}-x^{k-1}\|}{2\|\nabla f(x^{k})-\nabla f(x^{k-1})\|}$. Therefore, by induction we can prove that

$$ $\lambda_{k}\geqslant\frac{1}{2L_{0}(1+L_{1}D\exp(L_{1}D))\exp(\sqrt{2}L_{1}D)}$ (86) $$

that implies

$$ $\displaystyle S_{k}$ $\displaystyle=$ $\displaystyle\lambda_{1}\theta_{1}+\sum_{i=1}^{k}\lambda_{i}\geqslant\frac{k}{ 2L_{0}(1+L_{1}D\exp(L_{1}D))\exp(\sqrt{2}L_{1}D)}.$ $$

Therefore, we have

$$ $f(\hat{x}^{k})-f(x^{*})\leqslant\frac{D^{2}}{2S_{k}}\leqslant\frac{L_{0}(1+L_{ 1}D\exp{\left(L_{1}D\right)})\exp{\left(\sqrt{2}L_{1}D\right)}D^{2}}{k},$ $$

which is equivalent to (78) when $k=N$.
∎

###### Lemma F.1 (Lemma 1 from Malitsky and Mishchenko, ( 2020 ) ) .

###### Theorem F.2 (Theorem 6.1 ) .

###### Proof.

### F.2 Proof of Theorem 6.2

To show an improved result, we consider Algorithm 4 with $\gamma=\frac{1}{4}$ and refine Lemma F.1 as follows.

###### Lemma F.3 .

Let Assumption 1.1 with $\mu=0$ hold, and $x^{*}$ be any minimizer of $f$. Then, the iterates generated
by Algorithm 4 with $\gamma=\frac{1}{4}$ satisfy for all $k\geqslant 1$

$$ $\lVert x^{k+1}-x^{*}\rVert^{2}+\frac{1}{4}\lVert x^{k+1}-x^{k}\rVert^{2}+2 \lambda_{k}(1+\theta_{k})(f(x^{k})-f(x^{*}))+\frac{1}{2}\sum_{i=0}^{k}\|x^{i+1 }-x^{i}\|^{2}\\ \leqslant\lVert x^{k}-x^{*}\rVert^{2}+\frac{1}{4}\lVert x^{k}-x^{k-1}\rVert^{2 }+2\lambda_{k}\theta_{k}(f(x^{k-1})-f(x^{*}))+\frac{1}{2}\sum_{i=0}^{k-1}\|x^{ i+1}-x^{i}\|^{2}.$ (87) $$

###### Proof.

The proof is almost identical to the one from (Malitsky and Mishchenko,, ) and starts as the standard proof for GD:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle=\|x^{k}-x^{*}\|^{2}+2\langle x^{k+1}-x^{k},x^{k}-x^{*}\rangle+\| x^{k+1}-x^{k}\|^{2}$ $\displaystyle=\|x^{k}-x^{*}\|^{2}+2\lambda_{k}\langle\nabla f(x^{k}),x^{*}-x^{ k}\rangle+\|x^{k+1}-x^{k}\|^{2}.$ $\displaystyle\overset{\eqref{eq:convexity}}{\leqslant}\|x^{k}-x^{*}\|^{2}+2 \lambda_{k}(f(x^{*})-f(x^{k}))+\|x^{k+1}-x^{k}\|^{2}.$ $$

Introducing $\Sigma_{k+1}=\frac{1}{2}\sum_{i=0}^{k}\|x^{i+1}-x^{i}\|^{2}$, we rewrite the above inequality as

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}+\Sigma_{k+1}$ $\displaystyle\leq$ $\displaystyle\|x^{k}-x^{*}\|^{2}-2\lambda_{k}(f(x^{k})-f(x^{*}))+\|x^{k+1}-x^{ k}\|^{2}$ (88) $\displaystyle\quad+\Sigma_{k}+\frac{1}{2}\|x^{k+1}-x^{k}\|^{2}.$ $$

Next, we transform $\lVert x^{k+1}-x^{k}\rVert^{2}$
similarly to the original proof:

$$ $\displaystyle\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle=$ $\displaystyle 2\lVert x^{k+1}-x^{k}\rVert^{2}-\lVert x^{k+1}-x^{k}\rVert^{2}$ (89) $\displaystyle=$ $\displaystyle-2\lambda_{k}\langle\nabla f(x^{k}),x^{k+1}-x^{k}\rangle-\lVert x ^{k+1}-x^{k}\rVert^{2}$ $\displaystyle=$ $\displaystyle 2\lambda_{k}\langle\nabla f(x^{k})-\nabla f(x^{k-1}),x^{k}-x^{k+ 1}\rangle$ $\displaystyle\quad+2\lambda_{k}\langle\nabla f(x^{k-1}),x^{k}-x^{k+1}\rangle- \lVert x^{k+1}-x^{k}\rVert^{2}.$ $$

Next, we apply Cauchy-Schwarz inequality, the definition of $\lambda_{k}$ with $\gamma=\frac{1}{4}$, and Young’s inequality to estimate the first inner-product in the right-hand side:

$$ $\displaystyle 2\lambda_{k}\langle\nabla f(x^{k})-\nabla f(x^{k-1}),x^{k}-x^{k+ 1}\rangle$ $\displaystyle\leqslant 2\lambda_{k}\lVert\nabla f(x^{k})-\nabla f(x^{k-1}) \rVert\lVert x^{k}-x^{k+1}\rVert$ $\displaystyle\leqslant\frac{1}{2}\lVert x^{k}-x^{k-1}\rVert\lVert x^{k}-x^{k+1}\rVert$ $\displaystyle\leqslant\frac{1}{4}\lVert x^{k}-x^{k-1}\rVert^{2}+\frac{1}{4} \lVert x^{k+1}-x^{k}\rVert^{2}.$ (90) $$

Then, using the convexity of $f$, we handle the second inner product from the right-hand side of (89):

$$ $\displaystyle 2\lambda_{k}\langle\nabla f(x^{k-1}),x^{k}-x^{k+1}\rangle$ $\displaystyle=\frac{2\lambda_{k}}{\lambda_{k-1}}\langle x^{k-1}-x^{k},x^{k}-x^ {k+1}\rangle$ $\displaystyle=2\lambda_{k}\theta_{k}\langle x^{k-1}-x^{k},\nabla f(x^{k})\rangle$ $\displaystyle\leqslant 2\lambda_{k}\theta_{k}(f(x^{k-1})-f(x^{k})).$ (91) $$

Plugging (F.2) and (F.2)
in (89), we get

$$ $\displaystyle\lVert x^{k+1}-x^{k}\rVert^{2}\leqslant\frac{1}{4}\lVert x^{k}-x^ {k-1}\rVert^{2}-\frac{3}{4}\lVert x^{k+1}-x^{k}\rVert^{2}+2\lambda_{k}\theta_{ k}(f(x^{k-1})-f(x^{k})).$ $$

Finally, using the above upper bound for $\lVert x^{k+1}-x^{k}\rVert^{2}$ in
(88), we obtain

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}+\Sigma_{k+1}$ $\displaystyle\leq$ $\displaystyle\|x^{k}-x^{*}\|^{2}-2\lambda_{k}(f(x^{k})-f(x^{*}))$ $\displaystyle\quad+\frac{1}{4}\lVert x^{k}-x^{k-1}\rVert^{2}-\frac{3}{4}\lVert x ^{k+1}-x^{k}\rVert^{2}+2\lambda_{k}\theta_{k}(f(x^{k-1})-f(x^{k}))$ $\displaystyle\quad+\Sigma_{k}+\frac{1}{2}\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle=$ $\displaystyle\|x^{k}-x^{*}\|^{2}+\frac{1}{4}\lVert x^{k}-x^{k-1}\rVert^{2}+2 \lambda_{k}\theta_{k}(f(x^{k-1})-f(x^{*}))+\Sigma_{k}$ $\displaystyle\quad-\frac{1}{4}\lVert x^{k+1}-x^{k}\rVert^{2}-2\lambda_{k}(1+ \theta_{k})(f(x^{k})-f(x^{*})).$ $$

Rearranging the terms, we derive (87).
∎

The above lemma implies not only the boundedness of the iterates but also the boundedness of $\sum_{i=0}^{k-1}\|x^{i+1}-x^{i}\|^{2}$ for $k\geqslant 1$.

###### Corollary F.4 .

Let Assumption 1.1 with $\mu=0$ hold, and $x^{*}$ be any minimizer of $f$. Then, the iterates generated
by Algorithm 4 with $\gamma=\frac{1}{4}$ satisfy for all $k\geqslant 1$

$$ $\lVert x^{k+1}-x^{*}\rVert^{2}\leqslant D^{2},$ (92) $$

$$ $\lVert x^{k+1}-x^{k}\rVert^{2}\leqslant 4D^{2},$ (93) $$

$$ $\sum_{i=0}^{k-1}\|x^{i+1}-x^{i}\|^{2}\leqslant 2D^{2},$ (94) $$

where $D>0$ and $D^{2}:=\lVert x^{1}-x^{*}\rVert^{2}+\frac{3}{4}\lVert x^{1}-x^{0}\rVert^{2}+2
\lambda_{1}\theta_{1}(f(x^{0})-f(x^{*}))$.

Using the above results, we derive the following theorem.

###### Theorem F.5 (Theorem 6.2 ) .

Let Assumptions 1.1 with $\mu=0$ and 1.3 hold. For all $N\geqslant 1$ we define point $\hat{x}^{N}:=\frac{1}{S_{N}}\left(\lambda_{N}(1+\theta_{N})+\sum_{k=1}^{N}w_{k
}x^{k}\right)$, where $w_{k}:=\lambda_{k}(1+\theta_{k})-\lambda_{k+1}\theta_{k+1}$, $S_{N}:=\lambda_{1}\theta_{1}+\sum_{k=1}^{N}\lambda_{k}$, and $\{x^{k}\}_{k\geqslant 0}$ are the iterates produced by AdGD with $\gamma=\nicefrac{{1}}{{4}}$. Then, for $N>\sqrt{2N}(m+1)L_{1}\exp{(2L_{1}D)}D$ iterate $\hat{x}^{N}$ satisfies

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{2L_{0}\exp(2L_{1}D)D^{2}}{N-\sqrt{2N}(m+ 1)L_{1}\exp(2L_{1}D)D},$ (95) $$

where $D>0$ and $D^{2}:=\lVert x^{1}-x^{*}\rVert^{2}+\frac{3}{4}\lVert x^{1}-x^{0}\rVert^{2}+2
\lambda_{1}\theta_{1}(f(x^{0})-f(x^{*}))$, and $m:=1+\log_{\sqrt{2}}\left\lceil\frac{(1+L_{1}D\exp{\left(2L_{1}D\right)})}{2}\right\rceil$. In particular, for $N\geqslant 8(m+1)^{2}L_{1}^{2}\exp{(4L_{1}D)}D^{2}$, we have

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{4L_{0}\exp{(2L_{1}D)}D^{2}}{N}.$ (96) $$

In addition, if Assumption 1.2 holds, one can formally replace $\exp(2L_{1}D)$ in (95) and (96) with $1$.

###### Proof.

Since we will use $(L_{0},L_{1})$-smoothness only between two consecutive iterates $x^{k},x^{k-1}$, for the sake of brevity, we unify the notation for Assumptions 1.2 and 1.3 as

$$ $\left\|\nabla f(x^{k})-\nabla f(x^{k-1})\right\|\leqslant\|x^{k}-x^{k-1}\| \left(M_{0}+M_{1}\left\|\nabla f(x^{k})\right\|\right),$ (97) $$

where $M_{0}:=L_{0}$, $M_{1}:=L_{1}$ if Assumption 1.2 holds (follows from the definition), and $M_{0}:=L_{0}\exp{\left(2L_{1}D\right)}$, $M_{1}:=L_{1}\exp{\left(2L_{1}D\right)}$ if Assumption 1.3 holds (follows from (6) and (93)).

Since(^6^66In practice $\theta_{0}$ it is sufficient to take $\theta_{0}\geqslant\frac{\lVert x^{1}-x^{0}\rVert^{2}}{16\lambda_{0}^{2}\lVert \nabla f(x^{1})-\nabla f(x^{0})\rVert^{2}}-1$.) $\theta_{0}=+\infty$, we have $\lambda_{1}=\frac{\lVert x^{1}-x^{0}\rVert}{4\lVert\nabla f(x^{1})-\nabla f(x^
{0})\rVert}$. Next, for $k>1$ we have either $\lambda_{k}=\sqrt{1+\theta_{k-1}}\lambda_{k-1}$ or $\lambda_{k}=\frac{\lVert x^{k}-x^{k-1}\rVert}{4\lVert\nabla f(x^{k})-\nabla f(
x^{k-1})\rVert}$. For convenience of the analysis of these two options, we let ${\cal K}$ be the set of indices $k>1$ such that $\lambda_{k}=\sqrt{1+\theta_{k-1}}\lambda_{k-1}$ and $\lambda_{k-1}=\frac{\lVert x^{k-1}-x^{k-2}\rVert}{4\lVert\nabla f(x^{k-1})-
\nabla f(x^{k-2})\rVert}$.

Option 1: $\lambda_{k}=\sqrt{1+\theta_{k-1}}\lambda_{k-1}$. Then, by definition of ${\cal K}$, there exists index $t$ such that $t\in{\cal K}$, $\lambda_{l}=\sqrt{1+\theta_{l-1}}\lambda_{l-1}$ for all $l\in\{t,t+1,\ldots,t+\tau-1\}$, $k\in\{t,t+1,\ldots,t+\tau-1\}$, and $\lambda_{t+\tau}=\frac{\lVert x^{t+\tau}-x^{t+\tau-1}\rVert}{4\lVert\nabla f(x
^{t+\tau})-\nabla f(x^{t+\tau-1})\rVert}$, i.e., $k$ belongs to some sub-sequence of indices such that Option 1 holds. Following exactly the same steps as in the derivation of (86), we conclude that $\lambda_{k}\geqslant\frac{1}{2M_{0}(1+DM_{1})}=:\lambda_{\text{min}}$ for any $k\geqslant 1$. Since $\theta_{l}\geqslant 1$ for all $l\in\{t,t+1,\ldots,t+\tau-1\}$, we get that $\lambda_{l}\geqslant\sqrt{2}\lambda_{l-1}\geqslant 2^{\frac{l-t}{2}}\lambda_{t
}\geqslant 2^{\frac{l-t}{2}}\lambda_{t-1}$ for $l\in\{t+1,\ldots,t+\tau-1\}$, meaning that for $l-t$ larger than $1+\log_{\sqrt{2}}\left\lceil\frac{1}{4M_{0}\lambda_{\text{min}}}\right\rceil
\leqslant 1+\log_{\sqrt{2}}\left\lceil\frac{(1+DM_{1})}{2}\right\rceil=:m$ we have $\lambda_{l}\geqslant\frac{1}{4M_{0}}$. Putting all together, we conclude that

$$ $\lambda_{l}\geqslant\begin{cases}\lambda_{t-1},&\text{for }l\in\{t,t+1,\ldots, t+m\},\\ \frac{1}{4M_{0}},&\text{for }l\in\{t+m+1,t+m+2,\ldots,t+\tau-1\}.\end{cases}$ (98) $$

Option 2: $\lambda_{k}=\frac{\lVert x^{k}-x^{k-1}\rVert}{4\lVert\nabla f(x^{k})-\nabla f(
x^{k-1})\rVert}$. Then, using (97), we get

$$ $\lambda_{k}=\frac{\lVert x^{k}-x^{k-1}\rVert}{4\lVert\nabla f(x^{k})-\nabla f( x^{k-1})\rVert}\geqslant\frac{1}{M_{0}+M_{1}\|\nabla f(x^{k})\|}=\frac{\lambda _{k}}{4\left(\lambda_{k}M_{0}+M_{1}\lVert x^{k+1}-x^{k}\rVert\right)},$ $$

implying that

$$ $\lambda_{k}\geqslant\frac{1}{4M_{0}}-\frac{M_{1}}{4M_{0}}\lVert x^{k+1}-x^{k}\rVert.$ (99) $$

To continue the proof, we split the set of indices $\{1,2,\ldots,N\}$ into three disjoint sets ${\cal T}_{1},{\cal T}_{2},{\cal T}_{3}$ defined as follows: ${\cal T}_{2}:=\left\{k\in\{1,2,\ldots,N\}\mid\lambda_{k}=\frac{\lVert x^{k}-x^
{k-1}\rVert}{4\lVert\nabla f(x^{k})-\nabla f(x^{k-1})\rVert}\right\}$,
${\cal T}_{1}:=\left\{k\in\{1,2,\ldots,N\}\mid\lambda_{k}=\sqrt{1+\theta_{k-1}}
\lambda_{k-1}\text{ and }\exists t\in{\cal K}\text{ such that }t\leqslant k
\leqslant t+m\right\}$, and ${\cal T}_{3}:=\{1,2,\ldots,N\}\setminus({\cal T}_{1}\cup{\cal T}_{2})$. Then, taking into account the lower bounds (98) and (99), we have $\forall k\in\{1,2,\ldots,N\}$

$$ $\displaystyle\lambda_{k}$ $\displaystyle\geqslant$ $\displaystyle\begin{cases}\lambda_{t-1},&\text{if }k\in{\cal T}_{1}\text{, where }t\in{\cal K}\text{ and }0\leqslant k-t\leqslant m,\\ \frac{1}{4M_{0}}-\frac{M_{1}}{4M_{0}}\lVert x^{k+1}-x^{k}\rVert,&\text{if }k \in{\cal T}_{2},\\ \frac{1}{4M_{0}},&\text{if }k\in{\cal T}_{3},\end{cases}$ $\displaystyle\overset{t-1\in{\cal T}_{2},\eqref{eq:lower_bound_lambda_AdGD_ option_2}}{\geqslant}$ $\displaystyle\begin{cases}\frac{1}{4M_{0}}-\frac{M_{1}}{4M_{0}}\lVert x^{t}-x^ {t-1}\rVert,&\text{if }k\in{\cal T}_{1}\text{, where }t\in{\cal K}\text{ and } 0\leqslant k-t\leqslant m,\\ \frac{1}{4M_{0}}-\frac{M_{1}}{4M_{0}}\lVert x^{k+1}-x^{k}\rVert,&\text{if }k \in{\cal T}_{2},\\ \frac{1}{4M_{0}},&\text{if }k\in{\cal T}_{3}.\end{cases}$ $$

Therefore, we can lower bound the sum of stepsizes as follows:

$$ $\displaystyle\sum_{k=1}^{N}\lambda_{k}$ $\displaystyle\geqslant$ $\displaystyle\frac{N}{4M_{0}}-\frac{M_{1}}{4M_{0}}\sum\limits_{k\in{\cal T}_{2 }}\|x^{k+1}-x^{k}\|-\frac{mM_{1}}{4M_{0}}\sum\limits_{t\in{\cal T}_{2}:t+1\in{ \cal K}}\|x^{t+1}-x^{t}\|$ (100) $\displaystyle\geqslant$ $\displaystyle\frac{N}{4M_{0}}-\frac{(m+1)M_{1}}{4M_{0}}\sum\limits_{k\in{\cal T }_{2}}\|x^{k+1}-x^{k}\|$ $\displaystyle\geqslant$ $\displaystyle\frac{N}{4M_{0}}-\frac{(m+1)M_{1}}{4M_{0}}\sum\limits_{k=0}^{N}\| x^{k+1}-x^{k}\|$ $\displaystyle\geqslant$ $\displaystyle\frac{N}{4M_{0}}-\frac{(m+1)M_{1}}{4M_{0}}\sqrt{N\sum\limits_{k=0 }^{N}\|x^{k+1}-x^{k}\|^{2}}$ $\displaystyle\overset{\eqref{eq:series_bound}}{\geqslant}$ $\displaystyle\frac{N}{4M_{0}}-\frac{\sqrt{2N}(m+1)M_{1}D}{4M_{0}}.$ $$

Since $S_{N}\geqslant\sum_{k=1}^{N}\lambda_{k}$ (see the definition in (84)) we have from (85) and the above lower bound on $\sum_{k=1}^{N}\lambda_{k}$ that

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{D^{2}}{2S_{N}}\overset{\eqref{eq:sum_ lambda_k_lower_bound}}{\leqslant}\frac{2M_{0}D^{2}}{N-\sqrt{2N}(m+1)M_{1}D},$ $$

which gives

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{2L_{0}\exp(2L_{1}D)D^{2}}{N-\sqrt{2N}(m+ 1)L_{1}\exp(2L_{1}D)D},$ (101) $$

when Assumption 1.3 holds, and

$$ $f(\hat{x}^{N})-f(x^{*})\leqslant\frac{2L_{0}D^{2}}{N-\sqrt{2N}(m+1)L_{1}D},$ $$

when Assumption 1.2 is satisfied. In particular, we derived (95) under Assumption 1.3 holds, and when $N\geqslant 8(m+1)^{2}L_{1}^{2}\exp(4L_{1}D)D^{2}$, we have $N-\sqrt{2N}(m+1)L_{1}\exp(2L_{1}D)D\geqslant\frac{N}{2}$, which in combination with (101) implies (96).

∎

###### Lemma F.3 .

###### Proof.

###### Corollary F.4 .

###### Theorem F.5 (Theorem 6.2 ) .

###### Proof.

### F.3 Convergence in the Strongly Convex Case

To show an improved result in the strongly convex case ($\mu>0$ in Assumptions 1.1), we consider Algorithm 4 with more a more conservative stepsize selection rule:

$$ $\lambda_{k}=\min\left\{\sqrt{1+\frac{3\theta_{k-1}}{4}}\lambda_{k-1},\frac{ \lVert x^{k}-x^{k-1}\rVert}{4\lVert\nabla f(x^{k})-\nabla f(x^{k-1})\rVert} \right\}.$ (102) $$

For these stepsizes, Lemma F.3 holds as well. However, in contrast to the convex case, we will use Assumption 1.2 instead of Assumption 1.3. The key reason for this is that we need to use (10) for $x=x^{k}$ and $y=x^{*}$ that not necessarily satisfy (9). In contrast, inequality (10) holds for any $x,y\in\mathbb{R}^{d}$ under the Assumption 1.2 and convexity.

###### Theorem F.6 .

Let Assumptions 1.1 with $\mu>0$ and 1.2 hold. For all $N\geqslant 1$ we define the Lyapunov function

$$ $\displaystyle\Psi_{k}$ $\displaystyle=$ $\displaystyle\left(1-\frac{\lambda_{k}\mu}{4}\right)\left\|x^{k}-x^{*}\right\| ^{2}+\frac{1}{4}\left(1+(1-\alpha^{*})\frac{8\mu}{L_{0}}\right)\left\|x^{k}-x^ {k-1}\right\|^{2}$ $\displaystyle\quad+2\lambda_{k}\theta_{k}(f(x^{k-1})-f_{*}),$ $$

where $\{x^{k}\}_{k\geqslant 0}$ are the iterates produced by AdGD with $\lambda_{k}$ defined in (102), and $\alpha^{*}=\frac{73-\sqrt{3281}}{16}\approx 0.98$.
Then, for $N>\sqrt{2N}(m+1)L_{1}D$ Lyapunov function $\Psi_{N+1}$ satisfies

$$ $\Psi_{N+1}\leq\left(1-\frac{\alpha^{*}\mu}{8L_{0}}+\frac{\alpha^{*}\mu(m+1)L_{ 1}D}{4\sqrt{2N}L_{0}}\right)^{N}\Psi_{1},$ (103) $$

where $D>0$ and $D^{2}:=\lVert x^{1}-x^{*}\rVert^{2}+\frac{3}{4}\lVert x^{1}-x^{0}\rVert^{2}+2
\lambda_{1}\theta_{1}(f(x^{0})-f(x^{*}))$, and $m:=1+\log_{\sqrt{\frac{7}{4}}}\left\lceil\frac{1+L_{1}D}{2}\right\rceil$. In particular, for $N\geqslant 8(m+1)^{2}L_{1}^{2}D^{2}$, we have

$$ $\Psi_{N+1}\leq\left(1-\frac{\alpha^{*}\mu}{16L_{0}}\right)^{N}\Psi_{1}.$ (104) $$

###### Proof.

The proof follows the one from (Malitsky and Mishchenko,, ). First of all, we note that the stricter inequality $\lambda_{k}\leqslant\sqrt{1+\frac{3\theta_{k-1}}{4}}\lambda_{k-1}$ is not used in the derivation of Lemma F.3. Therefore, Lemma F.3 holds as well as Corollary F.4. Next, we make certain steps in the analysis tighter to use the fact that $\mu>0$. Strong convexity implies

$$ $\displaystyle\lambda_{k}\langle\nabla f(x^{k}),x^{*}-x^{k}\rangle$ $\displaystyle\leqslant\lambda_{k}(f(x^{*})-f(x^{k}))-\lambda_{k}\frac{\mu}{2} \|x^{*}-x^{k}\|^{2},$ (105) $$

and
$\left\|\nabla f(x^{k})-\nabla f(x^{k-1})\right\|\geqslant\mu\left\|x^{k}-x^{k-
1}\right\|$. The latter implies
that $\lambda_{k}\leqslant\frac{1}{4\mu}$ for $k\geqslant 1$. Since Lemma 2.2 holds under Assumption 1.2 with $\nu=1$ and without condition (9), and bound $\lambda_{k}\leq\frac{1}{4\mu}$ holds, we have

$$ $\displaystyle\lambda_{k}\langle\nabla f(x^{k}),x^{*}-x^{k}\rangle$ $\displaystyle\overset{\eqref{eq:grad_difference_bound_through_bregman_div}}{\leqslant}$ $\displaystyle\lambda_{k}(f(x^{*})-f(x^{k}))-\frac{\lambda_{k}}{2(L_{0}+L_{1}\| \nabla f(x^{*})\|)}\|\nabla f(x^{k})\|^{2}$ (106) $\displaystyle=$ $\displaystyle\lambda_{k}(f_{*}-f(x^{k}))-\frac{1}{2L_{0}\lambda_{k}}\|x^{k+1}- x^{k}\|^{2}$ $\displaystyle\overset{\lambda_{k}\leq\frac{1}{4\mu}}{\leq}$ $\displaystyle\lambda_{k}(f_{*}-f(x^{k}))-\frac{2\mu}{L_{0}}\|x^{k+1}-x^{k}\|^{ 2}.$ $$

Convex combination of (105) and (106) with $\alpha\in(0,1)$, which will be specified latter, gives

$$ $\displaystyle\lambda_{k}\langle\nabla f(x^{k}),x^{*}-x^{k}\rangle\leqslant \lambda_{k}(f_{*}-f(x^{k}))-\alpha\frac{\lambda_{k}\mu}{2}\|x^{k}-x^{*}\|^{2}- (1-\alpha)\frac{2\mu}{L_{0}}\|x^{k+1}-x^{k}\|^{2}.$ $$

Using the above inequality instead of convexity and keeping the rest of the proof of Lemma F.3 as is with omitted $\Sigma_{i}$ terms, we get an analog of (77):

$$ $\displaystyle\left\|x^{k+1}-x^{*}\right\|^{2}+\frac{1}{4}\left(1+(1-\alpha) \frac{8\mu}{L_{0}}\right)\left\|x^{k+1}-x^{k}\right\|^{2}+\frac{1+\theta_{k}}{ 1+3\theta_{k}/4}\cdot 2\lambda_{k+1}\theta_{k+1}(f(x^{k})-f_{*})$ $\displaystyle\leqslant$ $\displaystyle\left\|x^{k+1}-x^{*}\right\|^{2}+\frac{1}{4}\left(1+(1-\alpha) \frac{8\mu}{L_{0}}\right)\left\|x^{k+1}-x^{k}\right\|^{2}+2\lambda_{k}(1+ \theta_{k})(f(x^{k})-f_{*})$ $\displaystyle\leqslant$ $\displaystyle\left(1-\alpha\frac{\lambda_{k}\mu}{2}\right)\left\|x^{k}-x^{*} \right\|^{2}+\frac{1}{4}\left\|x^{k}-x^{k-1}\right\|^{2}+2\lambda_{k}\theta_{k }(f(x^{k-1})-f_{*}),$ $$

where the first inequality follows from $\frac{1+\theta_{k}}{1+3\theta_{k}/4}\lambda_{k+1}\theta_{k+1}\leqslant\lambda_
{k}(1+\theta_{k})$ provided by the new condition on $\lambda_{k}$. Thus, we have contraction in every term: $1-\alpha\frac{\lambda_{k}\mu}{2}$ in the first, $\frac{1}{1+(1-\alpha)\frac{8\mu}{L_{0}}}=1-\frac{(1-\alpha)\frac{8\mu}{L_{0}}}
{1+(1-\alpha)\frac{8\mu}{L_{0}}}$ in the second and $\frac{1+3\theta_{k}/4}{1+\theta_{k}}=1-\frac{\theta_{k}}{4(1+\theta_{k})}$
in the last one. We bound the third term as $\frac{\theta_{k}}{4(1+\theta_{k})}=\frac{1}{4}\cdot\frac{\lambda_{k}}{(\lambda
_{k}+\lambda_{k-1})}\geqslant\frac{\mu\lambda_{k}}{2}$ using $\lambda_{k}\leqslant\frac{1}{4\mu}$ for both terms in the denominator. Taking $\alpha=\alpha^{*}:=\frac{73-\sqrt{3281}}{16}\approx 0.98$, which is the root of $\alpha^{*}=\frac{64(1-\alpha^{*})}{1+8(1-\alpha^{*})}$, we bound the second term as $\frac{(1-\alpha)\frac{8\mu}{L_{0}}}{\left(1+(1-\alpha)\frac{8\mu}{L_{0}}\right
)}\geqslant\frac{\mu}{4L_{0}}\cdot\frac{32(1-\alpha)}{1+8(1-\alpha)}\overset{
\alpha=\alpha^{*}}{=}\alpha^{*}\frac{\mu}{8L_{0}}$. Therefore, for $\Psi_{k}=\left(1-\frac{\lambda_{k}\mu}{4}\right)\left\|x^{k}-x^{*}\right\|^{2}
+\frac{1}{4}\left(1+(1-\alpha^{*})\frac{8\mu}{L_{0}}\right)\left\|x^{k}-x^{k-1
}\right\|^{2}+2\lambda_{k}\theta_{k}(f(x^{k-1})-f_{*})$
we have

$$ $\Psi_{k+1}\leq\left(1-\frac{\alpha^{*}\mu}{2}\min\left\{\lambda_{k},\frac{1}{4 L_{0}}\right\}\right)\Psi_{k}.$ (107) $$

The final step of the proof is unrolling the recursion for Lyapunov function $\Psi_{k}$. Following the proof of Theorem F.5, we have that

$$ $\displaystyle\min\left\{\lambda_{k},\frac{1}{4L_{0}}\right\}$ $\displaystyle\geqslant$ $\displaystyle\begin{cases}\frac{1}{4L_{0}}-\frac{L_{1}}{4L_{0}}\lVert x^{t}-x^ {t-1}\rVert,&\text{if }k\in{\cal T}_{1}\text{, where }t\in{\cal K}\text{ and } 0\leqslant k-t\leqslant m,\\ \frac{1}{4L_{0}}-\frac{L_{1}}{4L_{0}}\lVert x^{k+1}-x^{k}\rVert,&\text{if }k \in{\cal T}_{2},\\ \frac{1}{4L_{0}},&\text{if }k\in{\cal T}_{3}.\end{cases}$ (108) $$

with $m:=1+\log_{\sqrt{\frac{7}{4}}}\left\lceil\frac{(1+DL_{1})}{2}\right\rceil$, which differs from $m$ defined in the convex case due to the new condition on $\lambda_{k}$.
Therefore, by repeating all the steps from the proof of (100),
we obtain

$$ $\displaystyle\sum_{k=1}^{N}\min\left\{\lambda_{k},\frac{1}{4L_{0}}\right\}$ $\displaystyle\geqslant$ $\displaystyle\frac{N}{4L_{0}}-\frac{\sqrt{2N}(m+1)L_{1}D}{4L_{0}}.$ (109) $$

Next, we bound the product that arises during recursion unrolling by using the relation between the geometric mean and the arithmetic mean:

$$ $\displaystyle\prod_{k=1}^{N}\left(1-\frac{\alpha^{*}\mu}{2}\min\left\{\lambda_ {k},\frac{1}{4L_{0}}\right\}\right)$ $\displaystyle\leqslant$ $\displaystyle\left(1-\frac{\alpha^{*}\mu}{2}\frac{1}{N}\sum_{k=1}^{N}\min\left \{\lambda_{k},\frac{1}{4L_{0}}\right\}\right)^{N}$ (110) $\displaystyle\overset{\eqref{eq:sum_mins_lower_bound}}{\leqslant}$ $\displaystyle\left(1-\frac{\alpha^{*}\mu}{8L_{0}}+\frac{\alpha^{*}\mu(m+1)L_{1 }D}{4\sqrt{2N}L_{0}}\right)^{N}.$ $$

Finally, we combine (107) and (110) and get

$$ $\displaystyle\Psi_{N+1}$ $\displaystyle\overset{\eqref{eq:AdGD_Lyapunov_contraction}}{\leq}$ $\displaystyle\prod_{k=1}^{N}\left(1-\frac{\alpha^{*}\mu}{2}\min\left\{\lambda_ {k},\frac{1}{4L_{0}}\right\}\right)\Psi_{1}$ $\displaystyle\overset{\eqref{eq:AdGD_product_bound}}{\leq}$ $\displaystyle\left(1-\frac{\alpha^{*}\mu}{8L_{0}}+\frac{\alpha^{*}\mu(m+1)L_{1 }D}{4\sqrt{2N}L_{0}}\right)^{N}\Psi_{1}.$ $$

Moreover, when $N\geqslant 8(m+1)^{2}L_{1}^{2}D^{2}$, we have $\frac{\alpha^{*}\mu(m+1)L_{1}D}{4\sqrt{2N}L_{0}}\leqslant\frac{\alpha^{*}\mu}{
16L_{0}}$, which in combination with the above inequality implies (104).

∎

###### Theorem F.6 .

###### Proof.

## Appendix G Stochastic Extensions: Missing Proofs and Details

### G.1 ( L 0 , L 1 ) subscript 𝐿 0 subscript 𝐿 1 (L_{0},L_{1}) ( italic_L start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_L start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) -Stochastic Gradient Descent

###### Theorem G.1 (Theorem 7.2 ) .

Let Assumption 7.1 hold. Then, the iterates generated by $(L_{0},L_{1})$-SGD with $0<\eta\leqslant\frac{\nu}{2}$, $\nu=e^{-\nu}$
after $N$ iterations satisfy

$$ $\min\limits_{k=0,\ldots,N}\mathbb{E}\left[\min\left\{\frac{\nu L_{0}}{4nL_{1}^ {2}},f(x^{k})-f(x^{*})\right\}\right]\leqslant\frac{2L_{0}\|x^{0}-x^{*}\|^{2}} {\eta(N+1)}.$ (111) $$

###### Proof.

Similarly to the deterministic case, we start by expanding the squared distance $x^{*}$, which is a common minimizer for all $\{f_{i}\}_{i=1}^{n}$:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle=$ $\displaystyle\left\|x^{k}-x^{*}-\frac{\eta}{L_{0}+L_{1}\|\nabla f_{\xi^{k}}(x^ {k})\|}\nabla f_{\xi^{k}}(x^{k})\right\|^{2}$ (112) $\displaystyle=$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{2\eta}{L_{0}+L_{1}\|\nabla f_{\xi^{k}}( x^{k})\|}\langle x^{k}-x^{*},\nabla f_{\xi^{k}}(x^{k})\rangle$ $\displaystyle\quad+\frac{\eta^{2}\|\nabla f_{\xi^{k}}(x^{k})\|^{2}}{(L_{0}+L_{ 1}\|\nabla f_{\xi^{k}}(x^{k})\|)^{2}}$ $\displaystyle\overset{\eqref{eq:convexity}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{2\eta}{L_{0}+L_{1}\|\nabla f_{\xi^{k}}( x^{k})\|}\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})\right)$ $\displaystyle\quad+\frac{\eta^{2}\|\nabla f_{\xi^{k}}(x^{k})\|^{2}}{(L_{0}+L_{ 1}\|\nabla f_{\xi^{k}}(x^{k})\|)^{2}}$ $\displaystyle\overset{\eqref{eq:sym_gradient_bound}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-2\eta\left(1-\frac{\eta}{\nu}\right)\frac{f_{ \xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})}{L_{0}+L_{1}\|\nabla f_{\xi^{k}}(x^{k})\|}$ $\displaystyle\overset{\eta\leqslant\frac{\nu}{2}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\eta\frac{f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{* })}{L_{0}+L_{1}\|\nabla f_{\xi^{k}}(x^{k})\|}.$ $$

As before, we consider two possible cases: $\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$ or $\|\nabla f_{\xi^{k}}(x^{k})\|<\frac{L_{0}}{L_{1}}$.

Case 1: $\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$. In this case, we have

$$ $\displaystyle L_{0}+L_{1}\|\nabla f_{\xi^{k}}(x^{k})\|\leqslant 2L_{1}\|\nabla f _{\xi^{k}}(x^{k})\|,$ (113) $\displaystyle\frac{\nu\|\nabla f_{\xi^{k}}(x^{k})\|}{4L_{1}}\overset{\eqref{eq :case_1_main_ineq_asym_L0_L1_SGD}}{\leqslant}\frac{\nu\|\nabla f_{\xi^{k}}(x^{ k})\|^{2}}{2(L_{0}+L_{1}\|\nabla f_{\xi^{k}}(x^{k})\|)}\overset{\eqref{eq:sym_ gradient_bound}}{\leqslant}f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*}).$ (114) $$

Plugging the above inequalities in (112), we continue the derivation as follows:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:descent_inequality_asym_case_sgd},\eqref{eq: case_1_main_ineq_asym_L0_L1_SGD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\eta\frac{f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{* })}{2L_{1}\|\nabla f_{\xi^{k}}(x^{k})\|}$ (115) $\displaystyle\overset{\eqref{eq:case_1_grad_bound_asym_L0_L1_SGD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu\eta}{8L_{1}^{2}}.$ $$

Case 2: $\|\nabla f_{\xi^{k}}(x^{k})\|<\frac{L_{0}}{L_{1}}$. In this case, we have

$$ $\displaystyle L_{0}+L_{1}\|\nabla f_{\xi^{k}}(x^{k})\|\leqslant 2L_{0},$ (116) $$

implying that

$$ $\|x^{k+1}-x^{*}\|^{2}\overset{\eqref{eq:descent_inequality_asym_case},\eqref{ eq:case_2_main_ineq_asym_L0_L1_SGD}}{\leqslant}\|x^{k}-x^{*}\|^{2}-\frac{\eta} {2L_{0}}\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})\right).$ (117) $$

To combine (115) and (117), we introduce event $E(x^{k}):=\left\{\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}\mid
x
^{k}\right\}$ for given $x^{k}$ and indicator of event $E(x^{k})$ as $\mathbbm{1}_{E(x^{k})}$, i.e., for given $x^{k}$, we have $\mathbbm{1}_{E(x^{k})}=1$ if $\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$, and $\mathbbm{1}_{E(x^{k})}=0$ if $\|\nabla f_{\xi^{k}}(x^{k})\|<\frac{L_{0}}{L_{1}}$. Then, inequalities (115) and (117) can be unified as follows:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}\leqslant\|x^{k}-x^{*}\|^{2}-\mathbbm{1}_{E( x^{k})}\cdot\frac{\nu\eta}{8L_{1}^{2}}-(1-\mathbbm{1}_{E(x^{k})})\cdot\frac{ \eta}{2L_{0}}\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})\right).$ $$

Let us denote the expectation conditioned on $x^{k}$ as $\mathbb{E}_{k}[\cdot]:=\mathbb{E}[\cdot\mid x^{k}]$. Taking $\mathbb{E}_{k}[\cdot]$ from the both sides of the above inequality, we derive

$$ $\displaystyle\mathbb{E}_{k}\left[\|x^{k+1}-x^{*}\|^{2}\right]$ $\displaystyle\leqslant$ $\displaystyle\|x^{k}-x^{*}\|^{2}-p_{k}\cdot\frac{\nu\eta}{8L_{1}^{2}}$ $\displaystyle\quad-\mathbb{E}_{k}\left[(1-\mathbbm{1}_{E(x^{k})})\cdot\frac{ \eta}{2L_{0}}\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})\right)\right],$ $$

where $p_{k}:=\mathbb{P}\left\{\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{
1}}\mid x^{k}\right\}=\mathbb{P}\{E(x^{k})\}=\mathbb{E}_{k}[\mathbbm{1}_{E(x^{
k})}]$. Note that $p_{k}$ is a random variable itself. Nevertheless, if $p_{k}>0$, it means that for at least one $\xi^{k}\in\{1,\ldots,n\}$ we have $\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$ for given $x^{k}$. Therefore, either $p_{k}\geqslant\frac{1}{n}$ or $p_{k}=0$. Moreover, when $p_{k}=0$, we have $1-\mathbbm{1}_{E(x^{k})}:=1$ for given $x^{k}$. Putting all together, we continue as follows:

$$ $\displaystyle\mathbb{E}_{k}\left[\|x^{k+1}-x^{*}\|^{2}\right]$ $\displaystyle\leqslant$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\mathbbm{1}_{\{p_{k}>0\}}\cdot p_{k}\cdot \frac{\nu\eta}{8L_{1}^{2}}$ $\displaystyle\quad-\mathbbm{1}_{\{p_{k}=0\}}\cdot\mathbb{E}_{k}\left[(1- \mathbbm{1}_{E(x^{k})})\cdot\frac{\eta}{2L_{0}}\left(f_{\xi^{k}}(x^{k})-f_{\xi ^{k}}(x^{*})\right)\right],$ $\displaystyle=$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\mathbbm{1}_{\{p_{k}>0\}}\cdot p_{k}\cdot \frac{\nu\eta}{8L_{1}^{2}}-\mathbbm{1}_{\{p_{k}=0\}}\cdot\frac{\eta}{2L_{0}} \left(f(x^{k})-f(x^{*})\right)$ $\displaystyle\leqslant$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\mathbbm{1}_{\{p_{k}>0\}}\cdot\frac{\nu\eta}{ 8nL_{1}^{2}}-\mathbbm{1}_{\{p_{k}=0\}}\cdot\frac{\eta}{2L_{0}}\left(f(x^{k})-f (x^{*})\right)$ $\displaystyle\leqslant$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\min\left\{\frac{\nu\eta}{8nL_{1}^{2}},\frac{ \eta}{2L_{0}}\left(f(x^{k})-f(x^{*})\right)\right\}.$ $$

Taking full expectation from the above inequality and telescoping the result, we get

$$ $\displaystyle\sum\limits_{k=0}^{N}\mathbb{E}\left[\min\left\{\frac{\nu\eta}{8 nL_{1}^{2}},\frac{\eta}{2L_{0}}\left(f(x^{k})-f(x^{*})\right)\right\}\right]$ $\displaystyle\leqslant$ $\displaystyle\sum\limits_{k=0}^{N+1}(\mathbb{E}[\|x^{k+1}-x^{*}\|^{2}]-\mathbb {E}[\|x^{k}-x^{*}\|^{2}])$ $\displaystyle\leqslant$ $\displaystyle\|x^{0}-x^{*}\|^{2}.$ $$

Since $\frac{\eta(N+1)}{2L_{0}}\min\limits_{k=0,\ldots,N}\mathbb{E}\left[\min\left\{
\frac{\nu L_{0}}{4nL_{1}^{2}},f(x^{k})-f(x^{*})\right\}\right]$ is not greater than
$\sum\limits_{k=0}^{N}\mathbb{E}\left[\min\left\{\frac{\nu\eta}{8nL_{1}^{2}},
\frac{\eta}{2L_{0}}\left(f(x^{k})-f(x^{*})\right)\right\}\right]$, we also have

$$ $\displaystyle\frac{\eta(N+1)}{2L_{0}}\min\limits_{k=0,\ldots,N}\mathbb{E}\left [\min\left\{\frac{\nu L_{0}}{4nL_{1}^{2}},f(x^{k})-f(x^{*})\right\}\right]$ $\displaystyle\leqslant$ $\displaystyle\|x^{0}-x^{*}\|^{2}.$ $$

Dividing both sides by $\frac{\eta(N+1)}{2L_{0}}$, we obtain (111).
∎

###### Theorem G.1 (Theorem 7.2 ) .

###### Proof.

### G.2 Stochastic Gradient Descent with Polyak Stepsizes

###### Theorem G.2 (Theorem 7.3 ) .

Let Assumption 7.1 hold. Then, the iterates generated by SGD-PS
after $N$ iterations satisfy

$$ $\min\limits_{k=0,\ldots,N}\mathbb{E}\left[\min\left\{\frac{\nu L_{0}}{4nL_{1}^ {2}},f(x^{k})-f(x^{*})\right\}\right]\leqslant\frac{4L_{0}\|x^{0}-x^{*}\|^{2}} {\nu(N+1)}.$ (118) $$

###### Proof.

Similarly to the deterministic case, we start by expanding the squared distance $x^{*}$, which is a common minimizer for all $\{f_{i}\}_{i=1}^{n}$:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle=$ $\displaystyle\left\|x^{k}-x^{*}-\frac{f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})}{ \|\nabla f_{\xi^{k}}(x^{k})\|^{2}}\nabla f_{\xi^{k}}(x^{k})\right\|^{2}$ (119) $\displaystyle=$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{2\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x ^{*})\right)}{\|\nabla f_{\xi^{k}}(x^{k})\|^{2}}\langle x^{k}-x^{*},\nabla f_{ \xi^{k}}(x^{k})\rangle$ $\displaystyle\quad+\frac{\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})\right)^{2 }}{\|\nabla f_{\xi^{k}}(x^{k})\|^{2}}$ $\displaystyle\overset{\eqref{eq:convexity}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^ {*})\right)^{2}}{\|\nabla f_{\xi^{k}}(x^{k})\|^{2}}$ $\displaystyle\overset{\eqref{eq:sym_gradient_bound}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu}{2}\cdot\frac{f_{\xi^{k}}(x^{k})-f_ {\xi^{k}}(x^{*})}{L_{0}+L_{1}\|\nabla f_{\xi^{k}}(x^{k})\|}.$ $$

As before, we consider two possible cases: $\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$ or $\|\nabla f_{\xi^{k}}(x^{k})\|<\frac{L_{0}}{L_{1}}$.

Case 1: $\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$. In this case, inequalities (113) and (114) hold and the derivation from (119) can be continued as follows:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:descent_inequality_SGD_PS},\eqref{eq:case_1_ main_ineq_asym_L0_L1_SGD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu}{2}\cdot\frac{f_{\xi^{k}}(x^{k})-f_ {\xi^{k}}(x^{*})}{2L_{1}\|\nabla f_{\xi^{k}}(x^{k})\|}$ (120) $\displaystyle\overset{\eqref{eq:case_1_grad_bound_asym_L0_L1_SGD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu^{2}}{16L_{1}^{2}},$ $$

which gives (56).

Case 2: $\|\nabla f_{\xi^{k}}(x^{k})\|<\frac{L_{0}}{L_{1}}$. In this case, inequality (116) holds and we have

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\overset{\eqref{eq:descent_inequality_SGD_PS},\eqref{eq:case_2_ main_ineq_asym_L0_L1_SGD}}{\leqslant}$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\frac{\nu}{2}\cdot\frac{f_{\xi^{k}}(x^{k})-f_ {\xi^{k}}(x^{*})}{2L_{0}}.$ (121) $$

To combine (120) and (121), we introduce event $E(x^{k}):=\left\{\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}\mid
x
^{k}\right\}$ for given $x^{k}$ and indicator of event $E(x^{k})$ as $\mathbbm{1}_{E(x^{k})}$, i.e., for given $x^{k}$, we have $\mathbbm{1}_{E(x^{k})}=1$ if $\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$, and $\mathbbm{1}_{E(x^{k})}=0$ if $\|\nabla f_{\xi^{k}}(x^{k})\|<\frac{L_{0}}{L_{1}}$. Then, inequalities (120) and (121) can be unified as follows:

$$ $\displaystyle\|x^{k+1}-x^{*}\|^{2}\leqslant\|x^{k}-x^{*}\|^{2}-\mathbbm{1}_{E( x^{k})}\cdot\frac{\nu^{2}}{16L_{1}^{2}}-(1-\mathbbm{1}_{E(x^{k})})\cdot\frac{ \nu}{4L_{0}}\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})\right).$ $$

Let us denote the expectation conditioned on $x^{k}$ as $\mathbb{E}_{k}[\cdot]:=\mathbb{E}[\cdot\mid x^{k}]$. Taking $\mathbb{E}_{k}[\cdot]$ from the both sides of the above inequality, we derive

$$ $\displaystyle\mathbb{E}_{k}\left[\|x^{k+1}-x^{*}\|^{2}\right]$ $\displaystyle\leqslant$ $\displaystyle\|x^{k}-x^{*}\|^{2}-p_{k}\cdot\frac{\nu^{2}}{16L_{1}^{2}}$ $\displaystyle\quad-\mathbb{E}_{k}\left[(1-\mathbbm{1}_{E(x^{k})})\cdot\frac{ \nu}{4L_{0}}\left(f_{\xi^{k}}(x^{k})-f_{\xi^{k}}(x^{*})\right)\right],$ $$

where $p_{k}:=\mathbb{P}\left\{\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{
1}}\mid x^{k}\right\}=\mathbb{P}\{E(x^{k})\}=\mathbb{E}_{k}[\mathbbm{1}_{E(x^{
k})}]$. Note that $p_{k}$ is a random variable itself. Nevertheless, if $p_{k}>0$, it means that for at least one $\xi^{k}\in\{1,\ldots,n\}$ we have $\|\nabla f_{\xi^{k}}(x^{k})\|\geqslant\frac{L_{0}}{L_{1}}$ for given $x^{k}$. Therefore, either $p_{k}\geqslant\frac{1}{n}$ or $p_{k}=0$. Moreover, when $p_{k}=0$, we have $1-\mathbbm{1}_{E(x^{k})}:=1$ for given $x^{k}$. Putting all together, we continue as follows:

$$ $\displaystyle\mathbb{E}_{k}\left[\|x^{k+1}-x^{*}\|^{2}\right]$ $\displaystyle\leqslant$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\mathbbm{1}_{\{p_{k}>0\}}\cdot p_{k}\cdot \frac{\nu^{2}}{16L_{1}^{2}}$ $\displaystyle\quad-\mathbbm{1}_{\{p_{k}=0\}}\cdot\mathbb{E}_{k}\left[(1- \mathbbm{1}_{E(x^{k})})\cdot\frac{\nu}{4L_{0}}\left(f_{\xi^{k}}(x^{k})-f_{\xi^ {k}}(x^{*})\right)\right],$ $\displaystyle=$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\mathbbm{1}_{\{p_{k}>0\}}\cdot p_{k}\cdot \frac{\nu^{2}}{16L_{1}^{2}}-\mathbbm{1}_{\{p_{k}=0\}}\cdot\frac{\nu}{4L_{0}} \left(f(x^{k})-f(x^{*})\right)$ $\displaystyle\leqslant$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\mathbbm{1}_{\{p_{k}>0\}}\cdot\frac{\nu^{2}}{ 16nL_{1}^{2}}-\mathbbm{1}_{\{p_{k}=0\}}\cdot\frac{\nu}{4L_{0}}\left(f(x^{k})-f (x^{*})\right)$ $\displaystyle\leqslant$ $\displaystyle\|x^{k}-x^{*}\|^{2}-\min\left\{\frac{\nu^{2}}{16nL_{1}^{2}},\frac {\nu}{4L_{0}}\left(f(x^{k})-f(x^{*})\right)\right\}.$ $$

Taking full expectation from the above inequality and telescoping the result, we get

$$ $\displaystyle\sum\limits_{k=0}^{N}\mathbb{E}\left[\min\left\{\frac{\nu^{2}}{16 nL_{1}^{2}},\frac{\nu}{4L_{0}}\left(f(x^{k})-f(x^{*})\right)\right\}\right]$ $\displaystyle\leqslant$ $\displaystyle\sum\limits_{k=0}^{N+1}(\mathbb{E}[\|x^{k+1}-x^{*}\|^{2}]-\mathbb {E}[\|x^{k}-x^{*}\|^{2}])$ $\displaystyle\leqslant$ $\displaystyle\|x^{0}-x^{*}\|^{2}.$ $$

Since $\frac{\nu(N+1)}{4L_{0}}\min\limits_{k=0,\ldots,N}\mathbb{E}\left[\min\left\{
\frac{\nu L_{0}}{4nL_{1}^{2}},f(x^{k})-f(x^{*})\right\}\right]$ is not greater than
$\sum\limits_{k=0}^{N}\mathbb{E}\left[\min\left\{\frac{\nu^{2}}{16nL_{1}^{2}},
\frac{\nu}{4L_{0}}\left(f(x^{k})-f(x^{*})\right)\right\}\right]$, we also have

$$ $\displaystyle\frac{\nu(N+1)}{4L_{0}}\min\limits_{k=0,\ldots,N}\mathbb{E}\left[ \min\left\{\frac{\nu L_{0}}{4nL_{1}^{2}},f(x^{k})-f(x^{*})\right\}\right]$ $\displaystyle\leqslant$ $\displaystyle\|x^{0}-x^{*}\|^{2}.$ $$

Dividing both sides by $\frac{\nu(N+1)}{4L_{0}}$, we obtain (118).
∎

###### Theorem G.2 (Theorem 7.3 ) .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 1
initial_rating: 5
presentation: 3
questions: **Typos and minor suggestions:**

Line 203: Since you cite the conference version rather than the arXiv version of the paper, please refer to it as "Proposition 1".

Line 383-387 / Inequality (20-21): I suggest that the authors avoid breaking the entire inequality into two labels, which can cause ambiguity as seen in the second step of (73). Using an underbrace might be a better option.

Line 419: "$\varepsilon$-solution".

Line 1095: a multiplier of $\exp(\eta)$ is missing in the last term.

**Questions:**

* As I mentioned in the Weaknesses section, are there any practical examples (either theoretical or experimental) that can justify the importance of the *improved* complexities?
* For Theorem 3.1, it appears that you integrate the analyses from Li et al. (2024) and Koloskova et al. (2023), substituting the normalization term $\ell(G)$ in $\eta$ into something related to $\|\nabla f(x^k)\|$, so that the sequence enjoys the monotonic properties and can be analyzed in two cases. Could you elaborate on the intuition behind this approach?
* You mention new technical results for $(L_0,L_1)$-smooth functions in Section 1.3. Could you specify these results for reference? 



Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. In Advances in Neural Information Processing Systems 36, 2024.

Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In Proceedings of the 40th International Conference on Machine Learning, 2023.
soundness: 3
strengths: This paper covers existing methods for convex $(L_0,L_1)$-smooth optimization, specifically Gradient Descent with Smoothed Clipping and Polyak Stepsizes. It also provides analyses of Similar Triangles Methods and Adaptive Gradient Descent under the setting of generalized smoothness. The results give an overview of existing and adapted methods.
summary: This paper analyzes the iteration complexities of several algorithms targeted at convex $(L_0,L_1)$-smooth optimization. In comparison to previous works, the authors focus on a more refined analysis, including the elimination of dependence on the smoothness parameter $L$ (although it is not the dominant term) for variants of Gradient Descent, as well as improvements on the naive adaption of Adaptive Gradient Descent for generalized smoothness.
weaknesses: My major concern is about the significance of the results. To be specific, for the first two variants of Gradient Descent, this paper only improves the non-dominant $\mathcal{O}(\sqrt{1/\varepsilon})$ term of iteration complexity, which is inconsequential for small $\varepsilon$, i.e., when finding a solution with good quality. For the adapted versions of Similar Triangles Method and Adaptive Gradient Descent, the iteration complexity is in the form of $\mathcal{O}(\sqrt{L_0L_1A\exp(L_1A)A^2/\varepsilon^2})$, where $A$ equals either $R_0$ or $D$, which generally aligns with a specification of Li et al. (2024). Thus, the overall contribution in terms of novel theoretical guarantees appears quite limited to me at this stage.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: - In the last part of the equation (15), should it be N+1 - T instead of N+1?
- Why is it so crucial to choose $\gamma= 1/4$? In Theorem 6.1, to achieve a rate better than in (25)? Can it be relaxed?
soundness: 4
strengths: 1. Paper improved existing convergence results for gradient methods with (smoothed) clipping and Polyak stepsizes.
2. New convergence results for AdGD under $(L_0, L_1)$-smooth assumption.
3. Proposed $(L_0, L_1)$-STM recovers the best-know convergence rate for accelerated methods without additional knowledge on $R_0$ and $f(x^0) - f^*$.
summary: The paper focuses on convex $(L_0, L_1)$-smooth optimization and answers important open questions in this domain. In particular, new convergence rates are derived for the gradient method with smoothed clipping and Polyak stepsizes, improving existing results. The best-known convergence rate is derived for $(L_0, L_1)$-STM. Also, new results proved for AdGD and a stochastic case under the additional assumption on a shared minimizer. The statements in the paper are clear, and compared with existing results in the literature, the proofs are correct.
weaknesses: 1. The paper is missing the conclusion and experiments sections. However, the experiments are provided in the appendix.
2. The assumptions for stochastic problem is restrictive; however, the derived results are new and better than previous ones.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 2
questions: * Can a version of the method that is somewhat more agnostic of the knowledge of L0 and L1 be designed, since right now this knowledge is quite necessary for selecting the correct step sizes?

* Ultimately, a high-level takeaway of the work (which is likely also a takeaway that follows from the Chen paper if one could quickly bridge their stationarity to function suboptimality here) seems to be that the results are ultimately of a *local nature*. What I mean by that is that due to the unavoidable dependence of the type $\exp(\|x-y\|)$, the terms involving that in the bound will be large, unless $\|x-y\|$ is sufficiently small, and hence, in spirit the results can be viewed as showing that the GD methods studied in the paper are good but only locally. This aspect is not a criticism of the paper, but just a comment on how one can typically interpret bounds that involve exponentials.

* Do the results really offer a significant improvement over Li et al. 2024a (_Convex and Non-convex Optimization Under Generalized Smoothness_). The results provided by Li et al. 2024a for GD and NAG also do not rely on the assumption of L-smoothness, and their acceleration results for NAG  **do not** have a dependence on exp(L1). The authors claim that the advantage of their results is that they do not require dependencies on $\Vert \nabla f(x_0) \Vert$ and $f(x_0) - f^*$, as in Li et al. 2024a, and they argue that these quantities could potentially be exponentially large in the worst case (Line 408-420)---But in the reviewer's opinion, assuming these initial quantities to be constants is not a very strong assumption, whereas in comparison, the authors' acceleration result depends on exp(L1), which seems to be less favorable.
soundness: 3
strengths: **UPDATE:** Given the authors willingness (mentioned in their final comment) to make the paper's claims more transparent and to perform the pedagogic and scholarly improvements, I have raised my score.

---
The paper makes a technical contribution to the convergence analysis of gradient descent(like) methods, under the general $(L_0,L_1)$ smoothness for differentiable functions. In the reviewer's opinion, the main contribution is a tighter bound on Clip-GD under the generalized smoothness assumption (e.g., The Polyak stepsize is chosen to minimize the upper bound in (59), so the result for GD-PS is not hard to get after having proved (45) for Clip-GD, while STM and AdGD have exponential terms in their upper bounds, and hence only of marginal interest).

Strengths: This article fills a gap in the analysis of convex L0-L1 problems that are differentiable, and claims to do that without having to resort to small stepsizes as in the recent work of Li et al. The work is reasonably clearly written, and is easy to follow. Some aspects that could do with more discussion are the two-phase nature of GD (with the $>, < L_0/L_1$), and what that may mean when compared with other work (does the same happen in the nonconvex case for instance? how does it relate to bounds from the work of Li et al for instance?)
summary: This paper takes a closer look at $(L_0,L_1)$-smoothness for the setting of convex optimization. There, it derives more fine-grained convergence rate guarantees than existing work, while discussing extensions to accelerated, stochastic, and certain adaptive settings.
weaknesses: *  From a quick skim of the literature, it seems that Zhang et al noted in passing that twice differentiability could be dropped at the expense of some more analysis, but the full details of the differentiable case were worked out in subsequent work. This aspect is not clear from how the current work cites related work, and should be fixed.

* While the related work section is overall fairly good, a more precise statement about the results of Chen et al is needed, especially because that work introduced some of the key technical tools too, and studied the nonconvex case; in particular, it would be worth noting what happens if one trivially takes their nonconvex results, and tries to adapt them to the convex case (by boosting stationarity to function suboptimality using the current assumptions). Also, their slightly more general $\alpha$-version of Assumption 3 could be noted.

* Section 5 on acceleration could be deferred to the appendix or noted in passing, and more discussion given to the exponential terms in the bound, which are tantamount to saying that essentially no practical acceleration happens, even though the technical result itself is interesting to note. Similarly, the bounds arising in Section 6 should be discussed a bit more, because due to the central assumption of the paper, ultimately the pessimistic exponential terms in D arise.

* The authors's motivation for studying AdGD should be as a result further enhanced: it seems inherently unsuitable to use under the generalized smoothness assumptions since AdGD does not utilize clipping.  And the result for the stochastic case (Section 7) requires a common minimizer for all the stochastic components (Assumption 4). Although such an assumption is also used in some works, this assumption is not that weak, and renders the results less applicable.

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 4
questions: Please refer to the weakness.
soundness: 3
strengths: 1. The analysis in this work does not rely on the L-smooth assumption, which was required in previous works. In this way, the work proves a convergence rate for the Gradient Descent (GD) method with Gradient Clipping and the Gradient Descent method with Polyak Stepsizes, with the dominant part having a smaller constant depending on $L_0$.

2. This work proposes a new variant of the Similar Triangles Method that accelerates GD.

3. This work provides a faster convergence rate for the Adaptive Gradient Descent Method in $(L_0,L_1)$-smoothness settings compared to the locally L-smooth setting.
summary: This paper focuses on analyzing optimization methods for convex problems under $(L_0,L_1)$-smoothness settings. It provides improved convergence rates for the Gradient Descent (GD) method with Gradient Clipping and the Gradient Descent method with Polyak Stepsizes. It introduces a new accelerated method based on the Similar Triangles Method and provides new convergence rates for the Adaptive Gradient Descent Method. Finally, it extends the analysis to the stochastic case in overparametrized settings.
weaknesses: 1. A new acceleration of GD is proposed. It would be supportive to add more remarks to highlight the theoretical merits of this acceleration compared with the STM in (Gasnikov & Nesterov, 2016). Additionally, it would be more supportive to numerically compare its performance with STM in (Gasnikov & Nesterov, 2016).

2. Example 1.3 considers a logistic function with L2 regularization. However, $f(x)$ is not related to L2. It would be better to specify where the L2 regularization is.

3. The discussion after Theorem 7.1 (line 521) claims that the probability must be smaller than $\frac{8nL_1^2\|x^0-x^*\|^2}{\eta\nu(N+1)}$. It would be clearer to explain why the probability should be smaller than this value.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: See weakness
soundness: 2
strengths: The paper is well-writen, and thus easy to follow. The paper has some signification theoretical contributions for the existing algorithms. There are also new algorithms being adapated from the classical smoothness to the new (L0,L1)-smoothness.
summary: The paper present a study for gradient method for solving optimization problems involving (L0,L1)-smooth objective function, which was first introduced in (Zhang et al, 2020b). The analysis in the current paper is devoted fully for the convex and strongly convex case, where the convergence analysis of several methods is proopsed, both in the deterministic and stochastic setting. However, there are some major issues needed to be addressed.
weaknesses: 1. The analysis of the current paper is mostly based on Assymetric and Symmetric (L0,L1) smoothness, which can be hold for functions that are not twice differentiable. This is good since this class cover the original class of function in (Zhang et al, 2020b), where twice differentiability is a must. However, which meaningful classes of functions satisfy Assymetric/Symmetric (L0,L1) smoothness while not C2? I found that all the examples presented are C2, and thus it seems that the use of  Assymetric and Symmetric (L0,L1) smoothness is not neccesary, which reduces the importance of the current paper much. Note that examples for L-smooth functions that are not C2 are diverse, so it is reasonable to use the gradient Lipschitz condition instead of the stronger one, bounded Hessian. I do not think it is the case for (L0,L1) smoothness.

2. Now assume that the function is C2. Lemma 2.1 shows that (L0,L1) smoothness implies (not equivalent) equation (7). In comparison with Lemma 2.2 (Vankov et al., 2024) below, their equation (2.2) seems to be a shaper inequality and in fact is a equivalent condition. Based on this, I suspect that the results obtained by the paper under review is not as tight as claimed by the authors, especially when compared with (Vankov et al., 2024).  

3. The convergence theory of algorithms for (L0,L1)-smooth function does not explain why they are better than standard gradient descent. For example, can the authors explain why standard GD performs worse than designated algorithms for (L0,L1)-smooth function in solving logistic regression?

Reference.
D Vankov, A Rodomanov, A Nedich, L Sankar, SU Stich, Optimizing (L0,L1) - Smooth Functions by Gradient Methods, https://arxiv.org/abs/2410.10800

Meta-review: This paper studies the optimization algorithm for strongly convex and (L0,L1)-smooth functions. They derived the improved convergence rates for multiple algorithm including Gradient Descent with Gradient Clipping, Gradient Descent with Polyak stepsizes, and Adaptive Gradient Descent. This work fills a gap in the analysis of convex (L0,L1)-smooth functions. The main weakness is that there are not many practical examples that are  (L0,L1)-smooth but not C2.

Decision: Accept (Poster)