## Multiple Greedy Quasi-Newton Methods for Saddle Point Problems

1 st Minheng Xiao dept. Integrated System Engineering Ohio State University Columbus, USA minhengxiao@gmail.com

2 nd Shi Bo dept. Mathematics and Statistics Boston University Boston, USA shibo@bu.edu

3 rd Zhizhong Wu dept. Engineering UC Berkeley Berkeley, USA ecthelion.w@gmail.com

Abstract -This paper introduces the Multiple Greedy QuasiNewton (MGSR1-SP) method, a novel approach designed to solve strongly-convex-strongly-concave (SCSC) saddle point problems. Our method enhances the approximation of the square of the indefinite Hessian matrix inherent in these problems, significantly improving both the accuracy and efficiency through iterative greedy updates. We provide a thorough theoretical analysis of MGSR1-SP, demonstrating its linear-quadratic convergence properties. Numerical experiments conducted on AUC maximization and adversarial debiasing problems, compared with stateof-the-art algorithms, underscore our method's enhanced convergence rates and superior quality in inverse Hessian estimation. These results affirm the potential of MGSR1-SP to improve performance across a broad spectrum of machine learning applications where efficient and accurate Hessian approximations are crucial.

cubic regularized Newton (CRN) method, which achieves quadratic local convergence, requires the computation of the exact Hessian matrix and solving of cubic variational inequality sub-problems [25]. Other adaptations, like the Newton proximal extragradient [26, 27], the mirror-prox algorithm [28], and the second-order optimistic method [29], incorporate line searches for step size optimization. Conversely, methods such as [30] and [31] avoid such complexities by omitting line searches and following a more streamlined approach akin to the CRN method, balancing efficiency and effectiveness in various optimization settings.

Index Terms -component, formatting, style, styling, insert

## I. INTRODUCTION

The saddle point problem is a fundamental formulation in machine learning and optimization and naturally emerges in several applications including game theory [1, 2], robust optimization [3, 4], reinforcement learning [5, 6], AUC maximization [7, 8, 9], fairness-aware machine learning [8, 10], and generative adversarial networks (GANs) [11]. In this paper, we consider the following saddle point problem formulated as

$$\min _ { x \in \mathbb { R } ^ { n } \times } \max _ { y \in \mathbb { R } ^ { n } y } f ( x, y ), \quad \quad ( 1 ) \ \text{rates}$$

where f ( x y , ) is smooth, strongly-convex in x , and stronglyconcave in y . The objective is to find the saddle point ( x ∗ , y ∗ ) such that:

$$f ( x ^ { * }, y ) \leq f ( x ^ { * }, y ^ { * } ) \leq f ( x, y ^ { * } )$$

for all x ∈ R n x , y ∈ R n y .

Several first-order optimization techniques have been developed to solve saddle point problems with linear convergence rate of iteration complexity of O (1 /ϵ ) including the extragradient (EG) method [12, 13], the optimistic gradient descent ascent (OGDA) method [14, 15], the proximal point method [16], mirror-prox method [17], and dual extrapolation method [18]. Their stochastic extensions have also been studied in large-scale settings [19, 20, 21, 22, 23, 24].

Second-order methods enhance convergence in saddle point problems but often entail higher computational demands. The

Quasi-Newton methods, compared to Newton's method, approximate the Hessian matrix and its inverse instead of direct computation, which employ low-rank updates to significantly reduce the cost per iteration. Notable quasi-Newton formulas for minimization include the Broyden-Fletcher-GoldfarbShanno (BFGS) [32, 33, 34, 35], Davidon-Fletcher-Powell (DFP) [33, 36], and Powell-Symmetric-Broyden (PSB) [37]. Despite their success in minimization problems, quasi-Newton methods are less commonly applied to minimax problems. Other advancements in quasi-Newton methods have been notable. For instance, [38, 39, 40] introduced greedy and random variants that achieve non-asymptotic superlinear convergence. Following this, [41] reported improvements in convergence rates that are independent of condition numbers, a significant enhancement over traditional models. Furthermore, research by [42] has confirmed that non-asymptotic superlinear convergence also applies to the classical DFP, BFGS, and SR1 methods, solidifying their utility in complex optimization scenarios.

Despite their success in minimization problems, quasiNewton methods are less commonly applied to minimax problems. Some research has explored proximal quasi-Newton methods for monotone variational inequalities [43, 44, 45], targeting convex-concave minimax problems. However, these adaptations may lack stability, particularly in simple bilinear settings, as indicated by numerical experiments. Recent developments have introduced new quasi-Newton methods tailored for minimax problems [46, 47], but comprehensive convergence rates for these methods have not been well documented.

In this paper, we explore quasi-Newton methods tailored for strongly-convex-strongly-concave saddle point problems.

Specifically, we propose a multiple greedy quasi-Newton algorithm, which takes leverage of approximating the squared Hessian matrix with multiple greedy quasi-Newton updates per iteration. We rigorously establish a linear to quadratic convergence rate of our algorithm. Through numerical experiments on popular machine learning problems including AUC maximization and adversarial debiasing, we demonstrate the superior performance of our algorithm compared to state-ofthe-art algorithms. The paper is organised as follows:

Paper Organization In Section II, we clarify the notations and provide assumptions and preliminaries of this paper. In Section III, we introduce a framework for saddle point problems and propose our MGSR1-SP algorithm with theoretical convergence guarantee. In Section IV, we validate our algorithm on AUC maximization and Adverasial Debiasing tasks.

## II. NOTATION AND PRELIMINARIES

We use ∥ · ∥ to denote the spectral norm and the Euclidean norm of a matrix and a vector, respectively. The standard basis in R d is denoted by { e 1 , . . . , e d } . The identity matrix is represented as I , and the trace of any square matrix is represented by tr ( ) · . We use S d ++ to represent the set of positive definite matrices. For two positive definite matrices Q ∈ S d ++ and H ∈ S d ++ , their inner product is defined as ⟨ Q H , ⟩ = tr ( QH ) . We denote Q ⪰ H if G -H ⪰ 0 . Referring to the objective function in equation (1), let d = d x + d y represent the full dimension. The gradient g x ( k , y k ) and Hessian matrix ˜ ( H x k , y k ) of function f at the k -th iteration at ( x k , y k ) are denoted as g k ∈ R d and ˜ H k ∈ R d × d respectively, abbreviated for convenience. We also use H xx , H xy and H yy to denote the sub-matrices.

Suppose that the objective function in Eq. (1) satisfies the following assumptions:

Assumption 1. The objective function f ( x y , ) is twice differentiable with an L 1 -Lipschitz gradient and an L 2 -Lipschitz Hessian, i.e.,

$$\left \| g ( x, y ) - g ( x ^ { \prime }, y ^ { \prime } ) \right \| \leq L _ { 1 } \right \| \left [ \begin{matrix} x - x ^ { \prime } \\ y - y ^ { \prime } \end{matrix} \right ] \left \|$$

and

$$\| \tilde { \mathbf H } ( x, y ) - \tilde { \mathbf H } ( x ^ { \prime }, y ^ { \prime } ) \| \leq L _ { 2 } \Big \| \left [ \begin{matrix} x - x ^ { \prime } \\ y - y ^ { \prime } \end{matrix} \right ] \Big \|$$

for any [ x y ; ] ⊤ ∈ R d and [ x ′ ; y ′ ] ⊤ ∈ R d .

Assumption 2. The objective function f ( x y , ) is µ -stronglyconvex in x and µ -strongly-concave in y , i.e.,

$$\tilde { H } _ { x x } \succeq \mu I$$

and

$$\tilde { H } _ { y y } \preceq - \mu \mathbf I$$

for any [ x y ; ] ⊤ ∈ R d . Additionally, the condition number of the objective function is defined as κ = L /µ 1 .

Note that the Hessian matrix ˜ ( H x y , ) in saddle point problems in Eq. (1) is usually indefinite. However, the following lemma derived a crucial property of the squared Hessian matrix, providing a guarantee of positive definiteness.

Lemma 1. [[8]] Define H x y ( , ) = ˜ ( H x y , ) 2 . Under Assumption 1 and Assumption 2, we have µ 2 I ⪯ H x y ( , ) ⪯ L 2 1 I for any [ x y ; ] ⊤ ∈ R d .

## III. METHODOLOGY AND THEORETICAL ANALYSIS

In this section, we explore an innovative framework designed to address saddle point problems as described in Eq. (1). We then review the basic principles of quasi-Newton methods, with a focus on the greedy variant discussed in [38]. Following this, we introduce our MGSR1-SP algorithm, which is characterized by its established linear-quadratic convergence rate and its near independence from condition numbers.

## A. A Quasi-Newton Framework for Saddle Point Problems

The standard update formula for Newton's method is expressed as

$$\begin{bmatrix} x _ { k + 1 } \\ y _ { k + 1 } \end{bmatrix} = \begin{bmatrix} x _ { k } \\ y _ { k } \end{bmatrix} - \tilde { \mathbf H } _ { k } ^ { - 1 } g _ { k },$$

which exhibits quadratic local convergence. However, this method incurs a computational complexity of O ( d 3 ) per iteration for the inverse Hessian matrix. In the realm of convex minimization, quasi-Newton methods such as BFGS, SR1, and their variations focus on approximating the Hessian matrix to reduce computational demands to O ( d 2 ) per iteration. Nonetheless, these methods presuppose a positive definite Hessian, which is unsuitable for saddle point problems as described in Eq. (1) due to the inherent indefiniteness of ˜ ( H x y , ) . To address this challenge, [9] reformulated the Newton's method as

$$\begin{bmatrix} x _ { k + 1 } \\ y _ { k + 1 } \end{bmatrix} & = \begin{bmatrix} x _ { k } \\ y _ { k } \end{bmatrix} - [ ( \tilde { \mathbf H } _ { k } ) ^ { 2 } ] ^ { - 1 } \tilde { \mathbf H } _ { k } g _ { k } \\ & = \begin{bmatrix} x _ { k } \\ y _ { k } \end{bmatrix} - \mathbf H _ { k } ^ { - 1 } \tilde { \mathbf H } _ { k } g _ { k }.$$

where H k = ˜ H 2 k is the auxiliary matrix defined in Lemma 1, which is guaranteed to be positive definite. Consequently, the update rule for Newton's method can be reformulated as

$$\begin{bmatrix} x _ { k + 1 } \\ y _ { k + 1 } \end{bmatrix} = \begin{bmatrix} x _ { k } \\ y _ { k } \end{bmatrix} - Q _ { k } ^ { - 1 } \tilde { \mathbf H } _ { k } g _ { k },$$

where Q -1 k ∈ S d ++ is an approximated inverse matrix of H -1 k . We will introduce the techniques to construct Q k and its inverse in the next section. Note that the update rule (3) does not necessarily require the explicit construction of Hessian matrix, which can be computed efficiently through HessianVector Product (HVP) [48, 49].

## B. Greedy Quasi-Newton Methods

̸

Quasi-Newton methods are developed to circumvent some of the computational inefficiencies associated with the classical Newton's method [9, 32, 35, 38, 40, 41, 42, 50, 51, 52, 53, 54]. Among these, the Broyden family updates, particularly the Broyden-Fletcher-Goldfarb-Shanno (BFGS) formula, has become the most celebrated, widely cited in many literature. Given two symmetric positive definite matrices H Q , ∈ S d ++ and a vector u ∈ R d , satisfying that Q ⪰ H and Qu = Au , the Broyden family update is given by

$$\text{Broyd} _ { \tau } ( Q, H, u ) = \tau \text{DFP} ( Q, H, u ) \\ + ( 1 - \tau ) \text{SR} 1 ( Q, H, u ), \quad \text{where}$$

which is proved to be a convex combination [38]. The SR1 update refines the Hessian approximation by

$$S R 1 ( Q, H, u ) = Q - \frac { ( Q - H ) u u ^ { \top } ( Q - H ) } { u ^ { \top } ( Q - H ) u },$$

which leverages a rank-one modification to adjust Q based on the discrepancy between Q and H . On the other hand, the DFP update incorporates both current and previous curvature information into the approximation:

$$\text{DFP} ( Q, H, u ) = Q - & \frac { H u u ^ { \top } Q + Q u u ^ { \top } H } { u ^ { \top } H u } \quad \begin{pmatrix} \xi \\ 1 \\ \gamma \\ + \left ( 1 + \frac { u ^ { \top } Q u } { u ^ { \top } H u } \right ) \frac { H u u ^ { \top } H } { u ^ { \top } H u } \end{pmatrix} \xi \\ \text{--} \quad \begin{pmatrix} \xi \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamphi \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamga \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamvar \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamgo \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamlu \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamve \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamtype \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\
 \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamria \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamtag \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamj \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamse \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\
 \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\
 \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gam-------- \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamjs \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamja \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gam{ \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gam
 \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \gamma \\ \$$

The parameter τ ∈ [0 , 1] determines the specific type of QuasiNewton update applied. Specifically, setting τ = u ⊤ Hu u ⊤ Qu leads to the well-known Broyden-Fletcher-Goldfarb-Shanno (BFGS) update formulated as

$$\text{BFGS} ( Q, H, u ) = Q - \frac { Q u u ^ { \top } Q } { u ^ { \top } Q u } + \frac { H u u ^ { \top } H } { u ^ { \top } H u }.$$

Greedy Quasi-Newton methods were proposed to achieve better convergence rates compared to classical Quasi-Newton methods, with a contraction factor that depends on the square of the iteration counter [38]. Specifically, for a given target matrix H ∈ S d ++ and an approximator Q ⪰ H , the greedily selected vector u is determined as follows:

$$u _ { H } ( Q ) = \underset { u \in \{ e _ { 1 }, \dots, e _ { n } \} } { \arg \max } \frac { u ^ { \top } Q u } { u ^ { \top } H u },$$

where e i represents the basis vector. Define the greedy Broyden family update as follows:

$$\ g { \text{proy} } { d _ { \tau } ( Q, H ) } \stackrel { \text{def} } { = } \text{proy} { d _ { \tau } ( Q, H, u _ { H } ( Q ) ) }.$$

Specifically, if τ = 0 , the update is greedy SR1 update defined as

$$\ g S R { 1 } ( Q, H ) \stackrel { \text{def} } { = } \ g S R { 1 } ( Q, H, u _ { H } ( Q ) ). \quad ( 4 ) \stackrel { [ x _ { k } ; Y } { \dots \dots }.$$

The following lemma demonstrates that the greedy SR1 update reduces the rank of Q -H at each iteration. Therefore, with at most d iterations, the gSR1 update will accurately recover the Hessian matrix.

Theorem 1 ([38], Theorem 3.5) . Suppose that for each k ≥ 0 , we choose u k = u H ( Q k ) and τ = 0 , then Q k = H for some 0 ≤ k ≤ d .

In quadratic optimization, the Hessian matrix remains constant, and with each iteration, the approximated Hessian matrix converges towards the true Hessian, as demonstrated by the previous lemma. For more general problems, we define the multiple gBroyd n τ as a series of nested gBroyd τ updates [55], targeting the same Hessian matrix H , such that

$$Q _ { i + 1 } \leftarrow g \text{Broy} d _ { \tau } ^ { n } ( Q _ { i }, \text{H} ), \ \ i = 0, \dots, n - 1,$$

where n is a non-negative integer representing the number of rounds of greedy Broyden family updates performed in each iteration. Specifically, for the multiple greedy SR1 updates denoted as gSR1 n , within each iteration, the updates occur as follows:

$$Q _ { i + 1 } \leftarrow g S R 1 ( Q, \mathbf H ), \ \ i = 0, \dots, n - 1, \quad ( 5 )$$

- C. MGSR1-SP Algorithm and Convergence Analysis

In this section, we introduce the Multiple Greedy Rank1 (MGSR1-SP) algorithm for solving Saddle Point Problems satisfying Assumption 1 and Assumption 2, which is outlined in Algorithm 1 with established convergence guarantee. The MGSR1-SP algorithm builds upon the framework in Section III-A and adopts the multiple greedy SR1 updates specified in Eq. (5).

## Algorithm 1 MGSR1-SP

- 1: Initialization: z 0 , Q 0 , stepsize α M , , and n ≥ 0 .
- 2: for k in 0 , . . . , N do
- 3: Compute g k
- 4: Update z k +1 ← z k -α · Q -1 k ˜ H g k k (HVP)
- 5: Perform gSR1 n updates: ˜ Q k = gSR1 n ( Q k , H k ) .
- 6: Compute r k = ∥[ ∥ ∥ ∥ x k +1 -x k y k +1 -y k ]∥ ∥ ∥ ∥
- 7: Correct ˜ Q k +1 ← (1 + Mr k ) ˜ Q k
- 8: Compute Q k +1 = gSR1 ( ˜ Q k +1 , H k +1 ))
- 9: end for

Lemma 2 (Modified from [38]) . If, for some η ≥ 1 , and two positive definite matrix H Q , ∈ S d ++ , we have

$$\mathbf H \preceq \mathbf Q \preceq \eta \mathbf H,$$

then using greedy SR1 update (4) , we also have

$$\mathbf H \preceq g S R l ( \mathbf Q, \mathbf H ) \preceq \eta \mathbf H.$$

Lemma 3 (Modified from [8]) . Let [ x k ; y k ] ⊤ , [ x k +1 ; y k +1 ] ⊤ ∈ R d with squared Hessian matrix H k , H k +1 ∈ S d ++ defined in Lemma 1. For some η ≥ 1 and let Q k ∈ S d ++ be a positive definite matrix such that

$$\mathbf H _ { k } \preceq Q _ { k } \preceq \eta \mathbf H _ { k },$$

we have

$$\mathbf H _ { k + 1 } \preceq g S R l ( \tilde { \mathbf Q } _ { k + 1 }, \mathbf H _ { k + 1 } ) \preceq ( 1 + M r _ { k } ) ^ { 2 } \eta \mathbf H _ { k + 1 }$$

$$& \text{where } \tilde { \mathbf Q } _ { k + 1 } \, = \, ( 1 + M r _ { k } ) \mathbf Q _ { k }, \, r _ { k } \, = \, \left \| \begin{bmatrix} x _ { k + 1 } - x _ { k } \\ y _ { k + 1 } - y _ { k } \end{bmatrix} \right \| \ a n d \quad \begin{smallmatrix} \, \frac { 1 0 ^ { - 6 } } { 1 0 ^ { - 6 } } \Big | _ { - } \\ \, \swarrow \cdot \quad \, \cdot \cdot \cdot \end{smallmatrix} \Big.$$

Given upon this, define the convergence measure as

$$\lambda _ { k } = \lambda ( x _ { k }, y _ { k } ) = \| g ( x _ { k }, y _ { k } ) \| _ { 2 }, \text{ \quad \ \ } ( 6 )$$

we establish a linear to quadratic convergence rate for our MGSR1-SP algorithm in the following theorem:

Theorem 2. Using Algorithm 1, suppose we have H k ⪯ Q k ⪯ η k H k for some η k ≥ 1 , and let β = L 2 2 µ 2 , then we have

$$\lambda _ { k + 1 } \leq \left ( 1 - \frac { 1 } { \eta _ { k } } \right ) \lambda _ { k } + \beta \lambda _ { k } ^ { 2 }.$$

Proof Sketch. Suppose H k ⪯ Q k ⪯ η k H k holds, with Lemma 2, the multiple greedy SR1 update also satisfies H k ⪯ gSR1 n ( Q k , H k ) ⪯ η H k , hence, following Lemma 3, we have H k +1 ⪯ Q k +1 ⪯ (1+ Mr k ) 2 η k H k +1 = η k +1 H k +1 . The rest follows Lemma 3.14 in [8].

## IV. NUMERICAL EXPERIMENTS

In this section, we demonstrate the efficiency of our algorithm using two popular machine learning tasks: AUC maximization and adversarial debiasing. The experiments are conducted on a Macbook Air with M2 chip.

## A. AUC Maximization

In machine learning, the Area Under the ROC Curve (AUC) is a key metric that evaluates classifier performance in binary classification, particularly useful with imbalanced data. The problem can be formulated as follows:

$$f ( { \mathbf x }, { \mathbf y } ) \coloneqq \frac { 1 } { m } \sum _ { i = 1 } ^ { m } f _ { i } ( { \mathbf x }, { \mathbf y } ) + \frac { \lambda } { 2 } \| { \mathbf x } \| ^ { 2 } - p ( 1 - p ) y ^ { 2 },$$

where x = [ w ; u v ; ] ⊤ , λ is the regularization parameter and p denotes the proportion of positive instances in the dataset. The function f i ( x , y ) is defined as:

$$f _ { i } ( { \mathbf x }, y ) = & ( 1 - p ) \left ( ( { \mathbf w } ^ { \top } { \mathbf a } _ { j } - u ) ^ { 2 } - 2 ( 1 + y ) { \mathbf w } ^ { \top } { \mathbf a } _ { j } ) { \mathbf I } _ { b _ { j } = 1 } \\ & + p \left ( ( { \mathbf w } ^ { \top } { \mathbf a } _ { j } - v ) ^ { 2 } + 2 ( 1 + y ) { \mathbf w } ^ { \top } { \mathbf a } _ { j } ) { \mathbf I } _ { b _ { j } = - 1 },$$

where a i ∈ R n x -2 are features and b i ∈ { +1 , - } 1 is the label.

## B. Adversarial Debiasing

Adversarial debiasing is a prominent method used to enhance equity in AI by integrating adversarial techniques to mitigate biases within machine learning algorithms. Given a dataset { a i , b i , c i } m i =1 , where a i represents input variables, b i ∈ R is the output, and c i ∈ R is the protected variable, the objective is to reduce bias, which can be formulated as:

$$\dot { \ } f ( { \mathbf x }, y ) = \frac { 1 } { m } \sum _ { i = 1 } ^ { m } f _ { i } ( { \mathbf x }, y ) + \lambda \| { \mathbf x } \| ^ { 2 } - \gamma y ^ { 2 },$$

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00241v2-figure-6d1933d5-f482-4068-9153-e3d129ca5571.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00241v2-figure-9ea15cd6-6d07-43ce-85c7-a8b4ffb7cf93.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00241v2-figure-f7391b7a-caae-4adf-9b2a-66eb58121238.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00241v2-figure-9f351eda-4ba9-4fb1-9bef-f8eeccdecdba.jpg)

Fig. 1. Numerical results for AUC Maximization task. The y-axis denotes the gradient norm ∥∇ f ( x , y ) ∥ 2 and x-axis denotes the number of iterations. Top two figures compares Extragradient, RandomSR1 and MGSR1-SP('gSR1') with 20 rounds update on 'a9a' and 'w8a' dataset. Bottom two figures compare MGSR1-SP('gSR1') with different number of updates per iteration.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00241v2-figure-b49d74a1-65ee-424e-824f-712aa41ca5f4.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00241v2-figure-9f84e437-90fc-40ed-9c74-aebc8ec5f123.jpg)

(a) adult, #iter

(b) law, #iter

Fig. 2. Numerical results for Adversarial Debiasing. The y-axis denotes the gradient norm ∥∇ f ( x , y ) ∥ 2 and x-axis denotes the number of iterations. Top two figures compares Extragradient, RandomSR1 and MGSR1-SP('gSR1') with 20 rounds update on 'a9a' and 'w8a' dataset. Bottom two figures compare MGSR1-SP('gSR1') with different number of updates per iteration.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00241v2-figure-5f5f7b50-dcbe-4dff-8eb7-44ea21400e41.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00241v2-figure-19d8a696-2c1f-4fc5-9921-d00f683cbdbc.jpg)

where λ, γ are regularization parameters. Function f i ( x , y ) is defined as

$$f _ { i } ( { \mathbf x }, y ) = & \log \left ( 1 + \exp \left ( - \, b _ { j } ( { \mathbf a } _ { j } ) ^ { \top } { \mathbf x } \right ) \right ) \\ & - \beta \log \left ( 1 + \exp \left ( - \, c _ { j } ( { \mathbf a } _ { j } ) ^ { \top } { \mathbf x } y \right ) \right ),$$

with β also serving as a regularization parameter.

## C. Analysis

We evaluated the performance of our MGSR1-SP algorithm against two baselines: Random SR1, where vectors u ∈ R d are drawn from a normal distribution N (0 , 1) , and the ExtraGradient algorithm for saddle point problems.

For AUC maximization, the experiments were conducted on the 'a9a' dataset ( n x = 125 , n y = 1 , N = 32651 ) and the 'w8a' dataset ( n x = 302 , n y = 1 , N = 45546 ). The results are shown in Figure 1. Notably, the Hessian AUC maximization is invariant ( L 2 = 0 ), indicating a linear convergence rate 2. Our MGSR1-SP algorithm demonstrated a faster convergence rate compared to the ExtraGradient algorithm. Moreover, it offered more stable Hessian approximations than the random SR1 update, particularly as the number of update rounds increased.

For adversarial debiasing, the experiments were conducted using the 'adult' dataset ( n x = 122 , n y = 1 , N = 32651 ) and the 'law school' dataset ( n x = 379 , n y = 1 , N = 20427 ). The results, shown in Figure 2, indicated that our algorithm achieved a linear-quadratic convergence rate, supporting Theorem 2. Our method outperformed both ExtraGradient and Random SR1 in terms of iterations required, with significant performance improvements as updates increased.

## V. CONCLUSION

In this paper, we introduce the Multiple Greedy QuasiNewton (MGSR1-SP) method, a novel approach designed to solve strongly-convex-strongly-concave (SCSC) saddle point problems. This algorithm approximates the square of the indefinite Hessian matrix, enhancing accuracy and efficiency through a series of iterative, enhanced quasi-Newton updates. Our comprehensive convergence analysis rigorously establishes the theoretical results of the MGSR1-SP algorithm, demonstrating its linear-quadratic convergence rates. Furthermore, we conducted extensive empirical validations against state-of-the-art optimization methods, including the ExtraGradient and Random SR1 algorithms, on two popular machine learning applications: AUC maximization and adversarial debiasing. The results clearly show that our method not only converges faster but also provides a more accurate estimation of the Hessian inverse, leading to more stable and reliable optimization outcomes.

For future work, several promising directions can be explored. These include adapting the MGSR1-SP framework to stochastic settings. Additionally, the development of limited memory quasi-Newton methods could make our approach feasible for large-scale problems, where computational resources and memory usage are significant constraints. Another area of potential exploration is the integration of adaptive step-size selection mechanisms to enhance effectiveness. Lastly, extending our method to tackle non-convex saddle point problems with appropriate regularization could broaden its applicability to a wider array of problems in machine learning and beyond.

## VI. ACKNOWLEDGMENT

The first paragraph of the conclusion section in this manuscript was polished using ChatGPT to enhance clarity and readability. The authors take full responsibility for the content of this manuscript, including this AI-assisted revision.

## REFERENCES

- [1] Ding-Zhu Du and Panos M Pardalos. Minimax and applications , volume 4. Springer Science &amp; Business Media, 1995.
- [2] Biagio Ricceri and Stephen Simons. Minimax theory and applications , volume 26. Springer Science &amp; Business Media, 2013.
- [3] Sven Leyffer, Matt Menickelly, Todd Munson, Charlie Vanaret, and Stefan M Wild. A survey of nonlinear robust optimization. INFOR: Information Systems and Operational Research , 58(2):342-373, 2020.
- [4] Virginie Gabrel, C´ ecile Murat, and Aur´ elie Thiele. Recent advances in robust optimization: An overview. European journal of operational research , 235(3):471-483, 2014.
- [5] Mohammad Gheshlaghi Azar, Ian Osband, and R´ emi Munos. Minimax regret bounds for reinforcement learning. In International conference on machine learning , pages 263-272. PMLR, 2017.
- [6] Alekh Agarwal, Sham Kakade, and Lin F Yang. Modelbased reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory , pages 67-83. PMLR, 2020.
- [7] Zhenhuan Yang, Yan Lok Ko, Kush R Varshney, and Yiming Ying. Minimax auc fairness: Efficient algorithm with provable convergence. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, pages 11909-11917, 2023.
- [8] Chengchang Liu and Luo Luo. Quasi-newton methods for saddle point problems and beyond. arXiv preprint arXiv:2111.02708 , 2021.
- [9] Chengchang Liu and Luo Luo. Quasi-newton methods for saddle point problems. Advances in Neural Information Processing Systems , 35:3975-3987, 2022.
- [10] Yulu Jin and Lifeng Lai. Fairness-aware regression robust to adversarial attacks. IEEE Transactions on Signal Processing , 2023.
- [11] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM , 63(11):139-144, 2020.
- [12] GM Korpelevich. An extragradient method for finding saddle points and for other problems, ekonomika i matematicheskie metody, 12 (1976), 747-756. Search in .
- [13] 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.
- [14] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv:1711.00141 , 2017.
- [15] Leonid Denisovich Popov. A modification of the arrowhurwitz method of search for saddle points. Mat. Zametki , 28(5):777-784, 1980.
- [16] R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization , 14(5):877-898, 1976.
- [17] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirrorprox algorithm. Stochastic Systems , 1(1):17-58, 2011.
- [18] Yurii Nesterov and Laura Scrimali. Solving strongly monotone variational and quasi-variational inequalities. 2006.
- [19] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory , pages 778-816. PMLR, 2022.
- [20] Tatjana Chavdarova, Gauthier Gidel, Franc ¸ois Fleuret, and Simon Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. Advances in Neural Information Processing Systems , 32, 2019.
- [21] Luo Luo, Cheng Chen, Yujun Li, Guangzeng Xie, and Zhihua Zhang. A stochastic proximal point algorithm for saddle-point problems. arXiv preprint arXiv:1909.06946 , 2019.
- [22] Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang. Near optimal stochastic algorithms for finite-sum unbalanced convex-concave minimax optimization. arXiv preprint arXiv:2106.01761 , 2021.
- [23] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle-point problems. Advances in Neural Information Processing Systems , 29, 2016.
- [24] Vladislav Tominin, Yaroslav Tominin, Ekaterina Borodich, Dmitry Kovalev, Alexander Gasnikov, and Pavel Dvurechensky. On accelerated methods for saddle-point problems with composite structure. arXiv preprint arXiv:2103.09344 , 2021.
- [25] 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(2):60, 2022.
- [26] Max LN Gonc ¸alves, Jefferson G Melo, and Renato DC Monteiro. On the iteration-complexity of a non-euclidean hybrid proximal extragradient framework and of a proximal admm. Optimization , 69(4):847-873, 2020.
- [27] Mauricio Romero Sicre. On the complexity of a hybrid proximal extragradient projective method for solving monotone inclusion problems. Computational Optimization and Applications , 76(3):991-1019, 2020.
- [28] Brian Bullins and Kevin A Lai. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM Journal on Optimization , 32(3):2208-2229, 2022.
- [29] Ruichen Jiang and Aryan Mokhtari. Generalized optimistic methods for convex-concave saddle point problems. arXiv preprint arXiv:2202.09674 , 2022.
- [30] Deeksha Adil, Brian Bullins, Arun Jambulapati, and
- Sushant Sachdeva. Optimal methods for higher-order smooth monotone variational inequalities. arXiv preprint arXiv:2205.06167 , 2022.
- [31] Tianyi Lin and Michael I Jordan. Perseus: A simple and optimal high-order method for variational inequalities. Mathematical Programming , pages 1-42, 2024.
- [32] Charles George Broyden. The convergence of a class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics , 6(1): 76-90, 1970.
- [33] Roger Fletcher. A new approach to variable metric algorithms. The computer journal , 13(3):317-322, 1970.
- [34] Donald Goldfarb. A family of variable-metric methods derived by variational means. Mathematics of computation , 24(109):23-26, 1970.
- [35] David F Shanno. Conditioning of quasi-newton methods for function minimization. Mathematics of computation , 24(111):647-656, 1970.
- [36] Roger Fletcher and Michael JD Powell. A rapidly convergent descent method for minimization. The computer journal , 6(2):163-168, 1963.
- [37] Michael JD Powell. A new algorithm for unconstrained optimization. In Nonlinear programming , pages 31-65. Elsevier, 1970.
- [38] Anton Rodomanov and Yurii Nesterov. Greedy quasinewton methods with explicit superlinear convergence. SIAM Journal on Optimization , 31(1):785-811, 2021.
- [39] Anton Rodomanov and Yurii Nesterov. New results on superlinear convergence of classical quasi-newton methods. Journal of optimization theory and applications , 188:744-769, 2021.
- [40] Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi-newton methods. Mathematical Programming , pages 1-32, 2022.
- [41] Dachao Lin, Haishan Ye, and Zhihua Zhang. Explicit convergence rates of greedy and random quasi-newton methods. Journal of Machine Learning Research , 23 (162):1-40, 2022.
- [42] Qiujiang Jin and Aryan Mokhtari. Non-asymptotic superlinear convergence of standard quasi-newton methods. Mathematical Programming , 200(1):425-473, 2023.
- [43] James V Burke and Maijian Qian. On the superlinear convergence of the variable metric proximal point algorithm using broyden and bfgs matrix secant updating. Mathematical Programming , 88:157-181, 2000.
- [44] James V Burke and Maijian Qian. A variable metric proximal point algorithm for monotone operators. SIAM Journal on Control and Optimization , 37(2):353-375, 1999.
- [45] Xiaojun Chen and Masao Fukushima. Proximal quasinewton methods for nondifferentiable convex optimization. Mathematical Programming , 85:313-334, 1999.
- [46] Fatemeh Abdi and Fatemeh Shakeri. A globally convergent bfgs method for pseudo-monotone variational inequality problems. Optimization Methods and Software , 34(1):25-36, 2019.
- [47] Montacer Essid, Esteban G Tabak, and Giulio Trigila. An implicit gradient-descent procedure for minimax problems. Mathematical Methods of Operations Research , 97(1):57-89, 2023.
- [48] Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation , 6(1):147-160, 1994.
- [49] Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation , 14(7):1723-1738, 2002.
- [50] Charles G Broyden. Quasi-newton methods and their application to function minimisation. Mathematics of Computation , 21(99):368-381, 1967.
- [51] Charles George Broyden, John E Dennis Jr, and Jorge J Mor´ e. On the local and superlinear convergence of quasinewton methods. IMA Journal of Applied Mathematics , 12(3):223-245, 1973.
- [52] William C Davidon. Variable metric method for minimization. SIAM Journal on optimization , 1(1):1-17, 1991.
- [53] Ching-pei Lee, Cong Han Lim, and Stephen J Wright. A distributed quasi-newton algorithm for empirical risk minimization with nonsmooth regularization. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery &amp; data mining , pages 16461655, 2018.
- [54] Haishan Ye, Dachao Lin, Zhihua Zhang, and Xiangyu Chang. Explicit superlinear convergence rates of the sr1 algorithm. arXiv preprint arXiv:2105.07162 , 2021.
- [55] Yubo Du and Keyou You. Distributed adaptive greedy quasi-newton methods with explicit non-asymptotic convergence bounds. Automatica , 165:111629, 2024.
Minheng Xiao Shi Bo Zhizhong Wu
Multiple Greedy Quasi-Newton Methods for Saddle Point Problems
This paper introduces the Multiple Greedy Quasi-Newton (MGSR1-SP) method, a
novel approach to solving strongly-convex-strongly-concave (SCSC) saddle point
problems. Our method enhances the approximation of the squared indefinite
Hessian matrix inherent in these problems, significantly improving both
stability and efficiency through iterative greedy updates. We provide a
thorough theoretical analysis of MGSR1-SP, demonstrating its linear-quadratic
convergence rate. Numerical experiments conducted on AUC maximization and
adversarial debiasing problems, compared with state-of-the-art algorithms,
underscore our method's enhanced convergence rate. These results affirm the
potential of MGSR1-SP to improve performance across a broad spectrum of machine
learning applications where efficient and accurate Hessian approximations are
crucial.