Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
Authors: Site Bai
Brian Bullins
Venue: ICLR 2025 Oral (2025)
Keywords: Convex Optimization
Uniform Convexity
Lower Bound
High-Order Method
Regularization
Hölder Smoothness
Primary area: optimization
TL;DR: This paper establishes tight lower bounds for minimizing high-order Hölder smooth and uniformly convex functions with high-order oracle access.

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^{th}$-order derivatives are Hölder continuous with degree $\nu$ and parameter $H$, and that is uniformly convex with degree $q$ and parameter $\sigma$, we focus on two asymmetric cases: (1) $q > p + \nu$, and (2) $q < p+\nu$. Given up to $p^{th}$-order oracle access, we establish worst-case oracle complexities of $\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)$ in the first case with an $\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)$ in the second case, for reaching an $\epsilon$-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.

Published as a conference paper at ICLR 2025
TIGHT LOWER BOUNDS UNDER ASYMMETRIC HIGH- ORDER HÖLDER SMOOTHNESS AND UNIFORM CON- VEXITY
Cedar Site Bai Department of Computer Science Purdue University West Lafayette, IN, USA ba i 123@purdue.
Brian Bullins
Department of Computer Science Purdue University West Lafayette, IN, USA
bbullins@purdue. edu
ABSTRACT
In this paper, provide tight lower bounds for the oracle complexity of min- imizing high-order Hölder smooth and uniformly convex functions. Specifi- cally, for funetion whose -oddr derivatives degree and parameter H, and that is uniformly convex with degree q and parameter o, we focus two asymmetric cases: (l) q p + V, and (2) < p + V. Given up to p"h-order oracle access, we estab- ((g-p-w) (((p+p)-2)
Hölder continuous with
lish worst-case oracle complexities of (#) (#) (2)
in the bb--aalltunnctte---aauaes smoothed hard function and in the second case, for reaching
first case with Ω
I1 का + log log
aptte 17
e-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.
INTRODUCTION
With the advancement in computational power, high-order optimization methods "o"derrder with p 2 2) 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, g 3) (Nesterov & Polyak, 2006) is an example, as are methods of even higher orders (p 2 3. q 2 (Zhu & Cartis, 2022).
Although these problems are high-order smooth by definition, lower-order algorithm may be em- ployed to obtain an approximate solution. For instance, solving the subproblem of cubic-regularized (i.e., 3) Newton with gradient descent (accessing first-order oracle, i.c., 1), or, more gener- ally, approximately solving the subproblem of (g 1)th -order Taylor descent (Bubeck al., 2019) (which typically contains 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 (g 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 (g < + 1). Examples include the objective function of logistic regression, which known to be infinite-order smooth. Coupled with standard fz-regularization, the problem can be analyzed as pth -order smooth and strongly convex (g = 2) problem, e.g., p = 2 with access to the Hessian matrix, = 3 accessing the third-order derivative tensor.
In addressing specific instances of this asymmetry, previous works established some upper bounds (Gasnikov al., 2019; Song al., 2021) and lower bounds (Arjevani et al., 2019; Kornowski

---

Published as a conference paper at ICLR 2025
& Shamir, 2020: Doikov, 2022: Thomsen & Doikov, 2024) for the oracle complexity. Notably, Song et al. (2021) proposed a unified acceleration framework for functions that are p -order Hölder smooth with degree v, and uniformly convex with degree q, providing upper bounds for any combination of p. and v. For the case where > + u, they show an oracle complex- 3(m-p-))
((3G)+9)-22 ity of O ()) s(p+e)-2 -2 (?) (2)
and for the case where q < p + v, the complexity is
+)) To the best of our knowledge, no lower bounds exist in this general setting, particularly with Hölder smoothness and uniform convexity.
O H S(pto)- + log log
((+7))
In this paper, we provide matching lower bounds to the upper bounds in (Song et al., 2021) for these asymmetric cases, Specifically, we establish 9
24y ((sipte)-2) for q > p
H S(p4e)-2 (4)
and ? Sipte) + loglog
for q < < v. For the q > p + v case, we
22
adopt the framework proposed by (Guzmán & Nemirovski, 2015), utilizing smoothing operator to generate a high-order smooth function. We propose the use of l -bal--al-ttumm -buul--runnctedd 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 foo ball are erucial to improve upon the sub-optimal derivation using uniform smoothing within an & ball in (Agarwal & Hazan, 2018). Our results generalize the lower bounds in (Doikov, 2022; Thomsen & Doikov, 2024) to higher-order and Hölder smooth settings, For the + V/ case, we adopt Nesterov's 's framework (Nesterov et al., 2018 8) and generalize the lower bounds (Arjevani et al., 2019; Kornowski & Shamir, 2020) to include Hölder smooth and uniformly convex settings.
2 RELATED WORK
Upper Bounds. Doikov & Nesterov (2021) 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. (2019) and Jiang et al. (2019) established a near optimal upper bound of Ô Sp17 in the simpler case of
without uniform convexity. Gasnikov et al. (2019) achieve the same near-optimal rate, but also consider uniform convexity, and by the restarting mechanism, derive the rate that for q > p + as well, generalizing the upper bounds established in second-order (Monteiro & Svaiter, 2013) and matching the lower bounds later derived in (Kornowski & Shamir, 2020). Kovalev & Gasnikov (2022) closed the log (2) gap. but does not consider uniform convexity or Hölder smoothness. For minimizing uniformly convex functions, Juditsky & Nesterov (2014) and Roulet & d' Aspremont (2017) study the complexity of first-order methods. Recently, Song et al. (2021) 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 p and g < p + v cases.
Lower Bounds. Agarwal & Hazan (2018) proved for = smooth convex functions an Q 2( 5pIT) ((=5AT)) lower bound based on constructing the hard function with randomized smoothing uni- formly 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 al. (2021) added softmax smoothing prior to randomized smoothing, achieving near-optimal rate of Ω 3p+1 for randomized and quantum algorithms. Separately, Arjevani et al. (2019) also established the optimal lower bound of Ω thermore, for the asymmetric case of q < + 1, Arjevani et al. (2019) proved the lower bound of ffTr -)) for the p- 2 and g 2 case, and the result is later generalized to considered
3pFT with the Nesterov's 's hard function construction approach. Fur-
Ω ((#) + log log the tth order in (Kornowski & Shamir, 2020). No q >> 2 uniformly convex settings in these works. For the case of 9 > p + v, lower bounds for uniformly convex functions for 4 2 3 limited to the first-order smoothness setting where p (Juditsky & Nesterov, 2014; Doikov,
2

---

Published as a conference paper at ICLR 2025
2022; Thomsen & Doikov, 2024). No lower bounds for uniformly convex functions were established, to our knowledge, in the high-order setting.
PRELIMINARIES AND SETTINGS
Notations. We use [n]] to represent the set {1, (1.2...,,) We use || denote an &g operator norm. We use V for gradients, @ for subgradients, and (..-) for inner products. Related to the algorithm, bold lower letters for vectors (e.g., x, y), and with subseript, the vectors different iterations (e.g.. X)). We use regular lower letters for scalars, and with subscript, a coordinate of a vector (e.g., 2;).. Depending on the context, we use capital letters for matrix or a random variable. We use Φ for the probability density function of the standard normal the standard multivariate normal (MVN), and for the cumulative (density) function standard normal or MVN. We further overuse the notation of [(..] [...) for their truncated counterparts for the normal distribution (standard normal if not specified with parameters), and @ Pl 4 + for the MVN truncated within an Eo ball.
3.1 DEFINITIONS
Definition 1 (High-order Smoothness). For p E Zt, a functinn f .R. R is ph "0 -oder smooth or whose pth- derivatives are Lp-Lipschitz if for Lp > 0, v x.y E Rd, [VP <ef(y)l I y||-
Definition (High-order Hölder Smoothness). For p Z+, a function f : Bd R is pth. order Hölder smooth or has Hölder continuous pd -order derivatives ffr E (0, and H > 0, x,y Rd. ||
V f(y)ll S H yyll"
Definition 3. (Uniform Convexity (Nesterov et al., 2018, Section 4.2.2)) For integer q 2 2 and > 0, a function f : Rd E is uniformly convex with degree q and modulus if V x.y E Rd.
f(y) f(x) - (V](xx, x) 2 yly - or the function sulisfies (V - Vx(x), y x)
olly -
4
LOWER BOUND FOR THE q >pt ++p1 CASE
The derivation of the lower bound is to find such function by construction that satisfies the uniformly convex and Hölder smooth conditions and requires least a certain amount of iterations reach an e-approximate solution. The general steps follow from the framework of showing lower complexity bounds for smooth convex optimization (Guzmán Nemirovski, 2015), which originates from (Nemirovskii & Nesterov, 1985) and serves as the basis for results in various follow-up settings (Agarwal & Hazan, 2018; Garg et al., 2021; Doikov, 2022). The construction starts from a non- smooth function, then smooths the function with
smoothing operator (e.g. Moreau envelope in (Guzmán & Nemirovski, 2015; Doikov, 2022), randomized smoothing uniformly within a ball in (Agarwal & Hazan, 2018: Garg al., 2021)). We design truncated Gaussian smoothing operator within the Loo 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 R2 and a parameter p O, define the truncated Gaussian smoothing operator Splf]: : (Rd - RR) + (R. + R) as
Sp[f(xx) = Ey [f PV)]
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
v VTV)
P(V = =] (2d)
exp
2
in which 1 is true otherwise is the indicator function i.e., the cumulative distribution within the d-dimensional unit Ebal (Cartinhour, 1990).
function and (dd) is the normalizing factor,
We denote fo = =S,f), and use the shorthand notation for the function that applied the smoothing operator for p times: S3 SY]S Spl... Sp(-.-(sp[[]] ) p times.
3

---

Published as a conference paper at ICLR 2025
Now we justify the choice of truncated Gaussian smoothing for the construction of hard function. We notice that Agarwal & Hazan (2018) choose randomized smoothing uniformly over a unit fz-ball, which by their Lemma 2.3 that the smoothed function is (dd) (which in fact can be tightened to O(v)) by (Yousefian et al., 2012; Duchi et al., 2012, Lemma 8)) where di is the dimension of the variable. Since the number of iteration T E (d), their result O sp-1 is sub-optimal by an extra 7 comparing to the tight lower bound O 3p++ (Arjevani et al., 2019). Therefore we search for a smoothing operator with Lipschitz constant being dimension-free. We notice that Gaussian smoothing (Duchi et al., 2012, Lemma 9), softmax smoothing (Bullins, 2020, Lemma 7), and Moreau smoothing (Doikov, 2022, Lemma 1) 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 be local, that is, accessing information within some neighborhood of the queried point, e.g., a unit b2-ball in (Doikov, 2022). 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, 2022), but not suited for the high-order setting. First, one may attempt the extension of Moreau smoothing with p" -power regularization, yet it can be shown that the function is not pth -order smooth. Next, one may try to apply Moreau smoothing p times, yet unlike randomized smoothing in (Agarwal & Hazan, 2018) 8), the Lipschitz constant does not raise to the =d -power with the number of times the smoothing operator applied, which leads to the same rate as in the first order. Observing the proof of (Agarwal & Hazan, 2018, 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 dimension-free constant (iii) p*d-order smooth with smoothness constant raising to the pd power as well. Initially, we applied the Gaussian smoothing truncated within a unit ball in l2 by default. We noticed later, however, that the marginal distribution of unit-f2-ball truncated multivariate Gaussian is not the truncated standard normal between [],, 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 smooth- ing truncated within an foc ball, a.k.a., the hypercube with edge length 2, whose marginal distribution is indeed the truncated standard normal between [-1, (Cartinhour, 1990). 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 J. the function f3 Spl SSp
... satisfies
(i) I convex, S8. is convex and T--Lipschitz with respect to the Eg norm.
(ii) If f is convex, fxx S ff(x) S f(x) + 3 Lpvd.
- (iii) Vi E [p). Vx, x' E Rd. V [V V fg('')) (3) L||x-x'11
4.2 THE LOWER BOUND: FUNCTION CONSTRUCTION AND TRAJECTORY GENERATION
Theorem 1. For any T T-step (5 d) deterministic algorithu A with oracle access up to the thhh order, there exists a convex function f(x) whose -order derivative is Hölder continuous of degree u with modulus H and a corresponding F(x) = f((x E||x|| with regularization that is uniformly convex of degree with modulus a, such that q > p + v, it takes
(!)) 3(P40)-
2(u 2(w-p-r) S(p
TEn
steps to reach an e-approximate solution XT satisfying F(XT) - F(x*) S
Proof. We begin the proof by constructing the hard function.
4

---

Published as a conference paper at ICLR 2025
4.2.1 FUNCTION CONSTRUCTION WITH TRUNCATED GAUSSIAN SMOOTHING
Non-smooth Function Construction. We first construct the function
Dr (x)
max rx(x)
where t E , Ex (Ca(M): x) -(k: (k- -kk-1) 1)6.
IskSt
& {-1,1), is the standard basis, is permutation of [T]. and 5 >> 0 is some parameter that will choose later. Lemma 2 characterizes the properties of 9: with proof in Appendix A.2.
Lemma 2. A E [T], gt is convex and 1-Lipschitz with respect the to norm, and also the 2--norm.
Truncate Gaussian Smoothing. Next, we smooth the function ge gx(x) with truncate Gaussian smoothing in Definition 4. Given parameter p > 0 and p E Z+
Gx(x) (x)
Based on Lemma 1, we show that (x) satisfies the following lemma, with proof in Appendix A.2.
Lemma 3. Vtt E [T]] xx,y E R
(i) (x( is convex and I-Lipschitz, i.e., Gx(x) G.(y) s |x yll- y-l-- (ii) ge (x(x) S G((x) S g (x) + ppvdd
(iii) For some fixed p E Zt, ViE (p), IV) V'G.(y)) S (B) [| -yl- -VGG>))
3. Adding Uniform Convexity. Now that the constructed function (x is all-order smooth, we add
to the uniformly convex regularization. We define
fx(x) (x)
f(x) fI (x) F(x) Fr(x).
0 |xx1 X q
Fx(x)= fx(x) + (x) for (x(x))
where 3> 0) is a parameter that we will choose later, 2 = fx ||x||2 S D} for DS ( (T- v
and C = =0(4 1) x x (q p).
Lemma 4. For F(x) = fr(x) + (x) where dg (x) = a |x|| and x E Q
(i) F is uniformly convex convex function with degree q and modulus o > O.
(ii) F(x) is ph porder Hölder smooth with parameter H
2 E
Therefore, by Lemma 4, the function constructed satisfies the desired uniform convexity and high- order smoothness conditions. Next, we characterize with Lemma 5 the upper and lower bounds of the constructed function which will be used in the proof later.
Lemma 5. For R(x) = 3 maxketu1 &A (ea(k)) x) + ||x||9, l we have
5
R(x) 3(T - 1)8 S F(x) R(x) ppppVd.
4.2.2 CONVERGENCE TRAJECTORY GENERATION
4. Trajectory Generation Procedure. The trajectory is generated following standard T T'step iterative procedure same as outlined in (Guzmán & Nemirovski, 2015; Doikov, 2022):
For 1, x1 is the first point of the trajectory and is chosen by initialization of some algorithm A, independent of F. Subsequently, choose
(x1) E arg max kE[2]
( (ea(H)) xl)|
ε ===iig sign ((ea(1) x1)),
after which a fixed (x( is generated.
We would note that for the > p v case, F is guaranteed to be p -odder smooth only in the bounded domain as constructed, since the regularization term dy (x) may not be pdh--rdee smooth on E The construction is inspired by that in (Juditsky & Nesterov, 2014). This is not explicitly discussed in (Song et al., 2021; Doikov, 2022; Thomsen Doikov, 2024).
5

---

Published as a conference paper at ICLR 2025
For 2 I t < T, the beginning of each such iteration, we have access to X1. Xx-1, the function Ft-1, and its gradient information, which we denote as Ix-1(x) =
{F, 1. FF,11. F. }. The algorithm A generates the next point with this information:
X = A(I-1 ... -x- Then choose
all)
arg max (E(()aa())s
(ea(a)) x+)1
&. = sign ((ea(e): xx))
after which a fixed Fx(x) is generated for the next iteration.
5. Indistinguishabbiityy of Ft, and F for Trajectory Generation. It's important to note that the trajectory " XT is generated based on a sequence of functions Fi,-.. PT, whereas our object of analysis should be just one hard function F Fr. Here we show:
The trajectory "1,"." XT generated by applying an algorithm A iteratively on the sequence of functions Fi..... ,r,, with up to ph p"h-order oracle access, is the same as the trajectory generated applying A directly on F when oracle access pertains only local information within an 30 -ball with radius 5/2.
Lemma 6.
Proof. The idea is to show that 2 S t S T, the function gr coincides with gr (so that F; coincides with FT in terms of generating X i.c., Iz = -Ir) under some mild conditions. Similar proof can be found in (Guzmán & Nemirovski, 2015; Doikov, 2022, Section 3). By construction, V E [T).
9r (x)
max Th (x) max 1sk-t
max Th (x), max rx(x) max [x(x), max rx(xx) ISk5
sckS!
sckst
Furthermore, a(s) E arg MaxAE(TMMal(sskc | (ea(k); x=) and E. = -iign ((ea(s)) Xz)). therefore
9x = max &N (Ba(k), x.) - (k- 166-1)622 max EA (Ba(k)) Xx) - (s - 1)0 ISAS
ISASa
2 (Co(s): x.)l - (s 1)6 max & ( (Co(K), x.) (s-- sck5i
2 max EN (Bnx(k), xx) - (k 6 scktt
(k, Z k > = = k2s+1)
If limit the information access within an -bll with radius 8/2 when searching for the next point x from xx, we then establish local region Vx, ||x xs11xc á. Further by Lemma 2 that Is (also & (Co(H): x)) 1-Lipschitz with respect to the foo norm, we have le such that s S t,
(x.) ) 2 Ex (Co(k): xx) - (A: 1)5 + 2/|x - x
2 Ea (Co(k): x.) (I: 1)5 + (x,( 9. (x)] + [Ex (Co(k)) x) Ex (Co(M)) xx)]
which implies that go (x) 2 max,ekgr EK (Pack): x) - -k- 1)6 = max (x). This concludes that V such that ||x l1 2 (x)) max (x), max rx(x)) go (xx. which further implies Fx(x) F. (x). Letting T have V [T], (x(x) (x))) for |x xelloo S 3.
4.2.3 LOWER BOUND DERIVATION
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(XT) F(x*) 2 -3(T 1)6 - 1p3pvd d + 2-1
8
9 LoT2
7. Setting the parameters. By Definition 4 and Lemma 14 (i), know that Sp]m((x), (g.,(
depends on the value of gi (x) within an -all of radius p. Therefore inductively, we see that for F(x) 3.5 [er]gr]( (x) + ||x||| F(x), VF(x).
F>F(x) depends on the value of F(x) within an ball of radius pp. For our construction to hold, we also need (x() and F F(x) to be indistinguishable V E [T], which is true within an -bll of radius 8/2.
Therefore, we set 8 = 2pp, so that for the purpose of oracle access at x, (computing (high-order) gradients of F), it's indistinguishable replace F(x) with Fx(x), and the sequence generated as in

---

Published as a conference paper at ICLR 2025
Section 4.2.2 is the same that directly applying some p"h algorithm A F(x). In other words, F(x) and the generated Xy serve as valid components for deriving the lower bound.
As a result, F(xT) ((xT))F((x" Fx(x)) 2 -2p3p(T vd)+ -=1
Let vd-12
Vd-1,
then F(xT)= - F(x*) 2 -pp8p7 + 9-1
By letting 4p8pT
24
2-1
we
rT
solve for p g-1 8pg
0
- - B
I
2-3g
C
. 3
2-3g
in which Co
4-1
8pg
and at the
same time,
9 9-1
399
F(XT) F(x") 2
(I)
2q
oT
By the construction of F(x) and Lemma 4, we know that F(x) is phh -order Hölder smooth with parameter 2F-13 pe
Plugging in the value of p. we have
H -2p+1 69
21r 3- T
(arr 11 2] 21u 17
He 1o 1
p-pto
fa 11184 2 0
equivalently, B
T
Plugging the value of B back into
25-1
Eq. (1), we have
Hoptu-1g 1
0T0
9-
(3pt 21p- gmP)
F(xT)- - F((x))
2
0
29
21+1
(pte\(1-g)
9
P-a-v
Ho
1) 2] 2(p-a-p
4p
T
8pq
2d+1
We complete the proof for Theorem by letting F(XT) F(x*) S 6, from which solve for
2ipleMe
(2 3
p paste
-
#
(g)
3ig-p-)) 3
8pg
LOWER BOUND FOR THE q < <pt CASE
For any T Ttep deterministic algorithu A with oracle access up the pth order, there exists convex function f(x) whose - derivative is Hölder continuous of degree v with modulus H and corresponding F(x) f(x)x(x+)))) + =[x[[| with regularization that is uniformly convex of degree g with modulus a, such that q p + v, it takes
Theorem 2.
(
H
3(p+0)-2
[oPt
T TEN Ω
log log
H9
steps to reach e-approximate solution XT satisfying F(XT) F(x*) S.
Proof. Similar to all other lower bound proofs, we construct such 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., 2018), and generalizes the construction in (Arjevani et al., 2019) to higher-order and the construction in (Kornwssk & Shamir, 2020) to Hölder smooth functions well as uniformly convex functions.
5.1 FUNCTION CONSTRUCTION BASED ON NESTEROV'S 'S HARD FUNCTION
direct generalization of Nestrov's 's construction for first- and second-order lower bounds (Nesterov
al., 2018. Section 2.1.2, 4.3. the orderrder Hölder smooth setting takes the form f(x)
yen ||x]|9 for g <p <p+ u, E [0, 1), which is uniformly convex by ri+1 11t1
p+u
7

---

Published as a conference paper at ICLR 2025
the regularization. We further add coefficient that the function -rd-r Hölder smooth with the desired parameter H and further on top of this a set of orthogonal basis Vs, viv [T' to limit the access of coordinates through the iterations:
H
f(x) = 20t 2p ( 1)!
Vi, x) - (Vi+1, x) - (V1, x)
|
P+V
is chosen iteratively to be orthogonal to XI. X; and Vi,... Vi-1. Similar to (Arjevani al., 2019, Lemma 7), one can show that the oracle information of f(x,). V S does not depend on Ve+1," Vi. so that the iterative construction of v, is valid, i.e., does not affect the x; generated running an algorithm on Now we characterize the relation between f and f.
H8 for (ptu-1-
equivalently, 5 (ptrt)(ptu113s
Lemma 8. x" = arg min f(x), y = arggmin,, f(x). (i) E (T], (v., x*) yv. (i) ||x* = ||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. fxx is (i) uniformly convex with degree and parameter a. (ii) ndh -order Hölder smooth with degree v and parameter H.
The analysis of (Nesterov al., 2018) then derives the lower bound based the closed-form optimal solution that minimizes the hard function. For our generalized construction of f. however, the closed-form solution hard obtain. As in (Arjevami al., 2019). we instead analyze some properties of for each of these lower bounds. For simplicity, we state the properties for function f. and since f is simply a scaling of f. the properties also apply to f with a difference of constants. To
prove Theorem 2, we show separately for the
[!
((ा-5)ー term and the log log
He
term. The derivation is largely based on some key lemmas whose complete proof is in Appendix B.
5.2 TEA(1 Motoo
Since we cannot solve for closed form solution from arg miny f(x), we need to alternatively bound the solution in a relative scale. One key observation is that the coordinates of the optimal solution form decreasing sequence (Arjevani et al., 2019; Carmon al., 2021), and their relative relation can be characterized as Lemma 10 (i) utilizing the first-order optimality condition. Based on the properties of each coordinate, one relate them to the norm of the optimal solution as in I Lemma 10 (iii).
Lemma 10. For arg min f(x).
(i) Vt E []]. Yt 2 8/1 - (t - 1)ppt
(ii) For T= = p
V1 S q V .
デ
(iii) For 2 2 || 119-2))
1l E [7] ye 2
|yyl 2 +
( -) n
Then the bound on the norm of the optimal solution can be established in the following lemma.
Kptei-2 2 2 (p+=-1 2339-)
Lemma 11. ||
The final step is to relate this norm to the optimality gap with the property of uniform convexity. By + (1 - T) yuti-1, Therefore,
Lemma 8 and Lemma 10 (iii), (VT,x*) = yr 2 2 1
8

---

Published as a conference paper at ICLR 2025
with Vy and Xy orthogonal to each other by construction,
4
f(XT) fx=(f(())= 2 _ XT x"1
11 ((V,, x3)
o
XT XT XVxxx--''''
xx1)
((VT, -
x}))²}
q
p+v
2i 1ptt-1)
[/2 --T T) p
q
20+
12 |1y
9
In order to achieve f(xx) f(x*) S c, we have a
(2 3 7 p
Sc
q
20tutig
||y||| "
from which we can solve for T
16-4-113
qe
I For
7F10-I0 24g
2P 20111187 lly
oypie
have 1
2 0. Therefore, T
2(p-v-1j
20-r+18 a Iyll 22
M(mte)-2 Dur
By Lemma 11, we know that |yll <
2
Therefore, for = 0, by Lemma 8,
[xo x = ||x*||
|y
To satisfy the condition ||x0-xx| S D, we let
20t (utu-11(3-22) 30--0-12 3(tte) D
D, then we can solve for y S 2
3(pte)-2 ÿ -(p-))-2
Plug this
as well as |y < D into the lower bound on T we have
p+o-2
1(p+=-1) 3(p42)-2
(p-e- 1129-2) M(pev-1)
T
2
3pptu--
2
(ptot1) D リiptシー=
pie
2pllo-
20
Plugging in ő 20t
(ptu- 1)le we have T E Ω 1e((5) ( s H
((ttte
5.3 Tel Ω log log
pio
For the log log term, follow similar narrative in Section 5.2, starting from characterizing the per-coordinate relation of the optimal solution.
Lemma 12. For y = arg min f(x), let t E [T] be such that yr, p+v-1 pob-2 ||y|| p4o-2 and
30 < - - ||y|| 2 Then
(i) Vi E [T] Yi = Vit1
(0lly|10-3 "イ
7 2j=+1191 83
and yit1 S -
1-レ-1
(i) Vi 2 f1. (g.i))
ptv-1 S 1i-1 where Cp.v is a constant depending on p. V.
al
11 11)
(iii) Vi < T 11 Wi+ti
pou-2
("lly|19-2) m4b (p + 1- --1 -p--v=-1
Next, we derive the bound on the norm ||x; - x" from the coordinate wise properties in Lemma 12 with the basis defined for f. When constructing the function, choose H > 20+v+1 (p + 1)la
so that < 1. Then for basis vector Vi, by Lemma 8 and Lemma 12 (iii),
(pts-1 [(ptt-1))-1)
(Vi++,, x*) = Moi+i 2
|y
p+o-z
(p + 1) (pto-1)'
Cppy
1 -(1
p-v-
2-V-
12+++1 + 1)l0
|xo
|||||
x
-ーー
(p + w- -11 1) 10+e-111)
Cp..v
H

---

Published as a conference paper at ICLR 2025
for O, in which the first inequality follows from Lemma 12 (iii), and then the fact that for q
and ē < 1, povio & πサシーz For - 2'
XT x+11 (1|T - x311)
XV xx)) xx)) 2 ((
= (((V)++2,x*)))) 8
((v,,+2,x")))
where the equality in the second line follows from the fact that by construction, + and xy are orthogonal.
Finally, with uniform convexity, we have
f(XT) f(x')2
XT
x
17T
2 (p+ +V - 1)10
pi
Ixo0 x x=|| =1 (p+ 10----1)-000 11)
vlu-23
Cp.
q
11
--p-a
(p+ 1o+u - 1) 1) 16tto1177
Lp
(ntv-11n p-o-
virto Mxitu- 15
for Cp.g.v
(p++0- 11!) p+0-0
p+0-2
D D in which | xx |1 S D.
Gpi
In order achieve f(xr) - f(x*) S e, we have Cp.g.v
ptv-a
(p 1) -)---ee (0tt--1" S c, from
L Lgle
1 which we solve for T 2 log 1o%p+y-1 Cp.g.
+ 1o% 1o% (t) which completes the
L
proof for Theorem 2 combined with the result Section 5.2.
CONCLUSION AND FUTURE WORK
We provide tight lower bounds for minimizing functions with asymmetric high-order Hölder smooth- ness and uniform convexity. Specifically, we show that the oracle complexity lower bounded
by Ω
H 3 ( ((3(+
2(p-p-o)
for the p + case with the construction of a -all-
mruncted--Gaussian smoothed hard function, and Ω ( MPli) + log log
PPto HG
for the < < + v case. Both lower bounds match the corresponding upper bounds in the general setting.
We note that the lower bounds for the g > p + 1 case and the q < < + case are derived based on two different frameworks. The first lower bound based on Nemirovski's max function can be directly extended to hold for randomized algorithms based on Trobust-zero-chait al., 2020; 2021). The second lower bound based on Nesterov's 's function, which is not robust zero-chain, holds only for determministic/errrrspeecti
arguments by (Carmon
algorithms.
We further note that the lower bound for the = p + D case is not included in this paper. Proposing unified framework for all three cases well generalizing the results to work for randomized algorithms would be of great interest, which we leave for future work.
REFERENCES
Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. In Conference On Learning Theory, pp. 774-792. PMLR, 2018. (Cited on pages 2, 3, and 4.)
Yossi Arjevani. Ohad Shamir, and Ron Shiff. Oracle complexity of second-orde methods for smooth convex optimization. Mathematical Programming, 178(1):327-366 2019. (Cited on pages 1, 2, 4, 7, 8, 20, and 21.)
10

---

Published as a conference paper at ICLR 2025
Dimitri P Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals.
Journal of Optimization Theory and Applications, 12(2):21822) 231, 1973. (Cited on page 14.)
Zygmunt William Birnbaum and FC Andrews. On sums of symmetrically truncated normal random variables. The Annals of Mathematical Statistics, 20(3):458 461, 1949. (Cited on page 16.)
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. (Cited on page 14.)
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near-optimal method for highly smooth convex optimization. In Conference on Learning Theory, pp. 492- 507. PMLR, 2019. (Cited on pages 1 and 2.)
Brian Bullins. Highly smooth minimization of non-smooth problems. In Conference on Learning Theory, pp. 1080. PMLR, 2020. (Cited page 4.)
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120, 2020. (Cited on page 10.)
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming. 185(1):315-355 2021. (Cited on pages and 10.)
Jack Cartinhour. One-dimensional marginal density functions of a truncated multivariate normal density function. Commmicaations in Statistics-Thent and Methods, 19(1):197-203, 1990. (Cited on pages 3, 4, and 13.)
Hao Chen, Lanshan Han, and Alvin Lim. A note on the sum of non-identically distributed doubly truncated normal distributions. arXiv preprint arXi::2008.0990 0705.0 2020. (Cited pages 15 and 16.)
Nikita Doikov. Lower complexity bounds for minimizing regularized functions. arXiv preprint arX1v:2202.04545, 2022. (Cited on pages 2, 3, 4, 5, 6, and 19.)
Nikita Doikov and Yurii Nesterov. Minimizing uniformly convex functions by cubic regularization of newton method. Journal of Optimization Theory and Applications, 189(1):317-339, 2021. (Cited on page 2.)
John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal Optimization, 22(2):674-701, 2012. (Cited pages 4, 14, and 15.)
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. Near-optimal lower bounds for convex optimization for all orders of smoothness. Advances in Neural Information Processing Systems, 11.29874-29884 2021. (Cited pages 2 and 3.)
Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Se- likhanovych, and César A Uribe. Optimal tensor methods in smooth convex and uniformly convexoptimization.. In Conference Learning l'heory, pp. 1374-1391. PMLR, 2019. (Cited on pages and 2.)
Cristóbal Guzmán and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31(1):1-14, 2015. (Cited on pages 2, 3, 5, and 6.)
Bo Jiang, Haoyue Wang. and Shuzhong Zhang. An optimal high-order tensor method for convex optimization. In Conference on Learning Theory, pp. 1799-1801. PMLR, 2019. (Cited on page 2.)
Anatoli Juditsky and Yuri Nesterov. Primal-dual subgradient methods for minimizing uniformly convex functions. arXiv preprint arXiv: /401. 1792, 2014. (Cited on pages 2 and 5.)
Guy Kornowski and Ohad Shamir. High-order oracle complexity of smooth and strongly convex optimization. arXiv preprint arXlv:2010.06642, 2020. (Cited on pages 1, 2, and 7.)
Dmitry Kovalev and Alexander Gasnikov. The first optimal acceleration of high-order meth- ods in smooth convex optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL happ::s//ppeeeviii iew net www.moirummee/ee doorummid=ygmii 112001P. (Cited on page 2.)

---

Published as a conference paper at ICLR 2025
Hariharan Lakshmanan and Daniela Pucci De Farias. Decentralized resource allocation in dynamic networks of agents. SIAM Journal on Optimization, 19(2):911-9444 2008. (Cited on page 15.)
Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 23(2):1022-1255, 2013. (Cited on page 2.)
Arkaddii S Nemirovskii and Yu E Nesterov. Optimal methods of smooth convex minimization. USSR Computational Mathematics and Mathematical Physics, 25-2) 1985. (Cited on page 3.)
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical programminng 108(1):177-205, 2006. (Cited page 1.)
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017. (Cited page 15.)
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018. (Cited on pages 2, 3, 7, 8, and 18.)
Vincent Roulet and Alexandre A'premoon. Sharpness, restart and acceleration. Advances in Neural Information Processing Systems, 30, 2017. (Cited page 2.)
Chaobing Song, Yong Jiang, and Yi Ma. Unified acceleration of high-order algorithms under general holder continuity, SIAM Journal on Optimization, 31(3):197--1826, 2021. (Cited on pages 1, 2, and 5.)
Daniel Berg Thomsen and Nikita Doikov. Complexity of minimizing regularized convex quadratic functions. arXiv preprint arXiv:2404. 17543, 2024. (Cited on pages 2, 3, and 5.)
Farzad Yousefian, Angelia Nedié, and Uday V Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56-6) 67, 2012. (Cited on page 4.)
Wenqi Zhu and Coralia Cartis. Quartic polynomial sub-problem solutions in tensor methods for nonconvex optimization. In NeurlPS 2022 Workshop, 2022. (Cited page 1.)
12

---

Published as a conference paper at ICLR 2025
Appendices
A PROOF FOR TECHNICAL LEMMAS SECTION 4
A.I PROPERTIES OF TRUNCATED GAUSSIAN SMOOTHING
Lemma 13 (f Truncated Gaussian and Its Marginal Distribution). For standard MVN truncated in unit 2 -bollall defined in Definition 4:
viv [ivlll Stp
PIV v) Z(2
exp
(i) The cumulative distribution within the boo-ball, i.e, the normalizing factor Z(d) = (O(1)-4(111 -(-1))
(ii) The marginal distribution is a standard normal truncated within [-1,
Proof. By Eq. (3) (Cartinhour, 1990), we know that 7(d)=
J/
I llv S1 (2x)
exp
2
dv
1
Σi= 1
exp
dun ... dua
(2T))
2
d-time integration, one for each coordinate
{
uf
II
exp
1-2
duc
2
i=1"
[11 (--1)
(ii) By Eq. (4) and (16) (Cartinhour, 1990), Vi E [d].
Σ Ejec
of cxp
exp
2
2
[[V]
duj ... do:-diid idu+i1 ... dua
(1)
(-11) 22T
(2mr
integration
uf
exp
exp
duj
(1(1) 4 (-1)
22T
2T
jæi
exp
2
(T(1)
((-1)]=-1
(1) ① (-) V2T
2
exp
(0(1) - Φ 1)]
22T
1
exp
22 [_] 22n
2-2 u² du;
2
exp
1 < 1, otherwise P [V.] = 0. Therefore, V; follows the truncated standard normal distribution within (-1
Lemma 14 (Properties of Truncated Gaussian Smoothing). For function Rd R that is L-Lisschitz with respect to the fg norm, then x E IRd.
(i) If f is convex and dinddifferentiable in set with Lebesgue measure then fo is continuously differentiable and fx))) = Ev [0 - pV)) for some random variable V.
(ii) If is convex, fp is convex and I.-liipchitzz with respect to the l norm.
13

---

Published as a conference paper at ICLR 2025
(iii) If f is convex, f(x) S fx(x)= S f(x)+ LpVd.
&
(iv) V is T.-lipschit, i.e, So is T--smooth.
Proof. The proof of this lemma is based on that of Lemma (Duchi al., 2012).
(i) The differentiability is established in (Bertsekas, 1973, Proposition 2.3), and ffp(x) = Ex
pV) in (Bertsekas, 1973, Proposition 2.2).
(ii) Expectation preserves convexity (Boyd & Vandenberghe, 2004, Section 3.2.1), therefore, given that f is convex, by definition, Ip also convex. For Lipschitz continuity, by the second part (i) and Jensen's s inequality, we have
[x)(())]
PVIII
Given that f is L-Lipschitz over Rd with respect to the & norm, it is implied that Vx R [[]](x)]] & L. As result, (x)]l & E[Z] s L which further implies that Sp is L-Lipschitz with respect the &g norm.
(iii) For (x) = Evlf(x + pV)]. [v = 0 by construction. And since smoothing preserves convexity, (x) also convex. For the lower bound, using Jensen's 's inequality,
f(x) = f(x+ + [Vv(V[]
f(Ev + pV1)
S Evif(x + PV)
fx(x).
For the upper bound, since is L-Lipschitz in f2-norm, f(x + pV) f(x) S LllpVl Therefore, fØ(x) Ev [v[s(x + pV)]
S Bv [5())(x + LPI
f(x)) + LpE
Σ V2
S 5(() Lp
E [V
By Lemma 13 (ii), V, follows the standard normal distribution truncated within [-1, 1]. Therefore, let ((-) denote the cumulative distribution function of standard normal distribution, then
Φ(T)
E V?
dt
+(1)
(
+(1) - (
1
((T)
4(1) - (11)-4((11)
E [U3]
+(1) - (D(-1)
for ~ (/(0 1), Vi E [d] Then for U = [U1, Ud)" T, U follows the standard MVN distribution
and
E Σd. U?
fx(x) & f(x) + Lp
((1) 4 (1)
E
|||
= = -LpN
T(1) (--1)
14

---

Published as a conference paper at ICLR 2025
E |||]|] is the second moment of the standard MVN, which is bounded by the dimension d (Nesterov
& Spokoiny, 2017, Lemma 1). We know that (11 +b (111)) z 0.6827. As result, we have
fo(x) S f(x) + Lpvd.
5
4
(iv) The proof of this lemma follows that of Lemma 3.3 point 3 in (Lakshmanan & De Farias, 2008),
also seen in that of Lemma (ii) in (Duchi et al., 2012). Denote the PDF of the unit &x -aal--llttunncc standard MVN as 51 (:; 0, 1). Then for [Λ(x) Bvrs pV)), pV has PDF o1 Ia < (:; 0, p²)
by Lemma (v) in (Chen et al., 2020). By (Duchi al., 2012, Lemma 11), V xx E Rd, for Z from P1l1l (p p²),
[V - Vfp(x')l2 S 10111050l2- -x; (1 xx;,,')0pp) dz.
Now we bound the integral. Note that V x, 011-11 So 0, p²) is truncated MVN symmetrically centered at the origin, consequently. is strictly decreasing with respect to ||x||2? As result, & 1ll1l Sp(zz - x: 0, p²) 2 11 Sp (z- x';0, p²) if and only if ||z - xxl22 S l|z x 1l2. Therefore,
1= 2
(01-1> - x: p²) 51 xx;0,p²)) dz
2 x 12-x'1 1/2
=2 12-x|l1s5 12-x112 122
91 1 x: 0, p2)dz -
112-x|15512-x11 11 11 - x²;0,²²)da
Denote y and y' x', then
-x' 011111 (y: 0, dyy -2 /
I=2
/| /11/1122111' (x- 1 50' pd)
2IP P1ll ~. 11|211e S 6 - (x' - [2 21 0- 21
|||2 [| 1 (x- x') [12]
2IP 2
[1/|] S 2 (x' x)113] 2P 2F Sp
|||2'|| 2 IZ' - (x x x'113
2IP S0
[2 x' - x) < ||x -x1[]] - 2IP 0111
[2 x - x') 2 ||x - x x11
{Zz, ZZ, 1x' x
x -
||' - =x|22
(zzz
x x'x'
x x
11
2IP 22
2P 1
2
2
||x x' 112
normalized vectors, W and W' follow the one-dimensional distribution projected onto a plane along some direction from the truncated multivariate Gaussian, which symmetrically centered at the origin. Therefore, by symmetry,
Denote W = (Z, x and W
Z
Since
x' and -
x 2
x
x
< X
x
2
x
x x'112
T= 2P
W
21
W
2
2
2
xx'
x
x|12
||x'
x l2
X
x||2
x
x'
11
= 2P
W <
+ 2P
W
<
2F
W
>
2
2
2
2
||X
x||2
Xx'
x||2
= 2P
<
W
<
2
2
As we later upper bound the integration by the peak of this distribution, we know by the geometry of loe -bll that the projection onto the diagonal yields the highest peak, and that is when W
Vd Ed Ze for Z being the marginal of Z that follows the truncated Gaussian distribution on
[ by Lemma 13 (ii). And further by Lemma 2 (V) in (Chen et al., 2020), Zn is also a truncated v
Gaussian whose PDF is +1 (,:; 0, 4) As a result, W is the sum of independent identically
Importantly, the PDF is strictly decreasing with respect to ||: not llolloc, no matter in which norm the truncation is done, as long as centered the origin.
15

---

Published as a conference paper at ICLR 2025
distributed (i.i.d.) truncated Gaussian variables. By Theorem 3 in (Chen et al., 2020) and E.q. (4.2) in (Birnbaum & Andrews, 1949) we know the sum truncated Gaussian variables converges to a normal distribution for large d. As result, W [Ei= Var (2.l) N (0, 1). Knowing from the CDF of
(0)=)(()))) }
+()+)(-11 truncated Gaussian that A E [d]. Var [Z,] d -1--
0.7089
we have EEE Var (24)
0.7089p²
1x x2l2
x 2 W
x
x
w²
P
expl
2 x 0.799 |d
2
2
2 0.708pp
1e xl2
Furthermore, since the PDF takes its peak
0, we have
|x xx12
2
I 2
dw
1x'=xll2
41|x 22
2m
Therefore,
[V,(2) - V)o(')|22 - LI
2L
S xxx x 2-
Lemma 1. Given a L-iiischhtz f. the function fb Spl [Splf]]
... satisfies
(i) I is convex, fo is convex and L-Lipschitz with respect to the Eg norm.
(ii) I convex, f(x) S (x(x) $ fxx) + 3 Lpva.
(iii) Vi E [p]. Vx,x Rdd (x) f((''ll $ (3) L||x - -x'I- x'I.
Proof. The proof of this lemma relies on inductively applying Lemma 14 and we provide formal proof by induction.
(i) The base case p holds directly by Lemma 14 (ii). Then we state the hypothesis that for p k, f is convex and I.-Lipschitz with respect the E norm. For the induction step, we have, by definition, f = S where f is convex and L-Lipschitz with respect to the Ez norm by our hypothesis, with which f satisfies the condition of Lemma 14. Then by Lemma 14 (ii), fo+ is convex and L-Lipschitz with respect the & norm.
(ii) The base case = 1 holds directly by Lemma 14 (iii). Then we state the hypothesis that for 5k p= k, f(x) < f% (x) < f(x) + 4 Lpv d holds. From the result of (i), we know that ff satisfies the condition of Lemma 14. Therefore, applying 14 (iii) to the function f (x) we have for the lower bound
fx+ 2 fx)) 2 f(x)
and for the lower bound
(x+ < (x) + _ + LOVE < f(x) + 5k Lpva d + LLvE- f(x) + 5(k + 1)
Lovd
4
4
which completes the induction step.
(iii) The base case p = 1 holds for 0 by Lemma 14 (ii) and for i by Lemma 14 (iv). Now we state the inductive hypothesis that for p = k. it holds that V x, x E R,
3IA [4), | p (x)
v <
( L X(||
16

---

Published as a conference paper at ICLR 2025
That is, V i [k], the function ViSA is ((2) L -Lppshiitz Then + E [k +1.
| 1 - V
(x'Il ||
| S [1x - V15,1/1((X11
|| fx((() - SpIV
= -|Ev/ -IEr|V' (x pV) Ev Ev fx + +VOII
|| f/ (x pV) V V' pVVII
S Ey f (x+ +vV
V 8' + PV)II
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 < k + 1, we can directly apply Lemma 14 (iv), with the hypothesis as the condition, on the function V fo+ to establish the result that V f is smooth with parameter
2 P
L. Therefore,
V pk+1 (x)
f
(x)) || - Ey III V x + pV)
ViS/(x ' + +P)
2
s Ev
L|| x1|
2
T.I|x
x'|
For l + 1, we have from our < k: case that the function 4 pkttt1 is (()) -Lipschitz
can therefore apply Lemma 14 (iv) on V f and claim that it's also smooth with parameter
k L
k+1
2
L. That is,
4+1 L||x x'1,
V
(x)
which completes the proof.
A.2 PROPERTIES OF THE CONSTRUCTED HARD FUNCTION
Lemma V E [T), gr is convex and 1-Lipschitz with respect to the too noom, and also the 22-norm.
Proof. (1) For convexity, by definition have
gx(x) = max (x)
where
A E Eu (ea(k)) x) (k- 1)6,
15k5t
Since (xx linear x, (x) convex. Then Sr (x) is the maximum of convex functions which is also convex.
(2) To show Lipschitzness, x, Rdd, without the loss of generality, denote
h1 arg max TA (x)
K2 arg max TA (y).
15k5t
15kst
Therefore,
9t (x) Fa(tr) - (k: 1)8
9t (y) -Nn (k2 1)6.
Since
Ft (y) Ekg (ecB))(k)) (k2 1)6
max EA (Co(K)) x) (I: 1)8
ISASt
2 ER, (arkk)) (k1 1)0,
17

---

Published as a conference paper at ICLR 2025
have
9r (x) go (y) < (Ex, (a()) (1g -))8 (EA, (a(kk) - (Ki 1)8)
(k()) (y((ka))
max Iz Vil
3and
x y1100
< x 2112:
where the last two inequalities show Lipschitzness in lo and l2 norm respectively.
Lemma 3. A [T], yx E R
(i) Gx(x) is convex and 1 L-pischhizz i.e., Gi(x) Gi(y) & |x -x----- (ii) (x) S G,(x)= & ge (x) + p.pdd.
(iii) For some fixed p E z+ A i E pp. (V) V'GG+>) & (3) ||x yll.
Proof. The proof follows directly from that for Lemma 1.
Lemma 4, For F(x) = fr(x) + (x) where (x) = a |x| and x E Q
(i) F is uniformly convex function with degree q and modulus a > O. 20
(ii) F(x) is pt -order Hölder smooth with parameter H p
Zt
Proof. (i) It is shown in (Nesterov et al., 2018, Section 4.2.2) that _ | is uniformly convex with de- gree and parameter By Lemma 3 (i), GT is convex, therefore f is also convex, that V y, R, (x) ff(y), y) 2 0. Therefore, by Definition 3, (v |||||| 9) V(2 (/>l>>1")) x-y a||x - yl. Adding them together we get (VF(x)- Fyy),, x - y) 2 aa|x - - which shows that Fxx) is uniformly convex function with degree q and modulus
q
0.
(ii) From Lemma 3 (iii) and Definition 1, we know that ʃ is pMh-order smooth with parameter
Lp = (3) (3) .ppe e Zt, ie., Vx,y QC
[V* vPf(y)ll & (2)² |xx ---ll yll.
Also, fs (2) (2) (3)²²
p- p-1
-Lipschitz, which implies that V x E R4, || (²)²² Then
P
we have V x, E ②
[|Vp](x) -V')())-V\((\]] [x
-
- vP
- [V VP (1V*) +1V*>>>))
p- 1-
2 P
2
<
8 xx 11-
28
p
2P3
||x - yl1".
pPtv-I
By letting H 20 8 p we can conclude that f is th -oddr Hölder smooth with parameter 2.
Furthermore, for dg(x), by definition, Q = fx ||||/ & D} for D < H ( and C = aqq - 1) x ... x (g p). As a result,
= 04 - 1) ... (q p)| S C. DP-P-1 This indicates that (x) is -oddr smooth with parameter C. D which is equivalent to xxy E Q.
||
(x),(x) (
dy)l < C. Da-8-111x yll-
18

---

Published as a conference paper at ICLR 2025
Given that ||x y/1 ||x y|l'~"|x y|1" 2 (|x] + Iyyl) lyll) " yll Σ (2D) -0) y we have
H x yll".
yll' -
That is, (x) is -oddr Hölder smooth with parameter H. we conclude that f + d is -order Hölder smooth with parameter H on domain Q
H -order Hölder smooth with parameter 2 on domain 2. Since f is also pdh -ordr
T
Lemma 5. For R(x) 3 ma]] & (Co(k)) x) : [|x|11 we have
5
R(x) B( 1)8 & F(x) S R(x) p3pVd.
Proof. Since F(x) is constructed with softmax smoothing, we are now able characterize it with the properties in Lemma 3. F(x) can be upper bounded using the second inequality of Lemma 3 (ii):
F(x) = (xr(x) + a |
s (xr(x) + pp3 - -11
max { Ex (Co(H): x) - (k 1)6} -p8pVd+ - |
kE(T]
< 8 max &u (Ba(k)) x) + ppppvd |x||"
kE(T]
F(x) can be lower bounded using the first inequality of Lemma 3 (ii):
F(x) = (x)(x) + |>/||
2 3gr(x)) (x)
|x|
3 max {EA ( (Ba(k)) x) (k: 1)6} - [||
kE(T]
9
2 8 max & (Ca(k)) x) (T - 1)0 + |x|
kE[T]
Lemma 7. F(xT) - F(x') - 1p3pvd 9-1
8r
oor
Proof.
F(x") = min Fxx)
5 I min R(x) pppvd
=min { { max & (Ca(K)) x) + |x|| + 5 RE(T)
Define
= maxke|m EN (Co(K), x){. Then by symmetry (Doikov, 2022),
||x| T277.
As result,
min R(x) min
8 max En (ea(K), x) kE(T)
|x||
x
x
min ( T
720
g
y -
1
39
q
oT
19

---

Published as a conference paper at ICLR 2025
Therefore,
F(x)) q g
5 ppspv
+
q
oT
Furthermore, for some X7 generated following some algorithm A along some trajectory, by definition,
gr(xT) 2 (ea(T)) xT) - (T' - 1)8
2 (T - 1)6.
Therefore,
F(xT) f(XT) + -||x||10
f(XT)
(GT(xTT)
2 (xr(
(Lemma 3 (ii)
3(T 1)6.
Given the upper bound on F(x*), we have
5
8
F(XT) - -T 1)8 T d+
oTT
q
B PROOF FOR TECHNICAL LEMMAS IN SECTION 5
Lemma 8. x" arg miny fxx), y arg min, f(x). (i) Vi [T]. (v., x*) = (ii) ||x*
|
Proof. (i) By definition. f is scaling and rotation of f. Since VI." Vig we can write for V [ Vyl. fxx) ppt.: (VVx). Therefore,
arg min f(x)
x
V arg min f(Vx)
V mig f(x)
Vx".
(ii) This can be shown in the same way as (Arjevani et al., 2019, Lemma 6).
Lemma 9. fxx is (i) uniformly convex with degree and parameter a. (ii) pth order Hölder smooth with degree v and parameter H.
Proof. (i) The proof similar to that for Lemma 4 (i).
(ii) Without the loss of generality, let the basis that defines be the standard basis. E [ denote
e, the tth vector in the standard basis. Denote function g(xr) p+v far p+v g(P) the p -rrdr
I
derivative of (x) is (p + v 1)k=" if p is odd, (p + v- 1) is even. Let d, e; e then
f
H
f(x) 20tu+1 (p + 1)!
g(dd x)) 700
|
4+v
q
20

---

Published as a conference paper at ICLR 2025
Since q < p + v, then q p. Therefore, Vx, y E R,,
T
-
H 2 V 1)!
g
(fde, ()) - 9 ((d,, زا)| [dP|||
1=1
H(p -v-1+ 1)!
(d, x [d,1
20tut (p + v/ - -1)!
H
20+0+1 V2 y11 | [d.1"]
H
20+++1 /2|xx 2
H|x yll".
Lemma 15. For y = arg min f(x).
(0) in 2 U2 2 ... 2 y/ 2 0.
(ii) Mt+1 = V/- (1 - - Σラ= 8/)
(iii) Σ Vi --
Proof. (i) The proof is similar (Arjevani et al., 2019, Lemma 1), relying on the fact that fis strictly convex, which holds true for our higher-order construction as well, since the function is uniformly convex.
(ii)
111 1/2 1tvー (y1 y2) - + ølly 1
1//2
4/1
p-v-2
(y/2 011 + 192 ys! 2-レー2 (02 Bs) + +
Vi())
p+v-2
(Nf 1/8 22) + 1 V/ ptv-2 (19ー1 - yo) + 111y118-2211
197-1 - 1/
pp (yz yア- + 8111r|10 yr
V/ V
Given that 11 2 922 2 ... 2 V/ 2 0, we have Vi E [ 1], l/, - Mit1l = - 1i+1 Therefore,
with f(y) O, we have
(y1 22 v2 p- 7 o ø|1y| 1 1/1
(2)
(Ui-1 - 1/ p-v- = (y:: - y/+ p-u- + 3 yi, 25isT 1,
(3)
(97-1 pー = ã /||y|| 2 yy.
(4)
Summing Eq. (2) and (3), we have
(y: - ) =-- -7-ōlyyl"
Σ Uj
5=1
which completes the proof.
(iii) We know from part (ii) that
--1 (17ー1 - -7t = - -11y|| 9-2
Σ y/
1=1
Grouping this with Eq. (4), we have ā - yz 7 - -ō11y|10-22 ー 1 My. which yields the desired result.
21

---

Published as a conference paper at ICLR 2025
Lemma 11. || < 2 2 y (++2 (2)
Proof. By Lemma 15 (iii) and Lemma 10 (i),
| z |
d
= max Wal x (E[T]
Σ
y
1=1
= y1 x
y/
1=1
27 p
7 +1
V
011yy|0-2
x
ō
27 2y
01
ã 011y|10-2
Let 7 2 (351ly|1-22)
31 2/2
then we have
36 yパ 2 and moreover
p
2 1, so that we
can merge the terms as follows:
2 S
||y| z
37 |y| +
7 /|
/ly|
y Piu 2 2!""
+ v2
3
3 | 1ل
8(p4m)-2
27
<
3/v 27 |
σ x
3(p-o)-2 -2 27 16
39-2
3(ptr) -2
We can solve for ||y|| S
2 3q 7
(p- 1)(3-223
39-
Lemma 10. For - arg minx f(x).
(i) Vt E [T], Ve 21 - (t - 1) p+
ypti-1 +1 81 S 7010 + V 2, zto
(ii) For i
21
8|1y||1-2
(iii) For 2 20r03 ||
(etu- 1)fy 21 p
Vt E [7], y: 21t
+ (t - 1) g
à ||y 2
Proof. (i) By Lemma 15 (ii), Vie [7]
i-1
y/4 = V:-1 - 1- -2
y/
5m1
2 Vi-! 1 - 7plrn
2 セı (i- 1)7
in which the first inequality follows from Lemma 15 (i) that Vi E [2]] y: 2 O, and the second inequality follows from applying the first inequality recursively.
22

---

Published as a conference paper at ICLR 2025
(ii) It follows from part (i) that
Σ yk
max 0.:91 -i- 1)y
For T
+1 1
1, we always have y11 - -IT 1 0. Consequently,
W [ 1/1 - (i- - 1)7 p 2 O. Therefore.
f
f
Σ
y1
2
Σ
y1 (i - 1) 1
1=1
i=1
/ +1
11 (i - 1)
(1-
(1
1
+1
-1
y1
7
21
7 p+u-t
v1
+ 1
2
1
91
1PP-1
1/1
7y -
2
yi
Vi
1/1
7 ア+4ー1
2-y p+レーd
2
1/1
1/1
2
Combining with Lemma 15 (iii) that Σi=1 1/
7
we have
Σ
V1
y1
δ 1-
=
y/s 2
2
1=1
Equivalently.
2 piv
1/2 1 1/1
7 ō||y|| 9-- 5.0
By the quadratic formula, we have
+
7 p
87 p43-T +
9-2
91 <
2
giv
+ 7
2
+
-
2
2 Ā-uー
7 -
||yy|| 5-2
(iii) Since Σ Σ1=1 V/
~ 2, 3 to E [T] such that Eie y/ (1 2" 7 and Vt < to.
Ei.1% V: < (1 .-
| z. Then V to. merge the terms in Lemma 15 (ii) as
23

---

Published as a conference paper at ICLR 2025
follows:
viv
11101yy110-
Vi+1 = yi -
5=1
1
p40-1
S Vi
7 (1
2 }7
y/i
2
Applying this relation recursively, we have
7pt--
7 P+0-1
yta I l/to
.... y1 - (lg - 1)
2
2
Given that yt, 2 0, this yields y1 2 (4o 1) y F-u-T
2
Now we characterize to. By definition, we have Eie y > (1 2 1) 1
7
In the meantime,
Vi
1/1
1=1
1001
2 p-o
S to p
where the first inequality follows from Lemma 15 (i) and the second from part (ii). Together, we have
(1 201 1 01 < to y + +
24---1 |y|l from which we solve for
(2P-w-1 1
to 2 Ø||y||0-2+ + v 28 2
utv-
11y10--2
Plugging this characterization of back in,
v1 2 (4o 1) 2
2
(2 1)y
20tv-1
ō 0|1y||9-2 + v 2200 ptu-2
||y||
2
(20-2-1 1)7
7 p
2p+++1
ō||y||8-2+ + V 2 2/ج ||y||--2
2
Finally, plugging this into the result from part (i), Vi [7].
y1 2 96 (i- 1)7
(20+v-1 1)y
7 -
(i 1
20+u+1 011y||a-2+ + 22 7 1|y|10-2
(20+4-1 1)7
(1 - y yotー-
+
2
-- + / 2200 カ-リー ||y||0-2
24

---

Published as a conference paper at ICLR 2025
By letting y 2 Optt~ are able merge the terms follows:
p
ly
(pt Diy 2) サfu-2
as stated in the condition, we have y
2 511y/|1~ and
(20tv-1- - 1/7
1 -1)
Y:
y pسuー
(011y)11-2) (ālly|10-) + (2(011y11102)8 (2
20+++1
(2ptD-1- 1)7
+
2 - i y
(8115|11228 ( & + (2 2 (ト
2ptu+1
(2 1)y
1 - i yيuي
1
(1+v2)(6) (olyy|11)))) ()5+)4)*)
204441 (1
[[ppv-11
2 (1-)
20tut104 |X|| 272 +
your
Lemma 12. For y arg min& f(x), let E [T] be such that yo pto-rōrio | > and
Ul++1 S p+v-1 8 काد ||y|| 2. Then
(i) Vi E [T]. Vi Vi+1 6
Ej-(+1 83
and Di+1 -
p-v-1
(ii) Vi 2 t Gp..
y 2 Ui
pto-l S v where Cp,u is a constant depending on p, V.
(ii) Vi < f 11 t/
(ā11y11-22) =T (p -1) 1))-(tt-1)',
Cp.
Proof. (i) Starting from Lemma 15 (i), Vi E E
p+u-1
y1 = yi+1 +
7- - ö|ly|
yj
1=1
T
T
p40-1
= -i+tt +
7 7-2lly Ø|ly| 1 19-2 Σ
Uj + +811y|19-2
Σ yj
1=1
1=i+1
F
1t0-1
= -Vi+1 +
7 1118lyy10 19
T o|yy 1 9-2
7
+ 1 9-2
Σ
yj
(Lemma 15 (ii))
jmi+1
Σ yj
= -i++1* +
j=i+1
Since 1441 2 0, we have
F
011
Σ V/
j=1+1
(611y|10221+++)
1i++1)
equivalently,
1
Vi+1
/1
25

---

Published as a conference paper at ICLR 2025
(ii)
f
Mj Vi+1 + 1/442 + .... y/
j=1-1
1 p+u-1
1p 1)2
$ Ui+ +
olly|1 9-2 Vi+1
(ō ly 9| 9- 2) (ptv 1)+1 8
(ptu 1) 1
(ōly|1 - - 11+μ-1)
(ō
7-i-1
yi++
Yi+1
y p-v-
Given that i 2 4, then i + 12 4 + 1 and by Lemma 15 (i) and part (ii) of this lemma, Vi+1 S +1 I p+2-1 t アサーー ||y p-u-2 Therefore,
(0+v-1)²-1
f-i-1
p+u- Ootira ||y| 9-2 340-2
Σ j=++1
yj S Vi+1
Σ
y
j=0
f-1-1
1
= (p+ + 1)9(+1
(p+ v 1)6tt-11)
==
P+V
(p + V/ - 2) 2)2 Vi+1
With this, we go back to part (i), for Mit1 S p+ م ||y| 3
1
I
V1 2441 +
01
Σ
yi
1=i+1
P - 1
PTO-1
$ 44++ +
(p+v 2)² 0 11y/11-22/6+1
pbv-2
pto-1
v
Vit1
ptv-1
(p+v 2)2 1 2/+1
p v v + #(
I I 1
p ||y|| معuيم
1p+r -ー 2)2 -= 31111111~2 y1+11
p+
(1+ (
2-p-v
p+リ-1
(ōlly|1-~2 नमेي
2)²
Cp. (ö1ly)1 p+i-a
for Cp = ((+t--1)ztt)
2ーpーy
ptp-l (+t--2
Therefore, gi+1 >
p
26

---

Published as a conference paper at ICLR 2025
(ii Vi $ T - t1 + 11, therefore, applying part (ii) recursively yields
p+レー1
(Vt,+i-1 joto-1
yt 2
5 0
Cp.e
1ptt-1)2+(pta
(Ve+ti 2) ((te-1)2
Cp.v
(ā ( 22p+
(p+u- -1)
ai 1)+
p4u-2
Cp.l
(ō 2)
(p-v-1)i-1 ptレ-2
By the definition of 11, know that yt, p+u- 7 rtuia
||y|| piv- Thus
||y मी (0tv-1)
(ott--((pte-D--- (pto-1)-1
Misti 2
Cp,p
loto 11 (ō11y|1--2)
(ple Di 1) p-1-2
1
( مमتं (p+2 10(+-=-1)
Cp.u
27


Reviews:
[{"review_id": "sy0OMXxIGQ", "reviewer": "Reviewer_JCuX", "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.", "questions": "How might future work address the remaining case of $q = p + \\nu$, and what specific challenges are anticipated?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "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.", "weaknesses": "The paper does not cover the case of $q= p + \\nu$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DMXwuzF2cB", "reviewer": "Reviewer_JCi9", "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.", "questions": "Is the norm in $||\\nabla^i f||$ (in line 201 and many other places) the operator norm?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 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.", "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. \n\n\n[1] Nikita Doikov. Lower complexity bounds for minimizing regularized functions. arXiv preprint arXiv:2202.04545, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jLWl5J2Mdj", "reviewer": "Reviewer_ApvT", "summary": "The paper studies oracle complexity lower bounds for optimizing highly-smooth uniformly-convex functions with high-order methods.\n\nTight 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.", "questions": "## Two inaccuracies\nI recommend to slightly revise the paper according to the following points:\n\n1) 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.\n\n2) 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. \n\n## Additional question\n- 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.\n\n\n## Minor comments\n- Notation: $\\|\\cdot\\|$ refers to operator $\\ell_2$ norms, maybe should emphasize this (just adding the word \"operator\") to avoid confusion with Frobenius l2.\n- Lemma 1 (i) - the authors probably forgot to assume the function is $L$-Lipschitz.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "This paper is well written. The results are motivated, well-explained and well-situated with respect to prior work.\n\nI 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.\n\nI haven't checked the math too carefully, but the authors make convincing points so that I believe the results should be solid.", "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.\n\nPersonally, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wCuZspLWNm", "reviewer": "Reviewer_srAx", "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.", "questions": "Please reference the weaknesses for my questions.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 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.\n* 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.", "weaknesses": "The main issue for me that causes confusion in section 4, concerning case (1) $q>p+v$ is the following:\n\n* 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.\n\nIn several places in the paper there are potentially typos that cause me confusion both in the main part and in the appendix. More specifically:\n\n__Line 783__ $\\rightarrow$ you say $1/\\sqrt{d}$ is a truncated Gaussian, I think you meant to say $Z_i/\\sqrt{d}$\n\n__Line 230__ $\\rightarrow$ I think it should be Lemma 1, not Lemma 14 according to the derivation in the appendix as well.\n\n__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?\n\n__Line 293__ $\\rightarrow$ I believe here that $x_t$ should be $x_s$.\n\n__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.\n\n__Line 317__ $\\rightarrow$ Lemma 14 should be Lemma 1 here or am I mistaken?\n\n__Line 1011__ $\\rightarrow$ Similar to 296 it should be $\\geq$ or am I mistaken here again?\n\n__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.\n\nFor 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.\n\nI 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.\n\n[1] Universal Gradient Methods for Stochastic Convex Optimization", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)