Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: [strength]

  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.

  [weakness]

 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.

  [typos]

  Equation 28: a pair of parentheses is missing.

  Equations 30 and 31: the sign $=$ should be the sign $\neq$.

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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.
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.

Questions:

Do 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)?

Could 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)?

Can 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?
limitations_and_societal_impact: Yes. No negative societal impact is applicable as this is purely a theoretical paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

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.
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. 

[GN15] C. Guzman and A. Nemirovski "On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization", Journal of Complexty, 31 (1): 1-14, 2015. 

[DG20] J. Diakonikolas and C. Guzmán. "Lower Bounds for Parallel and Randomized Convex Optimization", JMLR, 21 (5): 1-31, 2020. 

The 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.

Cons: 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. 

V. 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)

There are also some other near-optimal high-order algorithms in the literature: 

T. Lin and M. I. Jordan. "A control-theoretic perspective on optimal high-order optimization". (https://arxiv.org/abs/1912.07168)
 
M. 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) 

Nevertheless, 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. 

P. Xu, F. Roosta-Khorasani, M. W. Mahoney. "Second-order optimization for non-convex machine learning: an empirical study". ICDM 2020. 

But a lower bound proved for the convex case in this paper seems to be stretching this a little far.  

Moreover, 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.
limitations_and_societal_impact: Justify why studying the randomized high-order optimization algorithms and quantum algorithms is important given prior works.
review_title: null

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)