Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the question of minimization of convex functions with $p$-order smooth derivatives, given access to an oracle that can minimize the regularized $p$-th order Taylor expansion of the function at a given point. 

Recent works (Gasnikov et al, Bubeck et al., Jiang et al.) had previously established an oracle complexity of $O(\epsilon^{-2/(3p+1)}\log 1/\epsilon)$ extending the rate of $O(\epsilon^{-1/2})$ by Accelerated Gradient descent (Nesterov, 1983) for $p=1,$ $O(\epsilon^{-2/7})$ by Montero-Svaiter (2013) for $p=2,$ and Nesterov's accelerated tensor method (2021a) that achieved $O(\epsilon^{-1/(p+1)}).$ 

A lower bound of $\Omega(\epsilon^{-2/(3p+1)})$ is known from Arjevani et al. (2019). Thus, the known rates were off by a logarithmic factor. 

This paper gives an algorithm that achieves a tight bound of $O(\epsilon^{-2/(3p+1)})$ calls to the $p$-th order oracle, thus settling the complexity of $p$-th order smooth convex minimization.
strengths_and_weaknesses: **Strengths**:
The key strength of the result is immediate since it establishes the best-possible oracle complexity of solving $p$-th order smooth convex problems.

**Weakness**:
1. My primary concern is whether shaving off a log factor from the oracle complexity is that significant a question after all. The 3 independent papers that first achieved the almost-optimal complexity had achieved a significant improvement in the oracle complexity. While it is nice to achieve the exactly optimal bound in terms of epsilon, the logarithmic factor seems inconsequential in my opinion.
2. All these papers rely on making calls to an oracle that can not only compute $p$-th order derivatives, but can solve a regularized $p$-th order problem, see Algorithm 1, step 5, eq 15 and Algorithm 3, step 6 or Algorithm 4, line 11. (To the best of my knowledge) We do not know how to solve these problems efficiently for $p > 2$ even given access to the higher order derivatives. In my view, this hides the real complexity of being able to solve highly smooth problems. 
3. The notation of the paper is difficult to parse. e.g. in Algorithm 4, $x_g$ is a funny notation that gives no hint to what it means. It relies on $x_f$ which is again not so easy to see where it's defined. In line 11 in Algorithm 4, the notation for $\Phi$ has three(!!) orders of subscript.
questions: Am I correct in pointing out that your algorithm does not provide an efficient procedure to compute the next iterate on line 11 in Algorithm 4? If yes, I strongly suggest reflecting this in the definition of Oracle complexity. The current definition of oracle complexity in the paper (Definition 2) only assumes that the oracle returns the higher order derivatives.
limitations: I have listed the limitations above under weaknesses of the result.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this work, the authors propose a new accelerated high-order method for convex optimization. They prove that the global complexity of their method matches the lower complexity bound, thus the method is *optimal*. In the previous approaches, it was required to do some extra line search at each iteration, solving a one-dimensioanal nonlinear equation, which resulted in much more sophisticated algorithms with additional logarithmic factors. In the new method, the line search is not needed. Therefore, this is the first method having the pure *optimal* rate without extra logarithms.
strengths_and_weaknesses: The contribution is the new optimal accelerated high-order method and its analysys. I found these results interesting and significant. To the best of my knowledge, this is the first accelerated (high-order, p >= 2) method that does not use any line search, and matches the lower bounds without extra logarithms.

The main idea of their construction is to use the standard accelerated framework (from the works of Nesterov, 1983, 2018; Monteiro-Svaiter, 2013, Gasnikov et al. 2019) but with a predefined sequence of parameters which provides the method with a required rate of convergence (knowing in advance the optimal rate). Then, to ensure an actual convergence, they propose to solve a prox-point type subproblem by iterations of the basic high-order method (in their case, Tensor Extragradient Method). The main novelty of the analysys is to prove:
1. the convergence of the inner method to a reasonable stationary point in a certain amount of iterations.
2. the boundedness of the total number of inner steps.
While in the previous near-optimal high-order methods, it was required to do high-order step just once, but with solving a complicated nonlinear equation alongside.

In my opinion, this is a solid result which must be of interest for the optimization community.


The weaknesses of the paper are a little bit technical presentation and the lack of any practical evidence (experiments or at least a discussion).
The paper containts a lot of details comparing different analysis techniques with some unnecessary redundancy (e.g. Algorithm 1 and Algorithm 2), however almost no information about how to use their methods in practice. In particular, the following questions seem to be unanswered:

1. How to choose parameter $\nu$ in practice. The formula (30) contains both the Lipschitz constant and the radius R. Is it possible to use some line search? Is it possible to eliminate some of these parameters?

2. How many steps of the inner method are needed in practice, and what happens in case p = 1 (first-order accelerated methods)? 

-------------------- 
After rebuttal:
--------------------
I am happy to increase my score, since I believe that the main theoretical contribution of the paper is very significant for the optimization community.
questions: 1. Could you, please, make the difference between Algorithm 1 and 2 more transparent? I found no information in the text why the second algorithm is needed (it seems to be the same as the first one).

2. Line 171: 'the crucial mistake' -- I would propose to use slightly more polite wording, since there is no evidence of mistakes (the old algorithms still have some benefits as it seems, e.g. no need to know R).

3. I think it worths to add some references regarding Tensor Extragradient Method and high-order methods minimizing gradient norm.
limitations: --
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, the authors propose a p-order method for optimizing a p-times continuously differentiable objective. They prove that the convergence rate matches the theoretical lower bound and is better than the previous works. 
strengths_and_weaknesses: Strength:
1. Designing a high-order optimization method that matches the theoretical lower bound on the iteration complexity is indeed a contribution. 
2. The theoretical results are complete and solid. 

Weakness:
In the abstract, it seems that one of the motivations is that the previously proposed high-order methods are not practical. But in this paper, there are still no numerical experiments. Can you provide some experiments to verify that the proposed method is practical? 
questions: See the weakness points. 
limitations: NA
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies highly smooth convex optimization and provides the first optimal acceleration method under oracle model. A function is said to be p-th order smooth if its p-th order gradient is Lipschitz. The previous best known methods for high-order smooth function finds an $\epsilon$-approximation solution using $O(\log(1/\epsilon)\epsilon^{-2/(3p+1)})$ gradient oracles and follows the Monteiro and Svaiter framework, and a lower bound of $\Omega(\epsilon^{-2/(3p+1})$. The paper closes this gap and provide an algorithm using $O(\epsilon^{-2/(3p+1)})$ gradient oracle calls.

To summarize in very short words, the paper still utilizes the Monteiro and Svaiter framework (as previous work), but instead of performing some complex binary search for a fix point problem as a subroutine, the paper gives the explicitly parameter and an explicit high-order extra gradient for searching the ``middle'' point.


strengths_and_weaknesses: Strength. The paper is very well-written, easy to read and give a nice summary on previous work. On the technical side, the removal of binary search and an explicit method for high order smooth optimization is very nice and could be beneficial for practical implementation.


Weakness. There is no major weakness, but personally I think providing some experiments for the methods could make the paper more promising. Though I found the pure theoretical result is already very interesting.

In summary, I think this is a solid paper and could benefit the community. I would suggest to accept the paper.

--------------------------- Post rebuttal ---------------------------

I have read the author's response keep my evaluation, and I vote for acceptance of the paper.
questions: Some additional reference.

[1] Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss. COLT'2021
Yair Carmon, Arun Jambulapati, Yujia Jin and Aaron Sidford 

[2] Acceleration with a Ball Optimization Oracle
Yair Carmon, Arun Jambulapati, Yujia Jin, Qijia Jiang, Yin Tat Lee, Aaron Sidford and Kevin Tian 
limitations: No
review_title: null

Meta-review: metareview: The paper is interesting and the reviewers on average recommend (weak-ish) acceptance. I agree with that asessment. 
confidence: Less certain
Decision: Accept