Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
Authors: Ankit Garg
Robin Kothari
Praneeth Netrapalli
Suhail Sherif
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Convex optimization
Oracle complexity
Lower bounds
Acceleration

Abstract: We study the complexity of optimizing highly smooth convex functions. For a positive integer $p$, we want to find an $\epsilon$-approximate minimum of a convex function $f$, given oracle access to the function and its first $p$ derivatives, assuming that the $p$th derivative of $f$ is Lipschitz.
 
Recently, three independent research groups (Jiang et al., PLMR 2019; Gasnikov et al., PLMR 2019; Bubeck et al., PLMR 2019) developed a new algorithm that solves this problem with $\widetilde{O}\left(1/\epsilon^{\frac{2}{3p+1}}\right)$ oracle calls for constant $p$. This is known to be optimal (up to log factors) for deterministic algorithms, but known lower bounds for randomized algorithms do not match this bound. We prove a new lower bound that matches this bound (up to log factors), and holds not only for randomized algorithms, but also for quantum algorithms.


Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
Ankit Garg Microsoft Research India Bengaluru, KA, India gar pargammicrosoft. com
Robin Kothari
Microsoft Quantum and Microsoft Research Redmond, WA, USA
robin.kothar www.aokthhrriie fitchari@miie crosoft.commmmmmooo..oom com
Praneeth Netrapalli Google Research India Bengaluru, KA, India praneethn@gmail com
Suhail Sherif Vector Institute
Toronto, ON, Canada
suha il Scheriffee ffffmiggaal...m com
Abstract
We study the complexity optimizing highly smooth convex functions. For a positive integer p, we want to find an e-approximate minimum of convex function f. given oracle access to the function and its first p derivatives, assuming that the pth derivative of f is Lipschitz.
Recently, three independent research groups (Jiang et al., PLMR 2019; Gasnikov et al., PLMR 2019; Bubeck et al., PLMR 2019) developed new algorithm that solves this problem with O(1/e5111 oracle calls for constant p. This is known to optimal (up log factors) for deterministic algorithms, but known lower bounds for randomized algorithms do not match this bound. We prove new lower bound that matches this bound (up log factors), and holds only for randomized algorithms, but also quantum algorithms.
Introduction
In recent years, several optimization algorithms have been proposed, especially for machine learning problems, that achieve improved performance by exploiting the smoothness of the function to be optimized. Specifically, these algorithms have better performance when the function's first, second, or
higher order derivatives are Lipschitz [Ne008 Bae09] MS13 19s19
GDG 19 JWZ19 19b).
In this paper we study the problem of minimizing highly smooth convex function given black-box access to the function and its higher order derivatives. The simplest example of the family of problems consider here is the problem of approximately minimizing a convex function f R - R. given access to an oracle that on input I E R outputs (f(z), V fx)), under the assumption that the function's s first derivative, its gradient V.f. has bounded Lipschitz constant. This problem can be solved by Nesterov's 's accelerated gradient descent, and it is known that this algorithm is optimal (in high dimension) among deterministic and randomized algorithms (Nes83 NY83..
More generally, for any positive integer consider the pth-order optimization problem: For known R > 0, 0, and I.p 0, have a p times differentiable convex function f R R whose pth derivative has Lipschitz constant at most Lp, which means
V f(x) V f())ll < 1 - vll.
(1)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where ||-I| is the &g norm (for vectors) or induced Eg norm (for operators). Our goal is to find an e-approximate minimum of this function in ball of radius R, which any that satisfies
f(x")
min #0)
((x) S,
where (0) is the fz-ball of radius around the origin. We can access the function / through a pth order oracle, which when queried with point E R" outputs
(f(z),
(3)
As usual, 4 (z) denotes the pth derivative of f(z).
Our primary object of study will be the minimum query cost of an algorithm that solves the problem, i.e. the number of queries (or calls) to the oracle in eq. (3) that an algorithm has to make _ For fixed it seems like this problem has 4 independent parameters, not all independent since we can scale the input and output spaces of the function to affect the latter parameters. Thus the complexity of any algorithm can be written In this paper we focus on the high-dimensional setting where n may be much larger than the other parameters, and the best algorithms in this regime have complexity that only depends on Rp /e with no dependence on 72
Ly. R, and c, but the parameters are
function of n. and Lp [/ /e.
As noted, the = 1 problem has been studied since the early 80s [Ne883, NY83, and the > 1 problem has also been considered [Nes08] MS13. In an exciting recent development, new algorithms were proposed for all (with very similar complexity) by three independent groups of researchers: Gasnikov, Dvurechensky. Gorbunov, Vorontsova, Selikhanovych, and Uribe [GDG+ 19]: Jiang, Wang.
and Zhang [JWZ19]; Bubeck, Jiang, Lee, Li and Sidford [BJL 19b). deterministic algorithms that make
All three groups develop
Öp ((L,,ort) /e) (efppt1/)2//00//1) 22((pp21)
(4)
oracle calls Fl where the subscript p in the big Oh (or big Omega) notation means the constant in the big Oh can depend on p. other words, this notation means that we treat p as constant. This improved upon the bounds of [Bac09] Nes19]; both the works develop deterministic algorithms that make
Öb /c)
(5)
oracle calls.
This algorithm is nearly optimal among deterministic algorithms, since the works [Nes19]
ASS19 showed that any deterministic algorithm that solves this problem must make
Op (T,,p 1c) 2/(3x(1)) (2) queries. However, for randomized algorithms, the known lower bound weaker. Agarwal and Hazan [AH18] showed that any randomized algorithm must make
2p (LLg, /e) 2)(pt))))))))
(6)
queries. To the best of our knowledge, lower bounds are known in the setting of high-dimensional smooth convex optimization against quantum algorithms, although quantum lower bounds are known in the low-dimensional setting (CCLW20 vAAGGW20) and for non-smooth convex optimiza- tion [GKNS21].
In this work, we close the gap (up to log factors) between the known algorithm and randomized lower bound for all p. Furthermore, our lower bound also holds against quantum algorithms.
Theorem 1. Fix any p E N. For all > 0, R > 0, Lp > O, there exists an n > 0 and set of n-dimensional functions F with pth-order Lipschitz constant Lp (i.e., satisfying eq. (1) such that any randomized or quantum algorithm that outputs an e-approximate minimum (satisfying eg. (2)
for any function f E F must make
S2p RI. 1c) (2)-11/622/000)/ 2/(p+2))
(log I.p Re+ /c) 12)-1
queries to a pth order oracle for ff (as eg. (3)
For simplicity assume that the oracle's output computed to arbitrarily many bits of precision. This only makes our results stronger, since we prove lower bounds this paper.
NNote that the query complexity does not have any dependence on the dimension n. Of course, actually implementing each query will take (rly(r)) time, but we only count the number of queries here.

---

In fact, this lower bound holds even against highly parallel randomized algorithms, where the algorithm can make poly(n, L queries in each round and we only count the total number of query rounds (and not the total number of queries). See [BJI+ for previous work in this setting, including speedups for first-order convex optimization the low dimensional setring.
In this introduction, we have deliberately avoided explaining the quantum model of computation make the results accessible readers without background in quantum computing. The entire paper is written so that the randomized lower bound is fully accessible to any reader who does not wish to understand the quantum model and quantum lower bound. For readers familiar with quantum computing, we note that the only thing to be changed to get the quantum model is to modify the oracle in lqq. (3) to support queries in quantum superposition. This is done in the usual way, by defining unitary implementation of the oracle, which allows quantum algorithms to make superposition queries and potentially solve the problem more efficiently than randomized algorithms.
2 High level overview
Let us first consider the lower bound against randomized algorithms. Let us also first look at the special setting of p = 0 where we still assume access to the gradient (or = 1) oracle. To be more precise, the oracle returns subgradients, since gradients need not be defined all points for Lipschitz convex functions. For this setting, known popularly as nonsmooth convex optimization, the optimal lower bound of Ω (.3 is in fact a classical result [Y83]. The proof of this result is very elegant and has been used subsequently to prove several other related lower bounds such as for parallel randomized algorithms [Nm944), quantum algorithms [KKNS2]] etc. Since our proof builds on this framework, we now review this.
Nonsmooth lower bound instance. The lower bound instance for nonsmooth convex optimization is minj (x) where fv I - IR is chosen as
fv(x) max (v) x)) + (k- 1)% sE(k]
with k - (x>))) - (v) and (wI, 0k) comprises orthonormal vectors chosen uniformly random. The argument essentially shows that
in order to find a O approximate minimizer, one needs to know all the uy 's, and
(ii) with high probability, each query reveals at most one new vector
This yields lower bound of A queries for achieving an error of O Since f is a 1-Lipschitz function, when we rewrite this bound in terms of error, it yields the Q randomized lower bound. For the p- 1 setting, known popularly as smooth convex optimization, the optimal lower bound Ω also classical result originally proven in NY83 However, the proof of this result in NY83 is quite complicated and is not widely known. The recent papers of GN15 DG20] provide much simpler proof of the p = 1 result by using the lower bound construction for p = 0 setting described above and using smoothing, which we now review.
Smoothing refers the process of approximating given Lipschitz function f by another function which has Lipschitz continuous nd derivatives for some p 2 1. Further, since we will be applying this operation to (8), we will describe smoothing in this context.
Smoothing.
Definition 1. An operator S which takes 1 LLipschitz,uucctinn f to another convex function Sif] is called a (p. B, e) -mooohinig operation if it satisfies the following:
1. Smoothness: thhh derivatives of S(S) are Lipschitz continuous with parameter and
2. Approximation: For any x, we have (f(x) S1f]()) S..
If design smoothing operation per the above definition with e O (1/VR) and further ensure that property (ii) above i.c., with high probability, each query the first p derivatives of S(
3

---

reveals at most one new vector ti. then the proof strategy of lower bound for nonsmooth convex optimization can be executed on the smoothed instance S( there by giving us a lower bound for -order smooth convex optimization. This is the key idea of [GNI5] DG20 Further, the smaller / is, the better the bound we obtain. However, since f can have discontinuous y derivatives, there is a tension between the approximation property which tries to keep S( close to f and the smoothness property. So, one cannot make B very small after fixing O(1/Vk). For the rest of this section, fix O(1/v)()))))))) in Definition 1
For the p = 1 setting, there is a well-known smoothing operation known as Moreau/inf-comm smoothing [CCI]. which obtains the best possible smoothing with B = ((k..)). This gives the tight query lower bound of ? for smooth convex optimization.
However, there is known generalization of inf-conv smoothing for p 2, one needs use different smoothing operator to extend this proof strategy for proving query lower bounds for higher order smooth convex optimization. Given any p 2 [AHI8] indeed construct such smoothing, called randomized smoothing which maps Lipschitz convex functions to convex functions with Lipschitz pd derivatives. In the general p 2 setting, smoothing operator with 3 = O (k=sp/2)
would give the optimal lower bound of ? (P+T
However, the randomized smoothing of [AHI8)
can obtain only 3 = O (//)/22 leading to suboptimal Ω convex optimization.
T lower bound for pd order smooth
We design an improved smoothing operation, for the specific class of functions in Equation (8) with the optimal / = O (k:3/22) using two key ideas. The first idea is the softmax function with
(+)) where 2 E R If we apply smaxp.
parameter defined as szaxp(z) == plog EiE( exp
with p - 3/2 functions of the form (8) through:
x)) + (k +
1177
smax,(vecr(x)) = plogg
Σ exp KE(A]
where vecy (z)
((1). + (k- 1)7, (2), + (k- 2)...... (Uk, 2)), we can show that smax, (x)) satisfies Definition 1 with the optimal value of 3 O (23p/2). However, any
query on derivatives of smax, (maxx (vec reveals information about all the vectors e simultancously
since for instance the gradient is given by
exp (11,2) (k--)
Vsmax, (x)) = Σ
2/.-
(10)
Eje( exp (1
RE[K]
Consequently, it cannot be directly used to obtain a lower bound. The second idea is that even though the function value and derivatives of (vax, (z:) have contribution from all u, ss the contribution
is heavily dominated (i.e., up to poly(k) error) by (x)),, where i*x)) = argmax,e(M) x) i)7,
whenever (M=+()); + (k- i" (x)) > (u;, x) + (k- - 1)7 + 2(p log k) for every + i (x)).
Based on this insight, we design a new 1-Lipschitz convex function given by h(x)) == max (x( where f((x) = smax S (vecv (x:) + p(k - i)n for an appropriate a to be chosen later, where smax (v)c = plog Eyeli exp (1)=))+((-(7))) The key property satisfied by fa is that fi = fj implies that Vf. ff, for any i,j. This implies that near points of discontinuous gradients for h i.e., points where argmax;e]1] fa(x:) changes, the resulting discontinuity in Vh(x))
O (oly(a)): ). In contrast, the change in gradients of the original instance fv(x) near points of discontinuity is (2)). If we apply randomized smoothing to h. the resulting function then be shown to have Tdhh order Lipschitz constant Ô (1-30/2). The precise details, proved in Lemma 4 are technical and form the bulk of this paper. The same proof strategy immediately yields the same bound on the number of rounds for parallel randomized algorithms as long as the number of queries in each round is at most poly(k). The reason is that poly (k) queries are still not sufficient to obtain information about more than one vector per round. Finally, the same proof strategy can be adapted to the quantum setting using the hybrid argument [BBBV97]. See Appendix C for more details.

---

Smoothing preliminaries
In this section we look at some smoothing functions and their properties. The proofs of these properties can be found in Appendix A
Let (x(2)) (y R" lly - =|I S n) be the ball of radius around x R" t Definition 2 (Randomized smoothing). For any function f : RR and real-valued rj > O, the randomized smoothing operator S, produces a new function S, IR" + R from f with the same domain and range, defined as
S,]f[(>)= = vEB,(())
[f(y)]-
(11)
This smoothing turns non-smooth functions into smooth functions. If we start with a function f that is Lipschitz, then after randomized smoothing, the resulting function's 's first derivative will be defined and Lipschitz [AHI8]. Since we want to construct functions with derivatives, we define p-fold version of randomized smoothing. Recall that p is the same p as in the introduction (i.e., are proving lower bounds on the pth order optimization problem). This operation also depends on parameter /3 that we will fix later.
Definition (Smoothing). The smoothing operator S on input f R R outputs the function
Sif] S3/2r ( (5 [f]]...]]
(12)
The main properties we require from this smoothing are as follows.
Lemma 1. For the smoothing operator S defined above, the following statements hold true.
1. For any functions f.g R R. for which S(f),Sig) are well-defined, Sif gl
S[f] + S[gg).
2. The value (z)( only depends on the values of f within (1-2-P)3 radius of x.
3. The gradient and higher order derivatives of S(S) at depend only on the values of f within (ạ(x).
4. If f L-Lipschitz ball of radius B around x, then S also L-Lipschitz æ.
5. Let f be G-Lipschitz in a ball of radius around x. Then Sif) p-times differentiable, and for any S [ is T--Lipschitz in 3/22-ball around x with T. 5 n'246441/2
G.
8
6. Let f be G-Lipschitz in ball of radius B around x. Then (S(](x) - f(x)) s gG.
7. If [ is a convex function, then SIS) is also convex function.
We also use the softmax function introduced earlier.
Definition 4 (Softmax). For a real number p. the function smax, R" R defined as
smax,(z) = plnn Σ
exp(x</p)).
(13)
(E(m)
Let us also define, for m S n, smax Smh
Ras
smax smax, (m)m), or equivalently, smax (m (x) =pn= Σ
exp(xx/p))
(14)
[m(m]
We note the following smoothness properties of softmax. Lemma 2. The following are true of the function smax, for any p > 0.
1. The first derivative of smax can be computed as
@smaxp(x)
exp(s:/p)
(15)
Ox:
exp(xa/p))
5

---

2. smaxp is 1- L-Lipschitz and convex.
3. The higher-order derivatives of smax satisfy
p+1
p+1
p!
in(p+2)
s ssmaxp(y)l
|
vll-
(16)
p
will also need the following lemma which roughly states that smax(x)) and smaxS" (x) are nearly the same, then their gradients are also nearly the same at x.
Lemma 3. Let I E IR" and m < n.. If
smaxp(x) smax, mm
x 8 < 1
p
(17)
P
Then
Vsmaxp(>)
Vsmax (ammax"(())))) (T))]] S 48.
(18)
4 Function construction and properties
In this section we define the class of functions used in our randomized (and quantum) lower bound, and state the properties of the function that will be exploited in the lower bound. Some proof's have been moved to Appendix B due to space constraints.
Let & N, Y. P, E R be parameters to be defined shortly. i and parameters used in the high level overview (Equation (8)). 33 is the parameter required to define and is the parameter used in the definition of smax.
Function construction. Given list of orthonormal vectors "i....,,% 2k E IR",, which we collectively call V. we recall that vecy (z) E I denotes the vector
vecy (x) = (fv), 2) + (k: 1)7, (u2, x) + (k - .).... x)).
(19)
We can now define our hard function class as follows.
Definition 5. Let V = (v1,..., Uk) ) Rn. be of orthonormal vectors. The functions fú, .... Su. and depend on V as follows. Define, for each E [k], the function fe IR - lR as
fi(x) smax,'' ((vey (x)) + p(k a
(20)
Define h(x) max4e1k f((z). and g(x) (z).
Note that in the above definition apply the smax functions vecy (x) and not on However, since vecy (a) is obtained by applying unitary transform on æ and then translating it, the observations about smax(r) in Lemmas [ndd 3 also hold for (max(vecv
We set 7 / In k [(0.1/7)2/3] (or R 0.1/kvR). p 7/100a In = ann,a
p 1.
Function properties. We now state some properties the function that will be used show the lower bounds.
Lemma 4. For any choice of V, the function g is convex, p-times differentiable and satisfies 4 (())l < Lp][x - yll
||V (z)
(21)
where Lp < (0,(633// (l)))))
The proof relies on the fact that smax is smooth and hence each fo is smooth. If f; for a particular
i in f-neighborhood of z, then g = S Shh would also be smooth (by Lemma item 4). If h depends on multiple f&s in a (--eiigborroood of ær then we know that at least two softmax's involved definitions of the fis have nearly the same value in the neighborhood of and by Lemma 3 they have nearly the same gradient. This makes h nearly smooth, which will allow us to say that g is smooth at (by Lemma item 5).
the

---

Proof. Each fi is an instance of softmax applied to vecy (z) plus a constant. Since vecy (æ) is the vector x transformed by unitary and then translated. the smoothness and convexity properties of smax, also apply to ft. Hence each Si is convex, p-times differentiable and its pth derivatives are (ll="))-.ipschtz/ (see Lemma 2). The function h, being a maximum over convex functions, also convex. By the properties of the smoothing operator S Lemma 1. the function g = S(h) is also convex.
Let E R _ E [b] be the minimum number such that there is a point y E B3(x) for which h(y) = fv)). We can rewrite h as follows: h(2) fy(2) max,>} (f((2) - f2)). We call fz(2) the smooth term and max;>)(f(<z)
(=)) the non-smooth term. We know that fy has an Op(p -) upper bound on the Lipschitzness of its p-th order derivatives. If all points y E Bg (x) satisfy h(y) = (y)). then the non-smoote term is 0 and so it does not change the smoothness of h. g [h] will maintain this smoothness (see item Lemma 1).
the non-smooth term is non-zero at some point in (x), then we wish to show that the non-smooth term has small Lipschitz constant in (2(2). This would imply, via item 5 of Lffma that the p-th order derivative of the smoothing of the non-smooth term with S would have a small Lipschitz constant. Towards this let x' be any point in (x(x). Let Ly be the set Eie [k]]/(z') = (x(x)) The set of subgradients of the non-smooth term at x' is the convex hull of (V(J: 11)("")
So if we show that for an arbitrary E T(x'), [ (z)=)))) S L,, then we know that the non-smooth part is T--Lipschitz x'. If j. then the gradient is zero. Let take an i * j (since is the smallest, fact > j). By convexity of the ball and the continuity of fa and fz. there must be point
y in (x) for which (yy f(()) (y). Note that x' B22
The statement fi(y) = fv) translates to
smax (v)) smax
S (vecy (y)) = =ii j)m a << 1.
(22)
P
Expanding the expression for smaxs' and smax we get
(g.we) + (Ak- f)71
smax (eee'"veeee (vecy (y)) smax E (vecy (v))
i=1 exp
ln
(23)
P
1=1 exp
(ywre) +(k- f)7
((b
Ei=jt1 exp
=In
1+
P
(24)
(
A= exp
Since ||o' - y/| S 2/9, we have that (xx,, (y.w)) w)1 S 2,3 for any unit vector Hence
smax E (vecy (x') smax (vecy (z'))
2810 Etes+1 exp
(K--))
< In
1+
P
23 Ei exp
((.z))((--E1)
(25)
For all <> 0, In(1 + A3/0c) S c48/0 In(1 + c). So we can conclude from the above that
smax mmax$t(vecss (vecy(((v))' smax S (vecy (x') < (i (i-j) j)n (i--)e 4810.
(26)
Now by Lemma 3 |[V (z)(')| = ||Vsma / (vecv(xx)) Vsmax (vecy (x')))l S 4(i
in
Hence the non-smooth part of h is 4km () in Bz(x). The pth derivatives of g g= S h] S[f]] Smmas=smaxap Lipschitz. We know that a = p + 1,3 7/ 7/In// n and 7/ 7/10 In simplifying our bound to (a(lnn/7)") Furthermore, l = [0011/))2/3 and n = O(I k). Hence we can rewrite our upper bound as Op (1.3//((1n))))))
[0)] are thus by Lemma 1 Op(p-P P exp(43/pp)
7

---

We now see how to prove the query lower bound on optimizing this function class. In order to do so, we need introduce some intermediate functions. Let h((x)) max f((a) and gi(x) (a),]()). Let an oracle call a function f at a point z be denoted by Qy(z)
(f(x), ff()), f f(r)......... (=)() The following results will hold when the set V of orthonor- mal vectors is chosen uniformly at random (or Haar randomly). The next two lemmas about these intermediate functions form the backbone of our lower bound.
Lemma 5. Fix any E 10.....k - 1]. Let V be distributed Haar randomly. Conditioned on any fixing of (ui any query in the unit ball will satisfy Qg(x)) Que-n (I) with probability at least
1 - 1-1/n'0
Lemma 6. Let V be distributed Haar randomly. Conditioned on any fixing of [Us]esk-1, any point x in the unit ball will be e-optimal for with probability at most 1/n
To see how the lemmas above lead us to our lower bound, fix any k - l-query algorithm and consider the following experiment. For each from to k 1, when the algorithm makes its ith query do the following.
Sample v from the space orthogonal to the vectors V1 to 0--1-
Provide the algorithm the value that Qg. returns on the query. Note that the function 9: depends only the sampled vectors U1 through ez.
It follows that the output of the algorithm is independent of the vector Uy (conditioned on the vectors ii through 1). Now we use Lemma t say that with high probability the output of the algorithm not e-optimal for g. We can now use use Lemma 3Jalong with the hybrid argument to conclude that with high probability the transcript of this query algorithm is the same as the actual transcript (i.e. the transcript had 11 to Ug all been sampled at the beginning and all the queries been Qg). Since the transcripts are the same with high probability, the outputs of the algorithms are also the same with high probability. Hence even when all the queries are to Qg. with high probability the output not e-optimal for y. This proof is made formal as the proof oh 2
5 Lower bounds
We now establish the randomized lower bound using Lemma 4 Lemma 3| and Lemmamma 6
Theorem 2. Let A be a randomized query algorithm making at most k - 1 queries to Qg. When V is distributed Haar randomly, the probability that the output of A is e-optimal is o(1).
Proof. Let the success probability of A be Pauce when V distributed Haar randomly, We can fix the randomness of A to get deterministic algorithm B with success probability at least Psuce on the same distribution.
Let us denote the transcript of B as - = (æ1, Ø2, - oout) where is the ith query made and Fout is the output of the algorithm. Note that these are random variables that depend only on V. We now create hybrid transcripts m(() for 0 < i S k 1. The hybrid transcript (()
(0) o wout) is defined as the transcript of B when, for all j S i, its jth oracle call (which ..... 1
is supposed to be to Qg) is replaced with an oracle call to Qgy- Note that
For any V. v (())
(k-1) a function of {vilisk-1.
For any V. if "f
= Qg, (z(")) then ((1-1) (1). This is because they have queried the same oracles in their first - 1 calls, given the same input in the ith call and gotten the same output, and have been querying the same oracles thereafter.
We start with the observation that
(k-1) is e-optimal] = out
(k-1) is e-optimal] Foous
Pr V
E
Pr Pk/ock
(27)
10
(by Lemma 6
8

---

Next we show that Pry out
(k-1) Fout 2 o(1) which will complete the proof.
Pr(sout + =00t"11
Prlvout (f-1)
+ xoudd
(28)
ic 1E(k 1]
Σ
Pr|z Pr( * (
(29)
V
kE
Σ
Pr(Qu (+ ) * Qg. (m."0)
(30)
se|k-1]
1Qg (2ff--1) + Qg. (4.")]
E
Pr
(31)
iE(k-1] U1-
< -10
(32)
(f-1) since zi 2i
(1)
and using Lemma
We now translate the above lower bound to the optimization setting and establish the randomized lower bound in Theorem
Proof of randomized lower bound in Theorem 1
Our hard function class had Lp Op (I k)), R= = 0.1/VA. =.1/=01/VE Given these parameters, /c) (p(In)) k)). Hence
L R++ /c- (p(((/))t1)/ and Rn
sptT
In LpPett)
-2/3
SOp
(In 2/3) s Op()).
(33)
c
Since we have lower bound of k; the theorem statement follows.
We mention here that Lemmas 5 and 6 have even more far-reaching consequences. In Apppeddix C we note that these lemmas also prove lower bound of l: in (a) the parallel randomized setting where polynomially many non-adaptive queries are allowed each round and we want to bound the number of rounds and (b) the quantum setting. Hence the best known deterministic algorithm that was recently discovered also nearly optimal amongst parallel randomized and quantum algorithms.
Conclusion
In this paper, we obtained near optimal oracle lower bounds for -order smooth convex optimization, for any constant p. for randomized algorithms. Our results further hold for quantum algorithms and parallel randomized algorithms as well. To obtain our results, we introduce new smoothing operator that could be of independent interest. An interesting open problem is obtain both tight upper and lower bounds when we have oracle access only up to qth -order derivatives even though the function is guaranteed to have Lipschitz p" -ordr derivatives, for q p.
References
[AH18]
Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. In Conference On Learning Theory, pages 774-792, PMLR, 2018. URL: http: www.mm...............
//proceedings.no mlr www.ppresssssee vv75 /ateess//55///arwaaa aggawaa188: html
[vAGGdW20] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex Quantum, 4:220, January 2020. doi:10
optimization using quantum oracles.
22331/4-2020-01-13-
[ASS19]
Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, 178:327-360, 2019. doi 10. 1007 1010//00117001111111 129-13

---

[Bac09]
Michel Baes, Estimate sequence methods: extensions and approximations. Institute for Operations Research, ETH, Zürich, Switzerland, 2009.
[Ba197]
Keith Ball. An elementary introduction modemn convex geometry. In Silvio Levy, editor, Flavors of geomeiry, volume 31, pages 1-58. Cambridge University Press, 1997. URL::ttp:: htittp://libraryy .arr....aa.....m www.org/ooooo.oooooooooooo BBt//Booo333//llee http:f/llllaaaalapplp....aaa
[BBBV97]
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses quantum computing. SIAM Journal on Computing, 26(5):1510- 1523, 1997. :o:: 1137 110.111/000977333793003333
[BCI1]
Heinz H. Bauschke and Patrick L. Combettes. Infimal Convolution, pages 167-180. Springer New York, New York, NY, 2011. doi: 10. 00007/977-220 1000779988---44199948777-
12
[BIL++19]]
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sid- ford. Complexity of highly parallel non-smooth convex optimization. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019). URL: http::/papere. www.:iiiss.ccpppppeeee cc/paper smoo pages 13900-13909, 2019. cow.aaleeeeeooteoooooooooooooooo opt imization
[BJ++99] 19b]
Sébastien Bubeck. Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near- optimal method for highly smooth convex optimization. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 492-507. PMLR, 2019. URL:
mlr prwpp/ /99/ bubeck19a .htmllmllllmmmm1mm
[Bul20]
Brian Bullins. Highly smooth minimization of non-smooth problems. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Gruz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 988-1030. PMLR, 2020. URL: http:// proceedings mlr www..pprress..............e press / vtt//v122//11 httl/////l/blnla...oo
[CCLW20]
Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, January 2020. doi:10. /
221
[DG20]
Jelena Diakonikolas and Cristóbal Guzmán. Lower bounds for parallel and random- ized convex optimization. Journal of Machine Learning Research, 21(5):1-31, 2020. URL: wwwppptwrs./ppopoooooootppt..ert wwtpsrs//////99911e 771.hmm7
[GDG 19]
Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, and César A. Uribe. Optimal tensor methods in smooth convex and uniformly convexoptinization. In Proceedings of the Thirty-Second Conference Learning Theorr, volume 99 of Proceedings of Machine Learning Research, pages 1374-1391. PMLR, 2019. URL: http: http::://pooceeddngs.oo www.iiggssmr.r.r.sss/eee www.s/rsssveee.... /v99/ gasnikov19a.hta
[GKNS21]
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPlcs), pages 53:1-53:20, Dagstubl, Germany, 2021. Schloss Dagstuhl-Leibniz-Zenniie für Informatik. doi : 10. 4230/LIPIcs. ITCS. 2021.53 53
[GN15]
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. do1: 1016/j coo 24.4.084.. 08.0033
[JWZ19]
Bo Jiang, Haoyue Wang, and Shuzhong Zhang. An optimal high-order tensor method for convex optimization. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1799-1801, Phoenix, USA, 25-28 Jun 2019. PMLR. URL: htttp://proceedingg/ mlr www.:rpresseeeem v99/ / jingl .ttll
[MS13]
Renato D. C. Monteiro and B. F. Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM
Journal on Optimization, 23(2):1092-13 jan 2013. doi: 1
10

---

[Nem94]
Arkadi Nemirovski. On parallel complexity of nonsmooth convex optimization. Journal of Complexity, 10(4):451-46. 1994. doi: 10. wcom 1994, 1025
[Nes83]
Yu. E. Nesterov. A method of solving a convex programming problem with conver- gence rate ( Sov. Math., Dokd., 27:372-376, 1983.
[Nes08]
Yu. Nesterov. Accelerating the cubic regularization of newton's 's method on convex problems. Mathematical Programming, 12(():119-181, jan 2008. 101:10.10077 810107-006-0089-2
[Nes19]
Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical Programming, pages 1-27, 2019.
[NY83]
Arkadií Nemirovsky and David Borisovich Yudin, Problem complexity and method efficiency in optimization. Wiley, 1983.


Reviews:
[{"review_id": "qSop2F1R9aR", "reviewer": "Reviewer_2gRK", "summary": "This paper stuides the complexity of optimizing highly smooth convex functions. For a positive integer p, one wants to find an $\\epsilon$-approximate minimum of a convex function f, given oracle aceess to the function and its first p derivatives, assuming that the p-th derivative of f is Lipschitz. The near-optimal algorithms exist in deterministic setting while it remains a gap between the upper bounds and lower bounds for randomized algorithms. The contribution of this paper is to provide a new lower bound that matches the best existing upper bound (up to log factors), and shows that it holds not only for randomized algorithms, but also quantum algorithms. \n\nTo prove the desired lower bound, the paper started with a classical nonsmooth lower bound instance in Eq. (8) and employed a new random smoothing technique. By this construction, the proof strategy for nonsmooth convex optimization can be executed on the smoothed instance considered in this paper, thereby giving us a lower bound for p-th order smooth convex optimization. Using this idea, the authors prove the lower bound for the desired class of optimization problems.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Pros: Overall, I think the results are very interesting. Similar ideas have been widely used for proving complexity lower bound in the recent papers of [GN15] and [DG20] when p=1. \n\n[GN15] C. Guzman and A. Nemirovski \"On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization\", Journal of Complexty, 31 (1): 1-14, 2015. \n\n[DG20] J. Diakonikolas and C. Guzmán. \"Lower Bounds for Parallel and Randomized Convex Optimization\", JMLR, 21 (5): 1-31, 2020. \n\nThe novelty of this paper appears to be a different smoothing operator which extends the previous proof strategy for proving query lower bounds for high-order smooth convex optimization. Indeed, the inf-conv smoothing plays a fundamental role when p=1 and it is difficult to generalize it to p>=2. The authors did a great job in explaining the intuition behind their construction and I believe all the arguments are technically sound. I can see some new elements, but my knowledge of the previous work in this area is not deep enough to evaluate technical novelty very well.\n\nCons: Despite the tight lower bound, the motivation of this work is elusive. Indeed, the high-order randomized algorithm seems vary rare in the community and the only possible one I am aware of is the following article. \n\nV. S. Amaral, R. Andreani, E. G. Birgin, D. S. Marcondes, J. M. Martínez, \"On complexity and convergence of high-order coordinate descent algorithms\". (https://arxiv.org/abs/2009.01811)\n\nThere are also some other near-optimal high-order algorithms in the literature: \n\nT. Lin and M. I. Jordan. \"A control-theoretic perspective on optimal high-order optimization\". (https://arxiv.org/abs/1912.07168)\n \nM. Marques Alves. \"Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods\". (https://arxiv.org/abs/2102.02045) \n\nNevertheless, the high-order randomized optimization algorithms may have the potentials for structured nonconvex optimization since they may return better stationary points and thus have practical implications in machine learning. \n\nP. Xu, F. Roosta-Khorasani, M. W. Mahoney. \"Second-order optimization for non-convex machine learning: an empirical study\". ICDM 2020. \n\nBut a lower bound proved for the convex case in this paper seems to be stretching this a little far.  \n\nMoreover, I have some question about the extent to which this work is in scope for NeurIPS.  Indeed, the randomzied high-order optimization algorithms have received less attention and seem less competitive with the randomized first-order optimization algorithms for convex cases. Therefore, this paper seems like a somewhat good contribution that however would be of interest to a smallish subset of NeurIPS attendees.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Justify why studying the randomized high-order optimization algorithms and quantum algorithms is important given prior works. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "mPqj457fIAD", "reviewer": "Reviewer_wfjt", "summary": "The paper provides nearly tight lower bounds on the complexity of highly smooth convex optimization, using an oracle model where the oracle gives access to the function and its first p derivatives. The lower bounds extend previous bounds on deterministic algorithms to the randomized and quantum setting.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This is an excellent paper that resolves a relevant open question in the field of convex optimization. In addition, the quantum lower bound seems quite novel.\n\nQuestions:\n\nDo the authors think that the logarithmic factor in their bound could be improved with a tighter analysis and/or slight modification of the approach, or is it more likely to be fundamental and require different techniques to improve (or even, might it actually be tight)?\n\nCould these methods be generalized to obtain improved lower bounds for broader classes of functions, such as highly smooth star-convex functions (see https://arxiv.org/abs/1906.11985)?\n\nCan reduction be applied to generalize these lower bound results to the constrained setting (i.e., where the domain is a closed convex set that may not necessarily be a ball)? If the results can be generalized to the constrained setting, this might be a nice note to add. If not, what are the key challenges?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. No negative societal impact is applicable as this is purely a theoretical paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "OWrZnQI_8Wb", "reviewer": "Reviewer_jZkZ", "summary": "This paper studies the complexity of optimizing convex functions with Lipschitz $p$-th derivative. The authors prove a new lower bound $\\tilde{O} (1 / \\epsilon^{ \\frac{2}{3p+1} } )$ that holds for deterministic, randomized and quantum algorithms. This lower bound matches the upper bound up to log factors.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "[strength]\n\n  The construction of the hard functions is different from previous works. The authors use a novel combination of softmax function and randomized smoothing. The claims are well supported by theoretical analysis. The method is applicable to a general function class, information-hiding class of functions.\n\n  [weakness]\n\n The paper is not very well organized. Section 2 is a bit lengthy. while the detailed proof is a little brief. More interpretation of Lemmas 5 and 6 are preferred.\n\n  [typos]\n\n  Equation 28: a pair of parentheses is missing.\n\n  Equations 30 and 31: the sign $=$ should be the sign $\\neq$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for submitting your paper to NeurIPS'21.

Despite some minor concerns that should be addressed in the camera-ready version, the reviewers agreed that the paper is worthy of acceptance and is presented at NeurIPS'21. Congratulations!
Decision: Accept (Spotlight)