Convex and Non-convex Optimization Under Generalized Smoothness

Introduction

In this paper, we study the following unconstrained optimization problem

Recently, Zhang et al. (2019) proposed the more general $(L_{0},L_{1})$-smoothness condition, which assumes $\left\|\nabla^{2}f(x)\right\|\leq L_{0}+L_{1}\left\|\nabla f(x)\right\|$ for some constants $L_{0},L_{1}\geq 0$, motivated by their extensive language model experiments. This notion generalizes the standard Lipschitz smoothness condition and also contains e.g. univariate polynomial and exponential functions. For non-convex and $(L_{0},L_{1})$-smooth functions, they prove convergence of gradient descent (GD) and stochastic gradient descent (SGD) with gradient clipping and also provide a complexity lower bound for constant-stepsize GD/SGD without clipping. Based on these results, they claim gradient clipping or other forms of adaptivity provably accelerate the convergence for $(L_{0},L_{1})$-smooth functions. Perhaps due to the lower bound, all the follow-up works under this condition that we are aware of limit their analyses to adaptive methods. Most of these focus on non-convex functions. See Section 2 for more discussions of related works.

Contributions. In light of the above discussions, we summarize our main contributions as follows.

We prove the convergence of constant-stepsize GD/SGD/NAG in the convex and non-convex settings, and obtain the classical rates for all of them, as summarized in Table 1.

Besides the generalized smoothness condition and the new approach, our results are also novel in the following aspects.

The convergence results of constant-stepsize methods challenge the folklore belief on the necessity of adaptive stepsize for generalized smooth functions.

We obtain new convergence results for GD and NAG in the convex setting under the generalized smoothness condition.

We relax the assumption of bounded noise to the weaker one of bounded variance of noise in the stochastic setting with the simple SGD method.

Related work

Gradient-based optimizaiton. The classical gradient-based optimization problems for the standard Lipschitz smooth functions have been well studied for both convex (Nemirovskij and Yudin, 1983; Nesterov, 2003; d’Aspremont et al., 2021) and non-convex functions. In the convex setting, the goal is to reach an $\epsilon$-sub-optimal point $x$ satisfying $f(x)-\inf_{x}f(x)\leq\epsilon$. It is well known that GD achieves the $\mathcal{O}(1/\epsilon)$ gradient complexity and NAG achieves the accelerated $\mathcal{O}(1/\sqrt{\epsilon})$ complexity which is optimal among all gradient-based methods. For strongly convex functions, GD and NAG achieve the $\mathcal{O}(\kappa\log(1/\epsilon))$ and $\mathcal{O}(\sqrt{\kappa}\log(1/\epsilon))$ complexity respectively, where $\kappa$ is the condition number and the latter is again optimal. In the non-convex setting, the goal is to find an $\epsilon$-stationary point $x$ satisfying $\left\|\nabla f(x)\right\|\leq\epsilon$, since finding a global minimum is NP-hard in general. It is well known that GD achieves the optimal $\mathcal{O}(1/\epsilon^{2})$ complexity which matches the lower bound in (Carmon et al., 2017). In the stochastic setting for unbiased stochastic gradient with bounded variance, SGD achieves the optimal $\mathcal{O}(1/\epsilon^{4})$ complexity (Ghadimi and Lan, 2013), matching the lower bound in (Arjevani et al., 2019). In this paper, we obtain the classical rates in terms of $\epsilon$ for all the above-mentioned methods and settings, under a far more general smoothness condition.

Generalized smoothness. The $(L_{0},L_{1})$-smoothness condition proposed by Zhang et al. (2019) was studied by many follow-up works. Under the same condition, (Zhang et al., 2020) considers momentum in the updates and improves the constant dependency of the convergence rate for SGD with clipping derived in (Zhang et al., 2019). (Qian et al., 2021) studies gradient clipping in incremental gradient methods, (Zhao et al., 2021) studies stochastic normalized gradient descent, and (Crawshaw et al., 2022) studies a generalized SignSGD method, under the $(L_{0},L_{1})$-smoothess condition. (Reisizadeh et al., 2023) studies variance reduction for $(L_{0},L_{1})$-smooth functions. (Chen et al., 2023) proposes a new notion of $\alpha$-symmetric generalized smoothness, which is roughly as general as $(L_{0},L_{1})$-smoothness. (Wang et al., 2022) analyzes convergence of Adam and provides a lower bound which shows non-adaptive SGD may diverge. In the stochastic setting, the above-mentioned works either consider the strong assumption of bounded gradient noise or require a very large batch size that depends on $\epsilon$, which essentially reduces the analysis to the deterministic setting. (Faw et al., 2023) proposes an AdaGrad-type algorithm in order to relax the bounded noise assumption. Perhaps due to the lower bounds in (Zhang et al., 2019; Wang et al., 2022), all the above works study methods with an adaptive stepsize. In this and our concurrent work (Li et al., 2023), we further generalize the smoothness condition and analyze various methods under this condition through bounding the gradients along the trajectory.

Function class

In this section, we discuss the function class of interest where the objective function $f$ lies. We start with the following two standard assumptions in the literature of unconstrained optimization, which will be assumed throughout Sections 4 and 5 unless explicitly stated.

The objective function $f$ is differentiable and closed within its open domain $\mathcal{X}$.

The objective function $f$ is bounded from below, i.e., $f^{*}:=\inf_{x\in\mathcal{X}}f(x)>-\infty$.

In this section, we formally define the generalized smoothness condition, and present its properties and examples.

Definitions 1 and 2 below are two equivalent ways of stating the definition, where we use $\mathcal{B}(x,R)$ to denote the Euclidean ball with radius $R$ centered at $x$.

Next, we prove that the above two definitions are equivalent in the following proposition, whose proof is involved and deferred to Appendix A.2.

The condition in Definition 1 is simple and one can easily check whether it is satisfied for a given example function. On the other hand, Definition 2 is a local Lipschitz condition on the gradient that is harder to verify. However, it is useful for deriving several useful properties in the next section.

1.2 Properties

First, we provide the following lemma which is very useful in our analyses of all the methods considered in this paper. Its proof is deferred to Appendix A.3.

Lemma 3.3 states that, if the gradient at $x$ is bounded by some constant $G$, then within its neighborhood with a constant radius, we can obtain (2), the same inequalities that were derived in the textbook analysis (Nesterov, 2003) under the standard Lipschitz smoothness condition. With (2), the analysis for generalized smoothness is not much harder than that for standard smoothness. Since we mostly choose $x=x_{2}=x_{t}$ and $x_{1}=x_{t+1}$ in the analysis, in order to apply Lemma 3.3, we need two conditions: $\left\|\nabla f(x_{t})\right\|\leq G$ and $\left\|x_{t+1}-x_{t}\right\|\leq r(G)$ for some constant $G$. The latter is usually directly implied by the former for most deterministic methods with a small enough stepsize, and the former can be obtained with our new approach that bounds the gradients along the trajectory.

With Lemma 3.3, we can derive the following useful lemma which is the reverse direction of a generalized Polyak-Lojasiewicz (PL) inequality, whose proof is deferred to Appendix A.3.

Therefore, in order to bound the gradients along the trajectory as we discussed below Lemma 3.3, it suffices to bound the function values, which is usually easier.

1.3 Examples

Convex setting

In this section, we present the convergence results of gradient descent (GD) and Nesterov’s accelerated gradient method (NAG) in the convex setting. Formally, we define convexity as follows.

We assume the existence of a global optimal point $x^{*}$ throughout this section, as in the following assumption. However, we want to note that, for gradient descent, this assumption is just for simplicity rather than necessary.

There exists a point $x^{*}\in\mathcal{X}$ such that $f(x^{*})=f^{*}=\inf_{x\in\mathcal{X}}f(x)$.

The gradient descent method with a constant stepsize $\eta$ is defined via the following update rule

As discussed below Lemma 3.3, the key in the convergence analysis is to show $\left\|\nabla f(x_{t})\right\|\leq G$ for all $t\geq 0$ and some constant $G$. We will prove it by induction relying on the following lemma whose proof is deferred to Appendix B.

Lemma 4.1 suggests that for gradient descent (3) with a small enough stepsize, if the gradient norm at $x_{t}$ is bounded by $G$, then we have $\left\|\nabla f(x_{t+1})\right\|\leq\left\|\nabla f(x_{t})\right\|\leq G$, i.e., the gradient norm is also bounded by $G$ at $t+1$. In other words, the gradient norm is indeed a non-increasing potential function for gradient descent in the convex setting. With a standard induction argument, we can show that $\left\|\nabla f(x_{t})\right\|\leq\left\|\nabla f(x_{0})\right\|$ for all $t\geq 0$. As discussed below Lemma 3.3, then we can basically apply the classical analysis to obtain the convergence guarantee in the convex setting as in the following theorem, whose proof is deferred to Appendix B.

Since $\eta$ is a constant independent of $\epsilon$ or $T$, Theorem 4.2 achieves the classical $\mathcal{O}(1/T)$ rate, or $\mathcal{O}(1/\epsilon)$ gradient complexity to achieve an $\epsilon$-sub-optimal point, under the generalized smoothness condition. Since strongly convex functions are a subset of convex functions, Lemma 4.1 still holds for them. Then we immediately obtain the following result in the strongly convex setting, whose proof is deferred to Appendix B.

2 Nesterov’s accelerated gradient method

It is easy to note that Theorem 4.4 achieves the accelerated $\mathcal{O}(1/T^{2})$ convergence rate, or equivalently the $\mathcal{O}(1/\sqrt{\epsilon})$ gradient complexity to find an $\epsilon$-sub-optimal point, which is optimal among gradient-based methods (Nesterov, 2003).

In order to prove Theorem 4.4, we also use induction to show the gradients along the trajectory of Algorithm 1 are bounded by $G$. However, unlike gradient descent, the gradient norm is no longer a potential function or monotonically non-increasing, which makes the induction analysis more challenging. Suppose that we have shown $\left\|\nabla f(y_{s})\right\|\leq G$ for $s<t$. To complete the induction, it suffices to prove $\left\|\nabla f(y_{t})\right\|\leq G$. Since $x_{t}=y_{t-1}-\eta\nabla f(y_{t-1})$ is a gradient descent step by Line 6 of Algorithm 1, Lemma 4.1 directly shows $\left\|\nabla f(x_{t})\right\|\leq G$. In order to also bound $\left\|\nabla f(y_{t})\right\|$, we try to control $\left\|y_{t}-x_{t}\right\|$, which is the most challenging part of our proof. Since $y_{t}-x_{t}$ can be expressed as a linear combination of past gradients $\{\nabla f(y_{s})\}_{s<t}$, it might grow linearly with $t$ if we simply apply $\left\|\nabla f(y_{s})\right\|\leq G$ for $s<t$. Fortunately, Lemma 3.5 allows us to control the gradient norm with the function value. Thus if the function value is decreasing sufficiently fast, which can be shown by following the standard Lyapunov analysis of NAG, we are able to obtain a good enough bound on $\left\|\nabla f(y_{s})\right\|$ for $s<t$, which allows us to control $\left\|y_{t}-x_{t}\right\|$. We defer the detailed proof to Appendix C.

Non-convex setting

In this section, we present convergence results of gradient descent (GD) and stochastic gradient descent (SGD) in the non-convex setting.

Similar to the convex setting, we still want to bound the gradients along the trajectory. However, in the non-convex setting, the gradient norm is not necessarily non-increasing. Fortunately, similar to the classical analyses, the function value is still non-increasing and thus a potential function, as formally shown in the following lemma, whose proof is deferred to Appendix E.

Then using a standard induction argument, we can show $f(x_{t})\leq f(x_{0})$ for all $t\geq 0$. According to Corollary 3.6, it implies bounded gradients along the trajectory. Therefore, we can show convergence of gradient descent as in the following theorem, whose proof is deferred to Appendix E.

It is clear that Theorem 5.2 gives the classical $\mathcal{O}(1/\epsilon^{2})$ gradient complexity to achieve an $\epsilon$-stationary point, which is optimal as it matches the lower bound in (Carmon et al., 2017).

2 Stochastic gradient descent

In this part, we present the convergence result for stochastic gradient descent defined as follows.

where $g_{t}$ is an estimate of the gradient $\nabla f(x_{t})$. We consider the following standard assumption on the gradient noise $\epsilon_{t}:=g_{t}-\nabla f(x_{t})$.

Under Assumption 4, we can obtain the following theorem.

As we choose $\eta=\mathcal{O}(1/\sqrt{T})$, Theorem 5.3 gives the classical $\mathcal{O}(1/\epsilon^{4})$ gradient complexity, where we ignore non-leading terms. This rate is optimal as it matches the lower bound in (Arjevani et al., 2019). The key to its proof is again to bound the gradients along the trajectory. However, bounding gradients in the stochastic setting is much more challenging than in the deterministic setting, especially with the heavy-tailed noise in Assumption 4. We briefly discuss some of the challenges as well as our approach below and defer the detailed proof of Theorem 5.3 to Appendix F.

First, due to the existence of heavy-tailed gradient noise as considered in Assumption 4, neither the gradient nor the function values is non-increasing. The induction analyses we have used in the deterministic setting hardly work. In addition, to apply Lemma 3.3, we need to control the update at each step and make sure $\left\|x_{t+1}-x_{t}\right\|=\eta\left\|g_{t}\right\|\leq G/L$. However, $g_{t}$ might be unbounded due to the potentially unbounded gradient noise.

To overcome these challenges, we define the following random variable $\tau$.

3 Reconciliation with existing lower bounds

In this section, we reconcile our convergence results for constant-stepsize GD/SGD in the non-convex setting with existing lower bounds in (Zhang et al., 2019) and (Wang et al., 2022), based on which the authors claim that adaptive methods such as GD/SGD with clipping and Adam are provably faster than non-adaptive GD/SGD. This may seem to contradict our convergence results. In fact, we show that any gain in adaptive methods is at most by constant factors, as GD and SGD already achieve the optimal rates in the non-convex setting.

(Zhang et al., 2019) provides both upper and lower complexity bounds for constant-stepsize GD for $(L_{0},L_{1})$-smooth functions, and shows that its complexity is $\mathcal{O}(M\epsilon^{-2})$, where

is the supremum gradient norm below the level set of the initial function value. If $M$ is very large, then the $\mathcal{O}(M\epsilon^{-2})$ complexity can be viewed as a negative result, and as evidence that constant-stepsize GD can be slower than GD with gradient clipping, since in the latter case, they obtain the $\mathcal{O}(\epsilon^{-2})$ complexity without $M$. However, based on our Corollary 3.6, their $M$ can be actually bounded by our $G$, which is a constant. Therefore, the gain in adaptive methods is at most by constant factors.

(Wang et al., 2022) further provides a lower bound which shows non-adaptive GD may diverge for some examples. However, their counter-example does not allow the stepsize to depend on the initial sub-optimality gap. In contrast, our stepsize $\eta$ depends on the effective smoothness constant $L$, which depends on the initial sub-optimality gap through $G$. Therefore, there is no contradiction here either. We should point out that in the practice of training neural networks, the stepsize is usually tuned after fixing the loss function and initialization, so it does depend on the problem instance and initialization.

4 Lower bound

For $(\rho,L_{0},L_{\rho})$-smooth functions with $\rho<2$, it is easy to verify that the constant $G$ in both Theorem 5.2 and Theorem 5.3 is a polynomial function of problem-dependent parameters like $L_{0},L_{\rho},f(x_{0})-f^{*},\sigma$, etc. In other words, GD and SGD are provably efficient methods in the non-convex setting for $\rho<2$. In this section, we show that the requirement of $\rho<2$ is necessary in the non-convex setting with the lower bound for GD in the following Theorem 5.4, whose proof is deferred in Appendix G. Since SGD reduces to GD when there is no gradient noise, it is also a lower bound for SGD.

Given $L_{0},L_{2},G_{0},\Delta_{0}>0$ satisfying $L_{2}\Delta_{0}\geq 10$, for any $\eta\geq 0$, there exists a $(2,L_{0},L_{2})$-smooth function $f$ that satisfies Assumptions 1 and 2, and initial point $x_{0}$ that satisfies $\|\nabla f(x_{0})\|\leq G_{0}$ and $f(x_{0})-f^{\ast}\leq\Delta_{0}$, such that gradient descent with stepsize $\eta$ (3) either cannot reach a $1$-stationary point or takes at least $\exp(L_{2}\Delta_{0}/8)/6$ steps to reach a $1$-stationary point.

Conclusion

Acknowledgments

This work was supported, in part, by the MIT-IBM Watson AI Lab and ONR Grants N00014-20-1-2394 and N00014-23-1-2299. We also acknowledge support from DOE under grant DE-SC0022199, and NSF through awards DMS-2031883, DMS-1953181, and DMS-2022448 (TRIPODS program).

References

Appendix A Proofs related to generalized smoothness

In this section, we provide the proofs of propositions and lemmas related to the generalized smoothness condition in Definition 1 or 2. First, in Appendix A.1, we justify the examples we discussed in Section 3. Next, we provide the detailed proof of Proposition 3.2 in Appendix A.2. Finally, we provide the proofs of the useful properties of generalized smoothness in Appendix A.3, including Lemma 3.3, Lemma 3.5, and Corollary 3.6 stated in Section 3.1.2.

In this section, we justify the univariate examples of $(\rho,L_{0},L_{\rho})$-smooth functions listed in Table 2 and also provide the proof of Propositions 3.7.

First, it is well-known that all quadratic functions have bounded Hessian and are Lipschitz smooth, corresponding to $\rho=0$. Next, [Zhang et al., 2019, Lemma 2] shows that any univariate polynomial is $(L_{0},L_{1})$-smooth, corresponding to $\rho=1$. Then, regarding the exponential function $f(x)=a^{x}$ where $a>1$, we have $f^{\prime}(x)=\log(a)a^{x}$ and $f^{\prime\prime}(x)=\log(a)^{2}a^{x}=\log(a)f^{\prime}(x)$, which implies $f$ is $(1,0,\log(a))$-smooth. Similarly, by standard calculations, it is straight forward to verify that logarithmic functions and $x^{p}$, $p\neq 1$ are also $(\rho,L_{0},L_{\rho})$-smooth with $\rho=2$ and $\rho=\frac{p-2}{p-1}$ respectively. So far we have justified all the examples in Table 2 except double exponential functions $a^{(b^{x})}$ and rational functions, which will be justified rigorously by the two propositions below.

First, for double exponential functions in the form of $f(x)=a^{(b^{x})}$ where $a,b>1$, we have the following proposition, which shows $f$ is $(\rho,L_{0},L_{\rho})$-smooth for any $\rho>1$.

For any $\rho>1$, the double exponential function $f(x)=a^{(b^{x})}$, where $a,b>1$, is $(\rho,L_{0},L_{\rho})$-smooth for some $L_{0},L_{\rho}\geq 0$. However, it is not necessarily $(L_{0},L_{1})$-smooth for any $L_{0},L_{1}\geq 0$.

Next, to show $f$ is not necessarily $(L_{0},L_{1})$-smooth, consider the specific double exponential function $f(x)=e^{(e^{x})}$. Then we have

For any $x\geq\max\left\{\log(L_{0}+1),\log(L_{1}+1)\right\}$, we can show that

which shows $f$ is not $(L_{0},L_{1})$ smooth for any $L_{0},L_{1}\geq 0$. ∎

In the next proposition, we show that any univariate rational function $f(x)=P(x)/Q(x)$, where $P$ and $Q$ are two polynomials, is $(\rho,L_{0},L_{\rho})$-smooth with $\rho=1.5$.

The rational function $f(x)=P(x)/Q(x)$, where $P$ and $Q$ are two polynomials, is $(1.5,L_{0},L_{1.5})$-smooth for some $L_{0},L_{1.5}\geq 0$. However, it is not necessarily $(\rho,L_{0},L_{\rho})$-smooth for any $\rho<1.5$ and $L_{0},L_{\rho}\geq 0$.

Let $f(x)=P(x)/Q(x)$ where $P$ and $Q$ are two polynomials. Then the partial fractional decomposition of $f(x)$ is given by

Then we have $f(x)=w(x)+\sum_{i=1}^{m}\sum_{r=1}^{j_{i}}p_{ir}(x)+\sum_{i=1}^{n}\sum_{r=1}^{k_{i}}q_{ir}(x)$. We know that $\frac{r+2}{r+1}\leq 1.5$ for any $r\geq 1$. Then we can show that

where the first equality is because one can easily verify that the first and second order derivatives of $p_{ij_{i}}$ dominate those of all other terms when $x$ goes to $a_{i}$, and the second equality is by standard calculations noting that $\frac{j_{i}+2}{j_{i}+1}\leq 1.5$. Note that (7) implies that, for any $L_{\rho}>j_{i}+1$, there exists $\delta_{i}>0$ such that

Similarly, one can show $\lim_{x\to\infty}\frac{\left|f^{\prime}(x)\right|^{1.5}}{\left|f^{\prime\prime}(x)\right|}=\infty$, which implies there exists $x_{0}>0$ such that

We know $\mathcal{B}$ is a compact set and therefore the continuous function $f^{\prime\prime}$ is bounded within $\mathcal{B}$, i.e., there exists some constant $L_{0}>0$ such that

Combining (8), (9), and (10), we have shown

which completes the proof of the first part.

For the second part, consider the ration function $f(x)=1/x$. Then we know that $f^{\prime}(x)=-1/x^{2}$ and $f^{\prime\prime}(x)=2/x^{3}$. Note that for any $\rho<1.5$ and $0<x\leq\min\{(L_{0}+1)^{-1/3},(L_{\rho}+1)^{-1/(3-2\rho)}\}$, we have

which shows $f$ is not $(\rho,L_{0},L_{\rho})$ smooth for any $\rho<1.5$ and $L_{0},L_{\rho}\geq 0$. ∎

Finally, we complete this section with the proof of Proposition 3.7, which shows self-concordant functions are $(2,L_{0},L_{2})$-smooth for some $L_{0},L_{\rho}\geq 0$.

Integrating both sides from $x_{0}$ to $y$ for $x_{0},y\in(a,b)$, we have

Since $h^{\prime\prime}(y)>0$, we have $\left|h^{\prime\prime}(y)\right|=h^{\prime\prime}(y)$. Therefore, the above inequality shows that $h$ is $(2,L_{0},L_{2})$-smooth with $L_{0}=2(h^{\prime\prime}(x_{0})^{1/2}-h^{\prime}(x_{0}))^{2}$ and $L_{2}=2$. ∎

A.2 Proof of Proposition 3.2

In order to prove Proposition 3.2, we need the following several lemmas. First, the lemma below partially generalizes Grönwall’s inequality.

Let $\alpha:[a,b]\to[0,\infty)$ and $\beta:[0,\infty)\to(0,\infty)$ be two continuous functions. Suppose $\alpha^{\prime}(t)\leq\beta(\alpha(t))$ almost everywhere over $(a,b)$. Denote function $\phi(u):=\int\frac{1}{\beta(u)}\,du$. We have for all $t\in[a,b]$,

Integrating both sides, noting that $\gamma(a)=\alpha(a)$ by (11), we obtain

Then it suffices to show $\phi(\alpha(t))\leq\phi(\gamma(t)),\;\forall t\in[a,b]$. Note that the following inequality holds almost everywhere.

where the inequality is because $\alpha^{\prime}(t)\leq\beta(\alpha(t))$ by the assumption of this lemma and $\gamma^{\prime}(t)=\beta(\gamma(t))$ by (11). Since $\phi(\alpha(a))-\phi(\gamma(a))=0$, we know for all $t\in[a,b]$, $\phi(\alpha(t))\leq\phi(\gamma(t))$, which completes the proof. ∎

With Lemma A.3, one can bound the gradient norm within a small enough neighborhood of a given point as in the following lemma.

Denote $z(t):=(1-t)x+ty$ for $0\leq t\leq 1$. Then we know $z(t)\in\mathcal{X}$ for all $0\leq t\leq 1$ by the assumption made in this lemma. Then we can also define $\alpha(t):=\left\|\nabla f(z(t))\right\|$ for $0\leq t\leq 1$. Note that for any $0\leq t\leq s\leq 1$, by triangle inequality,

We know that $\alpha(t)=\left\|\nabla f(z(t))\right\|$ is differentiable almost everywhere since $f$ is second order differentiable almost everywhere (Here we assume $\alpha(t)\neq 0$ for $0<t<1$ without loss of generality. Otherwise, one can define $t_{m}=\sup\{0<t<1\mid\alpha(t)=0\}$ and consider the interval $[t_{m},1]$ instead). Then the following equality holds almost everywhere

Since $\psi$ is increasing, we have $\left\|\nabla f(y)\right\|\leq\left\|\nabla f(x)\right\|+a$. ∎

With Lemma A.4, we are ready to prove Proposition 3.2.

We prove the two directions in this proposition separately.

For each fixed $x\in\mathcal{X}$ where $\nabla^{2}f(x)$ exists and any unit-norm vector $w$, by Definition 2, we know that for any $t\leq r(\left\|\nabla f(x)\right\|)$,

On the other hand, by the definition of $t_{\text{b}}$, we know $z(t)\in\mathcal{X}$ for every $0\leq t<t_{\text{b}}$. Then by Lemma A.4, for all $0\leq t<t_{\text{b}}$, we have $\left\|\nabla f(z(t))\right\|\leq\left\|\nabla f(x)\right\|+a$. Therefore for all $0\leq t<t_{\text{b}}$,

which contradicts (13). Therefore we have shown $y\in\mathcal{X}$. Since $y$ is chosen arbitrarily with the ball $\mathcal{B}(x,r(\left\|\nabla f(x)\right\|))$, we have $\mathcal{B}(x,r(\left\|\nabla f(x)\right\|))\subseteq\mathcal{X}$. Then for any $x_{1},x_{2}\in\mathcal{B}(x,r(\left\|\nabla f(x)\right\|))$, we denote $w(t):=tx_{1}+(1-t)x_{2}$. Then we know $w(t)\in\mathcal{B}(x,r(\left\|\nabla f(x)\right\|))$ for all $0\leq t\leq 1$ and can obtain

where the last inequality is due to Lemma A.4. ∎

A.3 Proofs of lemmas implied by generalized smoothness

In this part, we provide the proofs of the useful properties stated in Section 3.1.2, including Lemma 3.3, Lemma 3.5, and Corollary 3.6.

Next, for the second inequality in (2), define $z(t):=(1-t)x_{2}+tx_{1}$ for $0\leq t\leq 1$. We know $z(t)\in\mathcal{B}(x,r(G))$. Note that we have shown

Then based on the definition of $G$, we have $\left\|\nabla f(x)\right\|\leq G$. ∎

Appendix B Analysis of GD for convex functions

In this section, we provide the detailed convergence analysis of gradient descent in the convex setting, including the proofs of Lemma 4.1 and Theorem 4.2, for which the following lemma will be helpful.

Define the Bregman divergences $\phi_{x}(w):=f(w)-\langle\nabla f(x),w\rangle$ and $\phi_{y}(w):=f(w)-\langle\nabla f(y),w\rangle$, which are both convex functions. Since $\nabla\phi_{x}(w)=\nabla f(w)-\nabla f(x)$, we have $\nabla\phi_{x}(x)=0$ which implies $\min_{w}\phi_{x}(w)=\phi_{x}(x)$ as $\phi_{x}$ is convex. Similarly we have $\min_{w}\phi_{y}(w)=\phi_{y}(y)$.

Note that for any $y\in\mathcal{B}(x,r(\left\|\nabla f(x)\right\|)/2)$ as in the lemma statement,

where the first inequality uses triangle inequality and $\nabla\phi_{x}(y)=\nabla f(y)-\nabla f(x)$; and the second inequality uses Definition 2. It implies that $y-\frac{1}{L}\nabla\phi_{x}(y)\in\mathcal{B}(x,r_{x})$. Then we can obtain

where the last inequality uses (15) where we choose $x_{1}=y-\frac{1}{L}\nabla\phi_{x}(y)$ and $x_{2}=y$. By the definition of $\phi_{x}$, the above inequality is equivalent to

Similar argument can be made for $\phi_{y}(\cdot)$ to obtain

Summing up the two inequalities, we can obtain the desired result. ∎

With Lemma B.1, we prove Lemma 4.1 as follows.

where we choose $\eta\leq r(G)/(2G)$. Thus by Lemma B.1, we have

where the first inequality uses Lemma B.1 and the last inequality chooses $\eta\leq 2/L$. ∎

With Lemma 4.1, we are ready to prove both Theorem 4.2 and Theorem 4.3.

Denote $G:=\left\|\nabla f(x_{0})\right\|$. Then we trivially have $\left\|\nabla f(x_{0})\right\|\leq G$. Lemma 4.1 states that if $\left\|\nabla f(x_{t})\right\|\leq G$ for any $t\geq 0$, then we also have $\left\|\nabla f(x_{t+1})\right\|\leq\left\|\nabla f(x_{t})\right\|\leq G$. By induction, we can show that $\left\|\nabla f(x_{t})\right\|\leq G$ for all $t\geq 0$. Then the rest of the proof basically follows the standard textbook analysis. We still provide the detailed proof below for completeness.

Note that $\left\|x_{t+1}-x_{t}\right\|=\eta\left\|\nabla f(x_{t})\right\|\leq\eta G\leq r(G)$, where we choose $\eta\leq r(G)/(2G)$. Thus we can apply Lemma 3.3 to obtain

where the last inequality chooses $\eta\leq 1/L$. Meanwhile, by convexity between $x_{t}$ and $x^{*}$, we have

Then reorganizing the terms of the above inequality, noting that

The above inequality implies $t(f(x_{t})-f^{*})+\frac{1}{2\eta}\left\|x_{t}-x^{*}\right\|^{2}$ is a non-increasing potential function, which directly implies the desired result. ∎

Since strongly convex functions are also convex, by the same argument as in the proof of Theorem 4.2, we have $\left\|\nabla f(x_{t})\right\|\leq G:=\left\|\nabla f(x_{0})\right\|$ for all $t\geq 0$. Moreover, (B) still holds. For $\mu$-strongly-convex function, we can obtain a tighter version of (17) as follows.

Let $A_{0}=0$ and $A_{t+1}=(1+A_{t})/(1-\eta\mu)$ for all $t\geq 0$. Combining (B) and (18), we have

Then reorganizing the terms of the above inequality, noting that

The above inequality means $A_{t}(f(x_{t})-f^{*})+\frac{1+\eta\mu A_{t}}{2\eta}\left\|x_{t}-x^{*}\right\|^{2}$ is a non-increasing potential function. Thus by telescoping we have

Appendix C Analysis of NAG for convex functions

Choose $\eta\leq\min\left\{\frac{1}{16L^{3-2/\alpha}},\frac{1}{2L}\right\}$. Then the iterates of Algorithm 1 satisfy

Before proving Theorem C.1, we first present several additional useful lemmas. To start with, we provide two lemmas regarding the weights $\{A_{t}\}_{t\geq 0}$ and $\{B_{t}\}_{t\geq 0}$ used in Algorithm 1. The lemma below states that $B_{t}=\Theta(t^{2})$.

The weights $\{B_{t}\}_{t\geq 0}$ in Algorithm 1 satisfy $\frac{1}{4}t^{2}\leq B_{t}\leq t^{2}$ for all $t\geq 0$.

We prove this lemma by induction. First note that the inequality obviously holds for $B_{0}=0$. Suppose its holds up to $t$. Then we have

Lemma C.2 implies the following useful lemma.

The weights $\{A_{t}\}_{t\geq 0}$ in Algorithm 1 satisfy that

First, note that it is easy to verify that $A_{s+1}-A_{s}-1=B_{s+1}-B_{s}-1\geq 0$, which implies each term in the LHS of the above inequality is non-negative. Then we have

The following lemma summarizes the results in the classical potential function analysis of NAG in [d’Aspremont et al., 2021]. In order to not deal with the generalized smoothness condition for now, we directly assume the inequality (20) holds in the lemma, which will be proved later under the generalized smoothness condition.

For any $t\geq 0$, if the following inequality holds,

These derivations below can be found in [d’Aspremont et al., 2021]. We present them here for completeness.

First, since $f$ is convex, the convexity between $x^{*}$ and $y_{t}$ gives

Similarly the convexity between $x_{t}$ and $y_{t}$ gives

Combining the above two inequalities as well as (20) assumed in this lemma, we have

Then we complete the proof noting that it is easy to verify

In the next lemma, we show that if $\left\|\nabla f(y_{t})\right\|\leq G$, then the condition (20) assumed in Lemma C.4 is satisfied at time $t$.

For any $t\geq 0$, if $\left\|\nabla f(y_{t})\right\|\leq G$, then we have $\left\|\nabla f(x_{t+1})\right\|\leq G$, and furthermore,

As disccued below Theorem C.1, the stepsize satisfies $\eta\leq 1/(2L)\leq\min\{\frac{2}{m(G)},\frac{r(G)}{2G}\}$. Therefore we can apply Lemma 4.1 to show $\left\|\nabla f(x_{t+1})\right\|\leq\left\|\nabla f(y_{t})\right\|\leq G$. For the second part, note that $\left\|x_{t+1}-y_{t}\right\|=\eta\left\|\nabla f(y_{t})\right\|\leq\frac{G}{2L}\leq r(G)$, we can apply Lemma 3.3 to show

With Lemma C.4 and Lemma C.5, we can show that $\left\|\nabla f(y_{t})\right\|\leq G$ for all $t\geq 0$, as in the lemma below.

For all $t\geq 0$, $\left\|\nabla f(y_{t})\right\|\leq G$.

We will prove this lemma by induction. First, by Lemma 3.5 and the choice of $G$, it is easy to verify that $\left\|\nabla f(x_{0})\right\|\leq G$. Then for any fixed $t\geq 0$, suppose that $\left\|\nabla f(x_{s})\right\|\leq G$ for all $s<t$. Then by Lemma C.4 and Lemma C.5, we know that $\left\|\nabla f(x_{s})\right\|\leq G$ for all $0\leq s\leq t$, and that for all $s<t$,

By telescoping (24), we have for all $0\leq s<t$,

For $0\leq s\leq t$, since $\left\|\nabla f(x_{s})\right\|\leq G$, then Lemma 3.5 implies

Since $\left\|\nabla f(y_{s})\right\|\leq G$ and $\left\|x_{s+1}-y_{s}\right\|=\left\|\eta\nabla f(y_{s})\right\|\leq r(G)$ for $s<t$, by Lemma 3.3, we have

Since $\left\|\nabla f(x_{t})\right\|\leq G$ and we just showed $\left\|x_{t}-y_{t}\right\|\leq r(G)$, by Lemma 3.3, we have

Then we complete the induction as well as the proof.

With the three lemmas above, it is straight forward to prove Theorem C.1.

Combining Lemmas C.4, C.5, and C.6, we know the following inequality holds for all $t\geq 0$.

Then by telescoping, we directly complete the proof.

Appendix D Analysis of NAG for strongly convex functions

In this section, we provide the convergence analysis of the modified version of Nesterov’s accelerated gradient method for $\mu$-strongly-convex functions defined in Algorithm 2.

The convergence results is formally presented in the following theorem.

The iterates generated by Algorithm 2 satisfy

In what follows, we will provide the proof of Theorem D.1. We will always use the parameter choices in the theorem throughout this section.

In this part, we provide several useful lemmas for proving Theorem D.1. To start with, the following two lemmas provide two useful inequalities.

For any $0\leq u\leq 1$, we have $\log(1+u)\geq\frac{1}{2}u$.

For all $0<p\leq 1$ and $t\geq 0$, we have

It is obvious that $f(t)\geq 0$ for $t\leq\frac{2}{\sqrt{p}}\log(e+\frac{1}{p})$. For $t>\frac{2}{\sqrt{p}}\log(e+\frac{1}{p})$, we have

In the next four lemmas, we provide several useful inequalities regarding the weights $\{A_{t}\}_{t\geq 0}$ and $\{B_{t}\}_{t\geq 0}$ used in Algorithm 2.

which implies $\tau_{t}\cdot\delta_{s}\leq 1.$

where in the inequality, we use the fact that $B_{s}$ is non-decreasing with $s$. Therefore

If $0<\eta\mu<1$, then for any $t\geq 1$, we have

For $t\geq 1$, we have $B_{t}\geq 1$ thus

Combined with Lemma D.5, we have the desired result. ∎

D.2 Proof of Theorem D.1

With all the useful lemmas in the previous section, we proceed to prove Theorem D.1, for which we need several additional lemmas. First, similar to Lemma C.4, the following lemma summarizes the results in the classical potential function analysis of NAG for strongly convex functions in [d’Aspremont et al., 2021].

For any $t\geq 0$, if the following inequality holds

These derivations can be found in d’Aspremont et al. . We present it here for completeness.

The strong convexity between $x^{*}$ and $y_{t}$ gives

The convexity between $x_{t}$ and $y_{t}$ gives

Combining the above two inequalities and the one assumed in this lemma, we have

Next, note that Lemma C.5 still holds in the strongly convex setting. We repeat it below for completeness.

For any $t\geq 0$, if $\left\|\nabla f(y_{t})\right\|\leq G$, then we have $\left\|\nabla f(x_{t+1})\right\|\leq G$, and furthermore,

With Lemma D.8 and Lemma D.9, we will show that $\left\|\nabla f(y_{t})\right\|\leq G$ for all $t\geq 0$ by induction in the following lemma.

For all $t\geq 0$, we have $\left\|\nabla f(y_{t})\right\|\leq G$.

We will prove this lemma by induction. First, by Lemma 3.5 and the choice of $G$, it is easy to verify that $\left\|\nabla f(x_{0})\right\|\leq G$. Then for any fixed $t\geq 0$, suppose that $\left\|\nabla f(x_{s})\right\|\leq G$ for all $s<t$. Then by Lemma D.8 and Lemma D.9, we know that $\left\|\nabla f(x_{s})\right\|\leq G$ for all $0\leq s\leq t$, and that for all $s<t$,

By telescoping (30), we have for all $0\leq s<t$,

For $0\leq s\leq t$, since $\left\|\nabla f(x_{s})\right\|\leq G$, then Lemma 3.5 implies

where the second inequality follows from Lemma D.4. We further control term $\mathcal{I}$ by

Since $\left\|\nabla f(x_{t})\right\|\leq G$ and we just showed $\left\|x_{t}-y_{t}\right\|\leq r(G)$, by Lemma 3.3, we have

Then we complete the induction as well as the proof. ∎

Combining Lemmas D.8, D.9, and D.10, we know the following inequality holds for all $t\geq 0$.

Finally, applying Lemma D.5, we have $A_{t}=B_{t}+1/(\eta\mu)\geq 1/(1-\sqrt{\eta\mu})^{t-1}+1/(\eta\mu)$. Thus completes the proof. ∎

Appendix E Analysis of GD for non-convex functions

In this section, we provide the proofs related to analysis of gradient descent for non-convex function, including those of Lemma 5.1 and Theorem 5.2.

First, based on Corollary 3.6, we know $\left\|\nabla f(x)\right\|\leq G<\infty$. Also note that

Then by Lemma 3.3 and Remark 3.4, we have $x^{+}\in\mathcal{X}$ and

By Lemma 5.1, using induction, we directly obtain $f(x_{t})\leq f(x_{0})$ for all $t\geq 0$. Then by Corollary 3.6, we have $\left\|\nabla f(x_{t})\right\|\leq G$ for all $t\geq 0$. Following the proof of Lemma 5.1, we can similarly show

Taking a summation over $t<T$ and rearanging terms, we have

Appendix F Analysis of SGD for non-convex functions

We first present some useful inequalities related to the parameter choices in Theorem 5.3.

Under the parameters choices in Theorem 5.3, the following inequalities hold.

First note that by Corollary 3.6, we know

i.e., $\sigma L\leq G^{2}\delta/16$. Then since we choose $\eta\leq\frac{1}{4G\sqrt{T}}$, we have

Under the parameters choices in Theorem 5.3, the following inequality holds

If $t<\tau$, by the definition of $\tau$, we know $f(x_{t})-f^{*}\leq F$ and $\left\|\epsilon_{t}\right\|\leq\frac{G}{5\eta L}$, and the former also implies $\left\|\nabla f(x_{t})\right\|\leq G$ by Corollary 3.6. Then we can bound

where we use the choice of $\eta\leq\frac{1}{2L}$. Then based on Lemma 3.3 and Remark 3.4, for any $t<\tau$, we have

where the equality is due to (4); the second inequality uses $g_{t}=\epsilon_{t}+\nabla f(x_{t})$ and Young’s inequality $\left\|y+z\right\|^{2}\leq 2\left\|y\right\|^{2}+2\left\|z\right\|^{2}$ for any vectors $y,z$; and the last inequality chooses $\eta\leq 1/(2L)$. Taking a summation over $t<\tau$ and rearanging terms, we have

Now we bound the last two terms on th RHS. First, for the last term, we have

where the first inequality uses $\tau\leq T$ by its defnition; and in the last inequality we use Assumption 4.

where the last inequality is due to Lemma F.1. ∎

With Lemma F.2, we are ready to prove Theorem 5.3.

We want to show the probability of $\{\tau<T\}$ is small, as its complement $\{\tau=T\}$ means $f(x_{t})-f^{*}\leq F$ for all $t\leq T$ which implies $\left\|\nabla f(x_{t})\right\|\leq G$ for all $t\leq T$. Note that

Therefore we only need to bound the probability of each of these two events on the RHS.

where we choose $\eta\leq\frac{1}{2L}$. Then based on Lemma 3.3 and Remark 3.4, we have

where the first inequality is obtained following the same derivation as in (F); the last equality is due to Corollary 3.6. Therefore we can show that under the event $\{\tau_{1}<T,\tau_{2}=T\}$,

where the second inequality uses Markov’s inequality; the third inequality uses Lemma F.2; and in the last inequality we choose $F=8(f(x_{0})-f^{*}+\sigma)/\delta$.

Appendix G Lower bound

In this section, we provide the proof of Theorem 5.4.

Let $c,\eta_{0}>0$ satisfy $\eta_{0}\leq c^{2}/2$. Consider

where $c>0$ is a constant and $y=(c+\sqrt{c^{2}+2\eta_{0}})/2>0$ is the fixed point of the iteration

and $k$, $b$ are chosen in such a way that $f(x)$ and $f^{\prime}(x)$ are continuous. Specifically, choose $k=c^{-1}f^{\prime}(c/2)$ and $b=f(c/2)-cf^{\prime}(c/2)/4$. Since $f(-x)=f(x)$, $f(x)$ is symmetric about the line $x=0$. In a small neighborhood, $f(x)$ is symmetric about $(y,f(y))$, so $f^{\prime}(x)$ is continuous at $y$.

Let us first consider the smoothness of $f$. By symmetry, it suffices to consider $x>0$. Then,

Note that $f(x)$ has a stationary point . For stepsize $\eta_{f}$ satisfying $\eta_{0}\leq\eta_{f}\leq c^{2}/4$, there exists $z=(c+\sqrt{c^{2}+2\eta_{f}})\geq y$ such that $-z=z-\eta_{f}(y-c)^{-1}$ and by symmetry, once $x_{\tau}=z$, $x_{t}=\pm z$ for all $t\geq\tau$, making the GD iterations stuck. Now we choose a proper $x_{0}$ such that $f^{\prime}(x_{0})$ and $f(x_{0})-f(0)$ are bounded.

We consider arriving at $y$ from above. That is, $x_{0}\geq x_{1}\geq\ldots x_{\tau}=z>c>0$. Since in each update where $x_{t+1}=x_{t}-\eta_{f}(x_{t}-c)^{-1}>c$,

Hence, we can choose $\tau$ in such a way that $3c/2\leq x_{0}<3c/2+\sqrt{\eta_{f}}$. Then,

By definition, $y-c=\eta_{0}(c+\sqrt{c^{2}+2\eta_{0}})^{-1}$. Hence,

For stepsize $\eta_{f}<\eta_{0}$, reaching below $4c/3$ takes at least

steps to reach $4c/3$, where $f^{\prime}(4c/3)=\log(c/3)$.

Now we set $c$ and $\eta_{0}$ and scale function $f(x)$ to satisfy the parameter specifications $L_{0},L_{2},G_{0},\Delta_{0}$. Define $g(x)=L_{2}^{-1}f(x)$. Then, $g(x)$ is $(2,2kL_{2}^{-1},L_{2})$-smooth. Since the gradient of $g(x)$ is $L_{2}^{-1}$ times $f(x)$, the above analysis for $f(x)$ applies to $g(x)$ by replacing $\eta_{0}$ with $\eta_{1}=L_{2}\eta_{0}$ and $\eta_{f}$ with $\eta=L_{2}\eta_{f}$. To ensure that

it suffices to take $c\geq 2/\sqrt{L_{0}L_{2}}$. To ensure that

it suffices to take $c\geq 2/(L_{2}G_{0})$. To ensure that

Since we require $\eta_{1}\leq c^{2}/2$, parameters $L_{2}$ and $\Delta_{0}$ need to satisfy

that is, $L_{2}\Delta_{0}\geq 5.5\log 2+0.5$, which holds because $L_{2}\Delta_{0}\geq 10$. Take $c=\max\{2/\sqrt{L_{0}L_{2}},2/(L_{2}G_{0}),\sqrt{8/L_{0}}\}$. Then, as long as $\eta\leq 2/L_{0}$, the requirement that $\eta\leq c^{2}/4$ is satisfied. Therefore, on $g(x)$ with initial point $x_{0}$, gradient descent with a constant stepsize either gets stuck, or takes at least

On the other hand, if $\eta>2/L_{0}$, consider the function $f(x)=\frac{L_{0}}{2}x^{2}$. For any $x_{t}\neq 0$, we always have $\left|x_{t+1}\right|/\left|x_{t}\right|=\left|1-\eta L_{0}\right|>1$, which means the iterates diverge to infinity. ∎