Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity

## Abstract

Abstract In this paper, we provide tight lower bounds for the oracle complexity of minimizing high-order Hölder smooth and uniformly convex functions. Specifically, for a function whose p t ⁢ h superscript 𝑝 𝑡 ℎ p^{th} italic_p start_POSTSUPERSCRIPT italic_t italic_h end_POSTSUPERSCRIPT -order derivatives are Hölder continuous with degree ν 𝜈 \nu italic_ν and parameter H 𝐻 H italic_H , and that is uniformly convex with degree q 𝑞 q italic_q and parameter σ 𝜎 \sigma italic_σ , we focus on two asymmetric cases: (1) q > p + ν 𝑞 𝑝 𝜈 q>p+\nu italic_q > italic_p + italic_ν , and (2) q < p + ν 𝑞 𝑝 𝜈 q<p+\nu italic_q < italic_p + italic_ν . Given up to p t ⁢ h superscript 𝑝 𝑡 ℎ p^{th} italic_p start_POSTSUPERSCRIPT italic_t italic_h end_POSTSUPERSCRIPT -order oracle access, we establish worst-case oracle complexities of Ω ⁢ ( ( H σ ) 2 3 ⁢ ( p + ν ) − 2 ⁢ ( σ ϵ ) 2 ⁢ ( q − p − ν ) q ⁢ ( 3 ⁢ ( p + ν ) − 2 ) ) Ω superscript 𝐻 𝜎 2 3 𝑝 𝜈 2 superscript 𝜎 italic-ϵ 2 𝑞 𝑝 𝜈 𝑞 3 𝑝 𝜈 2 \Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}\left(\frac{%
\sigma}{\epsilon}\right)^{\frac{2(q-p-\nu)}{q(3(p+\nu)-2)}}\right) roman_Ω ( ( divide start_ARG italic_H end_ARG start_ARG italic_σ end_ARG ) start_POSTSUPERSCRIPT divide start_ARG 2 end_ARG start_ARG 3 ( italic_p + italic_ν ) - 2 end_ARG end_POSTSUPERSCRIPT ( divide start_ARG italic_σ end_ARG start_ARG italic_ϵ end_ARG ) start_POSTSUPERSCRIPT divide start_ARG 2 ( italic_q - italic_p - italic_ν ) end_ARG start_ARG italic_q ( 3 ( italic_p + italic_ν ) - 2 ) end_ARG end_POSTSUPERSCRIPT ) in the first case with an ℓ ∞ subscript ℓ \ell_{\infty} roman_ℓ start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT -ball-truncated-Gaussian smoothed hard function and Ω ⁢ ( ( H σ ) 2 3 ⁢ ( p + ν ) − 2 + log ⁡ log ⁡ ( ( σ p + ν H q ) 1 p + ν − q ⁢ 1 ϵ ) ) Ω superscript 𝐻 𝜎 2 3 𝑝 𝜈 2 superscript superscript 𝜎 𝑝 𝜈 superscript 𝐻 𝑞 1 𝑝 𝜈 𝑞 1 italic-ϵ \Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}+\log\log\left%
(\left(\frac{\sigma^{p+\nu}}{H^{q}}\right)^{\frac{1}{p+\nu-q}}\frac{1}{%
\epsilon}\right)\right) roman_Ω ( ( divide start_ARG italic_H end_ARG start_ARG italic_σ end_ARG ) start_POSTSUPERSCRIPT divide start_ARG 2 end_ARG start_ARG 3 ( italic_p + italic_ν ) - 2 end_ARG end_POSTSUPERSCRIPT + roman_log roman_log ( ( divide start_ARG italic_σ start_POSTSUPERSCRIPT italic_p + italic_ν end_POSTSUPERSCRIPT end_ARG start_ARG italic_H start_POSTSUPERSCRIPT italic_q end_POSTSUPERSCRIPT end_ARG ) start_POSTSUPERSCRIPT divide start_ARG 1 end_ARG start_ARG italic_p + italic_ν - italic_q end_ARG end_POSTSUPERSCRIPT divide start_ARG 1 end_ARG start_ARG italic_ϵ end_ARG ) ) in the second case, for reaching an ϵ italic-ϵ \epsilon italic_ϵ -approximate solution in terms of the optimality gap. Our analysis generalizes previous lower bounds for functions under first- and second-order smoothness as well as those for uniformly convex functions, and furthermore our results match the corresponding upper bounds in this general setting.

## 1 Introduction

With the advancement in computational power, high-order optimization methods ($p^{th}$-order with $p\geq 2$) are gaining more attention for their merit of faster convergence and higher precision. Consequently, uniformly convex problems (with degree $q$) have become a recent focus, particularly the subproblems of some high-order optimization methods. The subproblem of the cubic-regularized Newton ($p=2,q=3$) (Nesterov and Polyak, ) is an example, as are methods of even higher orders ($p\geq 3$, $q\geq 4$) (Zhu and Cartis, ).

Although these problems are high-order smooth by definition, a lower-order algorithm may be employed to obtain an approximate solution. For instance, solving the subproblem of cubic-regularized (i.e., $q=3$) Newton with gradient descent (accessing first-order oracle, i.e., $p=1$), or, more generally, approximately solving the subproblem of $(q-1)^{th}$-order Taylor descent (Bubeck et al., ) (which typically contains a regularization term to the power of $q$) with lower-order oracle access, introduces an asymmetry between the algorithm’s oracle access order and the degree of uniform convexity ($q>p+1$).

Conversely, a lower-degree regularization can be paired with a higher-order smooth function. This enables methods that access higher-order oracles, which leads to the opposite asymmetry ($q<p+1$). Examples include the objective function of logistic regression, which is known to be infinite-order smooth. Coupled with standard $\ell_{2}$-regularization, the problem can be analyzed as a $p^{th}$-order smooth and strongly convex ($q=2$) problem, e.g., $p=2$ with access to the Hessian matrix, $p=3$ accessing the third-order derivative tensor.

In addressing specific instances of this asymmetry, previous works established some upper bounds (Gasnikov et al., ; Song et al., ) and lower bounds (Arjevani et al., ; Kornowski and Shamir, ; Doikov, ; Thomsen and Doikov, ) for the oracle complexity. Notably, Song et al. () proposed a unified acceleration framework for functions that are $p^{th}$-order Hölder smooth with degree $\nu$, and uniformly convex with degree $q$, providing upper bounds for any combination of $p$, $q$, and $\nu$. For the case where $q>p+\nu$, they show an oracle complexity of $\mathcal{O}\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}\left(
\frac{\sigma}{\epsilon}\right)^{\frac{2(q-p-\nu)}{q(3(p+\nu)-2)}}\right)$, and for the case where $q<p+\nu$, the complexity is $\mathcal{O}\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}+\log\log
\left(\left(\frac{\sigma^{p+\nu}}{H^{q}}\right)^{\frac{1}{p+\nu-q}}\frac{1}{
\epsilon}\right)\right)$. To the best of our knowledge, no lower bounds exist in this general setting, particularly with Hölder smoothness and uniform convexity.

In this paper, we provide matching lower bounds to the upper bounds in (Song et al., ) for these asymmetric cases. Specifically, we establish $\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}\left(\frac{
\sigma}{\epsilon}\right)^{\frac{2(q-p-\nu)}{q(3(p+\nu)-2)}}\right)$ for $q>p+\nu$ and
$\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}+\log\log\left
(\left(\frac{\sigma^{p+\nu}}{H^{q}}\right)^{\frac{1}{p+\nu-q}}\frac{1}{
\epsilon}\right)\right)$ for $q<p+\nu$. For the $q>p+\nu$ case, we adopt the framework proposed by (Guzmán and Nemirovski, ), utilizing a smoothing operator to generate a high-order smooth function. We propose the use of $\ell_{\infty}$-ball-truncated Gaussian smoothing, which, as we later justify, is novelly designed to achieve the optimal rate and be compatible with both high-order smooth and uniformly convex settings. Both the truncated Gaussian smoothing and the construction of the $\ell_{\infty}$ ball are crucial to improve upon the sub-optimal derivation using uniform smoothing within an $\ell_{2}$ ball in (Agarwal and Hazan, ). Our results generalize the lower bounds in (Doikov, ; Thomsen and Doikov, ) to higher-order and Hölder smooth settings. For the $q<p+\nu$ case, we adopt Nesterov’s framework (Nesterov et al., ) and generalize the lower bounds in (Arjevani et al., ; Kornowski and Shamir, ) to include Hölder smooth and uniformly convex settings.

## 2 Related Work

##### Upper Bounds.

Doikov and Nesterov () showcase the upper bound for uniformly convex functions with Hölder-continuous Hessian via cubic regularized Newton method, but the rate is not optimal. For higher order result, Bubeck et al. () and Jiang et al. () established a near optimal upper bound of $\tilde{\mathcal{O}}\left(\epsilon^{-\frac{2}{3p+1}}\right)$ in the simpler case of $\nu=1$ without uniform convexity.
Gasnikov et al. () achieve the same near-optimal rate, but also consider uniform convexity, and by the restarting mechanism, derive the rate that for $q>p+1$ as well, generalizing the upper bounds established in second-order (Monteiro and Svaiter, ) and matching the lower bounds later derived in (Kornowski and Shamir, ). Kovalev and Gasnikov () closed the $\log\left(\frac{1}{\epsilon}\right)$ gap, but does not consider uniform convexity or Hölder smoothness. For minimizing uniformly convex functions, Juditsky and Nesterov () studies the complexity of first-order methods in the non-Euclidean setting. Recently, Song et al. () establish the most general upper bounds for arbitrary combinations of the order of Hölder smoothness and the degree of uniform convexity, which include the rates for both $q>p+\nu$ and $q<p+\nu$ cases.

##### Lower Bounds.

Agarwal and Hazan () proved for $p^{th}$-order smooth convex functions an $\Omega\left(\epsilon^{-\frac{2}{5p+1}}\right)$ lower bound based on constructing the hard function with randomized smoothing uniformly over a unit ball.
But their rate is not optimal due to the extra dimension factor appearing in the smoothness constant due to the uniform randomized smoothing. Garg et al. () added softmax smoothing prior to randomized smoothing, achieving a near-optimal rate of $\Omega\left(\epsilon^{-\frac{2}{3p+1}}\right)$ for randomized and quantum algorithms. Separately, Arjevani et al. () also established the optimal lower bound of $\Omega\left(\epsilon^{-\frac{2}{3p+1}}\right)$ with the Nesterov’s hard function construction approach. Furthermore, for the asymmetric case of $q<p+1$, Arjevani et al. () proved the lower bound of $\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{7}}+\log\log\left(\frac{
\sigma^{3}}{H^{2}}\epsilon^{-1}\right)\right)$ for the $p=2$ and $q=2$ case, and the result is later generalized to the $p^{th}$ order in (Kornowski and Shamir, ). No $q>2$ uniformly convex settings were considered in these works. For the case of $q>p+\nu$, lower bounds for uniformly convex functions for $q\geq 3$ are limited to the first-order smoothness setting where $p=1$ (Juditsky and Nesterov, ; Doikov, ; Thomsen and Doikov, ). No lower bounds for uniformly convex functions were established, to our knowledge, in the high-order setting.

## 3 Preliminaries and Settings

##### Notations.

We use $[n]$ to represent the set $\{1,2,...,n\}$. We use $\|\cdot\|$ to denote an $\ell_{2}$ norm by default. We use $\nabla$ for gradients, $\partial$ for subgradients, and $\langle\cdot,\cdot\rangle$ for inner products. Related to the algorithm, bold lower letters for vectors (e.g., $\mathbf{x}$, $\mathbf{y}$), and with subscript, the vectors in different iterations (e.g., $\mathbf{x}_{T}$). We use regular lower letters for scalars, and with subscript, a coordinate of a vector (e.g., $x_{i}$). Depending on the context, we use capital letters for a matrix or a random variable. We use $\phi$ for the probability density function of the standard normal or the standard multivariate normal (MVN), and $\Phi$ for the cumulative (density) function of standard normal or MVN. We further overuse the notation of $\phi_{[\cdot,\cdot]}$ $\Phi_{[\cdot,\cdot]}$ for their truncated counterparts for the normal distribution (standard normal if not specified with parameters), and $\phi_{\|\cdot\|_{\infty}\leq\cdot}$ $\Phi_{\|\cdot\|_{\infty}\leq\cdot}$ for the MVN truncated within an $\ell_{\infty}$ ball.

### 3.1 Definitions

###### Definition 1 (High-order Smoothness) .

For $p\in\mathbb{Z}^{+}$, a function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is $p^{th}$-order smooth or whose $p^{th}$- derivatives are $L_{p}$-Lipschitz if for $L_{p}>0$, $\forall\ \mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$, $\|\nabla^{p}f(\mathbf{x})-\nabla^{p}f(\mathbf{y})\|\leq L_{p}\|\mathbf{x}-
\mathbf{y}\|$.

###### Definition 2 (High-order Hölder Smoothness) .

For $p\in\mathbb{Z}^{+}$, a function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is $p^{th}$-order Hölder smooth or has Hölder continuous $p^{th}$-order derivatives if for $\nu\in(0,1]$ and $H>0$, $\forall\ \mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$, $\|\nabla^{p}f(\mathbf{x})-\nabla^{p}f(\mathbf{y})\|\leq H\|\mathbf{x}-\mathbf{
y}\|^{\nu}$.

###### Definition 3 .

(Uniform Convexity (Nesterov et al., , Section 4.2.2)) For integer $q\geq 2$ and $\sigma>0$, a function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is uniformly convex with degree $q$ and modulus $\sigma$ if $\ \forall\ \mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$, $f(\mathbf{y})-f(\mathbf{x})-\left\langle\nabla f(\mathbf{x}),\,\mathbf{y}-
\mathbf{x}\right\rangle\geq\frac{\sigma}{q}\|\mathbf{y}-\mathbf{x}\|^{q}$,
or the function satisfies $\left\langle\nabla f(\mathbf{y})-\nabla f(\mathbf{x}),\,\mathbf{y}-\mathbf{x}
\right\rangle\geq\sigma\|\mathbf{y}-\mathbf{x}\|^{q}$.

###### Definition 1 (High-order Smoothness) .

###### Definition 2 (High-order Hölder Smoothness) .

###### Definition 3 .

## 4 Lower Bound for the q > p + ν 𝑞 𝑝 𝜈 q>p+\nu italic_q > italic_p + italic_ν Case

The derivation of the lower bound is to find such a function by construction that satisfies the uniformly convex and Hölder smooth conditions and requires at least a certain amount of iterations to reach an $\epsilon$-approximate solution. The general steps follow from the framework of showing lower complexity bounds for smooth convex optimization (Guzmán and Nemirovski, ), which originates from (Nemirovskii and Nesterov, ) and serves as the basis for results in various follow-up settings (Agarwal and Hazan, ; Garg et al., ; Doikov, ). The construction starts from a non-smooth function, then smooths the function with some smoothing operator (e.g. Moreau envelope in (Guzmán and Nemirovski, ; Doikov, ), randomized smoothing uniformly within a ball in (Agarwal and Hazan, ; Garg et al., )). We design a truncated Gaussian smoothing operator within the $\ell_{\infty}$ ball and start the derivation by stating its formal definition and key properties.

### 4.1 Truncated Gaussian Smoothing

###### Definition 4 (Truncated Gaussian Smoothing) .

For $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ and a parameter $\rho>0$, define the truncated Gaussian smoothing operator $S_{\rho}[f]:(\mathbb{R}^{d}\rightarrow\mathbb{R})\rightarrow(\mathbb{R}^{d}
\rightarrow\mathbb{R})$ as

$$ $\displaystyle S_{\rho}[f](\mathbf{x})=\mathbb{E}_{V}[f(\mathbf{x}+\rho V)]$ $$

where $V$ is a $d$-dimensional random variable that follows the standard multivariate normal (MVN) distribution truncated within a unit ball. That is, the probability density function (PDF) of $V$ is

$$ $\displaystyle\mathbb{P}[V=\mathbf{v}]=\frac{1}{Z(d)(2\pi)^{\frac{d}{2}}}\exp \left\{-\frac{\mathbf{v}^{\top}\mathbf{v}}{2}\right\}\mathbb{I}_{[\|\mathbf{v} \|_{\infty}\leq 1]},$ $$

in which $\mathbb{I}_{[\cdot]}=1$ if $\cdot$ is true 0 0 otherwise is the indicator function and $Z(d)$ is the normalizing factor, i.e., the cumulative distribution within the $d$-dimensional unit $\ell_{\infty}$-ball (Cartinhour, ).

We denote $f_{\rho}=S_{\rho}[f]$, and use the shorthand notation for the function that applied the smoothing operator for $p$ times:
$f_{\rho}^{p}=S^{p}_{\rho}[f]=S_{\rho}[\cdots[S_{\rho}[f]]\cdots]$ for $p$ times.

Now we justify the choice of truncated Gaussian smoothing for the construction of hard function. We notice that Agarwal and Hazan () choose randomized smoothing uniformly over a unit $\ell_{2}$-ball, which by their Lemma 2.3 that the smoothed function is $\mathcal{O}(d)$-smooth (which in fact can be tightened to $\mathcal{O}(\sqrt{d})$ by (Yousefian et al., ; Duchi et al., , Lemma 8)) where $d$ is the dimension of the variable. Since the number of iteration $T\in\mathcal{O}(d)$, their result $\mathcal{O}\big{(}T^{-\frac{2}{5p+1}}\big{)}$ is sub-optimal by an extra $T$ comparing to the tight lower bound $\mathcal{O}\big{(}T^{-\frac{2}{3p+1}}\big{)}$ (Arjevani et al., ). Therefore we search for a smoothing operator with Lipschitz constant being *dimension-free*. We notice that Gaussian smoothing (Duchi et al., , Lemma 9), softmax smoothing (Bullins, , Lemma 7), and Moreau smoothing (Doikov, , Lemma 1) are such operators.

Yet as the reader will later see in the proof that the converging points are generated through a sequence of functions, instead of those generated from one hard function. For these two sequences of points to be identical so that the lower bound is indeed for optimizing the hard function constructed, we need the smoothing operator to be *local*, that is, accessing information within *some neighborhood* of the queried point, e.g., a unit $\ell_{2}$-ball in (Doikov, ). Unfortunately, Gaussian smoothing and softmax smoothing need access to global information.

For Moreau smoothing that indeed depends on local information, it’s successfully applied in proving the lower bound in the first-order setting (Doikov, ), but is not suited for the high-order setting. First, one may attempt the extension of Moreau smoothing with a $p^{th}$-power regularization, yet it can be shown that the function is not $p^{th}$-order smooth.
Next, one may try to apply Moreau smoothing $p$ times, yet unlike randomized smoothing in (Agarwal and Hazan, ), the Lipschitz constant does not raise to the $p^{th}$-power with the number of times the smoothing operator is applied, which leads to the same rate as in the first order. Observing the proof of (Agarwal and Hazan, , Corollary 2.4), this is in essence due to the fact that the minimization in Moreau smoothing does not commute with derivative, whereas the expectation in randomized smoothing does.

We then come up with the idea of a truncated multivariate Gaussian smoothing operator that is (i) local (ii) smooth with a dimension-free constant (iii) $p^{th}$-order smooth with smoothness constant raising to the $p^{th}$ power as well. Initially, we applied the Gaussian smoothing truncated within a unit ball in $\ell_{2}$ by default. We noticed later, however, that the marginal distribution of unit-$\ell_{2}$-ball truncated multivariate Gaussian is not the truncated standard normal between $[-1,1]$, but with an extra $d$-dependent normalizing constant, which adds the $d$-dependency to the smoothness constant of the hard function.

To ensure a dimension-free smoothness constant, we instead apply the multivariate Gaussian smoothing truncated within an $\ell_{\infty}$ ball, a.k.a., the hypercube with edge length $2$, whose marginal distribution is indeed the truncated standard normal between $[-1,1]$ (Cartinhour, ). The following lemma characterizes these desired properties including convexity, continuity, approximation, and smoothness, with proof deferred to Appendix A.1.

###### Lemma 1 .

Given a L-Lipschitz function $f$, the function $f_{\rho}^{p}=S_{\rho}[\cdots[S_{\rho}[f]]\cdots]$ satisfies

- (i)
If $f$ is convex, $f^{p}_{\rho}$ is convex and $L$-Lipschitz with respect to the $\ell_{2}$ norm.
- (ii)
If $f$ is convex, $f(\mathbf{x})\leq f_{\rho}^{p}(\mathbf{x})\leq f(\mathbf{x})+\frac{5p}{4}L\rho
\sqrt{d}$.
- (iii)
$\forall i\in[p]$, $\forall\mathbf{x},\mathbf{x}^{\prime}\in\mathbb{R}^{d}$, $\|\nabla^{i}f_{\rho}^{p}(\mathbf{x})-\nabla^{i}f_{\rho}^{p}(\mathbf{x}^{\prime
})\|\leq\left(\frac{2}{\rho}\right)^{i}L\|\mathbf{x}-\mathbf{x}^{\prime}\|$.

###### Definition 4 (Truncated Gaussian Smoothing) .

###### Lemma 1 .

### 4.2 The Lower Bound: Function Construction and Trajectory Generation

###### Theorem 1 .

For any $T$-step $(\sqrt{d}-1\leq T\leq d)$ algorithm $\mathcal{A}$ with oracle access up to the $p^{th}$ order, there exists a convex function $f(\mathbf{x})$ whose $p^{th}$-order derivative is Hölder continuous of degree $\nu$ with modulus $H$ and a corresponding $F(\mathbf{x})=f(\mathbf{x})+\frac{\sigma}{q}\|\mathbf{x}\|^{q}$ with regularization that is uniformly convex of degree $q$ with modulus $\sigma$, such that $q>p+\nu$, it takes

$$ $\displaystyle T\in\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu) -2}}\left(\frac{\sigma}{\epsilon}\right)^{\frac{2(q-p-\nu)}{q(3(p+\nu)-2)}}\right)$ $$

steps to reach an $\epsilon$-approximate solution $\mathbf{x}_{T}$ satisfying $F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})\leq\epsilon$.

###### Proof.

We begin the proof by constructing the hard function.

###### Theorem 1 .

###### Proof.

#### 4.2.1 Function Construction with Truncated Gaussian Smoothing

*1. Non-smooth Function Construction. * We first construct the function

$$ $\displaystyle g_{t}(\mathbf{x})=\max_{1\leq k\leq t}r_{k}(\mathbf{x})$ $\displaystyle where$ $\displaystyle\forall\ k\in[T],r_{k}(\mathbf{x})=\xi_{k}\left\langle\mathbf{e}_ {\alpha(k)},\,\mathbf{x}\right\rangle-(k-1)\delta.$ $$

$\xi_{k}\in\{-1,1\}$, $\mathbf{e}$ is the standard basis, $\alpha$ is a permutation of $[T]$, and $\delta>0$ is some parameter that we will choose later. Lemma 2 characterizes the properties of $g_{t}$ with proof in Appendix A.2.

###### Lemma 2 .

$\forall\ t\in[T]$, $g_{t}$ is convex and $1$-Lipschitz with respect to the $\ell_{\infty}$-norm, and also the $\ell_{2}$-norm.

*2. Truncate Gaussian Smoothing. * Next, we smooth the function $g_{t}(\mathbf{x})$ with truncate Gaussian smoothing as in Definition 4. Given a parameter $\rho>0$ and $p\in\mathbb{Z}^{+}$,

$$ $\displaystyle G_{t}(\mathbf{x})=S^{p}_{\rho}[g_{t}](\mathbf{x})$ $$

Based on Lemma 14, we show that $G_{t}(\mathbf{x})$ satisfies the following lemma, with proof in Appendix A.2.

###### Lemma 3 .

$\forall\ t\in[T]$, $\forall\ \mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$,

- (i)
$G_{t}(\mathbf{x})$ is convex and 1-Lipschitz, i.e., $G_{t}(\mathbf{x})-G_{t}(\mathbf{y})\leq\|\mathbf{x}-\mathbf{y}\|$.
- (ii)
$g_{t}(\mathbf{x})\leq G_{t}(\mathbf{x})\leq g_{t}(\mathbf{x})+\frac{5}{4}p\rho
\sqrt{d}$.
- (iii)
For some fixed $p\in\mathbb{Z}^{+}$, $\forall\ i\in[p]$, $\|\nabla^{i}G_{t}(\mathbf{x})-\nabla^{i}G_{t}(\mathbf{y})\|\leq\left(\frac{2}{
\rho}\right)^{i}\|\mathbf{x}-\mathbf{y}\|$.

*3. Adding Uniform Convexity. * Now that the constructed function $G_{t}(\mathbf{x})$ is all-order smooth, we add to it the uniformly convex regularization. We define

$$ $\displaystyle f_{t}(\mathbf{x})=\beta G_{t}(\mathbf{x})$ $\displaystyle f(\mathbf{x})=f_{T}(\mathbf{x})$ $\displaystyle F_{t}(\mathbf{x})=f_{t}(\mathbf{x})+d_{q}(\mathbf{x})\quad\text{ for}\quad d_{q}(\mathbf{x})=\frac{\sigma}{q}\big{\|}\mathbf{x}\big{\|}^{q}, \quad\mathbf{x}\in\mathcal{Q}$ $\displaystyle F(\mathbf{x})=F_{T}(\mathbf{x}),$ $$

where $\beta>0$ is a parameter that we will choose later, $\mathcal{Q}=\{\mathbf{x}:\|\mathbf{x}\|_{2}\leq D\}$(^1^11We would note that for the $q>p+\nu$ case, $F$ is guaranteed to be $p^{th}$-order smooth only in the bounded domain as constructed, since the regularization term $d_{q}(\mathbf{x})$ may not be $p^{th}$-order smooth on $\mathbb{R}^{d}$. The construction is inspired by that in (Juditsky and Nesterov, ). This is not explicitly discussed in (Song et al., ; Doikov, ; Thomsen and Doikov, ).) for $D\leq\left(\frac{H}{2^{1-\nu}C}\right)^{\frac{1}{q-p-\nu}}$ and $C=\sigma(q-1)\times\cdots\times(q-p)$.

###### Lemma 4 .

For $F(\mathbf{x})=f_{T}(\mathbf{x})+d_{q}(\mathbf{x})$ where $d_{q}(\mathbf{x})=\frac{\sigma}{q}\big{\|}\mathbf{x}\big{\|}^{q}$ and $\mathbf{x}\in\mathcal{Q}$,

- (i)
$F$ is uniformly convex function with degree $q$ and modulus $\sigma>0$.
- (ii)
$F(\mathbf{x})$ is $p^{th}$-order Hölder smooth with parameter $H=\frac{2^{p+1}\beta}{{\rho}^{p+\nu-1}}$, $\forall\ p\in\mathbb{Z}^{+}$.

Therefore, by Lemma 4, the function constructed satisfies the desired uniform convexity and high-order smoothness conditions.

###### Lemma 5 .

For $R(\mathbf{x})=\beta\max_{k\in[T]}\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\,
\mathbf{x}\right\rangle+\frac{\sigma}{q}\|\mathbf{x}\|^{q}$, we have

$$ $\displaystyle R(\mathbf{x})-\beta(T-1)\delta\leq F(\mathbf{x})\leq R(\mathbf{x })+\frac{5}{4}p\beta\rho\sqrt{d}.$ $$

###### Lemma 2 .

###### Lemma 3 .

###### Lemma 4 .

###### Lemma 5 .

#### 4.2.2 Convergence Trajectory Generation

*4. Trajectory Generation Procedure. * The trajectory is generated following a standard $T$-step iterative procedure same as outlined in (Guzmán and Nemirovski, ; Doikov, ):

- $\cdot$
For $t=1$, $\mathbf{x}_{1}$ is the first point of the trajectory and is chosen by initialization of some algorithm $\mathcal{A}$, independent of $F$. Subsequently, choose
$\displaystyle\alpha(1)\in\operatorname*{arg\,max}_{k\in[T]}\left|\left\langle
\mathbf{e}_{\alpha(k)},\,\mathbf{x}_{1}\right\rangle\right|$
$\displaystyle\xi_{1}=\mathrm{sign}\left(\left\langle\mathbf{e}_{\alpha(1)},\,
\mathbf{x}_{1}\right\rangle\right),$
after which a fixed $F_{1}(\mathbf{x})$ is generated.
- $\cdot$
For $2\leq t\leq T$, at the beginning of each such iteration, we have access to $\mathbf{x}_{1},\cdots,\mathbf{x}_{t-1}$, the function $F_{t-1}$, and its gradient information, which we denote as $\mathcal{I}_{t-1}(\mathbf{x})=\{F_{t-1},\nabla F_{t-1},\cdots,\nabla^{p}F_{t-1}\}$. The algorithm $\mathcal{A}$ generates the next point with this information: $\mathbf{x}_{t}=\mathcal{A}(\mathcal{I}_{t-1}(\mathbf{x}_{1}),\cdots,\mathcal{I
}_{t-1}(\mathbf{x}_{t-1}))$. Then choose
$\displaystyle\alpha(t)\in\operatorname*{arg\,max}_{k\in[T]\setminus\{\alpha(i)
:i<t\}}\left|\left\langle\mathbf{e}_{\alpha(k)},\,\mathbf{x}_{t}\right\rangle\right|$
$\displaystyle\xi_{t}=\mathrm{sign}\left(\left\langle\mathbf{e}_{\alpha(t)},\,
\mathbf{x}_{t}\right\rangle\right)$
after which a fixed $F_{t}(\mathbf{x})$ is generated for the next iteration.

*5. Indistinguishability of $F_{t}$ and $F$ for Trajectory Generation. * It’s important to note that the trajectory $\mathbf{x}_{1},\cdots,\mathbf{x}_{T}$ is based on *a sequence of functions* $F_{1},\cdots,F_{T}$, whereas our object of analysis should be just *one hard function* $F=F_{T}$. Here we show:

###### Lemma 6 .

The trajectory $\mathbf{x}_{1},\cdots,\mathbf{x}_{T}$ generated by applying an algorithm $\mathcal{A}$ iteratively on the sequence of functions $F_{1},\cdots,F_{T}$, with up to $p^{th}$-order oracle access, is the same as the trajectory generated applying $\mathcal{A}$ directly on $F$ when oracle access pertains only local information within an $\ell_{\infty}$-ball with radius $\delta/2$.

###### Proof.

The idea is to show that $\forall\ 2\leq t\leq T$, the function $g_{t}$ coincides with $g_{T}$ (so that $F_{t}$ coincides with $F_{T}$ in terms of generating $\mathbf{x}_{t+1}$, i.e., $\mathcal{I}_{t}=\mathcal{I}_{T}$) under some mild conditions. Similar proof can be found in (Guzmán and Nemirovski, ; Doikov, , Section 3). By construction, $\forall\ t\in[T]$,

$$ $\displaystyle g_{t}(\mathbf{x})=\max_{1\leq k\leq t}r_{k}(\mathbf{x})=\max \left\{\max_{1\leq k\leq s}r_{k}(\mathbf{x}),\max_{s<k\leq t}r_{k}(\mathbf{x}) \right\}=\max\left\{g_{s}(\mathbf{x}),\max_{s<k\leq t}r_{k}(\mathbf{x})\right\}$ $$

Furthermore, $\alpha(s)\in\operatorname*{arg\,max}_{k\in[T]\setminus\{\alpha(i):i<s\}}\left|
\left\langle\mathbf{e}_{\alpha(k)},\,\mathbf{x}_{t}\right\rangle\right|$ and $\xi_{s}=\mathrm{sign}\left(\left\langle\mathbf{e}_{\alpha(s)},\,\mathbf{x}_{s}
\right\rangle\right)$, therefore

$$ $\displaystyle g_{s}(\mathbf{x}_{s})$ $\displaystyle=\max_{1\leq k\leq s}\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\, \mathbf{x}_{s}\right\rangle-(k-1)\delta\geq\max_{1\leq k\leq s}\xi_{k}\left \langle\mathbf{e}_{\alpha(k)},\,\mathbf{x}_{s}\right\rangle-(s-1)\delta$ $\displaystyle=\left|\left\langle\mathbf{e}_{\alpha(s)},\,\mathbf{x}_{s}\right \rangle\right|-(s-1)\delta\geq\max_{s<k\leq t}\xi_{k}\left\langle\mathbf{e}_{ \alpha(k)},\,\mathbf{x}_{s}\right\rangle-(s-1)\delta$ $\displaystyle\geq\max_{s<k\leq t}\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\, \mathbf{x}_{s}\right\rangle-(k-1)\delta+\delta\hskip 30.0pt(k,s\in\mathbb{Z}^{ +},k>s\implies k\geq s+1)$ $$

If we limit the information access within an $\ell_{\infty}$-ball with radius $\delta/2$ when searching for the next point $\mathbf{x}_{s+1}$ from $\mathbf{x_{s}}$, we then establish a local region $\forall\mathbf{x}$, $\|\mathbf{x}-\mathbf{x_{s}}\|_{\infty}\leq\frac{\delta}{2}$. Further by Lemma 2 that $g_{s}$ (also $\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\,\mathbf{x}\right\rangle$) is $1$-Lipschitz with respect to the $\ell_{\infty}$ norm, we have $\forall\ k$ such that $s<k\leq t$,

$$ $\displaystyle g_{s}(\mathbf{x}_{s})$ $\displaystyle\geq\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\,\mathbf{x}_{s} \right\rangle-(k-1)\delta+2\|\mathbf{x}-\mathbf{x_{s}}\|_{\infty}$ $\displaystyle\geq\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\,\mathbf{x}_{s} \right\rangle-(k-1)\delta+\left[g_{s}(\mathbf{x}_{s})-g_{s}(\mathbf{x})\right] +\left[\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\,\mathbf{x}\right\rangle-\xi _{k}\left\langle\mathbf{e}_{\alpha(k)},\,\mathbf{x}_{s}\right\rangle\right],$ $$

which implies that $g_{s}(\mathbf{x})\geq\max_{s<k\leq t}\xi_{k}\left\langle\mathbf{e}_{\alpha(k)}
,\,\mathbf{x}\right\rangle-(k-1)\delta=\max_{s<k\leq t}r_{k}(\mathbf{x})$. This concludes that $\forall\ \mathbf{x}$ such that $\|\mathbf{x}-\mathbf{x_{s}}\|_{\infty}\leq\frac{\delta}{2}$, $g_{t}(\mathbf{x})=\max\left\{g_{s}(\mathbf{x}),\max_{s<k\leq t}r_{k}(\mathbf{x
})\right\}=g_{s}(\mathbf{x})$, which further implies $F_{t}(\mathbf{x})=F_{s}(\mathbf{x})$. Letting $t=T$ we have $\forall\ t\in[T]$, $F_{t}(\mathbf{x})=F_{T}(\mathbf{x})$ for $\|\mathbf{x}-\mathbf{x_{t}}\|_{\infty}\leq\frac{\delta}{2}$.
∎

###### Lemma 6 .

###### Proof.

#### 4.2.3 Lower Bound Derivation

*6. Bounding the Optimality Gap. * The following lemma bounds optimality gap, whose proof is based on Lemma 5, and is presented in Appendix A.2.

###### Lemma 7 .

$F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})\geq-\beta(T-1)\delta-\frac{5}{4}p\beta
\rho\sqrt{d}+\frac{q-1}{q}\left(\frac{\beta^{q}}{\sigma T^{\frac{q}{2}}}\right
)^{\frac{1}{q-1}}$.

*7. Setting the parameters. *
By Definition 4 and Lemma 14 (i), we know that $S_{\rho}[g_{t}](\mathbf{x}),\nabla S_{\rho}[g_{t}](\mathbf{x})$ depends on the value of $g_{t}(\mathbf{x})$ within an $\ell_{\infty}$-ball of radius $\rho$. Therefore inductively, we see that for $F(\mathbf{x})=\beta S^{p}_{\rho}[g_{T}](\mathbf{x})+\frac{\sigma}{q}\|\mathbf{
x}\|^{q}$, $F(\mathbf{x}),\nabla F(\mathbf{x}),\cdots,\nabla^{p}F(\mathbf{x})$ depends on the value of $F(\mathbf{x})$ within an $\ell_{\infty}$-ball of radius $p\rho$. For our construction to hold, we also need $F_{t}(\mathbf{x})$ and $F(\mathbf{x})$ to be indistinguishable $\forall\ t\in[T]$, which is true within an $\ell_{\infty}$-ball of radius $\delta/2$.

Therefore, we set $\delta=2p\rho$, so that for the purpose of oracle access at $\mathbf{x}_{t}$ (computing (high-order) gradients of $F$), it’s indistinguishable to replace $F(\mathbf{x})$ with $F_{t}(\mathbf{x})$, and the sequence generated as in Section 4.2.2 is the same as that directly applying some $p^{th}$-order algorithm $\mathcal{A}$ on $F(\mathbf{x})$. In other words, $F(\mathbf{x})$ and the generated $\mathbf{x}_{T}$ serve as valid components for deriving the lower bound.

As a result,
$F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})\geq-2p\beta\rho(T-1+\frac{5}{8}\sqrt{d}
)+\frac{q-1}{q}\left(\frac{\beta^{q}}{\sigma T^{\frac{q}{2}}}\right)^{\frac{1}
{q-1}}$.
Let $T\geq\sqrt{d}-1\geq\frac{5}{8}\sqrt{d}-1$, then
$F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})\geq-4\beta\rho T+\frac{q-1}{q}\left(
\frac{\beta^{q}}{\sigma T^{\frac{q}{2}}}\right)^{\frac{1}{q-1}}$.
By letting $4\beta\rho T=\frac{q-1}{2q}\left(\frac{\beta^{q}}{\sigma T^{\frac{q}{2}}}
\right)^{\frac{1}{q-1}}$, we solve for $\rho=\frac{q-1}{8q}\sigma^{-\frac{1}{q-1}}\beta^{\frac{1}{q-1}}T^{\frac{2-3q}{
2(q-1)}}=c_{q}\sigma^{-\frac{1}{q-1}}\beta^{\frac{1}{q-1}}T^{\frac{2-3q}{2(q-1
)}}$, in which $c_{q}=\frac{q-1}{8q}$, and at the same time,

$$ $\displaystyle F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})$ $\displaystyle\geq\frac{q-1}{2q}\left(\frac{\beta^{q}}{\sigma T^{\frac{q}{2}}} \right)^{\frac{1}{q-1}}.\vspace{-20pt}$ (1) $$

By the construction of $F(\mathbf{x})$ and Lemma 4, we know that $F(\mathbf{x})$ is $p^{th}$-order Hölder smooth with parameter $H=\frac{2^{p+1}\beta}{{\rho}^{p+\nu-1}}$.
Plugging in the value of $\rho$, we have

$$ $\displaystyle H=2^{p+1}c_{q}^{-(p+\nu-1)}\sigma^{\frac{p+\nu-1}{q-1}}\beta^{- \frac{p-q+\nu}{q-1}}T^{\frac{(p+\nu-1)(3q-2)}{2(q-1)}},$ $$

equivalently, $\beta=\left(\frac{Hc_{q}^{p+\nu-1}\sigma^{-\frac{p+\nu-1}{q-1}}}{2^{p+1}}
\right)^{-\frac{q-1}{p-q+\nu}}T^{\frac{(p+\nu-1)(3q-2)}{2(p-q+\nu)}}$.
Plugging the value of $\beta$ back into Eq. (1), we have

$$ $\displaystyle F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})$ $\displaystyle\geq\frac{q-1}{2q}\sigma^{-\frac{1}{q-1}}\left(\frac{Hc_{q}^{p+ \nu-1}\sigma^{-\frac{p+\nu-1}{q-1}}}{2^{p+1}}\right)^{-\frac{q}{p-q+\nu}}T^{ \frac{q[3(p+\nu)-2]}{2(p-q+\nu)}}$ $\displaystyle=4\left(\frac{q-1}{8q}\right)^{\frac{(p+\nu)(1-q)}{p-q+\nu}} \sigma\left(\frac{H\sigma^{-1}}{2^{p+1}}\right)^{-\frac{q}{p-q+\nu}}T^{\frac{q [3(p+\nu)-2]}{2(p-q+\nu)}}.$ $$

We complete the proof for Theorem 1 by letting $F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})\leq\epsilon$, from which we solve for $T\geq\left(2^{(2p+2\nu+pq-q)/q}\right)^{-\frac{2}{3(p+\nu)-2}}\left(\frac{q-1}
{8q}\right)^{\frac{2(p+\nu)(q-1)}{q[3(p+\nu)-2]}}\left(\frac{H}{\sigma}\right)
^{\frac{2}{3(p+\nu)-2}}\left(\frac{\sigma}{\epsilon}\right)^{\frac{2(q-p-\nu)}
{q[3(p+\nu)-2]}}$.
∎

###### Lemma 7 .

## 5 Lower Bound for the q < p + ν 𝑞 𝑝 𝜈 q<p+\nu italic_q < italic_p + italic_ν Case

###### Theorem 2 .

For any $T$-step algorithm $\mathcal{A}$ with oracle access up to the $p^{th}$ order, there exists a convex function $f(\mathbf{x})$ whose $p^{th}$-order derivative is Hölder continuous of degree $\nu$ with modulus $H$ and a corresponding $F(\mathbf{x})=f(\mathbf{x})+\frac{\sigma}{q}\|\mathbf{x}\|^{q}$ with regularization that is uniformly convex of degree $q$ with modulus $\sigma$, such that $q<p+\nu$, it takes

$$ $\displaystyle T\in\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu) -2}}+\log\log\left(\left(\frac{\sigma^{p+\nu}}{H^{q}}\right)^{\frac{1}{p+\nu-q }}\frac{1}{\epsilon}\right)\right)$ $$

steps to reach an $\epsilon$-approximate solution $\mathbf{x}_{T}$ satisfying $F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})\leq\epsilon$.

###### Proof.

Similar to all other lower bound proofs, we construct such a function that satisfies the uniformly convex and Hölder smooth conditions and show that it requires at least the number of iterations stated in the Theorem. The construction is generally based on Nesterov’s hard function (Nesterov et al., ), and generalizes the construction in (Arjevani et al., ) to higher-order and the construction in (Kornowski and Shamir, ) to Hölder smooth functions as well as uniformly convex functions.

###### Theorem 2 .

###### Proof.

### 5.1 Function Construction based on Nesterov’s Hard Function

A direct generalization of Nestrov’s construction for first- and second-order lower bounds (Nesterov et al., , Section 2.1.2, 4.3.1) to the $p^{th}$-order Hölder smooth setting takes the form
$\tilde{f}(\mathbf{x})=\frac{1}{p+\nu}\sum_{i=1}^{\tilde{T}}\left|x_{i}-x_{i+1}
\right|^{p+\nu}-\gamma x_{1}+\frac{\tilde{\sigma}}{q}\|\mathbf{x}\|^{q}$,
for $q<p+\nu$, $\nu\in[0,1]$, which is uniformly convex by the regularization. We further add a coefficient so that the function $p^{th}$-order Hölder smooth with the desired parameter $H$ and further on top of this a set of orthogonal basis $\mathbf{v}_{i}$, $\forall\ i\in[\tilde{T}]$ to limit the access of coordinates through the iterations:

$$ $\displaystyle f(\mathbf{x})$ $\displaystyle=\frac{H}{2^{p+\nu+1}(p+\nu-1)!}\left(\frac{1}{p+\nu}\sum_{i=1}^{ \tilde{T}}\left|\left\langle\mathbf{v}_{i},\,\mathbf{x}\right\rangle-\left \langle\mathbf{v}_{i+1},\,\mathbf{x}\right\rangle\right|^{p+\nu}-\gamma\left \langle\mathbf{v}_{1},\,\mathbf{x}\right\rangle\right)+\frac{\sigma}{q}\| \mathbf{x}\|^{q},$ $$

for $\sigma=\frac{H\tilde{\sigma}}{2^{p+\nu+1}(p+\nu-1)!}$, or equivalently, $\tilde{\sigma}=\frac{2^{p+\nu+1}(p+\nu-1)!\sigma}{H}$. $\mathbf{v}_{i}$ is chosen iteratively to be orthogonal to $\mathbf{x}_{1},\cdots,\mathbf{x}_{i}$ and $\mathbf{v}_{1},\cdots,\mathbf{v}_{i-1}$. Similar to (Arjevani et al., , Lemma 7), one can show that the oracle information of $f(\mathbf{x}_{i})$, $\forall\ i\leq t$ does not depend on $\mathbf{v}_{t+1},\cdots,\mathbf{v}_{\tilde{T}}$, so that the iterative construction of $\mathbf{v}_{i}$ is valid, i.e., does not affect the $\mathbf{x}_{i}$ generated running an algorithm on $f$. Now we characterize the relation between $\tilde{f}$ and $f$.

###### Lemma 8 .

$\mathbf{x}^{\ast}=\operatorname*{arg\,min}_{\mathbf{x}}f(\mathbf{x})$, $\mathbf{y}=\operatorname*{arg\,min}_{\mathbf{x}}\tilde{f}(\mathbf{x})$. (i) $\forall i\in[\tilde{T}]$, $\left\langle\mathbf{v}_{i},\,\mathbf{x}^{\ast}\right\rangle=\mathbf{y}_{i}$. (ii) $\|\mathbf{x}^{\ast}\|=\|\mathbf{y}\|$.

Next, we characterize the convexity and smoothness of the constructed function. Specifically, we can show with the proof in Appendix B that $f$ satisfies the following lemma.

###### Lemma 9 .

$f(\mathbf{x})$ is (i) uniformly convex with degree $q$ and parameter $\sigma$. (ii) $p^{th}$-order Hölder smooth with degree $\nu$ and parameter $H$.

The analysis of (Nesterov et al., ) then derives the lower bound based on the closed-form optimal solution that minimizes the hard function. For our generalized construction of $f$, however, the closed-form solution is hard to obtain. As in (Arjevani et al., ), we instead analyze some properties of $f$ for each of these lower bounds. For simplicity, we state the properties for function $\tilde{f}$, and since $f$ is simply a scaling of $\tilde{f}$, the properties also apply to $f$ with a difference of constants. To prove Theorem 2, we show separately for the $\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}$ term and the $\log\log\left(\left(\frac{\sigma^{p+\nu}}{H^{q}}\right)^{\frac{1}{p+\nu-q}}
\frac{1}{\epsilon}\right)$ term. The derivation is largely based on some key lemmas whose complete proof is in Appendix B.

###### Lemma 8 .

###### Lemma 9 .

### 5.2 T ∈ Ω ⁢ ( ( H σ ) 2 3 ⁢ ( p + ν ) − 2 ) 𝑇 Ω superscript 𝐻 𝜎 2 3 𝑝 𝜈 2 T\in\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}\right) italic_T ∈ roman_Ω ( ( divide start_ARG italic_H end_ARG start_ARG italic_σ end_ARG ) start_POSTSUPERSCRIPT divide start_ARG 2 end_ARG start_ARG 3 ( italic_p + italic_ν ) - 2 end_ARG end_POSTSUPERSCRIPT )

Since we cannot solve for a closed form solution from $\operatorname*{arg\,min}_{\mathbf{x}}\tilde{f}(\mathbf{x})$, we need to alternatively bound the solution in a relative scale. One key observation is that the coordinates of the optimal solution form a decreasing sequence (Arjevani et al., ; Carmon et al., ), and their relative relation can be characterized as in Lemma 10 (i) utilizing the first-order optimality condition. Based on the properties of each coordinate, one can relate them to the norm of the optimal solution as in Lemma 10 (iii).

###### Lemma 10 .

For $\mathbf{y}=\operatorname*{arg\,min}_{\mathbf{x}}\tilde{f}(\mathbf{x})$,

- (i)
$\forall t\in[\tilde{T}]$, $y_{t}\geq y_{1}-(t-1)\gamma^{\frac{1}{p+\nu-1}}$.
- (ii)
For $\tilde{T}=\left\lfloor\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1}}}+1\right\rfloor$, $y_{1}\leq\gamma^{\frac{1}{p+\nu-1}}+\sqrt{\frac{2\gamma^{\frac{p+\nu}{p+\nu-1}
}}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}}$.
- (iii)
For $\gamma\geq\tilde{\sigma}^{\frac{p+\nu-1}{p+\nu-2}}\|\mathbf{y}\|^{\frac{(p+\nu
-1)(q-2)}{p+\nu-2}}$, $\forall t\in[\tilde{T}]$, $y_{t}\geq\frac{\gamma^{\frac{p+\nu}{2(p+\nu-1)}}}{2^{p+\nu+1}\tilde{\sigma}^{
\frac{1}{2}}\|\mathbf{y}\|^{\frac{q-2}{2}}}+\left(\frac{1}{2}-i\right)\gamma^{
\frac{1}{p+\nu-1}}$.

Then the bound on the norm of the optimal solution can be established in the following lemma.

###### Lemma 11 .

$\|\mathbf{y}\|\leq\frac{2^{\frac{2}{3q-2}}\gamma^{\frac{3(p+\nu)-2}{(p+\nu-1)(
3q-2)}}}{\tilde{\sigma}^{\frac{3}{3q-2}}}$.

The final step is to relate this norm to the optimality gap with the property of uniform convexity. By Lemma 8 and Lemma 10 (iii),
$\langle\mathbf{v}_{T},\mathbf{x}^{\ast}\rangle=y_{T}\geq\frac{\gamma^{\frac{p+
\nu}{2(p+\nu-1)}}}{2^{p+\nu+1}\tilde{\sigma}^{\frac{1}{2}}\|\mathbf{y}\|^{
\frac{q-2}{2}}}+\left(\frac{1}{2}-T\right)\gamma^{\frac{1}{p+\nu-1}}$.
Therefore, with $\mathbf{v}_{T}$ and $\mathbf{x}_{T}$ orthogonal to each other by construction,

$$ $\displaystyle f(\mathbf{x}_{T})-f(\mathbf{x}^{\ast})$ $\displaystyle\geq\frac{\sigma}{q}\|\mathbf{x}_{T}-\mathbf{x}^{\ast}\|^{q}= \frac{\sigma}{q}\left(\sum_{i=1}^{\tilde{T}}\left(\langle\mathbf{v}_{i}, \mathbf{x}_{T}-\mathbf{x}^{\ast}\rangle\right)^{2}\right)^{\frac{q}{2}}\geq \frac{\sigma}{q}\left(\left(\langle\mathbf{v}_{T},\mathbf{x}_{T}-\mathbf{x}^{ \ast}\rangle\right)^{2}\right)^{\frac{q}{2}}$ $\displaystyle=\frac{\sigma}{q}\left(\langle\mathbf{v}_{T},\mathbf{x}^{\ast} \rangle\right)^{q}\geq\frac{\sigma}{q}\left(\frac{\gamma^{\frac{p+\nu}{2(p+\nu -1)}}}{2^{p+\nu+1}\tilde{\sigma}^{\frac{1}{2}}\|\mathbf{y}\|^{\frac{q-2}{2}}}+ \left(\frac{1}{2}-T\right)\gamma^{\frac{1}{p+\nu-1}}\right)^{q}$ $$

In order to achieve $f(\mathbf{x}_{T})-f(\mathbf{x}^{\ast})\leq\epsilon$, we have $\frac{\sigma}{q}\left(\frac{\gamma^{\frac{p+\nu}{2(p+\nu-1)}}}{2^{p+\nu+1}
\tilde{\sigma}^{\frac{1}{2}}\|\mathbf{y}\|^{\frac{q-2}{2}}}+\left(\frac{1}{2}-
T\right)\gamma^{\frac{1}{p+\nu-1}}\right)^{q}\leq\epsilon$,
from which we can solve for
$T\geq\frac{\gamma^{\frac{p+\nu-2}{2(p+\nu-1)}}}{2^{p+\nu+1}\tilde{\sigma}^{
\frac{1}{2}}\|\mathbf{y}\|^{\frac{q-2}{2}}}+\frac{1}{2}-\left(\frac{q\epsilon}
{\sigma\gamma^{\frac{q}{p+\nu-1}}}\right)^{\frac{1}{q}}$.
For $\epsilon\leq\frac{\gamma^{\frac{q}{p+\nu-1}}\sigma}{2^{q}q}$, we have $\frac{1}{2}-\left(\frac{q\epsilon}{\sigma\gamma^{\frac{q}{p+\nu-1}}}\right)^{
\frac{1}{q}}\geq 0$. Therefore, $T\geq\frac{\gamma^{\frac{p+\nu-2}{2(p+\nu-1)}}}{2^{p+\nu+1}\tilde{\sigma}^{
\frac{1}{2}}\|\mathbf{y}\|^{\frac{q-2}{2}}}$.

By Lemma 11, we know that
$\|\mathbf{y}\|\leq\frac{2^{\frac{2}{3q-2}}\gamma^{\frac{3(p+\nu)-2}{(p+\nu-1)(
3q-2)}}}{\tilde{\sigma}^{\frac{3}{3q-2}}}$.
Therefore, for $\mathbf{x}_{0}=\mathbf{0}$, by Lemma 8, $\|\mathbf{x}_{0}-\mathbf{x}^{\ast}\|=\|\mathbf{x}^{\ast}\|=\|\mathbf{y}\|\leq
\frac{2^{\frac{2}{3q-2}}\gamma^{\frac{3(p+\nu)-2}{(p+\nu-1)(3q-2)}}}{\tilde{
\sigma}^{\frac{3}{3q-2}}}$.
To satisfy the condition $\|\mathbf{x}_{0}-\mathbf{x}^{\ast}\|\leq D$, we let $\frac{2^{\frac{2}{3q-2}}\gamma^{\frac{3(p+\nu)-2}{(p+\nu-1)(3q-2)}}}{\tilde{
\sigma}^{\frac{3}{3q-2}}}\leq D$,
then we can solve for $\gamma\leq 2^{-\frac{2(p+\nu-1)}{3(p+\nu)-2}}D^{\frac{(p+\nu-1)(3q-2)}{3(p+\nu
)-2}}\tilde{\sigma}^{\frac{3(p+\nu-1)}{3(p+\nu)-2}}$. Plug this as well as $\|\mathbf{y}\|\leq D$ into the lower bound on $T$ we have

$$ $\displaystyle T$ $\displaystyle\geq\frac{\left(2^{-\frac{2(p+\nu-1)}{3(p+\nu)-2}}D^{\frac{(p+\nu -1)(3q-2)}{3(p+\nu)-2}}\tilde{\sigma}^{\frac{3(p+\nu-1)}{3(p+\nu)-2}}\right)^{ \frac{p+\nu-2}{2(p+\nu-1)}}}{2^{p+\nu+1}\tilde{\sigma}^{\frac{1}{2}}D^{\frac{q -2}{2}}}=2^{-\frac{p+\nu-2}{3(p+\nu)-2}-(p+\nu+1)}D^{\frac{2(p+\nu-q-1)}{3(p+ \nu)-2}}\tilde{\sigma}^{-\frac{2}{3(p+\nu)-2}}$ $$

Plugging in $\tilde{\sigma}=\frac{2^{p+\nu+1}(p+\nu-1)!\sigma}{H}$, we have $T\in\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}\right)$.

###### Lemma 10 .

###### Lemma 11 .

### 5.3 T ∈ Ω ⁢ ( log ⁡ log ⁡ ( ( σ p + ν H q ) 1 p + ν − q ⁢ 1 ϵ ) ) 𝑇 Ω superscript superscript 𝜎 𝑝 𝜈 superscript 𝐻 𝑞 1 𝑝 𝜈 𝑞 1 italic-ϵ T\in\Omega\left(\log\log\left(\left(\frac{\sigma^{p+\nu}}{H^{q}}\right)^{\frac%
{1}{p+\nu-q}}\frac{1}{\epsilon}\right)\right) italic_T ∈ roman_Ω ( roman_log roman_log ( ( divide start_ARG italic_σ start_POSTSUPERSCRIPT italic_p + italic_ν end_POSTSUPERSCRIPT end_ARG start_ARG italic_H start_POSTSUPERSCRIPT italic_q end_POSTSUPERSCRIPT end_ARG ) start_POSTSUPERSCRIPT divide start_ARG 1 end_ARG start_ARG italic_p + italic_ν - italic_q end_ARG end_POSTSUPERSCRIPT divide start_ARG 1 end_ARG start_ARG italic_ϵ end_ARG ) )

For the $\log\log$ term, we follow a similar narrative as in Section 5.2, starting from characterizing the per-coordinate relation of the optimal solution.

###### Lemma 12 .

For $\mathbf{y}=\operatorname*{arg\,min}_{\mathbf{x}}\tilde{f}(\mathbf{x})$, let $t_{1}\in[\tilde{T}]$ be such that $y_{t_{1}}>\frac{1}{p+\nu-1}\tilde{\sigma}^{\frac{1}{p+\nu-2}}\|\mathbf{y}\|^{
\frac{q-2}{p+\nu-2}}$ and $y_{t_{1}+1}\leq\frac{1}{p+\nu-1}\tilde{\sigma}^{\frac{1}{p+\nu-2}}\|\mathbf{y}
\|^{\frac{q-2}{p+\nu-2}}$. Then

- (i)
$\forall i\in[\tilde{T}]$, $y_{i}=y_{i+1}+\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j={i+1}}^{\tilde{T
}}y_{j}\right)^{\frac{1}{p+\nu-1}}$ and $y_{i+1}\leq\frac{1}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}y_{i}^{p}$
- (ii)
$\forall i\geq t_{1}$, $\left(\frac{1}{c_{p,\nu}}\right)^{p+\nu-1}\frac{1}{\tilde{\sigma}\|\mathbf{y}
\|^{q-2}}y_{i}^{p+\nu-1}\leq y_{i+1}$ where $c_{p,\nu}$ is a constant depending on $p$, $\nu$.
- (iii)
$\forall i\leq\tilde{T}-t_{1}$,
$y_{t_{1}+i}\geq\left(\frac{1}{c_{p,\nu}}\right)^{\frac{({p+\nu-1})(({p+\nu-1})
^{i}-1)}{p+\nu-2}}\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\right)^{\frac{1}{p+
\nu-2}}({p+\nu-1})^{-({p+\nu-1})^{i}}.$

Next, we derive the bound on the norm $\|\mathbf{x}_{T}-\mathbf{x}^{\ast}\|^{q}$ from the coordinate-wise properties in Lemma 12 with the basis defined for $f$. When constructing the function, we choose $H\geq 2^{p+\nu+1}(p+\nu-1)!\sigma$ so that $\tilde{\sigma}\leq 1$. Then for basis vector $\mathbf{v}_{t_{1}+i}$, by Lemma 8 and Lemma 12 (iii),

$$ $\displaystyle\langle\mathbf{v}_{t_{1}+i},\mathbf{x}^{\ast}\rangle=y_{t_{1}+i} \geq\left(\frac{1}{c_{p,\nu}}\right)^{\frac{({p+\nu-1})(({p+\nu-1})^{i}-1)}{p+ \nu-2}}\cdot\tilde{\sigma}^{\frac{1}{p+\nu-q}}\|\mathbf{y}\|^{\frac{q-2}{p+\nu -2}}\cdot({p+\nu-1})^{-({p+\nu-1})^{i}}$ $\displaystyle=\left(\frac{1}{c_{p,\nu}}\right)^{\frac{({p+\nu-1})(({p+\nu-1})^ {i}-1)}{p+\nu-2}}\cdot\left(\frac{2^{p+\nu+1}(p+\nu-1)!\sigma}{H}\right)^{ \frac{1}{p+\nu-q}}\|\mathbf{x}_{0}-\mathbf{x}^{\ast}\|^{\frac{q-2}{p+\nu-2}} \cdot({p+\nu-1})^{-({p+\nu-1})^{i}},$ $$

for $\mathbf{x}_{0}=0$, in which the first inequality follows from Lemma 12 (iii), and then the fact that for $q\geq 2$ and $\tilde{\sigma}\leq 1$, $\tilde{\sigma}^{\frac{1}{p+\nu-q}}\leq\tilde{\sigma}^{\frac{1}{p+\nu-2}}$. For $t_{1}\leq\frac{\tilde{T}}{2}$,

$$ $\displaystyle\|\mathbf{x}_{T}-\mathbf{x}^{\ast}\|^{q}$ $\displaystyle=(\|\mathbf{x}_{T}-\mathbf{x}^{\ast}\|^{2})^{\frac{q}{2}}\geq \left(\sum_{i=1}^{\tilde{T}}\left(\langle\mathbf{v}_{i},\mathbf{x}_{T}-\mathbf {x}^{\ast}\rangle\right)^{2}\right)^{\frac{q}{2}}\geq\left(\left(\langle \mathbf{v}_{t_{1}+T},\mathbf{x}_{T}-\mathbf{x}^{\ast}\rangle\right)^{2}\right) ^{\frac{q}{2}}$ $\displaystyle=\left(\left(\langle\mathbf{v}_{t_{1}+T},\mathbf{x}^{\ast}\rangle \right)^{2}\right)^{\frac{q}{2}}=\left(\langle\mathbf{v}_{t_{1}+T},\mathbf{x}^ {\ast}\rangle\right)^{q}$ $$

where the equality in the second line follows from the fact that by construction, $\mathbf{v}_{t_{1}+T}$ and $\mathbf{x}_{T}$ are orthogonal.

Finally, with uniform convexity, we have

$$ $\displaystyle f(\mathbf{x}_{T})-f(\mathbf{x}^{\ast})\geq\frac{\sigma}{q}\| \mathbf{x}_{T}-\mathbf{x}^{\ast}\|^{q}$ $\displaystyle\geq\left(\frac{1}{c_{p,\nu}}\right)^{\frac{q(p+\nu-1)(({p+\nu-1} )^{T}-1)}{p+\nu-2}}\cdot\frac{\sigma}{q}\left(\frac{2^{p+\nu+1}(p+\nu-1)! \sigma}{H}\right)^{\frac{q}{p+\nu-q}}\|\mathbf{x}_{0}-\mathbf{x}^{\ast}\|^{ \frac{q(q-2)}{p+\nu-2}}\cdot({p+\nu-1})^{-q({p+\nu-1})^{T}}$ $\displaystyle=c_{p,q,\nu}\cdot\frac{\sigma^{\frac{p+\nu}{p+\nu-q}}}{L_{p}^{ \frac{q}{p+\nu-q}}}\cdot({p+\nu-1})^{-q({p+\nu-1})^{T}}$ $$

for $c_{p,q,\nu}=\frac{2^{\frac{(p+\nu+1)q}{p+\nu-q}}((p+\nu-1)!)^{\frac{q}{p+\nu-q
}}}{q}\left(\frac{1}{c_{p,\nu}}\right)^{\frac{q(p+\nu-1)(({p+\nu-1})^{T}-1)}{p
+\nu-2}}D^{\frac{q(q-2)}{p+\nu-2}}$ in which $\|\mathbf{x}_{0}-\mathbf{x}^{\ast}\|\leq D$.
In order to achieve $f(\mathbf{x}_{T})-f(\mathbf{x}^{\ast})\leq\epsilon$, we have $c_{p,q,\nu}\cdot\frac{\sigma^{\frac{p+\nu}{p+\nu-q}}}{L_{p}^{\frac{q}{p+\nu-q}
}}\cdot({p+\nu-1})^{-q({p+\nu-1})^{T}}\leq\epsilon$,
from which we solve for
$T\geq\log\log_{p+\nu-1}\left(c_{p,q,\nu}\frac{\sigma^{\frac{p+q-1}{p-1}}}{L_{p
}^{\frac{q}{p-1}}}\cdot\frac{1}{\epsilon}\right)+\log_{p+\nu-1}\left(\frac{1}{
q}\right)$, which completes the proof for Theorem 2 combined with the result in Section 5.2.
∎

###### Lemma 12 .

## 6 Conclusion and Future Work

We provide tight lower bounds for minimizing functions with asymmetric high-order Hölder smoothness and uniform convexity. Specifically, we show that the oracle complexity is lower bounded by $\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}\left(\frac{
\sigma}{\epsilon}\right)^{\frac{2(q-p-\nu)}{q(3(p+\nu)-2)}}\right)$ for the $q>p+\nu$ case with the construction of a $\ell_{\infty}$-ball-truncated-Gaussian smoothed hard function, and $\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}+\log\log\left
(\left(\frac{\sigma^{p+\nu}}{H^{q}}\right)^{\frac{1}{p+\nu-q}}\frac{1}{
\epsilon}\right)\right)$ for the $q<p+\nu$ case. Both lower bounds match the corresponding upper bounds in the general setting.

We note that the lower bound for the $q=p+\nu$ case is not included in this paper. Furthermore, the lower bounds for the $q>p+\nu$ case and the $q<p+\nu$ case are derived based on two different frameworks. Proposing a unified framework for all three cases would be of great interest, which we leave for future work.

## Appendix A Proof for Technical Lemmas in Section 4

### A.1 Properties of Truncated Gaussian Smoothing

###### Lemma 13 ( $\ell_{\infty}$ -Ball Truncated Gaussian and Its Marginal Distribution) .

For standard MVN truncated in a unit $\ell_{\infty}$-ball as defined in Definition 4:

$$ $\displaystyle\mathbb{P}[V=\mathbf{v}]=\frac{1}{Z(2\pi)^{\frac{d}{2}}}\exp\left \{-\frac{\mathbf{v}^{\top}\mathbf{v}}{2}\right\}\mathbb{I}_{[\|\mathbf{v}\|_{ \infty}\leq 1]},$ $$

- (i)
The cumulative distribution within the $\ell_{\infty}$-ball, i.e., the normalizing factor $Z(d)=\left[\Phi(1)-\Phi(-1)\right]^{d}$.
- (ii)
The marginal distribution is a standard normal truncated within $[-1,1]$.

###### Proof.

(i) By Eq. (3) in (Cartinhour, ), we know that

$$ $\displaystyle Z(d)$ $\displaystyle=\int_{\|\mathbf{v}\|_{\infty}\leq 1}\frac{1}{(2\pi)^{\frac{d}{2} }}\exp\left\{-\frac{\mathbf{v}^{\top}\mathbf{v}}{2}\right\}d\mathbf{v}$ $\displaystyle=\underbrace{\int_{-1}^{1}\cdots\int_{-1}^{1}}_{\text{$d$-time integration, one for each coordinate}}\frac{1}{(2\pi)^{\frac{d}{2}}}\exp\left \{-\frac{\sum_{i=1}^{d}v_{i}^{2}}{2}\right\}dv_{1}\cdots dv_{d}$ $\displaystyle=\prod_{i=1}^{d}\int_{-1}^{1}\frac{1}{\sqrt{2\pi}}\exp\left\{- \frac{v_{i}^{2}}{2}\right\}dv_{i}$ $\displaystyle=\left[\Phi(1)-\Phi(-1)\right]^{d}.$ $$

(ii) By Eq. (4) and (16) in (Cartinhour, ), $\forall i\in[d]$,

$$ $\displaystyle\mathbb{P}\left[V_{i}\right]$ $\displaystyle=\frac{\exp\left\{-\frac{v_{i}^{2}}{2}\right\}}{\left[\Phi(1)- \Phi(-1)\right]^{d}\sqrt{2\pi}}\underbrace{\int_{-1}^{1}\cdots\int_{-1}^{1}}_{ \text{$d-1$-time integration}}\frac{\exp\left\{-\frac{\sum_{j\neq i}v_{j}^{2}} {2}\right\}}{(2\pi)^{\frac{d-1}{2}}}dv_{1}\cdots dv_{i-1}dv_{i+1}\cdots dv_{d}$ $\displaystyle=\frac{\exp\left\{-\frac{v_{i}^{2}}{2}\right\}}{\left[\Phi(1)- \Phi(-1)\right]^{d}\sqrt{2\pi}}\prod_{j\neq i}\int_{-1}^{1}\frac{1}{\sqrt{2\pi }}\exp\left\{-\frac{v_{j}^{2}}{2}\right\}dv_{j}$ $\displaystyle=\frac{\exp\left\{-\frac{v_{i}^{2}}{2}\right\}}{\left[\Phi(1)- \Phi(-1)\right]^{d}\sqrt{2\pi}}\left[\Phi(1)-\Phi(-1)\right]^{d-1}$ $\displaystyle=\frac{1}{\left[\Phi(1)-\Phi(-1)\right]\sqrt{2\pi}}\exp\left\{- \frac{v_{i}^{2}}{2}\right\}$ $\displaystyle=\frac{1}{\sqrt{2\pi}\int_{-1}^{1}\frac{1}{\sqrt{2\pi}}\exp\left \{-\frac{v_{i}^{2}}{2}\right\}dv_{i}}\exp\left\{-\frac{v_{i}^{2}}{2}\right\},$ $$

if $-1\leq V_{i}\leq 1$, otherwise $\mathbb{P}\left[V_{i}\right]=0$.
Therefore, $V_{i}$ follows the truncated standard normal distribution within $[-1,1]$.
∎

###### Lemma 14 (Properties of Truncated Gaussian Smoothing) .

For a function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ that is $L$-Lipschitz with respect to the $\ell_{2}$ norm, then $\forall\ \mathbf{x}\in\mathbb{R}^{d}$,

- (i)
If $f$ is convex and non-differentiable in a set with Lebesgue measure 0 0, then $f_{\rho}$ is continuously differentiable and $\nabla f_{\rho}(\mathbf{x})=\mathbb{E}_{V}[\partial f(\mathbf{x}+\rho V)]$ for some random variable $V$.
- (ii)
If $f$ is convex, $f_{\rho}$ is convex and $L$-Lipschitz with respect to the $\ell_{2}$ norm.
- (iii)
If $f$ is convex, $f(\mathbf{x})\leq f_{\rho}(\mathbf{x})\leq f(\mathbf{x})+\frac{5}{4}L\rho\sqrt
{d}$.
- (iv)
$\nabla f_{\rho}$ is $\frac{2}{\rho}L$-Lipschitz, i.e., $f_{\rho}$ is $\frac{2}{\rho}L$-smooth.

###### Proof.

The proof of this lemma is based on that of Lemma 9 in (Duchi et al., ).

(i) The differentiability is established in (Bertsekas, , Proposition 2.3), and $\nabla f_{\rho}(\mathbf{x})=\mathbb{E}_{V}[\partial f(\mathbf{x}+\rho V)]$ in (Bertsekas, , Proposition 2.2).

(ii) Expectation preserves convexity (Boyd and Vandenberghe, , Section 3.2.1), therefore, given that $f$ is convex, by definition, $f_{\rho}$ is also convex. For Lipschitz continuity, by the second part of (i) and Jensen’s inequality, we have

$$ $\displaystyle\|\nabla f_{\rho}(\mathbf{x})\|$ $\displaystyle=\|\mathbb{E}_{V}[\partial f(\mathbf{x}+\rho V)]\|$ $\displaystyle\leq\mathbb{E}_{V}[\|\partial f(\mathbf{x}+\rho V)\|].$ $$

Given that $f$ is $L$-Lipschitz over $\mathbb{R}^{d}$ with respect to the $\ell_{2}$ norm, it is implied that $\forall\mathbf{x}\in\mathbb{R}^{d}$, $\|\partial f(\mathbf{x})\|\leq L$. As a result,
$\|\nabla f_{\rho}(\mathbf{x})\|\leq\mathbb{E}[L]\leq L$ which further implies that $f_{\rho}$ is $L$-Lipschitz with respect to the $\ell_{2}$ norm.

(iii) For $f_{\rho}(\mathbf{x})=\mathbb{E}_{V}[f(\mathbf{x}+\rho V)]$, $\mathbb{E}_{V}[V]=0$ by construction. And since smoothing preserves convexity, $f_{\rho}(\mathbf{x})$ is also convex. For the lower bound, using Jensen’s inequality,

$$ $\displaystyle f(\mathbf{x})$ $\displaystyle=f(\mathbf{x}+\rho\mathbb{E}_{V}[V])$ $\displaystyle=f(\mathbb{E}_{V}[\mathbf{x}+\rho V])$ $\displaystyle\leq\mathbb{E}_{V}[f(\mathbf{x}+\rho V)]$ $\displaystyle=f_{\rho}(\mathbf{x}).$ $$

For the upper bound, since $f$ is $L$-Lipschitz in $\ell_{2}$-norm, $f(\mathbf{x}+\rho V)-f(\mathbf{x})\leq L\|\rho V\|$. Therefore,

$$ $\displaystyle f_{\rho}(\mathbf{x})$ $\displaystyle=\mathbb{E}_{V}[f(\mathbf{x}+\rho V)]$ $\displaystyle\leq\mathbb{E}_{V}[f(\mathbf{x})+L\rho\|V\|]$ $\displaystyle=f(\mathbf{x})+L\rho\mathbb{E}\left[\sqrt{\sum_{i=1}^{d}V_{i}^{2} }\right]$ $\displaystyle\leq f(\mathbf{x})+L\rho\sqrt{\sum_{i=1}^{d}\mathbb{E}\left[V_{i} ^{2}\right]}.$ $$

By Lemma 13 (ii), $V_{i}$ follows the standard normal distribution truncated within $[-1,1]$. Therefore, let $\Phi(\cdot)$ denote the cumulative distribution function of standard normal distribution, then

$$ $\displaystyle\mathbb{E}\left[V_{i}^{2}\right]$ $\displaystyle=\int_{-1}^{1}\frac{\phi(\tau)}{\Phi(1)-\Phi(-1)}\tau^{2}d\tau$ $\displaystyle=\frac{1}{\Phi(1)-\Phi(-1)}\int_{-1}^{1}\phi(\tau)\tau^{2}d\tau$ $\displaystyle\leq\frac{1}{\Phi(1)-\Phi(-1)}\int_{-\infty}^{\infty}\phi(\tau) \tau^{2}d\tau$ $\displaystyle=\frac{\mathbb{E}\left[U_{i}^{2}\right]}{\Phi(1)-\Phi(-1)}$ $$

for $U_{i}\sim\mathcal{N}(0,1)$, $\forall i\in[d]$.
Then for $U=[U_{1},\cdots,U_{d}]^{\top}$, $U$ follows the standard MVN distribution and

$$ $\displaystyle f_{\rho}(\mathbf{x})$ $\displaystyle\leq f(\mathbf{x})+L\rho\sqrt{\frac{\mathbb{E}\left[\sum_{i=1}^{d }U_{i}^{2}\right]}{\Phi(1)-\Phi(-1)}}$ $\displaystyle=f(\mathbf{x})+L\rho\sqrt{\frac{\mathbb{E}\left[\|U\|^{2}\right]} {\Phi(1)-\Phi(-1)}}.$ $$

$\mathbb{E}\left[\|U\|^{2}\right]$ is the second moment of the standard MVN, which is bounded by the dimension $d$ (Nesterov and Spokoiny, , Lemma 1). We know that $\Phi(1)-\Phi(-1)\approx 0.6827$. As a result, we have

$$ $\displaystyle f_{\rho}(\mathbf{x})$ $\displaystyle\leq f(\mathbf{x})+\frac{5}{4}L\rho\sqrt{d}.$ $$

(iv) The proof of this lemma follows that of Lemma 3.3 point 3 in (Lakshmanan and De Farias, ), also seen in that of Lemma 9 (iii) in (Duchi et al., ). Denote the PDF of the unit $\ell_{\infty}$-ball-truncated standard MVN as $\phi_{\|\cdot\|_{\infty}\leq 1}(\cdot;0,1)$. Then for $f_{\rho}(\mathbf{x})=\mathbb{E}_{V}[f(\mathbf{x}+\rho V)]$, $\rho V$ has PDF $\phi_{\|\cdot\|_{\infty}\leq\rho}(\cdot;0,\rho^{2})$ by Lemma 2 (v) in (Chen et al., ). By
(Duchi et al., , Lemma 11), $\forall\ \mathbf{x},\mathbf{x}^{\prime}\in\mathbb{R}^{d}$, for $Z$ from $\phi_{\|\cdot\|_{\infty}\leq\rho}(\cdot;0,\rho^{2})$,

$$ $\displaystyle\|\nabla f_{\rho}(\mathbf{x})-\nabla f_{\rho}(\mathbf{x}^{\prime} )\|_{2}\leq L\underbrace{\int\left|\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{ \mathbf{z}-\mathbf{x}};0,\rho^{2})-\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{ \mathbf{z}-\mathbf{x}^{\prime}};0,\rho^{2})\right|d\mathbf{z}}_{I}.$ $$

Now we bound the integral. Note that $\forall\ \mathbf{x}$, $\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{x};0,\rho^{2})$ is a truncated MVN symmetrically centered at the origin, consequently, is strictly decreasing with respect to $\|\mathbf{x}\|_{2}$(^2^22Importantly, the PDF is strictly decreasing with respect to $\|\mathbf{\cdot}\|_{2}$, not $\|\mathbf{\cdot}\|_{\infty}$, no matter in which norm the truncation is done, as long as centered at the origin.). As a result, $\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{z}-\mathbf{x};0,\rho^{2})\geq\phi_{
\|\cdot\|_{\infty}\leq\rho}(\mathbf{z}-\mathbf{x}^{\prime};0,\rho^{2})$ if and only if $\|\mathbf{z}-\mathbf{x}\|_{2}\leq\|\mathbf{z}-\mathbf{x}^{\prime}\|_{2}$. Therefore,

$$ $\displaystyle I$ $\displaystyle=2\int_{\|\mathbf{z}-\mathbf{x}\|_{2}\leq\|\mathbf{z}-\mathbf{x}^ {\prime}\|_{2}}\left(\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{z}-\mathbf{x};0 ,\rho^{2})-\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{z}-\mathbf{x}^{\prime};0, \rho^{2})\right)d\mathbf{z}$ $\displaystyle=2\int_{\|\mathbf{z}-\mathbf{x}\|_{2}\leq\|\mathbf{z}-\mathbf{x}^ {\prime}\|_{2}}\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{z}-\mathbf{x};0,\rho^ {2})d\mathbf{z}-2\int_{\|\mathbf{z}-\mathbf{x}\|_{2}\leq\|\mathbf{z}-\mathbf{x }^{\prime}\|_{2}}\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{z}-\mathbf{x}^{ \prime};0,\rho^{2})d\mathbf{z}.$ $$

Denote $\mathbf{y}=\mathbf{z}-\mathbf{x}$ and $\mathbf{y}^{\prime}=\mathbf{z}-\mathbf{x}^{\prime}$, then

$$ $\displaystyle I$ $\displaystyle=2\int_{\|\mathbf{y}\|_{2}\leq\|\mathbf{y}-(\mathbf{x}^{\prime}- \mathbf{x})\|_{2}}\phi_{\|\cdot\|_{\infty}\leq\rho}(\mathbf{y};0,\rho^{2})d \mathbf{y}-2\int_{\|\mathbf{y}^{\prime}\|_{2}\geq\|\mathbf{y}^{\prime}-( \mathbf{x}-\mathbf{x}^{\prime})\|_{2}}\phi_{\|\cdot\|_{\infty}\leq\rho}( \mathbf{y}^{\prime};0,\rho^{2})d\mathbf{y}^{\prime}$ $\displaystyle=2\mathbb{P}_{\phi_{\|\cdot\|_{\infty}\leq\rho}}\left[\|Z\|_{2} \leq\|Z-(\mathbf{x}^{\prime}-\mathbf{x})\|_{2}\right]-2\mathbb{P}_{\phi_{\| \cdot\|_{\infty}\leq\rho}}\left[\|Z^{\prime}\|_{2}\geq\|Z^{\prime}-(\mathbf{x} -\mathbf{x}^{\prime})\|_{2}\right]$ $\displaystyle=2\mathbb{P}_{\phi_{\|\cdot\|_{\infty}\leq\rho}}\left[\|Z\|_{2}^{ 2}\leq\|Z-(\mathbf{x}^{\prime}-\mathbf{x})\|_{2}^{2}\right]-2\mathbb{P}_{\phi_ {\|\cdot\|_{\infty}\leq\rho}}\left[\|Z^{\prime}\|_{2}^{2}\geq\|Z^{\prime}-( \mathbf{x}-\mathbf{x}^{\prime})\|_{2}^{2}\right]$ $\displaystyle=2\mathbb{P}_{\phi_{\|\cdot\|_{\infty}\leq\rho}}\left[2\left \langle Z,\,\mathbf{x}^{\prime}-\mathbf{x}\right\rangle\leq\|\mathbf{x}^{ \prime}-\mathbf{x}\|_{2}^{2}\right]-2\mathbb{P}_{\phi_{\|\cdot\|_{\infty}\leq \rho}}\left[2\left\langle Z^{\prime},\,\mathbf{x}-\mathbf{x}^{\prime}\right \rangle\geq\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}^{2}\right]$ $\displaystyle=2\mathbb{P}_{\phi_{\|\cdot\|_{\infty}\leq\rho}}\left[\left \langle Z,\,\frac{\mathbf{x}^{\prime}-\mathbf{x}}{\|\mathbf{x}^{\prime}- \mathbf{x}\|_{2}}\right\rangle\leq\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2} }{2}\right]-2\mathbb{P}_{\phi_{\|\cdot\|_{\infty}\leq\rho}}\left[\left\langle Z ^{\prime},\,\frac{\mathbf{x}-\mathbf{x}^{\prime}}{\|\mathbf{x}-\mathbf{x}^{ \prime}\|_{2}}\right\rangle\geq\frac{\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}}{2 }\right]$ $$

Denote $W=\left\langle Z,\,\frac{\mathbf{x}^{\prime}-\mathbf{x}}{\|\mathbf{x}^{\prime}
-\mathbf{x}\|_{2}}\right\rangle$ and $W^{\prime}=\left\langle Z^{\prime},\,\frac{\mathbf{x}-\mathbf{x}^{\prime}}{\|
\mathbf{x}-\mathbf{x}^{\prime}\|_{2}}\right\rangle$. Since $\frac{\mathbf{x}^{\prime}-\mathbf{x}}{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}$ and $\frac{\mathbf{x}-\mathbf{x}^{\prime}}{\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}}$ are normalized vectors, $W$ and $W^{\prime}$ follow the one-dimensional distribution projected onto a plane along some direction from the truncated multivariate Gaussian, which is symmetrically centered at the origin. Therefore, by symmetry,

$$ $\displaystyle I$ $\displaystyle=2\mathbb{P}\left[W\leq\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{ 2}}{2}\right]-2\mathbb{P}\left[W^{\prime}\geq\frac{\|\mathbf{x}-\mathbf{x}^{ \prime}\|_{2}}{2}\right]$ $\displaystyle=2\mathbb{P}\left[W\leq-\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_ {2}}{2}\right]+2\mathbb{P}\left[-\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}} {2}\leq W\leq\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}{2}\right]-2\mathbb{ P}\left[W^{\prime}\geq\frac{\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}}{2}\right]$ $\displaystyle=2\mathbb{P}\left[-\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}{ 2}\leq W\leq\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}{2}\right]$ $$

As we later upper bound the integration by the peak of this distribution, we know by the geometry of $\ell_{\infty}$-ball that the projection onto the diagonal yields the highest peak, and that is when $W=\frac{1}{\sqrt{d}}\sum_{i=1}^{d}Z_{i}$ for $Z_{i}$ being the marginal of $Z$ that follows the truncated Gaussian distribution on $[-\rho,\rho]$ by Lemma 13 (ii).
And further by Lemma 2 (v) in (Chen et al., ), $\frac{1}{\sqrt{d}}$ is also a truncated Gaussian whose PDF is $\phi_{[-\frac{\rho}{\sqrt{d}},\frac{\rho}{\sqrt{d}}]}(w;0,\frac{\rho^{2}}{d})$.
As a result, $W$ is the sum of independent identically distributed (i.i.d.) truncated Gaussian variables. By Theorem 3 in (Chen et al., ) and E.q. (4.2) in (Birnbaum and Andrews, ) we know the sum of truncated Gaussian variables converges to a normal distribution for large $d$. As a result, $W\sim\left(\sum_{i=1}^{d}\mathrm{Var}\left[Z_{i}\right]\right)\mathcal{N}\left
(0,1\right)$. Knowing from the CDF of truncated Gaussian that $\forall\ i\in[d]$, $\mathrm{Var}\left[Z_{i}\right]=\frac{\sigma^{2}}{d}\left[1-\frac{\phi(1)+\phi(
-1)}{\Phi(1)-\Phi(-1)}-\left(\frac{\phi(1)-\phi(-1)}{\Phi(1)-\Phi(-1)}\right)^
{2}\right]=0.7089\frac{\rho^{2}}{d}$, we have $\left(\sum_{i=1}^{d}\mathrm{Var}\left[Z_{i}\right]\right)=0.7089\rho^{2}$

$$ $\displaystyle\mathbb{P}\left[-\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}{2} \leq W\leq\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}{2}\right]$ $\displaystyle=\frac{1}{\sqrt{2\pi}\sqrt{0.7089}\rho}\int_{-\frac{\|\mathbf{x}^ {\prime}-\mathbf{x}\|_{2}}{2}}^{\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}{ 2}}\exp\{-\frac{w^{2}}{2\times 0.7089\rho^{2}}\}dw$ $$

Furthermore, since the PDF takes its peak at $w=0$, we have

$$ $\displaystyle I$ $\displaystyle\leq 2\times\frac{2}{\sqrt{2\pi}\rho}\int_{-\frac{\|\mathbf{x}^{ \prime}-\mathbf{x}\|_{2}}{2}}^{\frac{\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}{2 }}dw$ $\displaystyle=\frac{4\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}}{\sqrt{2\pi}\rho}$ $$

Therefore,

$$ $\displaystyle\|\nabla f_{\rho}(\mathbf{x})-\nabla f_{\rho}(\mathbf{x}^{\prime} )\|_{2}$ $\displaystyle\leq LI$ $\displaystyle\leq\frac{2L}{\rho}\|\mathbf{x}^{\prime}-\mathbf{x}\|_{2}.$ $$

∎

See 1

###### Proof.

The proof of this lemma relies on inductively applying Lemma 14 and we provide formal proof by induction.

(i) The base case $p=1$ holds directly by Lemma 14 (ii). Then we state the hypothesis that for $p=k$, $f_{\rho}^{k}$ is convex and $L$-Lipschitz with respect to the $\ell_{2}$ norm. For the induction step, we have, by definition, $f_{\rho}^{k+1}=S_{\rho}[f_{\rho}^{k}]$ where $f_{\rho}^{k}$ is convex and $L$-Lipschitz with respect to the $\ell_{2}$ norm by our hypothesis, with which $f_{\rho}^{k}$ satisfies the condition of Lemma 14. Then by Lemma 14 (ii), $f_{\rho}^{k+1}$ is convex and $L$-Lipschitz with respect to the $\ell_{2}$ norm.

(ii) The base case $p=1$ holds directly by Lemma 14 (iii). Then we state the hypothesis that for $p=k$, $f(\mathbf{x})\leq f_{\rho}^{k}(\mathbf{x})\leq f(\mathbf{x})+\frac{5k}{4}L\rho
\sqrt{d}$ holds. From the result of (i), we know that $f_{\rho}^{k}$ satisfies the condition of Lemma 14. Therefore, applying 14 (iii) to the function $f_{\rho}^{k}(\mathbf{x})$ we have for the lower bound

$$ $f_{\rho}^{k+1}(\mathbf{x})\geq f_{\rho}^{k}(\mathbf{x})\geq f(\mathbf{x})$ $$

and for the lower bound

$$ $f_{\rho}^{k+1}(\mathbf{x})\leq f_{\rho}^{k}(\mathbf{x})+\frac{5}{4}L\rho\sqrt{ d}\leq f(\mathbf{x})+\frac{5k}{4}L\rho\sqrt{d}+\frac{5}{4}L\rho\sqrt{d}=f( \mathbf{x})+\frac{5(k+1)}{4}L\rho\sqrt{d}$ $$

which completes the induction step.

(iii) The base case $p=1$ holds for $i=0$ by Lemma 14 (ii) and for $i=1$ by Lemma 14 (iv). Now we state the inductive hypothesis that for $p=k$, it holds that $\forall\ \mathbf{x},\mathbf{x}^{\prime}\in\mathbb{R}$,

$$ $\forall\ i\in[k],\ \|\nabla^{i}f_{\rho}^{k}(\mathbf{x})-\nabla^{i}f_{\rho}^{k} (\mathbf{x}^{\prime})\|\leq\left(\frac{2}{\rho}\right)^{i}L\|\mathbf{x}- \mathbf{x}^{\prime}\|.$ $$

That is, $\forall\ i\in[k]$, the function $\nabla^{i}f_{\rho}^{k}$ is $\left(\left(\frac{2}{\rho}\right)^{i}L\right)$-Lipschitz.
Then for $p=k+1$, $\forall i\in[k+1]$,

$$ $\displaystyle\|\nabla^{i}f_{\rho}^{k+1}(\mathbf{x})-\nabla^{i}f_{\rho}^{k+1}( \mathbf{x}^{\prime})\|$ $\displaystyle=\|\nabla^{i}S_{\rho}[f_{\rho}^{k}](\mathbf{x})-\nabla^{i}S_{\rho }[f_{\rho}^{k}](\mathbf{x}^{\prime})\|$ $\displaystyle=\|S_{\rho}[\nabla^{i}f_{\rho}^{k}](\mathbf{x})-S_{\rho}[\nabla^{ i}f_{\rho}^{k}](\mathbf{x}^{\prime})\|$ $\displaystyle=\|\mathbb{E}_{V}[\nabla^{i}f_{\rho}^{k}(\mathbf{x}+\rho V)]- \mathbb{E}_{V}[\nabla^{i}f_{\rho}^{k}(\mathbf{x}^{\prime}+\rho V)]\|$ $\displaystyle=\|\mathbb{E}_{V}[\nabla^{i}f_{\rho}^{k}(\mathbf{x}+\rho V)- \nabla^{i}f_{\rho}^{k}(\mathbf{x}^{\prime}+\rho V)]\|$ $\displaystyle\leq\mathbb{E}_{V}[\|\nabla^{i}f_{\rho}^{k}(\mathbf{x}+\rho V)- \nabla^{i}f_{\rho}^{k}(\mathbf{x}^{\prime}+\rho V)\|]$ $$

where the first equality holds by definition, the second equality by the fact that expectation and derivative commute for differentiable functions, and the last inequality by the Jensen’s.

For $i<k+1$, we can directly apply Lemma 14 (iv), with the hypothesis as the condition, on the function $\nabla^{i}f_{\rho}^{k}$, to establish the result that $\nabla^{i}f_{\rho}^{k}$ is smooth with parameter $\left(\frac{2}{\rho}\right)^{i}L$. Therefore,

$$ $\displaystyle\|\nabla^{i}f_{\rho}^{k+1}(\mathbf{x})-\nabla^{i}f_{\rho}^{k+1}( \mathbf{x}^{\prime})\|$ $\displaystyle\leq\mathbb{E}_{V}[\|\nabla^{i}f_{\rho}^{k}(\mathbf{x}+\rho V)- \nabla^{i}f_{\rho}^{k}(\mathbf{x}^{\prime}+\rho V)\|]$ $\displaystyle\leq\mathbb{E}_{V}\left[\left(\frac{2}{\rho}\right)^{i}L\|\mathbf {x}-\mathbf{x}^{\prime}\|\right]$ $\displaystyle=\left(\frac{2}{\rho}\right)^{i}L\|\mathbf{x}-\mathbf{x}^{\prime}\|$ $$

For $i=k+1$, we have from our $i<k+1$ case that the function $\nabla^{k}f_{\rho}^{k+1}$ is $\left(\left(\frac{2}{\rho}\right)^{k}L\right)$-Lipschitz. We can therefore apply Lemma 14 (iv) on $\nabla^{k}f_{\rho}^{k+1}$ and claim that it’s also smooth with parameter $\frac{2}{\rho}\cdot\left(\frac{2}{\rho}\right)^{k}L=\left(\frac{2}{\rho}\right
)^{k+1}L$. That is,

$$ $\displaystyle\big{\|}\nabla\left[\nabla^{k}f_{\rho}^{k+1}\right](\mathbf{x})- \nabla\left[\nabla^{k}f_{\rho}^{k+1}\right](\mathbf{x}^{\prime})\big{\|}\leq \left(\frac{2}{\rho}\right)^{k+1}L\|\mathbf{x}-\mathbf{x}^{\prime}\|,$ $$

which completes the proof.
∎

###### Lemma 13 ( ℓ ∞ subscript ℓ \ell_{\infty} roman_ℓ start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT -Ball Truncated Gaussian and Its Marginal Distribution) .

###### Proof.

###### Lemma 14 (Properties of Truncated Gaussian Smoothing) .

###### Proof.

###### Proof.

### A.2 Properties of the Constructed Hard Function

See 2

###### Proof.

(1) For convexity, by definition we have

$$ $\displaystyle g_{t}(\mathbf{x})=\max_{1\leq k\leq t}r_{k}(\mathbf{x})$ $\displaystyle where$ $\displaystyle\forall\ k\in[T],r_{k}(\mathbf{x})=\xi_{k}\left\langle\mathbf{e}_ {\alpha(k)},\,\mathbf{x}\right\rangle-(k-1)\delta,$ $$

Since $r_{k}(\mathbf{x})$ is linear in $\mathbf{x}$, $r_{k}(\mathbf{x})$ is convex. Then $g_{t}(\mathbf{x})$ is the maximum of convex functions which is also convex.

(2) To show Lipschitzness, $\forall\ \mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$, without the loss of generality, denote

$$ $\displaystyle k_{1}=\operatorname*{arg\,max}_{1\leq k\leq t}r_{k}(\mathbf{x})$ $\displaystyle k_{2}=\operatorname*{arg\,max}_{1\leq k\leq t}r_{k}(\mathbf{y}).$ $$

Therefore,

$$ $\displaystyle g_{t}\left(\mathbf{x}\right)=\xi_{k_{1}}x_{\alpha\left(k_{1} \right)}-(k_{1}-1)\delta$ $\displaystyle g_{t}\left(\mathbf{y}\right)=\xi_{k_{2}}y_{\alpha\left(k_{2} \right)}-(k_{2}-1)\delta.$ $$

Since

$$ $\displaystyle g_{t}\left(\mathbf{y}\right)$ $\displaystyle=\xi_{k_{2}}y_{\alpha\left(k_{2}\right)}-(k_{2}-1)\delta$ $\displaystyle=\max_{1\leq k\leq t}\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\, \mathbf{x}\right\rangle-(k-1)\delta$ $\displaystyle\geq\xi_{k_{1}}y_{\alpha\left(k_{1}\right)}-(k_{1}-1)\delta,$ $$

we have

$$ $\displaystyle g_{t}\left(\mathbf{x}\right)-g_{t}\left(\mathbf{y}\right)$ $\displaystyle\leq\left(\xi_{k_{1}}x_{\alpha\left(k_{1}\right)}-(k_{1}-1)\delta \right)-\left(\xi_{k_{1}}y_{\alpha\left(k_{1}\right)}-(k_{1}-1)\delta\right)$ $\displaystyle\leq\lvert x_{\alpha\left(k_{1}\right)}-y_{\alpha\left(k_{1} \right)}\rvert$ $\displaystyle\leq\max_{1\leq i\leq d}\lvert x_{i}-y_{i}\rvert$ $\displaystyle=\big{\|}\mathbf{x}-\mathbf{y}\big{\|}_{\infty}$ $\displaystyle\leq\big{\|}\mathbf{x}-\mathbf{y}\big{\|}_{2},$ $$

where the last two inequalities show Lipschitzness in $\ell_{\infty}$ and $\ell_{2}$ norm respectively.
∎

See 3

###### Proof.

The proof follows directly from that for Lemma 1.
∎

See 4

###### Proof.

(i) It is shown in (Nesterov et al., , Section 4.2.2) that $\frac{\sigma}{q}\big{\|}\mathbf{x}\big{\|}^{q}$ is uniformly convex with degree $q$ and parameter $\sigma$. By Lemma 3 (i), $G_{T}$ is convex, therefore $f$ is also convex, so that $\forall\ \mathbf{x},\mathbf{y}\in\mathbb{R}$, $\left\langle\nabla f(\mathbf{x})-\nabla f(\mathbf{y}),\,\mathbf{x}-\mathbf{y}
\right\rangle\geq 0$. Therefore, by Definition 3, $\left\langle\nabla(\frac{\sigma}{q}\big{\|}\mathbf{x}\big{\|}^{q})-\nabla(
\frac{\sigma}{q}\big{\|}\mathbf{y}\big{\|}^{q}),\,\mathbf{x}-\mathbf{y}\right
\rangle\geq\sigma\|\mathbf{x}-\mathbf{y}\|^{q}$. Adding them together we get $\left\langle\nabla F(\mathbf{x})-\nabla F(\mathbf{y}),\,\mathbf{x}-\mathbf{y}
\right\rangle\geq\sigma\|\mathbf{x}-\mathbf{y}\|^{q}$, which shows that $F(\mathbf{x})$ is uniformly convex function with degree $q$ and modulus $\sigma>0$.

(ii) From Lemma 3 (iii) and Definition 1, we know that $f$ is $p^{th}$-order smooth with parameter $L_{p}=\beta\left(\frac{2}{\rho}\right)^{p}$, $\forall\ p\in\mathbb{Z}^{+}$, i.e., $\forall\ \mathbf{x},\mathbf{y}\in\mathcal{Q}\subset\mathbb{R}^{d}$,

$$ $\displaystyle\|\nabla^{p}f(\mathbf{x})-\nabla^{p}f(\mathbf{y})\|\leq\beta\left (\frac{2}{\rho}\right)^{p}\|\mathbf{x}-\mathbf{y}\|.$ $$

Also, $\nabla^{p-1}f$ is $\beta\left(\frac{2}{\rho}\right)^{p-1}$-Lipschitz, which implies that $\forall\ \mathbf{x}\in\mathbb{R}^{d}$, $\|\nabla^{p}f(\mathbf{x})\|\leq\beta\left(\frac{2}{\rho}\right)^{p-1}$.
Then we have $\forall\ \mathbf{x},\mathbf{y}\in\mathcal{Q}$,

$$ $\displaystyle\|\nabla^{p}f(\mathbf{x})-\nabla^{p}f(\mathbf{y})\|$ $\displaystyle=\|\nabla^{p}f(\mathbf{x})-\nabla^{p}f(\mathbf{y})\|^{\nu}\| \nabla^{p}f(\mathbf{x})-\nabla^{p}f(\mathbf{y})\|^{1-\nu}$ $\displaystyle\leq\beta^{\nu}\|\nabla^{p}f(\mathbf{x})-\nabla^{p}f(\mathbf{y}) \|^{\nu}\left(\|\nabla^{p}f(\mathbf{x})\|+\|\nabla^{p}f(\mathbf{y})\|\right)^{ 1-\nu}$ $\displaystyle\leq\left(\frac{2}{\rho}\right)^{p\nu}\beta^{\nu}\|\mathbf{x}- \mathbf{y}\|^{\nu}\left(2\beta\left(\frac{2}{\rho}\right)^{p-1}\right)^{1-\nu}$ $\displaystyle=\frac{2^{p}\beta}{{\rho}^{p+\nu-1}}\|\mathbf{x}-\mathbf{y}\|^{ \nu}.$ $$

By letting $H=\frac{2^{p+1}\beta}{{\rho}^{p+\nu-1}}$, we can conclude that $f$ is $p^{th}$-order Hölder smooth with parameter $\frac{H}{2}$.

Furthermore, for $d_{q}(\mathbf{x})$, by definition, $\mathcal{Q}=\{\mathbf{x}:\|\mathbf{x}\|_{2}\leq D\}$ for $D\leq\left(\frac{H}{2^{1-\nu}C}\right)^{\frac{1}{q-p-\nu}}$ and $C=\sigma(q-1)\times\cdots\times(q-p)$. As a result,

$$ $\|\nabla^{p+1}d_{q}(\mathbf{x})\|=\sigma(q-1)\times\cdots\times(q-p)\|\mathbf{ x}\|^{q-p-1}\leq C\cdot D^{q-p-1}.$ $$

This indicates that $d_{q}(\mathbf{x})$ is $p^{th}$-order smooth with parameter $C\cdot D^{q-p-1}$, which is equivalent to $\forall\ \mathbf{x},\mathbf{y}\in\mathcal{Q}$,

$$ $\|\nabla^{p}d_{q}(\mathbf{x})-\nabla^{p}d_{q}(\mathbf{y})\|\leq C\cdot D^{q-p- 1}\|\mathbf{x}-\mathbf{y}\|.$ $$

Given that $\|\mathbf{x}-\mathbf{y}\|=\|\mathbf{x}-\mathbf{y}\|^{1-\nu}\|\mathbf{x}-
\mathbf{y}\|^{\nu}\leq(\|\mathbf{x}\|+\|\mathbf{y}\|)^{1-\nu}\|\mathbf{x}-
\mathbf{y}\|^{\nu}\leq(2D)^{1-\nu}\|\mathbf{x}-\mathbf{y}\|^{\nu}$, we have

$$ $\|\nabla^{p}d_{q}(\mathbf{x})-\nabla^{p}d_{q}(\mathbf{y})\|\leq 2^{1-\nu}C \cdot D^{q-p-\nu}\|\mathbf{x}-\mathbf{y}\|^{\nu}\leq\frac{H}{2}\|\mathbf{x}- \mathbf{y}\|^{\nu}.$ $$

That is, $d_{q}(\mathbf{x})$ is $p^{th}$-order Hölder smooth with parameter $\frac{H}{2}$ on domain $\mathcal{Q}$. Since $f$ is also $p^{th}$-order Hölder smooth with parameter $\frac{H}{2}$, we conclude that $F=f+d_{q}$ is $p^{th}$-order Hölder smooth with parameter $H$ on domain $\mathcal{Q}$.

∎

See 5

###### Proof.

Since $F(\mathbf{x})$ is constructed with softmax smoothing, we are now able to characterize it with the properties in Lemma 3. $F(\mathbf{x})$ can be upper bounded using the second inequality of Lemma 3 (ii):

$$ $\displaystyle F(\mathbf{x})$ $\displaystyle=\beta G_{T}(\mathbf{x})+\frac{\sigma}{q}\|\mathbf{x}\|^{q}$ $\displaystyle\leq\beta g_{T}(\mathbf{x})+\frac{5}{4}p\beta\rho\sqrt{d}+\frac{ \sigma}{q}\|\mathbf{x}\|^{q}$ $\displaystyle=\beta\max_{k\in[T]}\left\{\xi_{k}\left\langle\mathbf{e}_{\alpha( k)},\,\mathbf{x}\right\rangle-(k-1)\delta\right\}+\frac{5}{4}p\beta\rho\sqrt{d }+\frac{\sigma}{q}\|\mathbf{x}\|^{q}$ $\displaystyle\leq\beta\max_{k\in[T]}\xi_{k}\left\langle\mathbf{e}_{\alpha(k)}, \,\mathbf{x}\right\rangle+\frac{5}{4}p\beta\rho\sqrt{d}+\frac{\sigma}{q}\| \mathbf{x}\|^{q}.$ $$

$F(\mathbf{x})$ can be lower bounded using the first inequality of Lemma 3 (ii):

$$ $\displaystyle F(\mathbf{x})$ $\displaystyle=\beta G_{T}(\mathbf{x})+\frac{\sigma}{q}\|x\|^{q}$ $\displaystyle\geq\beta g_{T}(\mathbf{x})+\frac{\sigma}{q}\|\mathbf{x}\|^{q}$ $\displaystyle=\beta\max_{k\in[T]}\left\{\xi_{k}\left\langle\mathbf{e}_{\alpha( k)},\,\mathbf{x}\right\rangle-(k-1)\delta\right\}+\frac{\sigma}{q}\|\mathbf{x} \|^{q}$ $\displaystyle\geq\beta\max_{k\in[T]}\xi_{k}\left\langle\mathbf{e}_{\alpha(k)}, \,\mathbf{x}\right\rangle-(T-1)\delta+\frac{\sigma}{q}\|\mathbf{x}\|^{q}.$ $$

∎

See 7

###### Proof.

$$ $\displaystyle F(\mathbf{x}^{\ast})$ $\displaystyle=\min_{\mathbf{x}}F(\mathbf{x})$ $\displaystyle\leq\min_{\mathbf{x}}R(\mathbf{x})+\frac{5}{4}p\beta\rho\sqrt{d}$ $\displaystyle=\min_{\mathbf{x}}\left\{\beta\max_{k\in[T]}\xi_{k}\left\langle \mathbf{e}_{\alpha(k)},\,\mathbf{x}\right\rangle+\frac{\sigma}{q}\|\mathbf{x} \|^{q}\right\}+\frac{5}{4}p\beta\rho\sqrt{d}.$ $$

Define $\gamma=\left|\max_{k\in[T]}\xi_{k}\left\langle\mathbf{e}_{\alpha(k)},\,\mathbf
{x}\right\rangle\right|$. Then by symmetry (Doikov, ),

$$ $\displaystyle\|\mathbf{x}\|^{q}$ $\displaystyle=T^{\frac{q}{2}}\gamma^{q}.$ $$

As a result,

$$ $\displaystyle\min_{\mathbf{x}}R(\mathbf{x})$ $\displaystyle=\min_{\mathbf{x}}\left\{\beta\max_{k\in[T]}\xi_{k}\left\langle \mathbf{e}_{\alpha(k)},\,\mathbf{x}\right\rangle+\frac{\sigma}{q}\|\mathbf{x} \|^{q}\right\}$ $\displaystyle=\min_{\gamma>0}\{-\beta\gamma+\frac{\sigma}{q}T^{\frac{q}{2}} \gamma^{q}\}$ $\displaystyle=-\frac{q-1}{q}\left(\frac{\beta^{q}}{\sigma T^{\frac{q}{2}}} \right)^{\frac{1}{q-1}}.$ $$

Therefore,

$$ $\displaystyle F(\mathbf{x}^{\ast})$ $\displaystyle\leq-\frac{q-1}{q}\left(\frac{\beta^{q}}{\sigma T^{\frac{q}{2}}} \right)^{\frac{1}{q-1}}+\frac{5}{4}p\beta\rho\sqrt{d}.$ $$

Furthermore, for some $\mathbf{x}_{T}$ generated following some algorithm $\mathcal{A}$ along some trajectory, by definition,

$$ $\displaystyle g_{T}(\mathbf{x}_{T})$ $\displaystyle=\left|\left\langle e_{\alpha(T)},\,\mathbf{x}_{T}\right\rangle \right|-(T-1)\delta$ $\displaystyle\geq-(T-1)\delta.$ $$

Therefore,

$$ $\displaystyle F(\mathbf{x}_{T})$ $\displaystyle=f(\mathbf{x}_{T})+\frac{\sigma}{q}\|\mathbf{x}_{T}\|^{q}$ $\displaystyle\geq f(\mathbf{x}_{T})$ $\displaystyle=\beta G_{T}(\mathbf{x}_{T})$ $\displaystyle\geq\beta g_{T}(\mathbf{x}_{T})$ $\displaystyle\geq-\beta(T-1)\delta.$ $$

Given the upper bound on $F(\mathbf{x}^{\ast})$, we have

$$ $\displaystyle F(\mathbf{x}_{T})-F(\mathbf{x}^{\ast})$ $\displaystyle\geq-\beta(T-1)\delta-\frac{5}{4}p\beta\rho\sqrt{d}+\frac{q-1}{q} \left(\frac{\beta^{q}}{\sigma T^{\frac{q}{2}}}\right)^{\frac{1}{q-1}}.$ $$

∎

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

## Appendix B Proof for Technical Lemmas in Section 5

See 8

###### Proof.

(i) By definition, $f$ is a scaling and rotation of $\tilde{f}$. Since $\mathbf{v}_{1},\cdots,\mathbf{v}_{\tilde{T}}$, we can write for $V=[\mathbf{v}_{1},\cdots,\mathbf{v}_{\tilde{T}}]$, $f(\mathbf{x})=\frac{H}{2^{p+\nu+1}(p+\nu-1)!}\tilde{f}(V\mathbf{x})$. Therefore,

$$ $\displaystyle\mathbf{y}$ $\displaystyle=\operatorname*{arg\,min}_{\mathbf{x}}\tilde{f}(\mathbf{x})$ $\displaystyle=V\operatorname*{arg\,min}_{\mathbf{x}}\tilde{f}(V\mathbf{x})$ $\displaystyle=V\operatorname*{arg\,min}_{\mathbf{x}}f(\mathbf{x})$ $\displaystyle=V\mathbf{x}^{\ast}.$ $$

(ii) This can be shown in the same way as (Arjevani et al., , Lemma 6).
∎

See 9

###### Proof.

(i) The proof is similar to that for Lemma 4 (i).

(ii) Without the loss of generality, let the basis that defines $f$ be the standard basis. $\forall\ i\in[\tilde{T}]$, denote $\mathbf{e}_{i}$ the $i^{th}$ vector in the standard basis. Denote function $g(x)=\frac{1}{p+\nu}|x|^{p+\nu}$. $g^{(p)}(x)$, the $p^{th}$-order derivative of $g(x)$ is $(p+\nu-1)!x^{\nu}$ if $p$ is odd, $(p+\nu-1)!|x|^{\nu}$ is even. Let $\mathbf{d}_{i}=\mathbf{e}_{i}-\mathbf{e}_{i+1}$, then

$$ $\displaystyle f(\mathbf{x})=\frac{H}{2^{p+\nu+1}(p+\nu-1)!}\left(\frac{1}{p+ \nu}\sum_{i=1}^{\tilde{T}}g(\left\langle\mathbf{d}_{i},\,\mathbf{x}\right \rangle)-\gamma x_{1}\right)+\frac{\sigma}{q}\|\mathbf{x}\|^{q}$ $$

Since $q<p+\nu$, then $q\leq p$. Therefore, $\forall\ \mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\|\nabla^{p}f(\mathbf{x})-\nabla^{p}f(\mathbf{y})\|$ $\displaystyle=\frac{H}{2^{p+\nu+1}(p+\nu-1)!}\big{\|}\sum_{i=1}^{\tilde{T}} \left[g^{(p)}(\left\langle\mathbf{d}_{i},\,\mathbf{x}\right\rangle)-g^{(p)}( \left\langle\mathbf{d}_{i},\,\mathbf{y}\right\rangle)\right][\mathbf{d}_{i}]^{ p}\big{\|}$ $\displaystyle\leq\frac{H(p+\nu-1)!}{2^{p+\nu+1}(p+\nu-1)!}\big{\|}\sum_{i=1}^{ \tilde{T}}\left|\left\langle\mathbf{d}_{i},\,\mathbf{x}-\mathbf{y}\right \rangle\right|^{\nu}[\mathbf{d}_{i}]^{p}\big{\|}$ $\displaystyle\leq\frac{H}{2^{p+\nu+1}}\sqrt{2}\|\mathbf{x}-\mathbf{y}\|^{\nu} \big{\|}\sum_{i=1}^{\tilde{T}}[\mathbf{d}_{i}]^{p}\big{\|}$ $\displaystyle\leq\frac{H}{2^{p+\nu+1}}\sqrt{2}\|\mathbf{x}-\mathbf{y}\|^{\nu}2 ^{p}$ $\displaystyle\leq H\|\mathbf{x}-\mathbf{y}\|^{\nu}.$ $$

∎

###### Lemma 15 .

For $\mathbf{y}=\operatorname*{arg\,min}_{\mathbf{x}}\tilde{f}(\mathbf{x})$,

- (i)
$y_{1}\geq y_{2}\geq\cdots\geq y_{\tilde{T}}\geq 0$.
- (ii)
$y_{t+1}=y_{t}-\left(\gamma-\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j=1}^{t}y_{
j}\right)^{\frac{1}{p+\nu-1}}.$
- (iii)
$\sum_{i=1}^{\tilde{T}}y_{i}=\frac{\gamma}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}$.

###### Proof.

(i) The proof is similar to (Arjevani et al., , Lemma 1), relying on the fact that $\tilde{f}$ is strictly convex, which holds true for our higher-order construction as well, since the function is uniformly convex.

(ii)

$$ $\displaystyle\nabla\tilde{f}(y)=\left[\begin{matrix}\left|y_{1}-y_{2}\right|^{ p+\nu-2}(y_{1}-y_{2})-\gamma+\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{1}\\ \left|y_{2}-y_{1}\right|^{p+\nu-2}(y_{2}-y_{1})+\left|y_{2}-y_{3}\right|^{p+ \nu-2}(y_{2}-y_{3})+\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{2}\\ \vdots\\ \left|y_{\tilde{T}-1}-y_{\tilde{T}-2}\right|^{p+\nu-2}(y_{\tilde{T}-1}-y_{ \tilde{T}-2})+\left|y_{\tilde{T}-1}-y_{\tilde{T}}\right|^{p+\nu-2}(y_{\tilde{T }-1}-y_{\tilde{T}})+\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{\tilde{T}-1}\\ \left|y_{\tilde{T}}-y_{\tilde{T}-1}\right|^{p+\nu-2}(y_{\tilde{T}}-y_{\tilde{T }-1})+\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{\tilde{T}}\end{matrix}\right]$ $$

Given that $y_{1}\geq y_{2}\geq\cdots\geq y_{\tilde{T}}\geq 0$, we have $\forall i\in[\tilde{T}-1],\ \left|y_{i}-y_{i+1}\right|=y_{i}-y_{i+1}$. Therefore, with $\nabla\tilde{f}(y)=0$, we have

$$ $\displaystyle(y_{1}-y_{2})^{p+\nu-1}$ $\displaystyle=\gamma-\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{1},$ (2) $\displaystyle(y_{i-1}-y_{i})^{p+\nu-1}$ $\displaystyle=(y_{i}-y_{i+1})^{p+\nu-1}+\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{i },\quad 2\leq i\leq\tilde{T}-1,$ (3) $\displaystyle(y_{\tilde{T}-1}-y_{\tilde{T}})^{p+\nu-1}$ $\displaystyle=\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{\tilde{T}}.$ (4) $$

Summing Eq. (2) and (3), we have

$$ $\displaystyle(y_{i}-y_{i+1})^{p+\nu-1}=\gamma-\tilde{\sigma}\|\mathbf{y}\|^{q- 2}\sum_{j=1}^{i}y_{j},$ $$

which completes the proof.

(iii) We know from part (ii) that

$$ $\displaystyle(y_{\tilde{T}-1}-y_{\tilde{T}})^{p+\nu-1}=\gamma-\tilde{\sigma}\| \mathbf{y}\|^{q-2}\sum_{j=1}^{\tilde{T}-1}y_{j}.$ $$

Grouping this with Eq. (4), we have $\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{\tilde{T}}=\gamma-\tilde{\sigma}\|\mathbf
{y}\|^{q-2}\sum_{j=1}^{\tilde{T}-1}y_{j}$, which yields the desired result.
∎

See 11

###### Proof.

By Lemma 15 (iii) and Lemma 10 (ii),

$$ $\displaystyle\|\mathbf{y}\|^{2}_{2}$ $\displaystyle\leq\|\mathbf{y}\|_{1}\|\mathbf{y}\|_{\infty}$ $\displaystyle=\max_{i\in[\tilde{T}]}\left|y_{i}\right|\times\sum_{i=1}^{d}y_{i}$ $\displaystyle=y_{1}\times\sum_{i=1}^{\tilde{T}}y_{i}$ $\displaystyle\leq\left(\gamma^{\frac{1}{p+\nu-1}}+\sqrt{\frac{2\gamma^{\frac{p +\nu}{p+\nu-1}}}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}}\right)\times\frac{\gamma }{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}$ $\displaystyle=\left(1+\sqrt{\frac{2\gamma^{\frac{p+\nu-2}{p+\nu-1}}}{\tilde{ \sigma}\|\mathbf{y}\|^{q-2}}}\right)\frac{\gamma^{\frac{p+\nu}{p+\nu-1}}}{ \tilde{\sigma}\|\mathbf{y}\|^{q-2}}$ $$

Let $\gamma\geq\left(3\tilde{\sigma}\|\mathbf{y}\|^{q-2}\right)^{\frac{p+\nu-1}{p+
\nu-2}}$, then we have $\frac{\gamma^{\frac{p+\nu-2}{p+\nu-1}}}{3\tilde{\sigma}\|\mathbf{y}\|^{q-2}}\geq
1$ and moreover $\sqrt{\frac{\gamma^{\frac{p+\nu-2}{p+\nu-1}}}{3\tilde{\sigma}\|\mathbf{y}\|^{q
-2}}}\geq 1$, so that we can merge the terms as follows:

$$ $\displaystyle\|\mathbf{y}\|^{2}$ $\displaystyle\leq\left(\sqrt{\frac{\gamma^{\frac{p+\nu-2}{p+\nu-1}}}{3\tilde{ \sigma}\|\mathbf{y}\|^{q-2}}}+\sqrt{\frac{2\gamma^{\frac{p+\nu-2}{p+\nu-1}}}{ \tilde{\sigma}\|\mathbf{y}\|^{q-2}}}\right)\frac{\gamma^{\frac{p+\nu}{p+\nu-1} }}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}$ $\displaystyle=\left(\sqrt{\frac{1}{3}+\sqrt{2}}\right)\frac{\gamma^{\frac{p+ \nu-2}{2({p+\nu-1})}+\frac{p+\nu}{p+\nu-1}}}{\tilde{\sigma}^{\frac{3}{2}}\| \mathbf{y}\|^{\frac{3(q-2)}{2}}}$ $\displaystyle\leq\frac{2\gamma^{\frac{3(p+\nu)-2}{2(p+\nu-1)}}}{\tilde{\sigma} ^{\frac{3}{2}}\|\mathbf{y}\|^{\frac{3(q-2)}{2}}}.$ $$

We can solve for $\|\mathbf{y}\|\leq\left(\frac{2\gamma^{\frac{3(p+\nu)-2}{2(p+\nu-1)}}}{\tilde{
\sigma}^{\frac{3}{2}}}\right)^{\frac{2}{3q-2}}=\frac{2^{\frac{2}{3q-2}}\gamma^
{\frac{3(p+\nu)-2}{(p+\nu-1)(3q-2)}}}{\tilde{\sigma}^{\frac{3}{3q-2}}}$.
∎

See 10

###### Proof.

(i) By Lemma 15 (ii), $\forall\ i\in[\tilde{T}]$

$$ $\displaystyle y_{i}$ $\displaystyle=y_{i-1}-\left(\gamma-\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j=1 }^{i-1}y_{j}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle\geq y_{i-1}-\gamma^{\frac{1}{p+\nu-1}}$ $\displaystyle\geq y_{1}-(i-1)\gamma^{\frac{1}{p+\nu-1}},$ $$

in which the first inequality follows from Lemma 15 (i) that $\forall i\in[\tilde{T}]$, $y_{i}\geq 0$, and the second inequality follows from applying the first inequality recursively.

(ii) It follows from part (i) that

$$ $\displaystyle\sum_{i=1}^{\tilde{T}}y_{i}\geq\sum_{i=1}^{\tilde{T}}\max\left\{0 ,y_{1}-(i-1)\gamma^{\frac{1}{p+\nu-1}}\right\}.$ $$

For $\tilde{T}=\left\lfloor\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1}}}+1\right\rfloor
\leq\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1}}}+1$, we always have $y_{1}-(\tilde{T}-1)\gamma^{\frac{1}{p+\nu-1}}\geq 0$. Consequently, $\forall i\in[\tilde{T}]$, $y_{1}-(i-1)\gamma^{\frac{1}{p+\nu-1}}\geq 0$. Therefore,

$$ $\displaystyle\sum_{i=1}^{\tilde{T}}y_{i}$ $\displaystyle\geq\sum_{i=1}^{\tilde{T}}y_{1}-(i-1)\gamma^{\frac{1}{p+\nu-1}}$ $\displaystyle=\sum_{i=1}^{\left\lfloor y_{1}/\gamma^{\frac{1}{p+\nu-1}}+1 \right\rfloor}y_{1}-(i-1)\gamma^{\frac{1}{p+\nu-1}}$ $\displaystyle=\left\lfloor\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1}}}+1\right \rfloor\cdot y_{1}-\gamma^{\frac{1}{p+\nu-1}}\cdot\frac{\left\lfloor\frac{y_{1 }}{\gamma^{\frac{1}{p+\nu-1}}}+1\right\rfloor\left(\left\lfloor\frac{y_{1}}{ \gamma^{\frac{1}{p+\nu-1}}}+1\right\rfloor-1\right)}{2}$ $\displaystyle\geq\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1}}}\cdot y_{1}-\gamma^{ \frac{1}{p+\nu-1}}\cdot\frac{\left(\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1}}}+1 \right)\left(\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1}}}+1-1\right)}{2}$ $\displaystyle=\frac{y_{1}^{2}}{\gamma^{\frac{1}{p+\nu-1}}}-\frac{y_{1}^{2}}{2 \gamma^{\frac{1}{p+\nu-1}}}-\frac{y_{1}}{2}$ $\displaystyle=\frac{y_{1}}{2}\left(\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1}}}-1 \right).$ $$

Combining with Lemma 15 (iii) that $\sum_{i=1}^{\tilde{T}}y_{i}=\frac{\gamma}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}$, we have

$$ $\displaystyle\frac{\gamma}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}=\sum_{i=1}^{ \tilde{T}}y_{i}\geq\frac{y_{1}}{2}\left(\frac{y_{1}}{\gamma^{\frac{1}{p+\nu-1} }}-1\right).$ $$

Equivalently,

$$ $\displaystyle y_{1}^{2}-\gamma^{\frac{1}{p+\nu-1}}y_{1}-\frac{2\gamma^{\frac{p +\nu}{p+\nu-1}}}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}\leq 0.$ $$

By the quadratic formula, we have

$$ $\displaystyle y_{1}$ $\displaystyle\leq\frac{\gamma^{\frac{1}{p+\nu-1}}+\sqrt{\gamma^{\frac{2}{p+\nu -1}}+\frac{8\gamma^{\frac{p+\nu}{p+\nu-1}}}{\tilde{\sigma}\|\mathbf{y}\|^{q-2} }}}{2}$ $\displaystyle\leq\frac{\gamma^{\frac{1}{p+\nu-1}}+\sqrt{\gamma^{\frac{2}{p+\nu -1}}}+\sqrt{\frac{8\gamma^{\frac{p+\nu}{p+\nu-1}}}{\tilde{\sigma}\|\mathbf{y} \|^{q-2}}}}{2}$ $\displaystyle=\gamma^{\frac{1}{p+\nu-1}}+\sqrt{\frac{2\gamma^{\frac{p+\nu}{p+ \nu-1}}}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}}$ $$

(iii) Since $\sum_{i=1}^{\tilde{T}}y_{i}=\frac{\gamma}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}$, $\exists\ t_{0}\in[\tilde{T}]$ such that $\sum_{i=1}^{t_{0}}y_{i}>(1-\frac{1}{2^{p+\nu-1}})\frac{\gamma}{\tilde{\sigma}
\|\mathbf{y}\|^{q-2}}$ and $\forall t<t_{0}$, $\sum_{i=1}^{t}y_{i}\leq(1-\frac{1}{2^{p+\nu-1}})\frac{\gamma}{\tilde{\sigma}\|
\mathbf{y}\|^{q-2}}$. Then $\forall\ i<t_{0}$, we can merge the terms in Lemma 15 (ii) as follows:

$$ $\displaystyle y_{i+1}$ $\displaystyle=y_{i}-\left(\gamma-\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j=1}^ {i}y_{j}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle\leq y_{i}-\left(\gamma-(1-\frac{1}{2^{p+\nu-1}})\gamma\right)^{ \frac{1}{p+\nu-1}}$ $\displaystyle=y_{i}-\frac{\gamma^{\frac{1}{p+\nu-1}}}{2}.$ $$

Applying this relation recursively, we have

$$ $\displaystyle y_{t_{0}}\leq y_{t_{0}-1}-\frac{\gamma^{\frac{1}{p+\nu-1}}}{2} \leq\cdots\leq y_{1}-(t_{0}-1)\frac{\gamma^{\frac{1}{p+\nu-1}}}{2}.$ $$

Given that $y_{t_{0}}\geq 0$, this yields $y_{1}\geq(t_{0}-1)\frac{\gamma^{\frac{1}{p+\nu-1}}}{2}$.

Now we characterize $t_{0}$. By definition, we have $\sum_{i=1}^{t_{0}}y_{i}>(1-\frac{1}{2^{p+\nu-1}})\frac{\gamma}{\tilde{\sigma}
\|\mathbf{y}\|^{q-2}}$. In the meantime,

$$ $\displaystyle\sum_{i=1}^{t_{0}}y_{i}$ $\displaystyle\leq\sum_{i=1}^{t_{0}}y_{1}$ $\displaystyle=t_{0}y_{1}$ $\displaystyle\leq t_{0}\left(\gamma^{\frac{1}{p+\nu-1}}+\sqrt{\frac{2\gamma^{ \frac{p+\nu}{p+\nu-1}}}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}}\right),$ $$

where the first inequality follows from Lemma 15 (i) and the second from part (ii). Together, we have $(1-\frac{1}{2^{p+\nu-1}})\frac{\gamma}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}<t_{
0}\left(\gamma^{\frac{1}{p+\nu-1}}+\sqrt{\frac{2\gamma^{\frac{p+\nu}{p+\nu-1}}
}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}}\right)$, from which we solve for

$$ $\displaystyle t_{0}>\frac{(2^{p+\nu-1}-1)\gamma^{\frac{p+\nu-2}{p+\nu-1}}}{2^{ p+\nu-1}\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}+\sqrt{2\tilde{\sigma}\gamma^{ \frac{p+\nu-2}{p+\nu-1}}\|\mathbf{y}\|^{q-2}}\right)}$ $$

Plugging this characterization of $t_{0}$ back in,

$$ $\displaystyle y_{1}$ $\displaystyle\geq(t_{0}-1)\frac{\gamma^{\frac{1}{p+\nu-1}}}{2}$ $\displaystyle>\left(\frac{(2^{p+\nu-1}-1)\gamma^{\frac{p+\nu-2}{p+\nu-1}}}{2^{ p+\nu-1}\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}+\sqrt{2\tilde{\sigma}\gamma^{ \frac{p+\nu-2}{p+\nu-1}}\|\mathbf{y}\|^{q-2}}\right)}-1\right)\frac{\gamma^{ \frac{1}{p+\nu-1}}}{2}$ $\displaystyle=\frac{(2^{p+\nu-1}-1)\gamma}{2^{p+\nu+1}\left(\tilde{\sigma}\| \mathbf{y}\|^{q-2}+\sqrt{2\tilde{\sigma}\gamma^{\frac{p+\nu-2}{p+\nu-1}}\| \mathbf{y}\|^{q-2}}\right)}-\frac{\gamma^{\frac{1}{p+\nu-1}}}{2}.$ $$

Finally, plugging this into the result from part (i), $\forall i\in[\tilde{T}]$,

$$ $\displaystyle y_{i}$ $\displaystyle\geq y_{1}-(i-1)\gamma^{\frac{1}{p+\nu-1}}$ $\displaystyle\geq\frac{(2^{p+\nu-1}-1)\gamma}{2^{p+\nu+1}\left(\tilde{\sigma} \|\mathbf{y}\|^{q-2}+\sqrt{2\tilde{\sigma}\gamma^{\frac{p+\nu-2}{p+\nu-1}}\| \mathbf{y}\|^{q-2}}\right)}-\frac{\gamma^{\frac{1}{p+\nu-1}}}{2}-(i-1)\gamma^{ \frac{1}{p+\nu-1}}$ $\displaystyle=\frac{(2^{p+\nu-1}-1)\gamma}{2^{p+\nu+1}\left(\tilde{\sigma}\| \mathbf{y}\|^{q-2}+\sqrt{2\tilde{\sigma}\gamma^{\frac{p+\nu-2}{p+\nu-1}}\| \mathbf{y}\|^{q-2}}\right)}+\left(\frac{1}{2}-i\right)\gamma^{\frac{1}{p+\nu-1}}$ $$

By letting $\gamma\geq\tilde{\sigma}^{\frac{p+\nu-1}{p+\nu-2}}\|\mathbf{y}\|^{\frac{(p+\nu
-1)(q-2)}{p+\nu-2}}$ as stated in the condition, we have $\gamma^{\frac{p+\nu-2}{p+\nu-1}}\geq\tilde{\sigma}\|\mathbf{y}\|^{q-2}$ and are able to merge the terms as follows:

$$ $\displaystyle y_{i}$ $\displaystyle\geq\frac{(2^{p+\nu-1}-1)\gamma}{2^{p+\nu+1}\left(\left(\tilde{ \sigma}\|\mathbf{y}\|^{q-2}\right)^{\frac{1}{2}}\cdot\left(\tilde{\sigma}\| \mathbf{y}\|^{q-2}\right)^{\frac{1}{2}}+\sqrt{2}\left(\tilde{\sigma}\|\mathbf{ y}\|^{q-2}\right)^{\frac{1}{2}}\cdot\left(\gamma^{\frac{p+\nu-2}{p+\nu-1}} \right)^{\frac{1}{2}}\right)}+\left(\frac{1}{2}-i\right)\gamma^{\frac{1}{p+\nu -1}}$ $\displaystyle\geq\frac{(2^{p+\nu-1}-1)\gamma}{2^{p+\nu+1}\left(\left(\tilde{ \sigma}\|\mathbf{y}\|^{q-2}\right)^{\frac{1}{2}}\cdot\left(\gamma^{\frac{p+\nu -2}{p+\nu-1}}\right)^{\frac{1}{2}}+\sqrt{2}\left(\tilde{\sigma}\|\mathbf{y}\|^ {q-2}\right)^{\frac{1}{2}}\cdot\left(\gamma^{\frac{p+\nu-2}{p+\nu-1}}\right)^{ \frac{1}{2}}\right)}+\left(\frac{1}{2}-i\right)\gamma^{\frac{1}{p+\nu-1}}$ $\displaystyle\geq\frac{(2^{p+\nu-1}-1)\gamma}{2^{p+\nu+1}\left((1+\sqrt{2}) \left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\right)^{\frac{1}{2}}\cdot\left(\gamma ^{\frac{p+\nu-2}{p+\nu-1}}\right)^{\frac{1}{2}}\right)}+\left(\frac{1}{2}-i \right)\gamma^{\frac{1}{p+\nu-1}}$ $\displaystyle\geq\frac{\gamma^{\frac{p+\nu}{2(p+\nu-1)}}}{2^{p+\nu+1}\tilde{ \sigma}^{\frac{1}{2}}\|\mathbf{y}\|^{\frac{q-2}{2}}}+\left(\frac{1}{2}-i\right )\gamma^{\frac{1}{p+\nu-1}}$ $$

∎

See 12

###### Proof.

(i) Starting from Lemma 15 (ii), $\forall i\in[\tilde{T}]$,

$$ $\displaystyle y_{i}$ $\displaystyle=y_{i+1}+\left(\gamma-\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j=1 }^{i}y_{j}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle=y_{i+1}+\left(\gamma-\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j=1 }^{\tilde{T}}y_{j}+\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j={i+1}}^{\tilde{T} }y_{j}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle=y_{i+1}+\left(\gamma-\tilde{\sigma}\|\mathbf{y}\|^{q-2}\cdot \frac{\gamma}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}+\tilde{\sigma}\|\mathbf{y}\| ^{q-2}\sum_{j={i+1}}^{\tilde{T}}y_{j}\right)^{\frac{1}{p+\nu-1}}$ (Lemma 15 (iii)) $\displaystyle=y_{i+1}+\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j={i+1}}^{ \tilde{T}}y_{j}\right)^{\frac{1}{p+\nu-1}}.$ $$

Since $x_{i+1}\geq 0$, we have

$$ $\displaystyle y_{i}$ $\displaystyle\geq\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j={i+1}}^{ \tilde{T}}y_{j}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle\geq\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{i+1}\right)^{\frac {1}{p+\nu-1}},$ $$

equivalently,

$$ $\displaystyle y_{i+1}\leq\frac{1}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}y_{i}^{p+ \nu-1}.$ $$

(ii)

$$ $\displaystyle\sum_{j=i+1}^{\tilde{T}}y_{j}$ $\displaystyle=y_{i+1}+y_{i+2}+\cdots+y_{\tilde{T}}$ $\displaystyle\leq y_{i+1}+\frac{1}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}y_{i+1}^ {p+\nu-1}+\frac{1}{\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\right)^{(p+\nu-1)+ 1}}y_{i+1}^{(p+\nu-1)^{2}}+\cdots$ $\displaystyle\quad+\frac{1}{\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\right)^{ \sum_{j=0}^{\tilde{T}-i-2}(p+\nu-1)^{j}}}y_{j+1}^{(p+\nu-1)^{\tilde{T}-i-1}}$ $\displaystyle=y_{i+1}\sum_{j=0}^{\tilde{T}-i-1}\left(\frac{y_{i+1}}{\tilde{ \sigma}^{\frac{1}{p+\nu-2}}\|\mathbf{y}\|^{\frac{q-2}{p+\nu-2}}}\right)^{(p+ \nu-1)^{j}-1}.$ $$

Given that $i\geq t_{1}$, then $i+1\geq t_{1}+1$ and by Lemma 15 (i) and part (ii) of this lemma, $y_{i+1}\leq y_{t_{1}+1}\leq\frac{1}{p+\nu-1}\tilde{\sigma}^{\frac{1}{p+\nu-2}}
\|\mathbf{y}\|^{\frac{q-2}{p+\nu-2}}$. Therefore,

$$ $\displaystyle\sum_{j=i+1}^{\tilde{T}}y_{j}$ $\displaystyle\leq y_{i+1}\sum_{j=0}^{\tilde{T}-i-1}\left(\frac{\frac{1}{p+\nu- 1}\tilde{\sigma}^{\frac{1}{p+\nu-2}}\|\mathbf{y}\|^{\frac{q-2}{p+\nu-2}}}{ \tilde{\sigma}^{\frac{1}{p+\nu-2}}\|\mathbf{y}\|^{\frac{q-2}{p+\nu-2}}}\right) ^{(p+\nu-1)^{j}-1}$ $\displaystyle=(p+\nu-1)y_{i+1}\sum_{j=0}^{\tilde{T}-i-1}\frac{1}{(p+\nu-1)^{(p +\nu-1)^{j}}}$ $\displaystyle\leq\frac{p+\nu-1}{(p+\nu-2)^{2}}y_{i+1}$ $$

With this, we go back to part (i), for $y_{i+1}\leq\frac{1}{p+\nu-1}\tilde{\sigma}^{\frac{1}{p+\nu-2}}\|\mathbf{y}\|^{
\frac{q-2}{p+\nu-2}}$,

$$ $\displaystyle y_{i}$ $\displaystyle=y_{i+1}+\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\sum_{j={i+1}}^{ \tilde{T}}y_{j}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle\leq y_{i+1}+\left(\frac{p+\nu-1}{(p+\nu-2)^{2}}\tilde{\sigma}\| \mathbf{y}\|^{q-2}y_{i+1}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle=y_{i+1}^{\frac{1}{p+\nu-1}}y_{i+1}^{\frac{p+\nu-2}{p+\nu-1}}+ \left(\frac{p+\nu-1}{(p+\nu-2)^{2}}\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{i+1} \right)^{\frac{1}{p+\nu-1}}$ $\displaystyle\leq y_{i+1}^{\frac{1}{p+\nu-1}}\left(\frac{1}{p+\nu-1}\tilde{ \sigma}^{\frac{1}{p+\nu-2}}\|\mathbf{y}\|^{\frac{q-2}{p+\nu-2}}\right)^{\frac{ p+\nu-2}{p+\nu-1}}+\left(\frac{p+\nu-1}{(p+\nu-2)^{2}}\tilde{\sigma}\|\mathbf{ y}\|^{q-2}y_{i+1}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle=\left(((p+\nu-1)^{\frac{2-p-\nu}{p+\nu-1}}+\left(\frac{p+\nu-1}{ (p+\nu-2)^{2}}\right)^{\frac{1}{p+\nu-1}}\right)\left(\tilde{\sigma}\|\mathbf{ y}\|^{q-2}y_{i+1}\right)^{\frac{1}{p+\nu-1}}$ $\displaystyle=c_{p,\nu}\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}y_{i+1}\right)^ {\frac{1}{p+\nu-1}}$ $$

for $c_{p,\nu}=((p+\nu-1)^{\frac{2-p-\nu}{p+\nu-1}}+\left(\frac{p+\nu-1}{(p+\nu-2)^
{2}}\right)^{\frac{1}{p+\nu-1}}$.
Therefore, $y_{i+1}\geq\left(\frac{1}{c_{p,\nu}}\right)^{p+\nu-1}\frac{1}{\tilde{\sigma}\|
\mathbf{y}\|^{q-2}}y_{i}^{p+\nu-1}$.

(iii) $\forall i\leq\tilde{T}-t_{1}$, $t_{1}+i\geq t_{1}$, therefore, applying part (ii) recursively yields

$$ $\displaystyle y_{t_{1}+i}$ $\displaystyle\geq\left(\frac{1}{c_{p,\nu}}\right)^{p+\nu-1}\frac{\left(y_{t_{1 }+i-1}\right)^{p+\nu-1}}{\tilde{\sigma}\|\mathbf{y}\|^{q-2}}$ $\displaystyle\geq\left(\frac{1}{c_{p,\nu}}\right)^{({p+\nu-1})^{2}+({p+\nu-1}) }\frac{\left(y_{t_{1}+i-2}\right)^{({p+\nu-1})^{2}}}{\left(\tilde{\sigma}\| \mathbf{y}\|^{q-2}\right)^{p+\nu}}$ $\displaystyle\geq\cdots$ $\displaystyle\geq\left(\frac{1}{c_{p,\nu}}\right)^{\frac{({p+\nu-1})(({p+\nu-1 })^{i}-1)}{p+\nu-2}}\frac{y_{t_{1}}^{({p+\nu-1})^{i}}}{\left(\tilde{\sigma}\| \mathbf{y}\|^{q-2}\right)^{\frac{({p+\nu-1})^{i}-1}{p+\nu-2}}}$ $$

By the definition of $t_{1}$, we know that $y_{t_{1}}>\frac{1}{p+\nu-1}\tilde{\sigma}^{\frac{1}{p+\nu-2}}\|\mathbf{y}\|^{
\frac{q-2}{p+\nu-2}}$. Thus

$$ $\displaystyle y_{t_{1}+i}$ $\displaystyle\geq\left(\frac{1}{c_{p,\nu}}\right)^{\frac{({p+\nu-1})(({p+\nu-1 })^{i}-1)}{({p+\nu-1})-1}}\frac{\left(\frac{1}{p+\nu-1}\tilde{\sigma}^{\frac{1 }{p+\nu-2}}\|\mathbf{y}\|^{\frac{q-2}{p+\nu-2}}\right)^{({p+\nu-1})^{i}}}{ \left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\right)^{\frac{({p+\nu-1})^{i}-1}{p+ \nu-2}}}$ $\displaystyle=\left(\frac{1}{c_{p,\nu}}\right)^{\frac{({p+\nu-1})(({p+\nu-1})^ {i}-1)}{p+\nu-2}}\left(\tilde{\sigma}\|\mathbf{y}\|^{q-2}\right)^{\frac{1}{p+ \nu-2}}({p+\nu-1})^{-({p+\nu-1})^{i}}$ $$

∎

###### Proof.

###### Proof.

###### Lemma 15 .

###### Proof.

###### Proof.

###### Proof.

###### Proof.

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: How might future work address the remaining case of $q = p + \nu$, and what specific challenges are anticipated?
soundness: 3
strengths: The problem studied in the paper is both important and well-motivated. The paper provides a rigorous analysis with novel contributions to the study of oracle complexity for asymmetric high-order convex functions, extending previous research by offering a general framework. The authors carefully construct proofs to demonstrate their lower bounds, presenting the results in a way that is accessible for further theoretical work. Additionally, the use of truncated Gaussian smoothing introduces an innovative approach to managing complexity in high-order smoothness contexts, achieving dimension-free smoothness without dependence on dimensionality.
summary: This paper investigates the oracle complexity of minimizing high-order Hölder smooth and uniformly convex functions, particularly under two asymmetric cases: when the degree of uniform convexity $q$ is greater than $p + \nu$, and when $q < p + \nu$, where $p$ is the order of smoothness, and $\nu$ is the Hölder degree. The authors establish tight lower bounds for these cases, generalizing previous lower bounds for uniformly convex functions with first- and second-order smoothness. They employ the $\ell_\infty$-ball-truncated Gaussian smoothing operator to achieve dimension-free smoothness for their hard function construction, providing theoretical insights into high-order optimization.
weaknesses: The paper does not cover the case of $q= p + \nu$

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: Is the norm in $||\nabla^i f||$ (in line 201 and many other places) the operator norm?
soundness: 4
strengths: The paper presents the problem setup, ideas, and results clearly. The lower bounds obtained are tight, and contribute to the oracle complexity of convex optimization literature.
summary: The paper studies oracle lower bounds for minimizing high-order holder smooth and uniform convex objective functions using pth-order oracles. The lower bounds are proven by explicit construction of hard problem instances, and match known upper bounds for the function classes considered.
weaknesses: The paper provides oracle lower bounds for function classes not studied before (in terms of lower bound). The construction of the hard instances, although novel (e.g. using the truncated Gaussian for the smooth), inherits some ideas used previously. For instance, the function in line 218 - line 220 is also used in [1]. It would be great if the authors can provide a brief summary/comparison of which parts of the lower bound construction are used before, and which parts are new. 


[1] Nikita Doikov. Lower complexity bounds for minimizing regularized functions. arXiv preprint arXiv:2202.04545, 2022.

---

confidence: 4
contribution: 2
initial_rating: 8
presentation: 4
questions: ## Two inaccuracies
I recommend to slightly revise the paper according to the following points:

1) In line 168 it is argued that Gaussian smoothing is dim-free, whereas uniform (over an l2 ball) is not. I believe this might be wrong, since they are essentially the same. Gaussian smoothing is nearly the same as uniform smoothing over an l2 ball with radius $\approx\sqrt{d}$, since the distributions are nearly the same by concentration of measure. So it's just that the authors seem to be comparing a $\delta$-approximation smoothing to a $\delta\sqrt{d}$-approximation, which clearly wouldn't have the same smoothing parameters. Is this the case, or am I missing something? Similarly, I believe the same is true for sofrmax smoothing, which isn't really dim-free since the approximation parameter has a $\log(d)$ factor. So making is $\delta$-approximate would mean that the smoothness constant is $\approx\log(d)/\delta$, no? This is a milder logarithmic dependence as opposed to polynomial, but still not entirely dim-free.

2) As written, the proofs hold for deterministic algorithms. The authors do not discuss what is the algorithm class their lower bound holds for, and specifically I believe their results hold for deterministic (or more generally, zero-respecting) algorithms. The first lower bound based on the Nemirovski max function should hold also for randomized algorithm (with a quadratically larger dimension) based on so called "robust-zero-chain" arguments due to "Lower bounds for finding stationary points" by Carmon et al., but these are not given by the authors. Moreover, the second lower bound based on in the Nesterov function is not a robust zero-chain so it shouldn't hold beyond deterministic/zero-respecting algorithms, if I am not mistaken. The authors should discuss this in their paper. 

## Additional question
- What seems to be preventing a lower bound for the symmetric $q=p+\nu$ case? Why do both proof techniques break? It would be great if the authors discuss this in the paper.


## Minor comments
- Notation: $\|\cdot\|$ refers to operator $\ell_2$ norms, maybe should emphasize this (just adding the word "operator") to avoid confusion with Frobenius l2.
- Lemma 1 (i) - the authors probably forgot to assume the function is $L$-Lipschitz.
soundness: 3
strengths: This paper is well written. The results are motivated, well-explained and well-situated with respect to prior work.

I especially liked discussion such as the one appearing in lines 170-191 explaining the intuition in the lower bound construction, and the subtle challenges appearing with respect to prior work on similar subjects.

I haven't checked the math too carefully, but the authors make convincing points so that I believe the results should be solid.
summary: The paper studies oracle complexity lower bounds for optimizing highly-smooth uniformly-convex functions with high-order methods.

Tight lower bounds are established in the "asymmetric" cases when $q\neq p+\nu$, where $q$ is the uniform-convexity degree, $\nu$ is the Holder-continuity degree, and $p$ is the oracle access degree.
weaknesses: One might argue that there isn't much technical novelty, as the two lower bound constructions are adaptations of previous know lower bounds (essentially the Nemirovski function and the Nesterov function), with relatively similar analyses to prior works.

Personally, I do not think this should prevent acceptance, as the authors explain what are the key differences, and the optimization community would benefit from these lower bounds being published.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Please reference the weaknesses for my questions.
soundness: 3
strengths: * The proposed lower bounds on this work match the corresponding upper bounds for general algorithms in these settings, therefore the results are of great interest to the community.
* The use of the truncated Gaussian Smoothing using the $L_{&infin;}$-norm is an interesting technical novelty to circumvent the dimensionality dependencies that would arise otherwise when using Smoothing.
summary: This paper provides general lower bounds for functions, which are uniformly convex with degree $q$ and parameter $\sigma$ and whose $p^{th}$-order derivatives are H&ouml;lder smooth for degree $v$. The proposed lower bounds focus on two asymmetric cases: (1) $q>p+v$ and (2) $q<p+v$, matching the corresponding upper bounds in these cases.
weaknesses: The main issue for me that causes confusion in section 4, concerning case (1) $q>p+v$ is the following:

* In line 327 in the lower bound for $F(x_T)-F(x^*)$ the first term is $-2p\beta\rho(T-1+5/8\sqrt{d})$, then you use the assumption that $2T\geq T-1+5/8\sqrt{d}$, however in line 328 your term becomes $-4\beta\rho T$, omitting $p$. I was wondering if there was a reason for this, as it is not discussed and in this setting $p\geq 1$, therefore for me it is not trivial to remove it.

In several places in the paper there are potentially typos that cause me confusion both in the main part and in the appendix. More specifically:

__Line 783__ $\rightarrow$ you say $1/\sqrt{d}$ is a truncated Gaussian, I think you meant to say $Z_i/\sqrt{d}$

__Line 230__ $\rightarrow$ I think it should be Lemma 1, not Lemma 14 according to the derivation in the appendix as well.

__Line 934__ $\rightarrow$ You have a $\beta^v$ appear in the first inequality, which is confusing to me does it not directly arise from the second inequality, where you use Lipschitzness?

__Line 293__ $\rightarrow$ I believe here that $x_t$ should be $x_s$.

__Line 296__ $\rightarrow$ Should the equality here be $\geq$, since the way that $e_{\alpha(s)}$ is chosen is for it to be the maximum possible that has not already been chosen.

__Line 317__ $\rightarrow$ Lemma 14 should be Lemma 1 here or am I mistaken?

__Line 1011__ $\rightarrow$ Similar to 296 it should be $\geq$ or am I mistaken here again?

__Line 1019__ $\rightarrow$ I think it would be beneficial to reference Lemma 1 here for justification as the write up is extremely lengthy and it caused some confusion for me here.

For Section 5, I only have one question. Concerning lines 402,403, what do you mean by scaling of $\tilde{f}$ and how does this imply directly that all of the properties of $\tilde{f}$ translate to properties of $f$. This seems a little bit informal to me.

I also found that there is at least one missing citation in the line of upper bounds for the case of H&ouml;lder Smooth functions.

[1] Universal Gradient Methods for Stochastic Convex Optimization

Meta-review: This is a theoretical paper that studies the oracle complexity of minimizing convex functions with varying degrees of high-order smoothness, p, and degrees of uniform convexity, q. The oracle has access to pth order derivatives. While the authors lower bounds do not cover all ranges of parameters, they are tight in the ranges covered, and thus the reviewers agreed that the paper makes fundamental progress on an important challenge in convex optimization. Moreover, it was agreed that the paper was well-written, with intuition provided throughout, and the problems well motivated. We would be happy to have this paper appear at ICLR.

Decision: Accept (Oral)