A Damped Newton Method Achieves Global $\mathcal O \left(\frac{1}{k^2}\right)$  and Local Quadratic  Convergence Rate
Authors: Slavomir Hanzely
Dmitry Kamzolov
Dmitry Pasechnyuk
Alexander Gasnikov
Peter Richtárik
Martin Takáč
Venue: NeurIPS 2022 Accept (2022)
Keywords: Cubic Newton method
Damped Newton method
fast global convergence
convex optimization

Abstract: In this paper, we present the first stepsize schedule for Newton method resulting in fast global and local convergence guarantees. In particular, we a) prove an $\mathcal O \left( 1/{k^2} \right)$ global rate, which matches the state-of-the-art global rate of cubically regularized Newton method of Polyak and Nesterov (2006) and of regularized Newton method of Mishchenko (2021), and the later variant of Doikov and Nesterov (2021), b) prove a local quadratic rate, which matches the best-known local rate of second-order methods, and c) our stepsize formula is simple, explicit, and does not require solving any subproblem. Our convergence proofs hold under affine-invariant assumptions closely related to the notion of self-concordance. Finally, our method has competitive performance when compared to existing baselines which share the same fast global convergence guarantees.

A Damped Newton Method Achieves Global O and Local Quadratic Convergence Rate
1 1.2
Slavomír Hanzely MBZUA KAUST shanzelydgmaii com
Dmitry Kamzolov"
Dmitry Pasechnyuk
MBZUAI kamzolov. copt@gmail.. com
MBZUAI! MIPT ISP RA dmivilensky @gmail
Alexander Gasnikov MIPT ISP RAS HSE]
Peter Richtárik KAUST ri rricttarikgmail.com
Martin Takáč
MBZUAI
gasnikovsyandex.
takac Mel...M@@mmii..omm
Abstract
In this paper, we present the first stepsize schedule for Newton method resulting in fast global and local convergence guarantees. In partieular, a) we prove an O (==) global rate, which matches the state-of ofute-of-thh-arr global rate of cubically regularized Newton method of Polyak and Nesterov (2006) and of regularized Newton method of Mishchenko (2021) and Doikov and Nesterov (2021). b) we prove local quadratic rate, which matches the hest-known local rate of second-order methods, and c) our stepsize formula is simple, explicit, and does not require solving any subproblem. Our convergence proofs hold under affine-invariance assumptions closely related to the notion of ceff-concordance. Finally, our method has competitive performance when compared to existing baselines, which share the same fast global convergence guarantees.
Introduction
Second-order optimization methods are the backbone of much of industrial and scientific computing. With origins that can tracked back several centuries the pioneering works of Newton [Newton) 1687]. Raphson [Raphson] [697] and Simpson [Simpson] 1740]. they were extensively studied, generalized, modified, and improved the last century [antorovich 1948 Moré 1978, Griewank]
1981a]. For review of the historical development of the classical Newton- Newton-Raphson method, we refer the reader to the work of Ymma [995].. The number of extensions and applications second-order optimization methods is enormous; for example, the survey of Conn et al. 20000 trust-region and quasi-Newton methods cited over a thousand papers.
1.1 Second-order methods and modern machine learning
Despite the rich history of the field, research second-order methods has been flourishing up this day. Some of the most recent development in the area was motivated by the needs of modern machine learning. Data-oriented machine learning depends large datasets (both in number of features and number of datapoints), which are often stored in distributee/deecentalied fashion. Consequently, there is need for scalable algorithms.
Equal contributions
'Mohamed bin Zayed University Artificial Intelligence, United Arab Emirates
$ "King Abdullah University of Science and Technology, Thuwal, Saudi Arabia
8 Moscoo Institute Physics and Technology, Russia
ISP RAS Research Center for Trusted Artificial Intelligence, Russia
National Research University Higher School of Economics, Russia
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

To tackle large number of features, Qu et al. [2016], Gower et al. (2019). Doikov and Richtárik (2018)
and Hanzely et al. (2020) proposed variants of Newton method operating in random low-dimensional
subspaces. On the other hand, Pillanci and Wainwright 2017]. Xu et al. [0200 and Kovalev et al.
[2019] developed subsampled Newton methods for solving empirical risk minimization (ERM)
problems with large training datasets. Additionally, [ordes et al. [2009] Mokhtari and Ribeiro 20133] Gower et al. [2016). Byrd et al. (2016) and Kovalev et al. (020) proposed stochastic variants of quasi-Newton methods. To tackle non-centralized nature of datasets, Shamir al. (2014), Reddi ct al. [2016], Wang et al. [2018] and [rane and Roosta [219 considered distributed variants of Newton method, with improvements under various data/function similarity assumptions. [slamov
ct al. 202T], Safaryan et al. 2022).. Qian et al. [022]. Islamov et al. [0222] and Agafonov et al. [022 developed communication -efficienntte distributed variants of Newton method using the idea of communication compression and error compensation, without the need for any similarity assumptions.
We highlight two main research directions throughout of history of second-order methods: globally convergent methods under additional second-order smoothness ( (Nesterov and Polyak [2006] and
local methods for self-conncrdant problems 12 Nesterov and Nemirovski|I198
Former approach
lead to various improvements such as acceleration Nesterov [2008). Monteiro and Svaiter (2013),
usage of inexact information Ghadimi et al. [2017]
Agafonov et al. 2020). generalization to tensor
methods and their acceleration Nesterov| [202 la
Gasnikov et al. [209 Kovalev and Gasnikov
2022). , superfast recond-order methods under higher smoothness Nesterov [202Ic Kamzolov and
Gasnikov [020]. Latter approach was a breakthrough in 1990s, it lead to interior- point methods.
Summary of the results can be found in books Nesterov and Nemirovski [994]. Nesterov 2018
This direction is still popular up to this day |Durrccenssyy and Nesterov [0188. Hildebrand 2020
Doikov and Nesterov
(2022b] Nesterov 2022
As easy-to-scale alternative to second-order methods, first-order algorithms attracted a lot of attention.
Many of their aspects have been explored, including strong results in variance reduction (Roux et al.
| Gower et al. [2020), Johnson and Zhang [2013), Nguyen et al. [202T] 2017)) ). preconditioning
Jahani et al.] [022] acceleration (Nesterov] [2013] 3| Aspremont et al. [202]] distributeddfeddratee
computation (Konečny et al. [2016], et al. [2022). Berahas et al. [2016]. Takáč et al. (2013).
Richtárik and Takáe [016). Kairouz al. [2021], and decentralized computation [Koloskoval
ct 2020 (aaiev et al. [222]] Borodich et al. [222]. However, the convergence of first-order
methods always depends the conditioning of the underlying problem. Improving conditioning
is fundamentally impossible without using higher-order information. Removing this conditioning dependence is possible by incorporating information about the Hessian. This results in second-order methods. Their most compelling advantage is that they can converge extremely quickly, usually in just few iterations.
1.2 Newton method: benefits and limitations
One of the most famous algorithms in optimization, Newton method, takes iterates of form
I++1 = xx - [(x)( V fzz)).
(1)
Its iterates satisfy the recursion ff S [ (for constant e >> O), which means that Newton method converges locally quadratically. However, convergence of Newton method is limited to only to the neighborhood of the solution. It is well-known that when initialized far from optimum, Newton can diverge, both in theory and practice (Jarre and Toint [2016), Mascarenhas (2007). We can explain intuition why this happens. Update rule of Newton (I) was chosen to minimize right hand side of Taylor approximation
f(y) = (v: def f(x) (Vf(=).vv))))))))))>)))))) 2) f(=(())))) x). 9 x).
1
(2)
The main problem is that Taylor approximation is not upper bound, and therefore, global convergence of Newton method is not guaranteed.
1.3 Towards a fast globally convergent Newton method
Even though second-order algorithms with superlinear local convergence rates are very common, global convergence guarantees of any form are surprisingly rare. Many papers proposed globalization strategies, essentially all of them require some combination of the following: line-search, trust regions, damping/truncation regularization. Some popular globalization strategies show non-increase

---

of functional value during the training. However, this turned out to be insufficient for convergence to the optimum. Parre and Toint (2016). Mascarenhas [2007] designed simple functions (strictly convex with compact level sets) so that Newton method with Armijo stepsizes does not converge to the optimum. To this day, virtually all known global convergence guarantees are for regularized Newton methods with, which can be written
28+1 = 24 - a& ((x)) + Ax1) Vf(=x),
where A 2 Parameter 0 is also known as Levenberg- -areruard regularization [Moré] 1978 which was first introduced for nonlinear least-squares objective. For simplicity, we disregard differences the objectives for the literature comparison. Motivation behind update (3) to
replace Taylor approximation in (2) by an upper bound. The first method with proven global
convergence rate O 2A= is Cubic Newton method [Nesterov and Polyak 2006) for function / with Lipschitz-continuuu Hessian,
VV v < L2]læ v/12.
(4)
Under this condition, one can upper bound of Taylor approximation eq. as f(v S Ø (w: + 2 ly - 2=122-
(5)
Next iterate of Cubic Newton can be written minimizer of right hand side of 5
Fk+1 argmin {Qr(v) + L/ [ly x 11
(6)
yEB
For our sewly-proposed algorithm AICN (Algorithm
I). we are using almost identical step
Tk+1 = argmin {Qr zx) Lagu l1
x& 11
(7)
y
The difference between the update of Cubic Newton and AICN is that we measure the cubic regularization term in the local Hessian norms. This seemingly negligible perturbation turned out to be of great significance for two reasons a) model in (7) is affine-invariant, b) surprisingly, the next iterate of (7) lies in the direction of Newton method step and obtainable without regularizer A (AICN just needs to set stepsize (x.). We elaborate both of these points later in the paper.
Cubic Newton method (6) can equivalently expressed in form B3 with as = and X L2lla; - Zạ+1 2|2. However, since such Å depends on 24++1. resulting algorithm requires additional subroutine for solving its subproblem each iteration. Next work showing convergence rate of regularized Newton method [Polyak] 2009] avoided implicit steps by choosing A f(xx)) |l,
However, this came with trade-off for slower convergence rate, O (k-1/4). Finally, Mishchenko 44/2021] (see also the work of Doikov and Nesterov (1/2001]) improved upon both of these works V f(xx) )
by using explicit regularization ag = 1, 2 & / L2
2. and proving global rate O (k 2).
2
Contributions
2.1 AICN as damped Newton method
In this work, we investigate global convergence for most basic globalization strategy, stepsized Newton method without any regularizer (Ax = 0). This algorithm is also referred as damped (or truncated) Newton method; can be written
Ik- = Ik as V'xl
Resulting algorithm investigated in detail an interior-point method. shows quadratic local convergence for stepsizes an
Nesterov 2018
def
def
1+G.
where
10
T+
I+C
Where EE d-dimensional Euclidean space, defined in Scction FFuccion f is bem---emi-stronge self-concordant (Definition bound Les: Lees Tzemi-
2.3 Instead of Lsemi, we will use its upper
9 Function ff is Iug-self-comcordam (Definition
Dual norm | [xx(x)) (Vf(xx) v² mA V (xx)) is defined in Section 2.3
3

---

Table 1: A summary of regularized Newton methods with global convergence guarantees. We consider algorithms with updates of form Tk+1 = Ik - a [V2 + ) fzz)) For simplicity of comparison, disregard differences in objectives and assumptions. We assume L2 smsothetsssss of Hessian, Lismi -eei---om self-concordance, convexity (Definition 3), p-strong convexity locally and bounded level sets. For regularization parameter holds A and stepsize satisfy 0 ag S 1. We highlight the best know rates blue.
Affime !! invariant? (alg,, ass., rate) search?
Avoids line
Global convergence convergence rate
Local (1)
Regularizer A
Stepsize
Algorithu
Reference
exponent
Newton
0
U.K.M
2
Kantorovich
1948
Newton
(115))
2
Nesterov Nemirovski
1994
Damped Newton
TFO
0
(+-+)
2
Nosterow 2018
1..1.28) 2828
Damped Nowton C
0
14014c]
1+G,
(1.50)
X
2
Nesterov 2018
(5.2.1)cr
Nesterow and Folvak
2006
Cubic Newton
L2l|
mxll2
(X.X.x)
Griowank
Duikov and Netterov 2022a
Locally Reg. Newton
(X.X.X)
X
2
Polyak
2009
Globally Reg. Newton
vf(x))ll2
(6.X,))
0 (1-+)
2
Polyak
2009
Globally Reg. Newton // (f(r)))
(X.X,X)
0 (k-2)
Daikoy and Nesterix
Mishehenko
4/2021
2201
ATC Newton (Algorithm D
O (I: 2)
01 In triplets, we report whether algorithm, used issumptions, convergencce rate are afline-inarriat, respectively.
(2) For a Iyapunov function q and constant c, we report exponent 8 of (m)44)) S c (xx)).
0) has Li Lipihisciitz continuous gradient.
(4) For simplicity, denote
L (mw))l,, and Lsaui (f(x))) (for Leani).
G1 def Lsc f
Our algorithm AICN is also damped Newton method with stepsize
Lyemil f Mentioned stepsizes a1 02 & share two characteristics. Firstly, all of them depends on gradient computed in the dual norm and scaled by smoothness constant (G1 or G). Secondly, all of these stepsizes converge to from below (for (an, (2,aa) a holds < à S 1 and limg- = 1). Our algorithm uses stepsize bigger by orders of magnitude (see Figure 3 in Appendix A detailed comparison). The main difference between already established stepsizes (11, 02 and our stepsize a are resulting global convergence rates. While stepsize a2 does not lead to global convergence rate, and a₁ leads rate O (k-1/2). our stepsize a leads to a significantly faster, O (k=2) rate. Our rate matches best known global rates for regularized Newton methods. We manage achieve these results by carefully choosing assumptions. While rates for aı and 0g follows from standard self-concordancee, our assumptions are a consequence of a slightly stronger version of self-concordance. We will discuss this difference in detail later.
a 1+/1+2G where 6
def
We summarize important properties of regularized Newton methods with fast global convergence guarantees and damped Newton methods in Table I
2.2 Summary of contributions
To summarize novelty in our work, we present novel algorithm AICN. Our algorithm can be interpreted in two viewpoints a) as a regularized Newton method (version of Cubic Newton method), b) damped Newton method. AICN enjoys the best properties of these two worlds:
Fast global convergence: AICN converges globally with rate (k 2) (Theorem which matches state-of-the-an global rate for all regularized Newton methods. Furthermore, it the first such rate for Damped Newton method.
Fast local convergence: In addition to the fast global rate, AICN decreases gradient norms locally in quadratic rate (Theorem 3 This result matches the best-known rates for both regularized Newton algorithms and damped Newton algorithms.

---

Previous works on Newton regularizations can be viewed as popular global-convergence fix for the Newton method. We propose an even simpler fix in the form of stepsize schedule (Section Bp.
Simplicity:
Implementability: Step of AICN depends smoothness constant Ssomi (Definition 3 Given this constant, next iterate AICN can be computed directly.
This is improvement over Cubic Newton [Nesterov and Polyak 2006], which for given constant Lg needs to run line-search subroutine each iteration to solve its subproblem
Avoiding latter subroutine yields theoretical improvements. If we compute matrix inverses naively, iteration cost of AICN is (d2) (where d is dimension of the problem). which is improvement over (d log = iteration cost of Cubic Newton [Nesterov and Polyak 2006].
Improvement:
Practical performance: We show that in practice, AICN outperforms all algorithms sharing same convergence guarantees: Cubic Newton [Nesterov and Polyak (006) and Globally Regularized Newton [Mishchenko] 4/202] Doikov and Nesterov [1/2021] and fixed stepsize Damped Newton method (Section 5))
We analyze AICN under more geometrically natural assumptions. Instead of smoothness, we use version of self-concordance (Section 3.1). which is invariant affine basis. AICN preserves affine-invariance obtained from assumptions throughout the convergence. In contrast, Cubie Newton uses base-dependen l2 norm and hence depends on choice of basis. This represents an extra layer of complexity.
Geometric properties:
transformations and hence also to a choice
Alternative analysis: We also provide alternative analysis under weaker assumptions (Appendix C).
The of the paper is structured follows. In Section 2.3
introduce our notation. In Section 3
we discuss algorithm AICN, affine-invariant properties and self-concordaanc, In Sections [4. and 4.2
show global and local convergence guarantees, respectively. In Section we present an empirical comparison of AICN with other algorithms sharing fast global convergence.
2.3 Minimization problem & notation
In the paper, consider d-dimensional Euclidean space E. Its dual space, E", is composed of all linear functionals on E. For functional E", we denote by (g,x) z) its value at x E E.
We consider the following convex optimization problem:
mün ((x), FEB
(8)
where f(x) E C2 is a convex function with continuous first and second derivatives and positive definite Hessian. We assume that the problem has unique minimizer v, arggmin (x: Note, that
.EB
E (zf(x) E E*. Now, we introduce different norms for spaces E and E* Denote h E E,g E" For self-adjoint positive-definite operator H E + E", we can endow these spaces with conjugate Euclidean norms:
|
del H
(Hr 1/2 E EE,
def gg
9) 1/2
9 E E
For identity H I, we get classical Eucledian norm || (x, 1/2. For local Hessian norm H f2f(() we use shortened notation
1/2
||], (z))()), hEB E,
(g. V2 f(x)
9 .gED E..
(9)
Operator norm is defined by
def sup
[H ||a||
(10)
op
for H E. E and fixed we consider specific case +- Rd. then H a symmetric positive definite matrix.
5

---

New Algorithm:
Affine-Invariant Cubic Newton
Finally, we are ready to present algorithm AICN. It is damped Newton method with updates
Ik-1 1 Ik Og vZ (V())))((()),,
(11)
with stepsize
1+ 1+ 1+22 V
ag
Les V
as summarized in Algorithm Stepsize satisfy a (from AG inequality, (45) Also lim 1, hence (II) converges to Newton method. Next, we are going to discuss geometric properties our algorithm.
Algorithm AICN: Affine-Invarian Cubic Newton
1: Requires: Initial point zo E, constant Less s.t. Less 2 Lygemi 0
2: for k 0, 21, do
3: -1+ /1+bball (((L)
Loal ((xx)) 1
4: Tk+1 Ik ar
2 [xx)]
Vf(x))
Note that rk+1
Sy (Ik).
5: end for
3.1 Geometric properties: affine invariance
One of the main geometric properties of the Newton method is affine invariance, invariance affine transformations of variables. Let A : E E be non-degenerate linear transformation. Consider function (ty) f(Ay). By affine transformation, we denote fx) K(y) f(Ay), + A-11
Significance of norms: Note that local Hessian norm [[]]) is affine-invariant because
|| | = (V)))) = VA ((ay) = (z)),, h) = ||!l
where h = Az. On the other hand, induced norm |||||r is not affine-invrrint because || (2, (A-1h, 1h) |A A11
With respect geometry, the most natural norm is local Hessian norm, [[Alvy/()) From affine invariance follows that for this norm, the level sets {v E T Ily 11 S c} are balls centered around (all directions have the same scaling). In comparison, scaling of the la norm is dependent on cigenvalues of the Hessian. In terms of convergence, one direction in l2 can significantly dominate others and slow down algorithm.
Significance for algorithms: Algorithms that are not affine-invariant can suffer from chosen coordinate system. This is the case for Cubie Newton, its model (4) is bound base-dependent l2 norm. Same is true for any other method regularized with an induced norm ||A||i. On the other hand, (damped) Newton methods have affine-invariant models, and hence algorithms independent of the chosen coordinate system. We prove this claim in following lemma (note: = I and from [I] affine-invariant).
Lemma 1 (Lemma 5.1.1 Nesterov (0188). Let the sequence {#x} be generated by a damped Newton method with affme-invariant stepsize ag applied to the function f: Ex+1 = Ik
ag 2 f(xx) f((z)) For function Φ(y), damped Newton method generates {yk}: yk+1
y4 os [v))) Veb(un) with yo = A- Then yk
A A-lrk-
3.2 Significance in assumptions: self-concordance
We showed that damped Newton methods preserve affin-invariance through iterations. Hence more fitting to analyze them under affine-invariant assumptions. Affine-invariant version of smoothness, seff-concordance, was introduced in Nesterov and Nemirovski (194)..

---

Definition Convex function f E C called self-concordamt if
|D*
1 Vx, h E E,
(12)
where for any integer p 2 1, by D2 [M d D (x)),,, [h,....,i hJ we denote the p-th order directional derivative of at x: E E along direction h E E.
"For example, D f(x))( (V)(),, h) and D2 f(x))(] (x)),)).
Both sides of inequality are affine-invariant This assumption corresponds to a big class of optimization methods called interior-poin methods. Self-concordance implies uniqueness of the solution, as stated following proposition.
Proposition (Theorem 5.1.16, Nesterov 2018), ). Let a self-concordant function f bounded below. Then it altains its minimum at single point.
Rodomanoy and Nesterov 2021 introduced stronger version of self-concordance assumption.
Definition 2. Convex function f E C² called strongly self-concordant if
(²) V f(x) 3 Lar ly V[ Vy, x. 2, E.
(13)
For our analysis, we introduce definition for functions between self-concordant and strongly self-concordant.
Definition 3. Convex finction f E C² called semi-strongly self-concordant if
((') 22 f(>))l. S Tcwmmllly x x1| Vy, x
E.
(14)
Note that all the Definitions are affine-invariant, their respective classes satisfy
strong self-concordance C semi-strong self-concordancc self-concorlance.
Also, for fixed strongly self-concordant function f and smallest such Lise, Lsemis List holds Los S
Limmi < Litr-
These notions are related to the convexity and smoothness; strong concordance follows from function Ly-Lipschitz continuous Hessian and strong convexity.
Proposition (Example 4.1 from RRoomaanov and Nesterov 2021 Let H E E" be self-adjoint positive definite operator. Suppose there exist μ > 0 and L2 2 O such that the function f
u-strongly convex and its Hessian Lo-Lipschitz continuous (4) with respect to the norm || ||H..
Then strongly self-concorlant with constant Logr 372--
3.3 From assumptions to algorithm
From semi-strong self- ceff-concordance can get second-orde bounds on the function and model.
Lemma 2. If f is semi-strongly self-concordant, then
If(y) Q x)1 < Lusi lyy x 11 Vx,
E.
(15)
Consequently, we have upper bound for function value in form
f(y) S Qr((:)))= + Lows Iyy x
(16)
One can show that (66) is not valid for just self-concordant functions. For example, there no such upper bound for lzg(z). Hence, the semi-strongly self-concordance is significant as assumption.
We can define iterates of optimization algorithm be minimizers of the right hand side of (16).

---

St.Lmi())
def x
argmin {f(x) + (Vf(2), + (V + a [111))
(17)
MEZ
Fk-1 = = S
(18)
easy to solve, To get an explicit solution, we compute its gradient w.r.t. h. For solution h², it should be equal to zero,
for an estimate constant Teu 2 Tsemi- turns out that subproblem 17
Vf(²) f + V f(x)h"
(19)
h" = [V-VV
( 1))
(20)
We get that step 18 has the same direction Newton method and is scaled by as
hes | + 1) Now, we substitute h from 20 to 19
V f())) - V(())a L (V [(x) V(( 1/2
Vs(r)a = 0,
Vx(x) az 1سE V [(}()) -0
(21)
We solve the quadratic equation 21 for ag, and obtain explicit formula for stepsizes of AICN, as (11. We formalize this connection in theorem, for further explanation see proof in Appendix B
Theorem 1. For Less 2 Lisemii update of AICN
-1+ 1++V++10 [1
14
Tk+1 Tk ak (Z
where
ar
Tk+1 = Sy.Lo (2x)) is minimizer of upper bound 17
4 Convergence Results
4.1
Global convergence
Next, we focus on global convergence guarantees. We will utilize the following assumption:
Assumption (Bounded level sets). The objective function f has a unique minimizer I.. Also, def {x E E: f(x) S f(xo)} is bounded by a constant D2
the diameter of the level set C(x))
a
xE((zo) | xxl12 I D2 +00.
We state in la for easier verification. In proofs, its variant 1) in Hessian norms,
23
Our analysis proceeds as follows. Firstly, we show that one step of the algorithm decreases function value, and secondly, we use the technique from Ghadimi et al.) 2017] show that multiple steps lead to O k (k-2) global convergence. We start with following lemma.
Lemma 3 (One step globally). Let function be Shem--emmi-stron Sesitive-effuitt Hessian and L,st 2 Lswni- Then for any x E E, we have
self-concordant, convex with
S1.Lm( min {f(v) WEE
Lyx lly =11))
3
(22)
This lemma implies that step I7 decreases function value (take y & x). Using notation of Assumption
3ik L(xr) for any k 0. Also, setting y and x. [1) yields
|| -xall (I]:r 1.2.... + Tiesal x. ) We denote those distances D and R.
def max
||ara x.all
and
R
def
(I|= 11.1. + -eeall pr x, [1 ) (23) xEC(xg)
max
EE [E[0:k++1]
They are both affine-invarian and R upper bounds D. While depends only on the level set C(xr)) D can be used to obtain more tight inequalities. We avoid using common distance D2, as la norm would ruin affine-ivvarian properties.

---

Theorem 2. Let [(x) be seemesyemi-ttoonlly self-concorlant convex function with positive-define Hessian, constant Les satisfy Lest 2 Liemi and Assumption 7 holds. Then, after iterations of Algorithm 7
we have the following convergence rate:
f(IR+1) f(xx) S
Lan" 12
O
Luatt K
(24)
Consequently, AICN converges globally with fast rate O 2k- We can now present local analysis.
4.2 Local convergence
For local quadratic convergence are going utilise following lemmas.
Lemma 4. For convex Lxem--Semi-stronnlly self-concordant function f for any 0 < << in the neighborhood of solution
3k fx [[f(()) (2c+1)2-1) holds V 310
(25)
2L,
Lemma 4 formalizes that inverse hessians of ceff-concordant function around the solution is non non-degeeerate. With this result, we can show one-step gradient norm decrease.
Lemma 5 (One step decrease locally). Let function f be semmi--emm-ttoongl selffconcordant and Len 2 Lsemi If æ such that (25) holds, then for next iterate Tx+1 of AICN holds
[V( S Lena V f(xx))) < Leal f(=+)))
(26)
Using Lemma we shift the gradient bound respective norms,
[V $ Lonak [V Loaa V
(27)
[f((+t))ll & [Vf(())) for [f I (2-c)--1
Gradient norm decreases
2h
As { x: [V S min
result,
neighbourhood
of the local convergence is
(2-e)²
(2c+1)-
Maximizing by c, we get c 1/3 and }
21s
2hea
neighrbourhood f2 [>)((> S 9lag
One step of AICN decreases gradient norm quadratically, multiple steps leads to following decrease.
Theorem 3 (Local convergence rate). Let function f be Lemmi-semi-steer self-concordant, Lest 2 Lyemi and starting point To be in the neighborhood of the solution such that || [[V) S 8. For 2 O, we have quadratic decrease of the gradient norms, VLes
(28)
Numerical Experiments
In this section, we evaluate proposed AICN (Algorithm 1 algorithm on the logistic regression task and second-order lower bound function. We compare it with regularized Newton methods sharing fast global convergence guarantees: Cubic Newton method [Nesterov and Polyak| 2006), and Globally Regularized Newton method ((Mishchenko) 4/202 Doikov and Nesterov 12/2021
with Lz-constant. Because AICN has a form of a damped Newton method, we also compare it with Damped Newton with fixed (tuned) stepsize or
We report decrease in function value f(xx),
function value suboptimality f(xx) - f(x.) with respect to iteration and time. The methods are implemented as Py Torch optimizers. The code is available at pttptts:/ wtw.ttub..com//PP1..
5.1 Logistic regression
For first part, we solve the following empirical risk minimization problem:
min #
f(x))
1 Σ log (1 e D.u || m
1=1

---

Eargii Neach
Eareid tevii
327
13
Figure 1: Comparison of regularized Newton methods and Damped Newton method for logistic regression task on a9a dataset.
Seatin
Caisalty
Sturia
CAL
4000 Mag. Sevion
Figure 2: Comparison regularized Newton methods and Damped Newton method for second-order lower bound function.
where {(a,, b,) are given data samples described by features a, and class 6, E {11,
In Figure [ we consider task of classification images on dataset a9a [Chang and Lin 2011 Number of features for every data sample d = 123, m 20000. We take staring point 10-3 Our choice is differ from zo 0 (equal to all zeroes)
def 10f1, 1]T and to show globalisation properties of methods (zg = is very close to the solution, as Newton method converges in 4 iterations). Parameters of all methods are fine-tuned, (of AICN, Cubic Newton, Damped Newton, resp.) to largest values having monotone decrease in reported metrics. Fine-tuned values Lest 0.97 L2 0.000215, demonstrates that AICN converges slightly faster than Cubic Newton method by iteration, notably faster than Globally Regularized Newton and significantly faster than Damped Newton. AICN outperforms every method by time.
To
choose parameters Lesa L2,
0.285. Figure [
5.2 Second-order lower bound function
For second part we solve the following minimization problem:
-1
0
d
min wERd
f(x)
1/4
Σ
|x
- I1 11121
where
A
=
0
1
-1
0
0
0
0
This function is lower bound for class of functions with Lipschitz continuous Hessian with additional regularization [Nesterov and Polyak 2006 Nesterov| 2021a] In Figure 2 we take = 20, fine tuned to largest values having monotone decrease in reported metrics: Lest 662 L2 = 0.662, a = 0.0172. Figure 2 demonstrates that AICN converges slightly slower than Cubic Newton method, slightly faster than Globally Regularized Newton, and significantly faster than Damped Newton. ain outperforms every method by time. More experiments presented in Appendix A Note, that the iteration of the Cubic Newton method needs an additional line-search, so one iteration of Cubie Newton is computationally harder than one iteration of AICN. More experiments are presented in Appendix A
Jo 0 (equal all zeroes). Parameters Lest L2,
Acknowledgement
The work of D. Pasechnyuk and A. Gasnikov was supported by grant for research centers in the field of artificial intelligence, provided by Analytical Center the Government of the RF in accordance with the subsidy agreement (agreement identifier (00000730321PSQ0000 and the agreement with the Ivannikov Institute for System Programming of the RAS dated November 2, 2021 No. 00-2021-00144
10

---

References
Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky, and Alexander Gasnikov. Inexact tensor methods and their application to stochastic convex optimization. arXiv preprint arXiv:2012.15636. 2020.
Artem Agafonov, Dmitry Kamzolov, Rachael Tappenden, Alexander Gasnikov, and Martin Takáč. Flecs: A federated learning second-order framework via compression and sketching, arXiv preprint arXiv:2206. 220000200002009, 2022.
Albert Berahas, Jorge Nocedal, and Martin Takáč. A multi-batch L-BFGS method for machine learning. In The Thirtieth Annual Conference Neural Information Processing Systems (NIPS), 2016.
Antoine Bordes, Léon Bottou, and Patrick Gallinari. SGD-QN: careful quasi-Newttn stochastic gradient descent. Journal of Machine Learning Research, 10: 10:1737-1754, 2009.
Ekaterina Borodich, Aleksandr Beznosikov, Abdurakhmon Sadiev, Vadim Sushko, Nikolay Savelyev, Martin Takáč, and Alexander Gasnikov. Decentralized personalized federated min-max problems. arXiv preprint arXiv:2106.072800 2021.
Richard H Byrd, Jorge Nocedal, and Yoram Singer. A stochastic quasi-Newton method for large-scale optimization. SIAM Journal on Optimization, 26(2):1008-1031, 2016.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
Yicheng Chen, Rick S Blum, Martin Takáč, and Brian M Sadler. Distributed learning with sparsified gradient differences. IEEE Journal of Selected Topics in Signal Processing, 2022.
Andrew R Conn, Nicholas IM Gould, and Philippe L. Toint. Trust Region Methods. SIAM, 2000.
Rixon Crane and Fred Roosta. DINGO:
Distributed Newton-type method for gradient-norm optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems (NewrIPS), volume 32, pages 9498-9508 Curran Associates, Inc., 2019. URL 6be 370e311131
htcpppprr/2199
Alexandre d' A'Asprmmont Damien Scieur, and Adrien Taylor. Acceleration methods. January 2021.
Li Deng. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Magazine, 29(6): 1412 2012.
Nikita Doikov and Yurii Nesterov. Gradient regularization Newton method with Bregman distances. arXiv preprint arXiv:21 12/2021.
Nikita Doikov and Yurii Nesterov. Local convergence of tensor methods. Mathematical Programming, -93:6, 2022a.
Nikita Doikov and Yurii Nesterov. Affine-invariant contracting-poinn methods for convex optimization. Mathematical Programming, pages 1-23, 2022b.
Nikita Doikov and Peter Richtárik. Randomized block cubic Newton method. In Jennifer Dy and Andreas Krause, editors, The 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 1290 1298, Stockholmsmässan Stockholm Sweden, 10-15 Jul 2018. PMLR. URL /tRR///cp///poooe.ggg...... press/ /880doikood
www.ooooo.......o... 1aa.vl8a... html
Pavel Dvurechensky and Yurii Nesterov. Global performance guarantees of second-order methods for unconstrained convex minimization. Technical report, CORE, 2018.
Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov, Evgeniya Vorontsova, Daniil Selikhanovych, César A Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, et Near optimal methods for minimizing convex functions with lipschitz p-th derivatives. In Conference Learning Theory, pages 1392-1393. PMLR, 2019.

---

Saced Ghadimi, Han Liu, and Tong Zhang. Sedond-order methods with cubic regularization under inexact information. arXiv preprint arXiv:1710.05782, 2017.
Robert M Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for
Machine Learning. Proceedings of the IEEE, 108(11):19881193) 2020.
Robert Ma Gower, Dmitry Kovalev, Felix Lieder, and Peter Richtárik. RSN: Randomized Subspace Newton. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox,
and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 616-225, Curran Associates, Inc., 2019. URL http:::/papprs.niii miw....nip.... cc cttpcpcccepp////// 8351 ran- rand zed- subspace
newton
Robert Mansel Gower, Donald Goldfarb, and Peter Richtárik. Stochastic block BFGS: squeezing more curvature out of data. In 33rd International Conference on Machine Learning, pages 1869-1878 2016.
Andreas Griewank. The modification Newton's 's method for unconstrained optimization by bounding cubic terms. Technical report, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, 1981a. Technical Report NA/12.
Andreas Griewank. The modification of Newton's 's method for unconstrained optimizatinn by bounding cubic terms. Technical report, Technical report NA/12, 1981b.
Filip Hanzely, Nikita Doikov, Peter Richtárik, and Yurii Nesterov. Stochastic subspace cubic Newton method. In 37th International Conference on Machine Learning (ICML), 2020.
Roland Hildebrand. Optimal step length for the Newton method near the minimum of self-concordant function. arXiv preprint arXiv:2003.0 086500, 2020.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. In International Conference on Machine Learning (ICML), 2021.
Rustem Islamov, Xun Qian, Slavomír Hanzely, Mher Safaryan, and Peter Richtárik. Distributed Newton-type methods with communication compression and bernoulli aggregation. arXiv preprint MrXiv:2206.03588 2022.
Majid Jahani, Sergey Rusakov, Zheng Shi, Peter Richtárik, Michael W Mahoney, and Martin Takáč. Doubly adaptive scaled algorithm for machine learning using second-order information. In Tenth International Conference on Learning Representations (ICLR 2022), 2022.
Florian Jarre and Philippe L Toint. Simple examples for the failure of Newton's 's method with line search for strictly convex minimization. Mathematical Programming, 158(1))23-34) 2016.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in Federated Learning. Foundations and Trends@ in Machine Learning, 14(1-2)) 14(1-2):1-210, 2021.
Dmitry Kamzolov and Alexander Gasnikov. Near-optimal hyperfast second-order method for convex optimization and its sliding, arXiv preprint arXiv:2002.09050 2020.
Leonid Vital'evich Kantorovich. Functional analysis and applied mathematics. Matematicheskiik Nauk, 366)889-185, 1948.
Uspekhi
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5395 PMLR, 2020.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated Learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05499. 2016.
12

---

Dmitry Kovalev and Alexander Gasnikov. The first optimal acceleration of high-order methods in smooth convex optimization. arXiv preprint arXiv:2205.096// 2022.
Dmitry Kovalev, Konstanting Mishchenko, and Peter Richtárik. Stochastic Newton and cubic Newton methods with simple local Iinear-quadratic rates. In NeurlPS Beyond First Order Methods Workshop, 2019. 2019.
Dmitry Kovalev, Robert M. Gower, Peter Richtárik, and Alexander Rogozin. Fast linear convergence of randomized BFGS. arXiv preprint urxi::2002./137, 2020.
Walter F Mascarenhas. On the divergence of line search methods. Computational & Applied Mathematics, 26(1):129-169) 2007.
Konstantin Mishchenko. Regularized Newton method with global ((1/k²) convergence. arXiv preprint arXiv 2112.02089, 4/2021.
Aryan Mokhtari and Alejandro Ribeiro. Global convergence of online limited memory BFGS. Journal of Muchine Learning Research, 16:3151-3181, 2015. URL httt:://axxi...rrrt/t
1409
2045
Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 239))1092-1125, 2013.
Jorge J Moré. The
algorithm: implementation and theory. In Numerical analysis, pages 105-116. Springer, 1978.
Yurii Nesterov. Accelerating the cubic regularization of Newton's method on convex problems. Mathematical Programming. 11((1):19-1811, 2008
Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87, Springer, 2013.
Yurii Nesterov. Lectures on Convex Optimization, volume 137 of Springer Optimization and Its Applications. Springer, 2018.
Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical Programmingg 186(1):157-183, 2021a.
Yurii Nesterov. Inexact high-order proximal-point methods with auxiliary search procedure. SIAM Journal on Optimization, 31(4):2807-2828, 2021b.
Yurii Nesterov. Superfast second-order methods for unconstrained convex optimization. Journal of Optimization Theory and Applications, 191(1):1-30, 2021c.
Yurii Nesterov. Set-limited functions and polynomial-ting interior-point methods. Technical report, 2022.
Yurii Nesterov and Arkadi Nemirovski. Self-concordant functions and polynomial time methods in convex programming, ussr acad. Sci., Central & Mathematical Institute, Moscow, 1989.
Yurii Nesterov and Arkadi Nemirovski. Interior-point polynomial SIAM, 1994.
polyiooo algorithms in Convex programming.
Yurii Nesterov and Boris T Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108 2006.
Isaac Newton. Philosophiae naturalis principia mathematica. Jussu Societatis Regiae Typis Josephi Streater, 1687.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613-2621 PMLR, 2017.
13

---

Lam M Nguyen, Katya Scheinberg, and Martin Takáč. Inexact SARAH algorithm for stochastic
optimization. Optimization Methods and Software, 36(1):237-258, 2021.
Mert Pilanci and Martin Wainwright. Newton sketch: A linear-time optimization algorithm with
linear-quadratic convergence. SIAM Journal on Optimization, 27(1):205- 245, 2017. URLhttps
//axxiv.orr///f//5555. 02250. pdf
Roman A Polyak. Regularized Newton method for unconstrained Convex optimization. Mathematical Programming, 120(1):125-14) 145, 2009.
Xun Qian, Rustem Islamov, Mher Safaryan, and Peter Richtárik. Basis matters: better communication-effcceett second order methods for federated learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Zheng Qu, Peter Richtárik, Martin Takáč, and Olivier Fercoq. SDNA: for empirical risk minimization. The 33rd International Conference on Machine Learning (ICML), pages 1823-1832, 2016.
Stochastic dual Newton ascent
Joseph Raphson. Analysis Aequationum Universalis Seu Ad Aequationes Algebraicas Resolvendas Methodus Generalis & Expedita, Ex Nova Infinitarum Serierum Methodo, Deducta Ac Demonstrata. Th. Braddyll, 1697.
Sashank J. Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczos, and Alex Smola. AIDE: Fast and communication efficient distributed optimization. arXiv:1608.0668 06879, 2016.
Peter Richtárik and Martin Takáč. Distributed coordinate descent method for learning with big data. Journal of Machine Learning Research, 17:1-25, 2016.
Anton Rodomanov and Yurii Nesterov. Greedy quasi-Newton methods with explicit superlinear convergence. SIAM Journal on Optimization, 31(1):785-811, 2021.
Nicolas Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. Advances in Neural Information Processing Systems, 25, 2012.
Abdurakhmon Sadiev, Ekaterina Borodich, Aleksandr Beznosikov, Darina Dvinskikh, Saveliy Chezhegov, Rachael Tappenden, Martin Takáč, and Alexander Gasnikov. Decentralized personalized federated learning: Lower bounds and optimal algorithm for all personalization modes. arXiv preprint arXiv:2107.07190, 2021.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. FedNL:
Making Newton-type methods applicable to federated learning. In Internatioanl Conference on Machine Learning. 2022.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-eficieen distributed optimization using an approximate Newton-type method. In The 31st International Conference Machine Learning (ICML), volume 32, pages 1000-1008, 2014.
Thomas Simpson. Essays on several curious and useful subjects, in speculative and mix't 'd mathematicks. Illustrated by a variety of examples. Printed by H. Woodfall, jun. for J. Nourse, the Lamb without Temple-Bat Bar, 1740.
Martin Takáč, Peter Richtárik, and Nathan Srebro. Distributed mini-batch SDCA. arXiv preprint arXiv: 2015.
Shusen Wang, Farbod Roosta-Khorasee Peng Xu, and Michael W. Mahoney. GIANT: Globally improved approximate Newton method for distributed optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2018
Peng Xu, Fred Roosta, and Michael W Mahoney. Newton-type methods for non-convex optimization under inexact Hessian information. Mathematical Programming, 187(1)35-77, 2020.
Tjalling J Ypma. Historical development of the Newton-Raphson method. SIAM Review, 37(4): 531-551, 1995.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Paper is of theoretical nature.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We highlighted all assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] For source code, supplementary materials.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Sections, 5
(c) Did you report error bars (e.g.. with respect to the random seed after running experiments multiple times)? [N/A] We compare deterministic algorithms.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [N/A] We used 0 GPU hours.
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] We use publicly available datasets.
(c) Did you include any assets either in the supplemental material URL?? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "sduZmsE_HiT", "reviewer": "Reviewer_dYEq", "summary": "The paper provide a Newton Method with simple step size and provide an affine-invariance analysis of it with local and global convergence rates.", "questions": "None.", "limitations": "None.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- The paper is very well-written and easy to follow. \n- The contributions are elegant and significant.\n- There are compelling numerical experiment.\n\nCCL: this is the best paper in my batch of review.\n", "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": "JSYpeNT0il", "reviewer": "Reviewer_xAoF", "summary": "In this submission, the authors proposed a new Newton's method called the Affine-Invariant Cubic Newton algorithm (AIC). This novel algorithm is the Newton's method with explicit new step size leading to the global convergence and local convergence. This AIC method can achieve a global convergence rate of $\\mathcal{O}(1/k^2)$ which matches the state-of-art global convergence rate. On the other hand, this algorithm can also reach a local quadratic convergence rate which is the best-known local rate of second-order methods. One advantage of this algorithm is that the computation of step size is simple and doesn't need to solve the sub-problem. Another advantage is that the convergence results hold under the assumption that the objective function is affine-invariant, which is a good geometric property. The authors also conduct numerical experiments and the empirical results show that the performance of AIC is competitive with other state-of-art algorithms.", "questions": "In the checklist the authors said that they discussed the limitations of this proposed algorithms. Could you please summarize the limitations in one final conclusions section after the numerical experiments section?", "limitations": "The authors didn't include limitations in the paper. They should add one conclusion section summarizing the paper and discussing any potential limitations and future work directions after the numerical experiments section.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper has the following strengths in terms of the originality, significance, quality and clarity:\n\nOriginality and significance: this paper provides the first variant of Newton's method that could achieve state-of-art convergence rates in both terms of the global and local convergence for the objective function satisfying the affine-invariant property. And the computation of the step size is not complicated. This is the main and independent contribution of this paper.\n\nQuality and clarity: the authors provides detailed and clear explanations in both the theoretical analysis section and the numerical experiments section. The theoretical proof in the appendix is correct. The empirical results show that the proposed novel algorithm is competitive against other state-of-art methods. The paper is also organized with clear and clean structure and the language is well-organized so that the readers can easily understand the content of this submission.\n\nHowever, despite the above advantages, the paper has the following weaknesses:\n\nThe main issue is that the parameters in definition 2, 3 and 4 are expressed a bit unclear. Is this $L_f$ the same for all assumptions 2,3,4? Or are they different? Then, the authors should use different notations to express them. Also in the Theorem 2 and 3, the authors should mention the exact parameter $L_f$ for the assumptions of weakly-strongly self-concordance and semi-strongly self-concordance.\n\nAnother issue is that the authors presented the definitions 2, 3, 4 explicitly and showed the relationship of them. Are these assumptions necessary for the theoretical analysis of the AIC algorithm? Can we obtain the similar results with only the assumption of self-concordance? If these global and local convergence rates also hold for the only assumption of standard self-concordance, then there is no need to create these new assumptions and this submission will be much more clear and simple.\n\nAlso, for all these variants of Newton's method, the authors should mention that the computational expense per iteration is $\\mathcal{O}(d^3)$ where $d$ is the dimension of the problem. This is because we need to compute the inverse of the Hessian matrix to obtain the step size at each iteration. And this expense is very high, which is the main limitation of the Newton's method. In term of the computational cost per iteration, the proposed new AIC algorithm is the same as all the previous variants of Newton's method.\n\nThe last minor issue is that in Algorithm 1, what's $L_H$? Is this a typo and it should be $L_f$?", "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": "InzxISnwU7", "reviewer": "Reviewer_42nd", "summary": "It is well known that Newton's method can fail to converge even for smooth, convex functions. This paper proposes a damped Newton's method with a stepsize schedule such that the method achieves $\\mathcal{O}(1/k^2)$ global rate, which matches the convergence rate of Nesterov's cubic regularization method. The main idea is to minimize a cubic upper bound similar to the one used in cubic regularization, but replace the cubic term with a local Hessian norm. \nCompared to previous methods, the proposed algorithm has an explicit formula for the step-size and enjoys fast local and global convergence. ", "questions": "- As the authors claim,  one advantage of AIC Newton is that it is affine-invariant. This is indeed a natural consequence of replacing the $\\ell_2$ norm by the local Hessian norm in the cubic term. But i'm not sure what is the real advantage here in terms of practical performance? What is the actual benefit of the method satisfying self-concordance?\n- In the numerical experiments, the authors say that the parameters $L_f, L_2$ and $\\alpha$ are all fine-tuned. How is this done exactly? In general, how would I pick $L_f$ for AIC Newton?\n- In terms of per-iteration cost, does AIC Newton offer any advantage compared to cubic Newton of Nesterov? There has been many recent work that reduce the cost of the cubic subproblem [1] [2]. In light of these, how does of real running time of AIC newton compare with cubic Newton?\n\n\n[1] Carmon, Y., & Duchi, J. (2019). Gradient descent finds the cubic-regularized nonconvex Newton step. SIAM Journal on Optimization, 29(3), 2146-2178.\n\n[2] Cartis, C., Gould, N. I., & Toint, P. L. (2011). Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Mathematical Programming, 127(2), 245-295.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This article is well-written and offers an overview of potential problems for Newton's method and how these problems were previously addressed. The authors motivate their algorithm, which they call AIC newton, quite naturally and the idea behind the proofs are also nicely communicated. In the end, under certain assumptions, the proposed algorithm is easy to implement and has strong local and global guarantees. However, there are a few issues that prevent me from giving this article a higher score.\n\n 1. The assumptions under which convergence is proved are quite strong. In particular, Theorem 2, which guarantees global convergence, requires that the function is weakly-strongly self-conconrdant and also *convex*. Compare this with cubic newton of Nesterov, which guarantees convergence towards a second-order stationary point for *non-convex* functions at the same rate, only under the assumption of gradient and Hessian lipschitz. The authors does indeed consider a relaxation of the self-concordance assumption, but in the case the convergence rate the prove is slower, and does not match best known results. \n\n2. The author states that one key advantage of the proposed algorithm is that it has an explicit stepsize and does not require line search, like previous methods. It seems to me that this claim is inaccurate, since computing the step-size requires knowledge of the parameter $L\\_f$, which is a constant related to self-concordance. In cubic regularization, for instance, if the Hessian lipschitz constant is also known, then the line search can also be avoided. Therefore, in this regard the proposed method again offers no advantage over cubic newton. \n\n3. In the numerical experiments, it seems to me that cubic Newton often outperforms the AIC newton, unlike what the authors claim in the intro. However the difference is usually minor and i do not consider this an huge issue. \n\nIn the end, I do think the global convergence of Newton's method is important and interesting for the NeurIPS community. The proposed method, AIC newton can potentially be a useful algorithm, but my main issue is that it has restrictive assumptions and no clear advantage over cubic newton. \n\n\n\n ", "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