Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
Year: 2021

Abstract:
We study the complexity of optimizing highly smooth convex functions. For a positive integer p, we want to find an -approximate minimum of a 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 a new algorithm that solves this problem with Õ(1/ 2 3p+1 ) 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 quantum algorithms.

text: We study the complexity of optimizing highly smooth convex functions. For a positive integer p, we want to find an -approximate minimum of a 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 a new algorithm that solves this problem with Õ(1/ 2 3p+1 ) 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 quantum algorithms.

heading: 1 Introduction
text: 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 [Nes08, Bae09, MS13, Nes19, GDG+19, JWZ19, BJL+19b].
In this paper we study the problem of minimizing a highly smooth convex function given black-box access to the function and its higher order derivatives. The simplest example of the family of problems we consider here is the problem of approximately minimizing a convex function f : Rn → R, given access to an oracle that on input x ∈ Rn outputs (f(x),∇f(x)), under the assumption that the function’s first derivative, its gradient ∇f , has bounded Lipschitz constant. This problem can be solved by Nesterov’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 p, consider the pth-order optimization problem: For known R > 0, > 0, and Lp > 0, we have a p times differentiable convex function f : Rn → R whose pth derivative has Lipschitz constant at most Lp, which means
‖∇pf(x)−∇pf(y)‖ ≤ Lp‖x− y‖, (1)
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
where ‖·‖ is the `2 norm (for vectors) or induced `2 norm (for operators). Our goal is to find an -approximate minimum of this function in a ball of radius R, which is any x∗ that satisfies
f(x∗)− min x∈BR(0) f(x) ≤ , (2)
where BR(0) is the `2-ball of radius R around the origin. We can access the function f through a pth order oracle, which when queried with a point x ∈ Rn outputs
(f(x),∇f(x), . . . ,∇pf(x)). (3) As usual, ∇pf(x) denotes the pth derivative of f(x). 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.1 For a fixed p, it seems like this problem has 4 independent parameters, n, Lp, R, and , but the parameters are not all independent since we can scale the input and output spaces of the function to affect the latter 3 parameters. Thus the complexity of any algorithm can be written as a function of n and LpRp+1/ . 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 LpRp+1/ with no dependence on n.
As noted, the p = 1 problem has been studied since the early 80s [Nes83, NY83], and the p > 1 problem has also been considered [Nes08, MS13]. In an exciting recent development, new algorithms were proposed for all p (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]. All three groups develop deterministic algorithms that make
Õp (( LpR p+1/ )2/(3p+1))
(4)
oracle calls,2 where the subscript p in the big Oh (or big Omega) notation means the constant in the big Oh can depend on p. In other words, this notation means that we treat p as a constant. This improved upon the bounds of [Bae09, Nes19]; both the works develop deterministic algorithms that make
Õp (( LpR p+1/ )1/(p+1))
(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 Ωp (( LpR p+1/ )2/(3p+1))
queries. However, for randomized algorithms, the known lower bound is weaker. Agarwal and Hazan [AH18] showed that any randomized algorithm must make
Ωp (( LpR p+1/ )2/(5p+1))
(6)
queries. To the best of our knowledge, no 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, vAGGdW20] and for non-smooth convex optimization [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 ∈ N. For all > 0, R > 0, Lp > 0, there exists an n > 0 and a 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 -approximate minimum (satisfying eq. (2)) for any function f ∈ F must make
Ωp (( LpR p+1/ )2/(3p+1) ( logLpR p+1/ )−2/3) (7)
queries to a pth order oracle for f (as in eq. (3)). 1For simplicity we assume that the oracle’s output is computed to arbitrarily many bits of precision. This only makes our results stronger, since we prove lower bounds in this paper. 2Note that the query complexity does not have any dependence on the dimension n. Of course, actually implementing each query will take poly(n) 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,LpRp+1/ ) queries in each round and we only count the total number of query rounds (and not the total number of queries). See [BJL+19a] for previous work in this setting, including speedups for first-order convex optimization in the low dimensional setting.
In this introduction, we have deliberately avoided explaining the quantum model of computation to make the results accessible to readers without a 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 eq. (3) to support queries in quantum superposition. This is done in the usual way, by defining a unitary implementation of the oracle, which allows quantum algorithms to make superposition queries and potentially solve the problem more efficiently than randomized algorithms.

heading: 2 High level overview
text: 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 p = 1) oracle. To be more precise, the oracle returns subgradients, since gradients need not be defined at all points for Lipschitz convex functions. For this setting, known popularly as nonsmooth convex optimization, the optimal lower bound of Ω ( 1 2 ) is in fact a classical result [NY83]. 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 [Nem94], quantum algorithms [GKNS21] 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 min‖x‖≤1 fV (x) where fV : Rn → R is chosen as
fV (x) = max i∈[k] 〈vi, x〉+ (k − i)γ, (8)
with k = O ( n1/3 ) , γ = Θ̃ ( 1√ n ) , and V = (v1, · · · , vk) comprises k orthonormal vectors chosen uniformly at random. The argument essentially shows that
(i) in order to find a O (
1√ k
) -approximate minimizer, one needs to know all the vi’s, and
(ii) with high probability, each query reveals at most one new vector vi. This yields a lower bound of k queries for achieving an error of O (
1√ k
) . Since f is a 1-Lipschitz
function, when we rewrite this bound in terms of error, it yields the Ω ( 1 2 ) randomized lower bound.
For the p = 1 setting, known popularly as smooth convex optimization, the optimal lower bound Ω (√ 1 ) is also a 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 a 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. Smoothing refers to the process of approximating a given Lipschitz function f by another function g, which has Lipschitz continuous pth derivatives for some p ≥ 1. Further, since we will be applying this operation to (8), we will describe smoothing in this context.
Definition 1. An operator S which takes a 1-Lipschitz function f to another convex function S[f ] is called a (p, β, )-smoothing operation if it satisfies the following:
1. Smoothness: pth derivatives of S[f ] are Lipschitz continuous with parameter β, and
2. Approximation: For any x, we have |f(x)− S[f ](x)| ≤ .
If we can design a smoothing operation as per the above definition with = O ( 1/ √ k )
and further ensure that property (ii) above i.e., with high probability, each query to the first p derivatives of S[f ]
reveals at most one new vector vi, then the proof strategy of lower bound for nonsmooth convex optimization can be executed on the smoothed instance S[f ], there by giving us a lower bound for pth-order smooth convex optimization. This is the key idea of [GN15, DG20]. Further, the smaller β is, the better the bound we obtain. However, since f can have discontinuous pth derivatives, there is a tension between the approximation property which tries to keep S[f ] close to f and the smoothness property. So, one cannot make β very small after fixing = O(1/ √ k). For the rest of this section, we fix = O(1/ √ k) in Definition 1.
For the p = 1 setting, there is a well-known smoothing operation known as Moreau/inf-conv smoothing [BC11], which obtains the best possible smoothing with β = Θ(k1.5). This gives the tight query lower bound of Ω ( 1√ ) for smooth convex optimization.
However, there is no known generalization of inf-conv smoothing for p ≥ 2, so one needs to use a different smoothing operator to extend this proof strategy for proving query lower bounds for higher order smooth convex optimization. Given any p ≥ 1, [AH18] indeed construct such a smoothing, called randomized smoothing which maps Lipschitz convex functions to convex functions with Lipschitz pth derivatives. In the general p ≥ 1 setting, a smoothing operator with β = O ( k3p/2
) would give the optimal lower bound of Ω ( −2 3p+1 ) . However, the randomized smoothing of [AH18]
can obtain only β = O ( k5p/2 ) leading to a suboptimal Ω ( −2 5p+1 ) lower bound for pth order smooth
convex optimization.
We design an improved smoothing operation, for the specific class of functions in Equation (8), with the optimal β = O ( k3p/2 ) using two key ideas. The first idea is the softmax function with
parameter ρ defined as smaxρ(z) := ρ log (∑ i∈[k] exp ( zi ρ )) , where z ∈ Rk. If we apply smaxρ, with ρ = k−3/2, to functions of the form (8) through:
smaxρ(vecV (x)) := ρ log ∑ i∈[k] exp ( 〈vi, x〉+ (k − i)γ ρ ) , (9) where vecV (x) := (〈v1, x〉 + (k − 1)γ, 〈v2, x〉 + (k − 2)γ, . . . , 〈vk, x〉), we can show that smaxρ(vecV (x)) satisfies Definition 1 with the optimal value of β = O ( k3p/2 ) . However, any query on derivatives of smaxρ(vecV (x)) reveals information about all the vectors vi simultaneously since for instance the gradient is given by
∇smaxρ(vecV (x)) = ∑ i∈[k]
exp ( 〈vi,x〉+(k−i)γ
ρ ) ∑ j∈[k] exp ( 〈vj ,x〉+(k−j)γ ρ
) · vi. (10) Consequently, it cannot be directly used to obtain a lower bound. The second idea is that even though the function value and derivatives of smaxρ(vecV (x)) have contribution from all vi’s, the contribution is heavily dominated (i.e., up to 1poly(k) error) by vi∗(x), where i
∗(x) = argmaxi∈[k] 〈vi, x〉+(k−i)γ, whenever 〈 vi∗(x), x 〉 + (k − i∗(x))γ > 〈vi, x〉+ (k − i)γ + Ω(ρ log k) for every i 6= i∗(x).
Based on this insight, we design a new 1-Lipschitz convex function given by h(x) := maxi∈[k] fi(x) where fi(x) := smax≤iρ (vecV (x)) + ρ(k − i)n−α for an appropriate α to be chosen later, where smax≤iρ (vecV (x)) := ρ log (∑ j∈[i] exp ( 〈vj ,x〉+(k−j)γ ρ )) . The key property satisfied by fi is that fi ≈ fj implies that ∇fi ≈ ∇fj for any i, j. This implies that near points of discontinuous gradients for h i.e., points where argmaxi∈[k] fi(x) changes, the resulting discontinuity in ∇h(x) is O ( 1
poly(k)
) . In contrast, the change in gradients of the original instance fV (x) near points of
discontinuity is Ω(1). If we apply randomized smoothing to h, the resulting function can then be shown to have pth order Lipschitz constant Õ ( k3p/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.

heading: 3 Smoothing preliminaries
text: In this section we look at some smoothing functions and their properties. The proofs of these properties can be found in Appendix A.
Let Bη(x) = {y ∈ Rn : ‖y − x‖ ≤ η} be the ball of radius η around x ∈ Rn. Definition 2 (Randomized smoothing). For any function f : Rn → R and real-valued η > 0, the randomized smoothing operator Sη produces a new function Sη[f ] : Rn → R from f with the same domain and range, defined as
Sη[f ](x) = E y∈Bη(x) [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 first derivative will be defined and Lipschitz [AH18]. Since we want to construct functions with p derivatives, we define a p-fold version of randomized smoothing. Recall that p is the same p as in the introduction (i.e., we are proving lower bounds on the pth order optimization problem). This operation also depends on a parameter β that we will fix later.
Definition 3 (Smoothing). The smoothing operator S on input f : Rn → R outputs the function
S[f ] = Sβ/2p [Sβ/2p−1 [· · ·Sβ/22 [Sβ/21 [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 : Rn → R for which S[f ],S[g] are well-defined, S[f + g] = S[f ] + S[g].
2. The value S[f ](x) only depends on the values of f within a (1− 2−p)β radius of x.
3. The gradient and higher order derivatives of S[f ] at x depend only on the values of f within Bβ(x).
4. If ∇pf is L-Lipschitz in a ball of radius β around x, then∇pS[f ] is also L-Lipschitz at x.
5. Let f be G-Lipschitz in a ball of radius β around x. Then S[f ] is p-times differentiable, and for any i ≤ p,∇iS[f ] is L-Lipschitz in a β/2p-ball around x with L ≤ n i2i(i+1)/2
βi G.
6. Let f be G-Lipschitz in a ball of radius β around x. Then |S[f ](x)− f(x)| ≤ βG.
7. If f is a convex function, then S[f ] is also a convex function.
We also use the softmax function introduced earlier.
Definition 4 (Softmax). For a real number ρ, the softmax function smaxρ : Rn → R is defined as smaxρ(x) = ρ ln (∑ i∈[n] exp(xi/ρ) ) . (13)
Let us also define, for m ≤ n, smax≤mρ : Rn → R as
smax≤mρ (x) = smaxρ(x≤m), or equivalently, smax ≤m ρ (x) = ρ ln (∑ i∈[m] exp(xi/ρ) ) . (14)
We note the following smoothness properties of softmax.
Lemma 2. The following are true of the function smaxρ for any ρ > 0.
1. The first derivative of smax can be computed as
∂smaxρ(x)
∂xi = exp(xi/ρ)∑ i exp(xi/ρ) . (15)
2. smaxρ is 1-Lipschitz and convex.
3. The higher-order derivatives of smax satisfy
‖∇psmaxρ(x)−∇psmaxρ(y)‖ ≤
( p+1
ln(p+2)
)p+1 p!
ρp ‖x− y‖. (16)
We will also need the following lemma which roughly states that if smax(x) and smax≤m(x) are nearly the same, then their gradients are also nearly the same at x. Lemma 3. Let x ∈ Rn and m < n. If
smaxρ(x)− smax≤mρ (x) ρ = δ < 1, (17)
Then ‖∇smaxρ(x)−∇smax≤mρ (x)‖ ≤ 4δ. (18)

heading: 4 Function construction and properties
text: 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 proofs have been moved to Appendix B due to space constraints.
Let k ∈ N, γ, β, ρ, α ∈ R be parameters to be defined shortly. k and γ are parameters as used in the high level overview (Equation (8)), β is the parameter required to define S and ρ is the parameter used in the definition of smax.
Function construction. Given a list of orthonormal vectors v1, . . . , vk ∈ Rn, which we collectively call V , we recall that vecV (x) ∈ Rk denotes the vector
vecV (x) = (〈v1, x〉+ (k − 1)γ, 〈v2, x〉+ (k − 2)γ, . . . , 〈vk, x〉). (19)
We can now define our hard function class as follows. Definition 5. Let V = (v1, . . . , vk) ∈ Rn be a set of orthonormal vectors. The functions f1, . . . , fk, h and g depend on V as follows. Define, for each i ∈ [k], the function fi : Rn → R as
fi(x) = smax ≤i ρ (vecV (x)) + ρ(k − i)n−α. (20)
Define h(x) = maxi∈[k] fi(x), and g(x) = S[h](x).
Note that in the above definition we apply the smax functions on vecV (x) and not on x. However, since vecV (x) is obtained by applying a unitary transform on x and then translating it, the observations about smax(x) in Lemmas 2 and 3 also hold for smax(vecV (x)).
We set γ = 40 √
lnn n , k =
⌊ (0.1/γ)2/3 ⌋ (or γ ≈ 0.1/k √ k), ρ = γ/100α lnn, β = γ/ lnn, α =
p+ 1.
Function properties. We now state some properties of the function that will be used to show the lower bounds. Lemma 4. For any choice of V , the function g is convex, p-times differentiable and satisfies
‖∇pg(x)−∇pg(y)‖ ≤ Lp‖x− y‖ (21)
where Lp ≤ Op(k3p/2(ln k)p).
The proof relies on the fact that smax is smooth and hence each fi is smooth. If h = fi for a particular i in a β-neighborhood of x, then g = S[h] would also be smooth (by Lemma 1, item 4). If h depends on multiple fis in a β-neighborhood of x, then we know that at least two softmax’s involved in the definitions of the fis have nearly the same value in the neighborhood of x, 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 x (by Lemma 1, item 5).
Proof. Each fi is an instance of softmax applied to vecV (x) plus a constant. Since vecV (x) is the vector x transformed by a unitary and then translated, the smoothness and convexity properties of smaxρ also apply to fi. Hence each fi is convex, p-times differentiable and its pth derivatives are Op(ρ
−p)-Lipschitz (see Lemma 2). The function h, being a maximum over convex functions, is also convex. By the properties of the smoothing operator S (Lemma 1), the function g = S[h] is also convex.
Let x ∈ Rn. Let j ∈ [k] be the minimum number such that there is a point y ∈ Bβ(x) for which h(y) = fj(y). We can rewrite h as follows: h(z) = fj(z) + maxi>j(fi(z) − fj(z)). We call fj(z) the smooth term and maxi>j(fi(z) − fj(z)) the non-smooth term. We know that fj has an Op(ρ
−p) upper bound on the Lipschitzness of its p-th order derivatives. If all points y ∈ Bβ(x) satisfy h(y) = fj(y), then the non-smooth term is 0 and so it does not change the smoothness of h. g = S[h] will maintain this smoothness (see item 4 of Lemma 1). If the non-smooth term is non-zero at some point inBβ(x), then we wish to show that the non-smooth term has a small Lipschitz constant in Bβ(x). This would imply, via item 5 of Lemma 1, 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 Bβ(x). Let Ix′ be the set {i ∈ [k]|h(x′) = fi(x′)}. The set of subgradients of the non-smooth term at x′ is the convex hull of {∇(fi − fj)(x′)}i∈I(x′). So if we show that for an arbitrary i ∈ I(x′), ‖∇(fi − fj)(x′)‖ ≤ L, then we know that the non-smooth part is L-Lipschitz at x′. If i = j, then the gradient is zero. Let us take an i 6= j (since j is the smallest, in fact i > j). By convexity of the ball and the continuity of fi and fj , there must be a point y in Bβ(x) for which h(y) = fi(y) = fj(y). Note that x′ ∈ B2β(y). The statement fi(y) = fj(y) translates to
smax≤iρ (vecV (y))− smax≤jρ (vecV (y)) ρ = (i− j)n−α << 1. (22)
Expanding the expression for smax≤iρ and smax ≤j ρ we get
smax≤iρ (vecV (y))− smax≤jρ (vecV (y)) ρ = ln
∑i`=1 exp ( 〈y,v`〉+(k−`)γ ρ ) ∑j `=1 exp ( 〈y,v`〉+(k−`)γ ρ )  (23)
= ln 1 + ∑i`=j+1 exp ( 〈y,v`〉+(k−`)γ ρ ) ∑j `=1 exp ( 〈y,v`〉+(k−`)γ ρ )  (24)
Since ‖x′ − y‖ ≤ 2β, we have that |〈x′, v〉 − 〈y, v〉| ≤ 2β for any unit vector v. Hence
smax≤iρ (vecV (x ′))− smax≤jρ (vecV (x′))
ρ ≤ ln
1 + e2β/ρ∑i`=j+1 exp ( 〈y,v`〉+(k−`)γ ρ ) e−2β/ρ ∑j `=1 exp ( 〈y,v`〉+(k−`)γ ρ )  .
(25)
For all c > 0, ln(1 + e4β/ρc) ≤ e4β/ρ ln(1 + c). So we can conclude from the above that
smax≤iρ (vecV (x ′))− smax≤jρ (vecV (x′))
ρ ≤ (i− j)n−αe4β/ρ. (26)
Now by Lemma 3, ‖∇(fi − fj)(x′)‖ = ‖∇smax≤iρ (vecV (x′)) − ∇smax≤jρ (vecV (x′))‖ ≤ 4(i − j)n−αe4β/ρ.
Hence the non-smooth part of h is 4kn−α exp(8β/ρ)-Lipschitz in Bβ(x). The pth derivatives of g = S[h] = S[fj ] +S[maxi>j(fi− fj)] are thus by Lemma 1, Op(ρ−p +npβ−pkn−α exp(4β/ρ))Lipschitz. We know that α = p + 1, β = γ/ lnn and ρ = γ/100α lnn, simplifying our bound to Op((lnn/γ) p). Furthermore, k = ⌊ (0.1/γ)2/3 ⌋ and lnn = O(ln k). Hence we can rewrite our
upper bound as Op ( k3p/2(ln k)p ) .
We now see how to prove the query lower bound on optimizing this function class. In order to do so, we need to introduce some intermediate functions. Let hi(x) = maxj∈[i] fi(x) and gi(x) = S[hi](x). Let an oracle call to a function f at a point x be denoted by Qf (x) = (f(x),∇f(x),∇2f(x), . . . ,∇pf(x)). The following results will hold when the set V of orthonormal 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 t ∈ [0, . . . , k − 1]. Let V be distributed Haar randomly. Conditioned on any fixing of {vi}i≤t, any query x in the unit ball will satisfy Qg(x) = Qgt+1(x) with probability at least 1− 1/n10. Lemma 6. Let V be distributed Haar randomly. Conditioned on any fixing of {vi}i≤k−1, any point x in the unit ball will be -optimal for g with probability at most 1/n10.
To see how the lemmas above lead us to our lower bound, fix any k− 1-query algorithm and consider the following experiment. For each i from 1 to k − 1, when the algorithm makes its ith query do the following.
• Sample vi from the space orthogonal to the vectors v1 to vi−1. • Provide the algorithm the value that Qgi returns on the query. Note that the function gi
depends only on the sampled vectors v1 through vi.
It follows that the output of the algorithm is independent of the vector vk (conditioned on the vectors v1 through vk−1). Now we use Lemma 6 to say that with high probability the output of the algorithm is not -optimal for g. We can now use Lemma 5 along 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 v1 to vk all been sampled at the beginning and all the queries been to 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 is not -optimal for g. This proof is made formal as the proof of Theorem 2.

heading: 5 Lower bounds
text: We can now establish the randomized lower bound using Lemma 4, Lemma 5, and Lemma 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 -optimal is o(1).
Proof. Let the success probability of A be psucc when V is distributed Haar randomly. We can fix the randomness of A to get a deterministic algorithm B with success probability at least psucc on the same distribution.
Let us denote the transcript of B as x = (x1, x2, . . . , xk−1, xout) where xi is the ith query made and xout is the output of the algorithm. Note that these are random variables that depend only on V . We now create hybrid transcripts x(i) for 0 ≤ i ≤ k − 1. The hybrid transcript x(i) = (x
(i) 1 , · · · , x (i) k−1, x (i) out) is defined as the transcript of B when, for all j ≤ i, its jth oracle call (which
is supposed to be to Qg) is replaced with an oracle call to Qgj . Note that
• For any V , x = x(0).
• x(k−1) is a function of {vi}i≤k−1.
• For any V , if Qg(x (i−1) i ) = Qgi(x (i) i ) then x (i−1) = x(i). This is because they have queried the same oracles in their first i− 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
Pr V
[x (k−1) out is -optimal] = E
v1,...,vk−1
[ Pr
vk|v<k [x
(k−1) out is -optimal] ] (27)
≤ n−10. (by Lemma 6)
Next we show that PrV [x (k−1) out = xout] ≥ 1− o(1) which will complete the proof.
Pr V
[xout 6= x(k−1)out ] ≤ ∑
i∈[k−1]
Pr V
[x (i−1) out 6= x (i) out] (28)
≤ ∑
i∈[k−1]
Pr V
[x(i−1) 6= x(i)] (29)
≤ ∑
i∈[k−1]
Pr V
[Qg(x (i−1) i ) 6= Qgi(x (i) i )] (30)
≤ ∑
i∈[k−1]
E v1,...,vi−1
[ Pr
vi,...,vk|v<i [Qg(x
(i−1) i ) 6= Qgi(x (i) i )]
] (31)
≤ kn−10, (32)
since x(i−1)i = x (i) i , and using Lemma 5.
We now translate the above lower bound to the optimization setting and establish the randomized lower bound in Theorem 1.
Proof of randomized lower bound in Theorem 1. Our hard function class had Lp = Op(k3p/2(ln k)p), R = 1, = 0.1/ √ k. Given these parameters, LpR p+1/ = Op(k
(3p+1)/2(ln k)p) and ln(LpRp+1/ ) = Op(ln k). Hence( LpR p+1 ) 2 3p+1 ( ln LpR p+1 )−2/3 ≤ Op ( k(ln k) 2p 3p+1 (ln k)−2/3 ) ≤ Op(k). (33)
Since we have a lower bound of k, the theorem statement follows.
We mention here that Lemmas 5 and 6 have even more far-reaching consequences. In Appendix C, we note that these lemmas also prove a lower bound of k in (a) the parallel randomized setting where polynomially many non-adaptive queries are allowed in 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 is also nearly optimal amongst parallel randomized and quantum algorithms.

heading: 6 Conclusion
text: In this paper, we obtained near optimal oracle lower bounds for pth-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 a new smoothing operator that could be of independent interest. An interesting open problem is to 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 pth-order derivatives, for q < p.

Review summaries:
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.   To 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.

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.