Second-Order Min-Max Optimization with Lazy Hessians

## Abstract

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

## 1 Introduction

We consider the following minimax optimization problem:

$$ $\displaystyle\min_{{\bm{x}}\in\mathbb{R}^{d_{x}}}\max_{{\bm{y}}\in\mathbb{R}^{ d_{y}}}f({\bm{x}},{\bm{y}}),$ (1) $$

where we suppose $f$ is (strongly-)convex in ${\bm{x}}$ and (strongly-)concave in ${\bm{y}}$.
This setting covers many useful applications, including functionally constrained optimization [], game theory [], robust optimization [], fairness-aware machine learning [], reinforcement learning [, , , ], decentralized optimization [, ], AUC maximization [, , ].

First-order methods are widely studied for this problem. Classical algorithms include ExtraGradient (EG) [, ], Optimistic Gradient Descent Ascent (OGDA) [, , ], Hybrid Proximal Extragradient (HPE) [], and Dual Extrapolation (DE) [, ].
When the gradient of $f(\cdot,\cdot)$ is $L$-Lipschitz continuous,
these methods attain the rate of ${\mathcal{O}}(\epsilon^{-1})$ under convex-concave (C-C) setting and the rate of ${\mathcal{O}}((L/\mu)\log(\epsilon^{-1}))$ when $f(\cdot,\cdot)$ is $\mu$-strongly convex in ${\bm{x}}$ and $\mu$-strongly-concave in ${\bm{y}}$ (SC-SC) for $\mu>0$.
They are all optimal under C-C and SC-SC setting due to the lower bounds reported by [, ].

Second-order methods usually lead to faster rates than first-order methods when the Hessian of $f(\cdot,\cdot)$ is $\rho$-Lipschitz continuous.
A line of works [, ] extended the celebrated Cubic Regularized Newton (CRN) []
method to minimax problems with local superlinear convergence rates and global convergence guarantee.
However, the established global convergence rates of ${\mathcal{O}}(\epsilon^{-1})$ by Nesterov and Scrimali [] and ${\mathcal{O}}((L\rho/\mu^{2})\log(\epsilon^{-1}))$ by Huang et al. [] under C-C and SC-SC conditions are no better than the optimal first-order methods.
Another line of work
generalizes the optimal first-order methods to higher-order methods.
Monteiro and Svaiter [] proposed the Newton Proximal Extragradient (NPE) method with a global convergence rate of ${\mathcal{O}}(\epsilon^{-2/3}\log\log(\epsilon^{-1}))$ under the C-C conditions. This result nearly matches the lower bounds [, ], except an additional ${\mathcal{O}}(\log\log(\epsilon^{-1}))$ factor which is caused by the implicit binary search at each iteration.
Recently, Alves and Svaiter [] proposed
a search-free NPE method to remove this ${\mathcal{O}}(\log\log(\epsilon^{-1}))$ factor based on ideas from homotopy.
Over the past decade, researchers also proposed various second-order methods, in addition to the NPE framework [], that achieve the same convergence rate. This algorithms include the second-order extension of EG [, , , ] (which we refer to as EG-2, Huang and Zhang [] call it ARE), that of OGDA [, ] (which we refer to as OGDA-2), and that of DE [] (they name the method Persesus).
For SC-SC problems, Jiang and Mokhtari [] proved the OGDA-2 can converge at the rate of ${\mathcal{O}}((\rho/\mu)^{2/3}+\log\log(\epsilon^{-1}))$, and Huang and Zhang [] proposed the ARE-restart with the rate of ${\mathcal{O}}((\rho/\mu)^{2/3}\log\log(\epsilon^{-1}))$.

Although the aforementioned second-order methods [, , , , ] enjoy an improved convergence rate over the first-order methods and have achieved optimal iteration complexities, they require querying one new Hessian at each iteration and solving a matrix inversion problem at each Newton step, which leads to a ${\mathcal{O}}(d^{3})$ computational cost per iteration. This becomes the main bottleneck that limits the applicability of second-order methods. Liu and Luo [] proposed quasi-Newton methods for saddle point problems that access one Hessian-vector product instead of the exact Hessian for each iteration. The iteration complexity is ${\mathcal{O}}(d^{2})$ for quasi-Newton methods. However, their methods do not have a global convergence guarantee under general (S)C)-(S)C conditions.

In this paper, we propose a computation-efficient second-order method, which we call LEN (Lazy Extra Newton method).
In contrast to all existing second-order methods or quasi-Newton methods for minimax optimization problems that always access new second-order information for the coming iteration, LEN reuses the second-order information from past iterations.
Specifically, LEN solves a cubic regularized sub-problem using the Hessian from the snapshot point that is updated every $m$ iteration, then conducts an extra-gradient step by the gradient from the current iteration.
We provide a rigorous theoretical analysis of LEN to show it maintains fast global convergence rates and goes beyond the optimal second-order methods [, , , , , ] in terms of the overall computational complexity.
We summarize our contributions as follows.

- •
When the object function $f(\cdot,\cdot)$ is convex in ${\bm{x}}$ and concave in ${\bm{y}}$, we propose LEN and prove that it finds an $\epsilon$-saddle point in $\mathcal{O}(m^{2/3}\epsilon^{-2/3})$ iterations. Under Assumption 3.4, where
the complexity of calculating ${\bm{F}}({\bm{z}})$ is $N$ and the complexity of calculating $\nabla{\bm{F}}({\bm{z}})$ is $dN$, the optimal choice is $m=\Theta(d)$. In this case, LEN
only requires a computational complexity of $\tilde{\mathcal{O}}((N+d^{2})(d+d^{2/3}\epsilon^{-2/3}))$, which is strictly better than ${\mathcal{O}}((N+d^{2})d\epsilon^{-2/3})$ for the existing optimal second-order methods by a factor of $d^{1/3}$.
- •
When the object function $f(\cdot,\cdot)$ is $\mu$-strongly-convex in ${\bm{x}}$ and $\mu$-strongly-concave in ${\bm{y}}$, we apply the restart strategy on LEN and propose LEN-restart. We prove the algorithm can find an $\epsilon$-root with
$\tilde{\mathcal{O}}((N+d^{2})(d+d^{2/3}(\rho/\mu)^{2/3}))$ computational complexity, where $\rho$ means the Hessian of $f(\cdot,\cdot)$ is $\rho$ Lipschitz-continuous. Our result
is strictly better than the $\tilde{\mathcal{O}}((N+d^{2})d(\rho/\mu)^{2/3})$ in prior works.

We compare our results with the prior works in Table 1.

**Table 1: We compare the required computational complexity to achieve an $\epsilon$-saddle point of the proposed LEN with the optimal choice $m=\Theta(d)$ and other existing algorithms on both convex-concave (C-C) and strongly-convex-strongly-concave (SC-SC) problems. Here, $d=d_{x}+d_{y}$ is the dimension of the problem. We assume the gradient is $L$-Lipschitz continuous for EG and the Hessian is $\rho$-Lipschitz continuous for others. We count each gradient oracle call with $N$ computational complexity, and each Hessian oracle with $dN$ computational complexity.**
| Setup | Method | Computational Cost |
| --- | --- | --- |
|  | EG [] | ${\mathcal{O}}((N+d)\epsilon^{-1})$ |
|  | NPE [] | $\tilde{\mathcal{O}}((N+d^{2})d\epsilon^{-2/3})$ |
|  | search-free NPE [] | ${\mathcal{O}}((N+d^{2})d\epsilon^{-2/3})$ |
| C-C | EG-2 [] | $\tilde{\mathcal{O}}((N+d^{2})d\epsilon^{-2/3})$ |
|  | Perseus [] | $\tilde{\mathcal{O}}((N+d^{2})d\epsilon^{-2/3})$ |
|  | OGDA-2 [] | ${\mathcal{O}}((N+d^{2})d\epsilon^{-2/3})$ |
|  | LEN (Theorem 4.3) | $\tilde{\mathcal{O}}((N+d^{2})(d+{\color[rgb]{0,0,1}d^{2/3}}\epsilon^{-2/3}))$ |
|  | EG [] | $\tilde{\mathcal{O}}((N+d)(L/\mu))$ |
|  | OGDA-2 [] | ${\mathcal{O}}((N+d^{2})d(\rho/\mu)^{2/3})$ |
| SC-SC | ARE-restart [] | $\tilde{\mathcal{O}}((N+d^{2})d(\rho/\mu))^{2/3})$ |
|  | Perseus-restart [] | $\tilde{\mathcal{O}}((N+d^{2})d(\rho/\mu)^{2/3})$ |
|  | LEN-restart (Corollary 4.1) | $\tilde{\mathcal{O}}((N+d^{2})(d+{\color[rgb]{0,0,1}d^{2/3}}(\rho/\mu)^{2/3}))$ |

## 2 Related Works and Technical Challenges

#### Lazy Hessian in minimization problems.

The idea of reusing Hessian was initially presented by Shamanskii [] and later incorporated into the Levenberg-Marquardt method, damped Newton method, and proximal Newton method [, , , ].
However, the explicit advantage of lazy Hessian update over the ordinary Newton(-type) update was not discovered until the recent work of [, ]. Let $M>0$ be a constant and $\pi(t)=t-t\mod m$.
They applied the following lazy Hessian update on cubic regularized Newton (CRN) methods []:

$$ $\displaystyle{\bm{z}}_{t+1}=\operatorname*{arg\,min}_{{\bm{z}}\in{\mathbb{R}}^ {d}}\left\{\langle{\bm{F}}({\bm{z}}_{t}),{\bm{z}}-{\bm{z}}_{t}\rangle+\frac{1} {2}\langle\nabla{\bm{F}}({\color[rgb]{0,0,1}{\bm{z}}_{\pi(t)}})({\bm{z}}-{\bm{ z}}_{t}),{\bm{z}}-{\bm{z}}_{t}\rangle+\frac{M}{6}\|{\bm{z}}-{\bm{z}}_{t}\|^{3} \right\},$ (2) $$

where ${\bm{F}}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}^{d}$ is the gradient field of a convex function.
They establish the convergence rates of $\mathcal{O}(\sqrt{m}\epsilon^{-3/2})$ for nonconvex optimization [], and $\mathcal{O}(\sqrt{m}\epsilon^{-1/2})$ for convex optimization [] respectively. Such rates lead to the total computational cost of $\tilde{\mathcal{O}}((N+d^{2})(d+\sqrt{d}\epsilon^{-3/2}))$ and $\tilde{\mathcal{O}}((N+d^{2})(d+\sqrt{d}\epsilon^{-1/2}))$ by setting $m=\Theta(d)$, which strictly improve the result by classical CRN methods by a factor of $\sqrt{d}$ on both setups.

We have also observed that the idea of the “lazy Hessian" is widely used in practical second-order methods. Sophia [] estimates a diagonal Hessian matrix as a pre-conditioner, and to reduce the complexity, the pre-conditioner is updated in a lazy manner. KFAC [, ] approximates the Fisher information matrix, and it also uses an exponential moving average (EMA) to update the estimate of the Fisher information matrix, which can be viewed as a soft version of the lazy update.

#### Challenge of using lazy Hessian updates in minimax problems.

In comparison to the previous works on lazy Hessian,
our methods LEN and LEN-restart demonstrate the advantage of using lazy Hessian for a broader class of optimization problems, the minimax problems.
Our analysis differs from the ones in Doikov et al. [], Chayti et al. [].
Their methods only take a lazy CRN update (2) at each iteration,
which makes the error term of using the lazy Hessian instead of the current Hessian $\|{\bm{z}}_{\pi(t)}-{\bm{z}}_{t}\|$ can be easily controlled by the progress of consecutive points generated by the lazy CRN updates $\{\|{\bm{z}}_{i+1}-{\bm{z}}_{i}\|\}_{i=\pi(t)}^{t}$ according to the Lipschitz continuity of Hessian $\|\nabla{\bm{F}}({\bm{z}}_{t})-\nabla{\bm{F}}({\bm{z}}_{\pi(t)})\|\leq\rho\|{
\bm{z}}_{\pi(t)}-{\bm{z}}_{t}\|\leq\rho\sum_{i=\pi(t)}^{t-1}\|{\bm{z}}_{i}-{
\bm{z}}_{i+1}\|$.

Our method, on the other hand, does not only take a lazy (regularized) Newton update but also requires an extra gradient step (Line 4 in Algorithm 1).
Thus, the progress of one Newton update $\{\|{\bm{z}}_{i+1/2}-{\bm{z}}_{i}\|\}_{i=\pi(t)}^{t}$ cannot directly bound the error term $\|{\bm{z}}_{t}-{\bm{z}}_{\pi(t)}\|$ introduced by lazy Hessian update.
Moreover, for minimax problems the matrix $\nabla{\bm{F}}({\bm{z}}_{\pi(t)})$ is no longer symmetric, which leads to different analysis and implementation of sub-problem solving (Section 4.3). We refer the readers to Section 4.1 for more detailed discussions.

#### Notations.

Throughout this paper, $\log$ is base $2$ and $\log_{+}(\,\cdot\,):=1+\log(\,\cdot\,)$. We use $\|\cdot\|$ to denote the spectral norm and Euclidean norm of matrices and vectors, respectively.
We denote $\pi(t)=t-(t\mod m)$ when presenting the lazy updates.

## 3 Preliminaries

In this section, we introduce notations and basic assumptions used in our work.
We start with several standard definitions for Problem (1).

###### Definition 3.1 .

We call a function $f({\bm{x}},{\bm{y}}):{\mathbb{R}}^{d_{x}}\times{\mathbb{R}}^{d_{y}}\rightarrow
{\mathbb{R}}$ has $\rho$-Lipschitz Hessians if we have

$$ $\displaystyle\|\nabla^{2}f({\bm{x}},{\bm{y}})-\nabla^{2}f({\bm{x}}^{\prime},{ \bm{y}}^{\prime})\|\leq\rho\left\|\begin{bmatrix}{\bm{x}}-{\bm{x}}^{\prime}\\ {\bm{y}}-{\bm{y}}^{\prime}\end{bmatrix}\right\|,\quad\forall({\bm{x}},{\bm{y}} ),({\bm{x}}^{\prime},{\bm{y}}^{\prime})\in{\mathbb{R}}^{d_{x}}\times{\mathbb{R }}^{d_{y}}.$ $$

###### Definition 3.2 .

A differentiable function $f(\cdot,\cdot)$ is $\mu$-strongly-convex-$\mu$-strongly-concave for some $\mu>0$ if

$$ $\displaystyle f({\bm{x}}^{\prime},{\bm{y}})$ $\displaystyle\geq f({\bm{x}},{\bm{y}})+({\bm{x}}^{\prime}-{\bm{x}})^{\top} \nabla_{x}f({\bm{x}},{\bm{y}})+\frac{\mu}{2}\|{\bm{x}}-{\bm{x}}^{\prime}\|^{2} ,\quad\forall{\bm{x}}^{\prime},{\bm{x}}\in{\mathbb{R}}^{d_{x}},{\bm{y}}\in{ \mathbb{R}}^{d_{y}};$ $\displaystyle f({\bm{x}},{\bm{y}}^{\prime})$ $\displaystyle\leq f({\bm{x}},{\bm{y}})+({\bm{y}}^{\prime}-{\bm{y}})^{\top} \nabla_{y}f({\bm{x}},{\bm{y}})-\frac{\mu}{2}\|{\bm{y}}-{\bm{y}}^{\prime}\|^{2} ,\quad\forall{\bm{y}}^{\prime},{\bm{y}}\in{\mathbb{R}}^{d_{y}},{\bm{x}}\in{ \mathbb{R}}^{d_{x}}.$ $$

We say $f$ is convex-concave if $\mu=0$.

We are interested in finding a saddle point of Problem (1), formally defined as follows.

###### Definition 3.3 .

We call a point $({\bm{x}}^{*},{\bm{y}}^{*})\in{\mathbb{R}}^{d_{x}}\times{\mathbb{R}}^{d_{y}}$ a saddle point of a function $f(\cdot,\cdot)$ if we have

$$ $\displaystyle f({\bm{x}}^{*},{\bm{y}})\leq f({\bm{x}},{\bm{y}})\leq f({\bm{x}} ,{\bm{y}}^{*}),\quad\forall{\bm{x}}\in\mathbb{R}^{d_{x}},~{}{\bm{y}}\in\mathbb {R}^{d_{y}}.$ $$

Next, we introduce all the assumptions made in this work. In this paper, we focus on Problem (1) that satisfies the following assumptions.

###### Assumption 3.1 .

We assume the function $f(\cdot,\cdot)$ is twice continuously differentiable, has $\rho$-Lipschitz continuous Hessians, and has at least one saddle point $({\bm{x}}^{*},{\bm{y}}^{*})$.

We will study convex-concave problems and strongly-convex-strongly-concave problems.

###### Assumption 3.2 (C-C setting) .

We assume the function $f(\cdot,\cdot)$ is convex in ${\bm{x}}$ and concave in ${\bm{y}}$.

###### Assumption 3.3 (SC-SC setting) .

We assume the function $f(\cdot,\cdot)$ is $\mu$-strongly-convex-$\mu$-strongly-concave. We denote the condition number as $\kappa:=\rho/\mu$

We let $d:=d_{x}+d_{y}$ and denote the aggregated variable ${\bm{z}}:=({\bm{x}},{\bm{y}})\in{\mathbb{R}}^{d}$. We also denote the GDA field of $f$ and its Jacobian as

$$ $\displaystyle\begin{split}{\bm{F}}({\bm{z}}):=\begin{bmatrix}\nabla_{x}f({\bm{ x}},{\bm{y}})\\ -\nabla_{y}f({\bm{x}},{\bm{y}})\end{bmatrix},\quad\nabla{\bm{F}}({\bm{z}}):= \begin{bmatrix}\nabla_{xx}^{2}f({\bm{x}},{\bm{y}})&\nabla_{xy}^{2}f({\bm{x}},{ \bm{y}})\\ -\nabla_{yx}^{2}f({\bm{x}},{\bm{y}})&-\nabla_{yy}^{2}f({\bm{x}},{\bm{y}})\end{ bmatrix}.\end{split}$ (3) $$

The GDA field of $f(\cdot,\cdot)$ has the following properties.

###### Lemma 3.1 (Lemma 2.7 Lin et al. [ 32 ] ) .

Under Assumptions 3.1 and 3.2, we have

- 1.
${\bm{F}}$ is monotone, i.e. $\langle{\bm{F}}({\bm{z}})-{\bm{F}}({\bm{z}}^{\prime}),{\bm{z}}-{\bm{z}}^{
\prime}\rangle\geq 0,~{}\forall{\bm{z}},{\bm{z}}^{\prime}\in{\mathbb{R}}^{d}$.
- 2.
$\nabla{\bm{F}}$ is $\rho$-Lipschitz continuous, i.e. $\|\nabla{\bm{F}}({\bm{z}})-\nabla{\bm{F}}({\bm{z}}^{\prime})\|\leq\rho\|{\bm{z
}}-{\bm{z}}^{\prime}\|,~{}\forall{\bm{z}},{\bm{z}}^{\prime}\in{\mathbb{R}}^{d}$.
- 3.
${\bm{F}}({\bm{z}}^{*})=0$ if and only if ${\bm{z}}^{*}=({\bm{x}}^{*},{\bm{y}}^{*})$ is a saddle point of function $f(\cdot,\cdot)$.

Furthermore, if Assumption 3.3 holds, we have ${\bm{F}}(\cdot)$ is $\mu$-strongly-monotone, i.e.

$$ $\displaystyle\langle{\bm{F}}({\bm{z}})-{\bm{F}}({\bm{z}}^{\prime}),{\bm{z}}-{ \bm{z}}^{\prime}\rangle\geq\mu\|{\bm{z}}-{\bm{z}}^{\prime}\|^{2},~{}\forall{ \bm{z}},{\bm{z}}^{\prime}\in{\mathbb{R}}^{d}.$ $$

For the C-C case, the commonly used optimality criterion is the following restricted gap.

###### Definition 3.4 ( Nesterov [ 46 ] ) .

Let ${\mathbb{B}}_{\beta}({\bm{w}})$ be the ball centered at ${\bm{w}}$ with radius $\beta$. Let $({\bm{x}}^{*},{\bm{y}}^{*})$ be a saddle point of function $f$. For a given point $(\hat{\bm{x}},\hat{\bm{y}})$, we let $\beta$ sufficiently large such that it holds

$$ $\displaystyle\max\left\{\|\hat{\bm{x}}-{\bm{x}}^{*}\|,~{}\|\hat{\bm{y}}-{\bm{y }}^{*}\|\right\}\leq\beta,$ $$

we define the restricted gap function as

$$ $\displaystyle{\rm Gap}(\hat{\bm{x}},\hat{\bm{y}};\beta):=\max_{{\bm{y}}\in{ \mathbb{B}}_{\beta}({\bm{y}}^{*})}f(\hat{\bm{x}},{\bm{y}})-\min_{{\bm{x}}\in{ \mathbb{B}}_{\beta}({\bm{x}}^{*})}f({\bm{x}},\hat{\bm{y}}),$ $$

We call $(\hat{\bm{x}},\hat{\bm{y}})$ an $\epsilon$-saddle point if ${\rm Gap}(\hat{\bm{x}},\hat{\bm{y}};\beta)\leq\epsilon$ and $\beta=\Omega(\max\{\|{\bm{x}}_{0}-{\bm{x}}^{*}\|,\|{\bm{y}}_{0}-{\bm{y}}^{*}\|\})$.

For the SC-SC case, we use the following stronger notion.

###### Definition 3.5 .

Suppose that Assumption 3.3 holds.
Let ${\bm{z}}^{*}=({\bm{x}}^{*},{\bm{y}}^{*})$ be the unique saddle point of function $f$. We call $\hat{\bm{z}}=(\hat{\bm{x}},\hat{\bm{y}})$ an $\epsilon$-root if $\|\hat{\bm{z}}-{\bm{z}}\|\leq\epsilon$.

Most previous works only consider the complexity metric as the number of oracle calls, where an oracle takes a point ${\bm{z}}\in{\mathbb{R}}^{d}$ as the input and returns a tuple $({\bm{F}}({\bm{z}}),\nabla{\bm{F}}({\bm{z}}))$ as the output.
The existing algorithms [, , , ] have achieved
optimal complexity regarding the number of oracle calls. In this work, we focus on the computational complexity of the oracle. More specifically, we distinguish between the different computational complexities of calculating the Hessian matrix $\nabla{\bm{F}}({\bm{z}})$ and the gradient ${\bm{F}}({\bm{z}})$. Formally, we make the following assumption as Doikov et al. [].

###### Assumption 3.4 .

We count the computational complexity of computing ${\bm{F}}(\cdot)$ as $N$ and the computational complexity of
$\nabla{\bm{F}}(\cdot)$ as $Nd$.

###### Remark 3.1 .

Assumption 3.4 supposes the cost of computing $\nabla{\bm{F}}(\cdot)$ is $d$ times that of computing ${\bm{F}}(\cdot)$. It holds in many practical scenarios as one Hessian oracle can be computed
via $d$ Hessian-vector products on standard basis vectors ${\bm{e}}_{1},\cdots,{\bm{e}}_{d}$, and one Hessian-vector product oracle is typically as expensive as one gradient oracle []:

- 1.
When the computational graph of $f$ is obtainable, both ${\bm{F}}({\bm{z}})$ and $\nabla{\bm{F}}({\bm{z}}){\bm{v}}$ can be computed using automatic differentiation with the same cost for any ${\bm{z}},{\bm{v}}\in{\mathbb{R}}^{d}$.
- 2.
When $f$ is a black box function, we can estimate the Hessian-vector $\nabla{\bm{F}}({\bm{z}}){\bm{v}}$ via the finite-difference ${\bm{u}}_{\delta}({\bm{z}};{\bm{v}})=\frac{1}{\delta}({\bm{F}}({\bm{z}}+\delta
{\bm{v}})-{\bm{F}}({\bm{z}}-\delta{\bm{v}}))$ and we have $\lim_{\delta\rightarrow 0}{\bm{u}}_{\delta}({\bm{z}};{\bm{v}})=\nabla{\bm{F}}(
{\bm{z}}){\bm{v}}$ under mild conditions on ${\bm{F}}(\cdot)$.

###### Definition 3.1 .

###### Definition 3.2 .

###### Definition 3.3 .

###### Assumption 3.1 .

###### Assumption 3.2 (C-C setting) .

###### Assumption 3.3 (SC-SC setting) .

###### Lemma 3.1 (Lemma 2.7 Lin et al. [ 32 ] ) .

###### Definition 3.4 ( Nesterov [ 46 ] ) .

###### Definition 3.5 .

###### Assumption 3.4 .

###### Remark 3.1 .

## 4 Algorithms and convergence analysis

In this section, we present novel second-order methods for solving minimax optimization problems (1). We present LEN and its convergence analysis for convex-concave minimax problems in Section 4.1. We generalize LEN for strongly-convex-strongly-concave minimax problems by presenting LEN-restart in Section 4.2.
We discuss the details of solving
minimax cubic-regularized sub-problem, present detailed implementation of LEN, and give the total computational complexity of proposed methods in Section 4.3.

### 4.1 The LEN algorithm for convex-concave problems

We propose LEN for convex-concave problems in Algorithm 1.
Our method builds on
the recently proposed optimal second-order methods ARE [, ] / Newton-Minimax []. The only change is that we reuse the Hessian from previous iterates, as colored in blue. Each iteration of LEN contains the following two steps:

$$ $\displaystyle\begin{cases}{\bm{F}}({\bm{z}}_{t})+\nabla{\bm{F}}({\color[rgb]{ 0,0,1}{\bm{z}}_{\pi(t)}})({\bm{z}}_{t+1/2}-{\bm{z}}_{t})+M\|{{\bm{z}}}_{t+1/2} -{\bm{z}}_{t}\|({{\bm{z}}}_{t+1/2}-{\bm{z}}_{t})={\bf 0},~{}~{}&\text{( Implicit Step)}\\ {\bm{z}}_{t+1}={\bm{z}}_{t}-\dfrac{{\bm{F}}({{\bm{z}}}_{t+1/2})}{M\|{{\bm{z}}} _{t+1/2}-{\bm{z}}_{t}\|}.~{}~{}&\text{(Explicit Step)}\end{cases}$ (4) $$

The first step (implicit step) solves a cubic regularized sub-problem based on the $\nabla{\bm{F}}({\bm{z}}_{\pi(t)})$ computed at the latest snapshot point and ${\bm{F}}({\bm{z}}_{t})$ at the current iteration point. This step is often viewed as an oracle [, , , ] as there exists efficient solvers, which will also be discussed in Section 4.3.
The second one (explicit step)
conducts an
extra gradient step based on ${\bm{F}}({\bm{z}}_{t+1/2})$.

Reusing the Hessian in the implicit step makes each iteration much cheaper, but would
cause additional errors compared to previous methods [, , , ].
The error resulting from the lazy Hessian updates is formally
characterized by the following theorem.

###### Lemma 4.1 .

Suppose that Assumption 3.1 and 3.2 hold. For any ${\bm{z}}\in{\mathbb{R}}^{d}$, Algorithm 1 ensures

$$ $\displaystyle\quad\gamma_{t}^{-1}\langle{\bm{F}}({\bm{z}}_{t+1/2}),{\bm{z}}_{t +1/2}-{\bm{z}}\rangle$ $\displaystyle\leq\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}\|^{2}-\frac{1}{2}\|{\bm{z} }_{t+1}-{\bm{z}}\|^{2}-\frac{1}{2}\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\|^{2}$ $\displaystyle\quad-\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}_{t+1/2}\|^{2}+\frac{\rho ^{2}}{2M^{2}}\|{\bm{z}}_{t}-{\bm{z}}_{t+1/2}\|^{2}+\underbrace{\frac{2\rho^{2} }{M^{2}}\|{\bm{z}}_{\pi(t)}-{\bm{z}}_{t}\|^{2}}_{(*)}.$ $$

Above, (*) is the error from lazy Hessian updates. Note that
(*) vanishes when
the current Hessian is used. For lazy Hessian updates, the error would accumulate in the epoch.

The key step in our analysis shows that we can use the negative terms in the right-hand side of the inequality in Lemma 4.1 to bound the accumulated error by choosing $M$ sufficiently large, with the help of the following technical lemma.

###### Lemma 4.2 .

For any sequence of positive numbers $\{r_{t}\}_{t\geq 1}$, it holds for any $m\geq 2$ that
$\sum_{t=1}^{m-1}\left(\sum_{i=0}^{t-1}r_{i}\right)^{2}\leq\frac{m^{2}}{2}\sum_
{t=0}^{m-1}r_{t}^{2}.$

When $m=1$, the algorithm reduces to the EG-2 algorithm [, , ] without using lazy Hessian updates. When $m\geq 2$, we use Lemma 4.2 to upper bound the error that arises from lazy Hessian updates.
Finally, we prove the following guarantee for our proposed algorithm.

Figure: Algorithm 1 LEN$({\bm{z}}_{0},T,m,M)$

###### Theorem 4.1 (C-C setting) .

Suppose that Assumption 3.1 and 3.2 hold. Let ${\bm{z}}^{*}=({\bm{x}}^{*},{\bm{y}}^{*})$ be a saddle point and $\beta=3\|{\bm{z}}_{0}-{\bm{z}}^{*}\|$. Set $M\geq 3\rho m$. The sequence of iterates generated by Algorithm 1 is bounded ${\bm{z}}_{t},~{}{\bm{z}}_{t+1/2}\in{\mathbb{B}}_{\beta}({\bm{z}}^{*}),\quad
\forall t=0,\cdots,T-1,$
and satisfies the following ergodic convergence:

$$ $\displaystyle{\rm Gap}(\bar{\bm{x}}_{T},\bar{\bm{y}}_{T};\beta)\leq\frac{9M\|{ \bm{z}}_{0}-{\bm{z}}^{*}\|^{3}}{T^{3/2}}.$ $$

Let $M=3\rho m$. Algorithm 1 finds an $\epsilon$-saddle point within ${\mathcal{O}}(m^{2/3}\epsilon^{-2/3})$ iterations.

###### Lemma 4.1 .

###### Lemma 4.2 .

###### Theorem 4.1 (C-C setting) .

#### Discussion on the computational complexity of the oracles.

Theorem 4.1 indicates that LEN requires ${\mathcal{O}}(m^{2/3}\epsilon^{-2/3})$ calls to ${\bm{F}}(\cdot)$ and ${\mathcal{O}}(m^{2/3}\epsilon^{-2/3}/m+1)$ calls to $\nabla{\bm{F}}(\cdot)$ to find the $\epsilon$-saddle point. Under Assumption 3.4, the computational cost to call the oracles ${\bm{F}}(\cdot)$ and $\nabla{\bm{F}}(\cdot)$ is

$$ $\displaystyle\text{Oracle Computational Cost}={\mathcal{O}}\left(N\cdot m^{2/3 }\epsilon^{-2/3}+(Nd)\cdot\left(\frac{\epsilon^{-2/3}}{m^{1/3}}+1\right)\right).$ (5) $$

Taking $m=\Theta(d)$ minimizes (5) to ${\mathcal{O}}(Nd+N{d^{2/3}}\epsilon^{-2/3})$.
In comparison to the state-of-the-art second-order methods [, , ], whose computational cost in terms of the oracles is ${\mathcal{O}}(Nd\epsilon^{-2/3})$ since they require to query $\nabla{\bm{F}}(\cdot)$ at each iteration, our methods significantly improve their results by a factor of $d^{1/3}$.

It is worth noticing that the computational cost of an algorithm includes both the computational cost of calling the oracles, which we have discussed above, and the computational cost of performing the updates (i.e. solving auxiliary problems) after accessing the required oracles.
We will give an efficient implementation of LEN and analyze the total computational cost later in Section 4.3.

### 4.2 The LEN-restart algorithm for strongly-convex-strongly-concave problems

We generalize LEN to solve the strongly-convex-strongly-concave minimax optimization by incorporating the restart strategy introduced by Huang and Zhang []. We propose the LEN-restart in Algorithm 2, which works in epochs.
Each epoch of LEN-restart invokes LEN (Algorithm 1), which gets ${\bm{z}}^{(s)}$ as inputs and outputs ${\bm{z}}^{(s+1)}$.

The following theorem shows that the sequence $\{{\bm{z}}^{(s)}\}$ enjoys a superlinear convergence in epochs.
Furthermore, the required number of iterations in each epoch to achieve such a superlinear rate
is only a constant.

Figure: Algorithm 2 LEN-restart$({\bm{z}}_{0},T,m,M,S)$

###### Theorem 4.2 (SC-SC setting) .

Suppose that Assumptions 3.1 and 3.3 hold. Let ${\bm{z}}^{*}=({\bm{x}}^{*},{\bm{y}}^{*})$ be the unique saddle point. Set $M=3\rho m$ as Theorem 4.1 and $T=\left(\frac{2M\|{\bm{z}}_{0}-{\bm{z}}^{*}\|}{\mu}\right)^{2/3}.$
Then the sequence of iterates generated by Algorithm 2 converge to ${\bm{z}}^{*}$ superlinearly as $\|{\bm{z}}^{(s)}-{\bm{z}}^{*}\|^{2}\leq\left(\frac{1}{2}\right)^{(3/2)^{s}}\|{
\bm{z}}_{0}-{\bm{z}}^{*}\|^{2}.$
In particular, Algorithm 2 with $M=3\rho m$ finds a point ${\bm{z}}^{(s)}$ such that $\|{\bm{z}}^{(s)}-{\bm{z}}^{*}\|\leq\epsilon$ within $S=\log_{3/2}\log_{2}(\nicefrac{{1}}{{\epsilon}})$ epochs.
The total number of inner loop iterations is given by

$$ $\displaystyle TS={\mathcal{O}}\left(m^{2/3}\kappa^{2/3}\log\log(\nicefrac{{1}} {{\epsilon}})\right).$ $$

Under Assumption 3.4, Algorithm 2 with $m=\Theta(d)$ takes the computational complexity of ${\mathcal{O}}((Nd+Nd^{2/3}\kappa^{2/3})\log\log(\nicefrac{{1}}{{\epsilon}}))$ to call the oracles ${\bm{F}}(\cdot)$ and $\nabla{\bm{F}}(\cdot)$.

###### Theorem 4.2 (SC-SC setting) .

### 4.3 Implementation Details and computational complexity Analysis

We provide details of implementing the cubic regularized Newton oracle (Implicit Step, (4)). Inspired by Monteiro and Svaiter [], Adil et al. [], Lin et al. [],
we transform the sub-problem into a root-finding problem for a univariate function.

###### Lemma 4.3 (Section 4.3, Lin et al. [ 32 ] ) .

Suppose Assumption 3.1 and 3.2 hold for function $f:{\mathbb{R}}^{d_{x}}\times{\mathbb{R}}^{d_{y}}\rightarrow{\mathbb{R}}$ and let
${\bm{F}}$ be its GDA field.
Define $\lambda=M\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t}\|$.
The cubic regularized Newton oracle (Implicit Step, (4)) can be rewritten as:

$$ $\displaystyle{\bm{z}}_{t+1/2}={\bm{z}}_{t}-(\nabla{\bm{F}}({\bm{z}}_{\pi(t)})+ \lambda{\bm{I}}_{d})^{-1}{\bm{F}}({\bm{z}}_{t}),$ $$

which can be implemented by finding the root of the following univariate function:

$$ $\displaystyle\phi(\lambda):=M\left\|\right(\nabla{\bm{F}}({\bm{z}}_{\pi(t)})+ \lambda{\bm{I}}_{d})^{-1}{\bm{F}}({\bm{z}}_{t})\|-\lambda.$ (6) $$

Furthermore, the function $\phi(\lambda)$ is strictly decreasing
when $\lambda>0$, i.e. it always holds that $\phi^{\prime}(\lambda)<0$ when $\lambda>0$.

From the above lemma, to implement the cubic regularized Newton oracle, it suffices to find the root of a strictly decreasing function $\phi(\lambda)$, which can be solved within $\tilde{\mathcal{O}}(1)$ iteration.
The main operation is to solve the following linear system:

$$ $\displaystyle(\nabla{\bm{F}}({\bm{z}}_{\pi(t)})+\lambda{\bm{I}}_{d}){\bm{h}}={ \bm{F}}({\bm{z}}_{t}).$ (7) $$

Naively solving this linear system at every iteration still results in an expensive computational complexity of ${\mathcal{O}}(d^{3})$ per iteration.

We present a computationally efficient way to implement LEN by leveraging the Schur factorization at the snapshot point $\nabla{\bm{F}}({\bm{z}}_{\pi(t)})={\bm{Q}}{\bm{U}}{\bm{Q}}^{-1}$, where ${\bm{Q}}\in{\mathbb{C}}^{d}$ is a unitary matrix and ${\bm{U}}\in{\mathbb{C}}^{d}$ is an upper-triangular matrix.
Then we apply the following update

$$ $\displaystyle{\bm{h}}={\bm{Q}}({\bm{U}}+\lambda{\bm{I}}_{d})^{-1}{\bm{Q}}^{-1} {\bm{F}}({\bm{z}}_{t})$ (8) $$

instead of solving the linear system (7) at each iteration.
The final implementable algorithm is presented in Algorithm 3.

Now, we are ready to analyze the total computational complexity of LEN, which can be divided into the following two parts:

$$ Computational Cost $\displaystyle=\text{Oracle Computational Cost}+\text{Update Computational Cost},$ $$

​where the first part has been discussed in Section 4.1.
As for the update computational cost,
the Schur decomposition with an ${\mathcal{O}}(d^{3})$ computational complexity is required once every $m$ iterations.
After the Schur decomposition has been given at the snapshot point, the dominant part of the update computational complexity is solving the linear system (7),
which can be done efficiently by solving the upper-triangular linear system (8) with the back substitution algorithm within ${{\mathcal{O}}}(d^{2})$ computational complexity.
Thus, we have

$$ $\displaystyle\text{Update Computational Cost}=\tilde{{\mathcal{O}}}\left(d^{2} \cdot m^{2/3}\epsilon^{-2/3}+d^{3}\cdot\left(\frac{\epsilon^{-2/3}}{m^{1/3}}+1 \right)\right),$ (9) $$

and the total computational Cost of LEN is

$$ $\displaystyle\text{Computational Cost}\overset{(\ref{eq:compu-cost}),(\ref{eq: update-cost})}{=}\!\tilde{{\mathcal{O}}}\left((d^{2}+N)\cdot m^{2/3}\epsilon^{ -2/3}+(d^{3}+Nd)\cdot\left(\frac{\epsilon^{-2/3}}{m^{1/3}}+1\right)\!\right).$ (10) $$

By taking $m=\Theta(d)$, we obtain the best computational complexity in (10) of LEN, which is formally stated in the following theorem.

###### Theorem 4.3 (C-C setting) .

Under the same setting of Theorem 4.1, Algorithm 3 with $m=\Theta(d)$ finds an $\epsilon$-saddle point with $\tilde{\mathcal{O}}((N+d^{2})(d+d^{2/3}\epsilon^{-2/3})$ computational complexity.

We also present the total computational complexity of LEN-restart for SC-SC setting.

###### Corollary 4.1 (SC-SC setting) .

Under the same setting of Theorem 4.2, Algorithm 2 implemented in the same way as Algorithm 3 with $m=\Theta(d)$ finds an $\epsilon$-root with $\tilde{\mathcal{O}}((N+d^{2})(d+d^{2/3}\kappa^{2/3})$ computational complexity.

In both cases, our proposed algorithms improve the total computational cost of the optimal second-order methods [, , , ] by a factor of $d^{1/3}$.

Figure: Algorithm 3 Implementation of LEN $({\bm{z}}_{0},T,m,M)$

###### Remark 4.1 .

In the main text, we assume the use of the classical algorithm for matrix inversion/decomposition, which has a computational complexity of ${\mathcal{O}}(d^{3})$. In fact, the fast matrix multiplication proposed by researchers in the field of theoretical computer science only requires a complexity of
$d^{\omega}$,
where the best-known
$\omega$ is currently around $2.371552$. This also implies faster standard linear algebra operators including Schur decomposition and matrix inversion [].
However, the large hidden constant factors in these fast matrix multiplication algorithms
mean that the matrix dimensions necessary for these algorithms to be superior to classical algorithms are much larger than what current computers can effectively handle.
Consequently, these algorithms are not used in practice. Therefore, we only present the computational complexity of using fast matrix operations in Appendix G.

###### Lemma 4.3 (Section 4.3, Lin et al. [ 32 ] ) .

###### Theorem 4.3 (C-C setting) .

###### Corollary 4.1 (SC-SC setting) .

###### Remark 4.1 .

## 5 Numerical Experiments

In this section, we conduct our algorithms on regularized bilinear min-max problem and fairness-aware machine learning tasks. We include EG [] and second-order extension of EG (which is denoted by EG-2) [, , ] as the baselines since they are the optimal first-order and second-order methods for convex-concave minimax problems, respectively.
We run the programs on an AMD EPYC 7H12 64-Core Processor.

### 5.1 Regularized bilinear min-max problem

We first conduct numerical experiments on the cubic regularized bilinear min-max problem that was commonly considered in the literature [, , , ]:

$$ $\displaystyle\min_{{\bm{x}}\in{\mathbb{R}}^{n}}\max_{{\bm{y}}\in{\mathbb{R}}^{ n}}f({\bm{x}},{\bm{y}})=\frac{\rho}{6}\|{\bm{x}}\|^{3}+{\bm{y}}^{\top}({\bm{A} }{\bm{x}}-{\bm{b}}).$ (11) $$

The function $f({\bm{x}},{\bm{y}})$ is convex-concave and has $\rho$-Lipschitz continuous Hessians. Moreover, the unique saddle point ${\bm{z}}^{*}=({\bm{x}}^{*},{\bm{y}}^{*})$ of $f({\bm{x}},{\bm{y}})$ can be explicitly calculated as ${\bm{x}}^{*}={\bm{A}}^{-1}{\bm{b}}$ and ${\bm{y}}^{*}=-\rho\|{\bm{x}}^{*}\|^{2}({\bm{A}}^{\top})^{-1}{\bm{x}}^{*}/2$, so we can compute the distance to ${\bm{z}}^{*}$ to measure the performance of algorithms.
Following Lin et al. [], we generate each element in ${\bm{b}}$ as independent Rademacher variables in $\{-1,+1\}$, set the regularization coefficient $\rho=1/(20n)$ and the matrix

$$ $\displaystyle{\bm{A}}=\begin{bmatrix}1&-1\\ &\ddots&\ddots\\ &&1&-1\\ &&&1\\ \end{bmatrix}.$ $$

We compare our methods with the baselines on different sizes of problem: $n\in\{100,200,500\}$. For EG, we tune the stepsize in $\{1,0.1,0.01,0.001\}$.
For LEN, we tune $m$ in $\{10,100,d\}$.
The results of running time against $\|{\bm{F}}({\bm{z}})\|$ and $\|{\bm{z}}-{\bm{z}}^{*}\|$ is presented in Figure 1.

Figure: Figure 1: We demonstrate running time v.s. gradient norm $\|{\bm{F}}({\bm{z}})\|$ and v.s. distance to saddle point $\|{\bm{z}}-{\bm{z}}^{*}\|$ for Problem (11) with different sizes: $n\in\{100,200,500\}$.
Refer to caption: x1.png

### 5.2 Fairness-Aware Machine Learning

We then examine our algorithm in the task of fairness-aware machine learning.
Let $\{{\bm{a}}_{i},b_{i},c_{i}\}_{i=1}^{n}$ be the training set, where ${\bm{a}}_{i}\in{\mathbb{R}}^{d_{x}}$ denotes the features of the $i$-th sample, $b_{i}\in\{-1,+1\}$ is the corresponding label, and
$c_{i}\in\{-1,+1\}$ is an additional feature that is required to be protected and debiased. For example, $c_{i}$ can denote the gender. Zhang et al. [] proposed to solve the following minimax problem to mitigate unwanted bias of $c_{i}$ by adversarial learning:

$$ $\displaystyle\min_{{\bm{x}}\in{\mathbb{R}}^{d_{x}}}\max_{y\in{\mathbb{R}}} \frac{1}{n}\sum_{i=1}^{n}\ell(b_{i}{\bm{a}}_{i}^{\top}{\bm{x}})-\beta\ell(c_{i }y{\bm{a}}_{i}^{\top}{\bm{x}})+\lambda\|{\bm{x}}\|^{2}-\gamma y^{2},$ (12) $$

where $\ell$ is the logit function such that $\ell(t)=\log(1+\exp(-t))$.
We set $\lambda=\gamma=10^{-4}$ and $\beta=0.5$.
We conduct the experiments on datasets “heart” ($n=270$, $d_{x}=13$) [], “adult” ($n=32,561$, $d_{x}=123$) [] and “law school” ($n=20,798$, $d_{x}=380$) [, ]. For all the datasets, we choose “gender” as the protected feature.
For EG, we tune the stepsize in $\{0.1,0.01,0.001\}$. For second-order methods (EG-2 and LEN), as we do not know the value of $\rho$ in advance, we view it as a hyperparameter and tune it in $\{1,10,100\}$.
We set $m=10$ for LEN and we find this simple choice performs well in all the datasets we test.
We show the results of running time against gradient norm $\|{\bm{F}}({\bm{z}})\|$ in Figure 2.

Figure: Figure 2: We demonstrate running time v.s. gradient norm $\|{\bm{F}}({\bm{z}})\|$ for fairness-aware machine learning task (Problem (12)) on datasets “heart”, “adult”, and “law school”.
Refer to caption: x7.png

## 6 Conclusion and future works

In this paper, we propose LEN and LEN-restart for C-C and SC-SC min-max problems, respectively. By using lazy Hessian updates, our methods improve the computational complexity of the current best-known second-order methods
by a factor of $d^{1/3}$.
Numerical experiments on both real and synthetic datasets also verify the efficiency of our method.

For future works, it will be interesting to extend our idea to adaptive second-order methods [, , , , ], stochastic problems with sub-sampled Newton methods [, , , , ], or distributed scenarios [].
Besides, our methods only focus on the convex-concave case, it is also possible to reduce the Hessian oracle for the nonconvex-concave problems [, , , , ] or study the structured nonconvex-nonconcave problems
[, , , , ].

## Appendix A Some Useful Lemmas

###### Lemma A.1 (Proposition 2.8 Lin et al. [ 32 ] ) .

Let

$$ $\displaystyle\bar{\bm{x}}_{t}=\frac{1}{\sum_{i=0}^{t-1}\eta_{i}}\sum_{i=0}^{t- 1}\eta_{i}{\bm{x}}_{i},\quad\bar{\bm{y}}_{t}=\frac{1}{\sum_{i=0}^{t-1}\eta_{i} }\sum_{i=0}^{t-1}\eta_{i}{\bm{y}}_{i}.$ $$

Then under Assumption 3.2, for any ${\bm{z}}=({\bm{x}},{\bm{y}})$, it holds that

$$ $\displaystyle f(\bar{\bm{x}}_{t},{\bm{y}})-f({\bm{x}},\bar{\bm{y}}_{t})\leq \frac{1}{\sum_{i=0}^{t-1}\eta_{i}}\sum_{i=0}^{t-1}\eta_{i}\langle{\bm{F}}({\bm {z}}_{i}),{\bm{z}}_{i}-{\bm{z}}\rangle.$ $$

###### Lemma A.1 (Proposition 2.8 Lin et al. [ 32 ] ) .

## Appendix B Proof of Lemma 4.2

###### Proof.

We prove the result by induction.

Apparently, it is true for $m=2$, which is the induction base.

Assume that it holds for $m\geq 2$. Then

$$ $\displaystyle\quad\sum_{t=1}^{m}\left(\sum_{i=0}^{t-1}r_{i}\right)^{2}$ $\displaystyle=\sum_{t=1}^{m-1}\left(\sum_{i=0}^{t-1}r_{i}\right)^{2}+\left( \sum_{i=0}^{m-1}r_{i}\right)^{2}$ $\displaystyle\leq\frac{m^{2}}{2}\sum_{t=0}^{m-1}r_{t}^{2}+m\sum_{t=0}^{m-1}r_{ t}^{2}$ $\displaystyle\leq\left(\frac{m^{2}+m}{2}\right)\sum_{t=0}^{m-1}r_{t}^{2}$ $\displaystyle\leq\frac{(m+1)^{2}}{2}\sum_{t=0}^{m-1}r_{t}^{2}.$ $$

∎

###### Proof.

## Appendix C Proof of Lemma 4.1

###### Proof.

In our analysis, we denote

$$ $\displaystyle\gamma_{t}\triangleq M\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t}\|~{}~{}~{} \text{and}~{}~{}~{}\eta_{t}\triangleq\frac{1}{\gamma_{t}}.$ (13) $$

For ant ${\bm{z}}\in{\mathbb{R}}^{d}$,
we have

$$ $\displaystyle\begin{split}&\quad\eta_{t}\langle{\bm{F}}({\bm{z}}_{t+1/2}),{\bm {z}}_{t+1/2}-{\bm{z}}\rangle\\ &=\langle{\bm{z}}_{t}-{\bm{z}}_{t+1},{\bm{z}}_{t+1/2}-{\bm{z}}\rangle\\ &=\langle{\bm{z}}_{t}-{\bm{z}}_{t+1},{\bm{z}}_{t+1}-{\bm{z}}\rangle+\langle{ \bm{z}}_{t}-{\bm{z}}_{t+1},{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\rangle\\ &=\langle{\bm{z}}_{t}-{\bm{z}}_{t+1},{\bm{z}}_{t+1}-{\bm{z}}\rangle+\langle{ \bm{z}}_{t}-{\bm{z}}_{t+1/2},{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\rangle+\langle{ \bm{z}}_{t+1/2}-{\bm{z}}_{t+1},{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\rangle\\ &=\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}\|^{2}-\frac{1}{2}\|{\bm{z}}_{t+1}-{\bm{z} }\|^{2}-\bcancel{\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}_{t+1}\|^{2}}\\ &\quad+\bcancel{\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}_{t+1}\|^{2}}-\frac{1}{2}\|{ \bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\|^{2}-\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}_{t+1/2 }\|^{2}+\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\|^{2}.\end{split}$ (14) $$

Note that by the updates of the algorithm, we have that

$$ $\displaystyle\gamma_{t}({\bm{z}}_{t}-{\bm{z}}_{t+1/2})$ $\displaystyle={\bm{F}}({\bm{z}}_{t})+\nabla{\bm{F}}({\bm{z}}_{\pi(t)})({\bm{z} }_{t+1/2}-{\bm{z}}_{t}),$ $\displaystyle\gamma_{t}({\bm{z}}_{t}-{\bm{z}}_{t+1})$ $\displaystyle={\bm{F}}({\bm{z}}_{t+1/2}).$ $$

It implies that

$$ $\displaystyle\begin{split}&\quad{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\\ &=\eta_{t}({\bm{F}}({\bm{z}}_{t+1/2})-{\bm{F}}({\bm{z}}_{t})-\nabla{\bm{F}}({ \bm{z}}_{\pi(t)})({\bm{z}}_{t+1/2}-{\bm{z}}_{t})))\\ &=\eta_{t}({\bm{F}}({\bm{z}}_{t+1/2})-{\bm{F}}({\bm{z}}_{t})-\nabla{\bm{F}}({ \bm{z}}_{t})({\bm{z}}_{t+1/2}-{\bm{z}}_{t}))+\eta_{t}(\nabla{\bm{F}}({\bm{z}}_ {\pi(t)}))-\nabla{\bm{F}}({\bm{z}}_{t}))({\bm{z}}_{t+1/2}-{\bm{z}}_{t})\end{split}$ (15) $$

Note that $\nabla{\bm{F}}$ is $\rho$-Lipschitz continuous.
Taking norm on both sides of (LABEL:eq:tt), we have that

$$ $\displaystyle\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\|$ $\displaystyle\leq\frac{\rho\eta_{t}}{2}\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t}\|^{2}+ \rho\eta_{t}\|{\bm{z}}_{\pi(t)}-{\bm{z}}_{t}\|\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t}\|$ $\displaystyle=\frac{\rho}{2M}\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t}\|+\frac{\rho}{M} \|{\bm{z}}_{\pi(t)}-{\bm{z}}_{t}\|,$ $$

which means

$$ $\displaystyle\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\|^{2}\leq\frac{\rho^{2}}{2M^{2} }\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t}\|^{2}+\frac{2\rho^{2}}{M^{2}}\|{\bm{z}}_{\pi( t)}-{\bm{z}}_{t}\|^{2}.$ $$

Plug the above inequality into the last term in (14).

$$ $\displaystyle\quad\eta_{t}\langle{\bm{F}}({\bm{z}}_{t+1/2}),{\bm{z}}_{t+1/2}-{ \bm{z}}\rangle$ $\displaystyle\leq\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}\|^{2}-\frac{1}{2}\|{\bm{z} }_{t+1}-{\bm{z}}\|^{2}-\frac{1}{2}\|{\bm{z}}_{t+1/2}-{\bm{z}}_{t+1}\|^{2}$ $\displaystyle\quad-\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}_{t+1/2}\|^{2}+\frac{\rho ^{2}}{2M^{2}}\|{\bm{z}}_{t}-{\bm{z}}_{t+1/2}\|^{2}+\frac{2\rho^{2}}{M^{2}}\|{ \bm{z}}_{\pi(t)}-{\bm{z}}_{t}\|^{2}.$ $$

∎

###### Proof.

## Appendix D Proof of Theorem 4.1

###### Proof.

When $m=1$, the algorithm reduces to the EG-2 algorithm [, , ]. When $m\geq 2$, we use Lemma 4.2 to bound the error that arises from lazy Hessian updates.

Define $r_{t}=\|{\bm{z}}_{t+1}-{\bm{z}}_{t}\|$.
By triangle inequality and Young’s inequality, we have

$$ $\displaystyle\quad\eta_{t}\langle{\bm{F}}({\bm{z}}_{t+1/2}),{\bm{z}}_{t+1/2}-{ \bm{z}}\rangle$ $\displaystyle\leq\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}\|^{2}-\frac{1}{2}\|{\bm{z} }_{t+1}-{\bm{z}}\|^{2}-\left(\frac{1}{4}-\frac{\rho^{2}}{2M^{2}}\right)\|{\bm{ z}}_{t}-{\bm{z}}_{t+1/2}\|^{2}$ $\displaystyle\quad-\left(\frac{1}{8}r_{t}^{2}-\frac{2\rho^{2}}{M^{2}}\left( \sum_{i=\pi(t)}^{t-1}r_{i}\right)^{2}\right).$ $$

For any $1\leq s\leq m$.
Telescoping over $t=\pi(t),\cdots,\pi(t)+s-1$, we have

$$ $\displaystyle\quad\sum_{t=\pi(t)}^{\pi(t)+s-1}\eta_{t}\langle{\bm{F}}({\bm{z}} _{t+1/2}),{\bm{z}}_{t+1/2}-{\bm{z}}\rangle$ $\displaystyle\leq\frac{1}{2}\|{\bm{z}}_{\pi(t)}-{\bm{z}}\|^{2}-\frac{1}{2}\|{ \bm{z}}_{\pi(t)+s}-{\bm{z}}\|^{2}-\left(\frac{1}{4}-\frac{\rho^{2}}{2M^{2}} \right)\sum_{t=\pi(t)}^{\pi(t)+s-1}\|{\bm{z}}_{t}-{\bm{z}}_{t+1/2}\|^{2}$ $\displaystyle\quad-\left(\frac{1}{8}\sum_{t=\pi(t)}^{\pi(t)+s-1}r_{t}^{2}- \frac{2\rho^{2}}{M^{2}}\sum_{t=\pi(t)+1}^{\pi(t)+m-1}\left(\sum_{i=\pi(t)}^{t- 1}r_{i}\right)^{2}\right).$ $$

Applying Lemma 4.2, we further have

$$ $\displaystyle\quad\sum_{t=\pi(t)}^{\pi(t)+s-1}\eta_{t}\langle{\bm{F}}({\bm{z}} _{t+1/2}),{\bm{z}}_{t+1/2}-{\bm{z}}\rangle$ $\displaystyle\leq\frac{1}{2}\|{\bm{z}}_{\pi(t)}-{\bm{z}}\|^{2}-\frac{1}{2}\|{ \bm{z}}_{\pi(t)+s}-{\bm{z}}\|^{2}-\left(\frac{1}{4}-\frac{\rho^{2}}{2M^{2}} \right)\sum_{t=\pi(t)}^{\pi(t)+s-1}\|{\bm{z}}_{t}-{\bm{z}}_{t+1/2}\|^{2}$ $\displaystyle\quad-\left(\frac{1}{8}-\frac{\rho^{2}s^{2}}{M^{2}}\right)\sum_{t =\pi(t)}^{\pi(t)+s-1}r_{t}^{2}.$ $$

Note that $s\leq m$. Let $M\geq 3\rho m$. Then

$$ $\displaystyle\quad\sum_{t=\pi(t)}^{\pi(t)+s-1}\eta_{t}\langle{\bm{F}}({\bm{z}} _{t+1/2}),{\bm{z}}_{t+1/2}-{\bm{z}}\rangle$ $\displaystyle\leq\frac{1}{2}\|{\bm{z}}_{\pi(t)}-{\bm{z}}\|^{2}-\frac{1}{2}\|{ \bm{z}}_{\pi(t)+s}-{\bm{z}}\|^{2}-\frac{1}{8}\sum_{t=\pi(t)}^{\pi(t)+s-1}\|{ \bm{z}}_{t}-{\bm{z}}_{t+1/2}\|^{2}.$ $$

Let $s=m$ and
further telescope over $t=0,\cdots,T-1$. Then

$$ $\displaystyle\sum_{t=0}^{T}\eta_{t}\langle{\bm{F}}({\bm{z}}_{t+1/2}),{\bm{z}}_ {t+1/2}-{\bm{z}}\rangle\leq\frac{1}{2}\|{\bm{z}}_{0}-{\bm{z}}\|^{2}-\frac{1}{2 }\|{\bm{z}}_{T}-{\bm{z}}\|^{2}-\frac{1}{8}\sum_{t=0}^{T}\|{\bm{z}}_{t}-{\bm{z} }_{t+1/2}\|^{2}.$ (16) $$

This inequality is the key to the convergence. It implies the following results. First, letting ${\bm{z}}={\bm{z}}^{*}$ and using the fact that $\langle{\bm{F}}({\bm{z}}_{t+1/2}),{\bm{z}}_{t+1/2}-{\bm{z}}^{*}\rangle\geq 0$ according to monotonicity of ${\bm{F}}$, we can prove the iterate is bounded

$$ $\displaystyle\|{\bm{z}}_{t}-{\bm{z}}^{*}\|\leq\|{\bm{z}}_{0}-{\bm{z}}^{*}\|, \quad{\rm and}\quad\|{\bm{z}}_{t}-{\bm{z}}_{t+1/2}\|\leq 2\|{\bm{z}}_{0}-{\bm{ z}}^{*}\|,\quad t=0,\cdots,T-1.$ $$

Then using triangle inequality, we obtain

$$ $\displaystyle\|{\bm{z}}_{t+1/2}-{\bm{z}}^{*}\|\leq 3\|{\bm{z}}_{0}-{\bm{z}}^{* }\|,\quad\forall t=0,\cdots,T-1.$ $$

Second, as (16) holds for all ${\bm{z}}\in{\mathbb{B}}_{\beta}({\bm{z}}^{*})$, Lemma
A.1 indicates

$$ $\displaystyle{\rm Gap}(\bar{\bm{x}}_{T},\bar{\bm{y}}_{T};\beta)\leq\frac{\|{ \bm{z}}_{0}-{\bm{z}}\|^{2}}{2\sum_{t=0}^{T-1}\eta_{t}}\leq\frac{9\|{\bm{z}}_{0 }-{\bm{z}}^{*}\|^{2}}{2\sum_{t=0}^{T-1}\eta_{t}}.$ (17) $$

Third, we can also use (16) to lower bound $\sum_{t=0}^{T-1}\eta_{t}$. (16) with ${\bm{z}}={\bm{z}}^{*}$ implies

$$ $\displaystyle\sum_{t=0}^{T}\gamma_{t}^{2}\leq 4M^{2}\|{\bm{z}}_{0}-{\bm{z}}^{* }\|^{2}.$ $$

By Holder’s inequality,

$$ $\displaystyle T=\sum_{t=0}^{T-1}\left(\eta_{t}\right)^{2/3}\left(\gamma_{t}^{2 }\right)^{1/3}\leq\left(\sum_{t=0}^{T-1}\eta_{t}\right)^{2/3}\left(\sum_{t=0}^ {T-1}\gamma_{t}^{2}\right)^{1/3}.$ $$

Therefore,

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}\geq\frac{T^{3/2}}{2M\|{\bm{z}}_{0}-{\bm{ z}}^{*}\|}.$ (18) $$

We plug in (18) to (17) and obtain that

$$ $\displaystyle{\rm Gap}(\bar{\bm{x}}_{T},\bar{\bm{y}}_{T};\beta)\leq\frac{9M\|{ \bm{z}}_{0}-{\bm{z}}^{*}\|^{3}}{T^{3/2}}.$ $$

∎

###### Proof.

## Appendix E Proof of Theorem 4.2

###### Proof.

Using the strongly monotonicity of operator ${\bm{F}}$ in (16), we obtain that

$$ $\displaystyle\sum_{t=0}^{T}\mu\eta_{t}\|{\bm{z}}_{t+1/2}-{\bm{z}}^{*}\|^{2} \leq\frac{1}{2}\|{\bm{z}}_{0}-{\bm{z}}^{*}\|^{2}-\frac{1}{2}\|{\bm{z}}_{T}-{ \bm{z}}^{*}\|^{2}.$ $$

Using Jensen’s inequality, for each epoch, we have

$$ $\displaystyle\|\bar{\bm{z}}_{T}-{\bm{z}}^{*}\|^{2}\leq\frac{\|{\bm{z}}_{0}-{ \bm{z}}^{*}\|^{2}}{2\mu\sum_{t=0}^{T-1}\eta_{t}}\leq\frac{M\|{\bm{z}}_{0}-{\bm {z}}^{*}\|^{3}}{\mu T^{3/2}}:=\gamma\|{\bm{z}}_{0}-{\bm{z}}^{*}\|^{2}.$ $$

Next, we consider the iterate $\{{\bm{z}}^{(s)}\}_{s=0}^{S-1}$. For the first epoch,
the setting of $T$ ensures $\gamma\leq 1/2$:

$$ $\displaystyle\|{\bm{z}}^{(1)}-{\bm{z}}^{*}\|^{2}\leq\frac{1}{2}\|{\bm{z}}_{0}- {\bm{z}}^{*}\|^{2}.$ $$

Then for the second one, it is improved by

$$ $\displaystyle\|{\bm{z}}^{(2)}-{\bm{z}}^{*}\|^{2}\leq\frac{\|{\bm{z}}^{(1)}-{ \bm{z}}^{*}\|^{3}}{2\|{\bm{z}}_{0}-{\bm{z}}^{*}\|}\leq\left(\frac{1}{2}\right) ^{1+3/2}\|{\bm{z}}_{0}-{\bm{z}}^{*}\|^{2}.$ $$

Keep repeating this process. We can get

$$ $\displaystyle\|{\bm{z}}^{(s)}-{\bm{z}}^{*}\|^{2}\leq\left(\frac{1}{2}\right)^{ q_{s}}\|{\bm{z}}_{0}-{\bm{z}}^{*}\|^{2},$ $$

where $q_{s}$ satisfies the recursion

$$ $\displaystyle q_{s}=\begin{cases}1,&s=1;\\ \dfrac{3}{2}q_{s-1}+1,&s\geq 2.\end{cases}$ $$

This implies

$$ $\displaystyle\|{\bm{z}}^{(s)}-{\bm{z}}^{*}\|^{2}\leq\left(\frac{1}{2}\right)^{ \left(\dfrac{3}{2}\right)^{s-1}+1}\|{\bm{z}}_{0}-{\bm{z}}^{*}\|^{2}.$ $$

Set $m=\Theta(d)$, LEAN-restart takes ${\mathcal{O}}(d^{2/3}\kappa^{2/3}\log\log(1/\epsilon))$ oracle to ${\bm{F}}(\cdot)$ and ${\mathcal{O}}((1+d^{-1/3}\kappa^{2/3})\log\log(1/\epsilon))$ oracle to $\nabla{\bm{F}}(\cdot)$.
Under Assumption 3.4, the computational complexities of the oracles is

$$ $\displaystyle{\mathcal{O}}\left(N\cdot d^{2/3}\kappa^{2/3}\log\log(1/\epsilon) +Nd\cdot(1+d^{-1/3}\kappa^{2/3})\log\log(1/\epsilon)\right)$ $\displaystyle={\mathcal{O}}\left((Nd+Nd^{2/3}\kappa^{2/3})\log\log(1/\epsilon) \right).$ $$

∎

###### Proof.

## Appendix F Proof of Corollary 4.1

###### Proof.

The computational complexity of inner loop can be directly obtained by replacing $\epsilon^{-1}$ by $\kappa$ in Theorem 4.3 such that

$$ $\displaystyle\text{ Inner Computational Complexity}=\tilde{{\mathcal{O}}}\left ((N+d^{2})\cdot(d+d^{2/3}\kappa^{2/3})\right).$ $$

The iterations of outer loop is $S=\log\log(1/\epsilon)$, thus, the total computational complexity of LEAN-restart is

$$ $\displaystyle S\cdot\text{ Inner Computational Complexity}=\tilde{{\mathcal{O} }}\left((N+d^{2})\cdot(d+d^{2/3}\kappa^{2/3})\right).$ $$

∎

###### Proof.

## Appendix G Computational Complexity Using Fast Matrix Operations

Theoretically, one may use fast matrix operations for Schur decomposition and matrix inversion [], with a computational complexity of $d^{\omega}$, where $\omega\approx 2.371552$ is the matrix multiplication constant. In this case, the total computational complexity of Algorithm 3 is

$$ $\displaystyle\tilde{\mathcal{O}}\left(\left(\frac{Nd+d^{\omega}}{m}+d^{2}+N \right)m^{2/3}\epsilon^{-2/3}\right)$ $$

Setting the optimal $m$, we obtain the following complexity of Algorithm 3:

$$ $\displaystyle\begin{cases}\tilde{\mathcal{O}}(d^{\frac{2}{3}(\omega+1)} \epsilon^{-2/3})~{}~{}(\text{with }m=d^{\omega-2}),&N\lesssim d^{\omega-1}\\ \tilde{\mathcal{O}}(N^{2/3}d^{4/3}\epsilon^{-2/3})~{}~{}(\text{with }m=N/d),&d ^{\omega-1}\lesssim N\lesssim d^{2}\\ \tilde{\mathcal{O}}(Nd^{2/3}\epsilon^{-2/3})~{}~{}(\text{with }m=d),&d^{2} \lesssim N.\end{cases}$ $$

Our result is always better than the ${\mathcal{O}}((Nd+d^{\omega})\epsilon^{-2/3})$ of existing optimal second-order methods.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: /
soundness: 3
strengths: 1. A new algorithm in min-max optimization with better computational complexity versus existing results.
2. The paper is well organized, the flow is easy to follow.
summary: This work proposed second-order algorithms LEN and LEN-restart for C-C and SC-SC min-max problems, these algorithms incorporate lazy Hessian update and Extragradient update, the computational cost analysis and numerical experiment results showed the outperformance of the proposed algorithms versus existing algorithms.
weaknesses: 1. The main component seems to be a combination of Doikov et al. (2023) on lazy Hessian and Adil et al., (2022) on extragradient, which may restrict the novelty a bit.
2. The experiment can be further enhanced. 
   - First, the $O(d^{1/3})$ improvement suggests the outperformance is valid in high-dimensional cases (while not in low-dimensional cases), now the experiment cannot exhibit such a pattern, how does the algorithm perform in low-dimensional case?
   - It is not clear how the choice of $m$ affects the performance, maybe you can follow Doikov et al. (2023) to add more experiments for clarification.
   - The theory part uses the gap function as the measurement, while the experiment uses the gradient norm or point distance, maybe you can add more clarification to rationalize your choice.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1) Is it possible to generalize the result in case strongly convex-strongly concave case with different constant of strong convexity/concavity?
2) Could you estimate the required accuracy for auxiliary problem that guarantee the desired precision for target problem? 
 I can make rating higher if you can positively answer for this questions.
soundness: 3
strengths: I guess the paper is good from mathematical point of view. The results is strong, original, well presented. I agree with authors that they developed significantly new tricks to work with this class of problems. I guess the paper is good!
summary: Authors generalize the results of Nikita Doikov, El Mahdi Chayti, and Martin Jaggi. Second-order optimization with lazy hessians. In ICML, 2023. related with lazy Hessian for Cubic regularized Newton method for Saddle-point problems (SPP). The developed result was cleary presented and sufficiently technical. Moreover, requires principally new ideas. However, the the motivation to consider second-order methods are quite limited and is mainly theoretical from my point of view. Also in the paper authors doesn't observe the accuracy required to solve auxiliary problem.
weaknesses: For me the main drawback is motivation. I do not understand why we should use second-order method with expensive iteration rather than the first-order one. I understand the motivation for convex optimization where the number of iteration significantly reduces by using optimal second-order scheme, but I do not understand it for SPP where the difference is minor.

---

confidence: 3
contribution: 2
initial_rating: 8
presentation: 3
questions: 1. Could you explain please, how did you get second inequality in eq. (17)?
1. Lines 155-160. Sentence "Their methods only take a lazy CRN update (2) at each iteration..." seems to me very weird. I needed to read it couple of times to understand. Please, rewrite in in more clear way.
soundness: 3
strengths: Authors propose a method with the same oracle complexity, as state-of-the-art methods but with less computational complexity. This means, that their algorithm can achieve the same estimation error with the same number of iterations, but overall spending less computational resources and taking less time. The experimental results only support this point. This makes method more attractive from the practical point of view. The paper is written in a clear way, and it is easy to understand.
summary: In this paper authors utilize the lazy Hessians technique inside second-order extragradient method for min-max optimization. The main idea of lazy Hessians technique is to update Hessian in second-order method only every $m$ iterations. Authors consider convex-concave and strongly-convex-strongly-concave setups. Authors claim, that if $m=\Theta(d)$ iterations, where $d$ is a dimension of the problem, their method achieves state-of-the-art computational cost.
weaknesses: Overall, the paper feels like a very incremental result. Authors employ a known technique to reduce number of Hessian computations to existing second-order method to solve convex-concave min-max problem. To adapt proposed method to strongly-convex-strongly-concave problem, authors use a universal restarts framework, that works like a "wrap" around any method for convex(-concave) problems and gives better theoretical convergence for strongly-convex(-strongly-concave). Despite the fact that this paper proposes a new method with better computational complexity compared to other analogs, it lacks any novel ideas or solution of any complex problems.

## Typos
1. Lines 785-786: it should be $\frac{m^2 + 2m}{2}$
1. Lines 862-863: upper index in the second sum should be $\pi(t) + s  - 1$
2. Definition 3.5: in the end it should be $||\hat z - z^*||\le \epsilon$

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: - In the proof of Theorem 4.1, what we essentially do is find an upper bound of
    $$ \begin{align*}
    \frac{1}{\sum_{i=0}^{t-1} \eta_i} \sum_{i=0}^{t-1} \eta_i \langle F(z_i),  z^{\star} - z_i\rangle
    \end{align*} $$
    which itself is an upper bound of the Gap function by Lemma A.1.
    
    My question is, can’t we just try to come up with an upper bound of the *MVI error* $\langle F(\hat{z}), z^{\star} - \hat{z} \rangle$ instead? If this works, it might be possible to extend the results to general MVIs. (I think one problem could be that we can’t use things like Jensen’s inequality if we step out of the convex-concave assumption.)
    
- Is the $\beta$ in Definition 3.4 just there for technical reasons (to ensure something like bounded iterates for the unconstrained case)?

- This might be a slightly irrelevant question, but any ideas of whether the proposed idea (or maybe the Lazy Hessian idea for minimization problems) could work for higher-order cases with $p \ge 3$?

- There seem to be complicated lower bound results in Adil et al. (2022) in terms of the *iteration* complexity. Can this naturally lead to some type of a lower bound in the *computational* complexity as well with which we can compare the new/previous upper bounds?

- Minor typo. In the middle of the inequality of Definition 3.3, I think it should be $f(x^{\star}, y^{\star})$.

**References.** \
Adil et al., 2022. Optimal methods for higher-order smooth monotone variational inequalities. \
Doikov et al., 2023. Second-order optimization with lazy Hessians. \
Lin et al., 2022. Explicit second-order min-max optimization methods with optimal convergence guarantee.
soundness: 3
strengths: - It is interesting to see that the idea of Doikov et al. (2023) can also work for minimax optimization problems.
- The paper seems to be well-written and clear, and there are empirical results supporting the theoretical arguments.
summary: This paper proposes a second-order algorithm designed for convex-concave minimax optimization problems. The algorithm brings the Lazy Hessian (or Lazy *Jacobian* for this paper, I guess) approach by Doikov et al. (2023) to second-order minimax optimization algorithms as in Adil et al. (2022), Lin et al. (2022). The new algorithm can achieve a computational complexity smaller by an order of $d^{1/3}$ compared to previous results both for the convex-concave case. The paper also shows superlinear convergence in the strongly-convex-strongly-concave case (by adding a restarting scheme) where we also have an improvement of $d^{1/3}$.
weaknesses: - The results only cover convex-concave minimax optimization for now, and there are no clear ways suggested to extend to broader problem classes like nonconvex-nonconcave functions or variational inequalities.
- As the main idea comes from combining two lines of previous work, it’s a bit hard to say that the ideas are highly original (except for the proof techniques of bounding the errors from lazy updates for the minimax case, particularly when there are EG steps in between).

Meta-review: This paper studies second-order methods for convex-concave minimax problem. In particular, the authors showed that the complexity result of previous work can be improved by reusing the Hessian information, which is called the lazy Hessians technique. Overall, the paper presents very novel results with better complexity and novel insights for second-order methods for minimax problem. This is of great importance to both optimization and machine learning community.

Decision: Accept (Oral)