A Primal-Dual Approach to Solving Variational Inequalities with General Constraints
Authors: Tatjana Chavdarova
Tong Yang
Matteo Pagliardini
Michael Jordan
Venue: ICLR 2024 poster (2024)
Keywords: Variational Inequaly
optimization
constraints
primal-dual
interior-point method
Monotone operator
last iterate convergence
Primary area: optimization
TL;DR: Novel first-order methods for solving constrained variational inequalities with convergence guarantees on monotone variational inequalities.

Abstract: Yang et al. (2023) recently showed how to use first-order gradient methods to solve general variational inequalities (VIs) under a limiting assumption that analytic solutions of specific subproblems are available.  In this paper, we circumvent this assumption via a warm-starting technique where we solve subproblems approximately and initialize variables with the approximate solution found at the previous iteration. 
We prove the convergence of this method and show that the gap function of the last iterate of the method decreases at a rate of $\mathcal{O}(\frac{1}{\sqrt{K}})$ when the operator is $L$-Lipschitz and monotone. 
In numerical experiments, we show that this technique can converge much faster than its exact counterpart. 
Furthermore, for the cases when the inequality constraints are simple, we introduce an alternative variant of ACVI and establish its convergence under the same conditions.
Finally, we relax the smoothness assumptions in Yang et al., yielding, to our knowledge, the first convergence result for VIs with general constraints that does not rely on the assumption that the operator is $L$-Lipschitz.

Published as a conference paper at ICLR 2024
A PRIMAL-DUAL APPROACH TO SOLVING VARIA- TIONAL INEQUALITIES WITH GENERAL CONSTRAINTS
Tatjana Chavdarova"
Tong Yang*
University of California, Berkeley tat jana. chavdarova@berkellg edu
Carnegie Mellon University
tongyange cmu edu
Matteo Pagliardini
Michael I. Jordan
University of California, Berkeley & EPFL matteo. ptt.epppaglaarrdnieeplllll
University of California, Berkeley
jordanêcs berkeley edu
ABSTRACT
Yang et al. (2023) recently showed how to use first-order gradient methods to solve general variational incqualities (VIs) under limiting assumption that analytic so- lutions of specific subproblems are available. this paper, we circumvent this assumption via warm-starting technique where solve subproblems approxi- mately and initialize variables with the approximate solution found at the previous iteration. We prove the convergence of this method and show that the gap function of the last iterate of the method decreases at a rate of O VR when the operator show that this tech- is L-Lipschitz and monotone. In numerical experiments,
nique can converge much faster than its exact counterpart. Furthermore, for the cases when the inequality constraints simple, we introduce alternative vari- ant of ACVI and establish its convergence under the same conditions. Finally, we relax the smoothness assumptions in Yang et al., yielding, our knowledge, the first convergence result for VIs with general constraints that does not rely on the assumption that the operator L--Lipschitz.
INTRODUCTION
We study variational inequalities (VIs), a general class of problems that encompasses both equilibria and optima. The general (constrained) VI problem involves finding point x E X' such that:
x - x F(x")) 2 O, Vo E X,
(cVI)
where X' is a subset of the Euclidean n-dimensional space R", and where F: X' + IR. is a con- tinuous map. VIs generalize standard constrained minimization problems, where F is gradient field F = Vf, and, by allowing F' to be a general vector field, they also include problems such finding equilibria in zero-sum games and general-sum games (Cottle & Dantzig, 1968; Rock- afellar, 1970). This increased expressivity underlies their practical relevance to a wide range of emerging applications in machine learning, such as (i) multi-agent games (Goodfellow al., 2014; Vinyals et al., 2017), (ii) robustification of single-objective problems, which yields min-max formu- lations (Szegedy et al., 2014; Mazuelas al., 2020; Christiansen al., 2020; Rothenhäusler al., 2018), and (ūi) statistical approaches to modeling complex multi-agent dynamics in stochastic and adversarial environments. We refer the reader to (Facchinei & Pang, 2003; Yang et al., 2023) for further examples.
Such generality comes, however, at a price in that solving for equilibria is notably more challenging than solving for optima. In particular, the Jacobian of F is not necessarily symmetric, may have rotational trajectories or limit cycles (Korpelevich, 1976; Hsich et al., 2021). Moreover, in sharp contrast standard minimization, the last iterate be quite far from the solution even though the average iterate converges to the solution (Chavdarova et al., 2019). This has motivated recent efforts
"Equal contribution. Source code: https:///itth// wttptttwww..com//ccaaaaarrraaaaa ACVI.

---

Published as a conference paper at ICLR 2024
to study specifically the convergence of the last iterate produced by gradient-based baseed methods. Thus, herein, our focus and discussions refer to the last iterate.
Recent work has focused primarily solving VIs in two cases of the domain X: (i) the uncon- strained setting where X' IR" (Golowich et al., 2020b; Chavdarova et al., 2023; Gorbunov et al., 2022a; Bot et al., 2022) and for (ži) the constrained setting with projection-based methods (Tseng, 1995; Daskalakis et al., 2018; Diakonikolas, 2020; Nemirovski, 2004; Mertikopoulos et al., 2019; Cai et al., 2022). The latter approach assumes that the projection is "simple," in the sense that this step does not require gradient computation. This holds, for example, for inequality constraints of the form I T where r is some constant, in which case fast operations such as clipping suffice. How- ever, as is the case in constrained minimization, the constraint set denoted herein with C S X'iss, in the general case, an intersection of finitely many inequalities and linear equalities:
C = {I E (z) S 0, [m], Ca dd.
(CS)
where each 4p:: R" + R. C RRxx" and d E RP. Given a general CS (without assuming additional structure), implementing the projection requires second-order methods, which quickly become computationally prohibitive as the dimension n increases. If the second-order derivative computation is approximated, the derived convergence rates will yet be multiplied with an additional factor; thus, the resulting rate of convergence may not match the known lower bound (Golowich et al., 2020a; Cai et al., 2022). This motivates third thread of research, focusing on projection- free methods for the constrained VI problem, where the update rule does not rely on the projection operator. This is the case we focus on in this paper.
There has been significant work on developing second-order projection-free methods for the formu- lation in cVI; we refer the interested reader to (Chapter 7, Nesterov & Nemirovski, 1994) and (Chap- ter 11, Facchinei & Pang, 2003, vol. 2) for example. We remark that the seminal mirror-descent and mirror-prox methods (Nemirovski & Yudin, 1983; Beck & Teboulle, 2003; Nemirovski, 2004) (see App. A.5) exploit a certain structure of the domain and avoid the projection operator, but cannot be applied for general CS.
In recent work, Yang et al. (2023) presented a first-order method, referred to as the ADMM-basee Interior Point Method for Constrained VIs (ACVI), for solving the eVI problem with general constraints. ACVI combines rath-following interior point (IP) methods and primal-dual meth- ods. Regarding the latter, it generalizes the alternating direction method of multipliers (ADMM) method (Glowinski & Marroco, 1975; Gabay & Mercier, 1976), an algorithmic paradigm that is central to large-scale optimization (Boyd et al., 2011; 1; Tibshirani, 2017)- see (Yang et al., 2023) and App. A.1; but which has been little explored in the cVI context. On a high level, ACVI has two nested loops: (i) the outer loop smoothly decreases the weight μu; of the inequality constraints in IP methods, whereas (ii) the inner loop performs a primal-dual update (for a fixed μ4)) as follows:
solve subproblem whose main (primal) variable æ/ aims to satisfy the equality constraints,
solve subproblem whose main (primal) variable y aims to satisfy the inequality constraints,
update the dual variable X(
The first two steps solve the subproblems exactly using analytical expression of the solution, and the variables converge to the same value, thus eventually satisfying both the inequality and equality constraints. See Algorithm 3 for full description, and see Fig. 2 for illustrative examples. The authors documented that projection-based methods may extensively zig-zag when hitting a con- straint when there is a rotational component in the vector field, an observation that further motivates projection-free approaches even when the projection is simple.
Yang al. showed that the gap function of the last iterate of ACVI decreases at a rate of O ( VK
when the operator is T.-L.ipschitz, monotone, and at least one constraint is active. is, however, an open problem to determine if the same rate on the gap function applies while assuming only that the operator is monotone (where monotonicity for VIs is analogous to convexity for standard min- imization, Def. 2.1). Moreover, in some cases, the subproblems of ACVI may be cumbersome to solve analytically. Hence, a natural question is whether we can show convergence approximately when the subproblems are solved. As result, we raise the following questions:
Does the last iterate of ACVI converge when the operator is monotone without requiring it to be L-Lipschit??
2

---

Published as a conference paper at ICLR 2024
Does ACVI converge when the subproblems are solved approximately?
In this paper, we answer the former question affirmatively. Specifically, we prove that the last iterate of ACVI converges at a rate of O (x)) in terms of the gap function (Def. 2.2) even when assuming only the monotonicity of the operator. The core of our analysis lies in identifying relationship between the reference point of the gap function and a KKT point that ACVI targets implicitly (i.e., does not appear explicitly in the ACVI algorithm). This shows that ACVI explicitly works to decrease the gap function at each iteration. The argument further allows us to determine a con- vergence rate by making it possible to upper bound the gap function. This is in contrast to the approach of Yang et al. (2023), who upper bound the iterate distance and then the gap function, an approach that requires a Lipschitz assumption. This is the first convergence rate for the last iterate for monotone VIs with constraints that does not rely on an L-Lipschitz assumption the operator.
To address the latter question, we leverage a fundamental property of the ACVI algorithm namely, its homotopic structure as it smoothly transitions to the original problem, a homotopy that inher- ently arises from its origin as an interior-point method (Boyd & Vandenberghe, 2004). Moreover, due to the alternating updates of the two sets of parameters of ACVI (ar and y: see Algorithm 3), the subproblems change negligibly, with the changes proportional to the step sizes. This motivates the standard warm-start technique where, at every iteration, instead of initializing at random, we ini- tialize the corresponding optimization variable with the approximate solution found at the previous iteration. We refer to the resulting algorithm as inexact ACVI, described in Algorithm 1. Further- more, inspired by the work of Schmidt et al. (2011), which focuses on the proximal gradient method for standard minimization, we prove that inexact ACVI converges with the same rate of O VKK )
under condition on the rate of decrease of the approximation errors. We evaluate inexact ACVI empirically on 2D and high-dimensional games and show how multiple inexact yet computationally efficient iterations can lead to faster wall-clock convergence than fewer exact ones.
Finally, we provide detailed study of a special case of the problem class that ACVI can solve. In particular, we focus on the case when the inequality constraints are simple, in the sense that projec- tion on those inequalities is fast to compute. Such problems often arise in machine learning, e.g., whenever the constraint set is an L--bbal,, with {1, 2, )o) } as in adversarial training (Goodfellow et al., 2015). We show that the same convergence rate holds for this variant of ACVI. Moreover, we show empirically that when using this method to train constrained GAN on the MNIST (Lecun & Cortes, 1998) dataset, it converges faster than the projected variants of the standard VI methods.
In summary, our main contributions are follows:
We show that the gap function of the last iterate of ACVI (Yang et al., 2023, Algorithm therein) decreases rate of O ( for monotone VIs, without relying the assumption that the oper- ator is L-Lipschitz.
We combine a standard warm-start technique with ACVI and propose a precise variant with ap- proximate solutions, named inexact ACVI see Algorithm 1. We show that inexact ACVI recovers the same convergence rate as ACVI, provided that the errors decrease at appropriate rates.
We propose a variant of ACVI designed for inequality constraints that are fast to project to see Algorithm 2. We guarantee convergence and provide the corresponding rate; this case, we omit the central path, simplifying the convergence analysis.
Empirically, we: (i) verify the benefits of warm-start of the inexact ACVI; (ii) observe that I-ACVI can be faster than other methods by taking advantage of cheaper approximate steps; (iii) train a constrained GAN on MNIST and show the projected version of ACVI is faster to converge than other methods; and (iv) provide visualizations contrasting the different ACVI variants.
1.1 RELATED WORKS
Last-iterate convergence of first-order methods on VI-related problems. When solving VIs, the last and average iterates can be far apart; see examples in (Chavdarova et al., 2019). Thus, an extensive line of work has aimed at obtaining last-iterate convergence for special cases of VIs that are important in applications, including bilinear or strongly monotone games (e.g.. Tseng, 1995; Malitsky, 2015; Facchinei & Pang, 2003; Daskalakis et al., 2018; Liang & Stokes, 2019; Gidel et al.. 2019b; Azizian et al., 2020; Thekumparampil et al., 2022), and VIs with cocoercive operators (Diakonikolas, 2020). Several papers exploit continuous-time analyses these provide
3

---

Published as a conference paper at ICLR 2024
direct insights on last-iterate convergence and simplify the derivation of the Lyapunov potential function (Ryu et al., 2019; Bot et al., 2020; Rosca et al., 2021; Chavdarova et al., 2023; Bot et al., 2022). For monotone VIs, (i) Golowich et al. (2020b;a) established that the lower bound of p- stationary canonical linear iterative (ū-SCLII first-order methods (Arjevani et al., 2016) is O DVR ) (ii) Golowich et al. (2020b) obtained rate in terms of the gap function, relying on first- and second- order smoothness of F. (ūi)) Gorbunov et al. (2022a) and Gorbunov et al. (2022b) obtained a rate of x for extragradient (Korpelevich, 1976) and optimistic GDA (Popov, 1980), respectively-inn terms of reducing the squared norm of the operator, relying on first-order smoothness of F, and (iv) Golowich et al. (2020b) and Chavdarova al. (2023) provided the best iterate rate for OGDA while assuming first-order smoothness of F. Daskalakis & Panageas (2019) focused on zero-sum convex- concave constrained problems and provided an asymptotic convergence guarantee for the last iterate of the optimistic multiplicative weights update (OMWU) method. For constrained and monotone VIs with L-Lipschitz operator, Cai et al. (2022) recently showed that the last iterate of extragradient and optimistic GDA have rate of convergence that matches the lower bound. Gidel et al. (2017) consider strongly convex-concare zero-sum games with strongly convex constraint set to study the convergence of the Frank-Wole method (Lacoste-Julien & Jaggi, 2015).
Interior point (IP) methods for VIs. IP methods are broad class of algorithms for solving prob- lems constrained by general inequality and equality constraints. One of the widely adopted sub- classes within IP methods utilizes log-barrier terms to handle inequality constraints. They typically rely on Newton's method, which iteratively approaches the solution from the feasible region. Sev- eral works extend IP methods for constrained VI problems. Among these, Nesterov & Nemirovski (Chapter 7, 1994) study extensions to VI problems while relying an extensive line of work discusses specific settings (c.g.. Chen et al., 1998; Qi & Sun, 2002; Qi al., 2000; Fan & Yan, 2010). On the other hand, Goffin et al. (1997) described a second-order outting-plane method for solving pseudomonotone VIs with linear inequalities. Although these methods enjoy fast convergence regarding the number of iterations, each iteration requires comput- ing second-order derivatives, which becomes computationally prohibitive for large-scale problems. Recently, Yang et al. (2023) derived the aforementioned ACVI method which combines IP methods and the ADMM method, resulting in a affisstooreer method that can handle general constraints.
Newton's is method. Further,
2 PRELIMINARIES
Notation. Bold small and bold capital letters denote vectors and matrices, respectively, while curly capital letters denote sets. We let [n] denote (1.....n) and let denote vector of all I's. The Euclidean norm of is denoted by ||/]] and the inner product in Euclidean space by (:-). @ denotes element-wise product.
Problem. Let ran = p be the rank of C as per (CS). With abuse of notation, let tp be the concatenated (p,()), E [m]] We assume that each of the inequality constraints is convex and fp; C² (R"), [m]. We define the following sets:
(x()) < 0}, C₂ a fx {xER R"
C. e fx E R" (x(()) < 0}, and C_ é E R Cy d):
thus the relative interior of C is int C C. We assume int C + 0 and that C is compact.
In the following, we list the necessary definitions and assumptions: see App. A for additional back- ground. We define these for general domain set S, and by setting S RD and S = X, these refer to the unconstrained and constrained settings, respectively. We will use the standard gap function as a convergence measure, which requires S to be compact to define it.
Definition 2.1 (monotone operators). An operator F: X' 2 S + R" is monotone on S if and only if the following inequality holds for all ar, xr E S: (x: x', F(() F(x')) 2 0.
Definition 2.2 (gap function). Given a candidate point x' E X and a map F: X: R" where compact, the gap function G : R - is defined as: G(x', ()) a max x' x).
WES
Definition 2.3 (a op-ppoxximaee solution). Given a map F: X - I and a positive scalar a, x E X is said to be a-approximate solution of F(x) = 0 iff [[ S a. Definition 2.4 (e-minimizer). Given minimization problem min h((r), s.t. E S, and fixed
positive scalar E, a point à S is said to be an e-minimizer of this problem if and only if it holds that: h())) < h(x) te, Vx E S.
4

---

Published as a conference paper at ICLR 2024
central path
point
(-JACVI
(a) ACVI
(b) I-ACVI, 2=20, (c) I-AVII, 1010 8= (d) I-ACVI, K=5,
Convergence of ACVI and I-ACVI on the (2D-BG) problem. The central path is depicted in yellow. For all methods, show the y-iterates initialized the same point (blue circle). Each subsequent point on the trajectory depicts the (exact or approximate) solution at the end of the inner loop. A yellow set is the interior of the red square. (a): As we decay j4,, the solutions the inner loop of ACVI follow the central path. As μ4 - 0, the solution of the inner loop of ACVI converges to the NE. d): When the a and y subproblems are solved approximately with a finite K and L, the iterates need not converge as the approximation error increases (and K decreases). See 5 for discussion.
Figure 1:
represents the game's Nash equilibrium (NE), and the constraint
Algorithm Inexact ACVI (I-ACVI) pseudocode.
1: Input: operator
- IR," constraints Ca d and (((()) S 0, [m], hyperparameters |_1,8 >> 0,8 E (0, 1), barrier map (P1 or P2), inner optimizers As (e.g. EG, GDA) and Ay (GD) for the æ and y subproblems, resp.; outer and inner loop iterations and K, resp.
2: Initialize: Fog (0)
E ER" Vo (0)
2,0 E ER" 1 E R
3: P. - -CTCCCCT
where P. E R
4: d. - (TCCCT) d
where de R
5: for l = 0,....,
do
6: Ne 8p-1
7: for k ===0
K 1 do
(1) Set #+1 to o a --ppoxxiiii solution of: x+ P.
8:
(w.rt. x), by running e(t) steps of Ag, with initialized the previous solution (ar (t)
k> O, else xx-1) (e-1))
(1) Set 1 to be an EK+1 minimizer of miny En ((p)())))))))))))))))())) (1) + x x 1
9:
by running elt) steps of Ay. with y initialized y when l > or yk
(t-1) otherwise
10:
k+11 x + B( Met1)
(0) (1)
(()
11: end for
12: (yo 1++)
A (+)))) & ( x
13: end for
3 CONVERGENCE OF THE EXACT AND INEXACT ACVI ALGORITHMS FOR MONOTONE VIs
In this section, we present our main theoretical findings: (i) the rate of convergence the last iterate of ACVI (the exact ACVI algorithm is stated in App. A) while relying exclusively on the assumption that the operator F is monotone; and (ii) the corresponding convergence when the subproblems are solved approximately- where the proposed algorithm is referred to as inexact ACVI-Algone L-Lipschitz for the latter result, and
(P1. D2 are defined below). Note that we only assume run Algorithm with extragradient for line 8, for example, the method only has convergence guarantee if F is L-Lipschitz (see Korpelevich, 1976, Theorem 1). For easier comparison with one loop algorithms, iteration count) as in (Yang et al., 2023); nonetheless, the same rates hold without knowing 1 see App. B.4 in Yang et al. (2023) and our App. B.3. Thus, both guarantees parameter-free
will state both of these results for fixed μ-1 (hence only have the & [K]
5

---

Published as a conference paper at ICLR 2024
3.1 LAST ITERATE CONVERGENCE OF EXACT ACVI
Theorem 3.1 (Last iterate convergence rate of ACVI- 1 in (Yang et al., 2023)), Given
continuous operator F: X + R", assume: (i) F is monotone on C.,, as per Def. 2.1; (ii) either F
strictly monotone on C or one of ys is strictly convex. Let (æx Y Ax denote the last iterate of ACvi any fixed K 14, with sufficiently small μt-1. then vE E [T] 1, it holds that:
(t) (t)
g( (0) C) S O
and
uk
S
O
VK
VK
App. B gives the details on the constants that appear in the rates and the proof of Theorem 3.1.
3.2 LAST ITERATE CONVERGENCE RATE OF INEXACT ACVI
For some problems, the equation in line 8 or the convex optimization problem in line 9 of ACVI may not have an analytic solution, the exact solution may be expensive to compute. Thus we consider solving these two problems approximately, using warm-starting, At each iteration, we set the initial variable and y to be the solution at the previous step when solving the x and y sub- problems, respectively, as described in Algorithm 1. The following Theorem cnarem-iisspredd by (Schmidt et al., 20 establissss that when the errors in the calculation of the subproblems satisfy certain conditions, the last iterate convergence rate of inexact ACVI recovers that of (exact) ACVI. The theorem holds for the standard barrier function used for IP methods, function (g2) that we propose that is smooth and defined in the entire domain, as follows:
well for new barrier
-plog(-22 (-2) = A
SP (2, A -u log(-2)
(p)
(2)
(g22
.ee z + p c, otherwise where e (f2) is fixed constant. Choosing among these is denoted with go.)) in Algorithm
Theorem 3.2 (Last iterate convergence rate of Inexact ACVi-Algorithm with Φ1 (22). Given
a continuous operator F: X + R", assume: (i) F is monotone on C=, as per Def. 2.1; (ū) either F is strictly monotone on C or one of yps is strictly convex; and (ii)) F is L-Lipschitz
X, that is, [[) F(x')ll S L | L'), for all x, x' E X and some L > Let (x 9y (() denote the last iterate of Algorithm I; and let ox and ex denote the approximation errors at step k of lines 8 and VK
(1)
9 (as per Def. 2.3 and 2.4), respectively. Further, suppose: lim 1 Lk=1 (k( + ow)) <
+00. Given any fixed K E N+, run with sufficiently small μ111. then for all t E [T]. it holds:
g (0) C) S O O and o yk S O
1 VK
VK
As is the case for Theorem 3. Theorem 3.2 gives nonasymptotic convergence guarantee. While the condition involving the sequences fc 1++1 and {ax {a K-1 requires the given expression to be summable, the convergence rate nonasymptotic as holds for any K. App. B gives details on the constants in the rates of Theorem 3.2, provides the proof, and also discusses the algorithms Az; Ay for the sub-problems that satisfy the conditions. App. C discusses further details of the implementation of Algorithm I; and we will analyze the effect of warm-starting in $ 5.
4 SPECIALIZATION OF ACVI FOR SIMPLE INEQUALITY CONSTRAINTS
We now consider that the inequality constraints are simple in that the projection is fast to compute. This scenario frequently occurs machine learning, particularly when dealing with Loo -ball con- straints, for instance. Projections onto the L2 and Li-bllls can also be obtained efficiently through simple normalization for Le and a O Onn log(n)) algorithm for L1 (Duchi et al., 2008). we have the flexibility to substitute the y y-subpooblem with projection onto the set defined by the inequalities. The n-subbroobem still accounts for equality constraints, and if there are none, this simplifies the æ-subproblem further since P. I, and d, = 0. Projection-basee methods can- not leverage this structural advantage of simple inequality constraints as the intersection with the equality constraints can be nontrivial.
ACVI,
The P-ACVI Algorithm: omitting the log barrier. Assume that the provided inequality con- straints can be met efficiently through a projection II (:): R2 - Cz. In that case, we longer need the log barrier, and we omit μ and the outer loop of ACVI over t E [T]. Differentiating the remaining expression of the y subproblem with respect y and setting it to zero gives:

---

Published as a conference paper at ICLR 2024
Algorithm 2 P-ACVI: ACVI with simple inequalities.
Input: operator F: K"" constraints C and projection operator 11g for the inequal-
ity constraints, hyperparameter 8 > 0, and number of iterations K.
2: Initialize: Yo R.". X E R"
3: I-
where Pa E Rax
4: d. - (CCCT)
where de RR"
5: for k ==00 =0..... K do
6: Set # to be the solution of: a + (PF Payx JPPP d. (w.rt. x)
7: yk+1 = 11 (xx+1 + + As)
8: Ak+1 2 + B(xx41 yk+1)
9: end for
3 y 0++1
1
1 Ik+1 + B
argmin y 2
Ak 3
A
This implies that line of the exact ACVI algorithm (given in App. A) can be replaced with the solution of the problem without the inequality constraints, and we can cheaply project to satisfy the inequality constraints, as follows: yk++1 (* { where the (p:(-) are included the projection. We describe the resulting procedure Algorithm and refer as P-ACVI. In this scenario with simple sis the problem is always solved exactly; nonetheless, when the z-subproolem also solved approximately, we refer as PI-ACVI.
10P
P-EG
PLACNE & 50
(scandd))
(a) of PI-ACVI
(b) of PI-ACVI
(a) FID, lower is better
(b) higher is better
Figure Intermediate iterates of PI-ACVI
Figure 3: Experiments on the (C-GAN) game, using GDA, EG, and PI-ACVI on MNIST. All curves are averaged over 4 seeds. (a): Frechet Inception Distance (FID, lower better) given CPU wall-clock time. (b): Inception Score (IS, higher better) given wall-clock time. We ob- serve that PI-ACVI converges faster than EG and GDA for both metrics. Moreover, we see that us- ing a large for the first iteration (fg) give sigmificant advantage. The two PI-ACVI curves use the same 4 20.
(Algorithm 2) the 2D minmax game (2D-BG). The boundary the constraint set is shown in red. (b) depicts the ys (from line 7 in Algorithm/ 2) which we obtain through pro- jections. In (a), each spiral corresponds to iter- atively solving the Øs subproblem for = 20 steps (line 6 in Algorithm 2). Jointly, the trajec- tories of æ and illustrate the ACVI dynamics: and the constrained y "collaborate" and con- verge to the same point.
Last-iterate convergence of P-ACVI. The following theorem shows that P-ACVI has the same last- iterate rate as ACVI. Its proof can derived from that of Theorem 3.1, which focuses on a more general setting, see App. B. We state it separate theorem, as it cannot be deduced directly from the statement of the former.
Theorem 4.1 (Last iterate convergence rate of -LACVI-Algorithe 2). Given a continuous opera- for F: X + IR"", assume F is monotone on C=, as per Def. 2.1. Let (æK. yK, Ax) denote the last iterate of Algorithm 2. Then for all K E N4, it holds that:
1
g(zk, C) S O( VK
and ||x** y x
O
VK
Remark 4.2. Note that Theorem 4.1 relies weaker assumptions than Theorem. 3.1. This is ramification of removing the central path in the P-ACVI Algorithm. Thus, assumption (ii) in Theo- rem used earlier guarantee the existence of the central path (see App. A)-is not needed.

---

Published as a conference paper at ICLR 2024
P-GDA
8000
P.RG
snsebe of Beresteess
P.CKIDA
10
ACN1
P.LAA CDD
30
20
6000
200
20-
50
4000
60
10
10
10-2
0.0
0.5
1.0
0.1 10
50
100
130
(a) fixed error
(b) rotational intensity
(c) I-ACVI: effect of Ko, K+
Figure 4: Comparison between I-ACVI, (exact) ACVI, and projection-based algorithms on the (HBG) problem. (a): CPU time (in seconds) to reach a given relative error (z-axis), where the rotational intensity is fixed 7/ 0.05 in (HBG) for all methods. (b): Number of iterations reach a relative eπror of 0.02 for varying values of the rotational intensity We fix the maximum number of iterations to 50. (c): joint impact of the number of inner-loop iterations Ko at
and different choices of inner-loop iterations for K at any > 0 on the number of iterations needed to reach fixed relative error of 10-1, We see that irrespective of the selection of K+, I-ACVI converges fast Ko is large enough. For instance, (Ko 130, K 1) converges faster than (Ko 20, K 20). We fix = 10 for all the experiments, in all of (a), (b), and (c).
5 EXPERIMENTS
Methods. We compare ACVI, Inexact-ACVI (I-ACVI), and Projected-Inexxct-ACCC (PI-ACVI) with the projected variants of Gradient Descent Ascent (P-GDA), Extragradient (Korpelevich, 1976) (P-EG), Optimistic-GD GDA (Popov, 1980) (P-OGDA), and Lookahead -inmaax (Zhang et al., 2019;
Chavdarova et al., 2021) (P-LA). We always use GDA as an inner optimizer for I-ACVI, PI-ACVI, and P-ACVI. See App. D and C for comparison with additional methods and implementation.
Problems. We study the empirical performance of these methods on three different problems:
2D bilinear game: version of the bilinear game with Los constraints, as follows
min max 21 # EA AAA
with A =
R 0.4 S 2.4).
(2D-BG)
High-dimensional bilinear game: where each player is a 500-dimensional vector. The iterates are constrained to the probability simplex. A parameter 1 E (0, 1) controls the rotational component of the game (when 1) = 1 the game is potential, when 1 0 the game is Hamiltonian):
min max noe + (1 - 11) æ æ nol22, with A =(x; E R 500
x 2 0, and eTx, =1}-
E
(HBG)
MNIST: We train GANs the MNIST (Lecun & Cortes, 1998) dataset. We linear inequality constraints and no equality constraints, as follows:
min max E [log [s)) + E (GG(1))(G()))]
(C-GAN)
GE DEAc a~pa
gnppe
where =
b1), Ac=(C b2).
with Pz, Pa respectively, noise and data distributions; and Ç are the parameters of generator and discriminator, resp. D and G are the Generator and Discriminator maps, parameterized with o and resp. A, E IR 10000; and b, E R": where n, is the number of parameters of or G.
5.1 INEXACT ACVI
2D bilinear game. In Fig. 1, we compare exact and inexact ACVI on the 2D-Bilinear game. Rather than solving the subproblems of I-ACVI until we reach appropriate accuracy of the solutions of the subproblems, herein, we fix the K and number of iterations in I-ACVI. We observe how I-ACVI can converge following the central path when the inner loop of I-ACVI over k E [K] is solved with sufficient precision. The two parameters influencing the convergence path are K and f, where the latter is the number of iterations solve the two subproblems (line 8 and line 9 in Algorithm 1). Fig. I shows that small values such as K = 20 and convergence for this purely rotational game. Nonetheless, as K and decrease further, the iterates
the iterates to the central
are sufficient for
8

---

Published as a conference paper at ICLR 2024
of I-ACVI may not converge. This accords with Theorem 3.2, which indicates that the sum of errors is bounded only if K is large. Hence, larger K implies a smaller error.
HD bilinear game. In Fig. 4(a) and Fig. 4(b) we compare I-ACVI with ACVI and the projection- based algorithms on the (HBG) problem. We observe that both ACVI and I-ACVI outperform the remaining baselines significantly in terms of speed of convergence measured in both CPU time and the number of iterations. Moreover, while I-ACVI requires more iterations than ACVI to reach a given relative error, those iterations are computationally cheaper relative to solving exactly each subproblem; hence, I-ACVI converges much faster than any other method. Fig. 4(c) aims to demon- strate that the subproblems of I-ACVI are suitable for warm-starrtng Interestingly, we notice that the choice of the number of iterations at the first step t = 0 plays crucial role. Given that we initialize variables at each iteration with the previous solution, it aids the convergence to solve the subprob- lems as accurately as possible at / = 0. This initial accuracy reduces the initial error, subsequently decreasing the error at all subsequent iterations. We revisit this observation in $ 5.3.
5.2
2D bilinear game. In Fig. 2 we show the dynamics of PI-ACVI on the 2D game defined by (2D-BG). Compared to ACVI in Fig. 1, the iterates converge to the solution without following the central path. comparison with other optimizers is available in App. D.
MNIST. In Fig. 3 we compare PI-ACVI and baselines on the (C-GAN) game trained on the MNIST dataset. We employ the greedy projection algorithm (Beck, 2017) for the projections. Since ACVI was derived primarily for handling general constraints, a question that arises is how it (and its vari- ants) performs when the projection is fast to compute. Although the projection is fast to compute for these experiments, PI-ACVI converges faster than the projection-based methods. Compared to the projected EG method, which only improves upon GDA when the rotational component of F is high, it gives more consistent improvements over the GDA baseline.
5.3 EFFECT OF WARM-UP ON I-ACVI AND PI-ACVI
I-ACVI. The experiments in Fig. I motivate increasing the number of iterations K only the first iteration = dedenoted Kp. so that the early iterates are close to the central path. Recall that the K steps (corresponding to line in Algorithm 1) bring the iterates closer the central path as K + co (see App. B). After those Ko steps, a is decayed, which moves the problem's 's solution along the central path. For I-ACVI, from Fig. A())-herr
is fixed to 10-we observed that regardless of the selected value of K+ for > 0, it can be compensated by large enough Ko-
PI-ACVI. We similarly study the impact of the warmup technique for the PI-ACVI method (Algo- rithm 2). Compared to I-ACVI, this method omits the outer loop over t E [T'. Hence, instead of varying Ko, we experiment with increasing the first l at iteration k = denoted by fo. In Fig. 3 we
solve the constrained MNIST problem with PI-ACVI using either Lu 500 or to 100, f is set to 20 in both cases. Increasing the lo value significantly improves the convergence speed.
We observe consistently that using large Ko or I-ACVI, or large lo for PI-ACVI aids the convergence. Conversely, factors such as I and K, in I-ACVI, or l in PI-ACVI, exert comparatively lesser influence. Further experiments and discussions are available in App. D.
Conclusion.
DISCUSSION
We contributed to an emerging line of research on the ACVI method, showing that the last iterate of ACVI converges at a rate of order O(1 (K) for monotone VIs. This result is significant because does not rely on the first-order smoothness of the operator, resolving an open problem in the VI literature. To address subproblems that cannot always be solved in closed form, we introduced an inexact ACVI (I-ACVI) variant that uses warm-starting for its subproblems and proved last iterate convergence under certain weak assumptions. We also proposed P-ACVI for simple inequality constraints and showed that it converges with O(1 rate. Our experiments provided insights into I-ACVI's behavior when subproblems are solved approximately, emphasized the impact of warm-starting, and highlighted advantages over standard projection-based algorithms.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We acknowledge support from the Swiss National Science Foundation (SNSF), grants SEELP2_199700 and PS00PT The work of T. Yang is supported in part by the NSF grant CCF-2007911 to Chi.
REFERENCES
Yossi Arjevani, Shai Shalev-Shwartz, and Ohad Shamir. On lower and upper bounds for smooth and strongly convex optimization problems. In JMLR, 2016.
Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julient and Gauthier Gidel. A tight and unified analysis gradient-based methods for a whole spectrum of differentiable games. AISTATS, pp. 2863-2877 2020.
Amir Beck. First-Order Methods in Optimization. SIAM, 2017.
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett., 31(3):167-175, 2003.
Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Convex Analysis and Optimization, vol- ume 1. Athena Scientific, 2003.
Radu Ioan Bot, Ernö Robert Csetnek, and Phan Tu Vuong. The forward-backwarde forward method from continuous and discrete perspective for pseudo-monotone variational inequalities in Hilbert spaces. arXiv:180S.0800 08084, 2020.
Radu Ioan Bot, Ernö Robert Csetnek, and Dang-Khoa Nguyen. Fast OGDA in continuous and discrete time. arXiv preprint arXiv:2203. 10947, 2022.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge university press, 2004.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends Machine Learning, 3, 2011. ISSN 1935-8237. doi: 10.1561/2200000166
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Tight last-iterate convergence of the extragra- dient method for constrained monotone variational inequalities. arXiv:2204.09228, 2022.
Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. In NeurIPS, 2019.
Tatjana Chavdarova, Mattco Pagliardini, Sebastian U Stich, François Fleuret, and Martin Jaggi. Taming GANs with Lookahead- Minmax. In ICLR, 2021.
Tatjana Chavdarova, Michael Jordan, and Manolis aampetakis. Last-iterate convergence of saddle point optimizers via high-resolution differential equations. In Minimax Theory and its Applica- tions, 2023.
Xiaojun Chen, Liqun Qi, and Defeng Sun. Global and superlinear convergence the smoothing newton method and its application to general box constrained variational inequalities. Mathemat- ics of Computation, 67(22)):519-540, 1998.
Rune Christiansen, Niklas Pfister, Martin Emil Jakobsen, Nicola Gnecco, and Jonas Peters. A causal framework for distribution generalization. orXiv:2006.07433, 2020.
Liang-Ju Chu. On the continuity of trajectories for nonlinear monotone complementarity problems. Scientiae Mathematicae, 1 1(3):263-277) 1998.
Richard W. Cottle and George B. Dantzig. Complementary pivot theory of mathematical program-
ming. Linear Algebra and its Applications, 11): 1968. ISSN 0024-3795.
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and
constrained min-max optimization. In ITCS, 2019.
10

---

Published as a conference paper at ICLR 2024
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR, 2018.
Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. COLT, 125, 2020.
Jim Douglas and H. H. Jr. Rachford. On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American Mathematical Society, 82:421-439, 1956.
John Duchi, Shai Shalev-Shwartz Yoram Singer, and Tushar Chandra. Efficient projections onto the 11-ball for learning in high dimensions. ICML, pp. 272-279, 2008. doi: 10. 145/139015. 1390191.
J. Eckstein. Splitring Methods for Monotone Operators with Applications Parallel Optimization. Ph.D. dissertation. MIT, Cambridge, 1989.
Francisco Facchinei and Jong-Shi Pang. Finite-dimensional Variational Inequalities and Comple- mentarity Problems. Springer, 2003.
Xiaona Fan and Qinglun Yan. An interior point algorithm for variational inequality problems. In- ternational Journal of Contemporary Mathematical Sciences, 5(52) 2010.
Daniel Gabay. Applications of the method of multipliers to variational inequalities. In Studies in Mathematics and its Applications, volume 15, pp. 299-331. Elsevier, 1983.
Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics with Applications, 2:17- 40, 1976. ISSN 0898-12211
Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. Frank-Wolfe algorithms for saddle point problems. In AISTATS, 2017.
Gauthier Gidel, Hugo Berard, Pascal Vincent, and Simon Lacoste-Julien. variational inequality perspective generative adversarial nets. In ICLR, 2019a.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Si- mon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In AISTATS, 2019b.
R. Glowinski and A. Marroco. Sur I d'approximation, par éléments finis d' d'ordre la résolution, par pénalisation-dualle d'une classe problèmes Dirichlet non linéaires. ESAIM: Mathemat- ical Modelling and Numerical Analysis Modélisation Mathématique et Analyse Numérique, (R2):41776, 1975.
Roland Glowinski and Patrick Le Tallec. Augmented Lagrangian and Operator-Splitingg Methods in Nonlinear Mechanics. Society for Industrial and Applied Mathematics, 1989. doi: 10.1 9771611970838.
Jean-Louis Goffin, Patrice Marcotte, and Daoli Zhu. An analytic center cutting plane method for pseudomonotone variational inequalities. Operations Research Letters, 20(1):1-6, 1997. ISSN 0167-6377.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In NeurlPS, 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In COLT, pp- 1758-1784, 2020b.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farles Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. NIPS, 2014.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
11

---

Published as a conference paper at ICLR 2024
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/K) last-iterate convergence for monotone variational inequalities and connections with cocoercivity, In AISTATS,, 2022a.
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradi- ent method for monotone variational inequalities. arXiv:2205.005: 08446,, 2022b.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge local Nash equilibrium. In NIPS, 2017.
Ya-Ping Hsich, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: convergence spurious non-critical sets. In ICML, 2021.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
Galina Michailovna Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 1976.
Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank- Frank-Wolfe optimiza- tion variants. In NIPS, 2015.
Yann Lecun and Corinna Cortes. The MNIST database of handwritten digits, 1998. URL http: //yann. lecun www.//od////occccccccoococcoocco foddb/mniset st//
Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. Artificial Intelligence and Statistics, 2019.
Zhouchen Lin, Huan Li, and Cong Fang. Alternating Direction Method of Multipliers for Machine Learning. Springer, 2022.
L. Lions and B. Mercier. Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6):964 1979.
Yu. Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25:502-520, 2015.
Santiago Mazuelas, Andrea Zanoni, and Aritz Pérez. Minimax classification with 0-1 loss and performance guarantees. In NeurIPS, volume 33, 2020.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile. In ICLR, 2019.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra-gradient and op- timistic gradient methods for saddle point problems: Proximal point approach. arXiv: UrXiv:1901.08515 091111 2019.
Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz. continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004. doi: 10.11377S110522234444566
Arkadi Nemirovski and David Yudin. Problem complexity and Method Efficiency in Optimization, volume 1. Wiley, New York, 1983.
Yurii Nesterov and Arkadi Nemirovski. Interior-point polynomial algorithms in convex program- ming. Siam Studies in Applied Mathematics, 1994.
Robert Nishihara, Laurent Lessard, Ben Recht, Andrew Packard, and Michael Jordan. A general analysis of the convergence of admm. In ICML, volume 37 of Proceedings of Machine Learning Research, pp. 343-352, 2015.
Adam Paszke, Sam Gross, Soumith Chintala, and Gregory Chanan. PyTorch. https: // http:/yytocch/pyttttt 2017.
12

---

Published as a conference paper at ICLR 2024
Leonid Denisovich Popov. A modification of the arrow- method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845-88) 848, 1980.
Liqun Qi and Defeng Sun. Smoothing functions and smoothing newton method for complementarity and variational inequality problems. Journal of Optimization Theory and Applications, 113(1):
121-147, 2002.
Liqun Qi, Defeng Sun, and Guanglu Zhou. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Mathematical Program- ming, 87(1): 2000.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. In ICLR, 2016.
Ralph Tyrrell Rockafellar. Monotone operators associated with funccionn and minimax prob- lems. Nonlinear functional analysis, 18(part 1):397-407, 1970.
Mihaela Rosca, Yan Wu, Benoit Dherin, and David G. T. Barrett. Discretization drift in two-player games. In ICMI,, 2021.
Dominik Rothenhäusler, Nicolai Meinshausen, Peter Bühlmann, and Jonas Peters. Anchor regres- sion: heterogeneous data meets causality. 1801.0220 2018.
Ernest K. Ryu and Wotao Yin. Large-Scale Convex Optimization via Monotone Operators. Springer Publishing Company, Incorporated, 2022.
Ernest K. Ryu, Kun Yuan, and Wotao Yin. Ode analysis of stochastic gradient methods with opti- mism and anchoring for minimax problems. 190.:/905./0999 2019.
Tim Salimans. Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. NIPS, 2016.
Mark Schmidt, Nicolas Roux, and Francis Bach. Convergence rates of inexact proximal-gradient methods for convex optimization. NIPS, 24, 2011.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. 1rXiv:1312.619,, 2014.
Kiran Koshy Thekumparampil, Niao Hc, and Sewoong Oh. Lifted primal-dual method for bilinearly coupled smooth minimax optimization. In AISTATS, 2022.
Ryan Tibshirani. Dykstra's algorithm, admm, and coordinate descent: Connections, insights, and extensions. In NeurlPS, volume 30, 2017.
Paul Tseng. On linear convergence of iterative methods for the variational inequality problem.
Journal of Computational and Applied Mathematics, 60:237-252, 1995. ISSN 0377-0427.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, John Quan, Stephen Gaffney, Stig Petersen, Karen Simonyan, Tom Schaul. Hado van Hasselt, David Silver, Timothy Lillicrap, Kevin Calderone, Paul Keet, Anthony Brunasso, David Lawrence, An- ders Ekermo, Jacoh Repp, and Rodney Tsing. Starcraft II: A challenge for reinforcement learning. arXiv: 708. 04782, 2017.
Tong Yang, Michael I. Jordan, and Tatjana Chavdarova. Solving constrained variational inequalities via an interior point method. In ICLR. 2023.
Michael Zhang, James Lucas, Jimmy Ba, and Geoffrey Hinton. Lookahead optimizer: k steps forward, 1 step back. In NeurlPS, 2019.
13

---

Published as a conference paper at ICLR 2024
A ADDITIONAL BACKGROUND
In this section, we give background in addition to that presented in the main part. This includes:
(i in A.1 we describe the ADMM method,
(ii) in App. A.2 we list relevant definitions,
(iii) details the ACVI method, including its derivation, required for the proofs of the theorems in this paper are explained in App. A.3, and
(iv) the baseline methods used in 5 of the main part are described in App. A.5.
A.1 ALTERNATING DIRECTION METHOD OF MULTIPLIERS-ADDI
The ADMM method. ADMM (Glowinski & Marroco, 1975; Gabay & Mercier, 1976; Lions & Mercier, 1979; Glowinski & Le Tallec, 1989) was proposed for objectives separable into two or more different functions whose arguments nondisjoint, follows:
min f(x) (3)) y.y
s.t. Ax By b,
(ADMM-Pr)
where f.g:F. R" + R are often assumed convex, a, y E R" A,B R' and E R" ADMM relies the augmented Lagrangian function (.):):
8
Ca(æ, y, f(x) + g + (Aæ + By b, A)
11 By bll?
(AL-CVX)
2
where B 0. If the augmented Lagrangian method is used to solve (AL--VXX,, at each step k we have:
1k+1: Uk+1 argmin La y. At) and w.y
Aet1 \ ( Byk+1 - b),
where the latter step is gradient ascent on the dual. In contrast, ADMM updates and y in an alternating way follows:
#k+1 argman La(æ, yk: Au),
yk+11 argmin L3( Uk. )b)
(ADMM)
A4+1 A 3(Ax++1 Byk+1 -b)
where the key difference is that for the y update the latest iterate of æ is used.
ADMM's popularity stems largely from its computational efficiency for large-scale machine learn- ing problems (Boyd al., 2011) and its rapid convergence in certain settings (e.g., Nishihara al., 2015). In particular, it achieves linear convergence when one of the objective terms is strongly convex (Nishihara al., 2015), and is known in the community that it can converge faster than the proximal point method in some regression examples. It can be viewed equivalent to the Douglas-Rache Rachford operator splitting technique (Douglas & Rachford, 1956) applied within the dual space (see e.g. Gabay, 1983; Eckstein, 1989; Lin et al., 2022).
A.2 ADDITIONAL VI DEFINITIONS AND EQUIVALENT FORMULATIONS
Here we give the complete statement of the definition of an I.-Lipschitz operator for completeness, which assumption used in Theorem 3.2.
Definition A.1 (I-Lipschitz operator). Let F: X' - R be an operator, we say that satisfies T--fist-order smoothness on S if F is T-Lipschitz map; that is, there exists L. such that:
F (:) F(x'))
< T. ||ær æ'Il. Va, x S.
To define cocoercive operators-mentione in the discussions of the related work, we will first introduce the inverse of an operator.
Seeing operator F: X + R" the graph GrF f(x, u)(u X,y F(x)), its inverse F-1 defined as GrF-12 A { m))( y) GrF) (see e.g. Ryu & Yin, 2022).
14

---

Published as a conference paper at ICLR 2024
Definition A.2 ( -cocoercive operator). An operator F: X 2 8 - R² is 1 --cooeercive (or 1 inverse strongly monotone) on if its inverse (graph) F-1 is je-ttrngly monotone on S, that is, P
Bu 0, (a x', F(x) F(x')) 2 / F()) F(x')ll Ya, x' E It is star cocoerrcve if the above holds when setting x' x² where x² denotes solution, that is:
μ 3u 0, s.t. ve-x", -(=)))F((*))) μ (1)))) f(*")l' vo yo S,x Sx.F
Notice that cocoercivity implies monotonicity, and is thus stronger assumption.
In the following, we will make use of the natural and normal mappings an operator F: X' - IR", where X' C IR We denote the projection to the set X' with 1ly. Following similar notation as in (Facchinei & Pang, 2003), the natural map FNAT X - R defined as:
FNAT Ixxx F(x)),
Væ E
(F-NAT)
whereas the normal map F xx
RT + 12 is:
FXO F(Ix(())) - x x IIx(x,
Vo R".
(F-NOR)
Moreover, have the following solution characterizations:
(i x² E EX2
iff
FX (x*) O, and
(ii) E EX
iff Ar' s.t. x² Ixx(x') and (NoR(x")) O.
A.3 DETAILS ON ACVI
For completeness, herein we state the ACVI algorithm and show its derivation, see (Yang et al., 2023) for details. We will use these equations also for the proofs of our main results.
Derivation of ACVI. We first restate the cVI problem a form that will allow us to derive an interior-pone point procedure. By the definition of cVI it follows (see $1.3 in Facchinei & Pang, 2003) that:
F(x) + +
x ar F s.t. <0<)) < 0
St +>
Ca =d d 0 Os (L)(()) 50,
(KKT)
Cz d
where À E RD and RR are dual variables. Recall that assume that int C * 0. thus, by the Slater condition (using the fact that ( E [m] are convex) and the KKT conditions, the second equivalence holds, yielding the KKT system of cVI. Note that the above equivalence also guarantees the two solutions coincide; see Facchinei & Pang (2003, Prop. 1.3.4 (b)).
Analogous the method described in 2, add log-barrier term the objective to remove the inequality constraints and obtain the following modified version of (KKT):
F(x)
CTD= =
æ
A o p(x) + pe =
x argmin F(w) Σ log (-9:(x))
(KKT-2)
Cx =
8.t. Cz-d d
((x)) < 0, X 0,
with μ > 0, e [1, l,....,.. T RT. The equivalence holds by the KKT and the Slater condition. The update rule at step is derived by the following subproblem:
min F(WL) To 1
log (p(())
s.t. Cx d,
15

---

Published as a conference paper at ICLR 2024
where fix wx- Notice that (i) wy is constant vector in this subproblem, and (ii) the objective is split, making ADMM a natural choice to solve the subproblem. To apply an ADMM- type method, we introduce variable y E R" yielding:
min
Ta + 1 = d - 1 E log pi(i)) 2.y
(ACVIsuuprooblem)
8.t. x=
where:
[Cr = - 0,
C
+00,
Ca: +
generalized real-valued convex function of a. As in Algorithm 1, for ACVI we also have the same projection matrix:
P - CT(CCT
(P.)
and:
d و ''c
(d.-EQ)
where P. E Rax= and de E R".
The augmented Lagrangian of (ACVIssubproblemm) is thus:
Ca y, A) F + I (Cx = d) - Σ Tog(-p:(y)) + (A, x - y) + || y1 (AL.
where 3 > 0 is the penalty parameter. Finally, using ADMM, we have the following update rule for step k:
1h+1 arg min Cx( yk )v)
(Def-X)
B yk 5 (F((ux) + As))
1
arg min =
This yields the following update for a::
Øk+1 Pe yk
(F(ws) + +Xa)) de.
(X-EQ)
For and the dual variable X, we have:
yk+1 argmin Co(xx+11 y: Ax)
(Def-Y)
argmin ( log (p(())
B
1 A
y xb+1
(Y-EQ)
B
To derive the update rule for we is set to be the solution of the following equation:
w P.F((n) Payk + 3 P.dx
de = O.
(W-FQ)
The following theorem ensures the solution of (W-EQ) exists and is unique, see App. B in (Yang et al., 2023) for proof.
Theorem A.3 (W-EQ: solution uniqueness). F F is monotone on C_, the following statements hold true for the solution of (W-EQ):
1. it always exists,
2. it is unique, and
3. it is contained in C=.
Finally, notice that wo as is redundant to be considered in the algorithm, since we = 2 +1+1 and thus removed.
16

---

Published as a conference paper at ICLR 2024
Algorithm 3 (exact) ACVI pseudocode (Yang et al., 2023).
1: Input: operator F; X + IR", constraints C d and (x))) < 0, = [m], hyperparameters 111, > 0, E (0, 1), number of outer and inner loop iterations T and K, resp.
2: Initialize: yo E R", Ao E ER"
3: P. I -CCTCCC--
where P. E R
4: d. a CT(CCT)-Ld
where de E IR"
5: for t O...., -1
6:
7: for k 0. ..... K do
8:
Set at k+1 to be the solution of: x: + P.F()) - Pay (9)
(8)
+ 1
3 P. (9)
de = 0 (w.r.. x)
9:
yk+i = argmin μ -E m log (- ( (p(()) + 0 y k+1 8^
(8)
k+ ( + B (t) (01
(0)
11:
end for
(g) (++1)
(1) )
A
13:
end for
The ACVI algorithm.
Algorithm 3 describes the (exact) ACVI algorithm (Yang al., 2023).
A.4 EXISTENCE OF THE CENTRAL PATH
In this section, we discuss the results that establish guarantees of the existence of central path. Let:
S(x,A, F(x) + (x)) + CTV,
and
h(x) = C d.
For (A, w. V) E 2 let
w X
w + sp(xr L(x, A. h(x)
G(A w. v) &
R 2m+
and
w + +(xxx
H(,, w. 2)
L(xx, X v)
E R mttn
h(x))
Let H++ H(R x Rd x RP).
By (Corollary 11.4.24, Facchinei & Pang, 2003) we have the following proposition.
Proposition A.4 (sufficient condition for the existence the central path). If F is monotone, ei- ther F is strictly monotone one of yps is strictly convex, and C is bounded. The following four statements hold for the functions and H:
1. G maps 2m
Bu+p homeomorphically onto R. H H4+:
2. IT H4+ C G( 1R*;));
3. for every vector a E RT, the system
H(), w, x. v) 0, w e X = a
has a solution (A, w, x, v) E 1R?m x t== and
4. the set H+4 + is convex.
17

---

Published as a conference paper at ICLR 2024
A.5 SADDLE-POIN OPTIMIZATION METHODS
In this section, we describe in detail the saddle point methods that we compare with in the main paper in 5. We denote the projection to the set X' with 1Ix, and when the method is applied in the unconstrained setting IIx = I.
For an example of the associated vector field and its Jacobian, consider the following constrained zero-sum game:
min max f011, Eiii EyE
(ZS-G)
where f 21 X2 R is smooth and convex in æ and concave in æ2. As in the main paper, we write x 2 (2) IR. The vector field F: X IR and its Jacobian are defined as:
V f())()) (=)(
f(x) J(x)= Ve, V fxx
V Va, f())
F(x)=
V f
In the remaining of this section, we will only refer to the joint variable and (with abuse of notation) the subscript will denote the step. Let yy E [0, 1] denote the step size.
(Projected) Gradient Descent Ascent (GDA). The extension of gradient descent for the cVI prob- lem is gradient descent ascent (GDA). The GDA update at step is then:
1
Ixx D (xxx))
(GDA)
(Projected) Extragradient (EG), EG (Korpelevich, 1976) uses "prediction" step obtain an trapolated point - using GDA: x 1 = 1Ix (ax ( (xx)), and the gradients at the extrapolated point are then applied to the current iterate z,:
Ik+1 = IIx
as - yF [Ix - -F((x)))
(EG)
In the original EG paper, (Korpelevich, 1976) proved that the EG method (with a fixed step size) converges for monotone Vls, as follows.
Theorem A.5 (Korpelevich (1976)). Given a map F: X + R", if the following is satisfied:
1. the set X' is closed and convex,
2. is single-valued, definite, and monotone on X-as per Def. 2.1,
3. F is L-Lipschitz-as per Asm. A.I.
then there exists solution x² X, such that the iterates 2tk produced by the EG update rule with a fixed step size 7 E (0, } converge to it, that is æy -> x², as k. 0o.
Facchinei & Pang (2003) also show that for any conve--concave function f and any closed convex sets Φ E X1 and x2 E X2, the EG method converges (Facchinei & Pang, 2003, Theorem 12.1.11).
(Projected) Optimistic Gradient Descent Ascent (OGDA), The update rule of Optimistic Gradient Descent Ascent OGDA (OOGA)) Popov, 1980) is:
In+1 Ixx (In 2yF((n)) + +=((==))))
(OGDA)
(Projected) Lookahead-Minmat (LA). The LA algorithm for min-max optimization (Chavdarova et al., 2021), originally proposed for minimization by Zhang et al. (2019), is a general wrapper of "base" optimizer where, every step l: (i) copy of the current iterate H, is made: i, + Fn. (ii) t., is updated k 2 times, yielding Wa+k, and finally (iii) the actual update 2a+1 is obtained point that lies line between the current F. iterate and the predicted one .
En+1 f- In + alăn+* In),
1].
(LA)
In this work, we use solely GDA as base optimizer for LA, and denote it with LAK-GDA.
Mirror-Descent. The mirror-descent algorithm (Nemirovski & Yudin, 1983; Beck & Teboulle, 2003) can be seen as generalization of gradient descent in which the geometry of the space is controlled by a mirror map V X + R. We define the Prox(-) mapping:
1 Dw xn))
Prox g) argmin exx T x + γ
18

---

Published as a conference paper at ICLR 2024
where Dy is the Bregman divergence associated with the mirror map V & + I, characterizing the geometry of our space. The mirror descent algorithm uses the Prox mapping to obtain the next iterate:
En Prox F(xn)).
(MD)
Mirror-Prox. Similarly Mirror Descent, Mirror Prox (Nemirovski, 2004) generalizes extragradi- ent to spaces where the geometry can be controlled by mirror map VD;
1121 f- (an, F(xx)),
a 1 f- Prox( F(2n+1/2))
(MP)
19

---

Published as a conference paper at ICLR 2024
B MISSING PROOFS
In this section, we provide the proofs of Theorems 3.2 and 4.1, stated in the main part. In the subsections B.3 and B.4, we also discuss the practical implications of Theorems 3.1 and 3.2, and the algorithms that can be used for the subproblems in Algorithm 1, respectively.
B. PROOF OF THEOREM 3.1: LAST-ITERATE CONVERGENCE OF ACVI FOR MONOTONE VARIATIONAL INEQUALITIES
Recall from Theorem 3.1 that we have the following assumptions:
F is monotone on C=, as per Def. 2.1; and
either is strictly monotone on C or one of ip is strictly convex.
B.1.1 SETTING AND NOTATIONS
Before proceed with the lemmas needed for the proof of Theorem 3.1, herein we introduce some definitions and notations.
Subproblems and definitions. We remark that the ACVI derivation derivation-givven in App. A.3 is help- ful for following the proof herein. Recall from it, that in order derive the update rule for æ, introduced a new variable w, and the relevant subproblem that yields the update rule for æ includes term (F(w), æ), where F is evaluated some fixed point. As the proof relates the x( iterate of ACVI with the solution xi (KKT-2), in the following we will define two different maps each (f) That is, for convenience, define the following maps from with fixed x and = #k+1 =x
R" to R:
(0) (x) A F( (Cr d),
((0)
(1) f( (x) a F( 1(Cx d), and m
m
where x is a solution of (KKT-2) when μ = pt, and #i++1 is the solution of the æ-subbroobem in ACVI at step (t, ke-see line Algorithm Note that the existence of x is guaranteed by g (y) 14 log (p(())) Σ (1() 14),
(g)
the existence of the central path-see App. A.4. Also, notice that f()), f(()) and g(t) are all convex functions. In the following, unless otherwise specified, we drop the superscript (1) of a K+1 ((), f and subscript i of b4 to simplify the notation.
In the remainder of this section, introduce the notation of the solution points of the above KKT systems and that of the ACVI iterates.
Let y x² In this case, from (KKT-2)
that (æ' yn) is optimal solution of:
min f(x) + g(y)
(f-Pr)
s.l. x
There exists A E R2 such that (x" y" Aa) is a KKT point of (f-Pr). By Prop. A.4, a² = yd converges solution of (KKT). We denote this solution by x² Then (x1 y", A²) converges to the KKT point of (ACVIsuubrobbeem) with we = x Let (x", y X²) denote this KKT point, where x = =y
On the other hand, let us denote with (of yh: A() the KKT point of the analogous problem of fx(-) of:
min (x + g(v) z.y
(fi-Pr
s.t. x y
20

---

Published as a conference paper at ICLR 2024
Note that the KKT point (xt yg x is guaranteed to exist by Slater's condition. Also, recall from the derivation of ACVI that (fe-Pr) is "non- monnssymetrii"" for æ, when using ADMM-like approach, in the sense that: when we derive the update rule for we fix y to y (see Def-X), but when we derive the update rule for we fix æ to #k+1 (see Def-Y). This fact is used later in (LB.3-1) and LB.3-2 in Lemma B.3 for example.
Then, for the solution point, which we denoted with (arf VK > we also have that o = yh By noticing that the objective above is equivalent to F( T + (Cx = d) - Mr -i=1 log
pp: (v)), it follows that the above problem (fx-Pr) is an approximation of:
min (F(2*+1), x) + 1 1(Cx d) (
(fx-Pr-2)
y where, a reminder, the constraint set C C X' is defined as intersection of finitely many inequal- ities and linear equalities:
s.t.
C= E (p))())) s 0, E [m]] Cx - d}:
(CS)
where each : + R. C Rex" d E R", and we assumed rank(C))
In fact, when μ + 0+, corollary 2.11 in (Chu, 1998) guarantees that (a* y X converges to a KKT point of problem (fa-Pr-2)--we) which immediately follows here since -P-22) is convex problem. Let (mrg Vi: Ai) denote this KKT point, where zi = Vi-
Summary. To conclude, (x" .e A²) ) the solution of (f-Pr), converges to (x" (=".y", (²), KKT point of (ACVIsuubrobbeem) with we = x", where x" y St.Fi (a yi X converges to (ot yū At)-a KKT point of problem (fi-Pr-2), where (x y X (in which x = y is KKT point of problem (fi-Pr). Table 1 summarizes the notation for convenience.
Solution point
Description
Problem
(x" yy X*)
cVI solution, more precisely x= = y² E St,F
(cVI)
central path point,
(aotie, you A
(J-Pr)
also solution point of the subproblem with fixed F()"))
solution point of the subproblem with fixed F( where the indicator function is replaced with bog-barrier
(att uk X
(fi-Pr)
(o% vh. A
solution point of the subproblem with fixed F(x (f) k+1
(fx-Pr-2)
Table Summary of the notation used for the solution points of the different problems. (fx-Pr) (() an approximation of (fu--rr2) which replaces the indicator function with bog-barrier. The t emphasizes that these solution points change for different (t)). Where clear from the context that we focus particular step we drop the super/sub-script to simplify the notation. See App. B.1.1.
B.1.2 INTERMEDIATE RESULTS
We will repeatedly use the following proposition that relates the output differences of fa(-) and f(-). defined above.
Proposition B.1 (Relation between fú and f). If F' is monotone, then Vk E N, we have that:
fa - fu(x²) 2
Proof of Proposition B.I. It suffices to notice that:
fx(#x-1) fa(a* - (f(# f(x*)) (F(*x+1) F(x"), Øx+1 x*).
The proof follows by applying the definition of monotonicity to the right-hand side.
21

---

Published as a conference paper at ICLR 2024
We will use the following lemmas.
Lemma B.2. For all æ and y, we have:
((x) + gly) s(x") )- -9(0)) (X*, x - y) 2 0,
(LB.2-f)
and:
fx(2)) + g(v) - fx((x)) s(v(() + (2 x y) 20
(LB.2-fa)
Proof. The Lagrange function of (f-Pr) is:
L(x, y, A) = f(x) + gty) + (2, 1 y).
And by the property of KKT point, have:
L(x", y , < L(x", y" (²) S L(,, v(E,y,A),
from which (LB.2-f) follows.
(LB.2-ft can be shown in an analogous way.
The following lemma lists some simple but useful facts that we will use in the following proofs.
Lemma B.3. For the problems (f-Pr). (fk-Pr) and the æh yk R of Algorithm 3, we have:
0 E 0 0f + Rx + (xx++1 yk), 2 - 3axx+1 - vx+1),
(LB.3-1)
0 E 0g(Ux+1)
(LB.3-2)
AR+1
A = 3(
-k+11)
(LB.3-3)
A" E 0f(x)),
(LB.3-4)
X E (zf()
(LB.3-5)
X E Og(v"),
(LB.3-6)
N e Or(v(), x" y".
(LB.3-7)
(LB.3-8)
x = yt
(LB.3-9)
Remark B.4. Since g is differentiable, 0g could be replaced by Vg in Lemma B.3. Here we use Ög so that the results could be easily extended to Lemma B.31 for the proofs of Theorem 4.1, where we replace the current g by the indicator function 1 (yy( < 0), which is non-differentiable.
Proof of Lemma B.3. We can rewrite (AL) as:
B 2
Co = (z) ( (A, y)
yl
(re-AL)
(LB.3-1) and (LB.3-2) follow directly from (Def-X) and (Def-Y), resp. (LB.3-3) follows from line 10 in Algorithm 3, and (LB.3-1) follows by the property of the KKT point.
We also define the following two maps (whose naming will be evident from the inclusions shown after):
v (2 2 - - -((xx+1 yk), and
(vf+)
Vg(Ukt1) A A + 3(xx+) Dk+1))
(4))
Then, from (LB.3-1) and (LB.3-2) it follows that:
- fi (xx41) (xx(4))) and &g(2)+1) 0g(He+1).
(I)
We continue with equalities for the dot products involving V and Vg.
22

---

Published as a conference paper at ICLR 2024
Lemma B.5. For the iterates 2k+1, to++, and A of the ACVI Algorithm 3-we we have:
(Vg(yk+1). 9k+1 y) = 11 yk++1),
(LB.5-1)
and
(24+ 2) + (Vg(y++1). yk41 - y) = (AE+1, yi+ 1 + y)
3 + yk. 1x+1 x))
(LB.5-2)
Proof of Lemma B.5. The first part of the lemma (LB.5-1), follows trivially by noticing that (g((k++1) Ak+1-
For the second part, from (LB.3-3), (V fi) and (Vg) we have:
(Ax + B(xx+1 ya), 0k-1 x)) (Vft(**+1), x) = (A8+1, Lk+1 - x) + 3( - + yks 0k-1 xK-1-- x),
(2)
yk+t
and
(Vg(y641). 9k+1 y) = (Ax++1: y yk+1))
Adding these together yields (LB.5-2).
The following Lemma further builds on the previous Lemma B.5, and upper- bounds some dot prod- uets involving fsx and Vg with a sum of only squared norms.
Lemma B.6. For the BE+1 I,+I and A iterates of the ACVI Algorithm 3-we
we have:
(Vf((<++1)) Øk+1 - x²) + (g yk+1 - yy) > + (A", 0b+1 - yk-1)
1
B 1ly" yx 11 yi++1l?
De 111112
| X" 1
23
23
3
A - Avl12
lly: 12
23
2
and
(
(x 0k+1
x
+ (Vg(3)++1)
Bk++ ytt + (Ni Øb+1 - 3
1
-/1112
Ax+1 X/4 ||
- 1 yı 11 y 112
2
23
|A4+1 - Ao
2 11y
32
233
Proof of Lemma B.6. For the left-hand side of the first part Lemma B.6:
LHS = (V fu(2x- 0b+1 - x²) + (V g (3)++1)) Ms++1 y²) + (A" 2x+1 yk+1), we let (x,y, A) = (x" y", A²) in (LB.5-2), and using the result of that lemma, we get that: yk+1 x" + y B yh++ + yks 2k+1 x²)) + (A" #1 yk+1),
LHS = -N
and since x² 4d (LB.3-8):
LHS = - (Ak+1, Tb++1 1 + B yk++ + yk. #k+1 x²) + (X Tk++1 yk+1)
(Ax+1 X" 0c+1 1 ) + 3( yv++ Yk, 0x+1 x!"),
where in the last equality, combined the first and last terms together. Using (LB.3-3) that 3 (Aa+1 - A = (Ø yk+1) yields (for the second term above, we add and subtract y in its second argument, and use xx = "));
LHS = 3 (AR+1 - X", A641 A&) + (- UK+1 + yk. A641 AE)
B. 4k+t yk. Uk+1 yd)
23

---

Published as a conference paper at ICLR 2024
Using the 3- 3-point identity- that for any vectors a, b, it holds (b a.b - c) 22(laa bll +
||b ell² lla - ccl²)_ for the first term above we get that:
xell-- -||x+11 2n112), (A-11 X", AK+1 >a) 2 2 x²11 ||
and similarly,
(- yk: + + yyy = 2 yv + -=111= -101--11--000
yk+l + y² 111-
y- + +2k yx112)
and by adding these together, we get:
1
1
LHS
AE
X²11
AR+1 X²11
A -
23
2/3
2
3
33
+
y + 1²1
11 + +z²113-
1- + yykl
2
2
2
+ yk-1 + yk: Ab+1 Ab).
(5)
On the other hand, (LB.5-1) which states that (Vg yk++1 y) + (Ak+1, yk+1 + y) = 0, also asserts:
(Vg(v)), yh - y) + (Ax: yy + y) =.
(6)
Letting y = yı (LB.5-1), and y = yk+1 1 in (6), and adding them together yields:
(Vg(y)+1) - Vg(y)), y yk) + (A++1 As yk+1 + yk) 0.
By the monotonicity of 0g, we know that the first term of the above equality is non-negative. Thus, have:
(AR+1 AR. Uk-1 + yk) S 0.
Lastly, plugging it into (5) gives the first inequality of Lemma B.6. The second inequality of Lemma B.6 follows similarly.
The following Lemma bounds the sum of (i) the difference of f()) evaluated 0&+1 and at x and (ii) the difference of g(-) evaluated at ys+11 and at y": up to a term that depends on #k+1 Vk+1 well. Recall that (æ" y", X²) is point the central path.
Lemma B.7. For the 0k+1, yk++, and AR+1 iterates of the ACVI Algorithm 3- we have:
f(xx+1) + ((8k+1) f(x") - g(x0)) + (A", xx+1
yk+1)
1
<
A
1=112=
|
11
2,3
2
8
8
+
| + yz
11
-1 + y²
2
1
A6t1
- Axll2
11-yyc+1 + t1ull
(LB.7)
23
2
Proof of Lemma B.7. From the convexity of (x)) and g(y): from proposition B.1 on the relation
between fx(()) and f(-) which asserts that f( (x* < fa( - S& (x**); as well as from
Eq. (1) which asserts that V (xx+1)) (fx(( and (g(( 0g ()) it follows for the
LHS of Lemma B.7 that:
f(x*) (( + (A", :i+1 - Mbt1)
I fa((x+1) + g(()++1))))))))))))) fx - g(x")) (X* xb41 gk+1)
(8)
< (20440)1) x²)) + (Vg(v++1), yh+1 y²)) + (A", 2b+1 yb+1)
24

---

Published as a conference paper at ICLR 2024
Finally, by plugging in the first part of Lemma B.6, Lemma B.7 follows, that is:
f(0++1) + ((vx+1)
f(* ( + (A* Lk+1 ys+1)
1
A 22112-
At+1 1
2
2
3
3
(9)
1-yy
Uk + y12
yk-1 -
2
2
1
8
1x+1
yk+1 + 31111
23
2
The following theorem upper bounds the analogous quantity but for fa(-) (instead of f as does Lemma B.7), and further asserts that the difference between the 2&+1 and yk+1 iterates of exact ACVI (Algorithm 3) tends to 0 asymptotically. The inequality in Theorem B.8 plays an important role later when deriving the nonasymptotic convergence rate of ACVI.
Theorem B.8 (Asymptotic convergence of (IX++1 yk+1) of ACVT). For the Es+1, yk++, and At+1 iterates of the ACVI-Algorithm 3-we have:
fx(+++1)= fx(**) + (()++1) -g(3%)
S | || - yk+ill + Blyk+11 |al11| - ax + 0, (TB.8-fa-UB)
and
#k+1 yk++ 0, as k 00.
00.
Proof of Theorem B.8: Asymptotic convergence of (œx+1 yk+1) of ACVI. Recall from (LB.2-f) of Lemma B.2 that by setting x = 2++1. yk++1 we asserted that:
((x+11 f(x"' g(yx+1) ,yy" + (X* #x+1
yk+1) 2 0.
Further, notice that the LHS of the above inequality overlaps with that of (LB.7). This implies that RHS (LB.7) has to be non-negative. Hence, we have that:
1
1
28 Ax+1 Axll2 2
yk+ + 12 -
A
1212
|AR+1 - 1!1
2
23
(10)
3
3
yı +
y²1l
yk-1 + y²1l?
2
Summing over 1e O...... 00 gives:
3 2 >xl12
1
3
R=O 23 ARTTI
yk+1 11
y1zl3))
1o
2d11
2
911-y0
yo 11
2.
from which we deduce that As+1 A 0 and ya++
Vv. -
Also notice that by simply reorganizing (10) we have:
Ax+1 2
Uk++
1
2
2
1
3
| 11
yk + n"
23 14411
Ax1l= -/
-1-1-- M
23
1
3
+
1 yk + y 112
2,
2
8
|A
2
yo
23
(II)
where the second inequality follows because the norm is non-negative.
25

---

Published as a conference paper at ICLR 2024
From (11) can see that || 1= and 11y yl are bounded for all k, as well as | Recall that:
AK+1 X2 (( yk+1) = (x x²) + 3( yk++1 + +y"",
where in the last equality, we add and subtract x y" Combining this with the fact that A++1
A + O (see above), we deduce that 0x-1 yk++ + 0 and that 2x+1 x² is also bounded.
Using the convexity of f-) and g(-) for the LHS of Theorem B.8 have:
LHS
fıx (xx+11) fx(()() + g(v++1) (
I (V ( Fx+1 - axt + (Vg(31+1)) yk+1 - y/"
Using (LB.5-2) with x = xx = y we have:
LHS v -AA+1. xx+1 - ys+1 t + y ) + 3
yx+1 +
06+1 - =x/)--
due (LB.3-9)
Hence, it follows that:
fa( - fa (2xf) g(v++1))))))))))))))))))())))( - ((y)
S (A++1, Ik+1 yk+1) B( (1+ + yk. 2k+1 2x2))
$ | Øk+11 ye+ill + 3 |1 yxll [0+11 x
where the last inequality follows from Cauchy-Schwee Recall that C is compact and the diameter of C:
D a sup || yl
x y.yCC
Thus, we have:
yk+1 2/2l = |1 ynll + 11 - y S |1 - 30 + D,
which implies that |//k yt are bounded for all k. Since:
A6+1 D B(xx+1 ya+1) f(0241 x 1--3(-yss yy++1 + +vh))
we deduce that 0b+1 2 is also bounded. Thus, we have (TB.8-f--UB).
The following lemma states an important intermediate result that ensures that 1
23 A >xa +
d -1- yk+1 + y does not increase.
Lemma B.9 (non-increment of 23 | - Au 11 +
61l 211- + 1), For the 0i41 Dh4 and
A++1 iterates of the ACVI ACVI-Algorithm we we have:
2 + 3 5 yk + 2 23 28 A >x112
B 2 1111 + 111111 (LB.9)
A - +
2
2
Proof of Lemma B.9. (LB.5-2) gives:
(V fk-1 (xx) ,. xx) + (Vg (yx) y) 4)
(12)
= (Ax, - 3k x + 4) + B yb + yb
2h -x).
26

---

Published as a conference paper at ICLR 2024
Letting (x, y. A) (ætg, yk: AA. in (LB.5-2) and y. (I++1, Yk AR+1) in (12), and adding them together, and using (LB.3-3) yields:
(V fe (I++1) fx-1 (2x), #k+11 m*) + (Vg (3k-1) - (Bkk. 3k++1 - yb)
(Ae+1 AR. Ix+ uk+1 3 + yk) + B yk++1 + y/ yk + yk-1) 3x+11 xkk)
1
B (A&+1 Ak+1 Ax= - -(A: -
+ (-yn+1 + UUk + (3yk - -2- 1). AR+1 - As + 3yk+1 (>x - A + Byn))
1
[lAA 11-1112 10-112240 ||x++1 >a.12 - -11 - d== - -Ax >x=-))1
28
3
+ 2
[|| yk + yk- yk-111 112 - 11 11 yk+1 + yx 112 - 11 yk+1 + +y - (-yx + 11111)11
+
(- Vk+1 + yk - ( yk + yk 1) x++1 - A - (At - -x=-1))
1
(1Ax A 1| | A/ Ax113 129) + 3 (11-)1 yk + -/--11 11 -11 11-yk++1 + 19:11²)
28
1
3
| d (Ak A 1111)112
Vk+1 + yk (-yyk
yk +
1112
2/3
2
+
1-yx+1+ + - ykk + yk- Au+1 As3 - (Ax - -k-1)))
1
3
(12x- 1 | An 11²)
+ (1 U) yk= 112 -11- 11-+++1 + 3x113)
2B
By the convexity of fu and fx-1, we get:
(V fa 1x+1 xR) 2fc(((+11) fx((
-(V fK- F 2x) 2/6-1 - Sk- (2x++).
Adding them together gives that:
fe (Ix+1) - V fa-1 (Ix) Tb+1 - -xa) 216(2x+1) - fk- fx-1((14+) - fx(( + f
=(F(a(+1) F(ax)), FK+1 mx) 2 20.
Thus by the monotonicity of F' and Vg. (LB.9) follows.
Lemma B.10. F is monotone C=, then for Algorithm 3, we have:
JK (xx+1) + 9 (yK+1) - fK (a
(y
A"
A"
(LB.10-1)
22/A4
|| + VBD) V K+
K+1
v3
AP V [B(K+1]
and
|| - yk+ S
(LB.10-2)
where A 2 1 11 1=122 + B1300 - 11
Proof of Lemma B. 10. Summing (10) over h = 0, K and using the monotonicity of
D
1x + - 11 +
y from Lemma B.9, we have:
20
1 ||x+1 1x112 + 311 DK+1 + 9k
3
1
K
D - >x112 + B
2 111-yc+1 yott + vall²)
K +1 1
2/3
k=0
11:0 1²122 + -111-00 yo e211e)
(13)
K +1
3
27

---

Published as a conference paper at ICLR 2024
From this, deduce that:
3A"
B|lo+11 -KK+ll = ||X+I1- - AK S
K+1
A 13(K+1] +1)
11-yK+1 + yklls
On the other hand, (11) gives:
28 AK+1 - 1²1 2111 111 UK+1 + y01 S A..
Hence, we have:
|KK+1 X S 33D"
(14)
A"
UK9K1 + + 1 V
3
Furthermore, we have:
A"
1yk+1 - 2k S 11y K+1 -y + 11 3 S
+ D,
3
| - xkx
Ak+1-AKk - yK- + 5kkc
||x+t1 dxll + |1K++1 y
A"
A"
#1 B +D D.
B(K +1)
and
AK || < ||| + |AK+1 X $ ||a + 3BA..
Then using (TB.8-ft-UB) in Lemma B.8, we have (LBB37-1)).
Discussion. Lemma B.10 has an analogous form Theorem 7 in (Yang et al., 2023), but here we change the reference points from x and y" in (28) of (Yang et al., 2023) to x and y we newly introduce in our paper. We stress that this change, together with our observation that at is the reference point of the gap function at D (see (16)), is crucial to weakening the assumptions in (Yang al., 2023). We can see this from the following proof sketch of Theorem 3.1:
1. Lemma 10 gives
1 VK
fK (*K+1) + g (yK+1) - fK (x*)) (y O
2. Note that g(yK41) - ( + 0, x x when P 0. Using the above inequality, we have that when is small,
(xx+) (xx)) 0(
VK
3. With observation (16), we could write the gap function at #1+1 explicitly
f(æK+1, fx (# fx (=x)-
Combining the above two expressions, we reach our conclusion:
(( = O(
28

---

Published as a conference paper at ICLR 2024
In contrast, (Yang et al., 2023) gives the upper bound w.r.t the gap function through two indirect steps, each introducing some extra assumptions:
1. Theorem 7 in (Yang et al., 2023) gives
JK (ØK+1) + (yK+1) - Sx (x*) - (y") - O
which leads (#(=)) x-)| = ) and (F(x=') x²)) 0 (
(the first indirect bound) when μ is small enough.
2. Under either the É-monotonicity assumption in Thm. 2 or assumption (iii) in Thm. 3 of (Yang et al., 2023), they are able to bound the iterate distance using the above results as follows:
| x"1 = O( VK
(the second indirect bound).
3. Finally, by assuming Lipschitzness of F, they derive from the above bound that
G( = O
VK
B.1.3 PROVING THEOREM 3.1
We now ready prove Theorem 3.1. Here, we give nonasymptotic convergence rale of Algo- rithm 3.
Theorem B.11 (Restatement of Theorem 3.1). Given an continuous operator F: X R", assume that:
(i) F is monotone on C=, as per Def. 2.1;
(ii) F either strictly monotone C or one of Pps is strictly corvex.
(1) Let (xx 3K AK denote the last iterate of Algorithm 3. Given any fixed K E N4, run with sufficiently small p-1, then for all E [T], have:
(1)
2A K +
1 A
A VBD+1++A K
g(
2
(na-Rate)
and
A
|
k
||| 2
(15)
3K
where A A 1110 2+ Bl
1²1 and D A
sup
| UlI. and M - sup [F())]
2.EEC
xEC
Proof of Theorem B.1l. Note that
(fx-Pr-2) + min (x+11),
mEC
+ max [F (2
Db+11 x))
#ec
+ C(
from which we deduce
G(xx+1,C) = (F(xx41) Et+1 xt) Vk.
(16)
For any fixed K E N, by Corollary 2.11 in (Chu, 1998) we know that
2 + xk
((yx+)) g(y + 0,
" 1
3 11:0 21
Bl1 1112 A.
(17)
29

---

Published as a conference paper at ICLR 2024
Thus, there exists μ-1 O, s.t.V0 < μ p-11
A
| - x $ V
K +11*
A"
-(yk+1) - g(unk) $ V
K ++1
Combining with Lemma B.10, have
(F(*K+1): Ik+1 xxx)
fx (IK+11) - fK (2l())
A
(2VA"+ + J | + VBD) V K K+1 tgl 9 (2K+1) (18)
AP
K +1 +
A"
(2VA*+ 1/ vB |* 1BD+1) V
AM
+
K ++1*
K +11
Using the above inequality, we have
G( = =F Øk+1 xkk
(19)
=(F(IK+1) 0K+1 xxx + (F(#x+1), 2 -
(20)
<(F(xr++)) 1); #K+1 x²x) + +1[ )|l 1a0 æ'xl
(21)
A' (2VA"=
A"
| + VBD+++
(22)
K +11*
K+1
Moreover, by (17), we can choose small enough μ-1 so that
G( 5
2A
+2
2
1 VB
a VBD+1+
A
K K+1
K+1
and
A
| - yK+1|
2
(23)
B(K+1)
where (23) uses (0B.1 in Lemma B.10.
30

---

Published as a conference paper at ICLR 2024
B.2 PROOF OF THEOREM 3.2: LAST-ITERATE CONVERGENCE OF INEXACT AC FOR MONOTONE VARIATIONAL INEQUALITIES
B.2.1 USEFUL LEMMAS FROM PREVIOUS WORKS
The following lemma is Lemma from (Schmidt et al., 2011).
Lemma B.12 (Lemma 1 in (Schmidt et al., 2011)). Assume that the nonnegative sequence } satisfies the following recursion for all k 2 1:
u S Sk
A
with { an increasing sequence, So un and X for all i. Then, for all k 1, it follows:
2
1/2
-
X + Sx +
A
2=
Proof. We prove the result by induction. is true for (by assumption). We assume true
for k - 1, and we denote by uk-1 = max Ux-1). From the recursion, we deduce:
X
(ux= >x/2)² < Sk
+ +
uk-1
Ai
(24)
4
1=1
leading to
dx
X2
h-1
1/2
uk S
Sk +
+
U/ 1
A
(25)
2
4
and thus
dk +
X
k-1
1/2
S
max
0k-1;
Sb +
+ ck
1k-
k:
X
(26)
2
4
1=1
1/2
Let 1t_ A D do +
Sx +
( Σ (# 21) 1
Note that
d +
X2
k-1
1/2
uk
Sk
+
Uk
1
A
2
4
> 8k
1
Since the two terms in the max are increasing functions of Uk-1, it follows that if uk S 1 then 2k I - Also note that
1/2
Uk 2 Ak
X + 0k 1
k-1
+
Sk +
A
2
4
1 2 1k-11
From which we deduce that if uk-1 that the property satisfied for k.
2 1 then e I Uk-1, and the induction hypotheses ensure
In the convergence rate analysis of inexact ACVI-Algorithm 1, need the following definition (Bertsekas et al., 2003): Definition B.13 (e-subdifferretiaal). Given convex function & R + lR and positive scalar s, vector a E R is called an e-subgradient of sa at a point x E domp if
(²) 2 vb(xr) (z T) 8, Vz R
(e-G)
The set of all e-subgradients convex function v0 at æ E dome is called the e-subdifferential of w, and is denoted by 0.
31

---

Published as a conference paper at ICLR 2024
B.2.2 INTERMEDIATE RESULTS
We first give some lemmas that will be used in the proof of Theorem 3.2.
In the following proofs, we assume én do = O. We need the following two lemmas to state lemma analogous to Lemma B.3 but for the inexact ACVI.
Lemma B.14. In inexact ACVI-Algoritam for each
each k. 3 Th+1 E IR" || S V 3
2e411 s.t.
B(xx+1 + g A - yk+1 - -k++1) E 9VVk+1)
Proof of Lemmna B.14. We first recall some properties of e-subdiiferentials (see, eg. (Bertsekas et al., 2003), Section 4.3 for more details). æ is an s-minimizer (see Def. 2.4) of a convex function & and only if 0 (x)(). Let t
d/ 4/2, where both t and the are convex, have O, (xx) C
(,v1(z) (2)) 1/1 (x)
& ||
=1|² then
B y R
y
(z)1(x)
SE
2
3
B ||||
y E Ra y 3x Bz + Br
S
2
Let 1/2 = 9 and z Ib+1 + AA,, then uk+t1 an Ex-r-minimizer of 1/1 + 1/2 Thus we have
E Sen ((y++1) C dex w (1)+1) + 1 (2 Hence, there is an +x+1 such that
1 3(0x+1 + zdx ykt1 Tk41) E ( with || 2Ek+1
3
Lemma B.15. In inexact ACVI-Algorithm for each k, 3 qk+1 R", ||gk+1l S o s.t.
3
Øs+1 + qs++1 = arrgmin fx(()) +
x
+ Au
(27)
2 where Cg is the augmented Lagrangian of problem (fx-Pr).
Proof of Lemma B.15. By the definition of 2x+1 (see line of inexact ACVI-Algorithm and Def. 2.3) we have
1
0k+1 + 4k+1 = PoF(x) + Patk } Podu + de
B
=argmin Co(x, ys. Ax)
where Lg is the augmented Lagrangian of the problem, which is given in AL (note that wi 2b++1 (fx-Pr). And from the above equation (27) follows.
Similar to Lemma B.3, and using Lemma B.14 and Lemma B.15, we give the following lemma for inexact ACVI-Algorithm 1.
Lemma B.16. For the problems (f-Pr), (fa- Pr) and inexact ACVI-Algorithn we have
E 0f + 4x+1) + A + 3(xx++ - yyk) + 8.
(LB.16-1)
0 Osueng(UR+ dB B(xx+1 Mx+1) + 3r
(LB..162)
A&+1 A 3(0+11 yk+1),
(LB.16-3)
X E Of(a"),
(LB.16-4)
A asa(att)
(LB.16-5)
A Vo(2"),
(LB.16-6)
A Vg(vtt,
(LB.16-7)
T y", of D.
(LB.16-8)
(LB..169))
32

---

Published as a conference paper at ICLR 2024
We define the following two maps (whose naming will be evident from the inclusions shown after):
(x(+++1 + qk+1) _ -Ax B(x++1 yk) 3qk+1, and
(noisy-V
V VeL+ig(yR+)) & X 3(xx+1 yk+1)) BT&+1
(noisy- Vg)
Then, from (LB.3-1) and (LB.3-2) it follows that:
(m + q++1) E 0f + qk+1) and ((1+1 E denti
(VV++1)
(28)
The following lemma is analogous to Lemma B.5 but refers to the noisy case.
Lemma B.17. For the iterates #k+1. yk+1, and A6+1 of the inexact ACVI Aoyo-iiigrihhmm I-we have:
Venng yk+1 y) -0K++1.9 - yk+1) - 3( k+1, yk+1 - y),
(I.B.17-1)
and
(V + qk+1),, 2x+1 - x)) (V 91 y)
(1411 Wk+1 x + y) + 3 yh++ 2k+1 x) Blgk+1, 0b+1 - x) - (rTk+1, y - y)
(LB..172)
Proof of Lemma B.17. From (LB.16-3), (noisy- via and (noisy- Vg we have:
(V + qu+1) + Squ+1, Øk+1 - x) = (As + 3(xx+1 yk)) 0x+1 - x))
=- (XE+1, 2x-11 xx) B(- yh+ + yk. 2k+11 x)),
and
(V ck+ ( + 381411 y) = --AA++1. ym+1).
Adding these together yields:
(V + (x+1) + 3q - x) + (V (Ve119((6+1) + Bre+i yk+1 y)
(A++1, 24+1 Vk+1 2 + y)
+ 3(- + yk. Tb+1 - x)
Rearranging the above equations, we obtain (LB.11-1) and (7B.17-2).
The following lemma is analogous to Lemma B.6 but refers to the noisy case.
Lemma B.18. For the #k+1. yk++1 and Ak+1 iterates of the inexact ACVI Algorithm l-we have:
V fi (x 9k+1), 16+1 z²) + < ex+1 (B ys+1
4²)) + (X" xx-1 4k++1)
1
B 11y" -
A A21122
| 1 + 11 3x-l2²
2/
2
2
1
|
1x12 2
_
3 I1y:
U) yk+ 11
23
Tk, Wk+1
yk)
3 9k+1 y²) + Sh + Sk41 3(gx+1, 1k411 x²))
and
( fa (x + qk+1); xb+1 - x411) + < Ek g( yk++ -3/ + (Xi 0x-1 yk+1)
1
8 11 y 1 1|2
AA
-21112
|d8+1 1 + 1 yx11
2/3
2,3
1
8 11 y 11
|
28
-
-8(rK4+
Tk. 34++1 - yk)) 3( 3ktt v 5 + + -B(g Ck+1 -x())
33

---

Published as a conference paper at ICLR 2024
Proof of Lemma B.18. For the left-hand side of the first part of Lemma B.18:
LHS = (a + qc+1), 2k+1 xxt) + (V Ex
Di+1 - -y(" + (Ag: 2R+1 - yk+1),
we let (ar, y. A) = [a"","" X²) in (I.B.17-2), and using the result of that lemma we get that: LHS (AE+1, 2k+1 yh++1 x² y" 3( yk++1 yk Lx++1 x²))
B(qR+1, 2k+1 x²)) 3(1++1, yk+1 y²) + (A 0x+1 yk+1)>
and since x" y" (LB.3-8):
LHS (AR+1) Fk++1 yk++) + 3 31+ + yks 2k+1 - x²)) (A", xx+1 - yo+t)
B(gu+1, Fk+1 - x²)) ( ; y²)
(Ax+1 - X", "8 - 4/++) + 9k+1 + yks Fk+1 x²1)
((gx+1, 2k+1 Fk+1 x²)) (r Vi+1 y²))
where in the last equality, we combined the first and third terms together. Using (LB.16-3) that (A&+1 - Ax) - # yields (for the second term above, we add and subtract yk+1 in its second argument, and use 2x = )
1 (x+41 N Ax+1 As) (- Yk-1 + yk. ARt1 Au)
LHS 3
(29)
- y + yk yk+1 + y") - B(qu+1, #x41 - x²) - -1(Pk+11.k2+1 - y")
Using the 3-point identity, that for any vectors a, b, c it holds (b - a.b-aa. c) ==(laa - b1l² +
|bb ell2 ||a - =, for the first term above, we get that:
(AR+1 A", ARtI Au) = - (1 - X0 | - Aull -
and similarly,
1 (11 yk + 8n1l - yk+1 + 3411 || yx+t + yxlll).
(- + yk: Ye+1 + +y²) =
and by plugging these into (29) we get:
1
A 2²122 - 1
LHS 23 1>x 2=122
A - Axel?
23
28
3
B
+ y1 yk + 11
Yk++ + 101
11- + yx
2
2
2
+ (- yk+1 + yk, A - Aa) - ((gh+1, 0x+1 - x² - 3(rrr+1, Uk+1 - -² (30)
On the other hand, (LBB. (LB.17-1) which states that (eu+gg(()+1): yk+1 4) + (Ax+1, -k++1 + y)
- ((T++1 Mk+1 y), also asserts:
(Veng(yR). yk y) (Ax, - + y) ((r yk
(31)
Letting y yı (LB.17-1). and y yk++1 (31), and adding them together yields:
(Venng(yRe) - Ve,g (y:) ys+t - yn) + (AR+1 - -xs + + yx)
(32)
= - Tk. uk+1 yz)
(33)
By the definition of c-subdiiffrential as per Def.B.13 13 we have:
Ck + 9 2 )((n)) + V g(w)) Mkt1 yk), and
E + g())) -( (V ((1++1)) yu va+1).
34

---

Published as a conference paper at ICLR 2024
Adding together the above two inequalities, obtain:
(V cat ((v++1) VeLg(yk): ys+1 ya) 2 Ek++1 Ek
(34)
Combining (32) and (34), we deduce:
(Ak+1 Ak. Uk+1 + yv) < -8( Tki yk+1 yk.) + Ek+1 + Ek.
(35)
Lastly, plugging it into (30) gives the first inequality of Lemma B.18. The second inequality of Lemma B.18 follows similarly.
Lemma B.19. For the 1k+1, 1,++1 and XE+ iterates of the inexact ACVI Algorithh 1-we we have:
fa(0 + 9c+1) + ((v+11) - fx((x")
g(y" + (N Mx+1 + 9++1 Vk+11
1
$
As
- 12
Ax++1 - 112
23
2,3
8
8
+
Yk + 1²1
Vk+1 + y²1
2
2
|xR41
Aa112
yk+1 +vlll
28
2
|AR+1
1a11
8k - y 11
23
2
3((k+] Tk: wk+1 yk) ((rx+1, yk+1 - y²)
+ Ek + 2Ex+1 (g A X2 + 3(xx+1 - yx) + 3(xx+1 - -xx)))
(LB..9)
Proof of Lemma B.19. From the convexity of fa(x) and gly) and Eq. (28) which asserts that V fa( + (s+1) E (1 + (k+1) and V ge E Ponng(94:: follows for the LHS of Lemma B.19 that:
fa (x + 4k+1) + g(yk+1) fa(x**) - g(x0)))))))))))))))) + (X* mb+1 + gh+1 - yk+1) V (x + qk+1)) 3b41 + q x") + (VeL. y yk+1 8r)
Ek+1 + 1 9 9
Finally, by plugging in the first part of Lemma B.18 and using (noisy- v fi), Lemma 19 follows, that is:
f f( + gk+1) + 1(v++1) - f(x*)) g(v") + AA Tb+1 + 9x+1 yk+1)
$
A
20112
|x++1
11 + _ 1- yı + yd 1111-11-y
11-++111 + yd 112
2
233
B 11-y++1 + yvel - 3(rx+1 Pk; 9k+1 yk)
|
2x11
233
B(re411 Uk+1
4²4) + 6 + 2Ex+1
B(gK+1, 06++1
x²
(qK+1, A 2 3(x -yx) (.
1 |A
1
B - 1 + y111
8 -
<
-11112-
A 111 +
-1 yk+t + 3d
23
2,3
-2
|A
Ax112
2 11 -b++1 + 31112 2- 3(Tx+1 - Th: 3k+1 yk)
2,3
-B(TK+I: uk+1 4² + E + 2Ex+1
- -(uk+1, dE N + (Ix+1 yx) + 3(xx+1 - x²))
35

---

Published as a conference paper at ICLR 2024
The following theorem upper bounds the analogous quantity but for fix(-) (instead of f), and further asserts that the difference between the 0x+1 and yx+1 iterates of inexact ACVI (Algorithm 1) tends to asymptotically.
Theorem B.20 (Asymptotic convergence of (Øx+1 yk+1) of I-ACVI). Assume that Σi= (o: + vE,) +00, then for the Bk+1 yk+1, and Xx+1 iterates of the inexact ACVI-Algorilm l-we have:
fa(xa+1 + 9 fe(x))) + o(yx+1) g(v(()
| ||0++1 yk+1ll + B yyk+1 y | x
+ Box+1 [22+1 - xf + / 22 11 yk + Ex41 - 0,
(TB.20- (U-B)
and
2k+1 yk+1 + 0, as k 00. 00.
Proof of Lemma B.20. Recall from (LB.2-f) Lemma B.2 that by setting a = #b41 + qu+1, =
yk+1 it asserts that:
f(zx+1 4k+1) - 9
f(x") g(v++1) ((v") + (X", 2x+1 + 9&+1 yk+1) 2 0.
Further, notice that the LHS of the above inequality overlaps with that of (LB.19). This implies that the RHS of 19) has to be non-negative. Hence, have that:
1
B
Aut1
1x11 +
yk+1 + 1k
2,9
2
1
Ahx x²112
| 1=12
2/3
2,3
3
3
+
y yy + yn112
y + 1
2
2
B 9k+1 - yk) -((r++1, yk+t1 -3")
+ Ek + 2ēp+1 (g A3 X ( yk) 3000111111000000 x²)))
Recall that ||*++||| <
2 3
and |q S T (see Lemma B.14 and Lemma B.1 by
Cauchy-Schwarz inequality we have:
1
B
AR+1
\x1l
+
-11-
y + y21l
2/
2
1
A A²112
| 1 2|
28
23
(36)
3
3
+
|| y + y/
y + 121
2
2
+ / ( + VEK) || ykll + / 22 ||
y"1l
+ 28 T (1|A= X + 3 ||000++1 yall + 3 ||00 xx"
Summing over 1: = 0, 0o, we have:
AR+1
Aoll 2 yu+t + y 12)
23
A=
11112 + -/1
PAD
11-30 yo 11
28
(37)
+ /28
((VE*+1 + VEN) |1 3k + VEN+1 11 yy + 3
>e
k=
k=n
00
+ Σ
Tbt1 | - X + well + 3 || - =x
k=
36

---

Published as a conference paper at ICLR 2024
Also notice that by simply reorganizing (36) we have:
AR++1 +
1yy++1 + +y212
2/
2
1 23
A 211112 8 211
211-y: yk + y"1 11 A 2x11 91 yk+t + 1x
$
2
+
2,3
VEx+1 + VEN) 11 - Yill + 28Ex+1 11 - 4"
+ + 2Ek+1 k- Ax X | yall || x 11)
1
8
A 1=1 +
- yv + y1
28
2
ek+1 + vēx) | yvll + v 22 || 9" + V 2
+
+ 2sk+1 + +0++1 (1)
Ap - 1 + 3 | yxll + 3 ||2 x0* I1)
1
3
A 12112 + 2
5 y/1 1
23
+ 2$
Ei+1 + vE,)
11
yill + 223 Σ
/Est1
yl - 30
Y=U
==0
+
9 + 2
Ei+1
1=0
1=0
X + 3 1
yill + | xx" ==11)),
1=0
(38)
where the second inequality follows because the norm is non-negative.
From the above inequality we deduce:
(|AR+1
1 + 3 || y"1) 1) 1)²
48
8
<
|xx+1 - -1
+ 2
1ly+11 - 1
2
8
1o A²1
Yo + 3
2/8
2
(39)
23
Eit1 + Voi) 19++1 well 228
Σ
Ves+i |1
==
+
Σ 1=
8
+
E1+1 +
0i+ (IIA;
X + 3 yill + 3|100411 x²' (1)
1=0
where the first inequality the Using (LB.16-3) and (LB.16-8), we have:
inequality.
[1:11
x11|
|| yd + xi+1 3i-1ll
1
yr B
|| - -Aill
(40)
1
< |1 y"ll + 3
| - X + 3 || X
|141 yill < | x + 1 y"ll
< 1y: y² + || yr + B || X² + + 12. - X²11
(41)
37

---

Published as a conference paper at ICLR 2024
11+41
Yall -
11
y"1l + 113: y
(42)
Plugging these into (39), we obtain:
43 [1++1 - 1 + 3 1yk++1 - 1)
Po - -1=112
+ 2 100 y²1 + V 233
Eitll + v5i) - y/1l - -111: - -y(1)
23
t=0
+ 2/
v Ve+t1 |,:441 y"1l +
E + 2
Eitl
1=0
i=0
1=0
1
+
0:-1
|| x + +B(111 8²1l + +1yi++1 8"1
B |1Ait1 - X"1l
1
|> - -)111) + (196411 - -011 + | 2=1l + 3 3 12: - -x11)
1
+ B
1
k
b
120 - 2²11 + 2 11300 1² +
Σ im
E + > Eit1
23
im0
2/ (Ei+1 + Vo,) + (0t+1)
11:1 - -011 +
30 ||= - 1
i=0
(223(2 /E+11 + VVe) + 230
||31+1 - 8/1l
Σ
20,-1 || X
1=0
k
b.
1
PA - 1²11 + 2/2 |1:00 1²1 + Σ
Es + Σ
Eit1
23
i=0
i=0
+ 233VET + 301) 11:0 y"1l ||
+ 300
11 A²1
+
(V233 (Vett)+ VE,) + B08+1) 11:: - y"
(V23(2VEi / + vE + 280,) 11y:- - v"ll
A+1
Σ 30141 1|, x111+ +
Σ
20, ||:; 11
i=1
1
12 1²11 2 + +,2 11 1² + (v2.3 + (01) 11:0 - 8²1l + 30 11:0 - >² + Σ
k+1
$ 23
6
1+1
(V 2.3 (Ve++1 + 3 + ve,-1) + 3(20; + 0141) 11y, - y
+
Σ 1=1
(20, + 301+1) - 11
1
12 24112 + 8 11 1² + (V23VEi+ S01) 11 - 3¹1l + 301 11:0 - 2² +
k+1
< 299
> E
1+1 1
(V V/3 (VEN- +iri++3/e +3VE+ VEs-1) + (20, + 301+1)) - y*1 + +112 2²11),
38

---

Published as a conference paper at ICLR 2024
From which we deduce:
(1Ax+1 - x + 3 |1 - y" 1²
$21 2=11 + 2330 11300 - --111 + +48(V23/51++ + 1180 - y"1l
k+1
+ 1230, 1|2p - 1 + +12 _e E2
1+1
+ 43
| + +3/5++ + +vi-)) + +20; + (3 llvi - y"1l 11, - 111)).
Now we set in _ Bly - y*1 + | |1 A ف 43 / / //VEEETT++ + +3EEi+ + V + (20x +
30,+1)) and Sk+1 - 2 A 2² + 2 1130 y 1| + 43( 43(V28V55 + B01) 1180 y*1l +
1280, |1:0 X + 12,3 Σ E3 and Lemma B.12 to get:
++1
118 k+1
2
1/2
01+1 S
Xi+ +
Sk+1
A1
(43)
2 1=1
2
Aut1
where we the RHS of (43) to be At+1-
Note that when Σe (or + VEi) t00, we have A" & lim A& < +00, and
k
Ilye- y"1l S 1 A",
(44)
3
| 1" s A".
(45)
Using Eq. (37) we could further get:
[ - x!1l S 3 n "
(46)
Combining (40).(41) and (42) with (37) and using the above inequalities, we have:
Ax+1 - Aul1 + 3 2
yk+1 + 1xll
1
2
k=0
Ao - 1²12 + 2/1 11 + 10
28
2
2 ((V + VEK)
1
80
+ V 2B
A" + Vekti g 44)
+ >e
Ek
k=0
k=0
3
+
Th+1 (A" + 3 Ar + 3
3/ AM
3
k=
2
80
< 29
Ao - X 1212 + 2
- + 111 + 5/
A"
V +
E/ + 8.4"
Σ
ok
(47)
k=1
k=1
from which we can see that AR41 d + 0 and yk++1 Recall that:
y/& - 0.
A++1 d = 3(xx+1 - 1b+1),
from which we deduce #4411 yk+1 - O.
39

---

Published as a conference paper at ICLR 2024
Using the convexity of f+) and g(-) for the LHS of Theorem B.20 we have:
LHS /x (+++1 + 4 [u(()) + g(yk-1) - g(y(k)
- (V [+++1 + qk+1), 2x+1 x + (V 9k+1 3/) + Ek+1
Using (LB.17-2) with x = 2 y = y we have:
IHS v 1k+1, U o + V
> + 18/-yk+1 + yh: 0k+1 ax²)
=0, due (LB.3-9)
-( x
(rr++l: yk+1
vic + Ek+1
Hence, it follows that:
f + 9k+1) fx(x²)) +99(+11 g(y(")
(M4+1,0444 yk-1) + 3( Yk+1 + yk: 2K- x/))
B(gu+1, - xx/²) - (( Uk+1 - 4kr + Ek+1
< Ax+1ll || - yk++1l + B 1 - ykll | - x+
+ fo ||0k-1 - == + 22 |1 vi'l Ex+1
where the last inequality follows from "auchy-Schwand Recall that C is compact and D is the diameter of C:
D A sup
|| - yl a.yEC
Combining with (42), we have:
1 1 vfll = 11 n01l + 1| Detall S 1r D:
(48)
3
which implies that 18 y are bounded for all Similarly, using (40), we deduce:
[0++1 wf = | - x1I + || x
S A" + D,
(49)
3
which implies that #x+1 x is also bounded. Note that when Eee (o, + VE,) < +00, we have lim lim 0. Thus, we have (TB.20-f:-UB)
k0000
Lemma B.21. Assume that F is L-Liscchitz For the Bs+1, Uktl, and A4+1 iterates of the ACVI- Algorithm 3-we have:
1
3 11-y + yx:12
A
Axl12
+
2/3
2
1
8 11--y
Ax
Ax-1112 +2-+ yy + yk-1
2/3
t0s - -yk-il + +(23 + L) ||yx+11 yall
(ox+1
+ 2+ I.
To +1) 1 A
| Ax
3
+ /23( + V |1 Bkll + + Ex+1.
(LBB.21)
Proof of Lemma B.21. (LB.17-2) gives:
(Vfx-1(21;) + qk), Ft x)) + ( (. y) y)
= =- yk x + y) + 3 y 9k Lt x) - -B(gk. 26 x) - -B(rk. yr - -
(50)
40

---

Published as a conference paper at ICLR 2024
Letting (z, y. A) = (zt,, Bk, Ax) in (LB.17-2) and (x. y. A) (xk+1: Pi++1, Ab+1) in (50), and adding them together, and using (L.3...3). we have
(V (Ix+1 + (k+1) V fk= (a+ qt.) #k++1 F4.) + (V cat1 (yk+1) Veng (yJk) yk++ yks)
(Ae+1 Xx. xx+1 yk+1 3 + yk) + B yk+1 + yk (- yr: + y # ..a)
31 qb, 0b41 - o1.) - 3 Tk yl++1 yn)
1
3 (A6+1 mk. Ak+1 21- (Ax xk-1))
+ (-9x+1 + yu + (y): - yk- 1), Ac+1 - Au + +yy++1 (AE Ak-1 + Byn))
31qx+1 IN xb+ mn) B(rx+1 The Uk+1 yk)
(51)
[| AR-111 | 1x11 | Av- -AAu -x--1)111]
2B
8
[I] yk + yk 1 112 || yk+1 + 1x11 - 11 Uk+11 Yk (- yk + 1
2
1-t++1 + yk (-yi y) yk- 1) Ak+1 2x- (Ax- -Aa-1))
3/g++1 9k. +b+1 22)) - B(rk+1 -kk, yk+11 - -yh)
1
(I
2 2 Ax++1 - >x + (11 (11-yk + - 11 - 1-y++1 + ykll 1x)
28
2
1
2/= (A:: d -/ -11-y++1
|A
4k+1 + yı: (-- 1k11))12
23
+
(- + yh (-yk + yk- 1), , Ax= - (Ax - -x=-1)>
3(gx+1 q xk+1 σb) B(rx+1 Tk, y yk)
1
8 (1) (1- + ys- 11 || yk++ + yyxl13))
(IIAR 16-1112 |x As 12) +
23
3(0k+1 ox) ||0 æx + / 2/ (ex + VEk+1) |1 yx
(52)
Using the monotonicity of fK and fk-1, deduce:
( fk (I*+1 + qk+1) 2h + qk (Ix+1 + gx+1)) + fü (xx+1 + gk+1) S fu (xx + qu)
( fk-1 (ax + qb) #h+1 + Q - (ax + qk)) + fk-1 (xxx + (b) S SA-1 (#0+4 + (c+1).
Adding together the above two inequalites and rearranging the terms, we have: (& Sn (#8+1 9k+1) 5/-1 (ar* + q 2x + Qk (#x+1 (x+1))
+ fu (#R+1 + 9x+1) fa-1 (00+1 + qx+1) + fa-1 (Ix + qu) fx (xxx + qu) S S0
which gives:
fa (Ik+1 + 9k+1) fk (xx + qk) 1 IKb)
2 (V (#K+1 + 1k+1) - V Sk-1 (xt + q1),g) (
+ Sa (#++1 + 11+1) SK-1 (I841 + (141) fk-1 (I + qu) - Ss (xxx + 4b)
= f (IK+1 + 9k+1) - À fx (x) + q1), 9s - qu+1))
+ (F(x*+11 F( Ik+1 96+1 24 91.)
2( A - 8(xx+11 - yk) 3qk+1 - (->x-1 - B(xx yk yk-1) -Bqx). 9k 9x+1)
+ (F(#*++1 +1 F(xx)), 31+11 gk+1 Ft qu)
2(A=11 do - -8(0x+1 - yb) + 3(xx - yk-1), qk gk+1)
+ (F(xx++1) -F((*), 2k+1 9k+1 Et ql.)
2 - --k0tt1- + xx) (1|A-11 - A 3xx++1 - yk) + 3(xs -k- [[ F(xx))))
(53)
where the second inequality uses (noisy- V fe), the penultimate inequality uses the nonnegativity of
(qu 9s+1.9. 9.+1), and the last inequality follows from the monotonicity of F, the Cauchy- Schwarz inequality and the fact that ||q=|| S oz.
41

---

Published as a conference paper at ICLR 2024
Note that by (LB.16-3) we have:
Ap-1 A 3(x2+1 yk) + B(xx yk- 1)
-B(x - (Ix+1 - -yk) + (æt yk--1))
=3(2yk xk++1 9k-1)
=3((Br yk-1) 1) (yk+1 - yv)) - (xxx+1 - yk+1))
=3((gk -YN-1) (yR+1 yv)) -AA++1 Au).
(54)
Yk + yk Ty. (Ac+1-AAA)) A4) + Yr + 1 g (2x -x-1))
Tk+1 24 2k+1 Mk+1 + Wk+1
(55)
Using (53), (55) and the L-smoothness property of F, we get:
(V (xX-1 + 9x+11 fa- (zgg + qR) Ik+1 xx)) (aR+1 ok) (B) 1lys yk- || + 3 |1y yk 1l + || Ax I. 2x 27 ll)
(oR+1 + -xx) B 1,yx yk- || + (B + L) |1 yx
+ [ 1 | ARll
1| S1-1ll). I _
Combining the above inequality with (34) and (52), and using (44) and (46), follows that:
2/ ARt1 Aol1
+ 2 111-1 yk+1 + y1
8
AA - -
2
111- + yx-1ll + B + ox) || xx
23
+ /28(VEK + VEk+T) 11 - yx
B113k - 34-1ll + (B L) 1 wxll + (1 1 | Au
+ (oh+1 + +ox)
L
ae Ax-1ll
B
+ Ek + Ek+1
5
AA - A6-111
1 - + 11=2112
23
1. 811 - Bk w + (2g + L) |1 - ydll+ + 2+ (2+ 3)) | - Axl
+ (0x+1 + txx
+11 1Ax - -Aa-1l)
+ 123( + Vex+i) | yull + + 8641
42

---

Published as a conference paper at ICLR 2024
Lemma B.22. If -lim vR
Ex=r
k(Ox VEK) too, then have:
+ Vēk < +00,
(56)
k=1
kep < to0.
(57)
k=1
1
ØK + VEk 5
(58)
VK
Proof. Te _ +imm-++00 VK E k( + EEk) If flmm-++oe TK < +00, then by Cauchy's
1 K+1
convergence test, Vp E N., Tk+p
Tk - 0, K + to0.
Note that
K+p+1
K+1
TK+p TK
1
Σ
klo + Vek)
1
1
Σ
k(o VER)
VK +P
/K +p
VK
k=K-2
K+p+1
K+1
1
p
k(o + Vok)
k(a + VEL).
VK
+
VK + "K+pVK
(VK + p VK)
k=K-2
k=1
where the second term
P
k(o + Vēk)
VK+ +K+
(59)
K+1
k(o VEk) + 0, K + +00,
K
k=1
Thus for any E N4. we have
K K+p+l
Σ K+2
k(o + VEK) 0 K +00.
(60)
K
K
From which we deduce that for any E N
K ++++1
K+p+1
K +p
K+2
Σ (a+
VER v
Σ (o+
K+2
VK
K+2
K+2
(61)
K+p+1
K +
1
k(a + VEk) +0, AK + 400.
K +
VK
+
K+2
Again by Cauchy's convergence test, we have
00
Σ σk o + VEK < V= +00,
which is (56).
Note that limg Tx To + E Tk+1 Th. And
T - === 0 (VK(as + vEE)) 2 O(kex)
Thus by the comparison test, we have
x kEy < +00,
km1
43

---

Published as a conference paper at ICLR 2024
ok + VEk S
which gives (57), (58).
Lemma B.23. Assume that F is monotone on C=, and lim VR
1
Eket klox + VER) < +00,
then for the inexact ACVI Alg. 1, we have:
fK (0K+1 + qK-1) + 9 (yK+1) fK (akk) - 9 (3)k)
$ | 4A+ 3D)
E
(3A" + 3D)Jk+1 + 2B3
Al
B 1BD D)
VEN+I Ex+111
BVK K
(LB.23-1)
E
and
| - yk+1 $
(LB.23-2)
3VK
where AP is defined in Theorem B.20.
Proof of Lemma B.23. First, we define: A 2 31100 1²112 + 31 yo - Summing (36) over ls = 0,1,.... K, we have:
2 AR+1
Aall² + 1-yyk+ yk+1 + yk y2ll2)
8 - yo + y"1 1²122
23
2
22 Ve++l
Vek) |1:44
ys
V /2 |1 - -
K 2
+
Σ
Ek 2
Sk-1 +
Oh+1
(1 1 + ||02+1 - 2ell + B || - x=
k=
k=0
k=0
B
AAo 2²122+
yo + 11
+
11
y"11
23
2
2
2
Σ
A"
(
Ekt1l + VEx) +
Σ
A" Vek+I
3
3
k=
h=
K
K
K
+ Σ
Ek
+
2
Sk-1 + Σ 0k+1
A 3
4
A"
+ 3-
3
A"
3
3
k=0
k=0
k=0
12 V
K+1
K+1
K+1
A
A"
VER
+ 8A"
Σ
+
Ek
662)
8
k=1
k=1
where the penultimate inequality follows from (41), (44), (45) and (46), and A" is defined in Theo- rem B.20.
Recall that Lemma B.21 gives:
A441
A
+
Vk+1 11l
28
2
<
AA - Ax-1 1
1-1-
8k + 11=
2/
2
B11y yk w + (28 + L) |1++1 will+ (2+ L
+ (ah+1 + ox)
2+ (2+ 3)
| Axll
+1) 1 -
+ 2223 + VEx+1) 1 Bull + tek + Ext1.
44

---

Published as a conference paper at ICLR 2024
Let:
Bl - yk- + (2. + L) |18+11 - yoll + 2 22+²) 5 | Akl
uk+1 (on+1 + ox)
+ (1)1) 1> Sc-1l1)
(6)
+ 23 + (ek+1) 1 - y: + ex + Ex+1
Then the above inequality could be rewritten
1
9
A
1x112
+ 11 yk+1 + yx11
28
2
1
3
Ax
21-1
+
yk + - 11| + 5x+1
2/
2
which gives:
1
3 Ax+1 Ax
1-1111100 1-y+++1 111-yx+1 yxl1
2/
1
B -1-yy yk yk-1 11 + Σ 6,41
A
12-
(63)
2/
Combining (63) with (62), we obtain:
3 Axl12
K
Ak+1
2 11-- + uxll²)
233
K
K-1 K
Ak+1
Axll2 + - 11 yk+1 + yxll?
Σ
6j+1
2
1=0
1=0
j=k+1
K+1
K+1
K+1
K
2
<A" " + 5/
A
Σ
VEk + 8A
Σ
σ, +
Σ
Ek
+
kōx+1
(64)
3
k=1
k=1
k=
k=1
We define:
ak+1 2 (ox+1 +ox) (1+
(a)
L. 2+
2 (VEE+1 + VEx),
bu+1 A (ox+1 + t0k)
+ V B
(b)
3
1441 A ||x++1 >xll + 3 Bl1 -vlll
(x))
Note that:
1
8K+1 Sek+ E6+1 + (0h41 + ow)
(1
(1|A A6+1 + 11 92--1l))
3
1/6
+ (ou+1 + ox) (2+
L
2 (VER+1 + VEN)
+ V
(1AR+1 A&ll + 3 11
3k 3x1))
bz+1
45

---

Published as a conference paper at ICLR 2024
from which we deduce that:
K
kōg+1
(ka++1 u/ (k: 1)bx+1
Σ k(Ex + Ex+1)
(65)
K+1
K+1
(ax+1 + bb)kuf +2
Σ kē
(66)
kml
K+1
1+ I.
2+ I.
Σ
(co+1 + ok)
+ (0k-1
ox)
+ V g(VER-1 + vEx)) kudy B
3
6h
K+1
+ 2 kε
(67)
where we define
L 3) (1+))
I+
+ (Ox-1 (2 1) = v ([VVE +Ve))+
c - ((ok+1 + ow)
(c)
3
Note that by Cauchy-Sehwarz inequality, we have:
K
u
([|A+11 - ARll + B B1111+111 - yxl1)²
43
433
K
< 23
(1Ax++ 1 + 11 yK++ + yx 112)
Combining this inequality with (64), (67), and letting:
K+1
K+1
K+1
B
A A
+
5
VeL + 8
0i +
Ck.
(B)
#=
1=1
1=1
gives:
K+1
K+1
48 S
48
2
Ba+1 +
ke
kccuk
K
Using Lemma B.12, we obtain:
K+1
K+1
u/+1 I
1
23
Σ
kcp +
48
B++1 + 2
Σ
KER
+
23
VK
VK
K
K+1
kck
k=1
k=
F4
(68)
Using the assumption that limg-++oc VK EKET k(ox + /EX) < +oo and (56) in Lamma B.22, we have B8+1 is bounded; using (57), we know that Ex+1 in the RHS of (68) is bounded.
1
K+1
Let E lom Eg, then by (68) we have
E
B B|ooK-1 4K+1|l = ||AK11 - AK| 5
(69)
VK
EP
|1-yK+1 + yK S
(70)
BVK
On the other hand, (44), (45) and (46) gives:
3
||
[
x
+ |0
x S
A" + +D,
1
yy
- yo
1ik
y
+
< AAA +D,
3
|| |
|
X"
+
||
A
+ |*1
46

---

Published as a conference paper at ICLR 2024
Plugging these into (TB.20-ft-UB) yields (LB.23-1).
B.2.3 ANALOGOUS INTERMEDIATE RESULTS FOR THE EXTENDED LOG BARRIER
Recall from $ 3.2 that we defined the following barrier functions,
Si (z, 14) - -- log(
(()1)
(2) A - 4 log( -z), ue न + μs + C; otherwise
2 =
(522)
where e in (f22) is fixed constant. For convenience, we also define herein:
m
(v)
Σ 22 (p(())y))
(g(t)
In the previous subsections, we focused on the standard barrier function used for IP methods ((1)). In this subsection, we first show that when we use barrier map (522 in Alg. 1, where constant in
(p2) is properly chosen, y the solution to the minimization problem in line 9 of Alg. 1 is the same when we standard barrier map (p1). Thus, all the above results hold if substitute g())
by g(t).
Proposition B.24 (Equivalent solutions of the y-subproblems with øi and with p2). For any fixed E t0....,T . 1} and k E {o..... K - 13. let T - miny 2==1, 62 (f;; me) +
8 2 y k+1
(t) }/21 (0) , ming (T)), and ch v1( (1) + t. Further, define:
v((v) - Σ क (p)))) + 2
y - x xk- B
(1)
(1))
and
(v) & Σ (v)
8
1 2000
(3)
+
y xk-1
where we let
cg in (p2). Then, holds that:
(8) Met1 argmin 3t (y) = argmin vi (2: c
(71)
y
Proof of Prop. B.24: Equivalent solutions of the y y-subproblems with pi and with p2. When c c in (52), Vy R", if E [m], s.t. p:(y) -t// then we have
(2(2) > ck = (1 +
(72)
Note that
p2(2, < 9e (x,, mt), Va,
(73)
thus, we have:
S < Vy'.
(74)
((t) Let Us41 argmin (1))). If 2 minigigm (Ti). then (72) and (74) give:
8 (a(y) Σ (2(p)
m
+22 y ( 1 1
v (0)
( (0(2))
(75)
which indicates ((1 9k--1 the minimum of यt (v( Note that / (-) =+) on S. Therefore, _ yk+1
(1) ) must be in the set S و {ω)p(x) S -e- -t/eee)
(1)
47

---

Published as a conference paper at ICLR 2024
The next Proposition shows the smoothness of the objective in line 9 of Alg. 1 when the extended log barrier term ($2).
Proposition B.25 (Smoothness (g2)). Suppose for all E [m]] we have [ S
L Ms Vy E IR", and Pi is Li-smooth in R", then +t(+) is de -smoothh, where F. EnS (meslllu Lss + 20 / Mc) + B.
Proof of Prop. B.25: Smoothness of (p2)). Note that for any 2, E I and μ O, have 0 1 (2 11) I pe and 0 S (z) I 2e2o/1. Thus, we have:
|| o (v) - (x)()
= (1))(((((0))))))))) ((0 VF((=)) + (s2(( (2((A(()), SuE ( V))(())] Millo - (2(2(()),
= (V).
I ( we2c/MM) M.) b1 æ|1| VE, E R
from which we can easily see that the proposition is true. Remark B.26. We note the following remarks regarding the above result.
(i) When t is large, 7, defined in Prop. B.24 or is very close O. Therefore, in order to let T satisfy t - minggim (Tr). it suffices to set it to a small positive number.
(i) (vv (9) is bounded and thus & is bounded. Suppose of is upper bounded by ct, i.e., de et, Vk, t. Then Vt {0, ...,... T 1}. (+)) is -mmoothh and B-strongly convex and the subproblem in line could be solved by commonly used first-order methods such as gradient descent a linear rate.
(iii) Alternatively, instead of updating cf for each k; as it is suggested in line of Alg. 1, for any could fix of be vi (y') + where y is arbitrary interior point of Cg: Appendix C for detailed implementation.
B.2.4 PROVING THEOREM 3.2
We are now ready to prove Theorem 3.2. Here we give nonasymptotic convergence rate of Algo- rithm 1.
Theorem B.27 (Restatement of Theorem 3.2). Given continuous operator F: X - R", assume
that:
(i) F is monotone on C_, as per Def. 2.1;
(ii) F is L-Lipschitz on X;
(iil) F either strictly monotone C or one of is is strictly convex.
(1) (1) (1)
For any fixed K N_, let (x K YK A denote the last iterate of Algorithm 1. Let & be P1 D2 with c = of (see Prop. B.24 for the definition of ct)). Run with sufficiently small p-1. Further, suppose:
K k(ox + VEN) < t00.
lim R K
K
k=1
We define:
2 43(1
A A
(Veii+ +3ve Ve-1)) + (20; + +30+4)),
48

---

Published as a conference paper at ICLR 2024
1 2 - 1-1 + 2 13o yy'l +333 + +8,1) 1110
k+1
+ +12001 1200 x1 + 12,3
1/2
A _ 1 k+1
1
k+1
$ Xx+ +
Si+1 +
2 1=1
and
_ lim A < +00.
k---00
We define
cx a ((okt1 +ow
(1+
L 3
+ (ax-1 +ox) (2+ L
+ V + veE))
B)
A -
11 + y'112
2 K-1
K+1
K+1
Bi+
a 5 V
A
Σ
VEk + 8A
Σ ai +3
Σ
Ek
1=1
K+1
K+1
233 VK
233
Ek41
kcp +
48
Bi+1 +2 2
Σ
ksk +
K
Σ k=
kck
1=1
k=
and
E= lim Eg k-200
Then, we have:
E
(( + +11
+ (4A +4
3D + M)0++1
BVK
+ 228
2A
+D)
VERTI+EAH
3
1
0
Vk
and
2E
| - -BK+1I -
3VK
where A 2 11100 - 1² + 3 - 12 and D 2 sup ||0 - yll. and M &
sup [F())] #EC
2.EEC
Proof of Theorem B.27. Note that
(Se-Pr-2) + min (I)+
aEC
+ max (1( 26.11 xx) sec
+ C(
49

---

Published as a conference paper at ICLR 2024
from which we deduce
2x+1 g(xx+1, C) = (x+1 -xt) vk.
(76)
For any K E N, by (Chu, 1998) we know that:
x²x + K
g +1) g - 0.
A" 1 =1Ao0 >011 Bly0 -y11²= =A,
(77)
A + A,
(78)
E" E.
(79)
Thus, there exists n-1 > 0, s.t.V0 < μ < p-11
E
| x*>l 5
BVK
E
l BVK
Combining with Lemma B.23, we have that: (F(* 1), ØK+1 - a*k))
-(F(IK+1), 9k+1 x²k) (
=fk (0K+I + qK+1) fK (ak)) (((
Eu
(11A"1| + 4A +3D)
+3AA + +3D)ou+1
BvK
A#
+ 2B
3 +D)
V +k+11
+ |||k-1|||F[((XH||
+ +g g (yK+1)
E
$ (||Aa|| + 4.4h +3D +
+ (3A" + 3D + M)OR+1
3VK
AH
+ 2B
D
VER+i + 58411
3
Using the above inequality, we have
C(IK+1,C) = =FF(ax+1), Øk+1 -xk)
= =F((#K+)), (,, ØK+1 -x*k) + (F(#x+1), -xk)
< {F ØK+1 - -xx) + [[(
E"
I (||a + 4A + 1.D+1++ M)
+ (3A" + +BD+ + M)x++1
BVK
+ /23
A"
+ +D)
V + Ex41
B
Moreover, by (77), we can choose small enough μ-1 so that
5A+ ( 5 3D M)
+ (4A+ 3D + M)0x+1
(80)
BVK
+ 228
2A 3
+D)
VEK+1 t6+11.
(81)
and
2E
9k+1 <
(82)
3vK
where (82) uses (LB.23-2) in Lemma B.23. By (64), (80), (82) and Prop. B.24, we draw the conclu- sion.
50

---

Published as a conference paper at ICLR 2024
B.3 DISCUSSION ON THEOREMS 3.1 AND 3.2 AND PRACTICAL IMPLICATIONS
We adopt the same way of stating our theorems 3.1 and 3.2 as in the main part of (Yang et al., 2023) (see remark therein) for clarity, easier comparison with one-loop algorithms, and because these are without loss of generality provided that K, T are selected appropriately, as Yang et al. (2023) showed. In particular, we require knowing a sufficiently small μ which depends on the selected K. Note that we cannot prove a faster rate than ((1/VK) for the inner loop for our algorithm; so even if we further adjust 1,11, the rate would still be ((1/VK) Given the statements in our paper, the same convergence rate of O J ) is implied for cases when we do not know sufficiently small p-11 by the argument App. B.4 of (Yang et al., 2023). For completeness, herein, we focus on clarifying why this is the case.
Remark B.28. Notice that only when we require a sufficiently small μ-1 (as we do in our statements) can we use any T, K N+. For versions of the theorems that do not require sufficiently small 1111, K, T must be appropriately selected.
We obtain explicitly how μ-11 depends on the given K by re-writing an equivalent re-formulation of
App. B.4 in (Yang al., 2023, Remark 5). In partieular, for any fixed μu11 0, K N_ and any
T 2 Oloo K), for Algorithms and 3 we have G( (T) C) = 0(1
As example, since μd-1 could be an arbitrary positive number, without loss of generality, we could let μ-- = 1; then the above implies that when μr = 066 ), we have g (2) C) = OLIV/K). This implies that for our Theorems 3.1 and 3.2, setting μ = 0(8108 K) is enough.
Interpretation. Here, we provide an intuitive explanation for the above statement. For any T E N. the inner loop of ACVI is solving (KKT-2), where μ = μr.. Note that (KKT-2) is a modified problem of the original VI problem, approaching the original problem when μ - O. Thus, when 4-1 is large, larger T is needed in order to let (KKT-2) be a good enough approximation of the original problem.
Practical implications. Suppose you need c-accurate solution. Then K is selected to satisfy K 2 zi, and then T 2 log(K) 2 log(1/c) Notice that the overall complexity to reach c precision is still ((1/e²) up a log factor.
B.4 ALGORITHMS FOR SOLVING THE SUBPROBLEMS IN ALG. 1
As in (Schmidt et al., 2011), Theorem 3.2 provides sufficient conditions on the errors so that the order of the rate is maintained. In other words, one think of running a single step of gradient- based method for the sub-problems. Thus, the inner loop has a complexity of the order of one (or constant number of) gradient computations. Below, we discuss the algorithms that satisfy the assumptions of Theorem 3.2 so as the shown convergence rate holds.
Choosing the As method. Let G(x) A x (pF((=) Parl" !.P. - d then from the proof Thm. 1 in Yang al. (2023) know that G strongly monotone C_. Moreover, when F is L-Lipschitz continuous, G is also Lipschitz continuous. Many common VI methods have a linear rate on the æ subproblem, thus satisfying the condition we give (Tseng, 1995; Gidel et al., 2019a; Mokhtari et al., 2019). Hence, for A.. we could use the first-order methods for VIs listed in App. A.5 to find the unique solution of the VI problem defined by the tuple (C=, G), at linear convergence rate. To solve VI defined by (C_, G), we need to compute the projection II. which is straightforward by noticing that IIc_ (x) = P.x + de, Va.
Choosing the Ay method. If using & to be P1. the objective of the y subproblem is strongly convex but non-smooth. Thus, to our knowledge, there is no known method achieve a linear rate for general constraints without additional assumptions. However, one could satisfy the condition we give by using methods for A, to exploit the constraint structure further. For example, if the constraints linear, it is straightforward to derive the update rule for the y subproblem, which satisfies the conditions of the theorem.
On the other hand, discussed in Remark B.26, when choosing ş to be p2, the objective of the subproblem in line 9 of Alg. 1 is smooth and strongly convex and thus could be solved by commonly used unconstrained first-order solvers such gradient descent at linear rate.
51

---

Published as a conference paper at ICLR 2024
Discussion.
The above facts allude to the advantages of ACVI, the sub-problems are "casier" than the original problem. To summarize, (i) if F is monotone, the a subproblem is strongly monotone; and (ii) the y subproblem is regular minimization which is significantly less challenging to solve in practice, and also is strongly convex.
52

---

Published as a conference paper at ICLR 2024
B.5 PROOF OF THEOREM 4.1: CONVERGENCE OF P-ACVI
B.5.1 SETTING AND NOTATIONS
We define the following maps from IR" to R":
[(x) F( + 1(C d),
(fx)
fx e F( 1(Cx dd.
and
(f)
g(y) _ ((p(()) 0))
(g)
where x* is solution of (KKT), Let y" = x². Then (a", y²) is an optimal solution of (f-Pr). Let us denote with (xj, g 2 the KKT point of (fi-Pr). Note that in this case, the problem (fi-Pr) is equivalent to (fx-Pr-)).
B.5.2 INTERMEDIATE RESULTS
In P-ACVI-Algorithm 2, by definition of y (line Algorithm 2), y and y² we immedi- ately know that
g(yx+1) g g 0.
(83)
The intermediate results for the proofs of Theorem 3.1 still hold in this case only with a little mod- ification, and the proofs of them very close to the previous ones. To avoid redundancy, we omit these proofs.
Proposition B.29 (Relation between f& and f). If F is monotone, then wk E N. we have that:
fa( fx(x=)) 2 f(xx+1) f(xx).
Lemma B.30. For all x and y. we have
x - y) 2 0, f(x) + +(v) - f(x=*) - ) + (X*,
(LB.30-f)
and:
fx(2) g(v) fie(xt) ((vi) (Ni v) 0.
(LB.30-fik)
The following lemma lists some simple but useful facts that we will use in the following proofs. Lemma B.31. For the problems (f-Pr), (fi-Pr) and Algorithm 2, we have
0 E (fx( A+ + (( ys)
(LB.31-1)
0 E 0g(Ux+1)
2 3(x D2+1),
(LB.31-2)
A
A 8(xx+1 -)++1),
(LB.31-3)
X E 0f(x));
(LB.31-4)
X E (fx()t)
(LB.31-5)
X E Oglv"), \ E Oglvit) x² y",
(LB.31-6)
(LB.3317)
(LB.31-8)
x yi
(LB.31-9)
Like in A.p.B.1.2, we also define (x and V9(2641) by (V and (V9). resp.
Then, from (LB.31-1) and (LB.31-2) follows that:
(m)+)) (m)(())1) and Vo(wk+1) 0g(yx+1)-
(84)
53

---

Published as a conference paper at ICLR 2024
Lemma B.32. For the iterates #c+1, yk+1, and Ak+1 the AACVV-Alloorthhn 2-we
we have:
(Vg(yx+1), yk+1 y) (1 y yk+1),
(85)
and
(V[r( 2) + (Vg(ve+1). 96+1 - 4) -AR+1, F4-11 4k+1 a + y)
(86)
+ + Vk+1 yk, Ex++ x).
Lemma B.33. For the 11+1 1 and A iterates of the PLACVI-Algrii 2-we
we have:
(V
(ax+1)
2x+1
x²) + (Vg()++1) yk+1 - y²) + (X* Lk+1 - yk+1)
1
1
1 11y* yk 112
B 11y* yk+t1l
$
A
x+1
23 A6+1 112
2/
2
2
1
1x+11
A=112
1ly: yс+ill 11
233
and
(2
fa
0641 x7,) + (Vg(vk+1) yk+1 - vi) + -Xx, xx+1 - yk+1)
B
$
1
-xtl12
|x+1 - 111 +
11
yxll2
2 1l yk+1ll?
2
233
2
B
|
Ax112
11yx yx+1l12
2/3
Lemma B.34. For the 2k+1 yk+1I and A iterates of the P-ACVI 2 we have: f(xx+1) + ((1)+1) f(x") g(y") + (X*, 1k+11 k
< (2x++1) + ((
[s((x²) - -(10")))) + (A*, 2x yR+1)
1
x-
| 1 -1-
23
28
B
+
-1- + +
Yk+t + y
2
8
Ax+1
Abl12
1-y++1 + 1
(LB.34)
233
2
The following theorem upper bounds the analogous quantity but for f'((-) (instead of Л) and further asserts that the difference between the #3+1 and yk++1 iterates of P-ACVI (Algorithm 2) tends asymptotically.
Theorem B.35 (Asymptotic convergence of (I*+1 94+1) of P-ACVI). For the Fx+1 yk-1- and Ak+1 iterates of the P-ACV7 P-ACVi-Algorithm w-we have:
fx(0x+1) (x || | ye+ill + 3 11 yell ||0+1| w + 0,
(TB.35-fr-UR
and
Øk+1 yk+1 0, as k 00.
Lemma B.36. For the 1k+1, Us and A iterates the P-ACVI P-ACVI-Algorilmm 2-we have:
1
Au+1 - Ax + 3 - -
y + 1x11 2
-111 A Au
1
1x-11
2
3
-
yv + 112 (LB.36)
2,3
2
23
2
54

---

Published as a conference paper at ICLR 2024
Lemma B.37. F is monotone C=, then for Algorithu 2, we have: fK (ØK-1) fK (xk)
-
K
A
(2V
VB |X
V
K+1'
A
(LB.37-1)
A V 33(K+))
and
| yk+1ll S
(LB.37-2)
where 11 112 + 30 yo - y²11²
B.5.3 PROVING THEOREM. 4.1
We are now ready to prove Theorem 4.1. Here we give nonasymptotic convergence rate of P- ACVI-Nlgorithm
Theorem B.38 (Restatement of Theorem 4.1). Given an continuous operator F: X R" assume F is monotone on C=, as per Def. 2.1. Let (IK, yk Ak) denote the last iterate of Algorithm 3. Then AK N4, we have
A K
1 (2VA+
J IX
A
C(zK,C)
(na-If-Rate)
vB
K
and
A
x y*
(87)
3K
where a 211100 2²1 + 31 - 11 and 2
sup
| yll.
and M & sup [F()))
a.yEC
sEC
Proof of Theorem 4.1. Note that
Pr-2 + min (F (in(F(x (x)+1),
sEc
max F (( I14+1 x)
aec
g(*x+1,C),
from which we deduce
C( (F(# 24+1 - x = fK (œx+1) fK (xk) Vk.
(88)
Combining with Lemma B.37, we obtain (na-If-Rate) and (87).
55

---

Published as a conference paper at ICLR 2024
C IMPLEMENTATION DETAILS
In this section, we provide the details on the implementation of the results presented 5 in the main part, well those of the additional results presented in App. D. In addition, provide the source code through the following link: ht https: : httpttttthuuoeoo http:///iiauub.c./////eeeeeeeeee wwt.aaa.cccccccaaaavvooaaaaaa ACV..
C.I IMPLEMENTATION DETAILS FOR THE 2D-BG GAME
Recall that we defined the 2D bilinear game as:
min max 2132 where A - E R 1.45 2.4}.
(2D-BG)
aE a
To avoid confusion in the notation, in the remainder of this section, rename the players in (2D-BG) as and p2:
min max P1P2 where A (p E R 0.4 PIE MEA
In the following, we list the I-ACVI and P-ACVI implementations.
I-CCVL For I-ACVI (Algorithm 1), we use the following Python code and the PyTorch li- brary (Paszke et al., 2017). We learning rate of 0.1. The following implementation uses the standard log-barrier (p11).
0.5, μ 3, K 20, 20, 0.5 and
Listing 1: Implementation of the I-ACVI algorithm (using (p1)) on the 2D constrained bilinear game.
Import torch
learning
beta = 0.5
ACVI beta parameter
ACVI poromater
K 20
ACVT X parameter
1 = 20
I-ACVI parameter
deltt
ACVT delta parameter: exponential decay of
9pl_x
Pa..Paaeette (torchh, (2.0))
10pl_
Serch.nr..araneeee htwpeaetttrtttrh..etom. (torch, (2.01)
11 plp
torch.nr. Pawameter (tarrartttttttrrh..tnomo. (0.01)
12
13 p2 X
torch.nr. nr. Ptrchnte tenao (2.C1)
p2_ Y Darcaann.Paaamete: (torch, Lensor (0.0))
(torch, (2.01)
15 p2
Lorca.nz. Paramete:
17 while ma 0.0001:
18
19
Ior itr range (
20
Ior - range
problem (line algorithm)
lose_pl 1/beta pl_x p2_x 0.5 (pl_x - play h/.ibetal..oo/ 22
pl_x.grad
24
loss_pt hho_pplhockksrdlt
25
with torch.no_grad!). pl_x.grad
26
pl_
27
1ose_p2
plxx p2_x (p2_x p2_y p2_l/beta) .pow
29
p2_x.grad = bone
30
loas_ baa__p2.backwrddl with torch.no_grad111
11
32
pz_x
p2_x.grad
33
34
for
in range (1): solve y problem (line 9 of algorithm)
1 pl_y 0.4 -0.4 pl_y define the inequelity constraiats
36
2hi_2 1.4-p1-- & plly 2.4
37
phi p2_y 0.4
p2_y
38
phi_4 - 2.4 p2_y $ pl_y 2.4
39
log_term mu (. phi_2.1og 1 phi 1o1g phi_4.1og
40
loss log_tern. beta/2 (pi_y plx pi_t/sete) (2) beta/2 x (p2_y - p2_x b/bt/b) (2)
41
play-grad, p2_y.gred Nene, loas.backward
43
zorch.no_grad!))
56

---

Published as a conference paper at ICLR 2024
FLay ply-ggaa
46
p2_y lr p2_y-grad
47
18
update the Lambdaa (line 10 of algerithm) with torch.no_grod(:
49
pl_1 beta (pl_x pi_y)
31
12_l +o beta A (p2_x p2_y)
53
-- delts # decay
For completeness, we provide the source code below when using the (p22 barrier map instead of (p1).
Listing 2: Implementation of the I-ACVI algorithm (using (p2)) on the 2D constrained bilinear game.
Import tozch
1r 0.1
learning
beta = 0.5
ACVI beta parametex
ACVI pazameter
k 20
ACVI X parcmeter
T-ACVT parameter
delta 0.5
aCVI delta parameter: exponential decay of
8 torch. tensor ([1.0])
perameter of the extended barrier
10 10plx - terca.mn. aecia.n..PPae. Paramete: sttorch.teeseeee (2.01)
11 j torch. Farammeeeeeeee tensor (2.0))
p2
torch.nr, Parameter torch.nr.Paramete: (tarch.tenaae (0.01)
13
14 p2_x
Lorca.ne an. Paramete: wwwrrhhteeeeee. (2.0) )
15 p2
terch. nn. Paremeter (torch, tensor (2.0)
16 p2 torch. Parameter (torch. tensor (0.0))
17
while ma 0.0001:
19
20
Ior itr range (
21
22
for in ranga (1): solve x problem (line 8 of algorithm)
lass_pt 1/beta pl_x p2_x 0.5 (pl_x play pl_t/betallco pew (2)
24
pl_x.grad Kone
loas_pi.backwrrdtt with torch.no_grad
26
27
pl_x 1r pl_x.grad
28
29
loss_p2 -1/beta x p2_x 0.5 (p2_x p2_y + hpww
p2_x.grad
31
baa__p2.beckwardf tarch.no_grad
32
33
pz_x Ir p2_x.grad
34
for rang=(1); solve y problem (line of algorithm)
36
phi pl_y + 0.4 $ -0.4 < pi_y define all the inequelity constrainta
phi_2
pl_y
2.4
38
phi_3 p2_y 1 0.4 $ 0.4 p2_y
39
phi_4
p2_y pl 2.4
40
log_terms [phi_l, phi_2, phi_3, phi_4]
41
clap_condition: [-phi -xorch.exp(-//mm) for phi in log_terms]
42
new_log_toms 1omu
if condition clse
43
-muxtorch.exp (o/mu) uphi for
phi, conditien zip tloogLeerme,
coip_oondition
45
loss
beta/2 (pl_y pl_x pi_l/bete) .pow (2) sun (new log___og_termms beta/2 (p2_y p2_x p2_1/betal pow (21
46
47
48
playd p2_y. None, None laas baockbackddddj
50
with torch. no torch.no_graat no_grad())
ply p2_y 1z p2_y-grad
graad
52
53
54
update the lambdas (line 10 of algerithm) with torch.no_grod
55
56
pl_1 beta (p1_x- pl_y)
57
12_1 1- beta x (p2_x p2_y)
59
*m delta dacay
57

---

Published as a conference paper at ICLR 2024
For PI-ACVI, the following Python code implementing Algorithm 2 using the Pytorch library. We set 8 = 0.5, K 20, 20, and use learning rate 0.1.
PI-ACVI
Listing 3: Implementation of the PI-ACVI algorithm on the 2D constrained bilinear game.
import terch
1r 0.1
learning rate
beta 0.5
ACVI beta perameter
20
ACVI parometar
T-ACVT paraamteer
splx
torch. az. Paremetee (torch. tensor (2.0))
opl_y
Lorca.or, Baccc.nr.PPaacee Parameet (Lorch, Censor (2.01)
10 10p1_ terca.nn nz. Paremete: (ttrch..eneeee.. (0.01) )
11
12 p2 X
torch.ne nr. Paramaett (tarra (tarch,tensor tengor (2.C1)
p2_
(torch, torca.nn. Paremete: tensor (0.0))
14 p2
16 loz itr in range (K):
17
18
+ solve problam (line of algorithm)
19 for ir range(1)
loss_pl 1/bela pl_x p2_x (pl_x pl_y ol_1/beta) spow (2)
21
pl_x.grad None
22
loss_pl. loss_pl.backwardl)
23
with toroh.no_grad(??
24
pl_x - 1r pl_x.grad
26
loss_p -1/beta + pl_x p2_x 3.3 1p2_x p2_y + pl_1/beta)
.pow .po.
p2_x.grad
28
loss_ p2_ backwaradd
29
torah.no_grad
30
p2_x Ir p2_x.grad
31
32
problem using projection (1ine of thm)
33
with (orca.no_grad()>=
pl_y.dats pix pl_1/bea
35
pl_y.dats pi..clip(-0.d, 2.4)
36
37
pž_y.data p2_x pi_l/beta
38
p2_y.dato p2_y.clip(-0.4, 2.4)
40
4 update the lambdas (line of algorithm) with scrch.no_grra(()-
42
pl_1 +s heta [pl_x - pl_y)
43
p2_ beta ip2_x p2_9)
C.2 IMPLEMENTATION DETAILS FOR THE HBG GAME
Solution and relative error. The solution (HBG) x 500 e, with e R 1000 As a metric [
of the experiments on this problem, we use the relative error: (xxx)
Experiments of Fig.4.a showing CPU time to reach a fixed relative error. The target relative error is 0.02. We the step size of GDA, EG, and OGDA to 0.3 and use k and a 0.5 for LA-GDA, For I-ACVI, we set 3 = 0.5, p = 10 = 0.8, A = 0, K = 10, = 10 and the step size is 0.05.
Experiments of Fig.4.b showing the number of iterations reach a fixed relative error. Hy- perparameters are the same as for F.a. We vary the rotation "strength" (1 -)), with v E (0, 1).
Experiments of Fig.4.c showing the impact of Ko- For this experiment, we depict, for various required to reach relative error smaller than 10 10-4 We
pairs (Ku, K ), how many iterations set 3 = 0.5, μ le - 6, 8 = 0.8, T = 5000 and 0.05 as learning rate. We experiment with Ko e (5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130) and K,, E {1, 5, 10, 20, 40, 50, 60, 70).
The following Python code snippet shows an implementation of I-ACVI (Algorithm 1) on the (HBG) game:
58

---

Published as a conference paper at ICLR 2024
Listing 4: Implementation of the I-ACVI algorithm the HBG game.
import numpy Import time
.02 target relative error
dim 500
(im(x)) (im dim
ap.ones (2+dim, /dim solution
# T-ACVT parsmetera
beta, mu, della, K, 1, T, 1r 0.5, le 6, -8, 10, 10, 100, 0.05
11 Building HBG matrices
12 =:2 0.05
13 np.concatenate (etaang..denttity (dim), (1-eta) +xp, identity (dim) axis=l)
14 A2 cp.concstenatt [[-(1-1)))) (1-eta) =opta)+pp.. idyntiity etasap, ident ity (dim)), exig=1)
15 np.concatenate (A1,
axia-0)
16
17
projection
Fc
18 Lemp1 up.concatenate (np. oses (1, dim)), up.zeros dim)),, axia=l)
19 temp2 np.concatenate (np. zezes ((1, dim) I, ap.ones dim) )), axis=l)
20 ap.accratenataa ((templ, tamp2), exis=0)
21 d oneonea (12, (12
Lemp np.1inalg. tap.dot (C,
23 temp np. (C.T, temp:
no. (temp, d)
25 Pc (y..iddettyyy2aaee
ap.det (temp,
26
Initialize players
28 init - up, random. (2+dim, 1)
init [:dim]
[ddmm sp.sum (:dim)) ensuring part the simplex
30 init [dim:] init(dim:] sum (init [dim:))
x_x ap.y (init:
32 np.copy (init)
33 x_imd za.zaros (init.chepe)
34
35 finished, cat, LO Falae, 0, Lime.time
37 for in range (T):
38
delta
39 for in (K)
40
ent +=
Solve approximately the problem (line algorithm)
42
for in (1);
g 2_x 1/beta (Pe, sp.det (A,)_x)) ap.dot (Pe, z_y) 1/beta ap. =_1md - do x_x
45
46
If op. hww.iinnn...r..t...ommo (x_xxx__x__pt) tinished True print (f a selative error of (eps) after (ent] iterations in (time. tiime.timeie (1-00:.2E) sec.*)
<= eps:
48
49
break
50
51
Bolve approximately the problem (line of algoritha) for in (a)g
52
assert (x_y ensuring log positive
54
mu 1/2_y betax zx a_md/bbaa) ==
55
56
37
Update lambdas (Line 10 algorithm) Imd beta. (2_x-z_8)
58
59
finished:
61
break
C.3 IMPLEMENTATION DETAILS FOR THE C-GAN GAME
For the experiments the MNIST dataset, the source code of Chavdarova al. (2021) for the baselines, and we build on it to implement PI-ACVI (Algorithm 2). For completeness, we provide overview of the implementation.
Models. We used the DCGAN architectures (Radford et al., 2016), listed in Table 2, and the pa- rameters of the models are initialized using PyTorch default initialization. For experiments this
59

---

Published as a conference paper at ICLR 2024
Generator
Discriminator
Input: Z E R ~ 1)
Input: E R xx2xxx2
transposed conv. (ker; 3x3, 128 -> 512; stride: 1)
conv. (ker: 4x4, -> 64; stride: p)
Batch Normalization
LeakyReLU (negative slope: 0.2)
ReLU
conv. (ker: 4x4, 64 -> 128; stride: 2; pad:1)
transposed conv. (ker: 4x4, 512 - 256, stride: 2)
Batch Normalization
Batch Normalization
LeakyReLU (negative slope: 0.2)
ReLU
conv. (ker: 4x4, 128 -> 256; stride: 2; pad:1)
transposed conv. (ker: 4x 256 128, stride: 2)
Batch Normalization
Batch Normalization
LeakyReLU (negative slope: 0.2)
ReLU
conv. (ker: 3x3, 256 - I; stride: I)
transposed conv. (ker: 4x4, 128 1, stride: 2, pad: 1)
Sigmoid(-)
Tank(-))
Table DCGAN architectures (Radford et al., 2016) used for experiments on MNIST. With "conv." we denote a convolutional layer and "transposed conv" a transposed convolution layer (Radford et al., 2016). We use ker and pad to denote kernel and padding for the (transposed) convolution layers, respectively. With hxw, we denote the kernel size. With Cin + your we denote the number of channels of the input and output, for (transposed) convolution layers. The models use Batch Normalization (loffe & Szegedy, 2015) layers.
dataset, we used the non-saturating GAN loss as proposed in (Goodfellow et al., 2014):
LD E log (D( da-pa
E 5-pp
log (1 D(G()))
(L--D)
LG E log (D(G(E))). Enps
(L-G)
where G(-), D(-) denote the generator and discriminator, resp., and Pa and ps denote the data and the latent distributions (the latter predefined as normal distribution).
Details on the PI-ACVI implementation. When implementing PI-ACVI on MNIST, we set B 0.5, and K 5000, we use 4 20 and by E {100, 500). We consider only inequality constraints (and there are no equality constraints), therefore, the matrices P. and d, are identity and zero, respectively. As inequality constraints, we use 100 randomly generated linear inequalities for the Generator and 100 for the Discriminator.
Projection details. Suppose the linear inequality constraints for the Generator are AO < b, where O E R" is the vector of all parameters of the Generator, A (a....., a aoo0) ) E R R100xn b ) E 1R000 We use the greedy projection algorithm described in (Beck, 2017). A greedy projection algorithm is essentially projected gradient method; it is easy implement in high- dimension problems and has convergence rate of (L)/K)). See Chapter 8.2.3 in (Beck, 2017) for more details. Since the dimension n is very large, at each step of the projection, one could only project 0 to one hyperplane a! x b; for some i I(0), where
I(0) A (j {jaa > b
For every j E (1,2,.... 100), let
S₁ 2 ( < bz}.
The greedy projection method chooses so that i E arg max ( (dis((O,S)))) 8:)}. Note that long 0 is not in the constraint set Cs = {m| Aa: I b), i would be I(0). Algorithm gives the details of the greedy projection method we use for the baseline, written for the Generator only for simplicity; the same projection method is used for the Discriminator as well.
Metrics. We describe the metrics for the MNIST experiments. We use the two standard GAN metrics, Inception Score (IS, Salimans et al., 2016) and Fréchet Inception Distance (FID, Heusel et al., 2017). Both FID and IS rely a pre-trained classifier and take finite set of m samples from the generator to compute these. Since MNIST has greyscale images, we used a classifier trained on this dataset and used m 5000.
60

---

Published as a conference paper at ICLR 2024
Algorithm 4 Greedy projection method for the baseline.
1: Input: IR", A = [a] (00))"
E 1000m. b (b,,..., 100)) E 100
E >
0
2: while True do
3: I(0) [ila] 0 > b,}
0-
4: if [())
then
j (EI
|ayl
5: break
6: end if
a 0-yl
7: choose: E arg max
e,
jEI(O)
8: 0 0
|a.1
9: end while
10: Return: 0
Metries: IS. Given sample from the generator B. ~ Pg-wheree Pa denotes the data distribution of the generator-15 IS uses the softmax output of the pre-trained network p(z](;)) which represents the probability that & is of class C;, E 1... C, i.e. ,f) E [0, _1 It then computes the marginal class distribution p(ğ) between the predicted conditional label distribution p(ÿ]ūg) and the marginal class distribution p(ğ). More precisely, it is computed as follows:
J p ( (mg). IS measures the Kullback-Leibler divergence IDx
(e.) log p(Boo(..) (IS) p(ye)
IS(G) exp
E Pp
(p())
= exp
It aims at estimating (i) if the samples look realistic i.e., p()( should have low entropy, and (ii) if the samples are diverse (from different ImageNet classes), i.c., p(ğ) should have high entropy. As these are combined using the Kullback-Leiie divergence, the higher the score is, the better the performance.
Metrics: FID. Contrary to IS, FID compares the synthetic samples ž, Pg with those of the training dataset L. ~ pd in a feature space. The samples are embedded using the first several layers of pretrained classifier. It assumes Py and pa multivariate normal distributions and estimates the means m, and m. and covariances C and C₁ respectively, for Py and pa in that feature space. Finally, FID is computed as:
DFD (pa, Pg) se Dz ((mss Ca), (my, Cy)) = ||ma - m -(CCC,,
(FID)
where Oy denotes the Fréchet Distance. Note that as this metric is a distance, the lower is, the better the performance.
Hardware, We used the Colab platform (https://col wwceearch.google..oo and Nvidia T4 GPUs.
61

---

Published as a conference paper at ICLR 2024
D ADDITIONAL EXPERIMENTS AND ANALYSES
In this section, we provide complementary experiments associated with the three games introduced in the main paper: (2D-BG), (HBG), and (C-GAN). We also provide an additional study of the robustness of I-ACVI to bad conditioning by introducing version of the (HBG) game, see $ D.3 for more details.
D.1 ADDITIONAL RESULTS FOR I-ACVI ON THE 2D-BG GAME
For completeness, in Fig. show the trajectories for the æ compates-comllleenntrr to the y iterates' trajectories depicted in Fig. of the main part.
(a)
(b) J-ACVI 2 (c) FACVI K 10,6
(d) FACVI 5,6
Figure 5: Complementary illustrations those in Fig. of the main part: depicting here the trajectories of the iterates. We compare the convergence of ACVI and I-ACVI with different parameters on the (2D-BG) problem while also depicting the central path (shown in yellow). Each subsequent bullet on the trajectory depicts the (exact approximate) solution at the end of the inner loop (when & K 1). The Nash equilibrium (NE) of the game is represented by a yellow star, and the constraint set is the interior of the red square.
Comparison between (01) and (p2). In Fig. and Fig. 7 we show the trajectories of respectively the y and æ iterates as we increase the learning rate. Increasing the learning rate increases the chance of crossing the standard log barrier, which makes the ((1) undefined for such input, as the log function not defined on the entire space. In contrast, the newly proposed barrier ($22) is defined everywhere; thus, the iterates crossing the boundary of the constrained set does not make the ($22) unstable and allows for convergence to the solution.
D.2 ADDITIONAL RESULTS FOR PI-ACVI ON THE 2D-BG GAME
In this section, we provide complementary visualization Fig. 2 in the main paper. We (i) compare with other methods in Fig. 8,9 and (ii) show PI-ACVI trajectories for various hyperparameters in Fig.
PI-ACVI baselines. In Fig, and can observe the behavior of projected gradient descent ascent, projected extragradient, projected lookahead, projected proximal point, mirror descent, and mirror prox on the simple 2D constrained bilinear game (2D-BG), we use the same learning rate of 0.2 for all methods except for mirror prox which is using learning rate of 0.4. In Fig. 10 we show trajectories PI-ACVI for & (1,4, 10, 100), B = 0.5, 150 and a learning rate 0.2.
D.3 ADDITIONAL RESULTS ON THE HBG GAME
In this section, we (i) provide complementary experiments Fig. from the main paper, well as (ii) analyze the robustness of I-ACVI against bad conditioning.
CPU time to reach a given relative error. In Fig. 11 we extend the x-axis of Fig. 4.a from the main paper for I-ACVI. Unlike baselines, I-ACVI remains fast when the target relative error is very small. This is due to the fact that I-ACVI uses cheaper approximate steps for lines 8 and 9 of Algorithm 1.
62

---

Published as a conference paper at ICLR 2024
(e) 0.3
(f) Ir 0.4
gg) 0.5
(h) Ir 0.6
Figure 6: I-ACVI trjectories the y iterates for different choices learning rates lr. Top Trajectories for the I-ACVI implementation using the standard barrier function (p11). As the learning rate increases, the y itcrates cross the log barrier, breaking the convergence. Bottom row: Trajectories for the I-ACVI implementation using the smooth barrier function defined over the entire domain (522). The extended barrier function we proposed is defined everywhere; thus, if the iterates cross the standard barrier, the method converges, allowing for the use of larger step sizes. We can reduce the constant c to improve the stability; we used e {10, 1, 0.2, 0} and ? {0.3, 0.4, 0.5, 0.6) for the learning rate.
(c) Ir = 0.3
( lr 0.4
(g) 0.5
(h) Ir = 0.6
Figure 7: Complementary to Fig. 6, I-ACVI trjectories for the & iterates for different choices of learning rates (r. Top row: Trajectories for the I-ACVI implementation using the standard barrier function (Pt). As the learning rate increases, the y iterates (see Fig. 6) are crossing the log barrier, which breaks the optimization. Bottom new smooth barrier function defined over the entire domain (p2). The iterates are allowed to cross the standard log barrier, which allows the y iterates recover from large steps. We can reduce the constant e to improve the stability, we used e = {10, 1, 0.2, 0), and = {0.3, 0.4, 0.5, 0.6} for the learning rate.
Trajectories for the I-ACVI implementation using the
63

---

Published as a conference paper at ICLR 2024
(a) P-GDA
(b) P-EG
(c) P-LA
(d) P-PP
Figure 8: Comparison of Projected Gradient Descent Ascent (P-GDA), extragradient (P-EG) (Korpelevich, 1976), Lookahead (P-LA) (Chavdarova et al., 2021) and Proximal-Point (P-PP) on the (2D-BG) game. For P-PP, we solve the inner proximal problem through multiple steps of GDA and use warm-start (the last PP solution used starting point of the next proximal prob- lem). All those methods progress slowly when hitting the constraint. Those trajectories can be contrasted with PI-ACVI Fig. 10.
(a) Mirror-Descent
(b) Mirror-Prop Prox
Figure 9: Comparison of Mirror-Descent (MD) and Mirror-Prox (MP) on the (2D-BG) game. Mirror-descent cycles around the solution without converging. Mirror-prox is converging to solution. Both methods have been implemented using simultaneous updates and with Bregman
divergence Dy (x, y) with (zx)
2-0.4 log( 2+0.1
(1 2-0.4 log(1
2+0.1)
2.8
2.8
2.8
2.8
(0) -=1
(1 1-=4 4
(g) f - 10
(h) L = 100
Figure 10: PI-ACVI (Algorithm 2) for different choices of f. Top row: Trajectories for the iterates. Bottom row: Trajectories for the y iterates. For e 1, the trajectory for the y iterates similar to the one of P-GDA (see Fig. 8), as we increase & we observe how relatively few iterations are required for convergence compared to baselines.
64

---

Published as a conference paper at ICLR 2024
400
GDA
EG
300
OGDA
LA4-GA
CPU time
ACVI
200
I-ACVI
100
0
10Th
10
relative error
Figure 11: Comparison between I-ACVI and other baselines used in $ 5 of the main part. CPU time (in seconds; y-axis) to reach a given relative error (x-axis); while the rotational intensity is fixed to y 0.05 in (HBG) for all methods. I-ACVI much faster converge than other methods, including ACVI.
10.0
10
20
7.5
30
40
50
5.0
60
2.5
5 10
50
100
130
Kg
Figure 12: Impact of Ko: joint impact of the number of inner-loop iterations Kg t 0, and different choices of inner-loop iterations for K at any / > 0, on the CPU-time needed to reach fixed relative error of 10-4, A large enough Ko compensate for small K+.
Impact of Ko- In Fig. 12 we show, for each (Ko, K4) the CPU time required to reach relative error of 10-4 Those times are highly correlated with number iterations shown in Fig. 4.c of the main paper.
Comparison with mirror-descent and mirror-prox. In Fig. 13 extend the experiments of Fig. 4.b of the main paper to include the mirror-deceent (MD) and mirror-prox (MP) methods described in App. A.5.
Impact of conditioning. We modify the (HBG) game to study the impact of conditioning. Hence, propose the following version:
min max . Dæ>.
(HBG-v2)
2. EA
A=
[2; E R 500
0, and eTx. 1), and D diag dia....,...,.. (500)
65

---

Published as a conference paper at ICLR 2024
GDA
BG
OCDA
number of d'iterations
40
LA4-CDA
ACVI
L-AVVI
30
Hitroo--Dscen
Mitror-Prus
20
10
0.0
0.2
0.4
0.6
0.8
1.0
Figure 13: Number of iterations to reach relative error of 0.02 for varying values of the rotational intensity (z-axiis). We fixed the maximum number of iterations to 50. For mirror-descent and mirror-prec proor, we used the KL-divergence Dæ(2z (x, y) and use large step sizes of respectively = 500 and ς 280. When the rotational intensity strong (small 17). mirror-descent fails to converge within the 50 iterations budget. However, when is large, mirror descent converges much faster than GDA, EG, OGDA, and LA4-GDA. Mirror-prox better than mirror-descent handling strong rotational intensities but is slowed down when the game is mostly potential. In comparison, ACVI converges after small number of steps regardless of r).
The solution of this game depends on the {a; 1500.
1/a1
1/02
x2
500 Σ === 1/as
//500
We define the conditioning к the ratio between the largest and smallest a;; K Omin. In our experiments we select ag linearly interpolated between 1 and Qmax (e.g. using the np np. mp.linspace (1, a.max, 500) NumPy function). We set Qmin = 1 and vary Qmax E {1, (1,2.3, 5,5, 6, 7, 9, 10). We compare projected extragradient (P-EG) with I-ACVI. For P-EG, we obtained better results when using smaller learning rates for larger Qmax: 7/ = 0.3 0.9"max For I-ACVI we set B 0.5, / = 10-5 = 0.5, 7 0.003, K = 100 and T 200. We vary l depending on Ommax: f = 20 for Omax E [1, 2),, L = 50 for Omaax E {4, 5, 6). and & = 100 for Qmax 87,8,9, 8, 9, 10). We compare the CPU times required to reach a relative error of 0.02 in Fig. 14. We observe that I-ACVI is more robust bad conditioning than P-EG. As - 0. P-EG fails to converge an appropriate time despite reducing the learning rate. For I-ACVI, keeping the same learning rate and only increasing is enough to compensate for smaller values. One can speculate that I-ACVI is more robust thanks to (i) the y y-problem (line in Algorithm 1) not depending on F(x). hence being relatively robust the problem itself, and (ii) the æ-problem (line 8 in Algorithm 1) being "regularized" by yı and A
Omaa
D.4 ADDITIONAL RESULTS ON THE C-GAN GAME
This section shows complementary results to our constrained GAN MNIST experiments. Fig. 15, we further show the impact of to the convergence speed by training different PI-ACVI models with Eu E {20, 50, 100, 200, 400, 600, 800, 1000). all other hyperparameters being equal - setting l 10. We compare in Fig. 16 the obtained curves for to 400 with projected-GDA (P-GDA), and verify that similarly to Fig. the main paper for which & = 20 PI-ACVI is here as well outperforming significantly P-GDA. This shows that PI-ACVI relatively unaffected by l as opposed to lg-
66

---

Published as a conference paper at ICLR 2024
400
P-EG
L-CVI
300
CPU time
200
100
0.25
0.50
0.75
1.00
Figure 14: Experiment on conditioning: CPU time to reach a relative error of 0.02 on (HBG-v2) game, for different conditioning values While P-EG struggles to converge when the conditioning bad (small k), I-ACVI, on the other hand, can cope relatively well.
PL-CNL G
PLACNI
PLACVIC
F10
10a
PLACNT
PLACNT f mm
12
PLACNT
PLACCE fo- 200
109
PLACNN
4CV1
PLACNE 1200
250
250
500
1000
1250
Timec (sceonds)
Time (scoodds)
(a) FID (C-GAN)
(b) IS (C-GAN)
Figure 15: Effect of l on FID and IS: On the MNIST datasets, comparison of various runs of
PI-ACVI for different to- All other hyperparameters
equal: l_ 10, 8 0.5, see C for more
details. (a) and (b): we observe the importance of Ep. despite 4 = 10 being relatively small we still converge fast to a solution in terms of both FID (4) and (t) given to large enough. All curves are obtained by averaging over two seeds.
P-GDA PI-ACVI & 100
10a
FID
2
10"
P-GDA
2
PI-CCI J00
500
1000
1500
0
500
1000
1500
Time (seconds)
Time (scconds)
(a) FID (C-GAN)
(b) IS (C-GAN)
Figure 16: PI-ACVI vs. P-GDA on (C-GAN) MNIST: On the MNIST datasets, comparison of
P-GDA and PI-ACVI. For PI-ACVI, we &n 400 and 4 10. (a) and (b): both FID (L) and IS (t), PI-ACVI converges faster than P-GDA. The difference with Fig. 3 from the main paper that we use 4 = 10 instead 4 = 20. This shows that PI-ACVI relatively robust different
values of E..
67


Reviews:
[{"review_id": "IXlUTXJEhm", "reviewer": "Reviewer_mjvt", "summary": "The paper studies how to use first-order methods to solve the variational inequality with general constraints. The authors first show the last iterate convergence of the ACVI method in Yang et al. (2023) without assuming the Lipschitzness of the operator. Then, the authors show similar convergence of an inexact version of ACVI if the errors of subproblem solvers decrease at proper rates. When the inequality constraints are fast to project, the authors show a simplified ACVI and its convergence. Experiments are provided to show the convergence and less computational time.", "questions": "- Since this paper focuses on improving existing analysis, can the authors more formally state new analysis techniques compared with Yang et al. (2023)? \n\n- How can the errors of solving subproblems be controlled in practice?\n\n- What is the computational complexity of inexact ACVI? How can this be compared with the one for ACVI in your experiments? \n\n- Any examples that lack Lipschitzness? and experiments? \n\n- Can the authors generalize inexact ACVI to more general operators? What would be failure if not?\n\n- Have you compared this work with last-iterate or non-ergodic convergence results in the constrained optimization literature?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written, and all results are supported by proofs.\n\n- The authors prove the same performance guarantee for ACVI under less restrictive conditions. A new analysis technique is developed to remove the Lipschitz assumption. \n\n- It is also important to consider inexact ACVI that takes warm-start technique, which provides a more practical algorithm than the original. The authors provide the same convergence rate by conditioning the quality of approximation solutions, which is a useful guide. \n\n-  Some experiments on standard bilinear games and GANs are provided to show convergence.", "weaknesses": "- The last iterate convergence is characterized by the gap function and the difference of two primal iterates. This metric is different from the optimality gap used in Yang et al. (2023). I am not sure if they are comparable. \n\n- The algorithm design has a great similarity with ACVI in Yang et al. (2023). I would expect much more on highlights on analysis techniques, which seem to be not formally presented in the main paper.\n\n- It is less discussed why removing the Lipschitz assumption is important in theory and practice. \n\n- The method is limited to monotone operators.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aGAjVviMsl", "reviewer": "Reviewer_VTND", "summary": "Variational inequality problems are a class of numerical problems that generalize constrained optimization problems. The rough idea is to use the first-order optimality characteization, and replace the gradient $\\nabla f(x)$ with some other more general function $F(x)$. These problems arise naturally when considering equilibrium computation or robust modifications of ordinary constrained optimization problems. The authors study the ACVI algorithm, an ADMM-type algorithm for this setting, and show that it converges under weaker assumptions compared to prior work, specifically under generalization of convexity to the variational inequality setting without Lipschitz-smoothness-type assumptions used previously. They also show this works even if certain steps within the respective algorithm are performed approximately rather than exactly, and use this to study how warm-start techniques affect those steps. The argument is reminiscent of Lyapunov analysis, and works by exhibiting a certain gap function which is shown to decrease at every iteration, revealing part of why ACVI behaves this way. The developed theory is illustrated on somewhat standard experiments.", "questions": "Can you comment a bit further on the role of the barrier function in ACVI, and in the theory of Section 3.2? The barrier function is already a part of ACVI, and therefore not a new component of inexact ACVI - is this correct? If so, why talk about it in detail before Theorem 3.2, rather than in the background section? Does Theorem 3.2 specifically require one of these two barrier functions, and would not work with others? If so, this should be stated more explicitly - right now it's buried in the definition of Algorithm 1, and one has to unroll that definition - including the line above saying \"Choosing among these is denoted with $\\wp$\" - to realize this, which isn't great because it puts a key part of the logic outside of both the text which defines Theorem 3.2 and the text that defines Algorithm 1.\n\nAppendix typo: \"subproblems and definitions\" -> \"Subproblems and definitions\" (missing caps)", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is a good paper. This review is going to be relatively short because the contribution is good, the paper is well-written, and everything makes sense.\n* Understanding the behavior of optimization algorithms and their generalizations in cases where smoothness assumptions are relaxed is a clear and well-motivated class of research questions, and many papers in convex optimization have been written about this, which overtime have significantly improved understanding of the field and led to advances. It makes a lot of sense to also do this for more general settings.\n* The paper as a whole and introduction in particular is clear, well-written, and makes sense. The authors do an excellent job at drawing attention to the aspects that distinguish variational inequalities from ordinary optimization, including limit-cycle-type behavior often found when solving for equilibria and similar problems. that monotonicity plays the role of convexity, and similar points.that someone who is familiar with optimization but not with variational inequalities - perhaps a significant fraction of readers  would want to know.\n* There is not enough work on algorithms for equilibrium-solving. The fact that algorithms for doing so are underdeveloped compared to gradient-based optimization is one of the big reasons why GANs have declined in favor of diffusion models and other approaches. Having better tools could help unlock technical tools for problems like this, and for getting multi-agent reinforcement learning algorithms to work more reliably, which is an important goal for machine learning.\n* The algebra in Appendix C, which is used to prove the results, is rather heavy: makes me glad that the authors have taken the effort to prove the necessary results, as it means that somebody else that wants to use the algorithm or a similar-enough variant doesn't have to. I'd imagine someone working on optimization would find it instructive to go through the appendix to see what kind of tricks are used, especially in comparison with more ordinary analysis of convex optimization algorithms.", "weaknesses": "* Experiments are somewhat limited. The only examples are synthetic bilinear games, and GANs. It would be nice to also have an example motivated by computational game theory, or by multi-agent reinforcement learning, or applications to economics, where equilibrium-finding algorithms that are a special case of the variational inequality framework are important.\n* Figure 1 needs a legend, because right now it is confusing. I understand the red square is the constraint set and the yellow star is the Nash from the caption: what's the difference between the yellow and blue line? Which one is the initial point? It would save my time and improve clarity to have this labeled in full on the actual plot rather than partially explained in a manner that is buried inside the caption which has a lot more details that I may or may not be ready to delve into. The vector fields are also way too small, I can't tell on my display which direction any of the arrows are pointing.\n* Please label all equations, not just the ones you think are important. When discussing technical papers with other people over Zoom, not labeling everything makes it needlessly difficult to communicate precise equation lines. Often, I end up saying \"the 3rd equation on page 4\" and then my collaborator is confused because they think I am counting by multi-line equation rather than per-line, or they think I am counting from the top rather than the bottom. This waste of time is extremely annoying and the outdated convention of \"not labeling important equations to reduce clutter (actually, to reduce ink and paper costs, which no longer exist in the digital world)\" needs to go away.\n* Font size in figures is a bit small, making it bigger would help see what is happening.\n* Notation is not always completely consistent, for instance min and argmin are sometimes italicized, sometimes not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lZckjOXYgw", "reviewer": "Reviewer_MAK9", "summary": "The present paper considers the problem of solving a variational inequality with constraints. Recall that a solution $x_\\star$ to variational inequality given by $F:\\mathcal{C}\\to\\mathbb{R}^n$ (with $\\mathcal{X}\\subset \\mathbb{R}^n$) satisfies\n$$\\forall x\\in \\mathcal{C}\\,:\\,\\langle F(x_\\star),x-x_\\star\\rangle\\geq 0.$$\nThe paper considers monotone VIs, which include convex optimization ($F=\\nabla f$ for $f$ convex) and minimal convex/concave games as special cases. The set $\\mathcal{C}$ is given by linear equality and convex inequality constraints. \n\nA standard first-order approach to this problem, such as Korpelevich's extragradient method, would require lots of projection steps to $\\mathcal{C}$. Since these may be quite expensive, Yang, Jordan and Chavdarova (ICLR 2023) considered a first-order interior point method. Their approach is based on a rewriting of the constrained VI problem using Lagrangian duality, which leads to an alternating direction method of multipliers (ADMM). Those authors show that their method works (with $O(1/\\sqrt{K})$ last-iterate error after $K$ iterations) only under assumptions that are significantly stronger than mere monotonicity (for instance, $F$ is assumed t be Lipschitz).\n\nThe present paper strengthens Yang et al's analysis in different ways. First, the algorithm by Yang et al. is shown to converge at the same rate previously shown under the sole assumption of monotonicity (plus strict monotonicity *or* strict convexity of one of the constraints). They also show that, if $F$ is Lipschitz, one may use *approximate* solvers for the optimization problems in each inner loop of the interior point method, while keeping the same convergence rate. Finally, when the constraints are \"simple\", a projection based method for the inner loop may also be used, with similar assumptions and results. The paper also presents a short empirical study suggesting that the methods given are accurate and faster than the \"competition\".", "questions": "In the proof of Theorem 3.1 (including the preceding Lemmas), can you pinpoint exactly where you manage to circumvent the strict/strong monotonicity assumption of Yang et al? It seems to me that equation (14) is one of the crucial steps: it avoids Lemma 1 in Yang et al, where the gap is bounded as a function of the distance to the optimal VI solution. However, I struggle to see where/how exactly the improvements were achieved.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper greatly increases the scope of application of first order methods in the solution of constrained VIs. In particular, it shows that such methods can be fast, while achieving similar or better theoretical guarantees than the \"competition\"", "weaknesses": "The main issue I had in reading the paper was the comparison with Yang et al. I tried to follow the long proofs in that paper and to compare them with the present proofs. Many of the steps were similar, but I was still left wondering where the main improvements took place.  \n\nGiven this, I have been somewhat conservative in my \"contribution\" score, but I am perfectly willing to reconsider it in the light of the answer to my question (see below).\n\n___\n\nA small typo: in the first two displays of page 23, the norms in the RHS are missing their squares (the mistake is fixed in the next display).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9ux12A9vaG", "reviewer": "Reviewer_uGBX", "summary": "Previous research has shown that first-order methods can be used to solve general variational inequality (VI) problems under the assumption that analytic solutions for the subproblems are available. This paper circumvents this assumption by using a warm-starting technique. The authors prove the convergence rate of the gap function for the last iteration of both the proposed exact ACVI and inexact ACVI methods. Additionally, the authors discuss scenarios where the inequality constraints are quick to project onto and introduce an alternative version of ACVI, confirming its convergence under identical conditions.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: The authors prove that the gap function of the last iterate of ACVI decreases at a rate of $O(1/\\sqrt{K})$ for monotone VIs, without depending on the assumption that the operator is L-Lipschitz.\n\nS2: The authors establish the convergence rate for both the exact ACVI and the inexact ACVI methods.\n\nS3: The authors discuss the special case of inequality constraints that are quick to project onto.\n\nS4: Experiments have been conducted to demonstrate that inexact ACVI can outperform other methods, such as the lookahead-Minmax algorithm, by advantageously solving linear systems implicitly beforehand (as shown in Steps 3 and 4 of Algorithm 1).", "weaknesses": "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.\n\nW2. 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.\n\nW3. It is preferred to provide an explanation for assuming the \"monotonicity\" of $F$ on $\\mathcal{C}_{=}$ and the \"strictly monotonicity\" of $F$ on $\\mathcal{C}$.\n\nW4. The barrier map is undefined when it first appears in Algorithm 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)