Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Near-Optimal Lower Bounds For Convex Optimization For All Orders of
  Smoothness   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 $\tilde{O}(1/\epsilon^{\frac{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 for
quantum algorithms.

15
The categories of this paper are: nucl-ex
17
The categories of this paper are: q-fin
21
The categories of this paper are: adap-org
36
The categories of this paper are: cmp-lg
12
The categories of this paper are: nucl-th
18
The categories of this paper are: econ
14
The categories of this paper are: math-ph
11
The categories of this paper are: hep-lat
4
The categories of this paper are: cond-mat
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
19
The categories of this paper are: eess
9
The categories of this paper are: nlin
37
The categories of this paper are: supr-con
29
The categories of this paper are: funct-an
33
The categories of this paper are: plasm-ph