A Primal-Dual Approach to Solving Variational Inequalities with General Constraints

Thanks for the time you took to review our paper and provide feedback.

W1. The assumption that $F(x)$ is monotone or strictly monotone may be overly stringent. This condition is not met in applications involving Generative Adversarial Networks.

Monotone variational inequalities (VIs) are crucial in the VI literature and are considered a relatively broad problem class, surpassing min-max problems, for example. Their significance mirrors that of convex optimization problems in minimization literature, where optimization methods are initially validated on convex problems due to the complexity of studying non-convex problems. Hence, it is essential and customary to initially examine the convergence properties of new algorithms on monotone VI problems, as evidenced by existing works (see [1-4], for instance). Extending our analysis to a broader class is left for future research. Additionally, our experiments with GANs (Figure 3) suggest that ACVI performs effectively even in non-monotone problems.

W2. The actual efficiency of the algorithm heavily depends on the solution approach for the x-subproblem, which is challenging to solve. The authors do not address the resolution of this general nonlinear system.

In terms of our theoretical contributions, our convergence rate does take into account the complexity of solving the $x$-subproblem. In particular, if either EG or GD are used for the $x$-subproblem, the convergence is $O(1/\sqrt{K})$. It's worth noting that if the original problem is monotone, the $x$ problem becomes strongly monotone, making it easier to solve; you can find more details in our discussion on page 51. Additionally, if general-form constraints are associated with the problem, there is no other alternative as a first-order method, as we elaborate in the introduction.

From a practical standpoint, solving the $x$-subproblem approximately using unconstrained GDA or ED methods is straightforward—this is reflected in our experiments, which include wall-clock time and gradient query comparisons. Setting the iteration number for solving $x$-subproblem (i.e., $l_x^{(t)}$ in line 8 of Alg. 1) to be a small constant yields good results. Refer to Figures 2-4, 11, and App. E for more details.

Please let us know if further clarification on the theoretical or practical aspects is needed.

W3. It is preferred to provide an explanation for assuming the "monotonicity" of $F$ on $C_=$ and the "strictly monotonicity" of $F$ on $C$.

The monotonicity of $F$ on $C_=$ guarantees the existence and uniqueness of the solution of the non-linear system for the $x$-subproblem. More details can be found in Theorem B.3 in our paper or Theorem 1 in Yang et al., 2023.

We require either strict monotonicity of $F$ or strict convexity of one of $\varphi_i$. This condition is necessary to ensure the "central path" exists—refer to Appendix B.3 for a more detailed discussion. It's worth noting that Remark 3 in Yang et al. explains that this assumption is relatively weak.

Please let us know if more clarifications are needed.

W4. The barrier map is undefined when it first appears in Algorithm 1.

We've postponed the definition of the barrier maps to the convergence subsection to ensure clarity that the theorem specifically applies to those barrier maps (which are clickable in the algorithm). Our revised paper also refers to their equations when introducing Algorithm 1 in Section 3. Thanks for bringing this to our attention.

[1] Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 1976.

[2] Mokhtari et al. Convergence Rate of O(1/K) for Optimistic Gradient and Extragradient Methods in Smooth Convex-Concave Saddle Point Problems. SIAM Journal on Optimization, 2020.

[3] Mokhtari et al. A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach. AISTATS, 2020.

[4] Daskalakis et al. The limit points of (optimistic) gradient descent in min-max optimization. NeurIPS, 2018.

Thank you for your attentive review of the proofs and for providing valuable feedback – it is greatly appreciated. We've corrected the mentioned typo in our revised paper; thanks for catching that.

We managed to circumvent the assumptions in Yang et al. by a simple yet not immediately apparent insight into understanding the point implicitly tracked by ACVI at each iteration. Indeed, (14) is one of the crucial steps -- we added more technical discussion below Lemma C.10 (paragraph discussion, page 28) in our revised paper, where we describe our new analysis technique and compare them with the approach of Yang et al., 2023. Please let us know if additional clarification could be helpful. Thanks.

Concerning the remaining proofs of the theorems, (i) addressing the main challenge of Thm. 3.2 involves handling the inherent approximation errors in our inexact algorithm. Meanwhile, (ii) the overall approach for proving Thm. 4.1. differs from the previous one for Thm. 3.1. since there are no central path points in Algorithm 2.

Thank you for reviewing our paper. We appreciate your unique and insightful summary.

Additional experiments

Thanks; integrating those experiments could indeed help highlight the value of our contributions. However, due to space limitations, we opt for the standard experiments commonly found in related works. To complement our numerical simulations, we include experiments on GANs—a less conventional practice in theoretical papers.

It's worth noting that the bilinear games we employ have been extensively explored in computational game theory, reinforcement learning, and economics, as indicated by references [1-5]. The high-dimensional bilinear games, coupled with the probability simplex constraints (problem (HBG) in Section 5), are reminiscent of two-player zero-sum games [5]. In each turn, players select actions from predetermined probability distributions, akin to defining their policies. The effectiveness of our methods in addressing this particular problem subtly implies that they may perform well in the mentioned areas as well.

W2: Fig. 1

We've edited Fig. 1 in the uploaded revised version; thanks for raising that. The yellow curve is the central path, or in other words, the trajectory that the second-order interior point methods would follow. The dark blue trajectory is that of the corresponding method (in the subfigure's caption), where all methods are initialized at the same point depicted with a dark blue circle.

W3: labeling all equations & W4: The figures' font size

Thanks for pointing that out; we will improve these for the final version.

W5: min and argmin

We've corrected that; thanks.

Whether the barrier function is a new component of inexact ACVI

In short, $\wp_1(\cdot)$ is the same as in Yang et al., and $\wp_2(\cdot)$ is new for I-ACVI.

In Yang et al., it is assumed that the $y$ subproblem can be solved exactly analytically. In contrast, in I-ACVI, where the solution is obtained iteratively through gradient-based methods, we introduced $\wp_2$ to make the objective nicer. Specifically, $\wp_1(\cdot)$ is non-smooth, and while technically functional, there are no efficient methods to solve it. We design $\wp_2(\cdot)$ to make the objective smooth; this barrier term could potentially be helpful also for constrained minimization. Please see App. C.4 for a more detailed discussion.

Does Theorem 3.2 specifically require one of these two barrier functions?

Yes. Theorem 3.2 requires one of these two barrier functions and would not work with others; in addition to Alg. 1, we noted it in Theorem 3.2, too.

subproblems and definitions caps

Fixed in the updated version.

[1] Hwang et al. Strategic decompositions of normal form games: Zero-sum games and potential games. Games and Economic Behavior, 2020 - Elsevier.

[2] Kannan et al. Games of fixed rank: A hierarchy of bimatrix games. Economic Theory, 2010 - Springer.

[3] Campana et al. Nash equilibria and bargaining solutions of differential bilinear games. Dynamic Games and Applications. 2021 - Springer.

[4] Sherali et al. A new reformulation-linearization technique for bilinear programming problems. Journal of Global optimization, 1992 - Springer.

[5] Cen et al. Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization. NeurIPS 2021.

Thanks very much for your rebuttal! I have no further questions. My main concern is that the font size in the figures is still too small. Please make it at least as big as the font size in the document itself.

Thanks a lot for your time reviewing our paper and for your feedback.

W1: convergence metric relative to Yang et al. (2023)

We use the standard gap function as in Yang et al. (2023); see our def. 2.2, and def. 2 in Yang et al., as well as item 3 in Thm.2 and Thm.3 of Yang et al.(2023).

W2: more highlights on analysis techniques relative to Yang et al. (2023)

The relaxed assumptions relative to Yang et al. (Thm. 3.1) are owning to a simple but helpful insight of identifying a relationship between the reference point of the gap function and a KKT point that ACVI implicitly targets, as we mention in the last paragraph on page 2. We also added a more formal discussion on page 27 to discuss this further; thanks. The remaining theorems' proofs differ from Yang et al. (2023) as Thm. 3.2 deals with approximation errors of our inexact algorithm and the proof of Thm. 4.1 differs in that we do not have central path points.

W3: Why removing the Lipschitz assumption is important

Practical scenarios often entail operators lacking Lipschitz continuity, such as in GANs and multi-agent reinforcement learning. For example, if using relu (or a lot of other activations), the successive multiplication of coefficient matrices leads to a derivative that is not Lipschitz continuous. Relaxing this assumption broadens the scope for which the convergence guarantee holds. It's worth noting that a substantial body of work in both VI and minimization literature focuses on eliminating the Lipschitzness assumption; references [1-5], for instance.

W4. The method is limited to monotone operators.

Monotone variational inequalities (VIs) occupy a pivotal position in the VI literature and are considered a relatively broad problem class, surpassing min-max problems, for example. Their significance is comparable to that of convex optimization problems in the realm of minimization literature, where, due to the complexity of non-convex problems, optimization methods are initially validated on convex problems. Hence, it is essential and customary to initially examine the convergence properties of new algorithms on monotone VI problems, as evidenced by existing works (see [6-9], for instance). Extending our analysis to a broader class is left for future research.

Our experiments with GANs (Figure 3) indicate that ACVI performs effectively even in non-monotone problems.

Q1. Since this paper focuses on improving existing analysis, can the authors more formally state new analysis techniques compared with Yang et al. (2023)?

Please refer to our earlier answer to W2. In addition to Thm. 3.1, which improves the mentioned analysis, we introduce two algorithms and study their convergence. This is in response to the limitation of the alg. in Yang et al. (2023) in handling the general case when the subproblem cannot be analytically solved and efficiently managing structured inequality constraints.

Q2. How can the errors of solving subproblems be in practice?

In our experiments, we found that the errors of solving subproblems can be controlled simply by fixing $l_x^{(t)}$ and $l_y^{(t)}$ to be a small constant number $l$ in lines $8$ and $9$ of Alg. 1. This entails running $l$ iterations of $\mathcal{A}_x$ and $\mathcal{A}_y$ each time to solve the subproblems. To provide specific examples, in the 2D-BG games in Figures 1 and 2, we set $l$ to be $2$ and $20$, respectively. In the C-GAN experiments (Figure 3, Section 5.3), we use a large $l$ for the first iteration ($l_0$) (the warm-start technique) and then fix $l=20$. See App. C.4, where we elaborate on this.

Q3. What is the computational complexity of inexact ACVI? How can this be compared with the one for ACVI in your experiments?

To give an $\varepsilon$-accurate solution, the overall complexity of inexact ACVI is still $\mathcal{O}(1/\varepsilon^2)$ up to a log factor, as we discussed at the end of App. C.4. In our experiments, the complexity is also $\mathcal{O}(1/\varepsilon^2)$ since we fix the number of iterations to solve the subproblems to be a small constant number, which only adds constant to the complexity.

Thank you for the response. I don't have futher questions. My overall suggestion is moving the comparison of proof techniques to the main paper, higlighting examples like GAN or multi-agent RL that lack lipscthizness, and emphasizing more on the proof challenges when stating theorems.