Second-Order Min-Max Optimization with Lazy Hessians

[1] Lin T, Jordan MI. Perseus: A simple and optimal high-order method for variational inequalities. Mathematical Programming. 2024.

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

[3] Bullins B, Lai KA. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM Journal on Optimization. 2022.

[4] Daskalakis C, Skoulakis S, Zampetakis M. The complexity of constrained min-max optimization. In STOC, 2021.

[5] Diakonikolas J, Daskalakis C, Jordan MI. Efficient methods for structured nonconvex-nonconcave min-max optimization. In AISTATS, 2021.

[6] Lee S, Kim D. Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. In NeurIPS. 2021

[7] Chen L, Luo L. Near-optimal algorithms for making the gradient small in stochastic minimax optimization. arXiv preprint arXiv:2208.05925. 2022.

[8] Grimmer B, Lu H, Worah P, Mirrokni V. The landscape of the proximal point method for nonconvex–nonconcave minimax optimization. Mathematical Programming. 2023.

[9] Alacaoglu A, Kim D, Wright S. Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity. In ICML, 2024.

[10] 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.

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

[12] VE Shamanskii. A modification of newton’s method. Ukrainian Mathematical Journal, 19(1): 118–122, 1967.

In terms of the questions, we address them below:

Q1: In the proof of Theorem 4.1, can’t we just try to come up with an upper bound of the MVI error 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.)

We have provided a positive answer to this question in our response to W1. Our results can be easily extended to monotone variational inequalities by simply modifying the gap function as we have discussed.

Q2: Is the $\beta$ in Definition 3.4 just there for technical reasons (to ensure something like bounded iterates for the unconstrained case)?

Def 3.4 ensures the gap function is well-defined. If we do not restrict the gap function in a bounded domain, it can be undefined for simple convex-concave functions such as $f(x,y) = \langle x, y\rangle$.

Q3: 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=3$?

We think the idea of reusing Hessian can be applied to higher-order methods by reusing the $p$-th order derivatives and it will be an interesting future work.

Q4: 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?

The lower bound in computational complexity is a very difficult unaddressed problem. Indeed, it remains open almost for any problems. If we want to show computational lower bound for (second-order)optimization, we should first try to give lower bounds to basic linear algebra operations such as matrix multiplication. However, to the best of our knowledge, even for matrix multiplication there only exists a trivial $\Omega(d^2)$ lower bound, which is the size of the output matrix.

Q5: In the middle of the inequality of Definition 3.3, I think it should be $f(x^*,y^*)$.

Thanks for pointing it out. We have fixed the typo in the revision.

We greatly appreciate the feedback from the reviewer. Below, we address the concerns of the reviewer.

W1: 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.

The convex-concave setting considered in our paper is foundamental and forms the basis of broader problem classes like nonconvex-nonconcave functions or variational inequalities. And our result can be easily extended to several setups as the reviewer suggested.

• Our results can be easily extended to monotone variational inequalities (MVI) just by simply changing the definition of gap function to ${\rm Gap}(\hat z; \beta)= \max_{z \in \mathbb{B}_{\beta}(z^*)} \langle F(z) , \hat z - z \rangle$ as in [1-3]. Then we can also upper bound the MVI error using Jensen's inequality like Lemma 2.7 in [3] to extend our result to MVIs.
• Nonconvex-nonconcave functions are in general intractable [4], but our results can be extended to cohypomonotone nonconvex-nonconcave functions considered in some works [5-9]. For this function class, if we define the saddle envelope (see e.g. Def. 5.3 [7], or Sec. 2 [8]), then by Proposition 5.2 [7], the saddle envelope is convex-concave and its gradient and Hessian are computable (e.g. see Lemma 2.1, 2.4 [8]). Therefore, we can simply run our algorithm on the convex-concave envelope in this setup.

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

The idea of reusing Hessian is proposed in 1960s [12]. Doikov et al. showed the advantage of reusing Hessian on minimization problem. Compared to their work, we consider (S)C-(S)C minimax optimization, which is more general and difficult than the (strongly)-convex minimization problem.

Moreover, we have the following contributions compared with Doikov et al..

• We provide better complexity even for the strongly convex minimization. Our results in Section 4.2 can 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`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`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$.

In the revision, we also follow the suggestions of Reviewer 6zp1 to analyze an algorithm that allows inexact auxiliary cubic regularized Newton (CRN) sub-problem solving (see Appendix H). 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 $O(\log \log (1/\epsilon))$ number of linear system solving. In contrast, [2-3]'s naive binary search procedure requires $O(\log (1/\epsilon))$ iterations, which is worse than ours.

We greatly appreciate the feedback from the reviewer. Below, we address the concerns of the reviewer.

Weakness

For convex optimization, the optimal rates of first-order methods are $\mathcal{O}(\epsilon^{-\frac{1}{2}})$ [1], while for second-order methods are $\mathcal{O}(\epsilon^{-\frac{2}{7}})$ [2]. The gap of convergence rate in first-order and second-order methods is $\mathcal{O}(\epsilon^{-\frac{3}{14}})$.

For saddle point problems (SPP), the second-prder methods can achieve the convergence of $O(\epsilon^{-2/3})$, which is better than the $O(\epsilon^{-1})$ optimal rates of first-order methods. The gap of convergence rate in first-order and second-order methods is $\mathcal{O}(\epsilon^{-\frac{1}{3}})$, which is even larger than the one for convex optimization.

Hence, we do not think the difference in SPP is minor and we think there exists sufficient motivation for designing efficient second-order methods for SPP just like the motivation for convex optimization.

Questions

In terms of the questions, we address them below:

Questions 1: Is it possible to generalize the result in case strongly convex-strongly concave case with different constant of strong convexity/concavity?

For first-order algorithmsm, we can use the Catalyst acceleration to achieve near-optimal rates for (S)C-(S)C case with different constant of strong convexity/concavity [3]. It is open whether one can develop a second-order Catalyst and it will be an interesting future work.

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

We can simply modify our algorithm to an inexact version as follows. Recall our algorithm:

Our exact algorithm means taking

in the above equation. Similar to the case in [5], we can get the same convergence rate (ignoring the constant factor) if condition (1) is weaken to

We only need a few lines of modifications (see the purple text in Section D) to the proof of the exact algorithm to give the proof for the inexact algorithm. We present a self-contained section for the inexact algorithm in Appendix H, and we also design an efficient sub-procedure (Algorithm 5) to achieve the required accuracy of the auxiliary sub-problem to desired accuracy in only $\mathcal{O}(\log \log (1/\epsilon))$ number of linear system solving, which improves the $\mathcal{O}(\log (1/\epsilon))$ complexity of [4,5].

We thank the reviewer for his/her suggestion on the inexact algorithm. We are happy to make further updates if the reviewer has any other questions or suggestions.

[1] Nesterov Y. Lectures on convex optimization. Berlin: Springer; 2018.

[2] Arjevani Y, Shamir O, Shiff R. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming. 2019.

[3] Lin T, Jin C, Jordan MI. Near-optimal algorithms for minimax optimization. In COLT, 2020.

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

[5] Bullins B, Lai KA. Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM Journal on Optimization. 2022.

Thanks for your reply.

If we take the complexity of the first-order oracles as $\mathcal{O}(d^2)$ for min and min-max problems, the situation for the motivation of considering min- and min-max problems remains the same. We list the trade-off between $\epsilon^{-1}$ and $d$ for first and second order methods again:

• For the minimization problems, optimal second-order methods outperform optimal first-order methods when $d \lesssim \epsilon^{-\frac{3}{14}}$ ($d^3\epsilon^{-2/7}\lesssim d^2\epsilon^{-1/2}$).

• For the min-max problems, optimal second-order methods outperform optimal first-order methods when $d \lesssim \epsilon^{-\frac{1}{3}}$ ($d^3\epsilon^{-2/3}\lesssim d^2\epsilon^{-1}$). The region where second-order methods outperform first-order methods in min-max optimization is still larger than in minimization problems.

• For our methods for min-max problems, it outperforms optimal first-order methods when $d \lesssim \epsilon^{-1/2}$ ($d^3 + d^{8/3}\epsilon^{-2/3}\lesssim d^2\epsilon^{-1}$), which further enlarges the region.

We agree with you that we can also use $k^{-\alpha}$ as the criteria, but we kindly disagree that the choice of the criteria impact the motivation nor the contribution of this work. Again, we sincerely appreciate your helpful review and the support to our work!

We greatly appreciate the feedback from the reviewer. Below, we address the concerns of the reviewer.

Weakness

We kindly argue that the statement "this paper feels like a very incremental result" is not proper. Indeed, the idea of reusing Hessian is proposed in 1960s [3]. Doikov et al. showed the advantage of reusing Hessian on minimization problem. Compared to their work, we consider (S)C-(S)C minimax optimization, which is more general and difficult than the (strongly)-convex minimization problem. Employing such an idea to min-max problem and obtaining a better computation complexity itself requires new techniques in analysis such as (a) controlling the error of lazy Hessian led by the extra gradient step; (b) designing difficult subproblem to solve due to the absence of symmetric of $\nabla F(z)$.

Our results are also not incremental as we have the following contributions 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`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`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$.

In the revision, we also follow the suggestions of Reviewer 6zp1 to analyze an algorithm that allows inexact auxiliary cubic regularized Newton (CRN) sub-problem solving. We design an efficient sub-procedure (Algorithm 5) to solve the auxiliary sub-problem to the desired accuracy in only $\mathcal{O}(\log \log (1/\epsilon))$ number of linear system solving. In contrast, Doikov et al. supposes the CRN step is exactly computable and our results of the inexact algorithm may be of independent interest.

In terms of the typos, we appreciate your detailed review and have fixed them in revision.

[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] VE Shamanskii. A modification of newton’s method. Ukrainian Mathematical Journal, 19(1): 118–122, 1967.

Questions

In terms of the questions, we address them below:

Q1: Could you explain please, how did you get second inequality in eq. (17)?

Let $\beta = \Vert z_0 - z^* \Vert$. We take maximum over $z \in \mathbb{B}\_{3 \beta}(z^*)$ in the inequality of Lemma A.1, and then use eq. (15) to obtain

where the last step uses $\Vert z_0 - z \Vert \le \Vert z_0 - z^* \Vert + \Vert z - z^* \Vert \le 4 \beta$ for any $z \in \mathbb{B}_{3 \beta}(z^*)$.

We apologize that we missed the notation "$\max_{z \in \mathbb{B}_{3 \beta}(z^*)}$" in our submitted version. We have also fixed this typo in the revision.

Q2: 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.

We are grateful for the suggestions from the reviewer. In the revision, we have rewritten the sentence to: Their methods only take a lazy CRN update at each iteration, which makes it easy to bound the error of lazy Hessian updates using the Hessian Lipschitz assumption and the triangle inequality in the following way:

$

\Vert \nabla F(z_t)-\nabla F(z_{\pi(t)}) \Vert \leq \rho \Vert z_{\pi(t)}-z_t \Vert \leq \rho \sum_{i=\pi(t)}^{t-1} \Vert z_{i}-z_{i+1} \Vert .

$

I thank the authors for such an answer and the further improvement of the paper. I've got a minor question.

Q1

Am I correct, that you do not just take $\max_{z \in B_{3\beta}(z^*)}$ in Lemma A.1, but take $\min_{x \in B_{3\beta}(x^*)} \max_{y \in B_{3\beta}(y^*)}$ to get duality gap, and then you do $\min_{x \in B_{3\beta}(x^*)} \max_{y \in B_{3\beta}(y^*)} ||z_0 - z||^2 \le \max_{z \in B_{3 \beta}(z^*)} ||z_0 - z||^2$, due to convexity of squared norm?

Thanks for your prompt response and engagement in the discussion!

In terms of Q1, our proof uses the following relationship:

and then applies Lemma A.1. We should say "take maximum over $z \in B_{3 \sqrt{2} \beta}(z^*)$" instead of "take maximum over $z \in B_{3 \beta}(z^*)$". However, since it only differs by a constant factor of $\sqrt{2}$, it does not affect our result. We really appreciate your careful reading that helped us identify our typo. We are very glad to answer any other questions you may have.

Thanks for your reply. We use the fact that $-\min_{x \in B_{3\beta}(x^*)} f(x, \bar y_T) = \max_{x \in B_{3\beta}(x^*)}(- f(x, \bar y_T))$ in the second equality. We hope this can address your concern. Please also let us know if you have any further questions and we are very glad to answer them.

We greatly thank the reviewer for his/her detailed suggestions on our experiments, and we have enhanced the experiments following the suggestions.

1. First, the theory 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?

We add an additional experiment in low dimension $(d=10)$ in the revision. See Figure 1(a). In such case, the effect of using and not using the lazy Hessian is quite similar.

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

We present the impact of different values of $m$ on the algorithm performance in Figure 1.

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

Although the theory part uses the gap function as the measurement, the duality gap is difficult to compute in practice. Therefore, we use the gradient norm as an alternative measurement. The gradient norm is also a valid measurement because a small gradient norm can imply a small gap due to the Cauchy–Schwarz inequality $\langle F(z),z-z^*\rangle \le \Vert F(z) \Vert \Vert z - z^* \Vert$. Below, we list some works that also use the duality gap in theory but use gradient norm in experiments [2-4].

The convergence of point distance $\Vert z - z^* \Vert$ for convex(-concave) optimization is impossible in general due to the lower bound (see the second inequality in Theorem 2.1.7 [1]). However, we observe the convergence on Problem (11), which indicates that this problem has a special structure. We think it is an interesting finding and thus also present it in our paper.

[1] Nesterov Y. Lectures on convex optimization. Berlin: Springer; 2018.

[2] Alves MM, Svaiter BF. A search-free $\mathcal{O}(1/k^{3/2})$ homotopy inexact proximal-Newton extragradient algorithm for monotone variational inequalities. arXiv preprint arXiv:2308.05887. 2023.

[3] Kevin Huang, Shuzhong Zhang. An Approximation-Based Regularized Extra-Gradient Method for Monotone Variational Inequalities. arXiv 2210.04440. 2022.

[4] Jiang R, Kavis A, Jin Q, Sanghavi S, Mokhtari A. Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization. In NeurIPS, 2024.

We greatly appreciate the feedback from the reviewer. Below, we address the concerns of the reviewer on weakness 1 "The main component seems to be a combination of Doikov et al. on lazy Hessian and Adil et al. on extragradient, which may restrict the novelty a bit."

In terms of novelty, we are indeed inspired by the Doikov et al., as we discussed in the manuscript. However, we kindly argue that the combination of Doikov et al. on lazy Hessian and Adil et al. on extragradient is non-trivial as we need to control the error of lazy Hessian led by the extra gradient step.

Moreover, we have the following contributions compared with Doikov et al..

• We provide better complexity even for the strongly convex minimization. Our results in Section 4.2 can 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`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`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$.

In the revision, we also follow the suggestions of Reviewer 6zp1 to analyze an algorithm that allows inexact auxiliary cubic regularized Newton (CRN) sub-problem solving (see Appendix H). In contrast, Doikov et al. supposes the CRN step is exactly computable. Additionally, we also design an efficient sub-procedure (Algorithm 5) to to achieve the required accuracy of the auxiliary sub-problem in $O(\log \log (1/\epsilon))$ number of linear system solving. In contrast, Adil et al.'s binary search procedure requires $O(\log (1/\epsilon))$ iterations, which is worse than ours.

[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)$. In Dokl akad nauk Sssr, 1983.