Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods

## 1 Introduction

In this paper, we focus on the deterministic unconstrained optimization problem

$$ $f^{*}\coloneq\min_{x\in\mathbb{R}^{d}}f(x),$ (1) $$

where $f\colon\mathbb{R}^{d}\to\mathbb{R}$ is a smooth function.
With the rise of deep learning, ensuring efficient convergence has become increasingly critical. Traditional optimization methods, such as the gradient descent method and its variants, often rely on assumptions like Lipschitz-smoothness to guarantee convergence rates. However, in modern machine learning problems, these assumptions might be too restrictive, especially when optimizing deep neural network models.

In experiments provided in \parencitezhang2019gradient, it was shown that the norm of the Hessian correlates with a norm of the gradient of a loss when training neural networks. This observation motivated the authors to introduce a new, more realistic assumption on a function class named $(L_{0},L_{1})$-smooth. The class of $(L_{0},L_{1})$-smooth functions includes the class of Lipschitz-smooth functions. Also, they provided the convergence rate of the gradient method with fixed, normalized, and clipped stepsizes for non-convex optimization and showed that normalized and clipped methods are favorable in the new setting. In recent years, many works have studied methods for solving $(L_{0},L_{1})$-smooth optimization problems. Despite this interest from the community, the existing convergence results are suboptimal in some important cases, and the analysis of such methods is not satisfactory.

Motivated by this gap, the present work investigates properties of $(L_{0},L_{1})$-smooth functions and gradient methods for optimizing these functions. The following subsection discusses existing results for $(L_{0},L_{1})$-smooth optimization.

#### Contributions.

Our contributions can be summarized as follows:

- •
In Section 2, we provide novel results and insights into the $(L_{0},L_{1})$-class by (i) providing new examples and operations that preserve the $(L_{0},L_{1})$-smoothness of functions and (ii) deriving new properties for this function class, leading to tighter bounds on descent inequalities. In Section 3, we propose new, intuitive step sizes that follow by directly minimizing our tighter upper bounds on the function growth. We also discuss the relation between these stepsizes and those used in the normalized and clipped gradient method.
- •
For nonconvex functions, we achieve the best-known $\mathcal{O}\left(\frac{L_{0}F_{0}}{\epsilon^{2}}+\frac{L_{1}F_{0}}{\epsilon}\right)$ (Theorem 3.1) complexity bound for finding an $\epsilon$-stationary point, where $F_{0}=f(x_{0})-f^{*}$ is a function residual at the initial point. For convex problems, we significantly improve existing results by achieving $\mathcal{O}(\frac{L_{0}R^{2}}{\epsilon}+L_{1}^{2}R^{2})$ (Theorem 3.2) complexity bound, where $R=\|x_{0}-x^{*}\|$ is an initial distance to a solution.
- •
We also study two new methods: normalized gradient method and gradient method with Polyak stepsizes, which do not require the knowledge of the parameters $L_{0},L_{1}$. For both methods, we show that they enjoy the same complexity bound as the gradient method knowing $L_{0}$ and $L_{1}$ (see Theorem 4.1 and Theorem 5.1 ).
- •
Finally, in Section 6, we present a simple procedure achieving the accelerated complexity of $\mathcal{O}(\sqrt{\frac{L_{0}R^{2}}{\epsilon}}+L_{1}^{2}R^{2})$. This procedure prescribes running the monotone version of the accelerated gradient method [nesterov2021primal] from the initial point constructed after a certain number of iterations of the (nonaccelerated) gradient method.

In contrast to other results in the literature, all our complexity bounds neither depend on the initial gradient norm, nor have an exponential dependency on $L_{1}$.

#### Related work.

Following the introduction of the $(L_{0},L_{1})$-class by [zhang2019gradient], subsequent works have explored other smoothness generalizations and analyzed gradient methods under these new assumptions.
[DBLP:conf/icml/00020LL23] introduced the $\alpha$-asymmetric class, relaxing the assumption on twice differentiability and allowing a sublinear growth on the norm of a gradient. In \parenciteDBLP:conf/nips/LiQTRJ23, authors went further and proposed the weakest $(r,l)$-smooth class, which allows even quadratic growth of the norm of the Hessian with respect to the norm of the gradient. Despite the generality of this assumption, there are still some issues and open questions regarding the existing results even for the basic $(L_{0},L_{1})$-smooth class.

In \parencitezhang2020improved, the authors analyzed the clipped gradient method with momentum and improved complexity bound with respect to problem parameters $L_{0},L_{1}$. Using the right choice of clipping parameters, [koloskova2023revisiting] proved, for nonconvex and convex problems, respectively, the $\mathcal{O}(\frac{L_{0}F_{0}}{\epsilon^{2}}+\frac{L_{1}F_{0}}{\epsilon})$ and $\mathcal{O}(\frac{L_{0}R}{\epsilon}+\sqrt{\frac{L}{\epsilon}}L_{1}R^{2})$ oracle complexity bounds for obtaining an $\epsilon$-approximate solution, where $L$ is a Lipschitz constant. For convex problems, [DBLP:conf/nips/LiQTRJ23] proposed an (asymptotically) faster accelerated gradient method achieving the complexity of $\mathcal{O}(\sqrt{\frac{(L_{0}+L_{1}\|\nabla f(x_{0})\|)R^{2}}{\epsilon}})$.
Several works have studied adaptive optimization methods that do not require the $(L_{0},L_{1})$ parameters to be known. [faw2023beyond, wang2023convergence] studied convergence rates for AdaGrad for stochastic nonconvex problems. [hubler2024parameter] proposed a gradient method with the backtracking line search and showed the $\mathcal{O}(\frac{L_{0}F_{0}}{\epsilon^{2}}+\frac{L_{1}^{2}F_{0}^{2}}{\epsilon
^{2}})$ complexity bound for nonconvex problems, where $L$ is a Lipschitz constant. For convex problems, [takezawa2024polyak] obtained the complexity of $\mathcal{O}(\frac{L_{0}R}{\epsilon}+\sqrt{\frac{L}{\epsilon_{g}}}L_{1}R^{2})$ for the gradient method with Polyak stepsizes, which requires knowing the optimal function value.

One interesting paper which is highly related to our work and independently appeared online during the finalization of our manuscript is [gorbunov2024methods].
In this paper, the authors propose a new formula (called “smooth clipping”) for choosing stepsizes in the gradient method for convex $(L_{0},L_{1})$-smooth functions. Up to absolute constants, this formula coincides with one of our suggestions (see Section 3), and the corresponding efficiency bound is the same as ours. The authors also show that the gradient method with Polyak stepsizes achieves the same result as in our work.
Additionally, they provide an accelerated method with complexity $\mathcal{O}(\sqrt{\frac{L_{0}R^{2}}{\epsilon}L_{1}R\exp(L_{1}R)}$ and study also the strongly convex and stochastic cases as well as some adaptive methods.
In contrast, our work has a slightly different scope and offers deeper insights by providing the intuition on arriving at the “right” stepsize formulas, an analysis for nonconvex functions, the study of normalized gradient methods, and
a superior version of the accelerated scheme with significantly better complexity.
Importantly, our proof techniques are somewhat different from those in [gorbunov2024methods] and are arguably more elegant, at least in the specific cases we consider in our paper.

## 2 Definition and Properties 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

In this section, we state our assumptions and discuss important properties of generalized smooth functions. We start with defining our main assumption on $(L_{0},L_{1})$-smooth functions.

Throughout this paper, unless specified otherwise, we use the standard inner product $\langle\cdot,\cdot\rangle$ and the standard Euclidean norm $\|\cdot\|$ for vectors, and the standard spectral norm $\|\cdot\|$ for matrices.

###### Definition 2.1 .

A twice continuously differentiable function $f\colon\mathbb{R}^{d}\to\mathbb{R}$ is called *$(L_{0},L_{1})$-smooth* (for some $L_{0},L_{1}\geq 0$) if it holds that

$$ $\|\nabla^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla f(x)\|\qquad\hbox{for all $x\in \mathbb{R}^{d}$}.$ (2) $$

The class of $(L_{0},L_{1})$-smooth function is a wide class of functions, which includes the class of Lipschitz-smooth functions. Definition 2.1 of generalized smooth function was introduced in \parencitezhang2019gradient. For twice differentiable function, this definition is equivalent to definition of $\alpha$-symmetric functions with $\alpha=1$ provided in \parenciteDBLP:conf/icml/00020LL23. All our further results also hold for
$\alpha$-symmetric functions, however, we use the stricter assumption for clarity in presentation.
Any $\alpha$-symmetric twice differentiable function is also $(L_{0},L_{1})$-smooth function, but with a different choice of parameters; thus, our results also hold for $\alpha$-symmetric functions.
For the purpose of analysis of the methods, we provide an alternative and more useful first-order characterization of the class.

###### Lemma 2.2 .

Let $f$ be a twice continuously differentiable function,
Then, $f$ is $(L_{0},L_{1})$-smooth if and only if any of the following inequalities holds for any $x,y\in\mathbb{R}^{d}$:(^1^11Hereinafter, for $L_{1}=0$ and any $t\geq 0$, we assume that $\frac{e^{L_{1}t}-1}{L_{1}}\equiv t$, $\frac{\phi(L_{1}t)}{L_{1}^{2}}\equiv\frac{1}{2}t^{2}$, etc., which are the limits of these expressions when $L_{1}\to 0;L_{1}>0$.)

$$ $\displaystyle\|\nabla f(y)-\nabla f(x)\|\leq(L_{0}+L_{1}\|\nabla f(x)\|)\frac{ e^{L_{1}\|y-x\|}-1}{L_{1}},$ (3) $\displaystyle|f(y)-f(x)-\langle\nabla f(x),y-x\rangle|\leq(L_{0}+L_{1}\|\nabla f (x)\|)\frac{\phi(L_{1}\|y-x\|)}{L_{1}^{2}},$ (4) $$

where $\phi(t)=e^{t}-t-1$ ($t\geq 0$).

The proof of Lemma 2.2 can be found in Appendix A.
It is worth noting that the bound in inequality (3) of Lemma 2.2 is stronger than the one provided in \parencite[Corollary A.4]zhang2020improved.
The bound in inequality (4) of Lemma 2.2 is tighter than those presented in previous works (see, for example, Lemma A.8 in \parencitezhang2020improved, Lemma 8 in \parencitehubler2024parameter). These tighter estimates allow us to construct gradient methods in the sequel. In our analysis we use the properties of a function $\phi(t)$ and its conjugate $\phi^{*}(t)$, which we summarize in the following lemma.

###### Lemma 2.3 .

The following statements for the function $\phi(t)=e^{t}-t-1$ hold true,

- 1.
$\phi(t)\leq\frac{t^{2}}{2-\frac{2}{3}t}$ for all $t\in[0,3)$.
- 2.
$\phi^{*}(\gamma)=(1+\gamma)\ln(1+\gamma)-\gamma$ ($\gamma\geq 0$) is the conjugate function to $\phi$.
- 3.
$\frac{\gamma^{2}}{2+\gamma}\leq\phi^{*}(\gamma)\leq\frac{\gamma^{2}}{2}$ for all $\gamma\geq 0$

In the following lemma, we summarize some important properties of $(L_{0},L_{1})$-smooth functions.

###### Lemma 2.4 .

Let $f$ be a convex $(L_{0},L_{1})$-smooth nonlinear(^2^22According to Lemma 2.2, this means that $L_{0}+L_{1}\|\nabla f(x)\|>0$ for any $x\in\mathbb{R}^{d}$.) function. Then, for any $x,y\in\mathbb{R}^{d}$,

$$ $\displaystyle f(y)\geq f(x)+\langle\nabla f(x),y-x\rangle+\frac{L_{0}+L_{1}\| \nabla f(y)\|}{L_{1}^{2}}\phi_{*}\Bigl{(}\frac{L_{1}\|\nabla f(y)-\nabla f(x) \|}{L_{0}+L_{1}\|\nabla f(y)\|}\Bigr{)},$ (5) $\displaystyle\begin{multlined}\langle\nabla f(x)-\nabla f(y),x-y\rangle\geq \frac{L_{0}+L_{1}\|\nabla f(y)\|}{L_{1}^{2}}\phi_{*}\Bigl{(}\frac{L_{1}\| \nabla f(y)-\nabla f(x)\|}{L_{0}+L_{1}\|\nabla f(y)\|}\Bigr{)}\\ \quad+\frac{L_{0}+L_{1}\|\nabla f(x)\|}{L_{1}^{2}}\phi_{*}\Bigl{(}\frac{L_{1} \|\nabla f(y)-\nabla f(x)\|}{L_{0}+L_{1}\|\nabla f(x)\|}\Bigr{)},\end{ multlined}\langle\nabla f(x)-\nabla f(y),x-y\rangle\geq\frac{L_{0}+L_{1}\| \nabla f(y)\|}{L_{1}^{2}}\phi_{*}\Bigl{(}\frac{L_{1}\|\nabla f(y)-\nabla f(x) \|}{L_{0}+L_{1}\|\nabla f(y)\|}\Bigr{)}\\ \quad+\frac{L_{0}+L_{1}\|\nabla f(x)\|}{L_{1}^{2}}\phi_{*}\Bigl{(}\frac{L_{1} \|\nabla f(y)-\nabla f(x)\|}{L_{0}+L_{1}\|\nabla f(x)\|}\Bigr{)},$ (8) $$

where $\phi_{*}(\gamma)=(1+\gamma)\ln(1+\gamma)-\gamma$ ($\gamma\geq 0$)
is the conjugate function to $\phi$ from Lemma 2.2. Moreover, since $\phi_{*}(\gamma)\geq\frac{\gamma^{2}}{2+\gamma}$ by Lemma 2.3 (3), lower bound in 5 can be simplified as follows

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

Notice that Lemma 2.4 is a generalization of \parencite[Theorem 2.1.5]nesterov2018lectures for $(L_{0},L_{1})$-smooth function, and matches it when $L_{1}=0$ (since $\frac{1}{L_{1}^{2}}\phi_{*}(L_{1}\alpha)\to\frac{1}{2}\alpha^{2}$ as $L_{1}\to 0$).
The proof of Lemma 2.4 is presented in Appendix A. Next, we present some examples to support the choice of $(L_{0},L_{1})$-smooth assumption.

###### Example 2.5 .

The function $f(x)=\frac{1}{p}\|x\|^{p}$, where $p>2$, is $(L_{0},L_{1})$-smooth with arbitrary $L_{1}>0$ and $L_{0}=(\frac{p-2}{L_{1}})^{p-2}$.

###### Example 2.6 .

The function $f(x)=\ln(1+e^{x})$ is $(L_{0},L_{1})$-smooth with arbitrary $L_{1}\in[0,1]$ and $L_{0}=\frac{1}{4}(1-L_{1})^{2}$.

The preceding examples also show that the choice of $L_{0},L_{1}$ parameters is generally not unique. While we cannot guarantee that the class is closed under all standard operations, such as the summation, affine substitution of the argument, we can still show that some operations do preserve $(L_{0},L_{1})$-smoothness under certain additional assumptions.

###### Proposition 2.7 .

Let $f\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a twice continuously differentiable $(L_{0},L_{1})$-smooth function.
Then, the following statements hold:

- 1.
Let $g\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$ be an $L$-smooth and $M$-Lipschitz twice continuously differentiable function. Then, the sum $f+g$ is $(L_{0}^{\prime},L_{1}^{\prime})$-smooth with $L_{0}^{\prime}=L_{0}+ML_{1}+L$ and $L_{1}^{\prime}=L_{1}$.
- 2.
Let $f_{i}\colon\mathbb{R}^{d_{i}}\rightarrow\mathbb{R}$ be an $(L_{0,i},L_{1,i})$-smooth function for each $i=1,\ldots,n$. Then, the function $h\colon\mathbb{R}^{d_{1}}\times\ldots\times\mathbb{R}^{d_{n}}\rightarrow
\mathbb{R}$ given by $h(x)=\sum_{i=1}^{n}f_{i}(x_{i})$, where $x=(x_{1},\ldots,x_{n})$, is $(L_{0},L_{1})$-smooth with $L_{0}=\max_{1\leq i\leq n}L_{0,i}$ and $L_{1}=\max_{1\leq i\leq n}L_{1,i}$.
- 3.
If $f$ is univariate ($d=1$) and $h(x)=f(\langle a,x\rangle+b)$, $x\in\mathbb{R}^{d}$, where $a\in\mathbb{R}^{d}$, $b\in\mathbb{R}$, then $h$ is $(L_{0}^{\prime},L_{1}^{\prime})$-smooth with parameters $L_{0}^{\prime}=\|a\|^{2}L_{0}$ and $L_{1}^{\prime}=\|a\|L_{1}$.
- 4.
Let additionally $\nabla^{2}f(x)\succ 0$ for all $x\in\mathbb{R}^{d}$ and $f$ be $1$-coercive(^3^33This means that $\frac{f(x)}{\|x\|}\to+\infty$ as $\|x\|\to\infty$.). Then, $f$ is $(L_{0},L_{1})$-smooth iff its conjugate $f_{*}$ (which is, under our assumptions, defined on the entire space and also twice continuously differentiable) satisfies $\nabla^{2}f_{*}(s)\succeq\frac{1}{L_{0}+L_{1}\|s\|}I$ for all $s\in\mathbb{R}^{d}$, where $I$ is the identity matrix.

One simple example of the additive term $g$ satisfying the assumptions in the first item of Proposition 2.7 is an affine function (for which $L=0$); another interesting example is the soft-max function $g(x)=\mu\ln(\sum_{i=1}^{m}e^{[\langle a_{i},x\rangle+b_{i}]/\mu})$, where $a_{i}\in\mathbb{R}^{d}$, $b_{i}\in\mathbb{R}$, $\mu>0$. Based on the second statement of Proposition 2.7 and Example 2.5,
the function $f(x)=\frac{1}{p}\|x\|_{p}^{p}\equiv\frac{1}{p}\sum_{i=1}^{d}|x_{i}|^{p}$ with $p>2$ is $(L_{0},L_{1})$-smooth with arbitrary $L_{1}>0$ and $L_{0}=(\frac{p-2}{L_{1}})^{p-2}$. Using the third statement, we can generalize Example 2.6 and conclude that $f(x)=\ln(1+e^{\langle a,x\rangle})$ is also $(L_{0},L_{1})$-smooth with arbitrary $L_{1}\in[0,\|a\|]$ and $L_{0}=\frac{1}{4}(\|a\|-L_{1})^{2}$.
Also, we can use the last statement of the proposition to show that $f(x)=\frac{L_{0}}{L_{1}^{2}}\phi(L_{1}\|x\|)\equiv\frac{L_{0}}{L_{1}^{2}}(e^{L
_{1}\|x\|}-L_{1}\|x\|-1)$ is $(L_{0},L_{1})$-smooth since the Hessian of its conjugate $f_{*}(s)=\frac{L_{0}}{L_{1}^{2}}\phi_{*}(\frac{L_{1}\|s\|}{L_{0}})\equiv\frac{
L_{0}}{L_{1}^{2}}[((1+\frac{L_{1}\|s\|}{L_{0}})\ln(1+\frac{L_{1}\|s\|}{L_{0}})
-\frac{L_{1}\|s\|}{L_{0}}]$ has the form $\nabla^{2}f_{*}(s)=\frac{1}{L_{0}+L_{1}\|s\|}I$. In particular, we can construct an $(L_{0},L_{1})$-smooth function by taking any convex function $h_{*}$, adding to it $\phi_{*}$ and taking the conjugate (this corresponds to the infimal convolution of $h$ with $\phi$).

###### Definition 2.1 .

###### Lemma 2.2 .

###### Lemma 2.3 .

###### Lemma 2.4 .

###### Example 2.5 .

###### Example 2.6 .

###### Proposition 2.7 .

## 3 Gradient Method

Having established a few important properties of an $(L_{0},L_{1})$-smooth function $f$, we now turn our attention to the *gradient method* for minimizing such a function:

$$ $x_{k+1}=x_{k}-\eta_{k}\nabla f(x_{k}),\qquad k\geq 0,$ (10) $$

where $x_{0}\in\mathbb{R}^{d}$ is a starting point and $\eta_{k}\geq 0$ are certain stepsizes.

We start with showing that the gradient update rule (10) and the “right” formula for the stepsize $\eta_{k}$ both naturally arise from the classical idea in optimization theory—choosing the next iterate $x_{k+1}$ by minimizing the global upper bound on the objective function value constructed around the current iterate $x_{k}$ (see \parencitenesterov2018lectures).
Indeed, let $x\in\mathbb{R}^{d}$ be the current point and let $a:=L_{0}+L_{1}\|\nabla f(x)\|>0$.
According to 4, for any $y\in\mathbb{R}^{d}$,

$$ $f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+\frac{a}{L_{1}^{2}}\phi(L_{1}\|y-x \|).$ $$

Our goal is to minimize the right-hand of the above inequality in $y$.
Since the last term in this bound depends only on the norm of $y-x$, the optimal point $y^{*}=T(x)$ is the result of the gradient step $T(x)=x-r^{*}\frac{\nabla f(x)}{\|\nabla f(x)\|}$ for some $r^{*}\geq 0$ ensuring the following progress in decreasing the function value:

$$ $f(x)-f(T(x))\geq\max_{r\geq 0}\Bigl{\{}\|\nabla f(x)\|r-\frac{a}{L_{1}^{2}} \phi(L_{1}r)\Bigr{\}}=\frac{a}{L_{1}^{2}}\phi_{*}\Bigl{(}\frac{L_{1}\|\nabla f (x)\|}{a}\Bigr{)},$ $$

where $\phi_{*}$ is the conjugate function to $\phi$ (see Lemma 2.3).
furthermore, $r^{*}$ is exactly the solution of the above optimization problem, satisfying $L_{1}\|\nabla f(x)\|=a\phi^{\prime}(L_{1}r^{*})$.
Solving this equation, using the fact that $(\phi^{\prime})^{-1}(\gamma)=\phi_{*}^{\prime}(\gamma)=\ln(1+\gamma)$, we obtain $r^{*}=\frac{1}{L_{1}}\phi_{*}^{\prime}(\frac{L_{1}\|\nabla f(x)\|}{a})=\frac{1
}{L_{1}}\ln(1+\frac{L_{1}\|\nabla f(x)\|}{a})$.

The above considerations lead us to the following *optimal* choice of stepsizes in (10):

$$ $\displaystyle\boxed{\eta^{*}_{k}=\dfrac{1}{L_{1}\|\nabla f(x_{k})\|}\ln\Bigl{( }1+\frac{L_{1}\|\nabla f(x_{k})\|}{L_{0}+L_{1}\|\nabla f(x_{k})\|}\Bigr{)},} \qquad k\geq 0,$ (11) $$

resulting in the following progress in decreasing the objective:

$$ $f(x_{k})-f(x_{k+1})\geq\frac{L_{0}+L_{1}\|\nabla f(x_{k})\|}{L_{1}^{2}}\phi_{* }\Bigl{(}\frac{L_{1}\|\nabla f(x_{k})\|}{L_{0}+L_{1}\|\nabla f(x_{k})\|}\Bigr{ )}\coloneq\Delta_{k}.$ (12) $$

The above expression for $\Delta_{k}$ is quite cumbersome but, in fact, it behaves as the simple fraction $\frac{\|\nabla f(x_{k})\|^{2}}{L_{0}+L_{1}\|\nabla f(x_{k})\|}$.
More precisely, from Lemma 2.3(3), we see that

$$ $\displaystyle\frac{\|\nabla f(x_{k})\|^{2}}{2L_{0}+3L_{1}\|\nabla f(x_{k})\|} \leq\Delta_{k}\leq\frac{\|\nabla f(x_{k})\|^{2}}{2(L_{0}+L_{1}\|\nabla f(x_{k} )\|)}.$ $$

Thus, there is not much point in keeping the complicated expression (12) and we can safely simplify it as follows:

$$ $f(x_{k})-f(x_{k+1})\geq\frac{\|\nabla f(x_{k})\|^{2}}{2L_{0}+3L_{1}\|\nabla f( x_{k})\|}.$ (13) $$

Interestingly, we can also arrive at exactly the same bound (13) by using a simpler choice of stepsizes.
Specifically, replacing $\ln(1+\gamma)$ with its lower bound $\frac{2\gamma}{2+\gamma}$ (which is responsible for the inequality in Lemma 2.3(3) that we used to simplify 12 into 13), we obtain
the following *simplified stepsizes*:

$$ $\boxed{\eta_{k}=\frac{1}{L_{0}+\frac{3}{2}L_{1}\|\nabla f(x_{k})\|},}\qquad k \geq 0.$ (14) $$

With this choice, the iterates of method (10) still satisfy 13 (see Lemma B.1).

Further, note that, up to absolute constants, stepsize (14) acts as $\frac{1}{\max\{L_{0},L_{1}\|\nabla f(x_{k})\|\}}=\min\{\frac{1}{L_{0}},\frac{1
}{L_{1}\|\nabla f(x_{k})\|}\}$, which is the so-called clipping stepsize used in many previous works [zhang2019gradient, zhang2020improved, koloskova2023revisiting].
Thus, with the right choice of absolute constants, we can expect the corresponding clipping stepsizes, to satisfy a similar inequality to (13).
This is indeed the case and we can show, in particular, that the *clipping stepsizes*

$$ $\boxed{\eta^{\mathrm{cl}}_{k}=\min\Bigl{\{}\frac{1}{2L_{0}},\frac{1}{3L_{1}\| \nabla f(x_{k})\|}\Bigr{\}},}\qquad k\geq 0,$ (15) $$

do satisfy (13) although with slightly worse absolute constants (see Lemma B.1).
We have thus demonstrated in this section that clipping stepsizes (15) are simply a convenient approximation of the optimal stepsizes (11) ensuring a similar bound on the objective progress.
This observation seems to be a new insight into clipping stepsizes which has not been previously explored in the literature.

### 3.1 Nonconvex functions

Based on preceding developments, we present a convergence rate result for nonconvex functions.

###### Theorem 3.1 .

Let $f(\cdot)$ be an $(L_{0},L_{1})$-smooth function, and let $\{x_{k}\}$ be iterate sequence of gradient decent method (10) with one of the stepsize choices given by (11) or (14).
Then, after $K\geq 0$ iterations, the following bound holds with $F_{0}:=f(x_{0})-f^{*}$:

$$ $\min_{0\leq i\leq K}\|\nabla f(x_{i})\|\leq\sqrt{\dfrac{2L_{0}F_{0}}{K+1}}+ \dfrac{3L_{1}F_{0}}{2(K+1)}.$ $$

The full proof of Theorem 3.1 can be found in Appendix B. By Theorem 3.1, the smallest number $K$ of iterations required to achieve an $\epsilon_{g}$-stationary point is $K\geq\max\{\frac{4L_{0}F_{0}}{\epsilon_{g}^{2}},\frac{6L_{1}F_{0}}{\epsilon_{g
}}\}$.
This rate matches, up to absolute constants, the rate in \parencitekoloskova2023revisiting for clipped gradient descent with $\eta=\frac{1}{9}(L_{0}+cL_{1})$ for $c=\frac{L_{0}}{L_{1}}$, or equivalently the gradient method with stepsize $\eta_{k}=\frac{1}{18L_{0}}\min\{1,\frac{L_{0}}{L_{1}\|\nabla f(x_{k})\|}\}$. Furthermore, our rate is significantly better than rate $\mathcal{O}(\frac{L_{0}F_{0}}{\epsilon_{g}^{2}}+\frac{L_{1}^{2}F_{0}}{L_{0}})$ obtained in \parencitezhang2019gradient for the clipped gradient method since $\frac{L_{1}F_{0}}{\epsilon_{g}}\leq\frac{L_{0}^{2}F_{0}}{2\epsilon_{g}}+\frac{
L_{1}^{2}F_{0}}{2L_{0}}$, and the latter expression can be arbitrarily far away from the former whenever $L_{0}$ is sufficiently small and $L_{1}$ is distinct from zero.
In addition to that, our convergence rate result does not depend on the gradient norm at the initial point, in contrast to [DBLP:conf/nips/LiQTRJ23] who consider a wider class of generalized smooth functions but whose rate depends on $\|\nabla f(x_{0})\|$. Also, our rate from Theorem 3.1 is better than $\mathcal{O}\bigl{(}\frac{L_{0}F_{0}}{\epsilon_{g}^{2}}+\frac{L_{1}^{2}F_{0}^{2
}}{\epsilon_{g}^{2}}\bigr{)}$ provided in \parencitehubler2024parameter for the gradient method with the backtracking line search.

###### Theorem 3.1 .

### 3.2 Convex functions

Let us now provide the convergence rate for convex functions.

###### Theorem 3.2 .

Let $f(\cdot)$ be convex and $(L_{0},L_{1})$-smooth function, and let $\{x_{k}\}$ be the iterate sequence of gradient descent method (10) with one of the stepsize choices given in (11) or (14).
Then, for a given $\epsilon>0$, we have $f(x_{K})-f^{*}\leq\epsilon$ when the number $K$ of iterations satisfies

$$ $K\geq\max\Bigl{\{}\frac{4L_{0}R_{0}^{2}}{\epsilon},36L_{1}^{2}R_{0}^{2}\Bigr{ \}},$ $$

where $R=\|x_{0}-x^{*}\|$ and $x^{*}$ is an arbitrary solution to the problem in (1).

To prove this estimate, we define a monotonically increasing function $\psi(g)=\frac{g^{2}}{2L_{0}+3L_{1}g}$.
Next, we use Lemma 2.2 with substituted $x=x^{*}$ and $y=x_{k}$ in 9, and provide a lower bound

$$ $f(x_{k})-f^{*}\geq\psi(\|\nabla f(x_{k})\|).$ $$

Hence, by denoting $R_{k}=\|x_{k}-x^{*}\|$, $g_{k}=\|\nabla f(x_{k})\|$, $f_{k}=f(x_{k})-f^{*}$ we have $g_{k}\leq\psi^{-1}(f_{k})$. Then, by using the preceding estimate and the updated rule of the method, we obtain that the following inequality holds for all $k\geq 0$

$$ $R_{k}^{2}-R_{k+1}^{2}\geq\frac{f_{k}\psi(g_{k})}{g_{k}^{2}}\geq\frac{f_{k}^{2} }{[\psi^{-1}(f_{k})]^{2}}.$ $$

Finally, we obtain the desired result by summing these inequalities over $k=0,\ldots,K$ and simplifying the equation. The full proof of Theorem 3.2 can be found in Appendix B.

It is worth noting that the convergence rate in Theorem 3.2 includes parameter $L_{1}$ without dependency on $\epsilon$, while for parameter $L_{0}$, the dependency is as in the standard rate for $L_{0}$-smooth functions $\mathcal{O}(\frac{L_{0}}{\epsilon})$. It can be seen as, for $(L_{0},L_{1})$-smooth functions, the gradient method with the proposed step sizes requires a constant number of iterations $\mathcal{O}(L_{1}^{2}R^{2})$ to reach a region where the function $f(\cdot)$ behaves like $L_{0}$-smooth function. After reaching this number of iterations, the rate of the method depends only on the parameter $L_{0}$ and does not depend on $L_{1}$.

In Theorem 3.2, we do not make an assumption on $L$-smoothness of a function, while this assumption is used in \parencitekoloskova2023revisiting. Moreover, the rate in the theorem is better than $\mathcal{O}(\frac{L_{0}R^{2}}{\epsilon}+\sqrt{\frac{L}{\epsilon}}L_{1}R^{2})$ rate provided in \parencitekoloskova2023revisiting for clipped gradient method, since it does not have $\frac{1}{\sqrt{\epsilon}}$ dependency on $L_{1}$ and $L$. Also, our result does not include the norm $\|\nabla f(x_{0})\|$ of the gradient at an initialization point in the estimate, while the rate provided in \parenciteDBLP:conf/nips/LiQTRJ23 does depend on $\|\nabla f(x_{0})\|$ which can be large and be an order of $L$. Consider for example $f(x)=\frac{1}{p}\|x\|^{p}$ (see Proposition 2.5) for $p>2$ and starting point $x_{0}$ sufficiently far from the origin, in this case, the gradient $\|\nabla f(x_{0})\|=\|x_{0}\|^{p-1}$ can be arbitrary large.

###### Theorem 3.2 .

## 4 Normalized Gradient Method

To run the gradient method from Section 3, it is necessary to know the parameters $(L_{0},L_{1})$ in advance. In many real-life examples, those parameters are unknown, and it might be computationally expensive to estimate them.
Furthermore, for any given function $f$, the pair $(L_{0},L_{1})$ is generally not unique (see Examples 2.5 and 2.6), and it is not clear in advance which pair would result in the best possible convergence rate of our optimization method.
To address this issue, in this section, we present another version of the gradient method that does not require knowing $(L_{0},L_{1})$.
This is the *normalized gradient method*:

$$ $x_{k+1}=x_{k}-\frac{\beta_{k}}{\|\nabla f(x_{k})\|}\nabla f(x_{k}),\qquad k \geq 0,$ (16) $$

where $x_{0}\in\mathbb{R}^{d}$ is a certain starting point, and $\beta_{k}$ are positive coefficients.

The following result describes the efficiency of the normalized gradient method.

###### Theorem 4.1 .

Let $f$ be a convex $(L_{0},L_{1})$-smooth function, and let $x_{k}$ be the iterates of the normalized gradient method (16) with constant coefficients $\beta_{k}=\frac{\hat{R}}{\sqrt{K+1}}$, $0\leq k\leq K-1$, where $\hat{R}>0$ is a parameter and $K\geq 1$ is the total number of iterations of the method (fixed in advance). Let $x_{K}^{*}=\operatorname*{arg\,min}_{x\in\{x_{0},\ldots,x_{K}\}}f(x)$ be the iterate with the smallest function value, and let $\bar{R}\coloneq\frac{R^{2}}{\hat{R}}+\hat{R}$, where $R\coloneq\|x_{0}-x^{*}\|$. Then, $f(x_{K}^{*})-f^{*}\leq\epsilon$ whenever

$$ $K\geq\max\Bigl{\{}\frac{L_{0}\bar{R}^{2}}{\epsilon},\frac{4}{9}L_{1}^{2}\bar{R }^{2}\Bigr{\}}.$ $$

The parameter $\hat{R}$ in the formula for coefficients $\beta_{k}$ is an estimation of the initial distance $R$ to a solution, and the best complexity bound of $K^{*}\coloneq\mathcal{O}(\frac{L_{0}R^{2}}{\epsilon}+L_{1}^{2}R^{2})$ is achieved whenever $\hat{R}=R$. Note that, even if $\hat{R}\neq R$, the method still converges but with a slightly worse total complexity of $K^{*}\rho^{2}$, where $\rho=\max\{\frac{R}{\hat{R}},\frac{\hat{R}}{R}\}$.

The proof of Theorem 4.1 is based on the following two important facts [nesterov2018lectures, Section 3].
First, under the proper choice of coefficients $\beta_{k}$, the normalized gradient method ensures that the minimal value $v_{K}^{*}$ among $v_{k}\coloneq\frac{\langle\nabla f(x_{k}),x_{k}-x^{*}\rangle}{\|\nabla f(x_{k}
)\|}$, $0\leq k\leq K$, converges to zero at the rate of $\frac{\bar{R}}{\sqrt{K}}$.
These quantities $v_{k}$ have a geometrical meaning—each of them is exactly the distance from the point $x^{*}$ to the supporting hyperplane to the sublevel set of $f$ at the point $x_{k}$.
Second, whenever $v_{K}^{*}$ converges to zero, so does $\min_{0\leq k\leq K}f_{k}-f^{*}$.
Moreover, we can express the latter convergence rate via the former whenever we can bound, for any given $v\geq 0$, the function residual $f(x)-f^{*}$ over the ball $\|x-x^{*}\|\leq v$:

###### Lemma 4.2 ( [ nesterov2018lectures , Lemma 3.2.1] ) .

Let $f\colon\mathbb{R}^{d}\to\mathbb{R}$ be a differentiable convex function. Then, for any $x,y\in\mathbb{R}^{d}$ and(^4^44Here $[t]_{+}\coloneq\max\{t,0\}$ is the nonnegative part of $t\in\mathbb{R}$.) $v_{f}(x;y)\coloneq\frac{[\langle\nabla f(x),x-y\rangle]_{+}}{\|\nabla f(x)\|}$, it holds that

$$ $\displaystyle f(x)-f(y)\leq\max_{z\in\mathbb{R}^{d}}\{f(z)-f(y):\|z-y\|\leq v_ {f}(x;y)\}.$ (17) $$

In our case—when the function $f$ is $(L_{0},L_{1})$-smooth—the corresponding bound can be obtained from Lemma 2.2.
The complete proof of Theorem 4.1 can be found in Appendix C.

In Theorem 4.1, we fix the number of iterations $K$ before running the method, which is a standard approach for the (normalized)-(sub)gradient methods (Section 3.2 in [nesterov2018lectures]).
However, doing so may be undesirable in practice since it becomes difficult to continue running the method if the time budget was suddenly increased and also prevents the method from using larger stepsizes at the initial iterations.
To overcome these drawbacks, one can use time-varying coefficients by setting $\beta_{k}=\frac{\hat{R}}{\sqrt{k+1}}$, $0\leq k\leq K-1$.
This results in the same worst-case theoretical complexity as in Theorem 4.1 but with an extra logarithmic factor (see Appendix C).
Moreover, one can completely eliminate this extra logarithmic factor by switching to an appropriate modification of the normalized gradient method such as Dual Averaging [Nesterov2005PrimaldualSM].

When $\hat{R}=R$, the complexity of the normalized gradient method is $\mathcal{O}(\frac{L_{0}R^{2}}{\epsilon}+L_{1}^{2}R^{2})$ which matches that of the previously considered gradient method (see Theorem 3.2). However, recall that the previous algorithm requires knowing $(L_{0},L_{1})$, and its rate depends on the particular choice of these constants. In contrast, the normalized gradient method does not require the knowledge of these parameters, and its “real” complexity is

$$ $\mathcal{O}(1)\min_{L_{0},L_{1}}\Bigl{\{}\frac{L_{0}^{2}\bar{R}^{2}}{\epsilon} +L_{1}^{2}\bar{R}^{2}\colon\text{$f$ is $(L_{0},L_{1})$-smooth}\Bigr{\}},$ $$

where $\mathcal{O}(1)$ is an absolute constant.

###### Theorem 4.1 .

###### Lemma 4.2 ( [ nesterov2018lectures , Lemma 3.2.1] ) .

## 5 Gradient Method with Polyak Stepsizes

In the previous sections, the parameters required to run the methods were $L_{0},L_{1}$ for the gradient method and the initial distance to a solution $R$ for the normalized gradient method. Sometimes, both of these parameters are unknown while the optimal value of the function is available. One of the examples of such problems is over-parametrized models in machine learning, where $f^{*}$ is usually 0.
In this section, we focus on the case when $f^{*}$ is known and analyze the gradient method (10) with *Polyak stepsizes*:

$$ $\eta_{k}=\frac{f(x_{k})-f^{*}}{\|\nabla f(x_{k})\|^{2}},\qquad k\geq 0.$ (18) $$

We show that in the convex case, the convergence rate of gradient method with Polyak stepsizes does not have an exponential dependency on $L_{0},L_{1}$ constants.

###### Theorem 5.1 .

Let $f(\cdot)$ be convex and $(L_{0},L_{1})$-smooth function, let $x_{k}$ be iterate from gradient method (10) with stepsizes (18). Let $x_{K}^{*}=\operatorname*{arg\,min}_{x\in\{x_{0},\ldots,x_{K}\}}f(x)$, then to get $f(x_{K}^{*})-f^{*}\leq\epsilon$ the method requires at most the following number of iterations:

$$ $K\leq\max\Bigl{\{}\frac{4L_{0}R^{2}}{\epsilon},36L_{1}^{2}R^{2}\Bigr{\}}.$ $$

We prove the theorem by using a standard inequality for the gradient method with Polyak stepsizes,

$$ $R_{k}^{2}-R_{k+1}^{2}\geq\frac{f_{k}^{2}}{g_{k}^{2}},$ $$

where $R_{k}=\|x_{k}-x^{*}\|$, $g_{k}=\|\nabla f(x_{k})\|$ and $f_{k}=f(x_{k})-f^{*}$ for all $k\geq 1$. We then leverage the simplified lower bound (9) from Lemma 2.4 and bound gradient norm $g_{k}$ by $\psi^{-1}(f_{k})$, where $\psi(g)=\frac{g^{2}}{2L_{0}+3L_{1}g}$ for $g\geq 0$, and obtain,

$$ $R_{k}^{2}-R_{k+1}^{2}\geq\frac{f_{k}^{2}}{[\psi^{-1}(f_{k})]^{2}}.$ $$

Further, by summing these equations, taking a minimum over all $f_{k}$, and simplifying the resulting inequalities, we obtained the desired bound on $f_{K}^{*}$. The full proof of Theorem 5.1 can be found in Appendix D
Notice that the rate $\mathcal{O}(\frac{L_{0}R^{2}}{\epsilon}+L_{1}^{2}R^{2})$ in Theorem 5.1 is the same as the rate for gradient method in Theorem 3.2 and normalized gradient method in Theorem 3.1. Our rate is better than $\mathcal{O}(\frac{L_{0}R^{2}}{\epsilon}+\sqrt{\frac{L}{\epsilon}}L_{1}R^{2})$ provided in [takezawa2024polyak], since it does not have a dependency on $\epsilon$ with respect to $L_{1}$ and $L$ parameters. Furthermore, it is more general since we do not assume $L$-smoothness of the function. Finally, it is worth mentioning that the rate for the gradient method with Polyak stepsizes holds for any choice of $(L_{0},L_{1})$. Thus, the rate holds for the best choice of $(L_{0},L_{1})$ pair and is the same as for the normalized gradient method.

###### Theorem 5.1 .

## 6 Accelerated Gradient Method

This section focuses on developing an accelerated method for $(L_{0},L_{1})$-smooth function.
We highlight the following important observations. Consider a point $x\in\mathbb{R}^{d}$, such that $\|\nabla f(x)\|\leq\frac{L_{0}}{L_{1}}$, then by the definition of $(L_{0},L_{1})$-smoothness, the following relation holds,

$$ $\|\nabla^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla f(x)\|\leq 2L_{0}.$ (19) $$

Hence, at all points $x$ whose gradients are bounded by a constant $\frac{L_{0}}{L_{1}}$, the function $f$ behaves like $2L_{0}$-smooth function.
Furthermore, leveraging the results of Lemma 2.4, it is possible to bound a gradient norm by a function progress $f(x)-f^{*}$. In case when the function progress along the trajectory of the method is non-increasing, one can guarantee that the iterates satisfy the bound 19.
However, the monotonic decrease cannot be guaranteed for all standard versions of the Fast Gradient Method (FGM). Nevertheless, one monotone version of the FGM exists, which turns out to preserve precisely the same property \parencitenesterov2021primal.
In contrast to the existing works and motivated by the above reasoning, we propose to use a two-stage procedure (see Algorithm 1): use gradient method to find a point $\bar{x}$ with small gradient norm and run Accelerated Gradient Method with Small-Dimensional Relaxation (AGMsDR) with initial point $x_{0}=\bar{x}$ , which ensures that the gradient norms of the iterates stays small. For convenience of the reader we re-stated AGMsDR in Algorithm 2.

By running the gradient method, we ensure that the starting point of AGMsDR satisfies the following condition, $F_{0}=f(x_{0})-f^{*}\leq\frac{L_{0}}{5L_{1}^{2}}$. This consequently helps us to upper bound a norm of the gradient $\|\nabla f(x)\|$ on a sublevel set $x\in\{z\in\mathbb{R}^{d}:f(z)\leq f(x_{0})\}$, using the simplified lower bound in Lemma 2.4, as follows:

$$ $\psi(\|\nabla f(x)\|)\leq f(x)-f^{*}\leq F_{0}\leq\frac{L_{0}}{5L_{1}^{2}},$ $$

where $\psi(\gamma)=\frac{\gamma^{2}}{2L_{0}+3L_{1}\gamma}$, from this inequality we obtain that $\|\nabla f(x)\|\leq\psi^{-1}(F_{0})=\frac{L_{0}}{L_{1}}$, and consequently 19 holds.

Our second ingredient for the further analysis, is an operation $T(\cdot):\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, which has the following property. For any point $x\in\mathcal{F}_{0}=\{x:f(x)\leq f(x_{0})\}$ in the sublevel set, the point $T(x)$ belongs to a sublevel set $\mathcal{F}_{0}$, $T(x)\in\mathcal{F}_{0}$, and

$$ $f(T(x))\leq f(x)-\frac{1}{2L}\|\nabla f(x)\|^{2}.$ (20) $$

One specific example of such an operation is the gradient step $T_{L}(x)=x-\eta_{x}\nabla f(x)$ with stepsizes (11) or (14) ($x_{k}$ replaced with $x$) for which $L=3L_{0}$, since on a sublevel set $\|\nabla f(x)\|\leq\frac{L_{0}}{L_{1}}$ and consequently $\frac{1}{6L_{0}}\|\nabla f(x)\|^{2}\geq\frac{\|\nabla f(x)\|^{2}}{2L_{0}+3L_{1
}\|\nabla f(x)\|}$ (see Lemma B.1).

Figure: Algorithm 1 Two-Stage Procedure

Figure: Algorithm 2 Accelerated Gradient Method with Small-Dimensional Relaxation (AGMsDR) [nesterov2021primal]

Our procedure guarantees two important properties of the iterates: (1) the gradient norms of iterates $x_{k}$ and $y_{k}$ of AGMsDR stay bounded by constant $L_{0}/L_{1}$, which is independent of the gradient norm of the initial point, and guarantees the small local Lipschitz constant along the trajectory (2) the monotonically decreasing function values along the iterates $x_{k},y_{k}$, meaning that $f(x_{k+1})\leq f(y_{k})\leq f(x_{k})$ for all $k\geq 0$.

The rest of the analysis of the method is similar to the proof of Theorem 1 in [nesterov2021primal], which leads to the following theorem.
The full proof of
Theorem 6.2 can be found in Appendix E.

###### Theorem 6.1 .

Let $f(\cdot)$ be a convex function, and let $x_{0}\in\mathbb{R}^{d}$, $L>0$ and an operator $T_{L}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ be such that for any $x\in\{z\in\mathbb{R}^{d}:f(z)\leq f(x_{0})\}$,
it holds that

$$ $f(x)-f(T_{L}(x))\geq\frac{1}{2L}\|\nabla f(x)\|^{2}.$ $$

Then the following statements are true for AGMsDR (Algorithm 2) with
initial point $x_{0}$ and update rule $T_{L}(\cdot)$ for all $k\geq 0$:

$$ $\displaystyle(1)\quad f(x_{k+1})\leq f(y_{k})\leq f(x_{k}),$ $\displaystyle(2)\quad f(x_{k})-f^{*}\leq\frac{2LR^{2}}{k^{2}}.$ $$

where $R=\|x_{0}-x^{*}\|$.

Based on Theorem 6.1, the smallest number of iterations required to achieve
$f(x_{k})-f^{*}\leq\epsilon$ with a right choice of starting point $x_{0}$ and parameter $L$ is $\sqrt{\frac{16L_{0}}{\epsilon}}R_{0}$, where $R_{0}=\|x_{0}-x^{*}\|$.
Denote $R=\|x_{s}-x^{*}\|$, where $x_{s}$ is a starting point of two-stage procedure and observe that $R_{0}\leq R$. Also, by Theorem 3.2, the gradient method requires $34L_{1}^{2}R^{2}$ number of iterations to obtain a point $\bar{x}$, such that $f(\bar{x})-f^{*}\leq\frac{L_{0}}{5L_{1}^{2}}$.
Combining these two results, we obtain the total complexity number, which is presented in the next theorem.

###### Theorem 6.2 .

Let $f(\cdot)$ be an $(L_{0},L_{1})$-smooth and convex function and $\{x_{k}\}$ be iterates from the two step-procedure (Algorithm 1)
with $T_{L}(\cdot)$ being a gradient update with stepsizes (11) or (11) ,
and $L=3L_{0}$. Then for a given $\epsilon>0$, we have $f(x_{K})-f^{*}\leq\epsilon$ when the number $K$ of oracle calls satisfies

$$ $K\geq m\sqrt{\frac{12L_{0}R^{2}}{\epsilon}}+36L_{1}^{2}R^{2},$ $$

where $m$ is a number of oracle calls to compute $y_{k}$.

Existing results on convex $(L_{0},L_{1})$-smooth problems include convergence of Nesterov Accelerated Gradient (NAG) method provided in \parenciteDBLP:conf/nips/LiQTRJ23 and Similar Triangles Method with Max (STM-max) from \parencitegorbunov2024methods.
However, the preceding rates depend the gradient norm $\|\nabla f(x_{0})\|$ at the initial point or the exponential factor $\exp(L_{1}R)$, both of which could be quite large if the initial point is far away from the minimizer.

Observe that the convergence rate from Theorem 6.2 includes $L_{1}$ without dependency on $\epsilon$, and it does not have an exponential dependency on the parameters $L_{0}$ and $L_{1}$ and initial distance $R$. Moreover, unlike the convergence rate for NAG obtained in [DBLP:conf/nips/LiQTRJ23] and Similar Triangles Method (STM) in [gorbunov2024methods], our rate does not depend on the gradient norm at the starting point. Because after the first stage of our procedure the gradient norm becomes smaller than $\frac{L_{0}}{L_{1}}$ and all the iterates of the second stage maintain this property and stay in the sublevel set $\mathcal{L}$ by construction.
However, AGMsDR at every step requires solving the one-dimensional problem to find the iterate $y_{k}$, which leads to an additional multiplicative factor $m$ in $m\sqrt{\frac{12L_{0}R^{2}}{\epsilon}}$. The corresponding one-dimensional problem can usually be solved efficiently with a small number $m$ of oracle calls for many practical problems. For simplicity, we are not estimating this number precisely and leave it for future work to understand how to estimate this complexity more precisely and whether it is possible to remove this one-dimensional search from the accelerated procedure.

###### Theorem 6.1 .

###### Theorem 6.2 .

## 7 Numerical Results

In Fig. 1, we compare the performance of the analyzed methods for solving optimization problem (1) with a function $f(x)=\frac{1}{p}\|x\|^{p}$ with a starting point such that $\|x_{0}\|=R$ for $R=10$, for different choices of $p\in\{4,6,8\}$. We fix $L_{1}=1$ and choose $L_{0}=(\frac{p-2}{L_{1}})^{p-2}$ according to Example 2.5. For the gradient method, we choose stepsizes according to 11, 14 and 15. While for the normalized gradient method we use time-varying coefficients $\beta_{k}=\frac{\hat{R}}{k+1}$, where the initial distance estimation $\hat{R}=2R$ is not too far from the true value $R$. This choice of estimated initial distance is motivated by the observation that normalized gradient method finds an optimal solution of $f(x)=\frac{1}{p}\|x\|^{p}$ in one iteration.

In Fig. 2, we present an experiment studying the performance of the gradient method with the stepsize rule 11 based on the choice of $(L_{0},L_{1})$. For each choice of $L_{1}\in\{1,2,4,8,16\}$ we set $L_{0}=(\frac{p-2}{L_{1}})^{p-2}$, according to Example 2.5. As expected from the theory (see the corresponding discussion at the end of Section 4), the choice of $(L_{0},L_{1})$ pair is crucial in practice for the performance of the gradient method and depends on a target accuracy $\epsilon$.

In Fig. 3, we conduct an experiment on tthe performance of accelerated methods and consider the gradient method with stetpsizes 11, the proposed two-stage procedure from Section 6 with $T_{L}(x)$ being the gradient method update with stepsize $L=4L_{0}$, and two variants of Similar Triangles Methods (STM, and STM-max) from [gorbunov2024methods]. We set $p=6$, $L_{1}=1$, and chose $L_{0}=(\frac{p-2}{L_{1}})^{p-2}$ according to Example 2.5 and compare the performance of the methods with different initial distances to the solution $\|x_{0}-x^{*}\|=R$, where $R\in\{5,100,500\}$.
We observe that for large initial distance to the solution our proposed procedure outperforms STM-max. This fact supports our theoretical founding and reasoning on accelerated methods provided in Section 6.
We also notice, that the second variant STM outperforms all considered methods, however, there is not theoretical analysis for it.

Figure: (a) $p=4$
Refer to caption: x1.png

Figure: (a) $p=4$
Refer to caption: x4.png

Figure: (a) $R=5$
Refer to caption: x7.png

## 8 Conclusion

This work investigates gradient methods for $(L_{0},L_{1})$-smooth optimization problems. We have provided new insights into this function class and presented examples along with the operations preserving the $(L_{0},L_{1})$-smoothness. Moreover, we have provided new properties of the function class that have rendered tighter bounds on the descent inequalities. Based on these tighter bounds, we derived new stepsizes for the gradient method and connected them with normalized and clipped stepsizes. For such stepsizes, we have shown the best-known $\mathcal{O}(\frac{L_{0}F_{0}}{\epsilon_{g}^{2}}+\frac{L_{1}F_{0}}{\epsilon_{g}})$ complexity for finding an $\epsilon_{g}$-stationary point in non-convex problems.
For convex problems, we have significantly improved the existing results and obtained the $\mathcal{O}(\frac{L_{0}R^{2}}{\epsilon}+L_{1}^{2}R^{2})$ complexity for the gradient method with our stepsizes. We have also analyzed the gradient method with Polyak stepsizes and a normalized gradient method that achieve a similar $\mathcal{O}(\frac{L_{0}R^{2}}{\epsilon}+L_{1}^{2}R^{2})$ complexity bound, which is significantly better than previously known complexity bounds.
Both of these methods are useful because they automatically adjust to the best possible pair of possible parameters $(L_{0},L_{1})$.
Finally, we have proposed a new procedure by combining our results on the gradient method with the AGMsDR method, and showed fast $\mathcal{O}(\sqrt{\frac{L_{0}R^{2}}{\epsilon}}+L_{1}^{2}R^{2})$ complexity bound which does not have the dependency on the initial gradient norm and does not have an exponential dependency on $L_{1}$, in contrast to previous works.
Whether it is possible to eliminate the line search for determining $y_{k}$ in AGMsDR method is an interesting open question for further research.

## Appendix A Missing Proofs in Section 2

### A.1 Proof of Lemma 2.2

###### Proof A.1 .

[2 $\implies$ 3]
Let $x,y\in\mathbb{R}^{d}$ be arbitrary and let $h:=y-x\neq 0$ (otherwise the claim is trivial).
Then, for any $t\in[0,1]$, using 2, we can estimate

$$ $\|\nabla f(x+th)-\nabla f(x)\|\leq\|h\|\int_{0}^{t}\|\nabla^{2}f(x+\tau h)\|d \tau\leq\|h\|\int_{0}^{t}(L_{0}+L_{1}\|\nabla f(x+\tau h)\|)d\tau=:\nu(t).$ $$

Our goal is to upper bound $\nu(1)$.
We may assume that $L_{1}>0$ since otherwise $\nu(1)=L_{0}\|h\|$ and the proof is finished.
Differentiating, we obtain, for any $t\in[0,1]$,

$$ $\nu^{\prime}(t)=L_{0}\|h\|+L_{1}\|h\|\|\nabla f(x+th)\|\leq(L_{0}+L_{1}\| \nabla f(x)\|)\|h\|+L_{1}\|h\|\nu(t),$ $$

where the final bound is due to the triangle inequality and the previous display.
Hence, for any $t\in[0,1]$, we have

$$ $\frac{d}{dt}\ln\bigl{[}(L_{0}+L_{1}\|\nabla f(x)\|+\epsilon)\|h\|+L_{1}\|h\| \nu(t)\bigr{]}\leq L_{1}\|h\|,$ $$

where $\epsilon>0$ is arbitrary(^5^55This additional term is needed to handle the possibility of $L_{0}+L_{1}\|\nabla f(x)\|$ being zero.).
Integrating this inequality in $t\in[0,1]$ and noting that $\nu(0)=0$, we get

$$ $\ln\frac{L_{0}+L_{1}\|\nabla f(x)\|+\epsilon+L_{1}\nu(1)}{L_{0}+L_{1}\|\nabla f (x)\|+\epsilon}\leq L_{1}\|h\|,$ $$

or, equivalently,

$$ $\nu(1)\leq(L_{0}+L_{1}\|\nabla f(x)\|+\epsilon)\frac{e^{L_{1}\|h\|}-1}{L_{1}}.$ $$

Passing now to the limit as $\epsilon\to 0$, we obtain 3.

[3 $\implies$ 4]
Let $x,y\in\mathbb{R}^{d}$ be arbitrary points and let $h:=y-x$.
Then, using 3, we can estimate

$$ $\displaystyle|f(y)-f(x)-\langle\nabla f(x),y-x\rangle|\leq\int_{0}^{1}|\langle \nabla f(x+th)-\nabla f(x),h\rangle|dt$ $\displaystyle\leq(L_{0}+L_{1}\|\nabla f(x)\|)\|h\|\int_{0}^{1}\frac{e^{L_{1}\| h\|t}-1}{L_{1}}dt=(L_{0}+L_{1}\|\nabla f(x)\|)\frac{e^{L_{1}\|h\|}-L_{1}\|h\|- 1}{L_{1}^{2}},$ $$

which is exactly 4.

[4 $\implies$ 2]
Let us fix an arbitrary point $x\in\mathbb{R}^{d}$ and an arbitrary unit vector $h\in\mathbb{R}^{d}$.
Then, for any $t>0$, it follows from 4 that

$$ $|f(x+th)-f(x)-t\langle\nabla f(x),h\rangle|\leq(L_{0}+L_{1}\|\nabla f(x)\|) \frac{e^{L_{1}t}-L_{1}t-1}{L_{1}^{2}}.$ $$

Dividing both sides by $t^{2}$ and passing to the limit as $t\to 0$, we get

$$ $|\langle\nabla^{2}f(x)h,h\rangle|\leq L_{0}+L_{1}\|\nabla f(x)\|.$ $$

This proves 2 since the unit vector $h$ was allowed to be arbitrary.

###### Proof A.1 .

### A.2 Proof of Lemma 2.4

###### Proof A.2 .

[Proof of 5]
Let $x,y\in\mathbb{R}^{d}$ be arbitrary points and let us assume w.l.o.g. that $L_{1}>0$.
In view of the convexity of $f$ and 4, for any $h\in\mathbb{R}^{d}$, we can write the following two inequalities:

$$ $\displaystyle 0$ $\displaystyle\leq$ $\displaystyle f(y+h)-f(x)-\langle\nabla f(x),y+h-x\rangle$ $\displaystyle\leq$ $\displaystyle\beta_{f}(x,y)+\langle\nabla f(y)-\nabla f(x),h\rangle+\frac{L_{0 }+L_{1}\|\nabla f(y)\|}{L_{1}^{2}}\phi(L_{1}\|h\|),$ $$

where $\beta_{f}(x,y):=f(y)-f(x)-\langle\nabla f(x),y-x\rangle$.
Denoting $a:=L_{0}+L_{1}\|\nabla f(y)\|>0$ and $s:=\nabla f(y)-\nabla f(x)$, we therefore obtain

$$ $\beta_{f}(x,y)\geq\max_{h\in\mathbb{R}^{d}}\Bigl{\{}\langle s,h\rangle-\frac{a }{L_{1}^{2}}\phi(L_{1}\|h\|)\Bigr{\}}=\max_{r\geq 0}\Bigl{\{}\|s\|r-\frac{a}{L _{1}^{2}}\phi(L_{1}r)\Bigr{\}}=\frac{a}{L_{1}^{2}}\phi_{*}\Bigl{(}\frac{L_{1} \|s\|}{a}\Bigr{)}.$ $$

[Proof of 8]
Summing up 5 with the same inequality but $x$ and $y$ interchanged, we obtain 8.

[Proof of 9]
By using a lower bound $\phi^{*}(\gamma)\geq\frac{\gamma^{2}}{2+\gamma}$ in 5 and denoting $a=\|\nabla f(x)-\nabla f(y)\|$ and $g=\|\nabla f(x)\|$, we obtain

$$ $\displaystyle f(y)$ $\displaystyle\geq f(x)+\langle\nabla f(x),y-x\rangle+\frac{L_{0}+L_{1}g}{L_{1} ^{2}}\frac{L_{1}^{2}a^{2}}{(L_{0}+L_{1}g)^{2}}\frac{L_{0}+L_{1}g}{2(L_{0}+L_{1 }g)+a}$ (21) $\displaystyle=f(x)+\langle\nabla f(x),y-x\rangle+\frac{a^{2}}{2(L_{0}+L_{1}g)+ a}.$ (22) $$

###### Proof A.2 .

### A.3 Proof of Example 2.5

###### Proof A.3 .

Differentiating, we obtain, for any $x\in\mathbb{R}^{d}$,

$$ $\nabla f(x)=\|x\|^{p-2}x,\qquad\nabla^{2}f(x)=\|x\|^{p-2}\biggl{(}I+(p-2)\frac {xx^{\top}}{\|x\|^{2}}\biggr{)},$ $$

where $I$ is the identity matrix.
Hence, for any $L_{1}>0$, the minimal value of $L_{0}$ satisfying the inequality from Definition 2.1 is given by

$$ $\displaystyle L_{0}=\max_{x\in\mathbb{R}^{d}}\bigl{\{}\|\nabla^{2}f(x)\|-L_{1} \|\nabla f(x)\|\bigr{\}}$ $\displaystyle=\max_{x\in\mathbb{R}^{d}}\bigl{\{}(p-1)\|x\|^{p-2}-L_{1}\|x\|^{p -1}\bigr{\}}$ $\displaystyle=\max_{\tau\geq 0}\bigl{\{}(p-1)\tau^{\frac{p-2}{p-1}}-L_{1}\tau \bigr{\}}.$ $$

The solution of the latter problem is $\tau^{*}=(\frac{p-2}{L_{1}})^{p-1}$.
Substituting this value, we obtain

$$ $L_{0}=(p-1)\Bigl{(}\frac{p-2}{L_{1}}\Bigr{)}^{p-2}-L_{1}\Bigl{(}\frac{p-2}{L_{ 1}}\Bigr{)}^{p-1}=\Bigl{(}\frac{p-2}{L_{1}}\Bigr{)}^{p-2}.$ $$

###### Proof A.3 .

### A.4 Proof of Example 2.6

###### Proof A.4 .

Differentiating, we obtain, for any $x\in\mathbb{R}$,

$$ $f^{\prime}(x)=\frac{e^{x}}{1+e^{x}}\in(0,1),\quad f^{\prime\prime}(x)=\frac{e^ {x}}{(1+e^{x})^{2}}=f^{\prime}(x)(1-f^{\prime}(x)).$ $$

Thus, for any $L_{1}\in[0,1]$, the minimal value of $L_{0}$ satisfying the inequality from Definition 2.1 is

$$ $\displaystyle L_{0}=\max_{x\in\mathbb{R}}\{|f^{\prime\prime}(x)|-L_{1}|f^{ \prime}(x)|\}$ $\displaystyle=\max_{\tau\in(0,1)}\{\tau(1-\tau)-L_{1}\tau\}$ $\displaystyle=\max_{\tau\in(0,1)}\{(1-L_{1})\tau-\tau^{2}\}=\frac{1}{4}(1-L_{1 })^{2}.$ $$

###### Proof A.4 .

### A.5 Proof of Proposition 2.7

###### Proof A.5 .

[Claim 1]
Since, $g$ and $\nabla g$ are $M$ and $L$ Lipschitz continuous, $\|\nabla g(x)\|\leq M$ and $\|\nabla^{2}g(x)\|\leq L$ for all $x\in\mathbb{R}$. Let $F=f+g$, then, for any $x\in\mathbb{R}^{d}$, we can estimate

$$ $\displaystyle\|\nabla^{2}F(x)\|$ $\displaystyle\leq\|\nabla^{2}f(x)\|+\|\nabla^{2}g(x)\|\leq L_{0}+L+L_{1}\| \nabla f(x)\|$ $\displaystyle\leq L_{0}+L+L_{1}\|\nabla g(x)\|+L_{1}\|\nabla F(x)\|$ $\displaystyle\leq(L_{0}+L_{1}M+L)+L_{1}\|\nabla F(x)\|.$ $$

[Claim 2]
Notice, that the gradient of $f$ is $\nabla f(x)=(\nabla f_{1}(x_{1})^{\top},\ldots,\nabla f_{n}(x_{n})^{\top})^{\top}$ and the Hessian of $f$ is $\nabla^{2}f(x)$ is a block-diagonal matrix, with $\nabla^{2}f_{i}(x_{i})$ blocks. Thus,

$$ $\displaystyle\|\nabla^{2}f(x)\|$ $\displaystyle=\max_{1\leq i\leq n}\|\nabla^{2}f_{i}(x_{i})\|\leq\max_{1\leq i \leq n}\{L_{0,i}+L_{1,i}\|\nabla f_{i}(x_{i})\|\}$ $\displaystyle\leq\max_{1\leq i\leq n}\{L_{0,i}+L_{1,i}\|\nabla f(x)\|\}\leq \max_{1\leq i\leq n}L_{0,i}+(\max_{1\leq i\leq n}L_{1,i})\|\nabla f(x)\|.$ $$

[Claim 3]
Observe that the gradient of a function is $\nabla f(x)=g^{\prime}(\langle a,x\rangle+b)a$, and the Hessian is $\nabla^{2}f(x)=g^{\prime\prime}(\langle a,x\rangle+b)aa^{\top}$. Hence,

$$ $\displaystyle\|\nabla^{2}f(x)\|=|g^{\prime\prime}(\langle a,x\rangle+b)|\|a\|^ {2}$ $\displaystyle\leq(L_{0}+L_{1}|g^{\prime}(\langle a,x\rangle+b)|)\|a\|^{2}$ $\displaystyle=L_{0}\|a\|^{2}+\|a\|L_{1}\|\nabla f(x)\|.$ $$

[Claim 4]
Under our assumptions, $s=\nabla f(x)$ is a one-to-one transformation from $\mathbb{R}^{d}$ to $\mathbb{R}^{d}$ (whose inverse transformation is $x=\nabla f_{*}(s)$); moreover, the Hessians at such a pair of points are inverse to each other: $\nabla^{2}f_{*}(s)=[\nabla^{2}f(x)]^{-1}$ (see, e.g., Corollaries 4.1.4 and 4.2.10 in [hiriart1993convex], as well as Example 11.9 from [rockafellar2009variational]).
Thus, for any pair of points $x,s\in\mathbb{R}^{d}$ such that $s=\nabla f(x)$, our assumption $\|\nabla^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla f(x)\|$ which, due to the convexity of $f$, can be equivalently rewritten as $\nabla^{2}f(x)\preceq(L_{0}+L_{1}\|\nabla f(x)\|)I$, is equivalent to

$$ $\nabla^{2}f_{*}(s)\equiv[\nabla^{2}f(x)]^{-1}\succeq\frac{1}{L_{0}+L_{1}\| \nabla f(x)\|}I\equiv\frac{1}{L_{0}+L_{1}\|s\|}I.$ $$

This proves the claim since the transformation $s=\nabla f(x)$ is one-to-one.

###### Proof A.5 .

## Appendix B Missing Proofs in Section 3

###### Lemma B.1 .

Let $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be an $(L_{0},L_{1})$-smooth function, let $x\in\mathbb{R}^{d}$, and let $T(x)=x-\eta\nabla f(x)$, where $\eta$ is given by one of the following formulas:

$$ $\displaystyle(1)\;\eta_{*}=\dfrac{1}{L_{1}\|\nabla f(x)\|}\ln\Bigl{(}1+\frac{L _{1}\|\nabla f(x)\|}{L_{0}+L_{1}\|\nabla f(x)\|}\Bigr{)},\quad(2)\;\eta=\frac{ 1}{L_{0}+\frac{3}{2}L_{1}\|\nabla f(x)\|},$ $\displaystyle(3)\;\eta_{\mathrm{cl}}=\min\Bigl{\{}\frac{1}{2L_{0}},\frac{1}{3L _{1}\|\nabla f(x)\|}\Bigr{\}}.$ $$

Then,

$$ $f(x)-f(T(x))\geq\frac{a\|\nabla f(x)\|^{2}}{2L_{0}+3L_{1}\|\nabla f(x)\|},$ $$

where $a=1$ in cases (1) and (2), and $a=\frac{1}{2}$ in case (3).

###### Proof B.2 .

[Case (1)] The proof of this case was already presented in Section 3.

For the other two cases, we start by applying Lemma 2.2 to get

$$ $\displaystyle\Delta\coloneq f(x)-f(T(x))$ $\displaystyle\geq\langle\nabla f(x),x-T(x)\rangle-\frac{L_{0}+L_{1}\|\nabla f( x)\|}{L_{1}^{2}}\phi(L_{1}\|T(x)-x\|)$ $\displaystyle=\eta g^{2}-\frac{L_{0}+L_{1}g}{L_{1}^{2}}\phi(\eta L_{1}g),$ $$

where $g\coloneq\|\nabla f(x)\|$ and $\phi(t)=e^{t}-t-1$.

[Case (2)]
Estimating $\phi(t)\leq\frac{3t^{2}}{6-2t}\leq\frac{t^{2}}{2-t}$ (see Lemma 2.3 (1)) and substituting the definition of $\eta$, we can continue as follows:

$$ $\displaystyle\Delta$ $\displaystyle\geq\eta g^{2}-\frac{L_{0}+L_{1}g}{L_{1}^{2}}\frac{\eta^{2}L_{1}^ {2}g^{2}}{2-\eta L_{1}g}=\biggl{(}1-\frac{(L_{0}+L_{1}g)\eta}{2-\eta L_{1}g} \biggr{)}\eta g^{2}$ $\displaystyle=\biggl{(}1-\frac{L_{0}+L_{1}g}{(L_{0}+\frac{3}{2}L_{1}g)(2-\frac {L_{1}g}{L_{0}+\frac{3}{2}L_{1}g})}\biggr{)}\frac{g^{2}}{L_{0}+\frac{3}{2}L_{1 }g}=\frac{g^{2}}{2L_{0}+3L_{1}g}.$ $$

[Case (3)]
Observe that

$$ $\frac{1}{2L_{0}+3L_{1}g}\leq\eta_{\mathrm{cl}}\equiv\frac{1}{\max\{2L_{0},3L_{ 1}g\}}\leq\frac{1}{L_{0}+\frac{3}{2}L_{1}g}.$ $$

Combining these bounds with $\phi(t)\leq\frac{3t^{2}}{6-2t}$ (Lemma 2.3 (1)), we get

$$ $\displaystyle\Delta$ $\displaystyle\geq\eta_{\mathrm{cl}}g^{2}-\frac{L_{0}+L_{1}g}{L_{1}^{2}}\frac{3 L_{1}^{2}\eta_{\mathrm{cl}}^{2}g^{2}}{6-2\eta_{\mathrm{cl}}L_{1}g}=\biggl{(}1- \frac{3\eta_{\mathrm{cl}}(L_{0}+L_{1}g)}{6-2\eta_{\mathrm{cl}}L_{1}g}\biggr{)} \eta_{\mathrm{cl}}g^{2}$ $\displaystyle\geq\biggl{(}1-\frac{3(L_{0}+L_{1}g)}{(L_{0}+\frac{3}{2}L_{1}g)(6 -\frac{2L_{1}g}{L_{0}+\frac{3}{2}L_{1}g})}\biggr{)}\frac{g^{2}}{2L_{0}+3L_{1}g}$ $\displaystyle=\biggl{(}1-\frac{3(L_{0}+L_{1}g)}{6L_{0}+7L_{1}g}\biggr{)}\frac{ g^{2}}{2L_{0}+3L_{1}g}\geq\frac{1}{2}\frac{g^{2}}{2L_{0}+3L_{1}g}.$ $$

###### Lemma B.1 .

###### Proof B.2 .

### B.1 Proof of Theorem 3.1

###### Proof B.3 .

For stepsizes choices (11) and  (14) and  (15) (up to a constant) in gradient method the inequality (13) holds (see Lemma B.1). Thus, substituting $x=x_{k}$ and $T(x)=x_{k+1}$, we have for all $k\geq 0$:

$$ $\displaystyle f(x_{k})-f(x_{k+1})\geq\frac{\|\nabla f(x_{k})\|^{2}}{2L_{0}+3L_ {1}\|\nabla f(x_{k})\|}.$ $$

By summing it over $k\in[0,\ldots,K]$ we get

$$ $f(x_{0})-f^{*}\geq f(x_{0})-f(x_{K+1})\geq\sum_{k=0}^{K}\frac{\|\nabla f(x_{k} )\|^{2}}{2L_{0}+3L_{1}\|\nabla f(x_{k})\|}\geq(K+1)\frac{\|\nabla f(x^{*}_{K}) \|^{2}}{2L_{0}+3L_{1}\|\nabla f(x_{K}^{*})\|},$ $$

where $x_{K}^{*}=\operatorname*{arg\,min}_{k\in[0,\ldots,K]}\|f(x_{k})\|$.
Denoting $F_{0}=f(x_{0})-f^{*}$, $g_{K}^{*}=\|\nabla f(x_{K}^{*})\|$ and solving the quadratic inequality, we obtain

$$ $\displaystyle g_{K}^{*}\leq\dfrac{\sqrt{9L_{1}^{2}F_{0}^{2}+8(K+1)L_{0}F_{0}}+ 3L_{1}F_{0}}{2(K+1)}\leq\sqrt{\dfrac{2L_{0}F_{0}}{K+1}}+\dfrac{3L_{1}F_{0}}{K+ 1},$ $$

where the final inequality is due to the fact that $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$.
To achieve an $\epsilon$-solution, we want to make each term less than $\frac{\epsilon}{2}$. Thus, the total number of iterations $T$ required to achieve an $\epsilon$-solution is $T\geq\max\{\frac{8L_{0}F_{0}}{\epsilon^{2}},\frac{6L_{1}F_{0}}{\epsilon}\}$.

###### Proof B.3 .

### B.2 Proof of Theorem 3.2

###### Proof B.4 .

Denoting $R_{k}=\|x_{k}-x^{*}\|,f_{k}=f(x_{k})-f^{*},\beta_{k}=\langle\nabla f(x_{k}),x_
{k}-x^{*}\rangle$ and $g_{k}=\|\nabla f(x_{k})\|$ we use the update rule of the method and get

$$ $\displaystyle R_{k+1}^{2}=R_{k}^{2}-2\eta_{k}\beta_{k}+\eta_{k}^{2}g_{k}^{2}.$ $$

Using the last inequality (9) in Lemma 2.4 with $x=x^{*}$ and $y=x_{k}$ we obtain,

$$ $f_{k}\geq\frac{g_{k}^{2}}{2L_{0}+3L_{1}g_{k}}$ $$

(Case I stepsizes 11) Substituting $x=x_{k}$ and $y=x^{*}$ in inequality (9) of Lemma 2.4, we get:

$$ $\beta_{k}\geq f_{k}+\frac{g_{k}^{2}}{2L_{0}+L_{1}g_{k}}\geq\frac{1}{2L_{0}+3L_ {1}g_{k}}+\frac{g_{k}^{2}}{2L_{0}+L_{1}g_{k}}\geq\frac{1}{L_{0}+L_{1}g_{k}}.$ $$

Next, define $\xi(g)\equiv\frac{g^{2}}{L_{0}+\frac{3}{2}L_{1}g}$. Using a bound $\frac{2t}{2+t}\leq\ln(1+t)\leq t$ we achieve,

$$ $R_{k}^{2}-R_{k+1}^{2}\geq\frac{2\beta_{k}}{L_{0}+\frac{3}{2}L_{1}g_{k}}-\frac{ g_{k}^{2}}{(L_{0}+\frac{3}{2}L_{1}g_{k})^{2}}\geq\frac{\beta_{k}\xi(g_{k})}{g_ {k}^{2}}\geq\Bigl{(}\frac{\beta_{k}}{\xi^{-1}(\beta_{k})}\Bigr{)}^{2}.$ $$

[Case 2, stepsizes (14)]
Using the estimating $\langle\nabla f(x_{k}),x_{k}-x^{*}\rangle\geq f(x_{k})-f^{*}\equiv f_{k}$, we get

$$ $R_{k}^{2}-R_{k+1}^{2}\geq\frac{2f_{k}}{2L_{0}+3L_{1}g_{k}}-\frac{g_{k}^{2}}{(2 L_{0}+3L_{1}g_{k})^{2}}.$ $$

From 9, we know that $f_{k}\geq\psi(g_{k})$, where $\psi(g)=\frac{g^{2}}{2L_{0}+3L_{1}g}$ is an increasing function.
Hence, we can continue as follows:

$$ $R_{k}^{2}-R_{k+1}^{2}\geq\frac{f_{k}}{2L_{0}+3L_{1}g_{k}}=\frac{f_{k}\psi(g_{k })}{g_{k}^{2}}.$ $$

Since $\frac{\psi(g)}{g^{2}}$ is decreasing in $g$ and $g_{k}\leq\psi^{-1}(f_{k})$, we can estimate $\frac{\psi(g_{k})}{g_{k}^{2}}\geq\frac{f_{k}}{[\psi^{-1}(f_{k})]^{2}}$.
Thus,

$$ $R_{k}^{2}-R_{k+1}^{2}\geq\Bigl{(}\frac{f_{k}}{\psi^{-1}(f_{k})}\Bigr{)}^{2},$ $$

In both cases similar inequality holds
By summing these inequalities over $k\in[0,\ldots,K]$ and rearranging terms, we get

$$ $\displaystyle\sum_{k=0}^{K}\Bigl{(}\frac{f_{k}}{\psi^{-1}(f_{k})}\Bigr{)}^{2} \leq R_{0}^{2}-R_{k+1}^{2}.$ $$

Note that $\frac{\psi^{-1}(t)}{t}$ is increasing in $t$ (as the composition of increasing in $\gamma$ function $\frac{\psi(\gamma)}{\gamma}\equiv\frac{\gamma}{2L_{0}+3L_{1}\gamma}$ with increasing in $t$ function $\gamma=\psi^{-1}(t)$). Thus, by taking a minimum over the terms on the left-hand side of the above display and denoting $x_{K}^{*}=\operatorname*{arg\,min}_{x\in\{x_{0},\ldots,x_{K}\}}f(x)$ and $f_{K}^{*}=f(x_{K}^{*})-f^{*}=\min_{0\leq k\leq K}f_{k}$, we get

$$ $\displaystyle K\Bigl{(}\frac{f_{K}^{*}}{\psi^{-1}(f_{K}^{*})}\Bigr{)}^{2}\leq R _{0}^{2}.$ $$

Rearranging, we obtain

$$ $\displaystyle\psi^{-1}(f_{K}^{*})\geq\frac{\sqrt{K}f_{K}^{*}}{R_{0}},$ $$

or, equivalently,

$$ $\displaystyle f_{K}^{*}\geq\psi\Bigl{(}\frac{\sqrt{K}f_{K}^{*}}{R_{0}}\Bigr{)} \equiv\frac{K(f_{K}^{*})^{2}}{R_{0}^{2}\bigl{(}2L_{0}+3L_{1}\frac{\sqrt{K}f_{K }^{*}}{R_{0}}\bigr{)}}=\frac{(f_{K}^{*})^{2}}{\frac{2L_{0}R_{0}^{2}}{K}+\frac{ 3L_{1}R_{0}}{\sqrt{K}}f_{K}^{*}}.$ $$

Hence,

$$ $\displaystyle f_{K}^{*}\leq\frac{2L_{0}R_{0}^{2}}{K(1-3L_{1}R_{0}\sqrt{K})},$ $$

whenever $3L_{1}R_{0}\sqrt{K}<1$.
Thus, to achieve desired accuracy $\epsilon>0$, the number $K$ of iterations should satisfy the following conditions:

$$ $3L_{1}R_{0}\sqrt{K}\leq\frac{1}{2},\qquad\frac{4L_{0}R_{0}^{2}}{K}\leq\epsilon.$ $$

Thus, the final iteration complexity is $K\geq\max\{\frac{4L_{0}R_{0}^{2}}{\epsilon},36L_{1}^{2}R_{0}^{2}\}$.

###### Proof B.4 .

## Appendix C Missing Proofs in Section 4

### C.1 Proof of Theorem 4.1

###### Proof C.1 .

Let $x^{*}$ be a minimizer of $f$.
Then, according to the normalized gradient method update (16) and the definition of $v_{k}\coloneq\frac{\langle\nabla f(x_{k}),x_{k}-x^{*}\rangle}{\|\nabla f(x_{k}
)\|}$ ($\geq 0$), we have

$$ $\displaystyle\|x_{k+1}-x^{*}\|^{2}$ $\displaystyle=\|x_{k}-x^{*}\|^{2}-2\eta_{k}\langle\nabla f(x_{k}),x_{k}-x^{*} \rangle+\eta_{k}^{2}\|\nabla f(x_{k})\|^{2}$ $\displaystyle=\|x_{k}-x^{*}\|^{2}-2\beta_{k}v_{k}+\beta_{k}^{2}.$ $$

Summing up these relations over $k=0,\ldots,K$ and rearranging the terms, we obtain

$$ $\displaystyle 2\sum_{k=0}^{K}\beta_{k}v_{k}\leq R^{2}+\sum_{k=0}^{K}\beta_{k}^ {2},$ $$

where $R\coloneq\|x_{0}-x^{*}\|$.
Denoting $v_{K}^{*}=\min_{0\leq k\leq K}v_{k}$ and substituting $\beta_{k}=\frac{\hat{R}}{\sqrt{K+1}}$, we get

$$ $\displaystyle v_{K}^{*}\leq\frac{R^{2}+\sum_{k=0}^{K}\beta_{k}^{2}}{2\sum_{k=0 }^{K}\beta_{k}}=\frac{R^{2}+\hat{R}^{2}}{2\hat{R}\sqrt{K+1}}=\frac{\bar{R}}{2 \sqrt{K+1}},$ $$

where $\bar{R}\coloneq\frac{R^{2}}{\hat{R}}+\hat{R}$.
Let $f_{K}^{*}\coloneq\min_{0\leq k\leq K}f(x_{k})$.
Then, by Lemma 4.2,

$$ $\displaystyle f_{K}^{*}-f^{*}\leq\max_{z}\{f(z)-f^{*}:\|z-x^{*}\|\leq v_{K}^{* }\}.$ $$

Applying Lemma 2.2 and the fact that $\phi(t)=e^{t}-t-1\leq\frac{3t^{2}}{6-2t}$ for $t\in[0,3)$, we obtain

$$ $f_{K}^{*}-f^{*}\leq\frac{L_{0}}{L_{1}^{2}}\phi(L_{1}\|x_{K}-x^{*}\|)\leq\frac{ L_{0}}{L_{1}^{2}}\phi(L_{1}v_{K}^{*})\leq\frac{3L_{0}(v_{K}^{*})^{2}}{6-2L_{1} v_{K}^{*}}\leq\frac{3L_{0}\bar{R}^{2}}{\left(K+1\right)(6-\frac{2L_{1}\bar{R}} {\sqrt{K+1}})},$ $$

whenever the corresponding denominators are strictly positive.
Thus, to achieve the desired accuracy $\epsilon>0$, it suffices to set $K$ satisfying the following two inequalities:

$$ $\frac{2L_{1}\bar{R}}{\sqrt{K+1}}\leq 3,\qquad\dfrac{L_{0}\bar{R}^{2}}{K+1}\leq\epsilon.$ $$

This is $K\geq\max\{\frac{L_{0}\bar{R}^{2}}{\epsilon},\frac{4}{9}L_{1}^{2}\bar{R}^{2}\}$.

In case when the stepsizes $\beta_{k}=\frac{\hat{R}}{\sqrt{k+1}}$ are decreasing, the bound on $v_{K}^{*}$ has a form,

$$ $\displaystyle v_{K}^{*}\leq\frac{\|x_{0}-x^{*}\|^{2}+\sum_{k=0}^{K}\beta_{k}^{ 2}}{2\sum_{k=0}^{K}\beta_{k}}\leq\frac{R^{2}+\hat{R}^{2}\log(K+1)}{4\hat{R}( \sqrt{K+1}-\sqrt{2})},$ $$

And by using the same reasoning be arrive at

$$ $\displaystyle f(x_{K}^{*})-f^{*}$ $\displaystyle\leq\frac{3L_{0}\bar{R}^{2}(\log(K+1))^{2}}{4(\sqrt{K+1}-\sqrt{2} )^{2}}\frac{1}{\left(6-\frac{L_{1}\bar{R}\log(K+1)}{\hat{R}(\sqrt{K+1}-\sqrt{2 })}\right)}.$ $$

###### Proof C.1 .

## Appendix D Missing Proofs in Section 5

### D.1 Proof of Theorem 5.1

###### Proof D.1 .

Let $x^{*}$ be an arbitrary solution.
By the method’s update rule and convexity of $f(\cdot)$, we get, for all $k\geq 0$,

$$ $\displaystyle\|x_{k+1}-x^{*}\|^{2}$ $\displaystyle=\|x_{k}-x^{*}\|^{2}-2\eta_{k}\langle\nabla f(x_{k}),x_{k}-x^{*} \rangle+\eta_{k}^{2}\|\nabla f(x_{k})\|^{2}$ $\displaystyle\leq\|x_{k}-x^{*}\|^{2}-\frac{(f(x_{k})-f^{*})^{2}}{\|\nabla f(x_ {k})\|^{2}}.$ $$

Denote $R_{k}=\|x_{k}-x^{*}\|$, $g_{k}=\|\nabla f(x_{k})\|$ and $f_{k}=f(x_{k})-f^{*}$.
According to Lemma 2.4, for each $k\geq 0$, it holds that

$$ $\displaystyle f_{k}\geq\psi(g_{k}),\qquad\text{where}\quad\psi(g):=\frac{g^{2} }{2L_{0}+3L_{1}g},\quad g\geq 0.$ $$

Observe that the function $\psi$ is increasing, so its inverse $\psi^{-1}$ is well-defined and is increasing as well.
In terms of this function, $g_{k}\leq\psi^{-1}(f_{k})$ and hence

$$ $\displaystyle R_{k}^{2}-R_{k+1}^{2}\geq\frac{f_{k}^{2}}{g_{k}^{2}}\geq\Bigl{(} \frac{f_{k}}{\psi^{-1}(f_{k})}\Bigr{)}^{2}.$ $$

By summing these inequalities over $k\in[0,\ldots,K]$ and rearranging terms, we get

$$ $\displaystyle\sum_{k=0}^{K}\Bigl{(}\frac{f_{k}}{\psi^{-1}(f_{k})}\Bigr{)}^{2} \leq R_{0}^{2}-R_{k+1}^{2}.$ $$

Note that $\frac{\psi^{-1}(t)}{t}$ is increasing in $t$ (as the composition of increasing in $\gamma$ function $\frac{\psi(\gamma)}{\gamma}\equiv\frac{\gamma}{2L_{0}+3L_{1}\gamma}$ with increasing in $t$ function $\gamma=\psi^{-1}(t)$). Thus, by taking a minimum over the terms on the left-hand side of the above display and denoting $x_{K}^{*}=\operatorname*{arg\,min}_{x\in\{x_{0},\ldots,x_{K}\}}f(x)$ and $f_{K}^{*}=f(x_{K}^{*})-f^{*}=\min_{0\leq k\leq K}f_{k}$, we get

$$ $\displaystyle K\Bigl{(}\frac{f_{K}^{*}}{\psi^{-1}(f_{K}^{*})}\Bigr{)}^{2}\leq R _{0}^{2}.$ $$

Rearranging, we obtain

$$ $\displaystyle\psi^{-1}(f_{K}^{*})\geq\frac{\sqrt{K}f_{K}^{*}}{R_{0}},$ $$

or, equivalently,

$$ $\displaystyle f_{K}^{*}\geq\psi\Bigl{(}\frac{\sqrt{K}f_{K}^{*}}{R_{0}}\Bigr{)} \equiv\frac{K(f_{K}^{*})^{2}}{R_{0}^{2}\bigl{(}2L_{0}+3L_{1}\frac{\sqrt{K}f_{K }^{*}}{R_{0}}\bigr{)}}=\frac{(f_{K}^{*})^{2}}{\frac{2L_{0}R_{0}^{2}}{K}+\frac{ 3L_{1}R_{0}}{\sqrt{K}}f_{K}^{*}}.$ $$

Hence,

$$ $\displaystyle f_{K}^{*}\leq\frac{2L_{0}R_{0}^{2}}{K(1-3L_{1}R_{0}\sqrt{K})},$ $$

whenever $3L_{1}R_{0}\sqrt{K}<1$.
Thus, to achieve desired accuracy $\epsilon>0$, the number $K$ of iterations should satisfy the following conditions:

$$ $3L_{1}R_{0}\sqrt{K}\leq\frac{1}{2},\qquad\frac{4L_{0}R_{0}^{2}}{K}\leq\epsilon.$ $$

Thus, the final iteration complexity is $K\geq\max\{\frac{4L_{0}R_{0}^{2}}{\epsilon},36L_{1}^{2}R_{0}^{2}\}$.

###### Proof D.1 .

## Appendix E Missing Proofs in Section 6

The proof of Theorem 6.1 is similar to the original proof Theorem 1 in [nesterov2021primal], but instead of smoothness of $f$ we use more general property provided in the statement of Theorem 6.1.

### E.1 Proof of Theorem 6.1

###### Proof E.1 .

Let us prove by induction that, for any $k\geq 0$, we have

$$ $A_{k}f(x_{k})\leq\zeta_{k}^{*}\coloneq\zeta_{k}(v_{k}).$ (23) $$

This trivially holds for $k=0$ since $A_{0}=0$ and $\zeta_{0}^{*}=0$. Now assume that 23 is satisfied for some $k\geq 0$ and let us prove that it is also satisfied for the next index $k^{\prime}=k+1$. We start by noting that

$$ $\displaystyle\zeta_{k+1}^{*}$ $\displaystyle=\zeta_{k+1}(v_{k+1})=\zeta_{k}(v_{k+1})+a_{k+1}[f(y_{k})+\langle \nabla f(y_{k}),v_{k+1}-y_{k}\rangle]$ (24) $\displaystyle\geq\zeta_{k}^{*}+\frac{1}{2}\|v_{k+1}-v_{k}\|^{2}+a_{k+1}[f(y_{k })+\langle\nabla f(y_{k}),v_{k+1}-y_{k}\rangle]$ (25) $\displaystyle\geq A_{k}f(x_{k})+\frac{1}{2}\|v_{k+1}-v_{k}\|^{2}+a_{k+1}[f(y_{ k})+\langle\nabla f(y_{k}),v_{k+1}-y_{k}\rangle],$ (26) $$

where the first inequality holds due to the strong convexity of $\zeta_{k}$, and the second one is due to the induction hypothesis.
Further, note that, by construction, $y_{k}\in[v_{k},x_{k}]$.
Considering separately any of the three possible situations, $y_{k}=v_{k}$, $y_{k}=x_{k}$ and $y_{k}\in(v_{k},x_{k})$, we see that, in all cases,

$$ $\langle\nabla f(y_{k}),v_{k}-y_{k}\rangle\geq 0.$ $$

Then, by adding and subtracting $\langle\nabla f(y_{k}),v_{k}\rangle$ in 24 and using the estimate in the preceding inequality, as well as $f(y_{k})\leq f(x_{k})$ (which holds by construction), we obtain

$$ $\displaystyle\zeta_{k+1}^{*}$ $\displaystyle\geq A_{k}f(x_{k})+a_{k+1}f(y_{k})+\frac{1}{2}\|v_{k+1}-v_{k}\|^{ 2}+a_{k+1}\langle\nabla f(y_{k}),v_{k+1}-v_{k}\rangle$ $\displaystyle\geq A_{k+1}f(y_{k})+\frac{1}{2}\|v_{k+1}-v_{k}\|^{2}+a_{k+1} \langle\nabla f(y_{k}),v_{k+1}-v_{k}\rangle$ $\displaystyle\geq A_{k+1}f(y_{k})-\frac{a_{k+1}^{2}}{2}\|\nabla f(y_{k})\|^{2} =A_{k+1}\Bigl{[}f(y_{k})-\frac{1}{2L}\|\nabla f(y_{k})\|^{2}\Bigr{]},$ $$

where the final identity is due to fact that, by the definition of $a_{k+1}$,

$$ $La_{k+1}^{2}=A_{k+1}.$ (27) $$

By the induction step and by construction, $y_{k}$ stays in the sublevel set $\mathcal{F}_{0}$, since $f(y_{k})\leq f(x_{k})\leq f(x_{0})$. Then, by the statement of the theorem,
we have $f(x_{k+1})\leq f(y_{k})-\frac{1}{2L}\|\nabla f(y_{k})\|^{2}$.
This proves that $\zeta_{k+1}^{*}\geq A_{k+1}f(x_{k+1})$ completing the induction.

Let $k\geq 1$ be arbitrary.
By the convexity of $f$ and the definition of $A_{k}$, we have

$$ $\zeta_{k}^{*}\leq\zeta_{k}(x^{*})=\frac{1}{2}R^{2}+\sum_{i=0}^{k-1}a_{i+1}[f(y _{i})+\langle\nabla f(y_{i}),x^{*}-y_{i}\rangle]\leq\frac{1}{2}R^{2}+A_{k}f^{*}.$ $$

where $R=\|x_{0}-x^{*}\|$.
Combining this with 23, we conclude that

$$ $f(x_{k})-f^{*}\leq\frac{LR^{2}}{2A_{k}}.$ (28) $$

It remains to estimate the rate of growth of the coefficients $A_{k}$.
From 27 and the definition of $A_{k+1}$, it follows, for any $k\geq 0$, that

$$ $\displaystyle\sqrt{\frac{A_{k+1}}{L}}=a_{k+1}=A_{k+1}-A_{k}$ $\displaystyle=(\sqrt{A_{k+1}}+\sqrt{A_{k}})(\sqrt{A_{k+1}}-\sqrt{A_{k}})$ $\displaystyle\leq 2\sqrt{A_{k+1}}(\sqrt{A_{k+1}}-\sqrt{A_{k}}).$ $$

Dividing both sides of this inequality by $\sqrt{A_{k+1}}$ and summing up the result, we see that,
for any $k\geq 1$, it holds that

$$ $\displaystyle A_{k}\geq\frac{k^{2}}{4L}.$ $$

Substituting this estimate into 28, we obtain the claim.

###### Proof E.1 .

### E.2 Proof of Theorem 6.2

###### Proof E.2 .

Based on Theorem 3.2 the number of iterations required to find a point $\bar{x}$, such that $f(\bar{x})-f^{*}\leq\frac{L_{0}}{5L_{1}^{2}}$ is $36L_{1}^{2}R^{2}$. Using the Lemma 2.2 and reasoning from Section 6, we have $\|\nabla f(\bar{x})\|\leq\frac{L_{0}}{L_{1}}$ and consequently $L_{0}+L_{1}\|\nabla f(\bar{x})\|\leq 2L_{0}$.
By equation (13),

$$ $f(T_{L}(x))\leq f(x)-\frac{1}{5L_{0}}\|\nabla f(x)\|^{2}\leq f(x)-\frac{1}{2L} \|\nabla f(x)\|^{2}.$ $$

Hence, a point $x_{0}=\bar{x}$ and parameter $L=3L_{0}$ satisfy the condition of Theorem 6.1. Then, by Theorem 6.1, AGMsDR with this choice of $x_{0}$ and $L$, requires $\sqrt{\frac{12L_{0}}{\epsilon}}R$ number of iterations to achieve $f(x_{k})-f^{*}\leq\epsilon$. Combining complexities of both methods we obtained the desired $36L_{1}^{2}R^{2}+\sqrt{\frac{12L_{0}}{\epsilon}}R$ complexity.

###### Proof E.2 .

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Writing issues (in the order of appearance)
- In pg. 3, lines 108-109, it will be illustrative to explain in more detail in which aspects the authors' proof techniques differ from that of the work [1], cited as Gorbunov et al. (2024) in the manuscript. Also I think the authors should be more cautious about claiming that the proof is more "elegant" than something else. One possible suggestion is to emphasize their clearer parallelism with the classical theory, rather than to describe the value of this paper's framework with a subjective expression like "elegant".
- The statement of Lemma 2.2 involves the notation $\phi(t) = e^t - t - 1$, while its proof in the Appendix uses the symbol $\phi$ to denote something else. Please change it.
- The bound $\phi_* (\gamma) \ge \frac{\gamma^2}{2+\gamma}$ appears suddenly in the statement of Lemma 2.3, while the relevant discussion appears later in Section 3. I think this should be relocated to somewhere near Lemma 2.3.
- In pg. 4, lines 164-165, the meaning of the sentence "we present some examples to support the choice of generalized smooth assumption" is unclear.
- Proposition 2.6 and the subsequent discussion doesn't seem very relevant to the rest of the paper. To some readers this information could be valuable, but generally speaking, I even think the whole part can be moved to the Appendix without altering the flow of the paper. Also, please clearly define the expressions like "$M$-Lipschitz twice continuously differentiable" before using it.
- In line 183-184, there is dangling "for some" after the period.
- In Theorem 3.1, it should have been assumed/defined that $f^* := \inf f > - \infty$. In general, the authors did not properly state that they assume the existence of a minimizer $x^*$, etc. (in subsequent theorems regarding convex cases). Please be precise about these points.
- In the statement of Theorem 3.2, is $||x_0 - x^*||$ intended to be denoted as $R_0$?
- In pg. 6, in lines 297-298, it is not clear what the authors mean with "by using the preceding estimate and the update rule of the method". Only after reading the proof in the Appendix I could understand the technique deriving equation (20), and I still do not feel that the text surrounding the equation is successfully conveying the idea. If you intend to provide a high-level intuition, please be more precise and detailed. Also, note that the exponent 2 is missing in $R_{k+1}^2$ within (20), and in equation (43), the $g_k^2$ factors seem to be missing.
- Lines 304-310 provide an interesting insight on the complexity $\mathcal{O}(L_0 R_0^2 / \epsilon + L_1^2 R_0^2)$, but I think the complexity analysis does not clearly show that the constant $\mathcal{O}(L_1^2 R_0^2)$ complexity corresponds to the phase where the algorithm reaches the regime where $f$ behaves like a smooth function. (Which is in contrast with Section 6, where the algorithm is deliberately designed in this way.) Can this discussion somehow be made more precise?
- In Theorem 4.2, $R$ is used without being defined.
- I do not see any reason why Lemma 4.1 is introduced in pg. 7. I think a discussion on how (22) is utilized in the analysis is missing.
- In lines 349-350, the authors say "time-varying stepsizes can be eliminated", but this seems to be a conjecture (or at least, something that the authors do not formally prove) and I think it should be reworded. Please be careful about making such statement.
- In pg. 8, lines 378-380, the authors emphasize that their rate does not have an exponential dependency on $L_0, L_1$, but why does this worth emphasis? Are there prior work which analyzed gradient method with Polyak stepsizes in the same setup and obtained rate that involves $\exp (L_0), \exp (L_1)$? If so, please specify.
- In lines 400-401, the authors mention that "Our rate is better than $\mathcal{O}(L_0 R^2 / \epsilon + \sqrt{L / \epsilon} L_1 R^2)$", but where does this rate come from?
- In the beginning of Section 6 (and also the same for Sections 4, 5) please clearly specify in the first sentence introducing the setup that you are dealing with convex functions.
- It is weird that Algorithm 1 (which is not the algorithm that the authors develop) is packaged using the Algorithm environment, while the authors' algorithm (lines 427-431) isn't. 
- The Step 1 of the authors' algorithm in Section 6 requires to find a point $\bar{x}$ satisfying $f(\bar{x}) - f(x^*) \le \frac{L_0}{8 L_1^2}$. I think this requires either the knowledge of $f(x^*)$ or $R=||x_0 - x^*||$ (in order to determine when to stop). Is this understanding correct? If so, this is a limitation that should be clearly explained.
- Theorem 6.1 misses the convexity assumption in the statement. Also, it analyzes the AGMsDR algorithm with initial point satisfying  $f(x_0) - f(x^*) \le \frac{L_0}{8 L_1^2}$, but this is inconsistent with the $\bar{x}$ notation used in lines 427-431. I think this also comes from the problem of not highlighting their "procedure" as a separate algorithm with a proper name.
- In lines 477-478, should the two occurrences of $R$ be the same values? It seems like one is $||x_0 - x^*||$ and one is $||\bar{x} - x^*||$.
- In line 483, the authors again mention "not have an exponential dependency". Please cite a relevant prior work explaining why this is worth emphasis.
- It is not clearly defined what the figure labels like NGD, GD1, GD2, etc. precisely means. Even though it could be speculated if one reads through Section 7, this should be done somewhere, for example, within the figure caption.
- In Figure 2, please specify that you are using $L_0 = (\frac{p-2}{L_1})^{p-2}$ according to Example 2.4 (if this understanding is correct).

[1] Gorbunov et al., Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity.
soundness: 4
strengths: As mentioned in the Summary section, this paper nicely demonstrates the parallelism of how the traditional techniques from smooth (convex) minimization should be properly interpreted and applied to the class of $(L_0, L_1)$-smooth functions. As a reader who is much more familiar with the classical optimization theory but not as much with the recent theory of $(L_0, L_1)$-smooth optimization, the paper was interesting, easily readable, and informative. It seems such viewpoint has not been provided previously with this level of clarity, and I think this work could serve as a solid reference for those future readers who are interested in this area. The algorithms and their convergence results the paper provides within various setups seem correct and competitive.
summary: This paper provides a general understanding of the $(L_0, L_1)$-smooth function class, which has recently gained increasing interest due to its empirically observed connections to deep learning applications. They authors establish a parallelism between the classical optimization theory for $L_0$-smooth functions, and show how analogous inequalities and algorithm design strategies should be carried out with $(L_0, L_1)$-smooth functions. This includes the derivation of $(L_0, L_1)$-smooth version of the cocoercivity inequality, analysis of fixed-stepsize gradient descent method for convex and nonconvex cases, and analysis of gradient methods using normalized stepsizes, Polyak stepsizes, and Nesterov-type acceleration for convex functions.
weaknesses: The primary weakness of the current version of the paper is the writing. While I think the technical contents are good, the writing does not seem to be polished carefully enough and should be managed before the publication. The general flow is okay, but there are many detailed points which I would recommend the authors to address; please refer to the Questions section. I would recommend acceptance of the paper provided that the writing issues get resolved.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: See weakness
soundness: 3
strengths: 1. The paper is well-written and easy to follow. The analysis is thorough and offers many insights for research in optimization.

2. I appreciate the comparison between this paper and Gorbunov et al. (2024), which is comprehensive and particularly crucial for readers.

3. I have attempted to implement some of the suggested algorithms and found that the analysis presented here is essential for practical use, especially when the optimal step size in equation (11) is given explicitly.
summary: The paper studies gradient methods for solving problems with (L0, L1)-smoothness, a recent class of functions developed by Zhang et al. (2019). Novel convergence results are established in this paper, including tighter bounds on function growth and the complexity bound for finding near stationary points in both nonconvex and convex cases. Some new methods with different step sizes are also examined.
weaknesses: The following are some major concerns about the paper.

1. The numerical experiments are conducted only on simple functions. I suggest that the authors significantly improve this section by employing more diverse examples, particularly in nonconvex cases. For examples, could the authors consider loss functions from deep learning models or other challenging nonconvex optimization problems from applications?

2. If I have not overlooked anything, the current paper does not discuss the difficulties of deriving the convergence properties for (L0, L1)-smooth functions compared to L-smooth functions, nor how the authors overcome these challenges. Can the author discuss key challenges in analyzing (L0,L1)-smooth functions compared to L-smooth functions, and to highlight any novel theoretical tools or techniques they developed to overcome these challenges.

3. I do not find Proposition 2.6 impressive, as the results are rather predictable, and the proofs seem straighforward. 

4. The authors mention that "we cannot guarantee that the class is closed under all standard operations, such as the summation". Can you provide a concrete counterexample showing that the sum of two (L0,L1)-smooth functions is not necessarily (L0,L1)-smooth? If so, are there any additional conditions that could guarantee the sum remains in this function class?

5. The authors claim that the estimate in (4) is tighter than those presented in previous works. Can you provide a numerical example or theoretical argument demonstrating how your estimate in (4) is tighter than previous bounds? Is it possible to prove that this bound is optimal, or are there cases where it could potentially be improved further?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Another way to dispense of the dependency of the constants $L_0$ and $L_1$ in the step-size is to perform backtracking line-search, which also guarantees descents in the objective function value. Can the given new bounds (Lemma 2.2, 2.3) improve the rate derived by Hubler et al 2024?

2. For Theorem 6.1, empirically, is there any way to tell when to switch to AGMsDR? That is, can we tell that we are in a local region?

3. Have you tried experimenting with a softmax function, which I believe the constants $L_0$ and $L_1$ can be analytically evaluated? This example will provide more insights than the simple function $||\mathbf{x}||^p$.
soundness: 3
strengths: To me, one of this paper's main strengths/contributions is the derivation of tighter first-order upper and lower bounds. The bounds will undoubtedly help any further work on analyzing this particular function class.

In Theorems 3.2 and 5.1, the author(s) is able to dispense $L$-gradient Lipschitz, which was additionally assumed in the previous works Koloskova et al 2023, while improving the current existing rate.

The overall flow of the paper is well-presented.
summary: The author(s) present non-asymptotic convergent analyses of various types of gradient methods on convex and non-convex functions satisfying $(L_0, L_1)$-smoothness, which is a type of generalized smoothness assumption that has gained some interests recently in machine learning community.

They derive a series of first-order upper bounds, implied by the generalized smoothness assumption, which are tigher bounds than previous works. Furthermore, they derive similar lower bounds when the functions are convex.

Using these newly derived bounds, they present a convergent analysis on non-convex functions, which matches the current best-known rate of this function class up to absolute constants.

For convex functions, however, they derive better-than-existing convergent rates for different gradient methods of this particular function class.

Finally, they experiment with a simple $||\mathbf{x}||^p / p$ function, where the constants $L_0$ and $L_1$ can be known in advance.
weaknesses: 1. Numerical results can be strengthened by providing more experiments.

2. For Theorem 3.1, even though your rate is better than the rate provided in Hubler et al 2024, they do not have the dependency on $L_0$ and $L_1$ (See section Questions, 1.).

3. (line 269) I believe "By Theorem 3.1, the smallest number K of iterations required to achieve ..." is incorrect, as one can happen to choose an initial point such that $\|\| \nabla f(x_{0}) || < \epsilon_{\mathbf{g}}$. In this case, $K = 0$, which violates your claim here. The correct wording should be "By Theorem 3.1, obtaining the stationary point requires at most ... ".

4. (Theorem 5.1) The presentation of your theorems should be consistent. It is recommended to present in the form of "$K \geq $", like in your other theorems. 

5. $||\mathbf{x}_0 - \mathbf{x}^*||$ is denoted to be both $R_0$ and $R$, e.g., Theorem 3.2. Notations should be consistent.

6. (line 257) "absolte" -> "absolute"

7. (eq. 14) I think the inequality should be $... \geq \frac{||\nabla f(x)||^2}{2L_0 + 3L_1||\nabla f(x)||}$, i.e., there is no 2 in the numerator (c.f. Lemma B.1)

8. (line 641) I think $s$ should be $s := \nabla f(x) - \nabla f(y)$. Otherwise, the sign in the inequality at line 643 is incorrect.

9. (line 648) Change $\phi^*(\gamma)$ to $\phi_*(\gamma)$ to maintain consistency.

10. (line 651) Some of the gradients should be of variable $y$, not just $x$, i.e., $\nabla f(y)$.

---

confidence: 5
contribution: 3
initial_rating: 5
presentation: 3
questions: - As a contribution authors listed in line 54 "tighter bounds on descent inequalities". But in line 58 authors "achieve the best-known" rate for non convex functions. I am curious if the tighter bounds actually helps to improve convergence. I would expect improving the rate, if they actually help. As far as I understand, the tighter bounds are supposed to help for the non-simplified stepsize version and some logarithmic improving factor should appear. Am I right? Could the authors answer this question by providing rates with their tighter bounds and with non-tight bounds?
- Acceleration does not seems fair. By initially running non-accelerated method authors enter the area where $\|\|\nabla f(x) \|\|\leq \frac{L_0}{L_1}$, making the right hand side of the generalized smoothness condition (line 121) $L_0 + L_1|\|\nabla f(x) \|\| \leq 2L_0$, that corresponds to the standard smoothness assumption. 
   - In the standard $L$-smooth case there exist accelerated methods without line search (e.g. Similar Triangles Method), that keep iteration bounded ($\|\|x^k - x^* \|\|  \leq R \cdot const$), so I am expecting such methods stay in the area. Can the line search be avoided in your analysis? Or what is it crucial role? 

  - The term  $L^2_1 R^2$ corresponds to the number of iteration to enter the area with bounded gradient. Then the authors in fact deal with the standard $2L$-smooth case, while obtaining the other term. This observation is consistent with non-accelerated methods, considered in the paper. I would like to note, that acceleration in fact is used only in the area where the standard $2L$-smooth case takes place, and does not help to enter the area faster. In other words I would say that the contribution in fact is -- a bound on the number of oracle calls to enter this area. And I am expecting this bound to be improved in the accelerated case. Don't get me wrong, but I could not consider the convergence of AGMSDR in the standard $2L$-smooth case as a contribution. I would like authors to address my concerns, and clarify about their contribution to this part. Is it an application of the authors result of non-accelerated method to bound the number to enter the area with bounded gradient? 

I would like to comment on the scores. Taking the above questions into account, I currently accept the contributions related to first-order methods. The results are new and significantly improve previous rates. But they rely on the only basic result -- descent inequalities. The rest is an application of the new inequalities to the well-known methods. That is why I consider the contribution as limited. I open for a discussion and the authors are likely to expect higher scores if my concerns are convincingly addressed, especially about the area with bounded gradient.
soundness: 3
strengths: - For convex problems, authors improves existing results by achieving $O( L_0R^2 / \varepsilon + L^2_1 R^2)$
- Normalized gradient method and gradient method with Polyak stepsizes, which do not require the knowledge of the parameters $L_0$, $L_1$ and have the same rate as above
- Accelerated method with $O( \sqrt{L_0R^2 / \varepsilon} + L^2_1 R^2)$
summary: The paper examines the extension of a certain optimization method to a broader smoothness assumption, specifically $L_0,L_1$-smoothness. While it broadens the class of functions to be minimized, the authors manage to recover convergence rates comparable to those of the standard $L$-smooth case, albeit with an additional term that does not depend on the final accuracy.
weaknesses: - Lack of analysis  for stochastic case is significantly limiting practical value of the work
- Accelerated method requires a line search (minor)
- The second part of the second question from below

Meta-review: The paper studies gradient methods for optimization problems with \((L_0, L_1)\)-smooth objectives, a generalization of Lipschitz-smooth functions. It offers new insights into this class and introduces a unified analysis framework for related methods. The authors establish state-of-the-art complexity guarantees for the simple gradient method in both convex and non-convex settings. They also analyze two variants--Polyak stepsize and normalized gradient methods--achieving optimal bounds without requiring prior parameter knowledge. Additionally, the paper extends accelerated gradient methods to this function class, demonstrating desirable convergence properties.

Overall the reviewers agree that the paper is interesting, contains several novel ideas, and makes notable contributions to the theory of first-order optimization methods.

Decision: Accept (Poster)