Extragradient Method for $(L_0, L_1)$-Lipschitz Root-finding Problems

We thank the reviewer for a positive evaluation of our work and for providing us with valuable questions and comments. We respond to the questions and concerns below.

Weakness

I am not entirely sure of the exact algorithm used in implementations and also the one analyzed. Maybe an algorithm box would help.] + [...A complete algorithm box would certainly help...

That is an excellent suggestion. We will incorporate that in the updated version of the paper.

Questions

Also the paper only talks about EG methods. It is not clear if there are other existing works based on other methods that show...

In this work, we analyze the extragradient (EG) algorithm under the $\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption. To the best of our knowledge, [1] is the only work that analyzes extragradient, past extragradient, and the projection method under this assumption. We have included a comparison with this work for EG, and we will include the comparison with the other two algorithms in the updated version.

It is not clear what the main challenge is with generalizing the EG methods to this setting. Maybe a bit more description on this would help.

In this work we analyze the extragradient method under the $\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, which involves a more general bound of the form $L_0 + L_1 \max_{\theta \in [0,1]} \| F(\theta x + (1 - \theta) y) \|^{\alpha}$ instead of the standard Lipschitz constant L. This generalization makes the analysis significantly more challenging. For example, in the standard L-Lipschitz case, one can easily bound $\| F(x_k) - F(\hat{x}_k) \|^2$ by $L^2 \| x_k - \hat{x}_k \|^2$, which appears in line 9 of the proof of Theorem 3.2 (Appendix page 24). However, under the $\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, it introduces a much involved term, which complicates the analysis.

This difficulty motivates the use of an adaptive step size of the form $\eta / (L_0 + L_1 \|F(x_k)\|^{\alpha})$, which is better suited for this setting. Moreover, throughout the analysis, several steps require us to carefully use the structure of the $\alpha$-symmetric Lipschitz condition and develop proof techniques that differ from those used under the standard Lipschitz assumption.

We hope this clarifies the technical challenges involved in working under this more general setup. We can easily include this discussion in the updated version of our submission.

We hope we have addressed all the questions and concerns of the reviewer. In our opinion, all concerns raised are clarification points and not really weaknesses of our work. If you agree, please consider increasing your score. If not, please let us know so we can respond accordingly.

References

[1] Vankov, Daniil, Angelia Nedich, and Lalitha Sankar. "Generalized smooth variational inequalities: Methods with adaptive stepsizes." Forty-first International Conference on Machine Learning. 2024.

We thank the Reviewer bk47, for reading our work carefully and providing us with a valuable review. We respond to the questions and concerns raised by the reviewer below.

Weaknesses

....This makes comparisons with prior work, particularly [Vankov 2024] somewhat misleading....

Thanks for the suggestion. We use unconstrained variational inequalities because they are extensively used as terminology in several papers over the last few years. This paper provides an analysis of the extragradient method under $\alpha$-symmetric $(L_0, L_1)$ Lipschitz assumption, and to the best of our knowledge, [1] is the only prior work that addresses this, even if in a different setting (constrained VIPs). We intended to ensure that we provide proper credit and offer a fair comparison with existing literature.

The authors focus only on extragradient. It would be nice to see if this analysis applies to similar methods, e.g. KM iteration, optimistic gradient method

We do not view this as a weakness of our work. Prior to this, even the convergence behavior of the extragradient method under generalized Lipschitz conditions was not fully understood. In this paper, we improve the convergence rate for strongly monotone problems and provide the first analysis for monotone and weak Minty problems under $\alpha$-smmteric $(L_0, L_1)$ Lipschitz assumptions. These results lay the groundwork for extending the analysis to more advanced algorithms such as the optimistic gradient method and KM iteration. We appreciate the reviewer’s suggestion, and exploring such extensions is indeed on our research agenda.

Typically, in the limited conference space, a paper can focus on one algorithm and understand the behavior in depth in different important settings, or focus on a setting and explore the behavior of different algorithms. Having several methods in all different settings can be quite challenging in a limited number of pages with a proper exposition.

It would also be good to see some discussion of, and comparison to Halpern-style methods [Park & Ryu].

Thank you for the suggestion. We will include a discussion in the updated version comparing our results with the Halpern iteration method [2]. However, this is not a weakness of our work. We would like to emphasize that [2] analyzes under the standard L-Lipschitz assumption, whereas our analysis is conducted under the more general $\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption. Therefore, the settings are not directly comparable.

Although the new step-size rule is nice, it requires knowing three parameters (L_0, L_1, \alpha) of F....

Yes, Reviewer bk47 is correct in observing that solving this more general class of problems requires knowledge of three parameters, in contrast to standard L-Lipschitz settings. However, this is not a limitation of our work. The problem class we consider is significantly more general and complex, and thus naturally demands more information for effective algorithm design and analysis. That said, developing methods that do not require prior knowledge of these parameters, i.e., tuning-free algorithms for this broader class of problems, is an exciting direction for future research.

Typos

We appreciate the reviewer for carefully reviewing the appendix and identifying the typos. We agree with all the typos mentioned and will make the necessary corrections in the updated version.

Questions

How easily do your results extend to the true VI problem, where there is a non-trivial constraint set?

Extending the algorithm to handle non-trivial constraint sets would require significant modifications. In particular, solving the constrained version would involve incorporating projections in both the extrapolation and update steps. Additionally, the presence of projections would also affect the step size choices in that scenario.

For these reasons, we focus on the unconstrained setting in this work, as it lays the theoretical groundwork and provides key insights that can facilitate the analysis of more complex algorithms for constrained problems in the future. It is definitely on our to-do list to extend the analysis to a constrained setting in the future.

Could you apply your analysis to, say, the optimistic gradient method?

As mentioned earlier, this is one of the directions we intend to explore in future work. We firmly believe that our proof technique can be extended to analyze the optimistic gradient method and KM iterations under the $\alpha$-symmteric $(L_0, L_1)$ Lipschitz assumption.

Is there a reason for choosing to focus on ...

Thank you for the question. The $\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption was introduced because many deep learning problems appear to satisfy this condition empirically in the minimization setting with the operator replaced by the gradient of the objective function. We provide a detailed discussion motivating this assumption between lines 32–65 in the introduction, along with illustrative examples in Section 2.2. Our analysis under this assumption is purely motivated by its relevance and empirical support in practical scenarios.

I'm not familiar with the weak Minty condition. Could you provide some intuition for why this is interesting?..

The weak Minty condition was first introduced in [4]. General unconstrained variational inequality problems are known to be computationally intractable, which has motivated the search for structural assumptions that allow for meaningful convergence guarantees. Among the known conditions, the weak Minty condition is currently the most relaxed assumption under which convergence of algorithms can be established.

In the proof of Theorem 3.4, in the ninth line, I believe there is a sign error.

Thank you for the pointer. The expressions in lines 9 and 10 contain a typo, which is corrected in line 11 of the same proof. As a result, this does not affect any of the constants appearing in the final result of Theorem 3.4. We will correct the typo in the updated version of the paper.

..so I suggest you package them into a lemma...

Thanks for the suggestion. We will incorporate this in the revised version of the paper.

We hope we have addressed all the questions and concerns of the reviewer. If you agree, please consider increasing your score. If not, please let us know so we can respond accordingly.

References

[1] Vankov, Daniil, Angelia Nedich, and Lalitha Sankar. "Generalized smooth variational inequalities: Methods with adaptive stepsizes." Forty-first International Conference on Machine Learning. 2024.

[2] Park, Jisun, and Ernest K. Ryu. "Exact optimal accelerated complexity for fixed-point iterations." International Conference on Machine Learning. PMLR, 2022.

[3] Zhang, Jingzhao, et al. "Why gradient clipping accelerates training: A theoretical justification for adaptivity." arXiv preprint arXiv:1905.11881 (2019).

We thank the reviewer for the positive evaluation of our work. We address the questions and concerns raised by the reviewer below.

Weaknesses

...The extension may not be trivial, but it seems like something that could be expected.... + .... Is there a significant technical difficulty compared to the function minimization problem or the standard Lipschitz ..]

Thank you for the question. Compared to the literature in the minimization setting, our submission solves unconstrained variational inequality problems with the extragradient method. Our submission has no notion of functional values in contrast to the minimization analysis, and moreover, the extragradient method has an extrapolation step, which introduces further challenges. The proof technique of analyzing the extragradient methods is very different from the methods used in minimization problems.

Compared to the analysis of extragradient method under Lipschitz assumption, this new assumption introduces further challenges. In the submission we have, the $\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, which involves a more general bound of the form $L_0 + L_1 \max_{\theta \in [0,1]} \| F(\theta x + (1 - \theta) y) \|^{\alpha}$ instead of the standard Lipschitz constant L. This generalization makes the analysis significantly more challenging. For example, in the standard L-Lipschitz case, one can easily bound $\| F(x_k) - F(\hat{x}_k) \|^2$ by $L^2 \| x_k - \hat{x}_k \|^2$, which appears in line 9 of the proof of Theorem 3.2 (Appendix page 24). However, under the $\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, it introduces a much involved term, which complicates the analysis.

This difficulty motivates the use of an adaptive step size of the form $\eta / (L_0 + L_1 \|F(x_k)\|^{\alpha})$, which is better suited for this setting. Moreover, throughout the analysis, several steps require us to carefully use the structure of the $\alpha$-symmetric Lipschitz condition and develop proof techniques that differ from those used under the standard Lipschitz assumption.

Questions

...the authors state that the results in their paper recover the result in [Gorbunov et al., 2022b]. However, as the title of the cited paper suggests...]** Thank you for the question. Although [1] only emphasizes last-iterate convergence in its title, which is indeed their main contribution, the paper also provides an ergodic convergence rate, as stated in Theorem 3.1. We hope this clarifies the confusion, and we will include this clarification in the updated version of the submission.

We hope we have addressed all the questions and concerns of the reviewer. If not, please let us know so we can respond accordingly.

References

[1] Gorbunov, Eduard, Nicolas Loizou, and Gauthier Gidel. "Extragradient method: O (1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

We thank the reviewer for a positive evaluation and for providing us with valuable feedback. We address the questions and concerns raised by the reviewer below.

Weaknesses

.... For example, [3] proposes an approach that estimates L0 locally....

We are not sure which paper the reviewer is referring to with [3] in this context. We agree that it would be highly valuable to develop a fully adaptive algorithm for this general class of problems. However, we would like to emphasize that even the analysis of such problems, assuming knowledge of $(L_0, L_1, \alpha)$, has been missing in several important settings. Our current work addresses this gap, and in future work, we aim to extend the analysis further and explore techniques for estimating these constants in practice.

.... It seems that most of related works cited in the main text appear to focus on the (L0,L1)-smooth and α-symmetric assumption, rather than on method-level analyses...

Thank you for the suggestion. Indeed, our related work section is primarily organized around the assumptions rather than the methods. This is because, to the best of our knowledge, there are no prior works analyzing algorithms under the $\alpha$-symmetric $(L_0, L_1)$-Lipschitz assumption, except for [1], which we have referenced multiple times. That said, we agree it would be helpful to include a broader discussion. In the revised version, we can easily add a section in the appendix reviewing methods developed in the minimization setting that are analyzed under the $\alpha$-symmetric $(L_0, L_1)$-smoothness assumption.

.... While the paper is primarily theoretical—so this may not be a major concern—it seems that most experiments were conducted on synthetic data. ...

Yes, the primary focus of this work is to strengthen the theoretical foundations for this general setting. Our current experiments are designed to demonstrate the advantage of using step sizes of the form $1 / (c_0 + c_1 \| F(x_k) \|^{\alpha})$ over constant step sizes. We will include additional experiments in the updated version to validate the effectiveness of our algorithm further.

Typos

We thank the reviewer for carefully reading our work and pointing out the typos. We will fix them in the updated version of the paper.

Questions

What are the problem parameters (L0,L1, α) of equation (19)? ...

In Appendix D2, we explained a way to compute these values in a simplified setting.

The choice of stepsize differs significantly depending on whether α = 1 or not. However, in practice, α is typically unknown. Given only a problem instance, how should one select an appropriate stepsize?

At present, for general problems, one can only consider sweeping over different values of $\alpha$ and check which one performs best. However, our future goal is to develop methods for estimating the parameter $\alpha$, which we believe will be a significant contribution to the literature.

We hope we have addressed all the questions and concerns of the reviewer. If not, please let us know so we can respond accordingly.

References

[1] Vankov, Daniil, Angelia Nedich, and Lalitha Sankar. "Generalized smooth variational inequalities: Methods with adaptive stepsizes." Forty-first International Conference on Machine Learning. 2024.

We thank the reviewer for their insightful comments and suggestions. Our detailed responses are provided below.

Weaknesses

[In the strongly monotone .... it is a relatively minor change.....] We respectfully disagree with the reviewer’s comment. In optimization, practical interest typically lies in obtaining high-accuracy solutions, i.e., small values of $\epsilon$. In such cases, any significant constant multiplying the $\log(1/\epsilon)$ term can have a substantial impact on the convergence rate.

To illustrate this, consider the well-known comparison between Gradient Descent and Accelerated Gradient Descent for smooth, strongly convex functions. Gradient Descent achieves a rate of $O\left(\frac{L}{\mu} \log(1/\epsilon)\right)$, while Accelerated Gradient Descent achieves $O\left(\sqrt{\frac{L}{\mu}} \log(1/\epsilon)\right)$. The difference between $\frac{L}{\mu}$ and $\sqrt{\frac{L}{\mu}}$ leads to huge improvements in performance, especially as higher accuracy is desired.

In our setting, removing the exponential dependence on the initial distance to the solution from the convergence rate and moving it into a constant factor is a meaningful theoretical improvement. The exponential factor can be arbitrarily large depending on the initialization, and its removal explains the performance of the algorithm in practice. Moreover, in experiments, we show improvement with our proposed step size compared to the prior work (check figure 3a, 3b). We hope this clarifies the significance of our result.

.... for weak Minty variational inequalities, though the convergence is only local....

We agree that the assumption on $\rho$ for weak Minty problems is currently restrictive. However, this is the first analysis conducted under the $\alpha$-symmetric $(L_0, L_1)$ Lipschitz assumption for this class of problems, and we believe it lays the groundwork for further theoretical developments in this direction.

However, a number of the results are only minor improvements....] + [it feels more incremental than a major new direction of research.

We disagree with this statement. As mentioned in the previous response, the improvement in the strongly monotone setting is not minor. Moreover, we provide the first analysis in a monotone and weak Minty setting.

It would also be nice if there was a brief discussion or conclusion section added to this work discussing potential future directions.

We were unable to do that due to space constraints. Thanks for the suggestion, and we will include it in the updated version.

Questions

.... Are there any conditions under which this exponential dependence may vanish ...

Thank you for the insightful question. We would like to clarify that the convergence analysis of our proposed algorithms fundamentally relies on the equivalent formulation in Proposition 3.1. This formulation introduces the exponential dependence you noted, and we currently do not believe it is possible to eliminate this term entirely from the convergence rate. We can only improve how this term appears in the rate and minimize its impact on the convergence rate.

As mentioned in our earlier response, in the strongly monotone case, we show that the exponential dependence no longer appears as a multiplicative factor to the $O(\log(1/\epsilon))$ term, but rather as an additive constant. As explained earlier, this is not a minor improvement. We agree with the reviewer that, in the weak Minty setting, the condition on $\rho$ is currently restrictive. However, we believe that the dependence of $\rho$ on the exponential term can be improved even in the weak minty setting, and we view this as an important direction for future research.

For the weak Minty experiment, do the methods struggle when started far from the solution?...

That is an excellent suggestion. We can easily include such experimental evaluation in the camera-ready version of our work to visually verify our theoretical findings.

In the theoretical results, the adaptive stepsize is dependent on the constant $\alpha$ in the $\alpha$-symmetric assumption, however in the numerical experiments, $\alpha = 1$ is used throughout....

Indeed, for our proposed experiments, we used $\alpha = 1$ as all problems satisfy the $1$-symmetric $(L_0, L_1)$ assumption. Let us highlight that the primary goal of our experiments is to demonstrate the benefit of using the adaptive step size $1/(c_0 + c_1 \|F(x_k)\|^{\alpha})$ over the constant step size typically used in the extragradient method. In our experiments, we show that our proposed step-size selection with $\alpha = 1$ yields better performance than the constant step size. That said, we agree that exploring different values of $\alpha$ may lead to further improvements. We can easily include additional experiments to investigate the impact of varying $\alpha$ in the updated version of our paper.

We hope we have addressed all the questions and concerns raised by Reviewer 4hmy. We believe that most concerns raised can be easily addressed in the updated version of our work (not major issues). If you find our clarifications satisfactory, please consider increasing your score. If not, we would appreciate the opportunity to respond further.

Dear Reviewer,

Thanks for the follow-up question and for the positive evaluation of our work.

While I agree that root finding problems are common in the literature, are there many known examples where L-Lipschitz continuity (or Holder continuity) does not hold?

The AC has already reached out to us, mentioning your question and some follow-up clarification.

Please have a look at the long response to the AC. There, we explain that several minimization and min-max problems are not L-Lipschitz to motivate our new condition, and we point out some basic constructed examples of root finding problems, already included in our paper, that are not L-Lipschitz but that satisfy our $(L_0, L_1)$-Lipschitz condition (to justify further the need for our new condition).

are there alternative conditions to $\alpha$ -symmetric $(L_0, L_1)$ (e.g. Holder smooth) that are relaxations of the standard L-Lipschitz continuity used in most works that would not inevitably lead to such an exponential dependence? I understand this is likely outside the scope of this work, but some discussion of other relaxations of L-Lipschitz continuity in root finding problems is likely warranted

Thank you for the suggestion. We will make sure to include such a comparison in the camera-ready version of our work.

Thanks again for the support of our work.

Best, Authors

Dear AC,

Thank you for your engagement and for asking a valuable question.

some motivating examples for root-finding problems, coming from applications

Finding the saddle point of an unconstrained minimization problem $\min_{x \in \mathbb{R}^d} f(x)$ is a simple example of a root-finding problem, where the operator is given by $F = \nabla f$.

Beyond minimization, any unconstrained smooth min-max optimization problem can be formulated as a root-finding problem. Consider the unconstrained problem $\min_u \max_v L(u, v)$, where $L$ is differentiable in both variables but may be nonconvex in $u$ (for fixed $v$) and nonconcave in $v$ (for fixed $u$). Defining $x = (u, v)$ and $F(x) = (\nabla_u L(u, v), − \nabla_v L(u, v))$, the first-order optimality condition becomes

which is a root-finding problem. Such formulations arise in many practical settings, including:

• Reinforcement Learning (equation 10 in [1]),
• Generative Adversarial Network training ([2], equation 1 in [3]),
• Robust Least Squares (equation 8 in [4]), and
• Constrained minimization via Lagrangian formulation [5].

Apart from unconstrained smooth min-max problems, root-finding problems are also important for $N$-player games (section 3.1 in [6]), in particular for multi-agent reinforcement learning (equation 4.5 in [7]). Additionally, fixed-point problems of the form “find $x_*$ such that $x_* = T(x_*)$,” which are common across various fields, can be reformulated as root-finding problems by defining $F(x) = x - T(x)$.

I also agree with Reviewer bk47 that for unconstrained problems, the terminology VI is misleading

We adopted the terminology of unconstrained variational inequality problems (VIPs) following prior works in the literature [8, 9] (also noted by Reviewer bk47 in their last response). However, we are happy to revise the introduction to emphasize the root-finding perspective instead, and we are willing to update the title accordingly.

References

[1] Du, Simon S., et al. "Stochastic variance reduction methods for policy evaluation." International conference on machine learning. PMLR, 2017.

[2] Goodfellow, Ian J., et al. "Generative adversarial nets." Advances in neural information processing systems 27 (2014).

[3] Daskalakis, Constantinos, et al. "Training gans with optimism." arXiv preprint arXiv:1711.00141 (2017).

[4] Yang, Junchi, Negar Kiyavash, and Niao He. "Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems." Advances in neural information processing systems 33 (2020): 1153-1165.

[5] Boyd, S., Boyd, S. P. & Vandenberghe, L. Convex optimization (Cambridge university press, 2004).

[6] Azizian, Waïss, et al. "A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games." International conference on artificial intelligence and statistics. PMLR, 2020.

[7] Zhang, Kaiqing, Zhuoran Yang, and Tamer Başar. "Multi-agent reinforcement learning: A selective overview of theories and algorithms." Handbook of reinforcement learning and control (2021): 321-384.

[8] Gorbunov, Eduard, Nicolas Loizou, and Gauthier Gidel. "Extragradient method: O (1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity." In International Conference on Artificial Intelligence and Statistics, pp. 366-402. PMLR, 2022.

[9] Diakonikolas, Jelena, Constantinos Daskalakis, and Michael I. Jordan. "Efficient methods for structured nonconvex-nonconcave min-max optimization." In International Conference on Artificial Intelligence and Statistics, pp. 2746-2754. PMLR, 2021.

Dear Authors,

Thanks for your reply! Overall, I wanted to hear about specific problems rather than other generic problem formulations that you mostly pointed out. For example by specific problem, I mean a problem such as $\min_x \| x\|_1: \|Ax-b\|\leq \delta$. Can you please provide some specific problems with specific functions to motivate your setting? These applications shouldn't be simple minimization because for minimization problems, we already have many other methods to use, so we wouldn't formulate them as a root-finding problem.

1. Can you please explain how Constrained minimization via Lagrangian formulation would fit in your template? Unless the problem is minimizing a smooth $f$ over $Ax=b$, you will have either nonsmoothness in $f$ (say, l1 norm) or constraints appearing in the dual (with inequality constraints). For the former template, the only example that comes to mind is $\min_x \|x\|^2: Ax=b$ which is not very interesting since one can just solve $\min_x \|Ax-b\|^2$ instead. If you can find a smooth loss where one needs L0-L1 and then show that with linear constraints $Ax=b$, the problem is still interesting. Then if you can show your L0-L1 assumption holds, this can be a specific example problem.

2. The example in [1] comes from a least squares problem, I am not sure: why would one not solve the minimization problem which is very simple in that case?

3. For [6], the only example they have for the template is the standard bilinar problem from Example 1 in [6] which is mostly a toy problem rather than problems coming from applications. Indeed many game theory problems have simplex as constraints. Can you tell us some specific unconstrained games where we need L0-L1 assumption?

4. GANs are a bit far-fetched since they will not satisfy any of the other assumptions in this paper. Still they can be acceptable if you can show that L0-L1 assumption is necessary to handle these problems. Is this possible?

5. Your Example 2 seems like a toy problem rather than a problem that can be more useful broadly. Can you comment if GlobalForsaken problem satisfy your assumption?

6. Example 3 in your appendix has constraints, how does it fit to your template?

7. Example 4 in your appendix: Can you tell us some specific games?

Moreover, following-up on the question from Reviewer 4hmy, which of these applications, or which applications in general, does one need to handle the L0-L1 Lipschitzness rather than the standard Lipschitzness? Can you please provide motivating specific problems?

One point your Example 1 makes is that it may be good to use L0-L1 Lipschitzness even when regular Lipschitzness hold but then you would have to justify what we lose in this transition. For example, the exponential blow-up in Theorem 3.5 or asymptotic-type rate in Theorem 3.6 are things we don't have with regular Lipschitzness. Needless to say we lose the ability to use constraints.

Overall, can you please make your motivating problems a little more specific?

Regarding terminology, even though other papers may have used it, I don't think it is a strong enough reason to use a terminology that can be misleading to others.

Thanks!