Second-Order Min-Max Optimization with Lazy Hessians

Authors: Lesi Chen, Chengchang Liu, Jingzhao Zhang
Primary area: optimization
Keywords: min-max optimization; second-order methods; computational complexity

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

Decision: accept (oral)
Reviewer scores: 8, 8, 8, 6

Reviews and discussion:
<thread>
creation date:
1730017669909

thread_type:
official_review

<thread_object>
creator: reviewer_latj

<content>
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}$.

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.

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).

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730566896808

thread_type:
official_review

<thread_object>
creator: reviewer_qgt2

<content>
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.

strengths:
Authors propose a method with the same oracle complexity, as state-of-the-art methods but with less computational complexity. This means, that their algorithm can achieve the same estimation error with the same number of iterations, but overall spending less computational resources and taking less time. The experimental results only support this point. This makes method more attractive from the practical point of view. The paper is written in a clear way, and it is easy to understand.

weaknesses:
Overall, the paper feels like a very incremental result. Authors employ a known technique to reduce number of Hessian computations to existing second-order method to solve convex-concave min-max problem. To adapt proposed method to strongly-convex-strongly-concave problem, authors use a universal restarts framework, that works like a "wrap" around any method for convex(-concave) problems and gives better theoretical convergence for strongly-convex(-strongly-concave). Despite the fact that this paper proposes a new method with better computational complexity compared to other analogs, it lacks any novel ideas or solution of any complex problems.

## 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$

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730583284461

thread_type:
official_review

<thread_object>
creator: reviewer_6zp1

<content>
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.

strengths:
I guess the paper is good from mathematical point of view. The results is strong, original, well presented. I agree with authors that they developed significantly new tricks to work with this class of problems. I guess the paper is good!

weaknesses:
For me the main drawback is motivation. I do not understand why we should use second-order method with expensive iteration rather than the first-order one. I understand the motivation for convex optimization where the number of iteration significantly reduces by using optimal second-order scheme, but I do not understand it for SPP where the difference is minor.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730729204946

thread_type:
official_review

<thread_object>
creator: reviewer_z87q

<content>
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.

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.

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.

questions:
/
</content>
</thread_object>

</thread>
<thread>
creation date:
1732107122960

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response to all the Reviewers

comment:
We thank all the reviewers for their valuable and constructive comments. Overall, we appreciate that all the reviewers acknowledged our contributions in proving a better computational complexity for second-order min-max optimization. 

One common concern of the reviewers is the comparison with Doikov et al. which analyzes lazy Hessian method in minimzation problems. We highlight the following novelty and contributions of our work compared with Doikov et al..

- **We provide better complexity even for the strongly convex minimization.** Our results can in Section 4.2 be applied to solve strongly convex minimization problem as considered in Doikov et al. Doikov et al. gives the iteration complexity of $\tilde{\mathcal{O}}(m^2L_2^2/\mu^3)$ (Corollary D.4 in Doikov et al.). Our result of $\tilde{\mathcal{O}}(m^{2/3}L_2^{2/3}/\mu^{2/3})$ is strictly better than theirs.
- **We provide novel insights on the optimality of the second-order methods.** Our results show that the optimal second-order methods in terms of the oracle complexity are not optimal in terms of the computation complexity. Doikov et al. finds the $(\epsilon,\sqrt{d\epsilon})$ stationary point for non-convex minimization problem which is weaker than the $(\epsilon,\sqrt{\epsilon})$ stationary point that the standard cubic regularized Newton method finds. Chayti et al. finds $f(x)-f^*\leq \epsilon$ with computational cost of $\mathcal{O}(d^{1/2}\epsilon^{-1/2}\cdot\texttt{Gradcost})$, whose dependency on $\epsilon$ cannot match the optimal second-order methods $\mathcal{O}(\epsilon^{-2/7})$ [1], and is strictly worse than the $\mathcal{O}(\epsilon^{-1/2}\cdot\texttt{Gradcost})$ of AGD (accelerated gradient descent [2]). In contrast, our computational complexity bound on $\epsilon$ matches the **optimal** second-order methods for minimax optimization, while reducing their dependency on $d$.

Moreover, we have enhanced our paper by following the suggestions from the reviewers.

- **We have analyzed an algorithm that allows inexact auxiliary cubic regularized Newton (CRN) sub-problem solving following the suggestions from Reviewer 6zp1  (see the new Appendix H) .**
We show that the desired accuracy of the sub-problem is dynamic such that
$$
M \Vert z_t - z_{t+1/2} \Vert \le \gamma_t \le 2 M \Vert z_t - z_{t+1/2} \Vert, ~~~~~~~ \text{(see Algorithm 4)}
$$
which can be satisfied within $\mathcal{O}(\log \log (1/\epsilon))$ numbers of linear system solving (the linear system  can be solved within $\mathcal{O}(d^2)$ time, please refer to line 378-line 397 in Section 4.3). In contrast, Doikov et al. supposes the CRN step is exactly computable. **Additionally**, we also design an efficient sub-procedure (Algorithm 5) to achieve the required accuracy of the auxiliary sub-problem in only $\mathcal{O}(\log \log (1/\epsilon))$ number of linear system solving. In contrast, [3-4]'s naive binary search procedure requires $\mathcal{O}(\log (1/\epsilon))$ iterations, which is worse than ours. 

- **We have enhanced the experiments following the suggestions from Reviewer Z87Q (see the updated Figure 1).** We have included additional experiments in low dimension $(d=10)$ and ablation study on the effect of hyperparamter $m$.

We have also addressed all other issues raised by the reviewers. We hope that the reviewers will engage with us in a back-and-forth discussion and we will be very happy to answer any further questions.

[1] Monteiro RD, Svaiter BF. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization. 2013.

[2] Nesterov Y. A method for solving the convex programming problem with convergence rate $\mathcal{O} (1/k^2)$. InDokl akad nauk Sssr, 1983.

[3] Adil D, Bullins B, Jambulapati A, Sachdeva S. Optimal methods for higher-order smooth monotone variational inequalities. arXiv preprint arXiv:2205.06167. 2022.

[4] Bullins B, Lai KA. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM Journal on Optimization. 2022.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.