Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper introduces a new variant of Monteiro-Svaiter (MS) framework which serves as a meta-algorithm to accelerate (inexact) backward optimization method in convex optimization, like proximal point algorithm, cubic regularization, etc. The proposed variant removes the bisection step in the original MS method, improving the theoretical complexity by a logarithmic term so that the obtained bound matches the optimal bounds up to constant factors. The proposed method does not require any parameter tuning in a way that the regularization parameter $\lambda$ is adaptively adjusted, without requiring any knowledge of the Lipschitz/Hölder constant and order in advance. The paper shows that the algorithm achieves optimal complexity bound and provide a detailed discussion on the use case of cubic regularization. Experiments are conducted to validate the theoretical guarantees. 
strengths_and_weaknesses: Strength: Theoretical improvement on existing MS framework
Weakness: very hard to follow, the presentation need to be improved. More clarification on several key technical component is required. 
questions: The paper provides detailed discussion on how to improve MS framework with the cubic regularization method and further abstract it to a more generalized framework. However, some steps in the abstraction is not very clear to me. 

In Definition 1/Algorithm 1, the paper introduces a novel oracle called MS oracle which takes input of a couple of iterate and regularization parameter ($y, \lambda'$)  and output another couple $(x, \lambda)$ such that 
$$ \Vert x - (y - \frac{1}{\lambda} \nabla f(x)) \Vert \le \sigma \Vert x- y \Vert $$
However, what is a bit intriguing to me is that the oracle does not seem to depend on the $\lambda' $. Conceptually, I understand that we want to perform some line search type method from $\lambda'$ to get $\lambda$. However, without any restriction on $\lambda$, the oracle seems meaningless as the obtained $\lambda$ could be arbitrary. More precisely, take the example of proximal point algorithm, for any $\lambda$, when we solve the subproblem 
$$F(z) := f(z) + \frac{\lambda}{2} \Vert z - y \Vert^2 $$
to sufficient accuracy, the solution will satisfies the MS oracle. In other words, take a very small $\lambda = 10^{-10} \lambda'$  and solve the above $F$ up to very high accuracy is essentially solving the original problem. So I think an important step in Algorithm 1 should be discussing how to select $\lambda$ with respect to $\lambda'$. Otherwise the complexity bound could be vacuous or non-meaningful. 

Another question I have is how the algorithm achieves no parameter tuning. Upon my understanding (correct me if I am wrong), the parameters $s$ and $c$ in the ($s$, $c$) movement bound serves as some sort of approximate Holder order. However, I am not able to understand how the algorithm adaptively select them, it seems like they are kept constant along the way. 

Minor questions: 
In equation right below line 191, it is claimed that the MS oracle is satisfied for Taylor descent step. It seems to me this only hold  for $p+\nu =2 $, otherwise there would be a power in the (x-y) term. 

Literature: 
I believe the following literature on accelerated proximal point algorithms are related (as special case $\lambda' =\lambda$)
1.  Inexact and accelerated proximal point algorithms.  Salzo and Villa
2. Catalyst acceleration for first-order convex optimization: from theory to practice. Lin et al
limitations: The contribution of the paper is mostly theoretical where might have limited practical impact
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors present a new version of the Monteiro-Svaiter (MS)
acceleration framework. The main feature of this new version, compared to the
original MS framework, is that there is no need to (approximately) solve a
complicated nonlinear equation at every iteration that adds an extra logarithmic
factor to the total oracle complexity of the algorithm. As a result, the new
framework allows constructing optimal tensor methods of any order $p \geq 1$
(without any hidden logarithmic factors in the final complexity bound). In the
special case, that corresponds to the second-order method ($p = 2$), the authors
additionally propose a novel efficient procedure for solving the auxiliary
subproblem that arises at each iteration of the method. This procedure can be
seen as an alternative to the standard "line search" which is typically used for
an adaptive estimation of the Lipschitz (or Hölder) constant of the Hessian. In
the end, the authors obtain a new "universal" second-order method that requires
no knowledge of the problem parameters, and can be implemented using either an
exact linear system solver or an auxiliary conjugate gradient-type method.
Finally, the authors present several numerical experiments which confirm the
efficiency of their approach, and raise several interesting open questions.
strengths_and_weaknesses: This is an excellent work that has at least two significant contributions.

First, the authors solve an important open problem of constructing an optimal
tensor method that does not have any extra logarithmic factors in its complexity
estimate. Their solution is quite elegant in that their method is essentially
the original MS algorithm with a couple of small (but nontrivial) modifications.
Specifically, instead of having an inner loop searching for an (approximate)
solution to the nonlinear equation, they simply make one step (of the basic
method) and then check if a certain condition is satisfied: if yes, they keep
the result and go to the next iteration; if no, they take the average of the
"unsuccessful" new point and the current one, and also go the next iteration. In
addition to that, they have a very simple adaptation procedure for the "guess"
of the solution to the nonlinear equation: it is either multiplied by a constant
if it happens to be too small, or divided by a constant if it happens to be too
large, but, in any case, the corresponding adjustment happens only once at each
iteration and does not require an auxiliary inner loop. Overall, the method is
very interesting and definitely requires further attention.

It is also important that the authors do not stop after obtaining a method that
is theoretically optimal but requires the knowledge of certain problem
parameters (such as the Lipschitz constant). Instead, they develop an adaptive
variant of their scheme for the special case of the second-order oracle.
Essentially, they propose a new variant of the "line search" procedure which is
quite different (and also simpler and more efficient) than the standard one that
is typically used in second-order methods. Personally, I find this new
"line search" very interesting and believe it could be of use in a broader
context.

In my opinion, the main part of the paper is clearly written. However, the
quality of the supplementary material is slightly worse.

Please see my detailed remarks in the next section.
questions: Major remarks:

1. Algorithm 2: Please clarify why the loops in lines 4 and 10 are guaranteed to
   terminate eventually.

1. Display between lines 895\-\-896: Please clarify the identity in the second
   line.

1. Lemma 3: 1) There is no need to assume that $r\_1, \\ldots, r\_k$ are integers.
   They can be any nonnegative real numbers. 2) You can assume that $\\beta \= 1$
   as it can always be "incorporated" into $r\_j$ (by defining $r\_j' \= \\beta
   r\_j$). 3) The proof can be considerably simplified. Indeed, denote $C\_i \=
   \\sum\_{j \= 1}^i B\_j r\_j$ for any $0 \\leq i \\leq k$ (with $C\_0 \= 0$). In this
   notation, our relation reads $B\_i^m \\geq C\_i$ (we assume that $\\beta \= 1$).
   Consequently, for any $0 \\leq i \\leq k$,
   $$
   C\_{i + 1} \- C\_i
   \\equiv
   B\_{i + 1} r\_{i + 1}
   \\geq
   C\_{i + 1}^{1 / m} r\_{i + 1},
   $$
   and hence
   $$
   r\_{i + 1}
   \\leq
   \\frac{C\_{i + 1} \- C\_i}{C\_{i + 1}^{1 / m}}
   \\leq
   \\int\_{C\_i}^{C\_{i + 1}} \\frac{d t}{t^{1 / m}}
   \=
   \\frac{m}{m \- 1} (C\_{i + 1}^{(m \- 1) / m} \- C\_i^{(m \- 1) / m})
   $$
   Summing up these inequalities and using $C\_0 \= 0$, we get, for any $1 \\leq i
   \\leq k$,
   $$
   C\_i^{(m \- 1) / m} \\geq \\frac{m \- 1}{m} \\sum\_{j \= 1}^i r\_j.
   $$
   Rearranging and using $B\_i \\geq C\_i^{1 / m}$, we obtain the claim.

Minor remarks:

1. Theorem 1: 1) Please clarify why the final convergence bound does not depend
   on $\\lambda\_0'$. 2) Is the formula for $C\_{\\alpha, s}$ correct? Why is it
   different from the one in lines 700\-\-701? 3) It would be better to add some
   remarks on the "optimal" value of $\\alpha$.

1. Line 278: "equivalent to". Not exactly, the constants are different.

1. How do you choose $\\lambda\_0'$ in the experiments (Section 4)?

1. Line 293: Perhaps you should divide by $6 \\sqrt{3}$ in the formula for the
   Lipschitz constant?

1. Proposition 1: 1) The letter $M$ is already used to denote the regularization
   coefficient in eq. (6), therefore it would be better to rename it. 2) Eq.
   (14): You can remove $A\_0 E\_0$ since $A\_0 \= 0$.

1. Lemma 1: Please clarify that the statement holds for **any** $T \\geq 1$ and
   that the index sets $Q\_T$ and the numbers $r\_{t, T}$ are consistent in the
   sense that $Q\_T \\subseteq Q\_{T + 1}$ and $r\_{t, T} \= r\_{t, T + 1}$ for all $T
   \\geq 1$ and all $t \\in Q\_T$. This is implicitly used later in Section C.3.

1. Proof of Lemma 1: It might be reasonable to write $n\_i$ instead of
   $\\operatorname{next}(\\tau\_i)$ to make the formulas more compact.

1. Line 668: Why $r\_1 \\geq \\frac{1}{2}$? Can it happen that
   $\\operatorname{next}(\\tau\_1) \= 1$ and then $r\_1 \= 0$?

1. Line 669: This is just the arithmetic\-geometric mean (AM\-GM) inequality.

1. Display between lines 670\-\-671: Please clarify what happens with the first
   term ($i \= 1$) in the second inequality. Should we define $r\_1 \=
   \\operatorname{next}(\\tau\_1) \- 1$ (without dividing by $2$)?

1. Section C.3: "The $s < \\infty$ case". It looks as if the case $s \= 1$ needs
   to be considered separately. Otherwise, it is not clear what
   $(\\lambda\_t')^{(s + 1) / (s \- 1)}$, $c^{2 s / (s \- 1)}$, etc. mean.

1. Please clarify that eqs. (27) and (28) hold for **any** $T \\geq 1$.

1. Line 688: Is it true that $r\_t \\geq 1$? According to line 668, we may only
   guarantee that $r\_t \\geq \\frac{1}{2}$.

1. Lemma 9: 1) One should add $\\lambda\_1 > 0$. 2) The claim in line 814 is not
   true in general as $0 \\preceq M\_1 \\preceq M\_2$ does not imply $M\_1^2 \\preceq
   M\_2^2$. Nevertheless, in this particular case, the implication does hold
   since the matrices $M\_1$ and $M\_2$ have the same orthonormal eigenbasis.

Typos:

1. Line 49: "term" $\\to$ "factor"?

1. Lines 51 and 242: "$\\mathcal{O}\_{\\mathrm{cr}}(1)$" $\\to$
   "$\\mathcal{O}\_{\\mathrm{cr}}$"?

1. Algorithm 1: 1) Line 9: Should be $A\_{t + 1} \= A\_{t + 1}'$. 2) Line 14:
   Should be $A\_{t + 1} \= A\_t + a\_{t + 1}$.

1. Algorithm 0: 1) Line 7: Should be $a\_{t + 1}'$ in the second fraction. 2)
   Line 10: Should be $A\_{t + 1} \= A\_{t + 1}'$.

1. Line 101: "$\\mathcal{X}$" $\\to$ "$\\mathbb{R}^d$"? The same applies to lines
   128, 135, ...

1. Line 118: "... very far **from** ...".

1. Footnote 1 (page 4): "... interval ... which always". Remove "which".

1. Line 156: There should be "$\\geq$" in the definition of $S\_T^{\\geq}$.

1. Line 216: $\\lambda$ should be in the right\-hand side, not the left\-hand side.

1. Algorithm 2, line 10: "$\\lambda\_{\\mathrm{vld}}$" $\\to$
   "$\\lambda\_{\\mathrm{invld}}$".

1. Lines 248, 272: What does $\\alpha \= (1.1, O(1))$ mean?

1. Eq. (16): There should be $v\_t \- x\_\*$ and $M\_{t + 1}$. The same applies to
   the display between lines 635\-\-636.

1. Line 630: There should be $\\lambda\_{t + 1}'$.

1. Eq. (17): There should be "$\\leq$" in the second line.

1. Display in lines 635\-\-636: Forgotten $[f(\\tilde{x}\_{t + 1}) \- f^\*]$ at the
   end of the first line.

1. Eq. (18): Should be $M\_{t + 1}$.

1. Line 660: Should be $k \\in (\\operatorname{next}(\\tau\_i), \\tau\_{i + 1}]$
   (including $\\tau\_{i + 1}$).

1. Line 664: 1) "we **have**". 2) Should be
   $\\lambda\_{\\operatorname{next}(\\tau\_i)}' \= \\ldots$ instead of "$\\leq$"?

1. Eq. (26): Rename "$i$" $\\to$ "$j$" in the second sum.

1. Display between lines 691\-\-692: 1) There should be $B\_T$ instead of $B\_t$ in
   the first identity. 2) "for all $t \\in Q\_T$" $\\to$ "for all $T \\geq 1$".

1. Lemma 10: There should be $H / (1 + \\nu)$ instead of $H / 2$ in the displays
   between lines 816\-\-817 and 818\-\-819.

1. Display between lines 895\-\-896: There should be "$\\log\_2$" everywhere.

1. Line 897: "holds **for** every".

1. Display between lines 900\-\-901: Should be $x\_0 \- x\_\*$.
limitations: N/A
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: This paper presents a variant of the Monteiro-Svaiter (MS) acceleration framework that requires no bisection, but which maintains optimal complexity bounds (up to constant factors). The work by MS shows how to accelerate an oracle, and demonstrates the connection with the accelerated proximal point method, as well as establishing complexity guarantees. However, algorithms based upon this framework require the solution of an implicit equation to determine the dynamic regularization parameter, which typically requires the use of bisection, so that there is a 'gap' between the theoretical complexity and the practical behaviour. 

This work 'bridges the gap' by developing an MS variant that requires no bisection, does not involve lots of parameters that need tuning, performs well in practice, and maintains the optimal complexity bounds. Moreover, they develop an adaptive alternative of the cubic regularization oracle that does not require tuning of parameter M (related to the Lipschitz constant of the Hessian), and obtains the optimal Hessian evaluation complexity for functions with order \nu Holder Hessian.

A first order implementation of the adaptive oracle is presented, which uses MinRes/Conjugate Residuals with an adaptive stopping criterion that comes from their analysis. 

Finally, the authors also present numerical experiments in support of their work, and also show that momentum can be harmful for logistic regression. 
strengths_and_weaknesses: I felt that the paper was well written, and the authors clearly identified how their work fitted in with the current literature, and also what the main contributions of the current work are. This was helpful in terms of readability.  
I felt that the contribution (bridging the gap between optimal complexity vs practicality) was nice, and I think is a welcome addition to the field. 

The paper is clearly, by its nature, quite technical. However, I felt that the authors were careful to include additional explanations to contextualize their work. I also felt the inclusion of Section 3.1 was really good. 
questions: .
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work proposes a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the logarithmic factor arises in its bisection procedure in each iteration. The authors then implement the MS oracle using several existing oracles and a new adaptive MS-Newton oracle. When using Taylor descent step to implement MS oracle, the resulting algorithm removes the logarithmic gap between the existing upper bounds and the lower bound for minimizing convex functions with Lipschitz pth order derivative, which resolves an important and challenging open problem in optimization theory. The authors also provide numerical evaluations which show some interesting observation regarding the effect of momentum for second-order methods, and point out several future directions.
strengths_and_weaknesses: This work resolves the open problem of closing the gap between the upper bound and lower bound of minimizing convex functions with Lipschitz pth order derivative, which is a significant contribution. This problem is marked as an "open and challenging question in
Optimization Theory" by Nesterov in his 2018 textbook. The proof is highly technical and hard to verify. However, the authors provide proof sketches and numerical verifications to the proposed schemes, which increases my confidence in the correctness.

The authors also propose adaptive implementations of the MS-oracle for the second order case, and demonstrates the benefits through several numerical evaluations. 

Overall, this is a significant, clearly presented and solid theoretical work. The content is pretty technical which seems not preventable for this research topic (constructing optimal methods). I strongly recommend to accept this work.
questions: I am curious about the connection between the MS framework and the inexact high-order proximal points framework proposed in [1]. They have similar rate of convergence. Can the proposed MS framework serve as an upper-level process in the bi-level minimization framework? Is it possible to obtain lower-order methods that "overpass" traditional limits of the Complexity Theory similar to [1] under the MS framework?


[1] Inexact accelerated high-order proximal-point methods. Y Nesterov. Mathematical Programming, 2021.
limitations: The limitations and the potential negative societal impact have been adequately addressed by the authors.
review_title: null

Meta-review: metareview: The paper proposes a variant of MS acceleration that requires no bisection. This in turn can be used to accelerate the cubic regularization method and other proximal based methods, matching previously established lower bounds. The specialized second order variant requires no knowledge of the lipschitz constant of the Hessian by using what can be considered as a new type of line-search. Furthermore, the level of writing and contributions was enough to motivate the reviewers to examine the paper in depth, including the supplementary material. Finally, the expert reviewers were very impressed with contributions of the paper, and believe this will have repercussions outside of the immediate targeted applications. 
confidence: Certain
Decision: Accept