Second-Order Min-Max Optimization with Lazy Hessians
Authors: Lesi Chen
Chengchang Liu
Jingzhao Zhang
Venue: ICLR 2025 Oral (2025)
Keywords: min-max optimization; second-order methods; computational complexity
Primary area: optimization
TL;DR: We propose novel second-order methods for min-max optimization that are provably better than existing optimal methods

Abstract: This paper studies second-order methods for convex-concave minimax optimization.  
Monteiro & Svaiter (2012)  proposed a method to solve the problem with an optimal iteration complexity of 
$\mathcal{O}(\epsilon^{-3/2})$ to find an $\epsilon$-saddle point.  However, it is unclear whether the
computational complexity, $\mathcal{O}((N+ d^2) d \epsilon^{-2/3})$, can be improved. In the above, we follow  Doikov et al. (2023) and assume the complexity of obtaining a first-order oracle as $N$ and the complexity of obtaining a second-order oracle as $dN$. 
In this paper, we show that the computation cost can be reduced by reusing Hessian across iterations. Our methods take the overall computational complexity of $\tilde{\mathcal{O}}( (N+d^2)(d+ d^{2/3}\epsilon^{-2/3}))$, which improves those of previous methods by a factor of $d^{1/3}$. 
Furthermore, we generalize our method to strongly-convex-strongly-concave minimax problems and establish the complexity of $\tilde{\mathcal{O}}((N+d^2) (d + d^{2/3} \kappa^{2/3}) )$ when the condition number of the problem is $\kappa$, enjoying a similar speedup upon the state-of-the-art method. 
Numerical experiments on both real and synthetic datasets also verify the efficiency of our method.

Published as a conference paper at ICLR 2025
SECOND-ORDER MIN-MAX OPTIMIZATION WITH LAZY HESSIANS
Lesi Chen
Chengehang Liu
IIIS, Tsinghua University & Shanghai Qizhi Institute chen1c23@maill 1s. t.iinguua.....m edu.cn
The Chinese University of Hong Kong 71 i uuchnncchangeggggg gmai com
Jingzhao Zhang!
III,, Tsinghua University & Shanghai Qizhi Institute & Shanghai Al Lab jingzhazz@mall tsinghua. edu. en
ABSTRACT
This paper studies second-order methods for convex-concave minimax optimiza- tion. MMnteiro & Svaiter (2012) proposed method to solve the problem with optimal iteration complexity of ((e-3/2) to find an e-saddle point. However, it is unclear whether the computational complexity, O((N + de))c-223) can be improved. the above, we follow Doikov et al.J (2023) and assume the com- plexity of obtaining first-order oracle as N and the complexity of obtaining second-order oracle as dN. In this paper, we show that the computation cost can be reduced by reusing Hessian across iterations. Our methods take the over- all computational complexity of O((N + )d d (2/3)), which improves generalize those of the previous methods by factor of d'/33 Furthermore, minimax problems and establish the complexity of O( + dd d2/3z2/3)) when the condition number of the problem is enjoying similar speedup upon the fate-of-the-ar method. Nu- merical experiments on both real and synthetic datasets also verify the efficiency of our method.
our method to soweell--ooeeeesonggyyoooom
INTRODUCTION
We consider the following minimax optimization problem:
min max [ax y), æER WER
where we suppose f(x, y) is (strongly-Jconvex in æ and (strongly- )concave in y. This setting covers many useful applications, including functionally constrained optimization (Xu 2020), , game
theory (Von Neumann & Morgenstern 1947). robust optimization (Ben- Tal et al. 2009), fairness-
aware machine learning (Zhang al. 2018), reinforcement learning (Du et al.] 2017 Wang 2017
Paternain et al. 2022; Wai et al.] 2018). decentralized optimization (Kovalev et al. 2021
2020
AUC maximization YYing al. 22166] Hanley & McNeil 1982
Yuan et al.) 2021).
First-order methods are widely studied for this problem. Classical algorithms include ExtraGradient
(EG) Korpelevich 1976] Nemirovski (2004). Optimistic Gradient Descent Ascent (OGDA) (Popov)
1980 Mokhtari et al.) 2020a b). Hybrid Proximal Extragradient (HPE) (Monteiro & Svaiter 2010).
and Dual Extrapolation (DE) (Nesterov & Scrimali] 2006) Nesterov 2007). When the gradient of
.)..)) is L-Lipschitz continuous, these methods achieve the rate of ((--)) under the convex- concave (C-C) setting and the rate of ((L//u) log(e-1)) when f(., is p-strongly convex in æ and j-strongly-concave in (SC-SC) for 0. They are all optimal in C-C and SC-SC settings
due to the lower bounds reported by [Nemirovski & Yudin 1983 Zhang et al. 2022a).
Equal contributions.
The corresponding author.

---

Published as a conference paper at ICLR 2025
Second-order methods usually lead to faster rates than first-order methods when the Hessian of f(...) is p-Lipschitz continuous. A line of works (Nesterov & Scrimali 2006 Huang et al.) 2022)
extended the celebrated Cubic Regularized Newton (CRN) (Nesterov & Polyak] 2006) method to minimax problems with local superlinear convergence rates and global convergence guarantee. However, the established global convergence rates of ((e=1) by Nesterov & Scrimali (006) and
((Lpp/z²) log(e-") by |Huang et al. (2022) under C-C and SC-SC conditions are no better than the optimal first-order methods. Another line of work generalizes the optimal first-order methods to higher-order methods. |Monteiro & Svaiter (2012) proposed the Newton Proximal Extragradient (NPE) method with a global convergence rate of ( 2/3 log log(s-1)) under the C-C conditions. This result nearly matches the lower bounds (Adil et al. 2022 Lin & Jordan 2024), except an addi-
tional (log log(e-)) factor which is caused by the implicit binary search at each iteration. [Bullins] y: Huang & Zhang (022): ) Lin et al. (2022) provided simple proof of NPE motivated by the EG analysis and showed that replacing the quadratic regularized Newton step with the cubic regularized Newton (CRN) step NPE achieves the optimal second-ordes oracle complexity of (e--2/)). Recently, Alles & Svaiter (003)) proposed a search-free NPE method to achieve the optimal second-order oracle complexity with pure quadratic regularized Newton step based on ideas from homotopy. Over the past decade, researchers also proposed various second- order methods, in addition to the NPE framework, that achieve the same convergence rate, such as the second-order extensions of OGDA (Jiang Mokhtari [022) Jiang et al., 2024) (which we refer to OGDA-2) and DE (Lin& & Jordan| (024) (they name the method Persesus). The results for C-C problems can also be extended to SC-SC problems, where Jiang & Mokhtari (2022) proved
& Lai (222); [Adil et al. (2022);
the OGDA-2 can converge at the rate of ((pp/u)2/3 + log log(e ")), and Huang Zhang 2022)
proposed the ARE-restart with the rate of ((p//n))/3 log log((-))
Although the aforementioned second-order methods Adil et al. (2022); Lin & Jordan 20244 Lin jt al. (2022): Jiang & Mokhtari (2022); Monteiro & Svaiter (2012) enjoy an improved convergence rate over the first-order methods and have achieved optimal iteration complexities, they require querying one new Hessian at each iteration and solving a matrix inversion problem at each Newton step, which leads to a (dd) computational cost per iteration. This becomes the main bottleneck that limits the applicability of second-ordes methods. Liu & Luo (2022a) proposed quasi-Newton meth- ods for saddle point problems that access one Hessian-vector product instead of the exact Hessian for each iteration. The iteration complexity is (de) for quasi-Newton methods. However, their methods do not have global convergence guarantee under general (S)C)-(S)C conditions. [Tiang] iet al. (023) proposed an online-learning guided Quasi-Newton Proximal Extragradient (QNPE) al- gorithm, but their method relies on more complicated subroutines than classical Newton methods. Although the oracle complexity of QNPE is strictly better than the optimal first-order method EG, their method is worse in terms of total computational complexity.
In this paper, we propose a computation efficcien second-order method, which we call LEN (Lazy Extra Newton method). contrast to all existing second-order methods or quasi-Newton methods for minimax optimization problems that always access new second-order information for the coming iteration, LEN reuses the second-order information from past iterations. Specifically, LEN solves a cubic regularized sub-problem using the Hessian from the snapshot point that is updated every m iteration, then conducts an extra-gradient step by the gradient from the current iteration. We provide a rigorous theoretical analysis of LEN to show it maintains fast global convergence rates and improves the overall computational complexity. We summarize our contributions follows (also see Table I.
second-order methods (Monteiro & Svaiter 2012) in terms of the
When the object function '(.,,) is convex in x and concave in y. we propose LEN and prove that it finds an e-saddle point in 0(m2/3,-2/3 iterations. Under Assumption 3.4 where the complexity of calculating F(z) is N and the complexity of calculating V is d.V, the optimal choice is m = (d). In this case, LEN only requires a computational complexity of ((NN+)))d++))))
2/3)), which is strictly better than (((++d)) )de 2/3)
for the existing optimal second-order methods by a factor of d!/3
When the object function ,(-,,) is p-strongly-comee
in æ and p-strongly-conean in y. we apply the restart strategy on LEN and propose LEN-restart. We prove the algorithm can find an e-root with Õ( + d') (d + (p/))/))) computational complexity, where means the Hessian of f(---) is p Lipschitz- Our result is strictly better than the Ö((N + (F)d(pp/))/// in prior works.
2

---

Published as a conference paper at ICLR 2025
We compare the required computational complexity achieve e-saddle point of the proposed LEN with the optimal choice m = ( and other existing algorithms on both convex- concave (C-C) and strongly-convve--sroe -strongly-concant
Table 1:
(SC-SC) problems. Here, d dg + dy the dimension of the problem. We assume the gradient is L-Lipschitz continuous for EG and the Hessian p- p-Lipschitz continuous for others. We count each gradient oracle call with N computational complexity, and each Hessian oracle with dN computational complexity. Computational Cost
Setup
Method
EG (Korpelevich 1976
O((N + +de
NPE (Monteiro & Svaiter 2012)
Ó(NN + dfyde 2/3)
C-C
search-free NPE AAves & Svaiter 2023
O((N + ddddde 2133)
OGDA-2 (Jiang Mokhtari 2022
O((N + dd)de 2113)
LEN (Theorem 4.3)
Ó((N + + + 6 (213))
EG
Korpelevich
1976
Ō((N + (1([[/M)
OGDA-2 Jaang & Mokhtari
2022
O(NN + dF)do//
SC-SC
ARE-restart (Huang & Zhang
2022
Ō((N + (
Perseus-restart (Lin & Jordan 2024
Ö(N xz)
LEN-restart (Corollary 4.1
+ 8 (p/1m)))))
Notations.
Throughout this paper, log is base 2 and log, (.) = 1 + log( We use || to denote the spectral norm and the Euclidean norm of matrices and vectors, respectively. We denote (t) = t - (t mod m) where m E N+.
RELATED WORKS AND TECHNICAL CHALLENGES
Lazy Hessian in minimization problems. The idea of reusing Hessian was initially presented
by Shamanskii (167)) and later incorporated into the Levenberg- -Maguurr-M method, the Damped
Newton method, and the proximal Newton method (Fan) 2013 Lampariello & Sciandrone 200T
Wang et al., 20066] Adler et al., 2020). However, the explicit ad advantage of lazy Hessian update over
ordinary Newton (-tyee) update was not discovered until the recent work of (Doikov et al. 2023
Chayti et al. 2023 They applied the following lazy Hessian update on cubic regularized Newton
(CRN) methods (Nesterov Polyak 2006):
M 1| z }
Zt41 arg min =ERd
(F(z), 2,) (VF()))) 21), zz)
(2)
where M 2 0 and F Rdd Rdd is the gradient field of a convex function. They establish the con- vergence rates of (0mme-///))) -3/2) for nonconvex optimization (Doikov et al. 2023). and ( for convex optimization (Chayti et 2023) respectively. Such rates lead to the total computational cost of Ö(NN + d² (d + de 3/2) and O(N + (d) + vde-1/2)) 1/2)) by setting m O(d), which strictly improve the result by classical CRN methods by a factor of vd both setups.
We have also observed that the idea of the "lazy Hessian" is widely used in practical second-order methods. KFAC (Martens Grosse 2015) Grosse & Martens 2016) approximates the Fisher infor- mation matrix and uses an exponential moving average (EMA) to update the estimate of the Fisher information matrix, which can be viewed as a soft version of lazy update. Sophia (Liu et al. 2024) estimates diagonal Hessian matrix duce the complexity. C2EDEN (Liu et al. (023) atomizes the communication of local Hessian in several consecutive iterations, which also benefits from the idea of lazy updates.
pre-conditioner, which is updated in lazy manner
Challenge of using lazy Hessian updates in minimax problems. In comparison to previous work on lazy Hessian, our LEN and EEN-rettart methods demonstrate the advantage of using lazy Hessian
3

---

Published as a conference paper at ICLR 2025
for broader class of optimization problems, the minimax problems. Our analysis differs from the ones Doikov et al. (023);; ; Chayti et al. (2023). Their methods only take a lazy CRN update (2) at each iteration, which makes easy to bound the enror of lazy Hessian updates using Assumption 3.1 and the triangle inequality in the following way:
( pl 2.11s SP
Σ 2 z+11ll-
Our method, on the other hand, not only takes lazy (regularized) Newton update but also requires an extra gradient step (Line Algorithm[]] [ Thus, the progress of one Newton update {I [|+ z (=))))))) camnot directly bound the error term || =x(t)]l introduced by the lazy Hessian update. Moreover, for minimax problems the matrix (=x(()) ) is no longer symmetric, which leads to different analysis and implementation of sub-problem solving (Section 4.3). We refer the readers to Section 4 for more detailed discussions.
PRELIMINARIES
In this section, we introduce the notation and basic assumptions used in our work. We start with several standard definitions for Problem (T).
Definition 3.1. We call function f(x, y) : Rds
x Rdd, + R has p-Lipschitz Hessians if we have
| f(x f² y') / | - s
x
1'|1, v(x, y), (ar' yy) E Rd x Rdv
Definition 3.2. differentiable funtrntttaaeeuuutiiiii p > if
for some
Va' x E R . E R² f(x', y) 2 f(x, v) + (x' - x) V vzf(x, y) + " ~ x'12,
2
f(x, v') S f(x, y) + (y' - y) V fz y) 1 11 - v', Vy'. e Rd, x Rd
We say f is comvex-concave if 0.
We are interested in finding saddle point of Problem ①.. formally defined as follows.
Definition 3.3. We call a point (x",y" E Rd x Rd a saddle point of a function f(.:)) if we have
f( y) I f(x", v²) S f(x E R. y E Rd
Next, we introduce all the assumptions made in this work. In this paper, we focus on Problem that satisfies the following assumptions.
Assumption 3.1. We assume the function f(:,.) is twice continuously differentiable, has p-Lipschitz continuous Hessians, and has at least one saddle point (a", ,"))
problems. Assumption 3.2 (C-C setting). We assume the function f(::-) convex in a and concave in y. Assumption 3.3 (SC-SC setting). We assume the function f(-.-) pestongglycooverrpssrnyyyy concave. We denote the condition number as k = p/p.
We will study convex-concave problems and stoongly-covvcc--stoonyyyyooo
We let d = dg + dy and denote the aggregated variable 2 = (xc, y) E Rdd. We also denote the GDA field of and its Jacobian as
V vzf(z,y) v fl
V2 fxx yo. f (2)
V2
f(x f(x y)
F(z)
V F
(3)
ny ff y)
The GDA field of f(.--) has the following properties.
Lemma 3.1 (Lemma 2.7 [in al. 2022)). Under Assumptions 3.1 and 3.2
have
4

---

Published as a conference paper at ICLR 2025
1. F is monotone, i.e. (F(z) F(z'), 2²) 2 0, Vz, 2' R
2. VF is p-Lipschitz continuous, i.e. [ (F('')l S plاz 2'11, V2 Rd.
3. F(z") ) 0 and only if (x² yy" is a saddle point of function (().)).
Furthermore, if Assumption 3.3 holds, we have F()) is y-strongly-monotone i.e.
(F(z) F(z', 2²) 2 اعع - z' z²11?, Vz, z' E Rd..
For the C-C case, the commonly used optimality criterion is the following restricted gap. Definition 3.4 (Nesterov) (.007). Let Ba(w) be the ball centered at w with radius B. Let (x", .y" be a saddle point of junction f. For given point (ž, ÿ). we let 3 sufficiently large such that it holds
max {1| - x²1; 1 y01l 58
we define the restricted gap function
Gap(# 9: 9: = max f(Ø y) yEB2(M))
f(x g). (a
min
We call (æ, 9) an e-saddle point if Gap(a; (t. ÿ: B) S and 3 Q[max 11.1, v²ll))
For the SC-SC case, we use the following stronger notion. Definition 3.5. Suppose that Assumption 3.3 holds. Let (x")y") be the unique saddle point function f. We call & = (#. ÿ) an e-root
x" S1.
Most previous works only consider the complexity metric as the number of oracle calls, where an oracle takes a point E I&d the input and returns tuple (z), V F())) as the output. The existing algorithms (Monteiro & Svaiter 2012, Bullins & Lai 2022 Adil et al. 2022, Lin et al.) 2022) have achieved optimal complexity regarding the number of oracle calls. In this work, focus on the computational complexity of the oracle. More specifically, we distinguish between the different computational complexities of caleulating the Hessian matrix V F2) and the gradient Fzz). Formally, we make the following assumption as Doikov et al. 2003)).
Assumption 3.4. We count the computational complexity of computing F(-) (() as N and the compu- tational complexity of ((.)) Nd.
Remark 3.1. Assumption 3.4 supposes the cost of computing (-) is d times that of computing F(.) ). It holds in many pracfical scenarios vector products on standard basis vectors C1, Cdd and one Hessian-vector product oracle is rypically expensive one gradient oracle (Wright 2006):
Hessian oracle can be computed via d Hessian-
1. When the computational graph of f is obtainable, both F(z) and FZ(2) can be com- puted using automatic differentiation with the same cost cost for any z, E Rdd.
2. When f is black box function, we can estimate the Hessian-vector F(()) via the finite- difference us(2;v) (F(z 2 + 8v) F(z 5v)) and we have limg- us us(2; V F())u under mild conditions on F(.).
ALGORITHMS AND CONVERGENCE ANALYSIS
In this section, present novel second-order methods for solving minimax optimization prob- lems (T). We present LEN and its convergence analysis for convex-concave minimax problems in Section 4.1 We generalize LEN for strongly-convex- wwreeesttooglyyconnne minimax problems by pre- senting LEN-restart in Section 4.2 We discuss the details of solving minimax cubic-regularized sub-problem, present detailed implementation of LEN,, and give the total computational complexity of proposed methods in Section
4.3
4.1 THE LEN ALGORITHM FOR CONVEX-CONCAVE PROBLEMS
We propose LEN for convex-concan problems in Algorithm T Our method builds on the optimal Newton Proximal Extragradient (NPE) method (Monteiro & Svaiter 2012 Bullins & Lai 2022
5

---

Published as a conference paper at ICLR 2025
Algorithm LEN 2o. T, M)
1: for = O, ... , do
2:
Compute lazy cubic step, i.e. find 1/4 that satisfies
F(z:)= (V M Iz 2t-1/2 1/2llla)(zt 2141/2).
3: Compute "/: = Ml| 1211/211-
4: Compute extra-gradient step Zr++1 = - - F(z441/2).
5: end for
6: return 27 Ei-0 7/
1==0 Tt 1/+1/2-
Adil al. 2022 Lin et al.
2022). The only change is that we reuse the Hessian from previous tterates, as colored in blue. Each iteration of LEN contains the following two steps:
F(.,) + (F((
z+) + M| zel(2z+1122 - 2t) 0, (Implicit Step)
F21-1112
Z141 = 21 M| - zz
(Explicit Step)
The first step (implicit step) solves a cubic regularized sub-problem based on the (F(2z()) com- puted the latest snapshot point and ((,, the current iteration point. This step is often viewed as an oracle (Bullins & Lai, 2022 Adil et al. 2022 Lin et al. 2022) as there exists efficient solvers,
which will also be discussed Section 4.3 The second one (explicit step) conducts an extra gradient step based on F(#+11/2)
Reusing the Hessian the implicit step makes each iteration much cheaper, but would cause ad- ditional errors compared to previous methods (Monteiro & Svaiter 2012 Huang & Zhang [222]] Adil et al. 2022 Lin et al.] 2022). The error resulting from the lazy Hessian updates is formally characterized by the following theorem.
Lemma 4.1. Suppose that Assumption 3.1 and 3.2
hold. For any z E Ed, Algorithm 1 ensures
7/ (F((e11/2) 1141/2 2)
I
2 - x1|²-
3 || - =x112- 2 | - =2+1112
2
122
2p²
2 = 2++1/2|
|| - 2+11/212
M [|))(() 2z 12.
2M
(*)
Above, (*) is the error from lazy Hessian updates. Note that (*) vanishes when the current Hessian is used. For lazy Hessian updates, the error would accumulate in the epuch.
The key step in analysis shows that inequality in Lemma 4.1 to bound the accumulated error by choosing M sufficiently large, with the help of the following technical lemma.
use the negative terms in the right-hand side of the
Lemma 4.2. For any sequence of positive numbers (re)e2o, holds for any m 2 2 that EP
mm rī.
2012 Bullins & Lai 2022 Adil et al.) 2022; Lin et al.) 2022) without using lazy Hessian updates. When m 2 2, we use Lemma 4.2 to upper bound the error that arises from lazy Hessian updates. Finally, we prove
When 1, the algorithm reduces to the NPE algorithm (Monteiro & Svaiter
the following guarantee for our proposed algorithm.
Theorem 4.1 (C-C setting). Suppose that Assumption
3.1 and 3.2 hold. Let z" (x" ; yy) be saddle point and B = =0 - 211.. Set M 2 3pm. The sequence of iterates generated by Algorithm Vt 0.... T 1, and satisfies the following
I is bounded zı Bz((z), 2411/2 E B30(2*).
ergodic convergence:
32M 20 x=
Gap(@r, Fr: 38)
T3/2
Let M 3pm. Algorithm finds e-saddle point within 2/3 22/3) 2/3) iterations.

---

Published as a conference paper at ICLR 2025
Algorithm 2 LEN-restart(A4 2n. T, M, S)
1: z =0)) 20
2: for = 0, ..... .S .S-1
3: 2 ( LEN( LEN M)
end for
Discussion the computational complexity of the oracles. Theorem indicates that LEN requires 0 -2/3) calls to F()) and 0(m2/se- /////////mmm//m //m+11 1) calls to V (-) to find the e-saddle
point. Under Assumption 3.4 the computational cost to call the oracles (-) and FF()) is
Oracle Computational Cost = O .m. m/33 2/3 (Nd)
(e (6- 1/3 + +1))
(5)
Taking ((d) minimizes 5 to ONN Nd 2/3). Compared to state-of-the-ar second-
order methods (Monteiro & Svaiter 2012 Bullins & Lai 2022: Adil et al. 2022 Lin et al. 2022
whose computational cost in terms of the oracles is O de 2nd) since they require query (-(()
each iteration, our methods significantly improve their results by factor of d2/3
is worth noticing that the computational cost of an algorithm includes both the computational cost of calling the oracles, which we have discussed above, and the computational cost of performing the updates (i.e. solving auxiliary problems) after accessing the required oracles. We will give an efficient implementation of LEN and analyze the total computational cost later Section 4.3
4.2 THE LEN-RESTART ALGORITHIM FOR SONNNGLL-OONNE-SSTTNNGLLOOOOOOOO PROBLEMS
minimax optimization by incor- porating the restart strategy introduced by Huang & Zhang (2022); Lin & Jordan (2024). We propose the LeNtrestart in Algorithm 2 which works in epochs. Each epoch of LEN rrstaat invokes LEN
We generalize LEN to solve the -oongly--oooee--roonyyy---o
Lin
(Algorithm D. which gets (()) as inputs and outputs 2(++))
The following theorem shows that the sequence (2(*)) enjoys superlinear convergence in epochs. Furthermore, the required number of iterations in each epoch to achieve such superlinear rate is only a constant.
Theorem 4.2 (SC-SC setting). Suppose that Assumptions 3.1 and 3.3 hold. Let 2" = (x", .y") be
[2d][===='] 2/3 "
the unique saddle point. Set M 3pm as Theorem 4.1 and
Then the
sequence of iterates generated by Algorithm 2 converge to z" superlinearly as [| 2 2 s
(3) 03/2 | == 112. In other words, Algorithm 2 finds a point 2(0) such that || 2" S
within loga/2 (+e) epochs. The total number of inner loop iterations is given by
TS = O ( (m213 2/3 loglog log(1/)))
Under Assumption 3.4 Algorithm 2 with m ((d) takes the computational complexity of O(NN++ N/2/3 2/233 log (og(2())) to call the oracles F(.) and F())..
4.3 IMPLEMENTATION DETAILS AND COMPUTATIONAL COMPLEXITY ANALYSIS
We provide details of implementing the cubic regularized Newton oracle (Implicit Step. 4 In- spired by Monteiro & Svaiter (2012); Bullins & Lai 2022 Adil et al. (2022); Lin et al. 2022 we transform the sub- sub-problem into root-fiin not-finding problem for univariate function.
Lemma 4.3 (Section 4.3 Lin et al. (202))). Suppose Assumption 3.7 and 3.2 hold for function
Rd x Rd4y + R and let F be its GDA field. Define itt M 2111/2 zell. The cubic
regularized Newton oracle (Implicit Step, 4 can be rewritten as:
2r+1/2 21 (VF(zz(())
F
which can be implemented by finding the root of the following univariate function: <(7) M II( (F((())) + -1
(6)
Furthermore, the function ((7) is strictly decreasing when X > 0.
7

---

Published as a conference paper at ICLR 2025
Algorithm 3 Implementation of LEN (zo, T, m, M)
1: for = 0, ... , do
2: if mod
do
3:
Compute the Schur decomposition such that VF = QUQ
4: end if
5: Let <(.) defined as and compute 7tt as its root by a binary search.
6: Compute lazy cubic step 2t+1/2 QUU + TLaa) 'Q Fzz)).
7: Compute extra-grast aatti-gradeent step 2t+1 = 2t - 7t- (2
8: end for
9:
return 2T 2120 71
= 7h 22-1/2-
From the above lemma, implement the cubic regularized Newton oracle, it suffices to find the root of strictly decreasing function @(7), which can be solved within ((1) iteration. The main operation is to solve the following linear system:
(VF((=()) + +ddgh = F(z.).
Naively solving this linear system at every iteration still results in an expensive computational com- plexity (dd) per iteration.
We present a computationally efficient way to implement LEN by leveraging the Schur factorization at the snapshot point (=(((()) = QUQ where Q E Cd is unitary matrix and U E Cd an
upper-triangular matrix. Then solving the linear system 7 is equivalent
h QUU + F
The final implementable algorithm is presented in Algorithm 3
Now, we are ready to analyze the total computational complexity of LEN, which can be divided into the following two parts:
Computational Cost Oracle Computational Cost + Update Computational Cost,
where the first part has been discussed in Section 4.1 Regarding the update computational cost, the
Schur decomposition with an computational complexity O(d3) is required once every iterations. After Schur's s decomposition has been given at the snapshot point, the dominant part of the update computational complexity is solving the upper-triangular linear system (8) with the back substitution algorithm within the computational complexity (dd). Thus, we have
Update Computational Cost = Ô Ō( 2m.mm11 22/3 + +d8 10-33 + 1))
(9)
and the total computational cost of LEN
Computational Cost
5 (idP + N) 2
2/3 + (d) + Nd)
(f-2/mm 1/3 + +1)) (10)
By taking (d). obtain the best computational complexity in (10 of LEN, which is for- mally stated in the following theorem.
Theorem 4.3 (C-C setting). Under the same setting of Theorem 4.1 Algorithm with m O(d)
finds an e -saddle point with computational complexity Ō(NN + d (d + 223
We also present the total computational complexity of LEN-restan for SC-SC setting.
Corollary 4.1 (SC-SC setting). Under the same setting as Theorem 4.2 Amgorithm@imppemmenn in the same way as Algorithm with ((d) finds e-root with computational complexity Ö((N (d + d2/3,2/23
In both cases, our proposed algorithms improve the total computational cost of the optimal second- order methods (Monteiro & Svaiter 2012 Bullins & Lai 2022; Adil et al. 2022; Lin et al. 2022) by factor of d73
8

---

Published as a conference paper at ICLR 2025
10
10
gred. norm
10"1
grad norm
10-1
10"4
EG
NPE
NPE
NPE
10"1
LEN-10
20"3
LEN-10
2.10-
LEN-10
LEN-2
LEN-100
LCN-100
LEN-100
10-10
10-5
10-5
0.0
2.5
5.0
7.5
10.0
0
20
40
20
40
60
80
time (s)
time (6)
time (5)
(a) n 10
(b) n 100
(c)
200
Figure I: We demonstrate running time v.s. gradient norm [= for Problem 11 with different sizes: {10, 100, 2003.
Remark 4.1. In the main text, we assume the use of the classical algorithm for matrix inver- sion/decomposition, which has computational complexity of (dd).. The fast matrix multiplication proposed by researchers in the field of theoretical computer science only reguires a complexity of d' where the best known is currently around 2.371552 (Williams et al. 2024y. This also implies faster standard linear algebra operators including Schur decomposition and matrix inversion (Dem-) mel el al. 2007). However, the large hidden constant factors in these fast matrix multiplication al- gorithms mean that the matrix dimensions necessary for these algorithms to be superior to classical algorithms are much larger than what current computers can effectively handle. Consequentl, these algorithms are not always used in practice. We present the computational complexity of using fast matrix operations Appendix G
In Appendix H extend our algorithms to allow inexact auxiliary CRN sub-problem solving and analyze the total complexity. Specifically, we design an efficient sub-procedure (Algorithm 5 to solve the CRN sub sub-problem to desired accuracy in only Oloo log(1/c)) number of linear system solving. It tightens the (logg(1/e) iteration complexity in (Bullins & Lai 2022 Adil et al. 2022) Additionally, (Bullins& & Lai, 2022 Adil et al. 2022) assume min (VF(z) > l for some positive constant μ. which makes the problem similar to our analysis does require such assumption.
problems, while
NUMERICAL EXPERIMENTS
We conduct our algorithms on a regularized bilinear min-max problem and fairness-aware machine learning tasks. We include EG (Korpelevich) 1976) and NPE (Monteiro & Svaiter 2012: Bullins
Lai 2022; Adil et al. 2022. Lin al. (2022) (which is our algorithm with 1) baselines, since they are the optimal first- and second-ord order methods for convex-concan minimax problems, respectively. We run the programs on an AMD EPYC 7H12 64-Core Processor,
5.1 REGULARIZED BILINEAR MIN-MAX PROBLEM
We first conduct numerical experiments on the cubic regularized bilinear min-max problem consid- ered in the literature (Lin et al. 2022 Jiang et al. 2024
min max f(x y) #ER" MER"
~ (Ax b).
(11)
The function f(x, y) is convex-concave and has p- p-Lipschitz continuous Hessians. The unique saddle point z' (xr y²) of [(x, y) can be explicitly calculated x" bb and y -pl x (AT x=' /2, so we can compute the distance to x" to measure the performance of the algorithms. Following Lin al. (2022), we generate each element in independent Rademacher
variables in (-1,+1) set p 1/(20n) and the matrix A
1
-1
'The codes available httph///h...///gggttt.oo//////er

---

Published as a conference paper at ICLR 2025
10"1
gred. norm
10-3
grad. norm
10"3
grad. norm
4
10
10
EG
10
EG
10-2
NPE
10-9
NPE
10-15
NPE
LEN
LEN
LEN
10-12
10-12
10-13
0
3
200
400
2000
4000
time (9)
time
time (s)
(a) heart
(b) adult
(c) law school
Figure 2: We demonstrate running time v.s. gradient norm [=())] for faimess-awaare machine learning task (Problem (12) datasets "heart", "adult", and "law school".
We compare our methods with the baselines on different sizes of the problem: {10, 100, 200). For EG, we tune the stepsize in {1, 0.1, 0.01, 0.0013. For LEN, we vary m in {1, 10, 100). The results of the running time against [2))l are presented in Figure 1
5.2 WARRNESS-AWARE MACHINE LEARNING
We then examine our algorithm for the task of fairness-aware machine learning. Let {a,, bis Cs 2=1 be the training set, where a; E IRd denotes the features of the i-th sample, corresponding label, and G E +1] is an additional feature that is required to be protected and debiased. For example, e; can denote gender. [hhang al. (2018) proposed to solve the following minimax problem to mitigate unwanted bias of by adversarial Tearmin
{-1,+1] is the
min max- Σ e(b.a, x) - 3l(caya x) + A||x0| - ~y2
(12)
where / is the logit function such that ((t) = log exp( ()). We \ = 10-4 and 0.5. We conduct the experiments on datasets "heart" (n 270, dy = 13) (Chang & Lin 2011 "adult" (n 32, 561, d 123) (Chang & Lin 2011 and "law school" (n 20, 798, d₂ 380) (L Quy et al. 2022 Liu et al. 2022). For all the datasets, we choose "gender" as the protected feature. For EG, we tune the stepsize in (0.1, 0.01, 0.001). For second-order methods (NPE and LEN), as we do not know the value of in advance, we view it as a hyperparameter and tune it in {1, 10, 100). We set m 10 for LEN and we find that this simple choice performs well in all the datasets we test.
We show the results of the running time against the gradient norm [x)]] in Figure
6 CONCLUSION AND FUTURE WORKS
In this paper, we propose LEN and LEN-restart for C-C and SC-SC minimax problems, respectively. Using lazy Hessian updates, our methods improve the computational complexity of the current best- known second-orde methods by factor of d3/3, Numerical experiments on both real and synthetic datasets also verify the efficiency of our method.
For future work, it will be interesting extend idea adaptive second-order methods (Wang jet al. 2024a Doikov et al., 2024; Carmon et al. 2022) AAttonkkopoulos et al. 2022 Liu & Luo 2022b) and stochastic problems with sub-sampled Newton methods (Lin al. 2022] Chayti al. 2023 Zhou et al. 2019 Tripuraneni et al. 2018 Wang et al., 2019). Besides, our methods only focus on the convex- conceve case, also possible reduce the Hessian oracle for nonconvex- (strongly)-concave problems (Luo et al.) [002] Lin et al.) 2020 Yang et al.) [023] Zhang et al.) Wang et al. 2024b) or study structured
2022b
problems (Zheng et al.,
2024
Diakonikolas et al. 2021 Yang et al. 2020 Lee & Kim 2021
Chen & |Luo 2024).
ACKNOWLEDGMENTS
Lesi Chen and Jingzhao Zhang are supported by the Shanghai Qi Zhi Institute Innovation Program. Chengchang Liu is supported by the National Natural Science Foundation of China (624B2125).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Deeksha Adil, Brian Bullins, Arun Jambulapati, and Sushant Sachdeva. Optimal methods for higher- order smooth monotone variational inequalities. arXiv preprint arXiv:2205.06166. 2022.
Ilan Adler, Zhiyue T. Hu, and Tianyi Lin. New proximal newton-type methods for convex optimiza- tion. In CDC, 2020.
M. Marques Alves and Benar Svaiter. search-free O(1/k9/2) homotopy inexact proximal-newton extragradient algorithm for monotone variational inequalities. arXiv preprint arXiv:2308.05887, 2023.
Kimon Antonakopoulos, Ali Kavis, and Volkan Cevher. Extra-newton: A first approach to noise- adaptive accelerated second-order methods. In NeurlPS, 2022.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization, volume 28.
Princeton university press, 2009.
Brian Bullins and Kevin A. Lai. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM Journal Optimization, 32(3):2208-2229, 2022.
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and
adaptive monteiro-svaiter acceleration. In NeurIPS, 2022.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM fransactions on intelligent systems and technology (TIST), 2-) 2011.
El Mahdi Chayti, Nikita Doikov, and Martin Jaggi. Unified convergence theory of stochastic and variance-reduced cubic newton methods. arXiv preprini 2rXiv:2302.11966 2023.
Lesi Chen and Luo Luo. Near-optimal algorithms for making the gradient small in stochastic mini- max optimization. JMLR, 2024.
James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable, Numerische Mathe- matik, 108(1):59-91,20))
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan. Efficient methods for struc- tured nonconvex-moncconaree min-max optimization. In A/STATS, 2021.
Nikita Doikov, El Mahdi Chayti, and Martin Jaggi. Second-order optimization with lazy hessians. In ICML, 2023.
Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. Super-universal regularized newton method. SIAM Journal Optimization, 34(1):27-56, 2024.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In ICML, 2017.
Jinyan Fan. A shamanskii-like levenberg- -arbbbrrd- method for nonlinear equations. Computational Optimization and Applications, 56( (x63-80, 2013.
Roger Grosse and James Martens. A kronecker-factored approximate fisher matrix for convolution layers. In ICML, 2016.
James A Hanley and Barbara J McNeil. The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology, 143(1):29-36, 1982.
Kevin Huang and Shuzhong Zhang. An approximation-based regularized extra-gradient method for monotone variational inequalities. arXiv preprint arXiv:2210.044400, 2022.
Kevin Huang, Junyu Zhang, and Shuzhong Zhang. Cubic regularized newton method for the saddle point models: A global and local convergence analysis. Journal of Scientific Computing, 91()): 60, 2022.
Ruichen Jiang and Aryan Mokhtari. Generalized optimistic methods for convex-concave saddle point problems. arXiv preprint arXiv:2202.09674 2022.

---

Published as a conference paper at ICLR 2025
Ruichen Jiang. Qiujiang Jin, and Aryan Mokhtari. Online learning guided curvature approximation: A quasi-newton method with global non-asymptotic superlinear convergence. In COLT, 2023.
Ruichen Jiang, Ali Kavis, Qiujiang Jin, Sujay Sanghavi, and Aryan Mokhtari. Adaptive and optimal second-order optimistic methods for minimax optimization. In NewrIPS, 2024.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. In NeurlPS, 2020.
Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtarik. Lower bounds and op- timal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. In NeurIPS. 2021.
Francesco Lampariello and Marco Sciandrone. Global convergence technique for the newton method with periodic hessian evaluation. Journal of optimization theory and applications, 111: 341-358, 2001.
Tai Le Quy, Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Eirini Ntoutsi. A survey on datasets for fairness-aware machine learning. Wiley Interdisciplinary Reviews: Data Mining and Knowl- edge Discovery, 1253) 2022.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. In NeurlPS, 2021.
Tianyi Lin and Michael Jordan. Perseus: A simple high-order regularization method for variational inequalities. Mathematical Programming, pp. 1-42, 2024.
Tianyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In COLT, 2020.
Tianyi Lin, Panayotis Mertikopoulos, and Michael I. Jordan. Explicit second-order min-max opti- mization methods with optimal convergence guarantee. arXiv preprint 22.:::2//0./2866/ 2022.
Chengchang Liu and Luo Luo. Quasi-newton methods for saddle point problems. In NeurlPS, 2022a.
Chengehang Liu and Luo Luo. Regularized newton methods for monotone variational inequalities with Holders continuous jacobians. arXiv preprint arXiv:2212.07824, 2022b.
Chengchang Liu, Shuxian Bi, Luo Luo, and John CS Lui. Partial-quasi-newton methods: efficient algorithms for minimax optimization problems with unbalanced dimensionality. In SIGKDD, 2022.
Chengehang Liu, Lesi Chen, Luo Luo, and John CS Lui. Communication efficient distributed new- ton method with fast convergence rates. In SIGKDD, 2023.
Hong Liu, Zhiyuan Li, David Hall, Percy Liang. and Tengyu Ma. Sophia: A scalable stochastic second-order optimizer for language model pre-training. In ICLR, 2024.
Luo Luo, Yujun Li, and Cheng Chen. Finding second-order stationary points in nonconvex-stroogly- concave minimax optimization. In NeurlPS, 2022.
James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factoree approximate curvature. In ICML, 2015.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTATS, 2020a.
Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate of O(1kk) for op- timistic gradient and extragradient methods smooth convex-concawe saddle point problems. SIAM Journal on Optimization, 30(4):3230-3251, 2020b.
12

---

Published as a conference paper at ICLR 2025
Renato DC Monteiro and Benar F Svaiter. Iteration-com complexxit of newton proximal extragra- dient method for monotone variational inequalities and inclusion problems. SIAM Journal on Optimization. 22(3):914-933 14-55,, 2012.
Renato DC Monteiro and Benar Fux Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 2066):755-22777, 2010.
Arkadi Nemirovski. Prox-method with rate of convergence O(L/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15()):22--251, 2004.
Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2-3):319-344, 2007.
Yurii Nesterov and Boris T Polyak. Cubie regularization of newton method and its global perfor- mance. Mathemutical Programming, 108(1): 2006.
Yurii Nesterov and Laura Scrimali. Solving strongly monotone variational and qursi-variational inequalities. 2006.
Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods. IEEE Transactions Automatic Control, 68(3):131--1336, 2022.
Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845-844 1980.
R. Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal control and optimization, 14(5).877-89) 1976.
VE Shamanskii. 118-122, 1967.
modification of newton's 's method. Ukrainian Mathematical Journal, 19(1):
Nilesh Tripuraneni, Mitchell Stem, Chi Jin, Jeffrey Regier, and Michael I Jordan. Stochastic cubic regularization for fast nonconvex optimization. In NewrlPS, 2018.
John Von Neumann and Oskar Morgenstem. Theory of games and economic behavior, 2nd rev. 1947.
Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. In NeurIPS, 2018.
Chang-yu Wang, Yuan-yuan Chen, and Shou-qiang Du Further insight into the shamanskii modifi- cation of newton method. Applied mathematics and computation, (80(1):46-55 2006.
Junlin Wang, Junnan Yang, and Zi Xu. fully parameter- freee second-order algorithm for convex- concave minimax problems with optimal iteration complexity. arXiv preprint arXiv:2407.03571, 2024a.
Mengdi Wang. Primal-dual r-learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprint arXiv: 2017.
Nuozhou Wang, Junyu Zhang, and Shuzhong Zhang. Efficient first order method for saddle point problems with higher order smoothness. SIAM Journal on Optimization, 34(4):3342-3370, 2024b.
Zhe Wang, Yi Zhou, Yingbin Liang, and Guanghui Lan. Stochastic variance-reduced cubic regular- ization for nonconvex optimization. In AISTATS, 2019.
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In SODA, 2024.
13

---

Published as a conference paper at ICLR 2025
Stephen J. Wright. Numerical optimization, 2006.
Yangyang Xu. Primal-dual stochastic gradient method for convex programs with many functional constraints. SIAM Journal on Optimization, 30(2):6644-166 2020.
Haikuo Yang, Luo Luo, Chris Junchi Li, Michael Jordan, and Maryam Fazel. Accelerating inexact hypergradient descent for bilevel optimization. In OPT 2023: Optimization for Machine Learn- ing. 2023.
Junchi Yang, Negar Kiyavash, and Niao Hc. Global convergence and variance reduction for class of conconvex-noncooceee minimax problems. In NeurIPS, 2020.
Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. In NIPS, 2016.
Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep auc maxi- mization: A new surrogate loss and empirical studies on medical image classification. In ICCV, 2021.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adver- sarial learning. In Proceedings of the 2018 AAAT/ACM Conference on AI, Ethics, and Society, pp. 335-340, 2018.
Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1-2):0119335 2022a.
Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. SAPD+: An accelerated stochastic method for conconvex-coneav minimax problems. NeurlPS, 2022b.
Taoli Zheng, Linglingzhi Zhu, Anthony Man-Cho So, José Blanchet, and Jiajin Li. Universal gradi- ent descent ascent method for mmnconvex-nonconcee minimax optimization. In NeurIPS, 2024.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularization meth- ods. JMLR, 20(134):1-41 2019.
14


Reviews:
[{"review_id": "utFT8zIf6A", "reviewer": "Reviewer_Z87Q", "summary": "This work proposed second-order algorithms LEN and LEN-restart for C-C and SC-SC min-max problems, these algorithms incorporate lazy Hessian update and Extragradient update, the computational cost analysis and numerical experiment results showed the outperformance of the proposed algorithms versus existing algorithms.", "questions": "/", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A new algorithm in min-max optimization with better computational complexity versus existing results.\n2. The paper is well organized, the flow is easy to follow.", "weaknesses": "1. The main component seems to be a combination of Doikov et al. (2023) on lazy Hessian and Adil et al., (2022) on extragradient, which may restrict the novelty a bit.\n2. The experiment can be further enhanced. \n   - First, the $O(d^{1/3})$ improvement suggests the outperformance is valid in high-dimensional cases (while not in low-dimensional cases), now the experiment cannot exhibit such a pattern, how does the algorithm perform in low-dimensional case?\n   - It is not clear how the choice of $m$ affects the performance, maybe you can follow Doikov et al. (2023) to add more experiments for clarification.\n   - The theory part uses the gap function as the measurement, while the experiment uses the gradient norm or point distance, maybe you can add more clarification to rationalize your choice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "ZgiXM8oAJM", "reviewer": "Reviewer_6zp1", "summary": "Authors generalize the results of Nikita Doikov, El Mahdi Chayti, and Martin Jaggi. Second-order optimization with lazy hessians. In ICML, 2023. related with lazy Hessian for Cubic regularized Newton method for Saddle-point problems (SPP). The developed result was cleary presented and sufficiently technical. Moreover, requires principally new ideas. However, the the motivation to consider second-order methods are quite limited and is mainly theoretical from my point of view. Also in the paper authors doesn't observe the accuracy required to solve auxiliary problem.", "questions": "1) Is it possible to generalize the result in case strongly convex-strongly concave case with different constant of strong convexity/concavity?\n2) Could you estimate the required accuracy for auxiliary problem that guarantee the desired precision for target problem? \n I can make rating higher if you can positively answer for this questions.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I guess the paper is good from mathematical point of view. The results is strong, original, well presented. I agree with authors that they developed significantly new tricks to work with this class of problems. I guess the paper is good!", "weaknesses": "For me the main drawback is motivation. I do not understand why we should use second-order method with expensive iteration rather than the first-order one. I understand the motivation for convex optimization where the number of iteration significantly reduces by using optimal second-order scheme, but I do not understand it for SPP where the difference is minor.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "gH23r6LFZX", "reviewer": "Reviewer_QgT2", "summary": "In this paper authors utilize the lazy Hessians technique inside second-order extragradient method for min-max optimization. The main idea of lazy Hessians technique is to update Hessian in second-order method only every $m$ iterations. Authors consider convex-concave and strongly-convex-strongly-concave setups. Authors claim, that if $m=\\Theta(d)$ iterations, where $d$ is a dimension of the problem, their method achieves state-of-the-art computational cost.", "questions": "1. Could you explain please, how did you get second inequality in eq. (17)?\n1. Lines 155-160. Sentence \"Their methods only take a lazy CRN update (2) at each iteration...\" seems to me very weird. I needed to read it couple of times to understand. Please, rewrite in in more clear way.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Authors propose a method with the same oracle complexity, as state-of-the-art methods but with less computational complexity. This means, that their algorithm can achieve the same estimation error with the same number of iterations, but overall spending less computational resources and taking less time. The experimental results only support this point. This makes method more attractive from the practical point of view. The paper is written in a clear way, and it is easy to understand.", "weaknesses": "Overall, the paper feels like a very incremental result. Authors employ a known technique to reduce number of Hessian computations to existing second-order method to solve convex-concave min-max problem. To adapt proposed method to strongly-convex-strongly-concave problem, authors use a universal restarts framework, that works like a \"wrap\" around any method for convex(-concave) problems and gives better theoretical convergence for strongly-convex(-strongly-concave). Despite the fact that this paper proposes a new method with better computational complexity compared to other analogs, it lacks any novel ideas or solution of any complex problems.\n\n## Typos\n1. Lines 785-786: it should be $\\frac{m^2 + 2m}{2}$\n1. Lines 862-863: upper index in the second sum should be $\\pi(t) + s  - 1$\n2. Definition 3.5: in the end it should be $||\\hat z - z^*||\\le \\epsilon$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "FOLDoq6Yjx", "reviewer": "Reviewer_LatJ", "summary": "This paper proposes a second-order algorithm designed for convex-concave minimax optimization problems. The algorithm brings the Lazy Hessian (or Lazy *Jacobian* for this paper, I guess) approach by Doikov et al. (2023) to second-order minimax optimization algorithms as in Adil et al. (2022), Lin et al. (2022). The new algorithm can achieve a computational complexity smaller by an order of $d^{1/3}$ compared to previous results both for the convex-concave case. The paper also shows superlinear convergence in the strongly-convex-strongly-concave case (by adding a restarting scheme) where we also have an improvement of $d^{1/3}$.", "questions": "- In the proof of Theorem 4.1, what we essentially do is find an upper bound of\n    $$ \\begin{align*}\n    \\frac{1}{\\sum_{i=0}^{t-1} \\eta_i} \\sum_{i=0}^{t-1} \\eta_i \\langle F(z_i),  z^{\\star} - z_i\\rangle\n    \\end{align*} $$\n    which itself is an upper bound of the Gap function by Lemma A.1.\n    \n    My question is, can’t we just try to come up with an upper bound of the *MVI error* $\\langle F(\\hat{z}), z^{\\star} - \\hat{z} \\rangle$ instead? If this works, it might be possible to extend the results to general MVIs. (I think one problem could be that we can’t use things like Jensen’s inequality if we step out of the convex-concave assumption.)\n    \n- Is the $\\beta$ in Definition 3.4 just there for technical reasons (to ensure something like bounded iterates for the unconstrained case)?\n\n- This might be a slightly irrelevant question, but any ideas of whether the proposed idea (or maybe the Lazy Hessian idea for minimization problems) could work for higher-order cases with $p \\ge 3$?\n\n- There seem to be complicated lower bound results in Adil et al. (2022) in terms of the *iteration* complexity. Can this naturally lead to some type of a lower bound in the *computational* complexity as well with which we can compare the new/previous upper bounds?\n\n- Minor typo. In the middle of the inequality of Definition 3.3, I think it should be $f(x^{\\star}, y^{\\star})$.\n\n**References.** \\\nAdil et al., 2022. Optimal methods for higher-order smooth monotone variational inequalities. \\\nDoikov et al., 2023. Second-order optimization with lazy Hessians. \\\nLin et al., 2022. Explicit second-order min-max optimization methods with optimal convergence guarantee.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It is interesting to see that the idea of Doikov et al. (2023) can also work for minimax optimization problems.\n- The paper seems to be well-written and clear, and there are empirical results supporting the theoretical arguments.", "weaknesses": "- The results only cover convex-concave minimax optimization for now, and there are no clear ways suggested to extend to broader problem classes like nonconvex-nonconcave functions or variational inequalities.\n- As the main idea comes from combining two lines of previous work, it’s a bit hard to say that the ideas are highly original (except for the proof techniques of bounding the errors from lazy updates for the minimax case, particularly when there are EG steps in between).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)