Optimal and Adaptive Monteiro-Svaiter Acceleration
Authors: Yair Carmon
Danielle Hausler
Arun Jambulapati
Yujia Jin
Aaron Sidford
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
optimization theory
second-order methods
Monteiro-Svaiter acceleration
proximal points
momentum
Newton's method
cubic regularization
conjugate residuals
oracle complexity
optimal algorithms
adaptive methods
parameter-free methods

Abstract: We develop a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the need to solve an expensive implicit equation at every iteration. Consequently, for any $p\ge 2$ we improve the complexity of convex optimization with Lipschitz $p$th derivative by a logarithmic factor,  matching a lower bound. We also introduce an MS subproblem solver that requires no knowledge of problem parameters, and implement it as either a second- or first-order method by solving linear systems or applying MinRes, respectively. On logistic regression problems our method outperforms previous accelerated second-order methods, but under-performs Newton's method; simply iterating our first-order adaptive subproblem solver is competitive with L-BFGS.

Optimal and Adaptive Monteiro-Svaiter Acceleration
Yair Carmon" Danielle Hausler*
Arun Jambulapati
Yujia Jin
Aaron Sidford
Abstract
We develop a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the need to solve an expensive implicit equation at every iteration. Con- sequently, for any 2 2 we improve the complexity of convex optimization with Lipschitz pth derivative by a logarithmic factor, matching a lower bound. We also introduce an MS subproblem solver that requires no knowledge of problem parameters, and implement as either a second- or first-order method via exact linear system solution MinRes, respectively. On logistic regression method outperforms previous second-orde acceleration schemes, but under-perfome New- ton's 's's method; simply iterating first-order adaptive subproblem solver performs comparably to L-BFGS.
Introduction
We consider the problem of minimizing convex function f X' R over closed convex set X' S Rd, given access to an oracle O - that minimizes a local model of f around a given query point. A key motivating example of such oracle the cubic-regularized Newton step
1 Oarly) argmin { ((() Vf() +)+ 1(1 v) ( y) zĒx
M 11 vll
(1)
i... minimizing the second-order Taylor approximation of f around y plus cubic regularization term. However, our results apply to additional oracles including simple gradient step. regularized
higher-order Taylor expansions [5, 19, 23, 8, 35, 21, 41, 36, 26], ball-constrained optimization [12].
and new adaptive oracles that we develop.
Seminal work by Monteiro and Svaiter [32] (MS) shows how accelerate the basic oracle iteration It-1 = (z,). Their algorithm is based on the fact that many oracles, including Oc. implicitly approximate proximal points. That is, for every y and
O(y), there exists Ar.y that argmin,*'t e'x ( (f())) + ll y1|2] J. with the approximation error controlled by a specific condition they define. MS prove that, under this condition, the accelerated proximal point method [22, 40] (with dynamic regularization parameter) maintains its rate of convergence. Applying their framework to Oer and assuming V is Lipschitz, they achieve error bounds that decay as Ot 7/2 log t) after t oracle calls, improving the O(t rate of the basic Ocr iteration [37] and the O(t rate of an earlier accelerated method [33]. Subsequent works apply variations of the MS framework to different oracles, obtaining improved theoretical guarantees for functions with continuous higher-order derivatives [19, 7, 23, 41, 2], parallel optimization [6], logistic and foo regression [8, 12], minimizing functions with Hölder continuous higher derivatives [41], and distributionally-rrbuss optimization [13, 11].
such
However, all of these algorithms based on the MS framework share a common drawback: the iterate Y1 used to produce t Ov)) depends the proximal parameter λr-1 Am which itself depends on both r++1 and yt- This circular dependence necessitates solving an implicit equation for
'Tel Aviv University, boyyyyyyr ycarmon@tauex. tau.ac. i1, hauslerdmail aau.ac.il 1 Stanford University, (jmblpati, siddoiinniddrddddssrtdddd edu
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A4+1; MS (and many subsequent results based upon it) propose bisection procedures for doing so using a number of oracle calls logarithmic in the problem parameters. From a theoretical perspective. the additional bisection complexity introduces logarithmic gap between the upper bounds due to MS-based algorithms and the best known lower bounds [3, 21] in a number of settings.
From a practical perspective, the use of bisection in the MS framework is undesirable as it potentially discards the optimization progress made by oracle calls during each bisection. In his textbook, Nesterov [34, $4.3.3] argues that the logarithmic cost of bisection likely renders the MS scheme for accelerating Oar inferior in practice to algorithms whose error decays the asymptotically worse rate ((t-a) but do not require bisection; he notes that removing the bisection from the MS algorithm is an "open and challenging question in Optimization Theory." Carmon al. [13] also point out bisection as one of the main hurdles in making their theoretical scheme practical, while Song et al. [41] note this limitation and propose a heuristic alternative to bisection. (See Appendix A for extended discussion of related work, including concurrent and independent result by Kovalev and Gasnikov [27].)
1.1 Our contributions
We settle this open question, providing variant of MS acceleration that does not require bisection (Section 2). When combined with certain existing MS oracles (Section 3.1), our algorithm obtains complexity bounds that are optimal up to constant factors, improving over prior art by a logarithmic factor (see Table 1). In addition, our algorithm has no parameters sensitive to tuning.
We then go a step further and (in Section 3.2) develop an adaptive alternative to Oer (Fquation (1)). Our oracle does not require tuning the parameter M, which in theory should be proportional to the (difficult to estimate) Lipschitz constant of f² Using our oracle, we obtain the optimal Hessian evaluation complexity O(t ((t- (4+-3)/22 for functions with order-v Hölder Hessian (Lipschitz Hessian is the V special case), without requiring any knowledge of the Hölder constant and order v. Our oracle is also efficient: while existing complexity bounds for computing Oar require logarithmic number of linear system solutions per call, our oracle requires logarihlo number. Moreover, when used with our acceleration method, the number of linear system solves per iteration is essentially constant.
We also provide a first-order implementation of our adaptive oracle (Section 3.3). It approximately solves linear systems via first-order operations (Hessian-vectte products) using MinRes/Conjjuee Residuals [42, 18] with a simple, adaptive, stopping criterion lifted directly from our analysis. Our oracle attains the optimal first-order evaluation complexity for smooth functions up to additive logarithmic term, without knowledge of the gradient Lipschitz constant or any parameter tuning. Moreover, it maintains an optimal outer iteration complexity for Hölder Hessian of any order.
Finally, we report empirical results (Section 4). On logistic regression problems, combining our optimal acceleration scheme with our adaptive oracle outperforms previously proposed acceler- ated second-order methods. However, we also show that (while somewhat helpful for Oor with conservative choice of H)), adding momentum to well-tuned or adaptive second-order methods is harmful in logistic regression: simply iterating our oracle-or, better yet, applying Newton's 's method-due dramatically outperforms all "accelerated" algorithms. This important fact seems to have gone unobserved in the literature on accelerated second-orde methods, despite logistic regression ap- pearing in many related experiments [41, 16. 30, 24]. Simply iterating our adaptive oracle outperforms the classical accelcrated gradient descent, and performs comparably to L-BFGS.
1.2 Limitations and outlook
While our algorithms resolve an enduring theoretical open problem in convex optimization, and are free of sensitive parameters that typically hinder theoretically methods, practical performance remains a limitation. On logistic regression, Newton's method is remarkably fast, and our acceleration scheme does not seem to help our adaptive oracle. We do not fully understand why this is so, but we suspect that it has to do with additional structure in logistic regression, which Newton's 's method can automatically exploit but momentum cannot. We believe that future research should identify the structure that makes Newton's 's method so efficient, and modifying momentum schemes to leverage it.
'The code for our experiments is available https / http//gtttttuubte com hww.lleeewseeeess-ooooaee optimal.

---

Scalability is another important limitation. While our first-order oracle significantly improves scalability over the second-order oracle from which built, it still relies on exact gradient and Hessian-vector vector products. Therefore, it will have difficulty scaling up to very large datasets. Never- theless, we hope that further scalability improvements may be possible by building an oracle that utilizes cheap stochastic gradient estimates instead of exact gradients, bringing with it the exciting prospect of a new and powerful adaptive stochastic gradient method. The alternative, probabilistic approximation condition we propose in Appendix C might be helpful in this regard.
2 Removing bisection from the Monteiro-Svaiter framework
Algorithm 1: Optimal MS Acceleration
Algorithm O: MS Acceleration
Input: Initial Ty. function f. oracle O Parameters: Initial X6. multiplicative
Input: Initial xo. function f. oracle O Parameters: Bisection limits X Xa, and tolerance p
adjustment factor
Set on 20. Ao 0
Set Uo = To. Ao = 0
2 F1, A1 = (ro; X)) Xi = A1
2 for = 1. do
for / = 0, do
3
X N/41 /+1
X
4/41 2% (1 v I+ 11,
1/41 +
4
A = =A + d'+1
5
4/+1 = -x,,1 (1+ v 41
2
Air1
At It +
Alt11
6
A/+1 = -Ar + 4
if > 0 then I2+1, det1 = Ocvri
Ar + Ker1
As
7
== = Ar, It
if A S X241 then
0:11 4(+1 A441 A/+11
8
i141, = =O(y X/41)
if Ae11 E [1,1411 X then
10
Ø[41 I1+1
9
X4 a 1
10
a++1 = =d41 A 4/41
T(+1 Et+1
12
else
X111
else if A++1 < p N then 12
13
7++ Ae+1
M X/+1
14
at11 71414411 A411 A a++1
14
Go to line 4
(1-241)A4 de +
T01AL1 1 Te+1
15
It+1 Act1
A4t1
15
else
16
X442 a14+1
16
X No41 X/+1
17
0141 Vt -a441 V (((++))
Go to line
Ut+1 ac+1 (ā++1)
In this section we present our acceleration algorithm (Algorithm 1) which removes bisection from the MS method (shown in stylized form as Algorithm 0) and thereby attains optimal rates of convergence. For simplicity. in this section and the next we focus on unconstrained optimization (X' = R and assume that f is continuously differentiable, so that ff exists. In Appendix C we extend our framework to general closed and convex domains and non-differentiable convex objectives.
The key object in both the original MS algorithm and our variant is an oracle O that approximately minimizes a local model of f at query point y. In particular, O satisfies the following approximation error bound, adapted from Monteiro and Svaiter [32, eq. (3.3) (A in [32] is 1/2 in notation).
Definition 1 (MS oracle). An oracle O Rdd x R. + Rd R,, is a o-MS oracle for function RR R for every y E R& and X > 0, the points (x, A) Oy; X') satisfy
|| (y [()()) 0|| w|l-
Definition endows the oracle with an additional output À and an additional input X. The value of A has the following simple interpretation: any point æ satisfying (2) approximately minimizes F(x') = f=') + ||ا' - yll in the sense that [[V](()]] < Ao - y/|- In particular, computing an exact proximal point J argmin,, F(x') and outputting (ar, A) implements a O-MS oracle. The input X' is optional: oracle implementations in prior work do not require it, but our new adaptive
3

---

oracles (described in the next section) use it for improved efficiency. In Appendix C we provide a slightly more general approximation condition for MS oracles that handles non-smooth objectives and bounded domains, as well as different, stochastic condition similar to that of [4, 11].
Let us discuss the key differences between algorithm (Algorithm 1) and the stylized MS algorithm (Algorithm 0). At every iteration, Algorithm O searches for a value X such that Tz+1, A++1 (yti X4+1) satisfies Ac+1 X (note that y/: depends on M4+1). This is done via a bisection procedure iteratively shrinking an interval that contains a successful choice of X This bisection process is inefficient in the sense that every time we reach lines 14 and 17 (highlighted in red) all of the optimization progress made by the last oracle call is discarded.
In contrast, even though our algorithm queries O in the same way (with yr computed based on a guess 14+1). it makes use of the oracle output even if A2+1 is very far from X/+1 thus never discarding progress made by the oracle. Instead of performing bisection, we compare X1+1 and X to guide our next guess 1442. When X overshoots A, we decrease it by factor a (line 11, highlighted in green) and set Ty and A, as in Algorithm O. When it undershoots, we multiply it by a (line 16). In this case, we perform an additional key algorithmic modification which we call the momentum damping mechanism: we scale down the growth of the parameter A4+1 and replace the next iterate with a convex combination of 24 and ē ensure that our overly optimistic guess for \ does not destabilize the algorithm. In Appendix E.6 we demonstrate empirically that this mechanism is important for stabilizing Algorithm 1.
Different MS oracles attain different rates of convergence when accelerated via the MS framework. In the following definition, we distill key property that determines this rate.
Definition 2 (Movement bound). For s 2 L, c, À > O, and x, y E IRd say that (zz, y, A) satisfy (s, mo-oemment bound if
{ (A/ce)1/(o11)
| 211 N { 1/c
<< 00
00,
where a (1, c) movemmnt bound simply means that X S.
In the next section, we will show how to build MS oracles that, given query y, output (z, A) such that (z,, y,, A) always satisfy a (s, c)-movement bound, for certain 8 and e depending on the oracle type and function structure (e.g., level of smoothness). For example, when / has H-Lipschitz Hessian, the cubic-regularized Newton step with M 2H is 1 -MS oracle that guarantees (2, v /H) movemment bound. With the necessary definitions in hand, we are ready to state our main result: the iteration (and MS oracle query) complexity of Algorithm 1.
Theorem 1. Let f Rdd - TR. be corvex and differentiable, and consider Algorithm with parameters > X'> O, and a a aMMS oracle (Definition 1) for f with a E [0, 0.99). Let s Z and > O, and suppose that for all such that x > X₁ or = 1, the iterates (Tz, 3t-11 Ae) satisfy a (s, moveemmtt and Ka = ( a 1/3) such that
>
bound (Definition 2). There exist Ca.e = O min at 3641
s+1
for any x. E Ted and c > O, we have f(IT) f(xx)) S cwhen
Ca.s (C"leo-2.11 BOSI
< 00
T21
Ka (cllao - x. I11 log 2111
s = 0o.
Proof sketch. The remainder of this section is an overview of the proof of Theorem 1, which we provide in full in Appendix B. To simplify this proof sketch, we treat a, c, and 1/(1 - o) as (()),
'Algorithm 0 simplifies the bisection routine of Monteiro and Svaiter [32] and implicitly assumes that an initial interval [X x always contains a valid solution. One can guarantee such an interval exists by selecting very small X and very large X Alternatiely, one may construct valid initial interval via bracketing procedure, as we do the empirical comparison. Either way, the cost is logarithmic in problem parameters.
'It is also possible to set 1 = argmin (( fx) instead of the convex combination in line 15 and maintain our theoretical guarantees.
1
For a fixed s 2 1, the value of minimizing our complexity bound is a" = .... In practice, performance is not sensitive the choice of a (see Appendix E.3).

---

and focus on < oc. To highlight the novel aspects of the proof, let us first briefly recall the analysis
of Algorithm 0 [32. 19, 23, 12]. For every t 1 T let
E = f(r)) ) - f(x=)= D, =
2 1l x.ll and Mt = 2 | - 11-111?
The key facts about the standard MS iterations are
Do
ET
E
A.A,M, S (DD)) and A 201 Σ TE[T] VX
(4)
AT
RE(T)
The first fact implies that the optimality gap at iteration 7 is inversely proportional to Ar. while the latter two facts imply that Ar grows rapidly. More specifically, substituting the movement bound
and X 2 ((())) (thanks the bisection) yields ΣiE(r) X² A. O(o)). Mr 2 (2((()))/(
Combining this with the third fact in (4) and using the reverse Hölder inequality allows to conclude that, for k
s+1 and k'
s-1 3s+1' we have AG 2 (DDD EiETT] AW which, upon
3x+1
further algebraic manipulation, yields Ar 2 (( 1)/2 ()))) Plugging this back to to first fact in (4) gives the claimed convergence rate.
Having described the standard MS analysis, we move on to our algorithm. Our first challenge is re-establishing the facts (4). The difficult case is d > Xr where the standard cancellation that occurs in the MS analysis may fail. This where the momentum damping mechanism (lines 14 and 15 of our algorithm) comes into play, allowing us to show that (See Proposition 1 in the appendix)
Do
PJt
Σ (ES
X,A.M. ((Do) and V AAr 2(1)
Σ
(5)
AT
VX
BEST
where S (1 E (T) X 2 X) and S7. ST. S and SF analogously defined.
Comparing (4) and (5), the price removing the bisection becomes evident: at each iteration (except the first) only one of the terms forcing the growth of Ar receives contribution. The second challenge of our proof is establishing lower bound on v AA in terms of the 1/ 1/vX, values for E S U (1), where the movement bound holds for M,. This is where the multiplicative X' update rule (lines 11 and 16 of the algorithm) comes into play: it allows us to "credit" the contribution of every "down iterate" (in S
) to an adjacent "up" iterate (S7 {1}) and furthermore argue that contribution gets an exponential bonus based the distance between the two. Consequently, are able to identify set Qr C S U [1} of iterates, and a sequence {re} such that (see Lemma 1)
V 2 2(1) Σierr
and Every = -zd.
Repeating the reverse Hölder argument of prior work, we obtain the recursive bound
A 2 2(Dx
Σ AW kr 2 S(D,*) Σ
A r
(6)
1EΩT
with k = 3s+1 and K' = 1-1 Is+1 as before. The final challenge of our proof is to show that such
s+1
recursion implies sufficient growth of A₁. This is where careful algebra comes into play; we show that
(6) implies that AT 2 2 (Eremr r.) (e))3++1)/22)) (s- 112))) (see Lemmas 3 and 4) which establishes our result since Elepr Ft = T-1
3 MS oracle implementations
In this section we describe several oracles that satisfy both Definition (the MS condition) and Definition 2 (movement bounds) and may therefore be used by Algorithm 1. Section 3.1 briefly reviews oracles that have appeared prior work, while Section 3.2 and Section 3.3 describe our new adaptive oracle implementations, We summarize the key oracle properties and resulting complexity bounds Table 1.
3.1 Oracles from prior work
Here we consider several previously-studied oracles of the form (xr, A) O(y), where we omit the second argument X' since prior work does not leverage it to improve implementation efficiency.
5

---

Assumption
Oracle
Complexity with Algorithm 1
Lower bound
V is (1,k)-Hölder"
evals of S
Ω 3o
[3,
p,2-reg
f is 1-Lipschitz
3-reg-so
E Hessian evals
Q
t
[3, 21]
N/A
O r-ball
0
log !
oracle calls
rr-
[12]
Stable Hessian
O B-BaCON
r log }
Hessian evals
f is HHöldr
O aMSN (Alg. 2)
0 E 4430
Hessian evals
② 46:30
[3. 21J
T43r
+ Õ(1) linear systems
f is &-Lipschitz and 2 f is (1,2/)-Höldr f
O aMSN- (Alg. 3)
+ Ó(1) first-order evals
2 (2(55)
[34]
O min (7) 2,, (5)-2, x430
iterations
Table Complexity bounds for finding x such that f(x) fxx) S assuming |
22-1 I| 1, attained by MS oracles from literature (top 4 rows, described in Section 3.1) and oracles we develop (bottom two rows). In all cases we improve on prior work by logarithmic factor. "We require + v 2 2. 'Our adaptive oracles do not require knowledge of continuity constants even the Hölder order v [0. 1].
Gradient descent step [e.g., 34]. As a gentle start, consider the oracle Oga(y) = (y f)) i.e, an oracle that returns x by taking standard gradient step with size yj and À = 1/1.. Obviously, the oracle always satisfies (1, mmoovmmettt bound. Moreover, if we assume that Vf is L-Lipschitz, yll- Therefore, when y 2 L/a the
then || (y - /Vz()) = n/ V+)() Vf(ii < nDIl= oracle is a MS oracle.
Taylor descent step [5, 35, 19, 7, 23, 41). Generalizing both Oga and the cubic-regularized Newton step oracle Oar we define for every integer p 2 and [0, 1] the oracle Op Op.--reg- that, for parameter C' and input y returns (x, A) = O p.r.rog (V) where
M
M | y1lto-2 p!
==
argmin Z'ER
Fp(1:))) + pl(p + vj || - y1lptt x=
w) 01 is the Taylor expansion of f around evaluated at Oracles Ogd and Our correspond to the special cases 11,1-reg (with 17 - and O2 respectively. Clearly, by definition, the oracle always satisfies (p 1, (M/Pl)) movement bound. Moreover, it is easy to show that
and fx(;;) = D +
1 X (V((S) | x
- - vf,(;)) M
pl [Vf(z) - -
Ix - y ptu-2
For any p 2 1 and [0, 1] we say that
VPfin is (H, Hööler if for all x. we have [V) ('uill S H|I - vll'.
(An (H, Höödee derivative is H-Lipschitz.) If V is HHöler, Taylor's theorem gives pf || [41, Lemma 2.5], and so [y- < Therefore, when M 2 H/o the oracle is rMSS oracle.
|| f(= 1) < H
# M vvl-
Exploiting third-order smoothness with a second order oracle [36, 26). For p > 2. comput- ing Op Op.errg is typically intractable due to the need to compute the high-order derivative tensors v f(v), V'f(().... fw). Nevertheless for p = 3 Nesterov [36] designs approximate solver for (7), which we denote Oz.reg-so- using only f() and a logarithmic number of gradient eval- uations. When V f is (Tg, H)-Hölder, [36] shows that O3-reg-so valid MS-oracle satisfying a (3, mmovm)nmmveeenn movement bound, on par with the movement bound of O3,1-1eg-

---

Exact ball optimization oracle [12]. For given query y. consider the exact minimizer of f constrained to a ball of radius around y, i.e. consider an oracle Or-bal such that (z, A) = Or-ball (v) satisfy I E argming':le''wl f(x') and X = --- One may easily verify that (unless A [V = 0) we have I = y - X VV()), and therefore the oracle is a O-MS oracle. Moreover, when f is convex, we have either | - yl = r or is a global minimizer of f. and so may assume without loss of generality that the oracle satisfies an (oo,1/r) movement bound.
Ball- Moll-Constrained Newton (BaCoN) oracle [12]. Exactly implementing Oy-ball is generally in- tractable. Nevertheless, Carmon al. [12. Alg. 3] describe a method O-BaCoN based on solving a sequence of (1)) trust-region problems (ball-constrained Newton steps), which we call that, for functions that are O())-Hessian stable in a ball of radius (or s/r-quasi-self-coooorrfe
and have finite condition number, outputs (x, A) satisfying the 3-M oracle condition and an (oo, ((1/r))- movement bound. Implementing OBCCo requires only single Hessian evaluation and a number of linear system solutions that is polylogarithmic in problem parameters. Subsequent works imple- menting ball oracles [13, 4, 11] satisfy an approximation guarantee different than the MS condition, similar to the one we describe in Appendix C.
3.2 An adaptive Honteiro-Svaiter--eeiii oracle
The oracle implementations in Section 3.1 satisfy movement bounds by design and the MS condi- tion (2) by assumption. For example, the cubic-regularized Newton step oracle Oer is guaranteed to satisfy the MS condition only when the regularization parameter M is sufficiently larger than the Lipschitz constant of f.f. This suggests that M must be carefully tuned ensure good per- formance. Prior work attempt to dynamically adjust M in order to meet certain approximation conditions [14, 20, 21, 24]. However, even computing a single cubic-regularized Newton step entails searching for À that satisfies I| f(y) +
MAA Therefore, such a search over M is 2
essentially a (potentially) redundant double search over A.
We propose more direct and more adaptive MS oracle recipe: search for the smallest for which the regularized Newton step x = [ f(v) + - f'yy) satisfies the MS condition (2).7 This yields valid MS oracle by construction, independently of any assumption. Morcover, it is simple to argue that when f is (H, Ho-Her continuous for some / E [o, 1]. such oracle would guarantee the same movement bound as 22.u-reg with the best choice parameters M and (see Appendix D.I) even though our recipe requires neither of these parameters!
Exactly fulfilling this recipe, i.e., finding the ideal minimal X" that satisfies the MS condition, is difficult. Fortunately, to adaptively guarantee movement bounds, it suffices to find a value such the corresponding regularized Newton step satisfies the MS condition, while the step corresponding to X/2 does not; Algorithm 2 finds precisely such A.
Let us describe the operation of Algorithm 2. If the input X' is invalid (i.e., its corresponding regularized Newton step does not satisfy the MS condition so that CHECKMS(X' y. o) evaluates to False), we set Annid + A' and test a double--xponenntally increasing series of A's, until reaching a valid Avid (line 11). If X' is valid and the LAZY flag is set, we return it immediately. Otherwise X' and decrease it at a double-ex, couble--xponential rate until finding an invalid Ainvia (line 5). In either case (so long as LAZY is not set) we obtain an (invalid, valid)
(if LAZY is not set) we set Avid
pair (Aiuvia: Avia) such that Avia/ Aiva/ 22* at the cost of 2 + k- linear system solutions. We then perform precisely k* log-scale bisection steps in order to shrink Avia/ Amnia down to while maintaining the invariant that Xvia is valid and Ainvid is invalid (line 15).
The following theorem bounds the complexity of Algorithm 2 in terms of linear-system solution number, and establishes a movement bound for its output assuming that 2 is locally Hölder around the query point. We defer the proof of the theorem and its following corollary to Appendix D.2.
Theorem 2. Algorithm 2 with parameter is MM oracle OAMSN. For any y E IRd, computing (x, A) = OMMSN(y) requires at most 2 + 2 loga (1 + llog 1) linear systems solutions. LAZY is False or x > X, and if V2 is (H, -ööder in a ball of radius 2||z - yll around y, then (I. y, A) satisfy a (1 + v, (2H /a) 1/(+vv) /a) moovement bound.
'The prior works [30, 17] also directly consider auudratically-reularizz Newton steps, but employ approxi- mation conditions other than (2) to select the parameter X.
7

---

Algorithm 2: OAMSN
Algorithm 3: OaMSN-fo
Input:
Query y E Rd X > O. Flag LAZY.
Input: y E IR > O. Flag LAZY.
Parameters:
MS factor E (0.
Parameters: MS factor E (0, 1).
CHECKMS (X:; y,, v) then
À - X FAILEDCHECK < False
if LAZY then return
Repeat
y [()) - else
A < + -ea----jji -VS(v)
b Apply MinRes/Conjugate Residuals [18] until obtaining w | bll S 2/ [
Avid + X, 0+0 while CHECKMS(ANML) :.. do
x +- y + CONIRES A, b, Aa)
|| 1|-- (v [v(()) & o yll
Avid f Avid/22 /22 k k+11
then
if LAZY FAILEDCHECK then return æ, À
k- t- Xineld Avia/22"
else À 2/2
else
else
10
Aineld c +
10
FAILEDCHECK < True
while not CHECKMS (Aiavid oy)
A + 2A
do
Ainvdd 2 t- l: +
12 function CONJRES (A, Ao)
13
Win 0
he + Avid Xinvid
14
Po f- ro f- Awo -
D = Aw; -
14
So < 90 Aro
qi Ap,
while Ainvid Auta do
16
i 5+0 0
17
A + AiniiaAvii
CHECKMS y, o)) then Avid f À
17
while ||r:||
> Aa w do
2
(1
else Ainvid +-
18
W w;
|1 Pr
(r,
return y - f(y) + Avall VV Avia
19
Ti+1 f rj
110:112 qi
81+1
Ar1+1
20
21
function CHECKMS ();
I y/ 1V- s(y) + M -V)
21
Pi+1
(14418841)
(11-1.8111)
(Miies)
Pi + Fi+1
22 if r- x [f())) S < l/l
22
96+1 (-
(re.3e)
9: + 8i+1
then return True
23
i 1 1+11
else return False
return W;
To understand the LAZY option of Algorithm 2, note that when X' is valid we will necessarily output < X. In such case Theorem does not require movement bound (except for the first iteration). Therefore, we might as well save on computation and return X' The following Corollary gives the overall complexity bound for the combination of Algorithm and OaMSN, leveraging "lazy" oracle calls show that the number of linear system solves per iteration essentially constant.
Corollary 3. Consider Algorithm I with initial point To- parameters satisfying 1.1 S a O(1) and Xg- and a-MS oracle O OAMSN (with LAZY True in all but the first iteration) with E (0.01, 0.99). For any H.e Hölder Hessian, the algorithm produces an iterate such that f(IT) S f(x.) + using T =
v [0, 1] and any I. Rdd. if f is convex with (H,
O (H] - z. s2lltt/ee) 2/(4+33)) 22((at))) Hessian evaluations and O (T + log log max ear system solutions, where R is the distance between Zn and argming. f(x').
HR" N,R
}) lin-
X
Note that as long as X/ is in the range [2-2" H", 22" eR eR-2]. the double logarithmic term in our bound on linear system solution number is O(T). Therefore, the overall bound is O(T) for an extremely large range of Xn values.
3.3 First-order implementation via MinRes/Conjugate Residuals
We now present first-order implementation of our adaptive oracle, OaMSN-Io (Algorithm 3), which replaces exact linear system solutions with approximations obtained via Hessian-vectt -ectoor products and the MinRess/Cnjugate Residuals method [42, 18]. Similar to Algorithm 2, the algorithm searches

---

for À such that yλ = y (V())) satisfies the MS condition, but 2x/2 does not. Departing from the double-exponential scheme of Algorithm 2, here we adopt the following doubling scheme that allows us to control the cost of the æ approximation. If X is such that xx does not satisfy the MS condition, we repeatedly test À = 2X', 2X,4X, 4 ,'.'.... .... and return the first one for which aa satisfies the MS condition. If zx satisfies the MS condition and the algorithm is LAZY, we immediately return it. Otherwise, we repeatedly test À = 2 2X1, LN,... until reaching for which Z does not satisfy the MS condition, and return 22A-
The subroutine CONURES of Algorithm takes as imput matrix A, a vector b, and accuracy parameter λo, and iteratively generates { } that approximate A bb. The construction of the MinRes/Conjugen Residuals method guarnatees that w minimizes the norm of the residual r; Au; b in the Krylov subspace span{b, Ab,... A' bb. The key algorithmic decision here is when to stop the iterations: stop too early, and the approximation for the Newton step might not be accurate enough to guarantee movement bound; stop too late, and incur a high Hessian-vector product complexity. We introduce a simple stopping condition (line 17) that strikes a balance. On the one hand, we show that whenever the condition ||r:|] Ae || holds, the resulting point can certify roughly the same movement bounds as exact Newton steps. On the other hand, by invoking the complexity bounds in [28] and using the the optimality of ||rsll, we guarantee that the stopping condition is met within a number of iterations proportional to 1/VA. The structure of our doubling scheme for À then allows us to relate the overall first-order complexity to the lowest value of À queried, obtaining the following guarantees. See proof's in Appendix D.3.
Theorem Algorithm with parameter a is a a-MS oracle OaMSN-o- For any y E RR com- Hessian-vector product and O[1og x gradient computations. LAZY is False or X > X, and if V is (H,v)-Hölder then (z, U, A) satisfy (1 + (,HHHo/) (6H/o) -movement bound.
puting (I, A) OaMSNtoly) requires at most O (V 1+ /
mii((),)))
Corollary 5. Consider Algorithm with initial point Fo, parameters a satisfying 1.1 aa1 and Ng- and a-MS oracle OaMSN-t with LAZY set to True in all but the first iteration and E (0.01, 0.99). For any L, H, > 0, v E [0, and any In E Rd, if f is convex with (II, H)-öldr Hessian and L-Lipschitz gradient, the algorithm produces an iterate øT such 2/(4+30)
x, 1121 that f(IT) S f(x.) within T = -((
iterations and most
(( (HRoo=Zl1)) 1/2
+ log % I.) X
gradient and Hessian product evaluations.
Note that the T--Lipschitz gradient assumption implies an (I. -)- Hessian assumption, giv- ing the iteration complexity bound we state in Table 1. Moreover, note that our algorithm has the optimal O(v L| x. ll2 complexity for any X in the range S?(e/1|zo - x. 1|²) to L exp ((V - x. (3 }. By choosing a large X/ (say 10%) we may guarantee that only the logarithmic term is added the optimal first-order evaluation complexity.
4 Experiments
We conduct three sets of experiments. First, we consider Oz with fixed parameter M and compare previous acceleration schemes to Algorithm 1. Second, we combine Algorithm with our adaptive O and test it against previous adaptive accelerated (second-order) methods and Newton's method. Finally, we compare Algorithm with our first-order adaptive oracle OaMSN-to to other first-order methods. We provide full implementation details in Appendix 1. Figure I summarizes our results for logistic regression on the 'a9a' dataset [15]; see Appendix E.2 for similar results on three additional datasets. These experiments were conducted with tuning of Algorithm 1: the parameters a and a were simply set to and 2, respectively. An additional experiment, reported in Appendix E.3, shows that the algorithm is indeed insensitive to that choice.
ada-atee methods. We use the non-adaptive oracle Oor (1), and take M to 0.2H where, for feature vectors Φ1, ..,,,...... Pn. H = || Σx_ Φi !lop max || |I is an upper bound on 6/33 Rs 10 times the Lipschitz constant of the logistic regression Hessian [see, e.g., 41]. Fixing the MS oracle

---

Non-adpative methods
Adpative methods and Newtons' method
First-order methods
20a
10
Song
Adaptive
Ituned n=
ACR
Alg. 0
10
Alg.1 Cusn-n
Alg. 1 + Qges
Ag.. Oer
Iterating PaRcN
Iterating Parss-ro
Alg. 0a
Newton's methad
L-BFGS-6
optima ity
20-1
10-1-
10mh
10-
10rl
200
200
1000
Hessian evaluaaions
Hessian evalluations
First-order evaluations
(a)
(b)
(c)
Figure Empirical results for logistic regression the "a9a" dataset. See Section for description,
and Appendix E.2 for additional datasets. Boldface legend entries denote methods we contribute.
allows for a controlled comparison of different acceleration schemes: Figure ((a) shows that standard MS acceleration with carefully-implemmnneed bisection outperforms standard cubic regularization (CR) and its accelerated counterpart (ACR) [33, Alg. 4.8), and removing the bisection via Algorithm yields the best results. We also implemented the heuristic suggested by Song al. [41], where instead of a bisection in Algorithm we select a sequence X; such that A, = M | (t/3) 7/2 In Appendix E.4 we tune the M parameter for each method separately, finding that the optimal M for CR is near so that Our is nearly a Newton step (and not valid MS oracle).
Adaptive methods and Newton's method. We compare the following adaptive accelerated second- order methods (which do not require an estimate of the Hessian Lipschitz constant): Adaptive ACR (21, Algorithm 4] (which adaptively sets M in Oar), standard MS acceleration (Algorithm 0) with OAMSN (Algorithm 2, with LAZZ False) and Algorithm with OaMSN (with L.AZY True in all but the first iteration). Figure ((b) shows that the latter converges significantly faster than the other adaptive accelcration schemes. However, the classical "unaccelerated" Newton iteration Tt-1 - (V f(x;)) - V f(x) strongly outperforms all "accelerated" methods, indicating that momentum mechanisms might actually be slowing down convergence in logistic regression problems. To test this, we consider the following simple iteration of (the non-lazy variant) of our oracle: It-1, A O aMSNN (zz; ; A₂ k2); :);;t significantly improves over Algorithm
These results beg the question: is momentum ever useful for second-order methods? In Appendix E.5 we test different schemes on the lower bound construction [3, 21J. We find momentum is helpful for Ocr, but not for the adaptive oracle O OaMSN- What makes Newton's 's method perform so well on logistic regression, and whether simply iterating OaMSN is worst-case optimal, are important questions for future work.
First-order methods. We compare our first-order adaptive OaMSN-to (Algorithm 3) to the following baselines: gradient descent and accelerated gradient descent [38] with a tuned step size 7), and L- BFGS-B from SciPy [10, 44, 43]. In light of the above comparison with Newton's 's method,
also test the following simple iteration of (the lazy variant) of our oracle: It-1, A4+1 = O aaMSN-o (1y;; 2r/2). Figure ((c) shows that forgoing (second-order) momentum is better for the first-order oracle, too: Algorithm 1 performs comparably to tuned AGD (without tuning a single parameter), and the equally adaptive ia iteration performs comparably with L-BFGS-B.
Acknowledgments
We thank the anonymous reviewers for helpful questions and suggestions, leading to important writing clarifications, simplification of the proof of Lemma 3, and an improved complexity bound for second-order methods under third-order smoothness (due to the observation that our framework compatible with the oracle of [36]). YC and DH were supported part by the Israeli Science Foundation (ISF) grant no. 2486/21, the Len Blavatnik and the Blavatnik Family foundation and the Adelis Foundation. was supported in part by a Stanford Graduate Fellowship and the Dantzig- Lieberman Fellowship. AS was supported in part by a Microsoft Research Faculty Fellowship. NSF CAREER Award 184485,, NSF Grant CCF-1955039, PayPal research award, and Sloan Research Fellowship.
10

---

References
[1] D. Adil, B. Bullins, A. Jambulapati, and S. Sachdeva. Line search-free methods for higher-order smooth monotone variational inequalities. arXiv:2205.06117, 2022.
[2] M. M. Alves, Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods. vrXiv:2102.02045 2021.
[3] Y. Arjevani, O. Shamir, and Shiff. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming. 178(1-2):327-360, 2019.
[4] H. Asi, Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Stochastic bias-reduced gradient methods. Advances in Neural Information Processing Systems, 34, 2021.
[5] M. Baes. Estimate sequence methods: extensions and approximations. Optimization Online, 2009.
[6] S. Bubeck, Jiang Y. T. Lee, Y. Li, and A. Sidford. Complexity of highly parallel non-smooth convex optimization. arXiv: 1906. 10655 [math. OC], 2019.
[7] S. Bubeck, Q. Jiang, Y. T. Lee, Y. Li, and A. Sidford. Near-optimal method for highly smooth convex optimization. In Proceedings of the Thirty Second Annual Conference on Computational Learning Theory, pages 492-507, 2019.
[8] B. Bullins. Highly smooth minimization of non-smooth problems. In Conference Learning Theory, pages 983- 2020.
[9] B. Bullins and K. A. Lai. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. arXiv:2007.066 04520, 2020.
[10] R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on scientific computing, 16(5): 190-1128, 1995.
[11] Y. Carmon and D. Hausler. Distributionally robust optimization via ball oracle acceleration. arXiv:2203.13225 2022.
[12] Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y. Lee, A. Sidford, and K. Tian. Acceleration with ball optimization oracle. In Advances in Neural Information Processing Systems, 2020.
[13] Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference on Learning Theory, 2021.
[14] C. Cartis, N. I. M. Gould, and P. L. Toint. Adaptive cubic regularisation methods for uncon- strained optimization, part II: worst-case function- and derivattive-evallation complexity. Math. Program., 130(2):255-319) 2011.
[15] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http: ntu.
/ / www. csie. ntu. edu. tu/"<jjin/libbst
[16) N. Doikov and Y. Nesterov. Inexact tensor methods with dynamic accuracies. In International Conference on Machine Learning, 2020.
[17] N. Doikov and Y. Nesterov. Gradient regularization of Newton method with Bregman distances. arX1v:211..02952. 2021.
[18] D. C.-L. Fong and M. Saunders. CG versus MINRES: An empirical comparison. Sultan Qaboos University Journal for Science (SQUJS), 17(1):44-62 62, 2012.
[19] A. V. Gasnikov, P. E. Dvurechensky, E. Gorbunov, E. A. Vorontsova, D. Selikhanovych, and C. A. Uribe. Optimal tensor methods in smooth convex and uniformly convex optimization. In Proceedings of the Thirty Second Annual Conference on Computational Learning Theory, pages 1374-1391, 2019.
11

---

[20] N. I. M. Gould, M. Porcelli, and P. L. Toint. Updating the regularization parameter in the adaptive cubic regularization algorithm. Comput. Optim. Appl., 53(1):1-22, 2012.
[21] G. N. Grapiglia and Y. Nesterov. Tensor methods for minimizing convex functions with Hölder continuous higher-order derivatives. SIAM Journal on Optimization, 30(4):2750-2779 2020.
[22] O. Güler. New proximal point algorithms for convex minimization. SIAM Journal on Optimiza- lion, 2(4):649-664, 1992.
[23] B. Jiang, H. Wang, and S. Zhang. An optimal high-order tensor method for convex optimization. In Proceedings of the Thirty Second Annual Conference on Computational Learning Theory, pages 1799-1801, 2019.
[24] B. Jiang, T. Lin, and S. Zhang. A unified adaptive tensor approximation scheme accelerate composite convex optimization. SIAM Journal on Optimization, 30(():2897-22) 2926, 2020.
[25] R. Jiang and A. Mokhtari. Generalized optimistic methods for convex-concave saddle point problems. arXiv:2202. 026774 2022.
[26] D. Kamzolov and A. Gasnikov. Near-optimal hyperfast second-order method for convex optimization and its sliding. arXiv:2002.09055 2020.
[27] D. Kovalev and A. Gasnikov. The first optimal acceleration of high-order methods in smooth convex optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[28] J. Lee, C. Park, and E. Ryu. A geometric structure of acceleration and its role in making gradients small fast, Advances in Neural Information Processing Systems, 2021.
[29] T. Lin and M. Jordan. Perseus: A simple high-order regularization method for variational inequalities. arXiv:2205.03200 2022.
[30] K. Mishchenko. Regularized Newton method with global O(1/k²) convergence.
12X10:21 2021.
[31] R. D. Monteiro and B. F. Svaiter. corppixn-complexity of a Newton proximal extragradi- ent method for monotone variational incqualities and inclusion problems. SIAM Journal on Optimization, 22(3);914-935, 2012.
[32] R. D. C. Monteiro and B. F. Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Optim., 23(2): 1092-1125, 2013.
[33] Y. Nesterov. Accelerating the cubie regularization of Newton's method on convex problems. Mathematical Programming, 112(1):159-188) 2008.
[34] Y. Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[35] Y. Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical Programming, 186(1):157-183, 2021.
[36] Y. Nesterov. Superfast second-order methods for unconstrained convex optimization, Journal of Optimization Theory and Applications, 191(1):1-30, 2021.
[37] Y. Nesterov and B. T. Polyak. Cubic regularization Newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
[38] Y. E. Nesterov. A method for solving the convex programming problem with convergence rate of (1/12)). In Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
[39] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning Python, Journal of Machine Learning Research, 112885-28830 2.1
12

---

[40] S. Salzo and S. Villa. Inexact and accelerated proximal point algorithms. Journal of Comvex analysis, 1974:11677-192. 2012.
[41] C. Song, Jiang, and Y. Ma. Unified acceleration high-order algorithms under Hölder continuity and uniform convexity. SIAM Journal Optimization, 2021.
[42] E. Stiefel. Relaxationsmethoden bester strategie lösung linearer gleichungssysteme. Com-
mentarii Mathematici Helvetici, 29(1):157-179, 1955.
[43] Virtanen, R. Gommers, T. F. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, Peterson, W. Weckesser, J. Bright, S. van der Walt, M. Brett, Wilson, K. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, I. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, Perktold, R. Cimrman, I. Henriksen, A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing Python. Nature Methods, 17:261-272 2020.
[44] Zhu, R. H. Byrd, P. Lu, and J. Nocedal. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Transactions on mathematical software (TOMS), 2345)550--560 1997.
13


Reviews:
[{"review_id": "vXYleHMb2Tk", "reviewer": "Reviewer_dAbm", "summary": "In this paper, the authors present a new version of the Monteiro-Svaiter (MS)\nacceleration framework. The main feature of this new version, compared to the\noriginal MS framework, is that there is no need to (approximately) solve a\ncomplicated nonlinear equation at every iteration that adds an extra logarithmic\nfactor to the total oracle complexity of the algorithm. As a result, the new\nframework allows constructing optimal tensor methods of any order $p \\geq 1$\n(without any hidden logarithmic factors in the final complexity bound). In the\nspecial case, that corresponds to the second-order method ($p = 2$), the authors\nadditionally propose a novel efficient procedure for solving the auxiliary\nsubproblem that arises at each iteration of the method. This procedure can be\nseen as an alternative to the standard \"line search\" which is typically used for\nan adaptive estimation of the Lipschitz (or Hölder) constant of the Hessian. In\nthe end, the authors obtain a new \"universal\" second-order method that requires\nno knowledge of the problem parameters, and can be implemented using either an\nexact linear system solver or an auxiliary conjugate gradient-type method.\nFinally, the authors present several numerical experiments which confirm the\nefficiency of their approach, and raise several interesting open questions.", "questions": "Major remarks:\n\n1. Algorithm 2: Please clarify why the loops in lines 4 and 10 are guaranteed to\n   terminate eventually.\n\n1. Display between lines 895\\-\\-896: Please clarify the identity in the second\n   line.\n\n1. Lemma 3: 1) There is no need to assume that $r\\_1, \\\\ldots, r\\_k$ are integers.\n   They can be any nonnegative real numbers. 2) You can assume that $\\\\beta \\= 1$\n   as it can always be \"incorporated\" into $r\\_j$ (by defining $r\\_j' \\= \\\\beta\n   r\\_j$). 3) The proof can be considerably simplified. Indeed, denote $C\\_i \\=\n   \\\\sum\\_{j \\= 1}^i B\\_j r\\_j$ for any $0 \\\\leq i \\\\leq k$ (with $C\\_0 \\= 0$). In this\n   notation, our relation reads $B\\_i^m \\\\geq C\\_i$ (we assume that $\\\\beta \\= 1$).\n   Consequently, for any $0 \\\\leq i \\\\leq k$,\n   $$\n   C\\_{i + 1} \\- C\\_i\n   \\\\equiv\n   B\\_{i + 1} r\\_{i + 1}\n   \\\\geq\n   C\\_{i + 1}^{1 / m} r\\_{i + 1},\n   $$\n   and hence\n   $$\n   r\\_{i + 1}\n   \\\\leq\n   \\\\frac{C\\_{i + 1} \\- C\\_i}{C\\_{i + 1}^{1 / m}}\n   \\\\leq\n   \\\\int\\_{C\\_i}^{C\\_{i + 1}} \\\\frac{d t}{t^{1 / m}}\n   \\=\n   \\\\frac{m}{m \\- 1} (C\\_{i + 1}^{(m \\- 1) / m} \\- C\\_i^{(m \\- 1) / m})\n   $$\n   Summing up these inequalities and using $C\\_0 \\= 0$, we get, for any $1 \\\\leq i\n   \\\\leq k$,\n   $$\n   C\\_i^{(m \\- 1) / m} \\\\geq \\\\frac{m \\- 1}{m} \\\\sum\\_{j \\= 1}^i r\\_j.\n   $$\n   Rearranging and using $B\\_i \\\\geq C\\_i^{1 / m}$, we obtain the claim.\n\nMinor remarks:\n\n1. Theorem 1: 1) Please clarify why the final convergence bound does not depend\n   on $\\\\lambda\\_0'$. 2) Is the formula for $C\\_{\\\\alpha, s}$ correct? Why is it\n   different from the one in lines 700\\-\\-701? 3) It would be better to add some\n   remarks on the \"optimal\" value of $\\\\alpha$.\n\n1. Line 278: \"equivalent to\". Not exactly, the constants are different.\n\n1. How do you choose $\\\\lambda\\_0'$ in the experiments (Section 4)?\n\n1. Line 293: Perhaps you should divide by $6 \\\\sqrt{3}$ in the formula for the\n   Lipschitz constant?\n\n1. Proposition 1: 1) The letter $M$ is already used to denote the regularization\n   coefficient in eq. (6), therefore it would be better to rename it. 2) Eq.\n   (14): You can remove $A\\_0 E\\_0$ since $A\\_0 \\= 0$.\n\n1. Lemma 1: Please clarify that the statement holds for **any** $T \\\\geq 1$ and\n   that the index sets $Q\\_T$ and the numbers $r\\_{t, T}$ are consistent in the\n   sense that $Q\\_T \\\\subseteq Q\\_{T + 1}$ and $r\\_{t, T} \\= r\\_{t, T + 1}$ for all $T\n   \\\\geq 1$ and all $t \\\\in Q\\_T$. This is implicitly used later in Section C.3.\n\n1. Proof of Lemma 1: It might be reasonable to write $n\\_i$ instead of\n   $\\\\operatorname{next}(\\\\tau\\_i)$ to make the formulas more compact.\n\n1. Line 668: Why $r\\_1 \\\\geq \\\\frac{1}{2}$? Can it happen that\n   $\\\\operatorname{next}(\\\\tau\\_1) \\= 1$ and then $r\\_1 \\= 0$?\n\n1. Line 669: This is just the arithmetic\\-geometric mean (AM\\-GM) inequality.\n\n1. Display between lines 670\\-\\-671: Please clarify what happens with the first\n   term ($i \\= 1$) in the second inequality. Should we define $r\\_1 \\=\n   \\\\operatorname{next}(\\\\tau\\_1) \\- 1$ (without dividing by $2$)?\n\n1. Section C.3: \"The $s < \\\\infty$ case\". It looks as if the case $s \\= 1$ needs\n   to be considered separately. Otherwise, it is not clear what\n   $(\\\\lambda\\_t')^{(s + 1) / (s \\- 1)}$, $c^{2 s / (s \\- 1)}$, etc. mean.\n\n1. Please clarify that eqs. (27) and (28) hold for **any** $T \\\\geq 1$.\n\n1. Line 688: Is it true that $r\\_t \\\\geq 1$? According to line 668, we may only\n   guarantee that $r\\_t \\\\geq \\\\frac{1}{2}$.\n\n1. Lemma 9: 1) One should add $\\\\lambda\\_1 > 0$. 2) The claim in line 814 is not\n   true in general as $0 \\\\preceq M\\_1 \\\\preceq M\\_2$ does not imply $M\\_1^2 \\\\preceq\n   M\\_2^2$. Nevertheless, in this particular case, the implication does hold\n   since the matrices $M\\_1$ and $M\\_2$ have the same orthonormal eigenbasis.\n\nTypos:\n\n1. Line 49: \"term\" $\\\\to$ \"factor\"?\n\n1. Lines 51 and 242: \"$\\\\mathcal{O}\\_{\\\\mathrm{cr}}(1)$\" $\\\\to$\n   \"$\\\\mathcal{O}\\_{\\\\mathrm{cr}}$\"?\n\n1. Algorithm 1: 1) Line 9: Should be $A\\_{t + 1} \\= A\\_{t + 1}'$. 2) Line 14:\n   Should be $A\\_{t + 1} \\= A\\_t + a\\_{t + 1}$.\n\n1. Algorithm 0: 1) Line 7: Should be $a\\_{t + 1}'$ in the second fraction. 2)\n   Line 10: Should be $A\\_{t + 1} \\= A\\_{t + 1}'$.\n\n1. Line 101: \"$\\\\mathcal{X}$\" $\\\\to$ \"$\\\\mathbb{R}^d$\"? The same applies to lines\n   128, 135, ...\n\n1. Line 118: \"... very far **from** ...\".\n\n1. Footnote 1 (page 4): \"... interval ... which always\". Remove \"which\".\n\n1. Line 156: There should be \"$\\\\geq$\" in the definition of $S\\_T^{\\\\geq}$.\n\n1. Line 216: $\\\\lambda$ should be in the right\\-hand side, not the left\\-hand side.\n\n1. Algorithm 2, line 10: \"$\\\\lambda\\_{\\\\mathrm{vld}}$\" $\\\\to$\n   \"$\\\\lambda\\_{\\\\mathrm{invld}}$\".\n\n1. Lines 248, 272: What does $\\\\alpha \\= (1.1, O(1))$ mean?\n\n1. Eq. (16): There should be $v\\_t \\- x\\_\\*$ and $M\\_{t + 1}$. The same applies to\n   the display between lines 635\\-\\-636.\n\n1. Line 630: There should be $\\\\lambda\\_{t + 1}'$.\n\n1. Eq. (17): There should be \"$\\\\leq$\" in the second line.\n\n1. Display in lines 635\\-\\-636: Forgotten $[f(\\\\tilde{x}\\_{t + 1}) \\- f^\\*]$ at the\n   end of the first line.\n\n1. Eq. (18): Should be $M\\_{t + 1}$.\n\n1. Line 660: Should be $k \\\\in (\\\\operatorname{next}(\\\\tau\\_i), \\\\tau\\_{i + 1}]$\n   (including $\\\\tau\\_{i + 1}$).\n\n1. Line 664: 1) \"we **have**\". 2) Should be\n   $\\\\lambda\\_{\\\\operatorname{next}(\\\\tau\\_i)}' \\= \\\\ldots$ instead of \"$\\\\leq$\"?\n\n1. Eq. (26): Rename \"$i$\" $\\\\to$ \"$j$\" in the second sum.\n\n1. Display between lines 691\\-\\-692: 1) There should be $B\\_T$ instead of $B\\_t$ in\n   the first identity. 2) \"for all $t \\\\in Q\\_T$\" $\\\\to$ \"for all $T \\\\geq 1$\".\n\n1. Lemma 10: There should be $H / (1 + \\\\nu)$ instead of $H / 2$ in the displays\n   between lines 816\\-\\-817 and 818\\-\\-819.\n\n1. Display between lines 895\\-\\-896: There should be \"$\\\\log\\_2$\" everywhere.\n\n1. Line 897: \"holds **for** every\".\n\n1. Display between lines 900\\-\\-901: Should be $x\\_0 \\- x\\_\\*$.", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is an excellent work that has at least two significant contributions.\n\nFirst, the authors solve an important open problem of constructing an optimal\ntensor method that does not have any extra logarithmic factors in its complexity\nestimate. Their solution is quite elegant in that their method is essentially\nthe original MS algorithm with a couple of small (but nontrivial) modifications.\nSpecifically, instead of having an inner loop searching for an (approximate)\nsolution to the nonlinear equation, they simply make one step (of the basic\nmethod) and then check if a certain condition is satisfied: if yes, they keep\nthe result and go to the next iteration; if no, they take the average of the\n\"unsuccessful\" new point and the current one, and also go the next iteration. In\naddition to that, they have a very simple adaptation procedure for the \"guess\"\nof the solution to the nonlinear equation: it is either multiplied by a constant\nif it happens to be too small, or divided by a constant if it happens to be too\nlarge, but, in any case, the corresponding adjustment happens only once at each\niteration and does not require an auxiliary inner loop. Overall, the method is\nvery interesting and definitely requires further attention.\n\nIt is also important that the authors do not stop after obtaining a method that\nis theoretically optimal but requires the knowledge of certain problem\nparameters (such as the Lipschitz constant). Instead, they develop an adaptive\nvariant of their scheme for the special case of the second-order oracle.\nEssentially, they propose a new variant of the \"line search\" procedure which is\nquite different (and also simpler and more efficient) than the standard one that\nis typically used in second-order methods. Personally, I find this new\n\"line search\" very interesting and believe it could be of use in a broader\ncontext.\n\nIn my opinion, the main part of the paper is clearly written. However, the\nquality of the supplementary material is slightly worse.\n\nPlease see my detailed remarks in the next section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vBfwlBg8u0", "reviewer": "Reviewer_RYyk", "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.", "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?\n\n\n[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.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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\nOptimization 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.\n\nThe authors also propose adaptive implementations of the MS-oracle for the second order case, and demonstrates the benefits through several numerical evaluations. \n\nOverall, 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZNUUvMdPzVw", "reviewer": "Reviewer_Zcbv", "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. \n\nThis 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.\n\nA first order implementation of the adaptive oracle is presented, which uses MinRes/Conjugate Residuals with an adaptive stopping criterion that comes from their analysis. \n\nFinally, the authors also present numerical experiments in support of their work, and also show that momentum can be harmful for logistic regression. ", "questions": ".", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.  \nI felt that the contribution (bridging the gap between optimal complexity vs practicality) was nice, and I think is a welcome addition to the field. \n\nThe 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9zjO2jyoLy7", "reviewer": "Reviewer_RLWS", "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. ", "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. \n\nIn 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 \n$$ \\Vert x - (y - \\frac{1}{\\lambda} \\nabla f(x)) \\Vert \\le \\sigma \\Vert x- y \\Vert $$\nHowever, 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 \n$$F(z) := f(z) + \\frac{\\lambda}{2} \\Vert z - y \\Vert^2 $$\nto 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. \n\nAnother 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. \n\nMinor questions: \nIn 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. \n\nLiterature: \nI believe the following literature on accelerated proximal point algorithms are related (as special case $\\lambda' =\\lambda$)\n1.  Inexact and accelerated proximal point algorithms.  Salzo and Villa\n2. 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 ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: Theoretical improvement on existing MS framework\nWeakness: very hard to follow, the presentation need to be improved. More clarification on several key technical component is required. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept