Quasi-Newton Methods for Saddle Point Problems
Authors: Chengchang Liu
Luo Luo
Venue: NeurIPS 2022 Accept (2022)
Keywords: Minimax Optimization
Quasi-Newton

Abstract: This paper studies quasi-Newton methods for strongly-convex-strongly-concave  saddle point problems. 
We propose random Broyden family updates, which have explicit local superlinear convergence rate of ${\mathcal O}\big(\big(1-1/(d\varkappa^2)\big)^{k(k-1)/2}\big)$, where $d$ is the dimension of the problem, $\varkappa$ is the condition number and $k$ is the number of iterations. The design and analysis of proposed algorithm are based on estimating the square of indefinite Hessian matrix, which is different from classical quasi-Newton methods in convex optimization. We also present two specific Broyden family algorithms with BFGS-type and SR1-type updates, which enjoy the faster local convergence rate of $\mathcal O\big(\big(1-1/d\big)^{k(k-1)/2}\big)$. Our numerical experiments show proposed algorithms outperform classical first-order methods.

Quasi-Newton Methods for Saddle Point Problems
Chengehang Liu
Luo Luo" School of Data Science Fudan University luoluo@fudan, edu, cn
Department of Computer Science & Engineering The Chinese University of Hong Kong
7 com
Abstract
This paper studies quasi-Newton methods for strongly-conee ceceyy-ooooo---steeeee -tronnlyy-oonnantt saddle point problems. We propose random Broyden family updates, which have explicit local superlinear convergence rate of O((1 1/(d>")) ()((()))))))) where d is the dimension of the problem, x is the condition number and is the number of iterations. The design and analysis of proposed algorithm are based on estimating the square of indefinite Hessian matrix, which different from classical quasi- Newton methods in convex optimization. We also present two specific Broyden family algorithms with BFGS- and SRI-type updates, which enjoy the faster local convergence rate of O((1 1/d) Our numerical experiments show proposed algorithms outperform classical first-order methods.
Introduction
In this paper, we focus on the following smooth saddle point problem
min max f(x,y), xER yER
where f is strongly-convex x and strongly-concave in y. We target to find the saddle point (x") (x",y" y*)
which holds that
f(x",y) S f(x", f(x
for all x Rd, and y E Rd, This formulation is widely used in game theory 1 39 AUC
maximization [3 43), fairness-aware machine learning [44], robust optimization
36),
empirical risk minimization
46 and reinforcement learning [10].
There are great number first-order optimization algorithms for solving problem T.. including extragradient method [I8] 38 optimistic gradient descent ascent 77 proximal point method [3]
and dual extrapolation [24]. These algorithms iterate with first-order oracle and achieve linear
convergence. Lin et al. (21. Wang and Li [40] used Catalyst acceleration reduce the complexity for unbalanced saddle point problem, nearly matching lower bound first-order algorithms [26
45 under some specific assumptions. Compared with first-order methods, second-order methods usually enjoy superior convergence numerical optimization. Huang et al. [16] extended cubic regularized Newton (CRN) method [23 24] to solve saddle point problem (T). which has quadratic local convergence. However, each iteration of CRN requires accessing the exact Hessian matrix and solving the corresponding linear systems. These steps arise O (d d time complexity, which is too expensive for high dimensional problems.
37 are popular ways avoid accessing exact second-order informa- Quasi-Newion methods [355
tion applied in standard Newton methods. They approximate the Hessian matrix based on the Broyden family updating formulas 3. which significantly reduces the computational cost. These algorithms
TThe corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: We summarize the convergence behaviors of proposed algorithms for solving saddle point def
problem in the view of gradient norm Ak+ IV after (k + ko) iterations, where
del d + dy is dimensions of the problem and x is the condition number. The results come from
3.18 and the upper bound holds with high probability at least - 8.
Algorithms
U Upper Bound of Ak+Ko
ko
Broyden (Alg. 5
k(k R(k-1)/
1)/2
(1 - 1x
1
Ko
(dx² In (4x
dx
BFGS/SRI (Alg. 6 and 7
k(k-
(1) (1
No
((d + x²) In (dx)
d41
are well studied for convex optimization.
The famous quasi-Newton methods including Davidon- Goldfeee Shanno (BFGS) method
Fletcher- (DFP) method 8 12.
4
5 37
29 when the ob- jective function is strongly- cronve..-covvx.... Recently, Rodomanov and Nesterov 32 33 proposed greedy
and symmetric rank I (SR1) method 3 enjoy local superlinear convergence 6
9
and random variants of quasi-Newton methods, which first achieves non con-asymptotic superlinear con- vergence. Later, Lin et al. [20] established a better convergence rate which condition ceaiitionnnumbe---eee free. 42 showed the non-asymptotic superlinear convergence rate also holds for classical DFP, BFGS and SRI methods.
Jin and Mokhtari [17], Ye et al.
In this paper, we study quasi-Newton methods for saddle point problem ( Note that when the Hessian matrix of the objective function indefinite, the existing Broyden family update formulas and their convergence analysis cannot be applied directly. To overcome this issue, we propose a variant framework of random quasi-Newton methods for saddle point problems, which approximates the square of the Hessian matrix during the iteration. Our theoretical analysis characterizes the convergence rate by the gradient norm, rather than the weighted norm of gradient used in convex optimization [17 22 32 34 42]. We summarize the theoretical results for proposed algorithms in Table | The local convergence behaviors for all of the algorithms have two periods. The first period has kn iterations with a linear convergence rate O(11 - 1/x2)#o)) ).). The second one enjoys superlinear convergence, that is,
For general Broyden family methods, we have - 1/112 + 1)) 4(t-1)/22).
k(k -1)2) which is For BFGS method and SR1 method, we have 0(1 1/(d + 1)) 1)) condition-number-fee
Paper Organization In Section we state the notation and preliminaries of this paper. In Section 3
first propose random quasi-Newton methods for quadratic saddle point problem which enjoys local superlinear convergence. Then we extend it to solve general strongly-comvex-stronggg www-ssstroolloyoccceee saddle point problems. Section 5 we provide numerical experiments to validate our algorithms on popular machine learning models. All proofs, experiment details and extensions are deferred to appendix.
2 Notation and Preliminaries
We use ||||| to present spectral norm and Euclidean norm of matrix and vector respectively. We denote the standard basis for R2d by (ei,..., ea) and let be the identity matrix. The trace of a square matrix is denoted by tr(-). Given two positive definite matrices and H. we define their inner product as H) def GH)
We introduce the quantity TH (G) (H-1 G H) (H- G) - d, which is used to measure how well does matrix G approximate matrix H. If we further suppose G > H. then according to Rodomanov and Nesterov (32 it holds that G H - G H = (G)H.

---

Using the notation of problem ① we let yx E R2 where d def dN dy and denote the gradient and Hessian matrix of f at yx as g(z) E I2 and H(z) E Rdxd
We suppose the saddle point problem
I satisfies the following assumptions.
Assumption 2.1. The objective function f(x,y) y) is twice differentiable and has I--I.pschitz con- tinuous gradient and L2 Lipschitz continuous Hessian i.e., there exists constants L > 0 and L2 0 such that for any z xx y). [x'y'] E IR, we have [g) - g(z')l < L z'll
and [H(2) Hz'')l < L2| z'|1-
Assumption 2.2. The objective function y( is twice differentiable, j-strongly-convex in and j-strongly-conccve in y, i.c., there exists constant V fx, = - I for any yx.y) E Rd x Rdd
0 such that V yx,,)) ł ,Il and
The L-Lipschitz continuous of gradient means the spectral norm of Hessian matrix Hz)) can be upper bounded, that is [[H())]] s L.. Additionally, the condition number of the objective function is defined as def L.pp.
Quasi-Newton Methods for Saddle Point Problems
In this section, focus designing quasi-Newton methods for saddle point problem and showing their superlinear local convergence rate. The update rule of standard Newton's method can be written Z++ (H))) g(z) for solving problem (T. It has quadratic local convergence, but takes (dd) time complexity per iteration. For convex minimization, quasi-Newton methods including BFGS/SR1 355 8 37 and their variants (20 32
33 42 focus on approximating the Hessian which reduce the computational cost O (d2) for each round. However, all these algorithms and related convergence analysis are based on the assumption that the Hessian matrix is positive definite, which is not suitable for our saddle point problems since H(z) is indefinite.
We introduce the auxiliary matrix Hzz) be the square of Hessian H(z) def (H(z))² The following lemma shows that Hzz) is positive definite.
Lemma 3.1. Under Assumption 2.1 and 2.2 we have 1²1 H(z) I'r all e Rd.
Hence, we can reformulate the update Newton's 's method by
z_ - =z H-)) HH22))
Then it is natural to characterize the second-order information by estimating the auxiliary matrix H(z). rather than the indefinite Hessian H(z). If one can obtain symmetric positive definite matrix G e dxd as an estimator for Hzz), the update rule of 2 can be approximated by
z4 = G- HZ))g()).
The remainder of this section introduce strategies to construct G, resulting the quasi-Newtor methods for saddle point problem with local superlinear convergence. We should point out the implementation of iteration 33 is unnecessary construct Hessian matrix Hzz) explicitly, since we are only interested
the Hessian-vector product (Z))g(z) which can computed efficiently [27 35
3.1 The Broyden Family Updates
We first review some basic results for quasi-Newton methods in convex optimization. We introduce the Broyden family [25] Section 6.3] of quasi-Newton updates for approximating an positive definite matrix H. Rdxd by using the information of current estimator G E ddd

---

Definition 3.2. Suppose two positive definite matrices H E Rdxd and G Rddd satisfy H = G. For any u E R Gu Hu, we define Broyd, (royd,(G,y H, u)
def H. Otherwise, we define
G (G (G-H)uu Hu TG H) u ( Hju
Broyd, (G, H. u) def r)
(4)
G Huu T G + Guu H
Gu
Huu T H
+
Hu +1)
u Hu
HH
Hu
The different choices of parameter T for above formula contain several popular quasi- Newton updates:
For 7 = Hu/ (u Gu) E [0, 1], it corresponds to the BFGS update
BFGS(G, H, u) def G
Guu G
Huu" H u H
(5)
Gu
For r = 0, corresponds to the SRI update
(G- H ((G H)
SRI(G, H. def G
(6)
u (G H)u
Now introduce the update rule 20 32 by choosing
(0,1)
u~ Unif (8U-1).
The following lemma shows applying the update rule 4 with 7 leads to a new estimator with tighter error bound in the measure of on(-).
Lemma 3.3 (Modified from Lin et al. [20] Theorem 3.1]). Suppose two positive definite matrices I² H L and E Rdxd satisfy that < G. Ler G = Broyd (G. H, u)), where u cho-
sen random method as (7). then for any [0, 1], have E (G+) (1 1/(xx)) (G(G)
For specific Broyden family updates BFGS and SRI shown in and 66) the update can achieve better convergence result. Concretely, for BFGS method, first find L such that G 1 where L is an upper triangular matrix. This step can be implemented with (dd) complexity 20 Proposition 1]. We present the subroutine for factorizing G-1 in Algorithm and give its detailed implementation in the appendix. And we use the direction L u instead of u for the BFGS update. Applying the BFGS update rule 5 with formula follows.
L L.
7 we obtain condition-number. number-free result as
Lemma 3,4 (Modified from Lin et al. 200 Theorem 4.2]). Suppose two posiiivee definite matrices H. Raxd and G E Idddd satisfy H G. Les G. BFGS (G, H, "u,, where chosen by the random method in (7) and L is an upper triangular matrix such that E [TH (G+)) & (1 1/d) (G).
L Then we have
Remark 3.5. Note that the step of conducting G-1 - L LL requires QR decomposition of rank-1 1 change matrix which requires (26dl) flops [14, Section 12.5.1]. We do not recommend using this BFGS update strategy in practice when large.
The convergence of the SR1 update can be characterized by the measure TH Applying the SR1 update rule (6) with formula 77). the convergence also holds a cundition-numbedn free result.
(G) tr(G H).
Lemma 3.6 (Modified from Lin et al. (20, Theorem 4.1)). Suppose two positive definite matrices H Rdd and G E IRaxd satisfy H < G. Let G = SR1 (G, H.u), where u is chosen by the random method in 77) Then we have E [T (G+)) < (1 - 1/d) (G)
3.2 Algorithms for Quadratic Saddle Point Problems
We now solve simple quadratic saddle point problem that f(x,y) = fz Az bT (1) where [x; b
E Rd. A Rdxd symmetric and = d, + dy. We suppose A could be partitioned
z
Axx
Axy
where the sub-matrices Axx Rdo Axy E IRd Xd,, Ayx E xd, Ayr
as
A Ayx

---

Algorithm (ast-Chol(H, u)
1: Input: positive definite matrix H E Rdddd upper triangular matrix L E R direction E IRd
2: Using QR-decomposition to obtain [Q, R] =QR (L (T Huu HuuT/(u Hu)))
3: Calculate v = u/vu" Hu and [Q', R'] = QR((v R RT]²)
4: Output: L R'
Algorithm 2 Random- Random-Broyden Broyden-Quadrati
Input: Zg Fdd Go L and Ta E [0, 1]
2: for k = 0, 1,...
3: Zk+1
G Hg(Zz)
4: Randomly choose us from and update Gk+1 Broyd,, (Ga; H, ug)
5: end for
and Ay Rdy satisfy Axx = μI, Ayy 3 - and |||| - L. Using notations introduced in
Section we have yx, g(z) Az b, H def H(z) and H def
H A
We present the detailed procedure random quasi-Newer methods for quadratic saddle point problem by using the Broyden family update, BFGS update and SR1 update in Algorithm and respectively.
We define Å as the gradient norm zµ for convergence analysis, that is A def definition of 0 in this paper different from the measure used in convex optimization 20 32 but it also holds the similar property follows.
[g(zz)) The
Lemma 3.7. Assume we have тk and G₂ E Rddd such that H < G5 I 17s H. Hor Algorithm then we have dp+1 I (1 1/ms) dg-
The theorem states the assumptions of Lemma 3.7 always holds with T/E: x² 1, which means D converges to linearly.
Theorem 3.8. For all 2 0. Algorithu
4 hold that A s (1- )0 do and - G2 S x.
Lemma 3.7 also implies superlinear convergence can be obtained if there exists m which converges 3.4 and 3.6 we can show holds for proposed algorithms.
to 1. Applying Lemma 3.3
Theorem 3.9. Solving quadratic saddle point problem by the proposed quasi-Newton Algorithmss
for all k 2 0, have:
1. For the Broyden family method (Algorithm) 24. we have [16+1/AA /Ax S (1 1/(d2)))) dxo..
2. For the BFGS method (Algorithm we have [AR+1/AA Av] S (1-1/d) 1/d)* dx?..
3. For the SR1 method (Algorithm
have EE 1 Au (1 k1-k/dd)zz dz
Combining the results of Theorem 3.8 and 3.9 we achieve the two-stages convergence behavior, that is, the algorithm the global linear convergence and local superlinear convergence. We leave the formal description in appendix.
3.3
Algorithms for General Saddle Point Problems
In this section, we consider the general saddle point problem where f(x, y) [
satisfies Assump-
tion [2.] 2.2 We propose quasi-Newton methods for solving the problem with local superlinear convergence and (d time complexity for each iteration.
II later section, we will see the measure X methods for saddle point problems.
||gu| || is suitable to convergence analysis of quasi-Newter
5

---

Algorithm 3 Random-BFGS Quadratic
Algorithm 4 Random-SRI-Qun
1: Input: Zu E R Go = I -= 1-
1: Input: E RR Go I,²1
2: for k = 0, 1.......
K +1
3: 7x++1 = 7 F2 (gs)))
2: for k = 0, 1...,,KK K
4: Randomly choose ü, from
3: Zk+1 = 24 G Hg(z))
5: L un
4: Randomly choose uy from
6: G BFGS (Ge, H, ul)
7: L++1 Fast-Chol La,
5: GG+1 SR1 (G H.
8: end for
6: end for
3.3.1 Algorithms
The key idea of designing quasi-Newton methods for saddle point problems approximating the
auxiliary matrix H(z) def (H()))² to characterize the second-order information. Since the Hessian of f is Lipschitz continuous and bounded by Assumption 2.1 and 2.2 which means the auxiliary matrix operator Hz)) is also Lipschitz continuous.
Lemma 3.10. Under Assumption
2.1 and 2.2 we have (z) is -ips-hipshhtzz continuous.
Combining Lemma 3.1 and 3.10 we achieve the following properties of Hz),, which analogize the strongly self-concordance in convex optimization (32.
Lemma 3.11. Under Assumption 2.1 and 2.2 for all z, z, w E Rd, the auxiliary matrix operator H()) satisfies H(z) H(z') M z' [H(w). where M =2x2
||z z|1. Suppose the objective function f satisfies Assumption 2.1 and 2.2 then for all z,z' E Rd and M =2x² L2/ L. the auxiliary matrix operator H(.) holds that
Corollary 3.12. Let z. z' E Rd and
H(z) (1 Mr)
H(z)) (1 (2)
Different from the quadratic case, the auxiliary matrix Hzz)) is not fixed for general saddle point problem. Based on the smoothness of Hzz), apply Corollary 3.12 to generalize Lemma 3.13 as follows.
Lemma 3.13. Letz Rdd and G Rddd be a positive definite matrix such that H(z) 3 G N (z) for some 1) 2 In addition, define 244 E Rdd and ||z+ z||, then for all Rdd [0, and
M = 2x L2 L, we have
H(2+) 3 Broyd, ((2,), u) 3 (r)
where G def (1 G = H(Z+).
Lemma 3.13 implies is reasonable to have the algorithms using G = Broyd, (G H H Up) with G (1 + Gr and rı || 2x| Similarly, also achieve G by such Gy for specific BFGS and SRI update. Combining this with iteration (3), we propose several quasi-Newton methods for general soangllyyoonve--stoogyy-ooooo
saddle point problems. The 6 and for Broyden family, BFGS and SRI updates respectively.
details shown Algorithm
3.3.2 Convergence Analysis
Let us consider the convergence guarantee for algorithms proposed in Section 3.3.1 We introduce the following notations to simplify the presentation. We let {2x} be the sequence generated from Algorithm or 7 and denote
g
def
g(z)).
Fk
def
zell:
H.
def
H(z))
and Hg def ?
We still use gradient norm A def and AR+1, which is shown in Lemma
(Zz for analysis and establish the relationship between A
3.14

---

Algorithm 5 Rendom--rroyden-GGnend
1: Input: Zu E R., GD 2 H, Tы E [0, and M 2 0.
2: for = 0, ...
3: 2k+1
G T--HHgg H
4: Compute т = |z z and
= Gr
5: Randomly choose uy from and update G Broyd,, (Gk, H&41,
6: end for
Algorithm 6
Algorithm Random-SRI-Generll
1: Input: Zn E Rd
Go H, M 0.
Input: 2n E R. Go > H and M > 0
2: Lg = G1//2
-1/2
2: for k 0, L...
3: for k = 0..
Zt+1 = Zz G G.H.
4:
H
5: Tk = |z++1 Zull
4: тk || - Z
6:
G2 = (1+ Mr
5: GN = (1 Mr.)
7:
L = LL/VI+ Mrk
8:
Randomly choose ug from
6: Randomly choose uy from
9:
G BFGS HA k-1 Ug)
7: G SRI(G H up)
L++1 (ast-Chol(HHav H1 Lgs Lgu
11: end for
end for
Lemma 3.14. Using Algorithm 5 aand suppose we have Hi GR. mh HR. for some The 2 and let 3 = (2 then we have
A 1 1 Tpk
A B 3X and S R
Rodomanov and Nesterov [32 Lemma 4.3] derive a result similar to Lemma 3. 14 for minimizing
the strongly-convex function f(-) the different measure X²(-) def
V
Note that our algorithms are based the iteration rule Z Z G Hags- Compared with quasi-Newton methods for convex optimization, there exists an additional term H, between G and ge, which leads to the fact that the convergence analysis based on X (2x) is difficult. Fortunately, we find using gradient norm A directly makes the analysis achievable.
For further analysis, we also denote ak def OH, (G&) = (H (G)
Then we establish the linear convergence for the first period of iterations, which can be viewed as the extension of Theorem 3.8 Note that the following result holds for Algorithm 6 and 7 and it does not depend on the choice of u;:-
Theorem 3.15. Using Algorithm anddd 7 by Go L and M =2x² L, suppose the initial point Zo is sufficiently close to z such that MNo/1 < lnb/(4bx²)) with 1 < b < 5, then we
have A S (1-1)) 11/2bxx)) & do and H 1 G2 1 exp (2Σ pi) x2H; I H for all k 2 O, where def MAa/p.
We now analyze how changes after one iteration to show the local superlinear convergence for the Broyden family method (Algorithm 5) and the BFGS method (Algorithm 6). Recall that or is defined to measure how well does matrix G approximate Hę.
Lemma 3.16. Solving the general strongly-convex- sowpg///-ccoeeesttooogoooooooom strongly-coonave saddle point problem ① under Assumption and a.22 our quasi-Newtor algorithms and supposing the sequences Go G generated by the Algorithm 1inhhmmmaaaa and are given, then we have the following results for o for all k:
"The original notations of Rodomanov and Nesterov 32 is minimizing the strongly-convex function f(-),
avoid ambiguity, notations f(.) and y describe their work in this paper.
7

---

1. The random Broyden framiyy.family method (Algorithm 5
holds that
[o & (0-1//d22)) (1 Mr (ox + 2dMrr/(1 Mrr)))))
2. The random BFGS method (Algorithm 6 holds that
B [o S (1 1/d) (1 Mr&)2 (ax + 2dMr + Mrx)).
The analysis for the SRI method is based constructing T/ such that 7p, tr(G.= -r.Ge-H ()))))HH,)))) and the technical details are showed in appendix. Based on Lemma 3.16, one can show that our algorithms enjoy the local superlinear convergence for the general saddle point problems.
Theorem 3.17. Solving general saddle point problem under Assumption 2.7 and 2.2 by proposed random quasi-Newton methods (Algorithm and by Go = L and M 2x L2 L. we have the following results for all k >
1. For the random Broyden family method (Algorithm we have E [/R+1/Au] S (1 (1- 1/dx²))) 2dx².
54 if do satisfies that Mda <
In
2. For the random BFGS method (Algorithm 6). if do satisfies that Mho
In
we have
8(1+d)277
IE [AR+1/Au] (1 (1-1/d)* 2dx2.
3. For the random SRI method (Algorithm if Xn satisfies that MA
In2
we have
3(1-2dx")e"
E [At+1/AR] S (1 1/d)* 2dx
Finally, combining the results of Theorem 3.15 and 3.17 we can prove the algorithms achieve the two-stages convergence behaviors as follows.
Corollary 3.18. Solving the general saddle point problem (1 under Assumption 2.7 and 2.2 by our random quasi-Newton methods (Algorithm [|oaand with Go L and M 2xx L2/ L. if the initial point is sufficiently close to the saddle point such that M / I In 2/ (8x²), then with probability 5 for any 8 E (0, 1). we have the following results:
1. The random Broyden family method (Algorithm 5 holds that
A(R-1)
Ako S (1- (1- dxe
1
1
Ao
2
4x2
for all Ko = O (dv? in(zz/0)) and k 2 0.
2. The random BFGS/SR1 method (Algorithm 6
holds that
k)
Ako - (1- d d+1)
1
1
Ao
2
4x02
for all Ko = O (max {d, x2 (m(]n//6))))))) and 2 0.
4 Discussion
The relationship between our quasi-Newton methods (Algorithm 5 and 7 and existing first-order method for minimax problem similar to the one for minimization problem. For our BFGS and SR1 methods, the dependency x² only appears the first period of linear convergence, which matches the convergence rate of gradient descent ascent. As an analogy, minimizing strongly-conve function in the first period of linear convergence, which matches the convergence rate of gradient descent.
by quasi-Newton methods 200 32) has dependency
Our Newti- methods also can be extended for solving non-linear equations, and the two-stage convergence hehavior still hold. We provide the detailed discussion and the comparison with related work [19] 41 in Appendix F.
8

---

1
10
10
10
Ra5R1-9
10
RaSA1-Q
10-6
RubFcSvi-0
nubroSvi-O
10-10
RaBFGSK2 0 BG
10
BG
RafrGSv2-
10 10
RaBFGSy1-Q
RaSRI-9
10-14
10-15
10-14
2000
4000
6000
0
2000
4000
10000
20000
30000
(a) a9a (iteration)
(b) w8a (iteration)
(c) sidoO (iteration)
10-2
10-3
10
RaBFGGV1
EG
10-6
10-7
10
BaSRI-Q
10 10-10
RaBFOSy2
RaBRGSy1-Q
10-11
10-10
10-14
10-15
RaBFG9y1-0
RatrGS-2-0
10-14
0
10
20
30
50
100
150
2500
5000
7500
(d) a9a (time)
(e) w8a (time)
(f) sido0 (time)
Figure We demonstrate iteration numbers vs. llg(z) ll2 and CPU time (second) vs. llg(z))l ||l for AUC model on datasets "a9a" (d 126, 32561), "w8a" (d 303, 45546) and "sido"
(d = 4935, n 12678).
5 Numerical Experiments
In this section, we conduct the experiments on machine learning applications of AUC Maximization and adversarial debiasing to verify our theory. We refer Algorithm and | with parameter
Ta = H4-1/(( /u G as RaBFGSvI-O I-Q and SaBFGSv1-G; refer to Algorithm 3 6 and 7 as
RaBFGSv2-Q Q, RaSRI-Q, RaBFGSv2-G and RaSRI-G respectively. We compare these proposed algorithms with classical first-order method extragradient (EG) [18 38
5.1 AUC Maximization
15 aims to find the classifier w E R on the training set fa,, b where a, RT and by (+1,- 1). We denote n+ be the number of positive instances and p nt /n.
AUC maximization
The minimax formulation for AUC maximization can be written as
min max f(x, y) xERm+2 yER
def f(lxyy;,,
where x = [w; E 12+2 0 is the regularization parameter and fi is defined as
f(xxy;; bi. A)
|x|2 - p(1 p)y² + +((("aa a; - 0)² + 2(1 + y)w a, T6.=-1 + (1 >(((w =)² - 2(1 +yww TT
2
The objective function of AUC maximization is quadratic, hence we conduct the algorithms in Section 3.2 (Algorithm) 2 and 4 for this model. We set = 100/n and evaluate all algorithms on three wealdworld datasets "a9a". "w8a" and "sido0". The dimension of the problem is d m 3. The results of iteration numbers against [gg())]|2 2 and CPU time against [lg(z) || are presented in Figure These results show that our algorithms perform better than the EG method.
5.2 Adversarial Debiasing
44 can be used on fairness-aware machine learning issues. Give the training set {a., by, 02) where a; E IRd contains all input variables, E R is the output and e the input variable which want to protect and make it unbiased. Our experiments are based on the
Adversarial learning 22

---

10
10
10
10
10-3
RaShI-6
10 12
10-12
RaBFGSy1-G
10-32
RASRI-G
R
RaBF0Sv1-G
Rabresv1-G
10-15
10
BaBrCSu2-G
10-26
10000
20000
0
10000
20000
10000
20000
30000
(a) adults (iteration)
(b) law school (iteration)
(c) bank market (iteration)
10
10
10-6
10
10-3
10-12 12
10-12
RashI-C RaBPoSy1-G EG
RaSR1 G
R G
RaBFCSv1-G RaBFCSu2-G
10-15
FaBrGSWI-G
10-15
10
200
400
0
500
1000 1500
20000
40000
(d) adults (time)
(e) law school (iteration)
(f) bank market (time)
Figure 2: We demonstrate iteration numbers vs. llg(z))l2 and CPU time (second) vs. llg(z))l for adversarial debiasing model on datasets "adults" (d 123, n 32561), "law school" (d 380, 20427) and "bank market" (d = 3880, = 45211).
fairness-aware binary classification dataset "adult", "bank market" and "law school" 300, leading to b, E (+1,-1}, The model is formulated by the minimax problem
Σ (lia Bl2(a, x, c4, u)) + X X||x|12 ?8? XEB YER TI
min max
where 11, la are the logit functions: logit(a, b, c) log(1 exp(-baTe c)). We the parameters A A and 7 as 0.5, 10 and 10 respectively. The dimension of the problem is d = m + 1. Since the objective function non-quadratic, we conduct the proposed algorithms Section 3.3 (Algorithm
5 and 7 here. We use extragradient warm up to achieve the local condition for proposed algorithms. The results of iteration numbers against (lg(2)]l2 and CPU time against (lg(2))lz presented in Figure algorithm.
2 which indicate that our algorithms significantly outperform the baseline
6 Conclusion
In this work, we propose quasi-Newton methods for solving sronglyyconvex-ssoonnyy.oom point problems. We characterize the second-order information by approximating the square of Hessian matrix, which avoids the issue of dealing with the indefinite Hessian directly. We present the explicit local superlinear convergence rates for Broyden's family update and faster convergence rates for two specific methods: SR1 BFGS updates. However, our algorithms still require to compute the exact gradient and store the approximate Hessian by Odd) space complexity. In future work, is interesting to design the stochastic algorithms to further reduce the computational cost of iteration. It is also possible to design the limited-ment memory quasi-Newton methods for more scalable saddle point problems.
saddle
Acknowledgements
would like to thank the anonymous reviewer for pointing out the mistakes in our previous proof. We would also like to thank Tong Zhang and John C.S. Lui for giving useful suggestions. This work supported by National Natural Science Foundation of China (No. 62206058) and Shanghai Sailing
Program (22YF1402900)
10

---

References
[1] Tamer Bacsar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
[2] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton university press, 2009.
[3] Charles G. Broyden. Quasi-Newton methods and their application to function minimisation. Mathematics of Computation, 21(99):368-33) -81 1967.
[4] Charles G. Broyden. The convergence of a class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics, 6(1):76-90, 1970.
[5] Charles G. Broyden. The convergence of a class double-rank minimization algorithms: the new algorithm. IMA journal of applied mathematics, 6(3):222-231, 1970.
[6] Charles G. Broyden, J. Dennis, and Jorge J. Moré. On the local and superlinear convergence of quasi-Newton methods. IMA Journal of Applied Muthematics, 12(3):223-245, 1973.
[7] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR, 2018.
[8] William C. Davidon. Variable metric method for minimization. SIAM Journal on Optimization, 1(1):1-17, 1991. 1991.
[9] J. E. Dennis, Jr., and Jorge J. Moré. A characterization of superlinear convergence and its application to quasi-Newton methods. Mathematics of Computation, 28 28(12)):549 (600):59--50 1974.
[10] Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In JCML, 2017.
[11] John C. Duchi and Hongseok Namkoong, Variance- regularization with convex objectives. Journal of Machine Learning Research, 20(68):1 2019.
[12] Roger Fletcher and Micheal J.D. Powell. A rapidly convergent descent method for minimization. The Computer Journal, 6: 6:16--66, 1963.
[13] Rui Gao and Anton J. Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. arXiv preprint arXiv: /99, 2016.
[14] Gene Golub and Charles F. Van Loan. Matrix computations, 1996.
[15] James A. Hanley and Barbara J. McNeil. The meaning and use of the area under receiver operating characteristic (ROC) curve. Radiology, 143(1):29-366 1982.
[16] Kevin Huang, Junyu Zhang, and Shuzhong Zhang. Cubic regularized Newton method for saddle point models: global and local convergence analysis. arXiv preprint arXiv:2008. 09999, 2020.
[17] Qiujiang Jin and Aryan Mokhtari. Non asppootmi superlinear convergence of standard quasi- Newton methods. arXiv preprint arXiv:2003.13607 2020.
[18] G. M. Korpelevich. An extragradient method for finding saddle points and for other problems. Matecon, 12:747-756, 1976.
[19] Dachao Lin, Haishan Ye, and Zhihua Zhang. Explicit superlinear convergence rates of Broyden's 's methods in nonlinear equations. arXiv preprint arXiv:2 2021.
[20] Dachao Lin, Haishan Ye, and Zhihua Zhang. Explicit convergence rates of greedy and random quasi-Newton methods. arXiv preprint arXiv:2104.0876: 2021.
[21] Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. In COLT, 2020.
[22] Daniel Lowd and Christopher Meek. Adversarial learning. In KDD, 2005.

---

[23] Yurii Nesterov. Accelerating the cubic regularization of newton's 's method on convex problems. Mathematical Programming, 11((1):159-18) 2008.
[24] Yurii Nesterov and Laura Scrimali. Solving strongly monotone variational and quasi- vuritivariational inequalities. Discrete and Continuous Dynamical Systems, 31(4):1383-1399 2007.
[25] Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, New York, NY, USA, second edition, 2006.
[26] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. arXiv preprint: 180.. 02901, 2018.
[27] Barak A. Pearlmutter. Fast exact multiplication by the Hessian. Neural computation, 6(1): 147-160, 1994.
[28] L.D. Popov. A modification of the arrow- wrrwwhhrwicz method for search of saddle points. Mathe- matical Notes of the Academy of Sciences of the USSR, 28(5):845 8488888, 1980.
[29] Micheal J.D. Powell. On the convergence of the variable metric algorithm. IMA Journal of Applied Mathematics, 7(1):21-36, 1971.
[30] Tai Le Quy, Arjun Roy, Vasileios Iosifidis, and Eirini Ntoutsi. A survey on datasets for fairness-aware machine learning, 2021.
[31] R. Tymell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
[32] Anton Rodomanov and Yurii Nesterov. Greedy quasi-Newton methods with explicit superlinear convergence. SIAM Journal on Optimization, (1(1):785-81, 2021.
[33] Anton Rodomanov and Yurii Nesterov. New results on superlinear convergence of classical quasi-Newton methods. Journal of optimization theory and applications, 188(3):744-700 2021.
[34] Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi- Newton methods. Mathematical Programming, pages 1-32, 2021.
[35] Nicol N. Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural Computation, 14(7):1723, 2002.
[36] Soroosh Shafieezadeh-Abadel Peyman Mohajerin Esfahani. and Daniel Kuhn. Distributionally robust logistic regression. arXiv preprint arXiv:1509.09255 2015.
[37] David F. Shanno. Conditioning of quasi-Newton methods for function minimization. Mathe- matics of computation, 24(111):647-656, 1970.
[38] Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-252 1995.
[39] John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton university press, 2007.
[40] Yuanhao Wang and Jian Li. Improved algorithms for convex-concave minimax optimization. In NeurlPS, 2020.
[41] Haishan Ye, Dachao Lin, and Zhihua Zhang. Greedy and random Broyden's methods with explicit superlinear convergence rates in nonlinear equations. arXiv preprint arXiv:2110.08572, 2021.
[42] Haishan Ye, Dachao Lin, Zhihua Zhang, and Xiangyu Chang. Explicit superlinear convergence rates of the SRI algorithm. arXiv preprini urXiv:2105.0F1 07162, 2021.
[43] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online AUC maximization. NIPS, 2016.
[44] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In AIES, 2018.
12

---

[45] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the saddle point problems. arXiv preprint:1912.07481, 2019.
[46] Yuchen Zhang and Lin Xiao. Stochastic primal-dual coordinate method for regularized empirical risk minimization. Journal of Machine Learning Research, 18(1):2939-2988) 2017.
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 describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(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] See Section 2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A-D,
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either
supplemental material or as a URL)? [Yes] We present them in the supplemental material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] We present them in Section 3 and in Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix E.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 5 and Appendix E.
(b) Did you mention the license of the assets? [Yes] See Section and Appendix E, the data is public available.
(c) Did you include any new assets either in the supplemental material URL? [Yes] See Appendix E.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) 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 to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "wT4hpe7GSEd", "reviewer": "Reviewer_SLU5", "summary": "This paper adapts greedy quasi-Newton method to saddle point problems. The proposed algorithms are based on estimating the square of indefinite Hessian matrix and turn out to have local superlinear convergence.", "questions": "Since in the paper authors mentioned two stages convergence behavior, I hope this characteristic can be discussed in the section: experiments. ", "limitations": "First, this paper requires sufficient smoothness of a strongly-convex and strongly concave function $f$ and proposed algorithm requires the evaluation of squared Hessian, which results in computational complexity. Second, the rate of local super linear convergence is highly related to dimension $n$ which can be very large in practice. If $n$ is large, then the rate will be close to the one for local linear convergence.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well structured. It is stated clearly for the proposed algorithm that the key is the estimation of squared Hessian. I would like to see a more intensive discussion on how to store the approximate Hessian efficiently. Nevertheless, if all ingredients fit into the memory and are computable, the proposed algorithm is quite efficient, in theory and practice. From all experiments shown in this paper, the proposed algorithms work pretty well eventually. However, in section 5.2, it is better to address more clearly that the objective function satisfies all assumptions. ", "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": "h4m6BybQsgR", "reviewer": "Reviewer_MK9J", "summary": "The authors propose a modifications of well-known Quasi-Newton methods for solving strongly-convex-strongly-concave saddle-points problems with Lipschitz gradietns and Hessians. The key algorithmic novelty is in changing the matrix that is inverted. Unlike to Quasi-Newton methods for minimization problems, where the methods approximate the inverse of the Hessian, the proposed methods estimate the squared Hessian. This modification is important for the analysis of the methods.\n\nFollowing the analysis in the case of minimization [37, 38, 39, 24], the authors derive two-period local convergence results (one period with linear convergence and one period with superlinear convergence) for general random Broyden family with better rates for BFGS and SR1. These rates are similar to the ones known for minimization up to the replacement of $\\kappa$ (condition number) by $\\kappa^2$. The worsening in terms of $\\kappa$ is expected, since the methods use the inverse of the approximated square of the Hessian.", "questions": "1. How do the initial conditions from Theorem 3.17 relate to the ones known for the same methods in minimization? How do they relate to the ones from the concurent works [23] and [46]?\n2. Line 582: object --> objective\n3. Line 587: continuous --> continuity; object --> objective; \"that\" should be removed\n4. Line 626: should be $\\frac{\\beta}{M} \\leq \\frac{1}{4L}$. In fact, this is sufficient since in (56) factor $\\mu$ in front of $\\frac{\\beta}{2M}\\rho_k^2$ is missing.\n5. Inequality (63): how the last inequality is obtained? \n\n", "limitations": "All assumptions are properly formulated. There are no potential negative social impact, since the work is purely theoretical.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. **Novelty and significance.** The results are novel: there are only 2 papers that also propose Quasi-Newton methods for min-max problems (for nonlinear equations), but they consider a different setup and use different ideas. The topic is relevant to ML community. The obtained results are significant.\n2. **Clarity.** The results are presented in the clear way, the proofs are also detailed enough and easy to follow. \n\n## Weaknesses\n1. **Bad dependence on the condition number.** The derived results suffer from the squared dependence on the condition number $\\kappa$. Although I find the proposed approach of approximating the squared Hessian matrix interesting, it would be interesting to see some discussion about the possibility of avoiding such dependence.\n2. **Comparison with [46] and [23] is incomplete.** Although the authors discuss the results and assumptions from the concurent works [23, 46], the explicit comparison of rates is missing. I believe such a comparison of rates should be presented in the text. Moreover, in the experiments, it would be interesting to compare with the method from [23] as well: although in [46] it is shown that the method from [23] is inferior to the one from [46], it is shown on particular problems different from the one considered in this paper. Therefore, for completeness, it is important to compare the proposed methods with the one from [23] as well.", "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": "cFDdeIdfq3f", "reviewer": "Reviewer_WrbW", "summary": "In this paper, the authors focus on applying quasi-Newton methods to solve the strongly-convex-strongly-concave saddle point problems. They achieved the explicit local superlinear convergence rates of quasi-Newton methods of Broyden updates. They utilized the technique of estimating the square of the indefinite Hessian matrix instead of the Hessian matrix itself. They also reach the non-asymptotic convergence rate of BFGS method and SR1 method. The authors conduct several numerical experiments on different datasets and these empirical results are consistent with the theoretical results.", "questions": "The authors didn't mention the specific results for the DFP method. Is it because that the theoretical results of DPF is not as good as BFGS so there is no need to present the part for DFP?", "limitations": "The authors have presented the limitations of this paper in the final conclusion section.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper has the following strengths in terms of the originality, quality and clarity:\n\nOriginality: this paper provides the first explicit local superlinear convergence rates of quasi-Newton algorithms applied to the saddle point problems. This is the main and independent contribution of this paper.\n\nQuality: the authors provides detailed proof in the theoretical section and the consistent empirical results in the numerical experiments section. These empirical results show that the theoretical results are correct in practice.\n\nClarity: the paper is 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 one weakness in term of the significance:\n\nThis submission presented incremental results of the non-asymptotic superlinear convergence analysis of quasi-Newton methods applied to different problems with different backgrounds. All these proof ideas and techniques are based on the previous work and reference as the authors mentioned in the paper. The authors extend the current superlinear convergence results of quasi-Newton methods applied to the general convex optimization problems to the strongly-convex-strongly-concave saddle point problems. Although the theoretical proof is correct and the authors presented the consistent empirical results, this does not change the essence that this work is an incremental analysis based on the previous similar work. Hence in summary, although this submission is with high quality which improves our understanding of explicit superlinear convergence rates of quasi-Newton methods, it is not totally original and 100% independent. This is a submission with good quality but neither very impressive nor very significant enough.\n\nSome other minor weakness includes:\n\n1. The authors should use t as the time index instead of the k. Because k is very similar to the condition number notation $\\kappa$. This can lead to misunderstanding.\n\n2. The authors should use d as the notation of the dimension instead of the n. In the numerical experiment section the authors used d. n is mostly used as the number of functions in the main objective function.\n\n3. The authors should use some other upper-class constant such as $K$ or $C$ to denote the Hessian Lipchitz parameter instead of $L_2$. This notation is much more clear and consistent.", "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": "StIK-Tktcgi", "reviewer": "Reviewer_fZXn", "summary": "This paper proposes a randomized Broyden family updates for strongly-convex-strongly concave saddle point problems and show that the algorithm achieves a local superlinear convergence rate. The key idea is to update the square of the Hessian instead of the Hessian itself. Numerical experiments show that the proposed algorithm outperforms classical first-order methods. ", "questions": "Although the authors do discuss relevant work in the introduction, a related work section is missing from this paper, which makes it unclear which parts of this paper are novel and which parts are mostly based on previous results. Can the authors clarify the key technical difficulties in this paper apart from the need to deal with an indefinite Hessian?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The authors circumvent the issue of dealing with an indefinite Hessian, which is a nontrival obstacle for saddle point problems, by applying BFGS type updates to the square of the Hessian instead. I am not aware of previous work that have established similar guarantees for quasi-newton methods on saddle point problems, so the analysis presented in this paper can be of interest to the NeurIPS audience. \n\n- My main concern about this paper is the presentation.  In this current form the notations are very dense and often introduced without much motivation. Section 3.1 is particularly difficult to parse as the authors introduces a number of lemmas in previous papers without clearly laying out a purpose for these lemmas. I think the presentation would be greatly improved if the main results are introduced first, and then the necessary lemmas for proving the main results are presented with some motivation. \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