Solving Constrained Variational Inequalities via a First-order Interior Point-based Method
Authors: Tong Yang
Michael Jordan
Tatjana Chavdarova
Venue: ICLR 2023 notable top 25% (2023)
Keywords: constrained variational inequality
interior point
admm

Abstract: We develop an interior-point approach to solve constrained variational inequality (cVI) problems. Inspired by the efficacy of the alternating direction method of multipliers (ADMM) method in the single-objective context, we generalize ADMM to derive a first-order method for cVIs, that we refer to as ADMM-based interior-point method for constrained VIs (ACVI). We provide convergence guarantees for ACVI in two general classes of problems: (i) when the operator is $\xi$-monotone, and (ii) when it is monotone, some constraints are active and the game is not purely rotational. When the operator is in addition L-Lipschitz for the latter case, we match known lower bounds on rates for the gap function of $\mathcal{O}(1/\sqrt{K})$ and $\mathcal{O}(1/K)$ for the last and average iterate, respectively. To the best of our knowledge, this is the first presentation of a first-order interior-point method for the general cVI problem that has a global convergence guarantee. Moreover, unlike previous work in this setting, ACVI provides a means to solve cVIs when the constraints are nontrivial. Empirical analyses demonstrate clear advantages of ACVI over common first-order methods. In particular, (i) cyclical behavior is notably reduced as our methods approach the solution from the analytic center, and (ii) unlike projection-based methods that zigzag when near a constraint, ACVI efficiently handles the constraints.

Published as a conference paper at ICLR 2023
SOLVING CONSTRAINED VARIATIONAL INEQUALITIES VIA A FIRST-ORDER INTERIOR POINT-BASED METHOD
Tong Yang" University of California, Berkeley pptmi @etmiao@berkeles edu
Michael I. Jordan" University of California, Berkeley jordanêca werkeley............. edu
Tatjana Chavdarova'
University of California, Berkeley fata. chavdaroov@@bereeley edu
ABSTRACT
We develop an interior-point approach to solve constrained variational incquality (cVI) problems. Inspired by the efficacy of the alternating direction method of multipliers (ADMM) method in the single-objective context, we generalize ADMM to derive first-order method for e VVIs, that refer as ADMM ADMM-bassd interior- point method for constrained VIs (ACVI). We provide convergence guarantees for ACVI in two general classes of problems: (i) when the operator is É-monotone, and (ii) when it is monotone, some constraints are active and the game is not purely rotational. When the operator is, addition, L-Lipschitz for the latter case, we match known lower bounds on rates for the gap function of 0(/VK) and (1/K)) for the last and average iterate, respectively. To the best of our knowledge, this is the first presentation of a first-order interior-point method for the general cVI problem that has a global convergence guarantee. Moreover, unlike previous work in this setting, ACVI provides a means to solve cVIs when the constraints are nontrivial. Empirical analyses demonstrate clear advantages of ACVI over common first-order methods. In particular, (i) cyclical behavior is notably reduced our methods approach the solution from the analytic center, and (ii) unlike projection-bal based methods that zigzag when near a constraint, ACVI efficiently handles the constraints.
INTRODUCTION
We are interested in the constrained variational inequality problem (Stampacchia, 1964):
find x" X s.t. (x=x",F(xz)) 2 0, E
(cVI)
where X' is subset of the Fuclidean n-dimensional space R" and where F: X' + R" is con- tinuous map. Finding (an element of) the solution set S of cVT is key problem in multiple fields such as economics and game theory. More pertinent to machine learning, CVIs generalize standard single-objective optimization, complementarity problems (Cottle & Dantzig, 1968), zero- sum games (von Neumann & Morgenstern, 1947; Rockafellar, 1970) and multi-player games. For example, solving cVI is the optimization problem underlying reinforcement learning (e.g., Omid- shafiei et al., 2017) and generative adversarial networks (Goodfellow et al., 2014). Moreover, even when training one set of parameters with one loss J, that is F(x) = (x)) natural way adversary to perturb the ob-
to improve the model's robustness in some regard is to introduce jective or the input, or to consider the worst sample distribution of the empirical objective. As has been noted in many problem domains, including robust classification (Mazuelas al., 2020), adversarial training (Szegedy et al., 2014), causal inference (Christiansen et al., 2020), and ro- bust objectives (e.g.. Rothenhäusler et al., 2018), this leads to a min-max structure, which is an instance of the cVI problem. To see this, consider two sets of parameters (agents), E X1 and 22 E X2, that share a loss/utility function, f: X, x X² - R, which the first agent aims to minimize
'All authors contributed equally. Link source code: https: / / htggggtttuuhoggog com wht./aaaaaaaaaaaeaaa ACV..

---

Published as a conference paper at ICLR 2023
Figure 1: ACVI (Algorithm 1) and EG iterates depicted in red and green, resp.-on the game:
min max 0.05 . + x1 - 0.05 xz. 21 21 22ER4
The constraints are depicted with dashed lines and the iterates with circles. ACVI gets close to the Nash Equilibrium (*) in a single step, whereas EG zigzags when hitting constraint. The remaining commonly used methods GDA, OGDA, and LA- GDA-perromd similarly to EG, see App. E.
and the second agent aims to maximize. Then the problem to find a saddle point of f. i.e., a point (xri, x²)) such that [ijj. (22) S f(x) az) S [(11, w5). This corresponds to cVI with F(x:) = V2, (2), -
Solving cVIs is significantly more challenging than single-objective optimization problems, due to the fact that F is general vector field, leading to "rotational" trajectories in parameter space (App. A). In response, the development of efficient algorithms with provable convergence has recently been the focus of interest in machine learning and optimization, particularly in the unconstrained setting, where = RR" (e.g., Tseng, 1995; Daskalakis et al., 2018; Mokhtari et al., 2019; 2020; Golowich et al., 2020b; Azizian et al., 2020; Chavdarova et al., 202 Gorbunov et al., 2022; Bot et al., 2022).
In many applications, however, we have constraints on (part of) the decision variable æ, that is, X is often strict subset of IR" As an example, let revisit the aforementioned distributionally robust prediction problem: consider a linear setting (cf. Eq. in Rothenhäusler et al., 2018) and class of parametrized distributions A fw E R w 0, e w 1}, where Rd is a vector of all ones. Thus, the robust problem is: millagR* mäX wT (y Dæ), subject to w 2 0, eTw = 1, where D E Rd contains d samples of an n-dimensiinal covariate vector, and y E R is the vector of target variables (the constraint < 1 is implicd). This illustrates that given standard minimization problem, its robustification immediately leads to an instance of the cVI problem; see further examples in 5. Additional example applications include (i) machine learning applications in business, finance, and economics where often the sum of the decision aariables-represente example, resources-canne exceed a specific value, (ii) contract theory (e.g. $2.3.2 in (Bates et al., 2022) where one player is the parameters of probability distribution as above), and (iii) solving optimal control problems numerically, among others.
for
Significantly fewer works address the convergence of first-order optimization methods in the con- strained setting; see $ 2 for an overview. Recently, Cai et al. (2022) established convergence rate for the projected extragradient method (Korpelevich, 1976), when F is monotone and Lipschitz (see $ 3 for definitions). However, (i) the proof that the authors presented computer-assise hard to interpret and of limited usefulness for inspiring novel (e.g., accelerated) methods, and (ii) the considered setting assumes the projection is fast to compute and thus ignores the projection in the rate. The latter assumption only holds in rare cases when the constraints are relatively simple that operations such as clipping suffice. However, when the inequality and/or equality constraints are of general form, each EG update requires two projections (see App. A.4). Each projection requires solving a new/separate constrained optimization problem, which if given general constraints implies the need for second-order method as explained next.
which makes
Interior point (IP) methods are the de facto family of iterative algorithms for constrained optimization. These methods enjoy well-established guarantees and theoretical understanding in the context of single-objective optimization [see, e.g.. Boyd & Vandenberghe (2004), Ch. 11, Megiddo (1989), Wright (1997)], and have extensions to a wide range of problem settings (c.g., Tseng, 1993; Nesterov & Nemirovski, 1994; Nesterov & Todd, 1998; Renegar, 2001; Wright, 2001). They build on a natural idea of solving simplified homotopic problem that makes it possible to "smoothly" transition to the original complex problem; see $ 3.1. Several works extend IP methods to cVI, by applying the second-order Newton method to a modified Karush-Kuihe Kuln-Tucker (KKT) system appropriate for the cVI (Ralph& & Wright, 2000; Qi & Sun, 2002; Fan & Yan, 2010; Monteiro & Pang, 1996; Chen et al., 1998). Many of these approaches, however, rely on strong assumptions- see $ 2. Moreover, although these methods enjoy fast convergence in terms of the number of iterations, each iteration involves the computation of the Jacobian F (or Hessian when F = fx)x) which quickly becomes prohibitive for large dimension n of æc. Hence first-order methods are preferred in practice.
2

---

Published as a conference paper at ICLR 2023
We are currently missing a first-order optimization method for solving cVI with general constraints. Accordingly, in this paper, we focus on the following open question:
Can we derive first-rrdr algorithms for the cVI problem that (i) can be applied when general constraints are given, and that (ii) have global convergence guarantees?
In this paper, we develop precisely such a method. To mitigate the computational burden of second- derivative computation, we replace the Newton step of the traditional IP methods with the alternating direction method of multipliers (ADMM) method. ADMM was designed with a different purpose: it is applicable only when the objective is separable into two or more different functions whose arguments are non disjoint-see $ 1.1 for full description and can be seen as equivalent to Douglas-Rackfors operator splitting (Douglas & Rachford, 1956) applied in the dual space (see e.g. Lin et al., 2022).
ADMM owes its popularity primarily to its computational efficiency (Boyd et al., 201 1) for large- scale machine learning problems and its fast convergence in some machine-learnine Nishihara et al., 2015). The core idea of our approach is reformulate the original cVI problem with equality and inequality constraints via the KKT conditions, so as to apply ADMM in such a way that the subproblems of the resulting algorithm have desirable properties (see 4.1). That is, by generalizing the technique underlying ADMM, we derive a novel first-order algorithm for solving monotone VIs with very general constraints. Furthermore, this framework can be used design novel algorithms for solving cVIs; see App. C.
settings (e.g..
Our contributions can be summarized as follows:
Based the KKT system for the constrained VI problem and the ADMM technique, derive an algorithm that we refer to as the ADMM-based Interior Point Method for Constrained VIs (ACVI) $ 4.1 and Algorithm 1.
We prove the global convergence of ACVI given two sets of assumptions: (i) when F is &- monotone, and (ii) when it is monotone, the constraints are active at the solution, and the game is not purely rotational. By further assuming F is a Lipschitz operator, we upper bound the rate of decrease of the gap function and we match the known lower bound for the gap function of O(I/VK) for the last iterate- $ 4.2.
Empirically, we document two notable advantages of ACVI over popular projection- saddle- point methods: (i) the ACVI iterates exhibit significantly reduced rotations, they approach the solution from the analytic center, and (ii) while projection based methods show extensive zigzagging when hitting constraint, ACVI avoids this, resulting in more efficient updates- 5.
Our convergence guarantees are parameter-free meaning these do not require priori knowledge of the constants of the problem (such as the Lipschitz constant), and, interestingly, the convergence guarantee does not require that F' is Lipschitz. This assumption is solely used to express the rate of decrease the gap function (in contrast to the extragradient method (Korpelevich, 1976) where such an assumption is necessary to show convergence. To the best of our knowledge, the proposed ACVI method is the first first-order IP algorithm for VIs with a global convergence proof.
2 RELATED WORK
Unconstrained VIs: methods and guarantees. Apart from the standard gradient descent ascent (GDA) method, among the most commonly used methods for VI optimization are the extragradi- ent method (EG, Korpelevich, 1976), optimistic GDA (OGDA, Popov, 1980), and the lookahead method (LA, Zhang al., 2019; Chavdarova et al., b0.1b). (See App. A for full description). In contrast to gradient fields (as in single-objective setting), when F is general vector field, the last iterate can be far from the solution even though the average iterate converges to it (Daskalakis et al., 2018; Chavdarova et al., 2019). This is problematic since it implies that the average convergence guarantee weaker in the sense that it may not extend to more general setups where we can no longer rely on the convexity of X. Golowich et al. (2020b;a) provided last-iterate lower bound of O PVK for the broad class of p-stationary canonical linear iterative (Ø-SCLI) first-order methods (Arjevani et al., 2016). An extensive line of further work has provided guarantees for the last iterate for other problem classes. For the general monotone VI (MVI) class, the following p-SCLI methods come with guarantees that match the lower bound: (i) Golowich al. (2020b) obtained rate in terms of
3

---

Published as a conference paper at ICLR 2023
the gap function relying on first- and second-order smoothness of F, and Gorbunov et al. (2022)
obtained a rate of O 1 K in terms of reducing the squared norm of the operator relying on first-order smoothness of F (Assumption 1), using a computer-assisted proof, and (ii) Golowich et al. (2020b) and Chavdarova et al. (2021a) provided the best iterate rate for OGDA.
Constrained zero-sum and VI classes of problems. Gidel et al. (2017b) extended the Frank- Wolfe (Frank& & Wolfe, 1956; Jaggi, 2013; Lacoste-Julien & Jaggi, 2015) method-also known as the conditional gradient (V.F Demyanov, 1970>-to solve a subclass of cVV, specifically constrained zero-sum problems. This extension was carried out under a strong convex-concavity assumption and also under the assumption that the constraint set is strongly convex; that is, it has sublevel sets that are strongly convex functions (Vial, 1983). Daskalakis & Panageas (2019) provided an asymptotic proof for the last iterate for 7ero-sum convex-concave constrained problems for the optimistic multiplicative weights update (OMWU) method. Wei et al. (2021) focused on OGDA and OMWU in the constrained setting and provided convergence rates for bilinear games over the simplex. In her seminal work, Korpelevich (1976) proposed the classical (projected) extragradient method (EG)-see App. A-and proved its convergence for monotone (c)VIs with an L-Lipschitz operator, and Cai et al. (2022) established rate with respect to the gap function using computer-aided proof. Tseng (1995) built on (Pang, 1987) and provided a linear convergence rate for EG in the setting of strongly monotone F, whereas Malitsky (2015) focused on the same constrained setting but on the projected reflected gradient method. Diakonikolas (2020) obtained parameter-free guarantee for Halpern iteration (Halpern, 1967) for cocoercive operators. Goffin et al. (1997) described second-order cutting-plane method for solving pscudomonotone VIs with linear inequalities.
Interior point (IP) methods in single-objective and VI settings. Traditionally IP methods primarily express the inequality constraints by augmenting the objective with a log-barrier penalty (see $ 3.1), and then use Newton's 's method to solve the subproblem (Boyd & Vandenberghe, 2004). The latter involves computing either the inverse of a large matrix or a Cholesky decomposition and yet it can be highly efficient in low dimensions as it requires only a few iterations to converge. When the dimensionality of the variable is large, however, the computation becomes infeasible. Among other IP variants that address this issue, Lin et al. (2018) replaced the Newton step with the ADMM method, which is known to be highly scalable in terms of the dimension (Boyd et al., 2011), 1). In the context of cVIs, a few works apply IP methods, mostly Newton-based (e.g.. Nesterov & Nemirovski, 1994, Chapter 7). Monteiro & Pang (1996) analyze path-following IP methods for complementarity problems, which are a subclass of cVI, using local homeomorphic maps. Chen et al. (1998) provided superlinear global convergence rate of the smoothing Newton method when F is semi-smooth for box constrained VIs. Similarly, Qi & Sun (2002); Qi et al. (2000) focused on the smoothing Newton method and provided the rate for the outer loop. Ralph & Wright (2000) showed superlinear convergence for MVI problems under inequality constraints, under the following set of assumptions: (i) existence of strictly complementary solution, (ii) full rank of the Jacobian of the active constraints at the solution, and (iii) twice differentiable constraints. They provided a local convergence rate. Fan & Yan (2010) considered inequality constraints and proposed second-order Newton-based method that has global convergence guarantees under certain conditions. A rate was not provided.
3 PRELIMINARIES
Notation. Bold small and capital letters denote vectors and matrices, respectively. Sets are denoted with curly capital letters, e.g., S. The Euclidean norm of is denoted by ||0/|, and the inner product in Euclidean space with (...). With @ we denote element-wise product. We let [r]] denote (1,...,n.}
and let e denote vector of all I's. We let xs 1. y denote and y are perpendicular.
In the remainder of the paper, we consider a general setting in which the constraint set C C X' is defined as an intersection of finitely many inequalities and linear equalities:
C (x E (x))) I 0, [m], Ca: =d)
(CS)
where each pp: R + R. C E T d E TRP, where we assume rank(C)) = p. For brevity, with yp
we denote the concatenated yp (-), E [m], and in the remainder of the paper, each yo E C*l (R"), [m] and is convex. For convenience we denote:
C₂ - (ac E RD (xx)) S 0}, Ca 2 {a R (+(x) < < and C_ C E Cy = d]
thus the relative interior of C is int C A Ce n==,, and we consider int C + 1 and C is compact.
4

---

Published as a conference paper at ICLR 2023
In the following, we list the definitions and assumptions refer to later Definition ((strong/E) monotonicity). An operator F X 2 S - R" is monotone on S if:
(x - x', F()x) F(x')) 2 Va, x' E S. F is said to be E-monotone on S iff there exist > 0 and & such that (x x', F(x) - F(x')) 2 c/ x' l1s for all x, x' E S. Finally, F is u--trongly monotone on S if there exists μ > 0, such that (æ x', F(x) F(x')) 2 μl| x' II? for all z, x, E S. Moreover, we say that an operator is star- monooonee,, star star-f-marn faar-fmmnotone or star-strongly-monooonee (on S) if the respective definition holds for x' = xx, where x² ESS
Note that the "star-" definitions are weaker relative to their respective non-star counterparts. The above definition holds similarly for unconstrained VIs, by setting S = R". The analog for cVI of the funetion values used as performance measure for convergence rates in convex optimization is the gap function (a. the optimality gap or primal gap), defined next.
Definition 2 (gap function). Given candidate point x' E X and map F F 2 S + R where S is compact, the gap function G R - RR is defined as (ix', S) - ma x' x)
#ES
Note that the gap function requires S to be compact in order to be defined (as otherwise, it can be infinite). We will rely on the following assumption to express our rates terms of the gap function. Assumption 1 (first-order smoothness). Let F X 2 S + IR be an operator, we say that satisfies L-first-oder smoothness S. or L-smoothness, L > 0 such that [F(x)) F(x')ll < L || - x' x'I.. for all x, x' E.S.
F is L-Lipschitz map; that is, there exists
As an informal summary, a solution existence guarantee follows when X' is compact; see Chapter 2.2 of (Facchinei Pang, 2003), and App. A.2.
3.1 RELEVANT PATH-FOLLOWING INTERIOR-POINT METHODS AND ADMM
In this section, we overview the interior-poin point approach to singlc-objective optimization, focusing on aspects that are most relevant to our proposed method. Consider the following problem:
min f(x) S.f.
(xx) < 0 and Cr d,
(cCVX)
where f. T. :" IP methods solve problem (cCVX) by reducing it sequence of linear qqualit-connstrinee problems via a logarithmic barrier (see, e.g., Boyd & Vandenberghe, 2004, Chapter 11):
R"
R are convex and continuously differentiable. a E R", C RP*", and d E RP.
min f(x)
Σ log(-<:(z)) s.l. =d,d
with / 0>0.
(I-CCVX)
Assume that (l-CVX) has solution for each μ > 0, and let x denote the solution of (l-CCVX for a given The centrul path of (I-CCVX) is defined as the set of points x" O. Note that x² E Ik" a strictly feasible point of (cCVX) as satisfies cfx**) < 0 and Cax
Alternating direction method of multipliers (ADMM) method. ADMM (Glowinski & Marroco, 1975; Gabay& & Mercier, 1976; Lions& Mercier, 1979; Glowinski & Le Tallec, 1989) is a gradient- based algorithm for convex optimization problems that splits the objective into subproblems each of which is easier to solve. Its popularity is due to its computational scalability (Boyd et al., 201 I). Consider problem of the following form: min
f(x) + gz)) s.t. a.
Ax
By b,
(ADMM-Pr)
where f,g : IR - are convex, x. y E R", B, E RR''xn xn and b E Rdd, The augmented Lagrangian function, C.(.), of the (ADMM-Pr) problem is:
8 |Ax + By - bl] (AL-CVX)
La(x, y, A) = ((x) + gly) + (Ax + By - b, X) 2
where 3 > is referred to as the penalty parameter. If the augmented Lagrangian method used
to solve (AL-CVX), each step i we have: 1 1 argmin La(2, y, )x) and A
2.y
A + 3(Ax++1 + Byk+1 - b), where the latter step is gradient ascent on the dual. In contrast, ADMM updates and y alternating way follows:
Øk++ argmin L,(x, yke AE),
yk+1 argmin Co( Dk. Au),
(ADMM)
y
A Au + 3 + By -b). b).
5

---

Published as a conference paper at ICLR 2023
4 ACVI: FIRST-ORDER ADMM-BASED IP METHOD FOR CONSTRAINED VIs
4.1 DERIVING THE ACVI ALGORITHM
In this section, we derive an interior-pois point method for the cVI problem that we refer as ACVI (ADMM-base) interior problem for constrained VIs), We first restate the cVI problem in a form that will allow us to derive an interior-poing procedure. By the definition of cVT follows (see $1.3 in Facchinei & Pang, 2003) that:
w (rgminF(ww))
F(x) + (x CTu= 0 Cx=d d 0 (0 00
a E St +
(KKT)
s.f. (=)) S 0 Cz=d
where À E Th and v E Rp are dual variables, and 1. denotes perpendicular. Recall that we assume that int C * thus, by the Slater condition (using the fact that (o [m]] are convex) and the KKT conditions, the second equivalence holds, yielding the KKT system of cVL. Note that the above equivalence also guarantees the two solutions coincide; see Facchinei & Pang (2003, Prop. 1.3.4 (b)). Analogous to the method described in $ 3, add log-barrier term the objective to remove the inequality constraints and obtain the following modified version of (KKT);
F(x) + (x) CTv= A (()) tue ue
m
x orgmin F(w)T=z - 1 > log (-vx(z))
+
(KKT-22
Cx- d=
s.t. Cz=d d
(pxx) < <,,>0 0,
with j > 0, a [I, 1| E Rm Again, the equivalence holds by the KKT and the Slater condition. We derive the update rule at step k via the following subproblem: min F(wx)
> log (- s.t. Ca = d, where we fix w = ww.- Directly projecting on the equality
constraint may cause the vectors to fall out of the domain of the log term. On the other hand, (i) wa is a constant vector in this subproblem, and (ii) the objective is split, making ADMM natural choice to solve the subproblem. Hence, we introduce a new variable y E IR yielding:
((wn)(w)))) Tx + [C = d - - - log ( (.))) 1 d a f0, 0,
C d
Ca + d. (1)
+00,
8.l. = y
Note that 1(Cx = d] is generalized real-valued convex function of æ. We introduce the following:
P. A (CCT)) C, (P.) and
d. CTCCT)) -'d, d,
(d.-EQ)
where P. R and de R The augmented Lagrangian of (1) is thus:
Ca y, A)=FF(w)TTar + 1(Cx d) - 1 Σ log(-pp:( (x())) + X, x y) + 8 1 =l (AL)
m
where 3 > 0 is the penalty parameter. Finally, using ADMM, we have the following update rule for æ at step k:
B x ys
1 (F( An)
#h+1
arg min Ca(æ, yk. Au) arg min =EC=
(2)
=EC=
This yields the following update for x::
Ek+1 = P yk
(F(wE) + xxa)) de.
(X-EQ)
3
For y and the dual variable A. we have:
log ( (-p)())) 8
1 = argmin Cg (x y, As) arrmin
3k+1
3 A
1=1
(Y-EQ)
A A 3(x yk+1))
(X-FQ)

---

Published as a conference paper at ICLR 2023
Next, we derive the update rule for w. We set wy to be the solution of the following equation:
W P.F(w) Payk + 3 P.dx de 0.
(W-EQ)
The following theorem ensures the solution of (W-EQ) exists and is unique, see App. B.I for proof. Theorem 1 (W-EQ: solution uniqueness). If F monotone on C_, the following statements hold true for the solution of (W-EQ): (i) it always exists, (ii) it is unique, and (iii) it is contained in C_. Remark 1. Note that when there are no equality constraints, C= becomes the entire space IR.". Further notice that w = 2k+1, thus it is redundant to state it in the algorithm, and we remove w.
We summarize the full algorithm as Algorithm 1. For problems such as affine or cow-dimensional VIs, or optimization over the probability simplex, (W-EQ) can be solved analytically, such that step 8 is fast to compute. For problems where (W-EQ) is cumbersome to solve analytically- e.g. in GANs- MnNN--oneao could use optimization methods for the unconstrained case, e.g., EG and GDA, among others. See App. B.5 for further discussion. In the remaining discussion, where clear from context, we drop the superscript from the iterate i
Algorithm 1 ACVI pseudocode.
1: Input: operator F X' + R", constraints Ca d and (x:) S 0, [m]]. hyperparameters 1-1,8 > 0,6 E (0, 1), number of outer and inner loop iterations T and K, resp.
2: Initialize: yo (0) E R x E R
3:
where P. E Raxn where de RR"
4: de A CT(CCT)-LL d
5: for l = =0, -0...., T - do
6: Ne = 614-1
7:
for k = 0....
K do
Set x x+41 to be the solution of: P.F((x)) P.y. (1) 1 P.A
(1)
(1) de 0 (w.rt. x))
8:
9:
yk+1 argmin - Pt Σm log (1())) + y x k+1 3 ;
(8)
(1)
(1)
10:
A k+1 x
(0)
+ B[ - vbt1)
end for
12: (y)
(+1)
0
(+1)))= e (y x
end for
4.2 CONVERGENCE ANALYSIS
We consider two broad classes of problems. The first class assumes that F is É-monotone on C=-a stronger assumption than monotonicity, yet weaker than strong monotonicity. The second setup requires that (i) F is monotone, (ii) the constraints are active at the solution, and (iii) F is not purely rotational. Note that (iii is weaker than requiring that the active constraints at the solution form an acute angle with the operator; in other words, given the latter, the former holds due to monotonicity of F. (See App. B). Note that (iii) is not strong, as purely rotational games occur "almost never" in Baire category sense (Kupka, 1963; Smale, 1963; Balduzzi et al., 2018; Hsieh et al., 2021). The proof's of the main theorems use the following lemma.
Lemma 1 (Upper bound for G())). When F is L-Lipschitz on C_ per Assumption we have that any iterate oy produced by Algorithm satisfies G( C) < Mo || - x+1, where My > depends linearly on L, and x² Sē,F
To state the results define the following sets. For s 0, let Ć, A dl re), and similarly let č, & {ar E [ dll 8, (xx)) 0). We have the following.
Theorem 2 (Last and average iterate convergence for star-E-monotone operator). Given an operator F:X + Rn monotone on C= (Def. 1), assume that either F is strictly monotone > O such that F is star-E-monotone on either C, or C.. Let K and (t) 2 & Ek (t) denote the last and average iterate of Algorithm 1, respectively, run with sufficiently small 11 Then for all E (T), we have that:
or one of yp:
strictly convex. Assume there exists
7

---

Published as a conference paper at ICLR 2023
K - x O R
1.
a x O (ttz))
2. If in addition F is E-monotone on C=,, we have
OK
3. Moreover, if F is L-Lipschitz on Ca per Assumption I the same corresponding upper bounds hold for g(xx KKK () and G( C): that is, g( K. C) S O( (()/tz))) and G( [ C) S ( (((TT))
Remark 2. Note that the convergence guarantee does not rely Assumption I, and it is solely used to relate the rate to the gap function. Also, note that μ111 does not impact the convergence rate. Moreover, for simplicity we state the result with sufficiently small μl1,, however, the proof extends to any p-1 > 0. That is, the above result can be made parameter-fiee see App. B.4.
Theorem 3 (Last and average iterate convergence for monotone operator). Given an operator F: X IR", assume (i) F is monotone on C.. and (ii) either F is strictly monolone on C or one of Pi is strictly convex, and (iii) in. F (x))
(t) 2==" > 0. where S = C2 or C.. Let æ'K ||
==S(((m))
and (1)) A : E xx sufficiently small p-1. Then for all t E [T], we have that:
(0) denote the last and averuge iterate of Algorithm 1, respectively, run with
1.
" x:1 ((()
2. If in addition inf F( x-2- 0 (with S = čr or C.), then | x² xk()).
|
x=S\
3. Moreover, if F is L-Lipschitz on Ca per Assumption 1-ehe same corresponding upper bounds (t) hold ( K C) and G( K C). that is. 9(
(t)
(t) K C) - 0 +x) and g
(1) 5
Assumption (iii) in Theorem 3 requires the angle of F(xx) and - xx to be acute on S\ {x*}. where S = C, or C.. For example, when there are equality constraints, Assumption (iii) becomes z==" O. From (cVT) and by the monotonicity of F, we can see that for any inf F(x) ||
point x E C) {x*}, }, the angle between F(x) and x - x² is always less than or equal to T/2. And assumption (iii) requires that F(xx) & O, which means some constraints active at z², and 30 E (0, 7 x/2) s.t. for any x E C) {x*}. the angle between F(x) and x xx is upper bounded by Remark 3. Our proofs rely on the existence of the central path see Appendix A. Note that since is compact, it suffices that either: (i) F is strictly monotone on C. that (ii) one of the inequality constraints Pp is strictly convex for the central path to exist (Facchinei & Pang, 2003, Corollary I 11.4.24). Thus, if F is E-monotone on C, then the central path exists. However, to relax the former assumption, notice that-by by the compactness of C-there exists a sufficiently large M such that for any x C, xxx= S M. Thus, one can add strictly convex inequality constraint Qm+1 1 (x) (3x--eg.. e.g. x - MM < 0-and the solution set remains intact. That is, as a tends to 0 the original problem is recovered. This ensures the existence of the central path without changing the original problem.
EXPERIMENTS
Problems. To study the empirical performance of ACVI we use the following 2D problems: (i) cBG: the common bilinear game, constrained on R,+ for the two players, stated in Fig. 1, (ii) Von Neumann's ratio game (Von Neumann, 1971; Daskalakis et al., 2020; Diakonikolas et al., 2021), (iii) Forsaken game (Hsieh et al., whhcc exhibits limit cycles, as well as (iv) toy GAN-used in (Daskalakis et al., 2018; Antonakopoulos et al., 2021). Note that these are known to be challenging problems in the literature, and interestingly the latter three are non non-monotoee, going beyond the assumptions that we made in our theoretical results. We also consider the following higher-dimension bilinear game on the probability simplex, with 1) E (0, 1), n 1000:
min q 11 + (1 - 11) x: x yan x2 A= E E4
R 500 ac; 2 0, and eTT = 13. (HBG)
As GANs on MNIST (Lecun & Cortes, 1998) enjoy well-established metrics, we use this setup and augment it solely with linear inequalities. We implement the baselines with the greedy projection algorithm-ss see App. D.3 for details- hence these baselines will be slower when equality constraints are also given. App. E lists additional experiments, including MaSSI (Xiao et al., 2017).
8

---

Published as a conference paper at ICLR 2023
GDA
RG
OGDA
LAS-GDA
ACVI
(a) Von Neumann's 's ratio game
(b) Forsaken game
(c) toy GAN
Figure Convergence of GDA, EG, OGDA, LA-GDA, and ACVI on three different 2d problems, for fixed number of total iterations, where markers denote the iterates of the respective method.
1300
0000000000000000000000 6000000
Suttler of 3teentiooss
ACVI w/
CPT (3)
40-
EG
ACVI w/
1000
OCDA
10
DG
LA4-DD
ACVI w/ BG
F1D
ACVI w/ BG, ---10
800
20
ACVI
0.0
relative error
10-1
(a) fixed error
(b) rotational intensity
1000
throc (scconde)
Figure 3: Comparison on the (HBG) problem: (a)-CPU time given fixed error, (b)-number of iterations needed reach e-distance to solution for varying intensity of the rota- tional component n)) For both plots, we maximum iterations/time to run. See 5 for discussion.
Figure 4: FID (lower is better) on MNIST with added constraints, over wall-clock time; averaged over seeds. See $ 5 and App. D for dis- cussion and implementation, resp.
Methods. We compare ACVI with the projected variants of the common saddle point optimizers (fully described in App. A.4): (i) GDA, (ii) EG (Korpelevich, 1976), (iii) OGDA (Popov, 1980), and (iv) LAR-GDA (Chavdarova et al., 2021b; Zhang et al., 2019), where is the hyperparameter of LA. For ACVI on MNIST, / denotes the number of steps solve the subproblems; see Algorithm 4.
Results. From Fig. we observe that projection-based algorithms may zigzag when hitting a constraint due to the rotational nature of F, behavior that ACVI avoids because it incorporates the constraints in its update rule; see Fig. 5 for the remaining baselines. Fig. 2 shows that even with problems that go beyond our theoretical assumptions, single step of ACVI significantly reduces the distance to the solution. Moreover, from Fig. 2(b), we observe that ACVI escapes the limit cycles; see also Fig. 6. Fig. 3 shows results for (HBG), indicating that ACVI time efficient, and that ACVI performs well relative to projection rrojection-based based methods for varying rotational intensity (1 - 77), Fig. summarizes the experiments on MNIST with linear inequality constraints; we observe that ACVI converges significantly faster than the corresponding baseline.
6 CONCLUSION
Motivated by the lack of a firsttorderr method to solve constrained VI (cVI) problems with general constraints, we proposed a framework that combines (i) interior-point methods--neddd to be able to handle general constraints- with (ii) the ADMM The combination yields ACV/- a first-order ADMM- based interior point method for cVIs. We proved convergence for two broad classes of problems and derived the corresponding convergence rates. Numerical experiments showed that while projection- based methods zigzag when hitting constraint due to the rotational vector field, ACVI avoids this by incorporating the constraints in the update rule.
to deal with separable objectives.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
TC thanks the support of the Swiss National Science Foundation (SNSF), grant P2ELP2_199744 The authors thank Mattco Pagliardini and Tianyi Lin for insightful discussions and feedback.
REFERENCES
Kimon Antonakopoulos, E. Veronica Belmega, and Panayotis Mertikopoulos. Adaptive extra-gradiemt methods for min-max optimization and games. In ICLR, 2021.
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-Julien, and Gauthier Gidel. A tight and unified analysis of gradient-based methods for whole spectrum of differentiable games. In AISTATS, pp. 2863-2873, 2020.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. In /CML, 2018.
Stephen Bates, Michael I. Jordan, Michael Sklar, and Jake A. Soloff. Principal-agent hypothesis testing, arXiv:2205.0688 2022.
Heinz H. Bauschke and Patrick L.. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2nd edition, 2017. ISBN 1441994661.
Amir Beck. First-Order Methods Optimization. SIAM, 2017.
Radu Ioan Bot, Emnö 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 optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3, 2011. ISSN 1935-8237. doi: 10. 10.1161/2200000016.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Tight last-iterate convergence of the extragradi- ent method for constrained monotone variational inequalities. arXiv:2204.09222, 2022.
Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien Reducing noise in
GAN training with variance reduced extragradient. In NeurlPS, 2019.
Tatjana Chavdarova, Michael Jordan, and Manolis Zampetakis. Last-iterate convergence of saddle point optimizers via high-resolution differential equations. NeurIPS Workshop on Optimization for Machine Learning, 2021a.
Tatjana Chavdarova, Matteo Pagliardini, Sebastian Stich, François Fleuret, and Martin Jaggi. In ICLR, 2021b.
Taming GANs with Lookahead-Ming
Xiaojun Chen, Liqun Qi, and Defeng Sun. Global and superlinear convergence of the smoothing newton method and its application to general box constrained variational inequalities. Mathematics of Computation, 67(222):519-540 1998.
Rune Christiansen, Niklas Pfister, Martin Emil Jakobsen, Nicola Gnecco, and Jonas Peters. causal framework for distribution generalization. arXiv:2006.07433, 2020.
Richard W. Cottle and George B. Dantzig. Complementary pivot theory of mathematical programming.
Linear Algebra and its Applications, 1(1):103-125, 1968. ISSN 0024-3795.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In /TCS, 2019.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR, 2018.
10

---

Published as a conference paper at ICLR 2023
Constantinos Daskalakis, Dylan J. Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. In NeurIPS, 2020.
Damek Davis and Wotao Yin. Convergence rate analysis of several splitting schemes. In Splitting Methods Communication, Imaging, Science, and Engineering, pp. 115-163. Springer, 2016.
Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. COLT, 125, 2020.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan. Efficient methods for structured nonconvex-nonconeee min-max optimization. In AISTATS, 2021.
Jim Douglas and H. H. Jr. Rachford. On the numerical solution of heat conduction problems two and three space variables. Transactions of the American Mathematical Sociery, 82:421-438 1956.
Jonathan Eckstein and Dimitri Bertsekas. On the Douglas-Racchoree Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1): 293-318, 1992.
Francisco Facchinei and Jong-Shi Pang. Finite-dimensional Variational Inequalities and Complemen- tarity Problems. Springer, 2003.
Xiaona Fan and Qinglun Yan. An interior point algorithm for variational inequality problems. International Journal of Contemporary Mathematical Sciences, 5(52):2595-2644, 2010.
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research htt.d//..orrr11..00/////a...a
Logistics Quarterly, 3(1-2):95-110, 1956. doi:
Daniel Gabay. Applications of the method of multipliers 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-1221.
Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. Frank-wolfe algorithms for saddle point problems. In Artificial Intelligence and Statistics, pp. 362-371. PMLR, 2017a
Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. Frank-Wolfe algorithms for saddle point problems. In AISTATS, 2017b.
R. Glowinski and A. Marroco. Sur I' 'apprxximmatin, par éléments finis d'ordre un, et la résolution, par rémalisation-duallis d' d'une classe de problèmes de Dirichlet non linéaires. ESAIM: Mathematical Modelling and Numerical Analysis Modélisation Mathématique et Analyse Numérique, 9(R2): 41-76, 1975.
Roland Glowinski and Patrick Le Tallec. Augmented Lagrangian and Operator-Splitiing Methods in Nonlinear Mechanics. Society for Industrial and Applied Mathematics, 1989. doi: 10.1137/1. 9781611970838.
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-concat saddle point problems. In COLT, pp. 1758-1784, 2020b.
Ian Goodfellow, Jean Abudie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS, 2014.

---

Published as a conference paper at ICLR 2023
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/K) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. AISTATS, 2022.
Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73:957 - 961, 1967.
Bingsheng He and Xiaoming Yuan. On the ((1/n) convergence rate of the Douglas- alternating direction method. SIAM Journal on Numerical Analysis, 50(2):700-700 2012.
Bingsheng He and Xiaoming Yuan. On non-ergodic convergence rate of douglas-rachinn rachford alternating direction method of multipliers. Numerische Mathematik, 13003):567-577, 2015.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to local nash equilibrium. NIPS, 2017.
Ya-Ping Hsieh, 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.
Martin Jaggi. Revisiting Frank- Wolfe: Projection-free sparse convex optimization. In ICML, volume 28, pp. pp. 427-435. PMLR, 2013.
Galina Michailovna Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 1976.
Ivan Kupka. Contributiona á la théorie des champs génériques. Contributions to Differential Equations, 2:457-484, 1963.
Simon Lacoste-Julicn and Martin Jaggi. On the global linear convergence of Frank--ooll optimization variants. In NIPS, 2015.
Yann Lecun and Corinna Cortes. The MNIST database of handwritten digits. 1998. URL http: 1/lyannneecut com/ exdoo / ///mmmissss it./
Tianyi Lin, Shiqian Ma, Yinyu Ye, and Shuzhong Zhang. An ADMM-based interior-point method for large-scale linear programming. arXiv:185.11234. 2018.
Zhouchen Lin, Huan Li, and Cong Fang. Alternating Direction Method of Multipliers for Machine Learning. Springer, 2022.
P. L. Lions and B. Mercier. Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6):964-979, 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 NewrIPS, volume 33, pp. 302-312. Curran Associates, Inc., 2020.
Nimrod Megiddo. Progress in Mathematical Programming: Interior-Point and Related Methods. Springer-Verlag, 1989, ISBN 0387968474.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and op- timistic gradient methods for saddle point problems: Proximal point approach. arXiv: 190.0851, 2019.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence rate of O(1kk) for optimistic gradient and extra-gradient methods in smooth convex-concar saddle point problems. In SIAM Journal on Optimization, 2020.
Renato DC Monteiro and Jong-Shi Shi Pang. Properties of an interior point mapping for mixed comple- mentarity problems. Mathematics Operations Research, 21(3))629 1996.
12

---

Published as a conference paper at ICLR 2023
Yurii Nesterov and Arkadi Nemirovski. Interior enterior-point polynomial algorithms in convex programming. In Stam Studies in Applied Mathematics, 1994.
Yurii Nesterov and Michael J. Todd. Primal-dual interior-point methods for self-scaled cones. SIAM Journal on Optimization, 8:324-364 1998.
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.
Shayegan Omidshafiei, Jason Pazis, Chris Amato, Jonathan P. How, and John Vian. Deep de- centralized multi-task multi-agent reinforcement learning under partial observability. In ICML, 2017.
Jong-Sh, Shi Pang. A posteriori enror bounds for the constriee variational inequality problem. Mathematics of Operations Research, 12:474 484, 1987.
Leonid Denisovich Popov. A modification of the arrow hurwee method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845-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 non- linear complementarity problems and box constrained variational inequalities. Mathematical Programming, 87(1): 1-35, 2000.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. In ICLR, 2016.
Daniel Ralph and Stephen J Wright. Superlinear convergence of an interior-point method despite dependent constraints. Mathematics of Operations Research, 25(2):179-11) 194, 2000.
James Renegar. A Mathematical View of Interior-Poine Methods in Convex Optimization. MPS- SIAM Series on Optimization. Society for Industrial and Applied Mathematies, 2001. ISBN
9780898715026.
Ralph Tyrrell Rockafellar.
Monotone operators associated with saddle-functions and minimax problems. Nonlinear functional analysis, 18(part 1):397-407, 1970.
Dominik Rothenhäusler. Nicolai Meinshausen, Peter Bühlmann, and Jonas Peters. Anchor regression: heterogeneous data meets causality. ArXiv:1801.06229 2018.
Ernest K. Ryu and Wotao Yin. Large-Scale Convex Optimization via Monotone Operators. Springer Publishing Company, Incorporated, 2022.
Tim Salimans, lan Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. In NIPS, 2016.
Stephen Smale. Stable manifolds for differential equations and diffeomorphisms. Annali della Scuola Normale Superiore di Pisa-Classe di Scienze, 17(1-2)977-116, 1963.
Guido Stampacchia. Formes bilineaires coercitives sur les ensembles convexes. Académie des Sciences de Paris, 258:4413-4416. 1964.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. 132.:913 2014.
Paul Tseng. A path-following algorithm for linear programming using quadratic and logarithmic penalty functions. SIAM Journal on Control and Optimization, 31:1578-1598, 1993.
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.
13

---

Published as a conference paper at ICLR 2023
A.M Rubinov V.F Demyanov. Approximate Methods in Optimization Problems, volume 9. American Elsevier, New York, 1970.
Jean-Philippe Vial. Strong and weak convexity of sets and functions. Mathematics of Operations Research, 8:231-259, 1983.
John Von Neumann. Model of General Economic Equilibrium. Palgrave Macmillan UK, 1971. ISBN
John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1947.
Chen-Ye Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In ICLR, 2021.
Stephen Wright. Primal-Dual Interior-Points Methods. SIAM, 1997.
Stephen Wright. Lectures on Modern Convex Optimization, Analysis, Algorithms, and Engineering Applications. SIAM, 2001.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for bench- marking machine learning algorithms, 2017.
Michael Zhang, James Lucas, Jimmy Ba, and Geoffrey Hinton. Lookahead optimizer: k steps forward, step back. In NeurlPS, 2019.
14

---

Published as a conference paper at ICLR 2023
A
BACKGROUND: ADDITIONAL DETAILS
This section lists additional background such as omitted definitions and description of the used baseline methods.
A.1 ADDITIONAL VI DEFINITIONS & EQUIVALENT FORMULATIONS
Seeing operator F X' R the graph GrF {(x, y)( X, F(x)). }. its inverse F-1 is defined as Grl = {y (æ y) E GrF). See, for example, (Ryu & Yin, 2022) for further discussion. We denote the projection to the X' with 1lx.
Definition -cocoercive operator). An operator F 2 R is -cocoercive (or -inverse strongly monotone) on S if its inverse (graph) F-1 is p-strongly monotone on S, that is, P
3u O, s.t. (x- - (((()))F(=))) 2 2 (l))())= F(x')ll² Vx, x' S. is star 1 cocoercive if the above holds when setting x' xx where x' denotes solution, that is:
Fu 0, s.f. (ar - x,, F(x:) F(x*)) 2 1 (())) F(**)| Vor E S, xt Sx
Note from Def. that cocoercivity is a strict subclass of monotone and L-Lipschitz operators, thus is it is stronger assumption. See Chapter 4.2 of (Bauschke & Combettes, 2017) for further relations of cocoercivity with other properties of operators.
In the following, we will make use of the natural and normal mappings of an operator F: 2 - R where X' T Following the notation of (Facchinei & Pang, 2003), the natural map NNTT, X - IR. is:
FAAT & x Ixx( (x - F(x)).
Vo X
(F-NAT)
whereas the normal map FNORR T R is:
NOR & F(Ixx())) x (xx(x,
Va E R".
(F-NOR)
Moreover, we have the following solution characterizations:
(i) x² &Sx
iff
PNAT (x*) = 0, and
(ii) x² E Sx.F iff Fr R s.t. x Txx(x') and FNNOR
Remark 4 ("rotational" component of the vector field). The rotational trajectories parameter space induced by the fact that the eigenvalues of the Jacobian of the vector field F (the second- order derivative matrix) belong to the complex set C; that is >3 E contrast, when F = f the second-order derivative matrix known the Hessian is always symmetric, and thus the eigenvalues are real.
A.2 EXISTENCE OF SOLUTION
We provide brief informal summary of some sufficient conditions for solution existence, that St A See Chapter 2 of (Facchinei & Pang, 2003) for a full treatment of the topic.
The common underlying tool to establish that solution to the VI(X' F) problem exists is using topological degree. The topological degree tool is designed so to satisfy the so-called homotopy invariance axiom, which turn allows for reducing solution existence question of a complicated map to simpler one (which is nomotopy-invarian show that has a solution (e.g., the identity map on a closed domain). can be used (as one way) to prove the celebrated Brouwer fixed- fixed-point theorem, which states that any continuous map $ S - S. where S is nonempty convex compact set, has fixed point in S.
the original one) for which we more easily
We have the following sufficient condition,
(Cor. 2.2.5, Facchinei & Pang, 2003)
Theorem 4 (sufficient condition for existence of the solution, Cor. 2.2.5, (Facchinei & Pang, 2003)).
If X C Rd is compact and convex, and F X' + R is continuous, then the solution set is nonempty and compact.
15

---

Published as a conference paper at ICLR 2023
It can also be shown that when X' is closed convex (and F continuous), if one find x' X s.t. (F(z), - =x') 2 O, vo E X, then Sx.F * 0.. The same conclusion follows if one can show that Fa' E X' and the set {a E (F)), x x²) < 0} is bounded (possibly empty, see Prop. 2.2.3 in (Facchinei & Pang, 2003)).
Sufficient conditions can also be established via the natural and the normal map due to the above solution characterizations. In this case, we require that F' is continuous on open set S and are interested if S2, + 0, where X' is assumed closed and convex and subset of S, X' C S. If one establishes that solution exists for F on bounded open set U1 and if cl U [ S, then it follows that Sx F * 0. A similar implication holds when we have such a guarantee for F See Theorem 2.2.1 of (Facchinei & Pang. 2003).
In summary, the solution existence guarantee follows from the boundness of some set which includes X. the boundness of the set of potential solutions (if we can construct such set), or the compactness of X' itself.
A.3 EXISTENCE OF CENTRAL PATH
In this section, we discuss the results that establish guarantees of the existence of the central path. Let [(x, X, v) A F(z) + V + Ctv, h(x)) = C d. For (X, w. x. v) E mm++++ let
X w + (pxr) L(xr,.,) X. h(xx)
G(A, w. 21)
E 2m
and
w + x+(x L(xx X v) h(x)
H(A, 2,) &
R mmtntp
Let H++ HR x R" IRP. By (Corollary 11.4.24, Facchinei & Pang, 2003) have the following proposition.
Proposition (sufficient condition for the existence of the central path.). F is monotone, either F strictly monotone or one of iss is strictly convex, and bounded. The following four statements hold for the functions G and H:
1. G maps 122m Ru+p homeomorphically onto RT+ H44;
2. RT x H++ S G(R2m x B=+t));
3. for every vector Ry, the system
H X, w, x. D) = 0,
w o X a
has a solution (X, w. v) E 2m2m x Ru+p; and
4. the set H is convex.
A.4 SADDLE-POINT OPTIMIZATION METHODS
In this section, we describe in detail the saddle point methods that we compare within the main part (in $ 5). We denote the projection the set X with TTx, and when the method is applied in the unconstrained setting II I.
For example of the associated vector field and its Jacobian, consider the following constrained zero-sum game:
min max f(11,
(ZS-G)
16

---

Published as a conference paper at ICLR 2023
where : X2 + R is smooth and convex in 21 and concave in 22. As in the main paper, write _ (2), E _. The vector field F: X + _ and its Jacobian J are defined as:
V f()) (zzf(w)
V ((x) J(z)= = Vai f
Va (a, f
F(x)= =
In the remainder of this section, we will only refer to the joint variable a, and (with abuse of notation)
the subscript will denote the step. Let?? [0, 1] denote the step size.
(Projected) Gradient Descent Ascent (GDA). The extension of gradient descent for the cVI problem gradient descent ascent (GDA). The GDA update at step l is then:
1k+1
xI (æ (axx))
(GDA)
(Projected) Extragradient (EG), EG (Korpelevich, 1976) uses "prediction" step to obtain ex- trapolated point #E-z using GDA: Tx+ = =Ixx - -FF(Fx))))))))))))>)))))>)))>})) and the gradients at the extrapolated point are then applied to the current iterate æy:
x++1= Ts. 1
yF [Ix (1x -FF(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 5 (Korpelevich (1976)). Given map F :. + R", the following is satisfied:
1. the set X is closed and convex,
2. F single-valued, definite, and monotone on X-as per Def. I,
3. F is L-Lipschitz-as per Asm. 1.
then there exists solution x' E X, such that the iterates 2 produced by the EG update rule with fixed step size 7 E (0, 1) converge to that 24 - xx" as k - 30.
Facchinei & Pang (2003) also show that for any convex-concave function f and any closed convex sets E X and 22 E X2, the EG method converges (Facchinei & Pang, 2003, Theorem 12.1.11).
(Projected) Optimistic Gradient Descent Ascent (OGDA). The update nule of Optimistic Gradient Descent Ascent OGDA (OGGDA) Popov, 1980) is:
In+1
11x FTF()n) + +=F((xnn))
(OGDA)
(Projected) Lookahead-Minman (LA). The LA algorithm for min-max optimization (Chavdarova et al., 2021b), originally proposed for minimization by Zhang al. (2019), is general wrapper of a "base" optimizer where, at every step t: (i) a copy of the current iterate कn is made: on + En. (ii) æ,, is updated & > times, yielding Wa+k, and finally (iii) the actual update 0,+1 is obtained as a point that lies on a line between the current on, iterate and the predicted one Entsi
#n+1 <- In. + a(Ān+k vn).
[0,
(LA)
In this work, we use solely GDA as base optimizer for LA and thus denote with LAk-GDA.
The projection-free Frank-Wood Wolfe (FW). FW (Frank & Wolfe, 1956) is an IP-type method for solving constrained smooth zero-sum games (ZS-G). It avoids the projection operator by ensuring we never leave the constraint set. To do so, it finds the intersection points of the inequality constraints- requires that the inequality constraints satisfy certain structures (such as linear) in order for this operation to be computationally cheap. We state FW for zero-sum games in Algorithm 2 as proposed by Gidel et al. (2017a, Alg. 2) for completeness. It requires access to a linear minimization oracle (LMO) over the constraint set-to minimize the linear function in line 5 in Algorithm 2. Currently, FW-style algorithms only have convergence guarantees when the constraint set is polytope ((Gidel al., 2017a)) with additional assumptions (which listed in $ 2.
17

---

Published as a conference paper at ICLR 2023
Algorithm 2 Frank-Wolfe algorithm for zero-sum games.
1: Input: C,v> 0
2: Initialize: 20) (a) (0)
E 21 X2
3: for = O,..., T" do
f(al
(1)
4: Compute (())
22
[ac (1) ,002
(
5: s(1) a 2 x(1)
6: Compute 9t (2(0) 811), ml())
7: if' ge S then
8: return 2())
9: end if
10: Let min (1, V 91) or y 2
2c
2+6
Update z(+1) (1 - 7)2(1) + 77((0)
12: end for
18

---

Published as a conference paper at ICLR 2023
B OMITTED PROOFS AND DISCUSSIONS CONCERNING ALGORITHM
This section provides the proofs of the theoretical results in $ 4.2.
B.1 PROOF OF THEOREM 1: UNIQUENESS OF THE SOLUTION OF EQ. W-EQ
Recall first that Eq. W-EQ is follows:
+ B P(F(m)) Pay +
1
1 P.dx de =0
since ur D.
Proof of Theorem I: uniqueness of the solution of (W-EQ). Let G(æ)) denote the LHS of (W-EQ), that is:
I P. - de
G( - x = PoF(w) Payk + 3
We claim that G(x)) is strongly monotone C=. In fact, Vz, C=, Po( y) y. Note that Pe is symmetric, thus we have:
(G(zz) Gly), x y) =1 y| + (P.((x) P y)
3
= =| yl
+
B (x F(x) F(y))
2 | y ?
Therefore, according to Theorem 2.3.3 (b) in (Facchinei & Pang, 2003), St_ G has a unique solution C_. Thus, we have:
(x - a) = O, Va E C=.
From the above, deduce that G(m)) E Span {cr, Cpl, where e₁ is the row vectors of C, E [p].
Suppose that G(Ø) Dim o;e, Notice that CG(x)) 0, Vo e C_. Thus, have that:
c)G(T) = cj Σ
a,c = 0, Vj Vje lp].
i=1
Hence,
(G(#), G()) = Σ O2C
0:c+ = 0,
which indicates that G(ø) = 0. Hence, ø is solution (W-EQ) in C_.
On the other hand, Vz e R", if æ is solution of (W-EQ), i.c G(æ) 0. then C_. By the uniqueness of ë in C= we have that x = ã, which means e is unique in R=.
B.2 PROOF OF LEMMA 1: UPPER BOUND ON THE GAP FUNCTION
Proof of Lemma 1: Upper bound on the gap function. Let a. denote iterate produced by Algo- rithm 1, and let x E C. Note that we always have 23 E C=. We have that:
(F(*)), Dg x) = (F(x"), ) - x) + (F(xx), Dt. x) (F(x"), x)
((F(*)), x) (F(*x), Ft xx + x) (F(x") x² x)
From the proof of Theorem we know that 3e bounded, which gives: (F(xxx, Dg x²) S
M ||, x:" []. with M > 0, as well as that { (F(x)), ), x² - x)) < 0. Thus, for the above we get:
(F(xx) vt x) < (F(xx) - F(x*), x² x)) + - || x'1
< D F((s)) - F(x*)l | M 2 x=1|
< (DL + M) || x=')
19

---

Published as a conference paper at ICLR 2023
where for the second row used x" I D where D ف max || -x'| is the largest distance between any point in C and x". For the last row we used that L-ipsschitz Assumption !-which concludes the proof.
The proof is analogous for the ys Cg iterates produced by Algorithm
B.3
PROOFS CONVERGENCE RATE: THEEREMS 2 AND
Let
(0)()) & F( 1(Cx = d),
(x) (x) - F( Tx + 1CCx = d).
(0) (y) F4
log p:(y)),
where a is solution of (KKT-2) when μ = Maa. Note that the existence of a is guaranteed by the
existence the central path-see App. A, and that f p(t) and g(t) are convex.
In the following proofs, unless causing confusion, we drop the subscript to simplify notations. Let y" xx" from (KKT-2) we can see that (xx ,y") is an optimal solution of
min [xx + +gy) s.t. -==9 y
There exists A E IR such that (x* y" X²) is KKT point (4). We give the following proposition which will repeatedly use in the proofs:
Proposition 2. If F is monotone, then vk N,
[x( Su(x* 2 / ((B++1) ((x!))
Furthermore, if F is E-monotone, per Def. 1
fe((x+1) fx((x") 2 f(0x+1)) f(x*) c||xx41 - x=1
Proof of Proposition 2. It suffices to note that:
fx( fa(x=) (f(xx)1) f(x*)) = (F(x*+1) F(x*)) xx)).
Some of our proof's that follow are inspired by some convergence proofs in ADMM (Gabay, 1983;
Eckstein & Bertsekas, 1992; Davis Yin, 2016; He Yuan, 2012: 2015; Lin et al., 2022). How- ever, although Algorithm adopts the high level idea of ADMM, we can not directly refer to the convergence proofs of ADMM, but need to substantially modify these.
We will use the following lemma.
Lemma 2. (xx + g(v) f(x -( + (A*, x y) 2 Var y.
Proof. The Lagrange function of (4) is
L(x, y. A) = f(x) + ((y) + AT y)-
And by the property of KKT point, we have
L( nd A) < L(xd" A²) (,),, V(x,,,)),
from which the conclusion follows.
20

---

Published as a conference paper at ICLR 2023
The following lemma is straightforward to verify: Lemma 3. If
f(z) + f(x")) - -3(2)) ) + (A* a - y) S an
x yl S 02
then we have
| S f(x) gly) f(x²)) "(="))"(("" p(v") S || + a1
The following lemma lists some simple but useful facts that we will use in the following proofs.
Lemma 4. For (4) and Algorithm we have
0 0f (xx+1) + A + 3(xx+1 yk+1)
(5)
O 0g(yk+1) A - 3(xx+1 yk+1),
(6)
Ak+1
A 8(0k+1 -1k+1),
(7)
0 E 0f(x") + +X",
(8)
0 0g(n") -X x" = =y"
(9)
(10)
We define:
[u( -
yk),
(11)
(9(8)+1) & d 3(xx++1 yh+1)).
(12)
Then from (5) and (6) we can see that
(x(441)) E (fx())+1) and (g(3k+1) E 0g(wk+1))
(13)
Lemma's S. For Algorithm 1, we have
(Vg(yx+1) Mk+1 y) = -Ax+11 yot2),
(14)
and
V (2(4411) - x) + (Vg(3)+1) 3 y) 3k+1
(15)
(AR+1: 0s41 yk+1 x 8) + B( yk+t + yks xx-1 - x).
Proof of Lemma 5. From (7), (11) and (12) we have:
(o xk-1 - xx)
(Ax + B(xk+1 -y%), 21,), 2x+1
x))
(A++1, #841 - x)) + 1-( yl+t1 + yk., 2x+1 xx);
and
(Vg())+1)) 9x+1 y) (Au+1. -ytt1) Adding these together yields (15).
Lemma 6. For Algorithm 1, we have
( (xx++)) Bb++1 x²) (Vg(y)+4)) 36+1 -y") (X" 2x+1 vot1)
A 111112-
| - 111
28
233
B
Ily
11
1ly" yk+ill 112
2
1
3 yy yk+1l 2
A
Ax112 2
2,3
21

---

Published as a conference paper at ICLR 2023
Proof of Lemma 6. Letting (z: y.
(x".y" in(15), adding (A", 2x41 yk+t) to both
sides, and using (7) and (10), we have:
(V LA (xx+1), Bh++1 - xx") + (Vg(y)++)) 9k+1 y") + (x" #x+1 - yktt)
(AR+1 X", 20x+1 - yk+t) + B( -1- 4k+ yk 3k+11 x²"))
B (A++1 X", \ - Aa) + y-y++1 + yk. A++1 - X1)
D9(-yk+1* + Uk: -/++1 + y²
(16)
1
1
1 | Axel
A -11112
| A²122
28
2,3
2B
B
13
13
yk + y²11 2
yk+1 + 11
y²112
-k++1 + yx11?
2
2
+( yk+1 + yk. ARt1 - Ab)
(17)
On the other hand, (14) gives
(V)())) ya y) + (Ai, yk + y) 0.
(18)
Letting y yı in (14) and y yk+1 in (18), and adding them together, have:
(Vg(D++1) Vg(y)), yk+1 yk) + (Au+1 AAs- yk+1 yu) 0.
By the monotonicity of Ög we know that the first term of the above equality is non-negative. Thus, we have:
(A Au. 1k+1 + yn) S 0.
(19)
Plugging it into (17), we have the conclusion.
Lemma 7. For Algorithm 1, we have
f(xx+1) + g( - -(xx') g(v") + (A"
(x411 0b41 31411
1
|Ag 2-112-
| 2
2/
2/
3
B
11yyk + yn11
11-yyks
yk+1 + 11111
2
2
8
|4+11
2b112
yk+1 + 11
(20)
23
2
Furthermore, F is E-monotone on C., have
cl Øk+1 201 + f(x2+1) + g((x+1)) f(x") - -g(0)) + (A", Øx+1 - -2++1)
1
A
21112
D 11112
23
2,3
1
8
11 Bk + 122
Yk+t + 112
2
2
|A-1
11112
-
- Yo+t + y
(21)
23
22

---

Published as a conference paper at ICLR 2023
Proof. From the convexity of (z) and g(y) and using Proposition 2 and (13), we have f(0x+1) + (( f(=") - g(y") + (X" ak+1 yk+1)
<.4 + ((v++1)) - /x(x") s(y") + ax+1 yk++1
0x++1
(V (2 1), 0k+1 x0th (Vg(y)++)) yk+1 -/")
AA #k++ - y/++1)
1
Ak+1 111
(22)
23
2
13
Yb + y²11
11 1-+++11 + y²11
2
2
AR+11 -
Ao11
2
-1 + yk
23
F is É-monotone on C=, again by Proposition 2, we can add the term c||0a+11 x012 to the first line and the inequality still holds.
Theorem 6. For Algorithm I, we have
f(x++1) - f(x")) + g()++1) g(y") 0,
fu(#x+1)= - fa(x")) + g(y++1) - g(y") + O,
Ik+1 yk+1 O,
as k cc. Furthermore, if F is g-monotone on C=, we have
Fk+1 -> x", + 00
Proof of Theorem 6. Proof From Lemma 2 and (20), we have
1
B
Ac+1
Ax112
yk++1 + 91:12
2/3
2
1
A₂
1²112
AR+1 - 1111
(23)
23
2/
8
3
11yyk
yk + y²11
yk-1 + 3"11
2
2
Summing over l: == ..., 00, we have
20
A
Ax + 201 1k+1 + yalll
11
2
k=U
1
AA
1²112
2 Yo 11
8
2/3
from which we deduce that AR+1 A + and - + + y/k - 0. Moreover, || A - 11112 and
||-yk yk + 1 are bounded for all k, well as || ||| Since
A A 3(xx+1 yk+1) (xx++1 x² + 1--3((0++ yk+1 + g
we deduce that #1+1 yk+1 + O and mx+1 - x is also bounded.
From (15) and the convexity of and g. and using Proposition 2, we have:
f(xx=1) fxx") (( g(y") [fv(2)+11 fu fxx + g(vx+1) - -g(3")
S (A++1, 2x+1 yk+1) Bi- + yk 36+11 x²) 0.
On the other hand, from (8), (9), and (10), we have:
fk (xx+1) - fir (xx") + 9 (yk++) )- - (1
2 (xx+1) - (xx))= + +g (H++1) -9 (3 2(-X", 0z+1 2,+1 - x²1 + (A ys+t 8r)
(A", 4k+1) + 0.
23

---

Published as a conference paper at ICLR 2023
Thus, we have f (2x-1) - f (a*) + (3k+1) (g (3)" - and fir (Ix+11) fu (xx") + +g (yx+1)
9 (33") + 0 00.
If F is m-monotone on C=, from Lemma 2 and (21) we have
A1 112 + 3
c| 2k| 201 +
A
-1 2k-1 11-9k-1
yk 11
2
2
1
A - X=112
(24)
2B
2/3
8
13
+ -1-y: yı + v²1
yk+1 + 1
From this we deduce that:
Axl1 + B Act1
cl|
x=11. + Σ
2 211- yk+1 + ykll?
23
k=0
3
A 2111 +
y + 1
23
2
Therefore, | 20"122 + 0, + 0o.
Lemma 8. For Algorithm 1, we have
Ast1
Avl12 + 2 1 11
yk++ + y
23
(25)
8
23 ||
-1
211
=11-y
yk + y
Furthermore, if F & E-monotone on C_, we have
3 11yykt+1
c| c| 22x11 +
| - Ael12
+ 2
yk+1 + yk 12
23
(26)
1
<
AAs
-x=1112
-
1
Yi yk-1ll
23
Proof of Lemma 8. (15) gives:
V fK-1 (xR) 1 D3 xx) + ( (yr) y) 4)
(27)
(Ae, Bs -Yk x + 3) + B( yt + 3/-1, x)
24

---

Published as a conference paper at ICLR 2023
Letting (z. y, A) (#) yk: 2&) in (15) and (z, y. A) = (Ix+1) 4k++1 Ac+1) in (27), and adding
them together, and using (7), we have
fa (IN+1) f (zx): Ib+1 xx)) + (Vg (yk 4 (B1L) yk+1 - yk)
(A++1 Xx, x++11 4k++ 3k + yv) + (3-- yk++1 yv y- + yk- 0x++1 2Tk)
1
= 3 (AR+1 Ax+1 Ax= (Ax Ab-1))
+(- 1-++++1 + yy: + +3yk 14--1) 1). A8+1 A + +Byk+1 (> \ Byx))
2B [lIA 1121/12 || || AaI1 - -||R++1 - AE= - (Ai- - -
B
+
[|| [1-ykk yk + yk 1| 112 1k-1 + yx11 || 1k-1 + yk - (- + +yk-1)1
2
+(- 4k+1 + yv (- yk + yk 1), AR+1 - Au (As (k-1))
1
|x++ An 11) + 3
28 (1AA- 1111 112
(1-9)s yk - 11 || 11y++11 + 3x
D A - (Ax - x
-/1 yk++1 + yv (-y
yx +
y)1?
2B
2
+(- yk+1 + yk - (-y + yk-11 Ax+1
2x= (Ax A 1))
1
3
(l 1 1|2 - | AR 12)
+
(1- yk + yk- || Ds+1 + 3xll
28
By the convexity of fx and fk-1, we have
(V (Ix+1) , xx+1 - xT) (xx+ - fx(()))
1i (Ix) 3++1 [x+11
xτ) (xx) f4- (
Adding them together gives that: fu (Ix+1) V f (Ix) xb+1 xxx) 2f((Ix+1) - fo-1(1041) - -x((x)))))( + f
=(F(xx+11 F((x)) xx+1 IT) 2 0.
Thus by the monotonicity of F and &g. (25) follows.
Theorem 7. If F is monotone on C_, then Algoritium 1, we have
AH
-11X"ly
Sf (x + + (BK+1)) (xx") - 9 (3²")
3 (K +1)
Sfk (IK+1) + (BK+1) fA (20") - (zy
(28)
A"
2A"
Au
< K -1 +
VK +1 + 11A11 V 3(K +1)
A
|0 - 9K+1ll S
(29)
V ([KKK -1)
where A A A 1'o 2x112 + Blyy0 - 1
Furthermore, if F is E-monotone on C.. we have
A
c||0x+1- - 10 S
(30)
K 11'
A
2A"
c||0x11 - xn1 5
(31)
K +1
K +1
where 0 K4I _k=1 K.K.
K+1
25

---

Published as a conference paper at ICLR 2023
Proof of Theorem 7. Summing (23) over k I...., K and using the monotonicity of 23 A
A
1 + 8
1-++++ + yx from Lemma 8, we have:
1
|AK+1 >x|12 2 + B|| yk+1 + yxll K+1
2=112 -
311 yo + 1111²) (32)
From the above we deduce that
3A"
3 B| 1K++1| ||Ax=1 Ax| 1 V
(K 1)
An 1/88/ (KKK+ +1)
IK + 5
On the other hand, (23) gives:
1
8
Ak+1
x=122 +
yk+1 + 112
23
2
1
1 + 2
8
1 yı + y
2,3
1
Ao
1112 +
8
-
11-
1 D0 + y01 Ar.
2,3
Hence, we have:
|AK+1 - A S v /BAm.
(33)
1K rd s
(34)
Then from (16) and the convexity of f and g. we have:
/ (œ - / (xx") + y (I g (n)) + (A* 0x+1 yK+1)
S fk (IK+1) fK (xx*) g (vk+1) (y") + xx+++ 9K41)
|AK+I - X² [*II|A+++ - Axll + 11 + yk ||| Axll B
(35)
+ yK+1 yk [1lyyKK+ -K+1++++" +
A +
2A"
K1 VI+I
From Lemma 3, we have (28).
If in addition F is E-monotone C=,, using (24), we can obtain the following inequality similar to (32):
EK
|F 11
k=
+ ||
A 111 yK+1 y
K+1
< K +1
Ao 2² -11- 831113
By the convexity of 11 we have c|lēk+1 - 1011$ S K+I. And from (35) we can see that c|æøк1 - =011 <
A 2
K+1 VK+T
Theorem 8. If is monotone on C_, then for Algorithm 1, we have
AP
+ 2/3A" |
(+x+1) + (ŪK+1) (xx" 1 900099(/0) (3")) < 2(K +1)
B(K +1)
2/3A"
| ~x+zll
(36)
B (K + 1)
1 K+1 where #x+1 K4I Lk=1 Kk. ÿK+1
K4I k+1 yk. and A A 11120 1 +/3l
y*1
26

---

Published as a conference paper at ICLR 2023
Proof of Theorem 8. Summing (20) over k = 0, 0....... K, dividing both sides with K + 1, and using the definitions of ø+1 and ØK+1 and the convexity of and 9, we have
A"
f0 + (9K+1) f (x") (3)") + (A", ØK+1 9K+1) S
2 2(K +
From (7) and (33), we have:
1
0K-I DK+1ll
(kx+1 AR)l
3K + +1)
k=0
1
|A Xo1l
(K +
1
(11A0
- X*I)
(K +1)
2v 2/BA"
3 +1)
Finally, from Lemma 3, the conclusion follows.
From Proposition I and the fact that C is compact we can see that lim x" and lim X exist and are
p-0
P-0
finite. Let x:' lim ae and A lim AH, then x² E St,F- 100
Theorem 9. Fd > 0, S.l.
if Pe < is then
x*)|
S
2
A"
K+I
24"
+ | Il B(K+T)),
F(x*)T(<k)) x*) < 2( A"
+
VK+T + |1^
21t
Ar B(K+i)
and
VK+T
K+I
F(xt)T(2())
(1) x²) (2(())
A" 2 AK 2 0. B(K+1)
[+1
Proof of Theorem 9. For simplicity we let B(x) denote the log-barrier term From Theorem and we have
Ee (o)(-)(((x))
F( K+1 x²) + ((B(U B(
((m - -(x") + g( - -9(8
A
2Aa
Av
K K+ VK + +11011|
(37)
B(K +1)
F F( K+1 - x²) + +1(B(y (t) B(y
+
[k(2)+t) - fx( + (0) - -((0))
A" 2A"
A
K+1 +I+ + ||-
(38)
3 B(K+1) 11)
F( (1)
K+1 x²) + ((B(OR)))) B(y
-(s(0k))) - -f(x)) + + (0(0)))))))))))))))))))))))))( -
A
2/34-1>>11
(39)
2(K +1K+1)
B(K+1)
27

---

Published as a conference paper at ICLR 2023
From Proposition 1 in App. A we know that when j 0, a0 B(y")) O, Fip 0, s.t. ue ji, then have
x, X
A and ((B(yk++) (6)
A
2
A"
(0 1 2
11
K
VK
+1
3(
+1)
(1) (( - 2 52
A"
2A"
||-1|
A
K +1
VK +1
(KK +
A
2/32
F(x*)T(*++) x²)
2
+
2 +1)
BK
+1)
To make the dependencies of the constants clear, here we restate Theorem 2 and Theorem 3 and provide their proofs.
Theorem 10 (restatement of Theorem 2). Given an operator F X R" monotone on C= (Def. 1), and either F is strictly monotone on C or one of qi is strictly convex. Assume there exists
T. 0 or s >> 0 such that F is star-E-monotone- as per Def. l-on either Ć, or C., resp. Let
A 1 - 11 + Bl y²
Let æK and &x
E (t) denote the last and average iterate of Algorithm 1, respectively, run with sufficiently small p- Then there exists Ko E N, Ko depends on r or 8, s.l.K K for all L E [T], we have that:
(6)
1= 2
1. || (6)
S
24 VK
+
A +
155
BR
If addition E-monotone on Cz, we have 1
x11 S (24) 1/E
Moreover, if F is L-Lipschitz on Ca-as
as per Assumption 1- then ( C)) S Mo ( +
24 VR
/ BK M) and ( (t) C) Mo o(K-1)
1/E
where Mo DL + M is linear function of L, the proof of Lemma I in App. B.
Proof of Theorem 10. Without loss of generality, we suppose that F is star-E-monotone on C, Since you (by)) S from (29) we can see that 3gg N, Kg depends on r, s.t.K 2 Ko: ag E Cr. so if (ū. is defined in Theorem 9), by Theorem 9 we have
cla2211 K+1
11 < (F(* F(xx) [) (2r K+1 - x*)
< (T(==)T((()) (1)
(
K+1 - x²))
+ (( (30 x*))
A
2A
A
<4
||*0||
K+1
VK +1
3(K
So we have
1/8
2A
A
|| x11| <
+
+
||*
K
+1
VK+I
3 (K
+1)
If in addition F m-montoone C=. then from (30) know that when ja is small enough, we have
2A
1/8
| K+1
2:
o(K +
28

---

Published as a conference paper at ICLR 2023
If F is L-Lipschitz C=, then from Lemma
1 that
1/E
A
2A
A
g(*k (8) C) - Mo
+
+ 11
K+1
VK +
3(K +
1)
24
1/E
10 C) & Mo g(
c(K +1)
Theorem 11 (restatement of Theorem 3). Given an operator F X RR. assume: (i) is monotone
on C=, as per Def. 1; (ii) either F is strictly monotone on or one of oi is strictly convex; and (ii)
inf F (x)
a > O, where S Cr or C.. Let A E1120 - X1 + Blyo y I12
---
Let okK and ax
(t)
- K 1 Ty
&
(1) denote the last and average iterate of Algorithm respectively,
run with sufficiently small n-1- Then there exists Ko E N, Ko depends on or 8, s.t.vt E [T].
RK > Kg, we have that:
1.
K x²
(3)
24 VK +
+111
A DR
If in addition
inf (=*)
F(xx')
F F- -----
b 0 (with 5 = Cr or Eo). then | - s
A
11
2K
3K
3. Moreover, if F is L-Lisschitz on C. Ca as per Assumplion
Ithen gl S
2
VK 2A + +11
and ( (1)
K C) <
2Mg
A
2VBA
BK
2K
3K
where Mo = DL + is a linear function of L, see the proof of Lemma I in App. B.
Proof of Theorem II. Without loss generality, we suppose
inf
F (xx)
|---01||
a
oEC,Ma)) When K Ko (Ko and jt are defined in the proof of Theorem 10 and in Theorem 9, resp.). by Theorem we have that
(( - x*)|
a 1 K+1 - x $
2
A
2A
A
+ +11771
K K+1
VK +1
3 (K +1)
Similarly, if inf F( aEdr)(wr)
x-wx x
b > 0, we have that
2 3A X
||0/t
x+1 5 b
K+1
2(K +1)
3(K
+
If F is L-Lipschitz on C_, then from Lemma 1 can that
0(x
2Mo
A
2A
|
A
a
K
VK
+1
3(K +1)
2M
A
g K
(t)
C)
2(K
+1)
(1)+)
From the above proofs, we can see that by setting 1 small enough, Theorem and 3 hold true. But since do not know exactly how small μ should be, in practice, small /-11, and
29

---

Published as a conference paper at ICLR 2023
Hu could be smaller than any fixed positive number after very small number of outer loops, Pa decays exponentially. Thus, Algorithm is actually parameter-free.
Note that the assumption (iii) in Theorem is the weakening of the assumption in F(xx)T =
w-#" ||0-001| O, where S C, C.. In fact, by the monotonicity of F,
have (x x²) 2 T( x²), so if inf F( xES\
---2-| 0, there must be
in. F(a))T 20-00 > 0. =ES((a">)
B.4 PARAMETER-FREE CONVERGENCE RATE
In this section, we give a convergence rate taking into account both the inner and the outer loop when the operator F is L-Lipschitz.
First, we bound x a*I| under the assumptions Theorem 2 and Theorem 3, resp, and give the following lemma:
Lemma 9, For monotone F, then for any μ > 0, we have:
(i) If F is star-t-taanoo m-monooooo (Def. 1), then ||=e x0ll S (m
(ii) If inf F (x) )
m- --~--|| > 0, where S ér or Ć. then x1'- - -x"' S m μ
Proof. Consider convex problem
min F(
s.h. ((x) S 0 Cr = d
(P)
The Lagrangian of (P) is
(0, = F(x") A p(x) + (C(x dd.
There exists X > and v", s.t. (x" X vi) is a KKT point of (KKT-2). By the stationarity condition in (KKT-2)) have that
g( v") = inf L(x" X N0) T( + ATv((a")) Dt (Cr" -d) d).
=0
Note that by the complementarity slackness condition in (KKT-2), have ÄT AT x((")= -mp. Since xx is feasible point of (P), (N' v") dual feasible, thus by the duality theory, we have: F( g(²,, v²) = F(xx") mp
from where we deduce that
F(* - -x") S mpp.
(40)
Therefore,
(i) If mtar---monoton::
Since xx E St,r, have
F(x') = =x)) 2 0.
(41)
Subtract (40) by (41) and using the star-f-monotonicity of F, we obtain
c " - x < (F(x*)) F)xx))) (x x²) S mp.
(ii) If a
inf
F (x=)T
--= 0, where S ć, or Č. since and S, by (40) have that
=E))
a 1ott x= < mp.
30

---

Published as a conference paper at ICLR 2023
We give another lemma that would be used in the proofs of our main results in this section.
Lemma 10. Assume F monotone and L-smooth (Assumption 1), then we have
((x K+1 x²) + (B 1 -B(Y)
(8)
Arr
24
Are
|1AS01 IV [(K + +1) +mp
K +1
VK +I
(42)
+L 1 x01l (1100h (I10MM -001 + V 3 (K +1 + |
A
A
3
F(nk (( (1)
K+1 - x²) (c(( -
(43)
A 2
Au
VK +1 + 11
+ M 1100 - xx
K +1
P(K+1]
and
(T (1)
K+1 - xx") (o((By (9) (1((((24))) B(y"
(x
A
2/3A" |2
mpe
2KK +1)
3(K +1)
(44)
+L |000 xx'1 | ||a""-=0"1 x²11
2/BA
A/
+
3 (K +
B({+1) 1)
B
where M sue [[(())] and B(x) = Emm, log( (pp(-))())))
Proof. Note that
|0 x/' || = xk+1 y || K+1 yk+1 + yk+1 gmvll
(45)
Recall that (29) gives
1 u yKtil S V
Are
3 (1)
and (34) gives
Am
uk+1
Plugging (29) and (34) into (45), we have
Ane
Ar
x K+1
S
+ $++VB+ B
+
(46)
Note that
F(x*))(x( (1) - xx) + (. -
=F(#*()T(<( (t) x + (B (B (2, (B())+1) B(y* + (xx x²)
+ +F(xx)) F(x*))) (xx K+1 x²).
31

---

Published as a conference paper at ICLR 2023
Thus by the Z-Lipschitzness of F. using (40), (46) and (37) in the proof of Thm. 9, we have
F(x") [=1 x²) 4e (B(y) (1) B(yy
(1)
F(attt) T(a (ar K+1 at + Mel (e (6)
(1)
B(() [F(z x²')
(F(x*) F)) (x (1)
[x
x²)
$ F( (t)
(xx+11 x + pe Pe (4) B(y (((x"))(x""+ x²)]
+ L | xx1l| (1 -2 -=(0) Ix+1 [
-x-1) x01l + 1|00 11=h-=11)
A
2
Ar
+++++11*M +112"111
+ mmpe
K K+1
VK +1
3KK +1)
(112th
Art
A H+
+L 1ptt
x"1l
V B(K +1)
+
8
Using (38), we have
F(a [2 ) - x²) + (1((BuRt1)) - B(
( K+1 - x²) + Ne (r (1) - B(y"))) + F( K+ (x= x²')
(( K+1 x²) + ne (B(ukBu - B(Br"()) + M ||00 x='l
A
2
Ar
+ ||* |l
M 11. BKK +1)
K+1
K
VK+1
+1
Similarly, recall that (36) gives
2 2/5An SA
|ē 9K+1ll $
(K + +1)
By (34) and the convexity of ||- we have
(e) Uk+t ydd ||=|=
K+1
An
7d
(47)
K
3
Note that Thus we have
(t) K+1 - x
ØK+1
(t)
you
(1)
K+
+ +
(0)
(48)
Plugging (36) and (47) into (48), we have
|
K+1
(0)
11
5
3(K +1)
2/3AM
+
*V
A
(49)
32

---

Published as a conference paper at ICLR 2023
Using the Z-Lipschitzness of F, (39) and (49), we have
P(a*) x²) ue (B((k++))) B(y
F( x² + (B B(x ((th
+ (F((2))) F(xx 1) (1)
K+1 2²)
< P( K+1 - xtt) + ui (B( B(y + (F(( -x0))
+ L | - x01 (|
+ 1|00 -x-1
x²11)
2 k+1
4
2V3A | ||
+ mpe
2(K +
B(K +1)
2/3
A
+ L ||a - =x
|| - =x (K + 1) + *V
Now we are ready to give our main theorems this section.
Theorem 12 (Complete convergence rate
man-c-monotone operator). Given an operator X' + T2t monotone and I--Lipschitz on C_ (Def. 1, 1), and either F is strictly monotone on C or one of ip is strictly convex. Assume there exists r > 0 or s >> 0 such that F is monooone- as per Def. 1on either TN or C,, resp. Let Dr A A - | + Bllyo - 1
0i denote the last and average iterate of Algorithm 1, respectively, run with sufficiently small p1-1- Then there exists Ko N, Ko depends on r or s, s.t.K Ko. for all t e [T], we have that:
Let æx and (1) K Ek (0)
1. 1 x.1
5
2
K
24
VK
+
1|
Ar4 BK
LM
p-1
)
and
g K C) x Mo (z
4" K
+
24
+
||
Are 9K
+ LM,
m p12
VR
2. If in addition F' is E-monotone on C=, we have |1 x² <
Aur ck
+
(m
and
g( C) & Mo ( ((AN)
1/8
(Th (2)x) +))
where Mo = DL + M is a linear function of L, see the proof of Lemma in App. B, and M1 e (m )) + 2 Am +
33

---

Published as a conference paper at ICLR 2023
Proof. By the monotonnnot of course F, using (42) and (43) in Lemma 10, we have
c||02111 x²
s(F(x)) - F( F(x () x²)
=F( - x²) + pe (B B(y
- -(P(a') (1) - x²) ) + (c(B(xx+1) B(y
(I (1) )²) + 1i (B (9 (l
+11F(0 (((K)) x0) + pu (B ( Bly
(6)
A
2A
A
$
| IV
+ +M || 1 x=11
K +1
VK +1
(K + +)
A
2
Arc
||2 1V
+ 1p4
K+1
VK +1
3KK +1)
AP
A
+ L 1|0
x11
|100
x"1l
+
[K + 1)
B
Att
24
A
22
11
K ++
VK+1
B BK +1)
Are
Art
M L
+ ||
x*1|
3 +
+ mpe
(KK +1)
A Hr
Are
<2
|| 1
K +1
VK+1 +1
B(K+1)
A
Ar
M L
+ L
Me)
+
(K
11
3
where in the last inequality we use Lemma 9 (i).
We let Mj A (
+ 2
Art 3
+
M T. then we have
K+1 x
(1)
<
A
24 uz
+ ||*I
AMt B(K
+
LM
m
14g
K +1
VK +1
c
By Lemma 1, we obtain
g0 0) Mo
2
APC
2
||*
Apc
LM
-
2/2
8
+1+
VK
+I
c
c
in addition F E-monotone on Cz, then from (30) we have:
A
a K+1
x11
o(K (I]++T)
+ (=1))
Again by Lemma 1, we have (( () < Mo
((=AM))
((
AMe ([K+T])
+ ( mh
Theorem 13 (Complete convergence rate for cour---mootone operator). Given an operator
X Ra assume: (i) F monotone and T--mooth on Cz, as per Def. 1, 1; (ii) either F is strictly
34

---

Published as a conference paper at ICLR 2023
monotone on C or of (ps is strictly convex: and (iii)
inf
F Fxx)
x-=x
0, where
mES (=*)
S = or C.. Let A. A 11100 x1 8l 11
Let oK and &x
& Then there exists Ko E N, Ko
(t)
Σ
Ei=
K
(1) denote the last and average iterate of Algorithm respectively. depends on r or 8, s.t.t E [T), AK > Ko, we have that:
x.
= a
A"
24
+
B(y
M-18 18 and
K
VK
3K
a
( C) V Mo (!
A
24
|
Art OK
m.M a
Bly B-B-)BBBB 11-18+11)
K
If in addition
inf (mr)
F(x*)T
= b >
(with S = C, or C.).
x--="
then
(() KK
x=*
S
A 2K
AAL
3(K)
+
Ma
b 1-- 1-1 and g( s
Mo
Are
PVDAPT |M ((K)
+
Ms
b (1-18++1)
2K
where M see [[)())) Mo DL + M is linear function of L, see the proof of Lemma 1 in B(y")))
App. B, and M3 A + Lm
m (1
2/33 a(K+1) +
Arte
B*
B
Proof. If the barrier term B(y 2 Byy using (43) in Lemma 10, we have
F(zk T(= x²)
<F(0 (1) K ((= K+1 xx) + He(B(BRR 12 -B((")
Att
2
Ane
$
K11
VK +1 11
((K+1)
M 1|x
x=
If Byyk-1 S B(y ) since B is lower bounded in any compact set, and by (46) in Lemma 9 we
have
1 K+1 m0te|
2/32 BK++J
Ar
< 3 Ar A M2, we let B = in j I|5 B(x)). p
Then we have
F( (1)
T
K+1 x²)
< F(
((
x²) + Pe(B(yR-)) B(y + +B(((())) -B")
A 2 Mr
Am
$
+ 12
B(K+ +1) + M 110 x + (B(((t)) -B*).
K+1
VK
+1
Thus in both case we have
x+1
K+1
< <F (1
T(x K+1
- xx))
A
24
A
mM Me (B(y"* B*).
||**||
K+1
VK +1
((K+)
a
where in the first inequality assumption (iii) is used and in the last inequality Lemma 9 used. Thus we have:
(8) x x x
A F1
2A
|1
I1
A+t
+
mM
B(y B* Pe
a
K
+1
VK
+1
3(K
+ 1)
a²
a
And by Lemma 1, we obtain
ARt
2
Ans
mM az
+ B B*
( S Mo
+
+
K+1
VK
+1
B(K+1)
35

---

Published as a conference paper at ICLR 2023
If in addition
inf F(x*)) =ES\
| -----1
#-=" b 0, then similarly, from (44) in Lemma 10, we have
b
2 K+1 - x*1
(2x (8)
x²) + p4 (B - B(yr*)) + (e(B(y")) B*)
A
+ 2/3A" |
(K +1) + mp
2(K +1)
L L- m
m
M4 + 2/3
A
+ +i((B(y")) B²)
14
a
3 (K +)
A
2/BA" |
2 2K +1)
(KK +1)
Lm
m
4-1 + 2/BAT
Ar
+
m +
B(y B²
ue
B (K 1)
3
Let M3 A m +
Im
m p
+
2VBAH B(K+I)
Ar
+ Bly B², then we have
1 K+1
0711 5 (KK 1)
A
2/BA"
[KK +1) (xx))))) 1
+
+
6 pl
By Lemma 1, we have
A
+ 2/3A 12
((++1) -(x++1))))) +
M3
0) 5 b 2 [K
me.
b
-xx (t) - x² 1 Remark 5. In Theorem 12, for any 2 O(n K), we have
g ,), s O (kike ).
and
1 K x+1
9( C) < O ( Similarly, in Theorem 13, for any t 2 OIn K), we have
x (2)
x=
1 C) < 0 (x) and 1 x01 g C) O(
B.5 DISCUSSION ON ALGORITHM
Advantages and disadvantages of Algorithm In Algorithm 1, the update of (step 8) requires solving (W-EQ). Our method is especially suitable for problems where (W-EQ) is easy to solve analytically. This includes the class of affine variational inequalities, low-dimensional problems, and when optimization variables represent probabilities, for example.
For problems where (W-EQ) is hard to solve- for example, min-max optimization problems in GANs one could other unconstrained methods like GDA EG methods (withoul projection) so as to solve (T(R", G), where G defined in (3). Algorithm 4 describes ACVI when using an unconstrained solver for the inner problems. We observe that Algorithm 4 outperforms the projection-based baseline algorithms, see for example Fig. 4.
Note that when there are constraints, the projection-based methods such as GDA, EG, OGDA etc. require solving quadratic programming problem in each iteration (or twice per iteration for EG). This problem often nontrivial and solving it may require using an interior point method or variants (such as the Frank-Woll algorithm). Because of this, Algorithm can be seen as an orthogonal approach to projection- based methods, in other words, as complementary tool to solve (cVI) and particularly relevant when the constraints are non-trivial.
ACVI with only equality or inequality constraints. If there are no equality constraints, then C= (t)
becomes R=" In this case, we have that 1 is the solution of:
1 (F(x) + x (0)) v 0.
+ 3
36

---

Published as a conference paper at ICLR 2023
When there inequality constraints, we let yı 2& and A 0 for every k and can remove the outer loop. Thus, Algorithm can be simplified to update only one variable æ each iteration with the following updating rule:
1k+1 is the unique solution of x B
P.F(a) Pa d. = 0.
37

---

Published as a conference paper at ICLR 2023
C VARIANT OF THE ACVI ALGORITHM (V-ACVI)
The presented approach of combining interior point methods with ADMM can be used as framework to derive additional algorithms that may be more suitable for some specific problems. More precisely, observe from Eq. that we could also consider different splitting than that in 4. Following this approach, we present a variant of Algorithm and discuss its advantages and disadvantages relative to Algorithm 1.
C.I INTRODUCTION OF THE VARIANT ACVI
Deriving the v-ACVI algorithm. By considering different splitting in (1) we get:
minF
(w)T T - Σ log (((x)) Cyy d
2.
s.t.
x == y
(50)
1[Cy d = {0
Cf
where:
+00, if Cy [
The augmented Lagrangian of (50) is thus:
8
Lp( y, A) = F(w) x log(-p:(z)) + 1 = d) + (A, x - y)
| y
(AL-CVI)
where B > 0 is the penalty parameter. We have that for æ at step is + 1:
0k+1 = arg min Ca( yk. As)
1
1 m
(51)
= arg min
x ys + B (F(w) + 2x)
M 8
log(-op (x)())))
The following proposition ensures the existence and uniqueness of rx+1 in Cz. i.c. We show that 2t41 is the unique solution C2 of the following closed-form equation (see App. C.2 for its proof):
()(( 0.
yk + 3 (F(w) + Ax)
(X-CF)
3
(x((x)
Proposition (unique solution). The problem (X-CF) has solution in Ci2 and the solution is unique.
For y. the updating rule is
yk+1 = argmin (x V, As)
argmin yEC_
(A
+
2 |1y xk++1l 113
B
(3)
arg min yEC=
11
0k+1
A 11
A
= Pa +
d
B
And the updating rule for dual variable is
A = A + 3(0x+11 - y
(A)
As in $ 4, we would like to choose so that = Ib+1- To this end, we need the following
assumption:
Assumption 2. vb E IR" and
0, x + FF(x)
Dm
Ve((#) v(x) + b 0 has solution in Cz.
38

---

Published as a conference paper at ICLR 2023
If Assumption holds true, can let wy be solution of
v yk++ + B (F(w)) AR+1)
1
m
V
(
(52)
B
pi(w)
in Ce. And by Proposition 3, we can let 16+11 be the unique solution of
1 m
yk + (F(un)) + A1)
(a)
pi(x)
in Ce.
Note that we is also solution of (a:). By the uniqueness of the solution (x) shown in Prop. 3, we know that Wy 2k+11
So in the (k + 1)-th step, we can compute a, y, and w by (x). (z). (A) and (52), respectively. Since Wk 2h+11, can simplify our algorithm by removing variable and only keep æ, y and A, see Algorithm 3.
Algorithm 3 v-ACVI pscudocode.
1: Input: operator F : X R equality Ca d and inequality constraints (ar( S 0, [m]. hyperparameters 1-1,3 > 0, E (0, 1), number of outer and inner loop iterations '' and K, resp.
2: Initialize: Yo E RR, n ER"
3: P. - (CCT))
where P. E Ru** where de RR"
4: de A CT(CCT) d
5: for = 0,...,
do
6: Me быt
7: Denote (ax,, y) as the solution of { Em
Va((w) (((
F(x) A) + y with respect
to 2. where y: are variables
8:
for k = 0..... K - do
9:
a k+1 => (1)
(6)
19k (0)
Ensures Øx+1 E N
(8) - 641 + 3 de
(1)
())
10:
Ve+1
A = + B(x M(41)
(0)
(6) (t)
12: end for
(yb (++1)
A
(1+1))
(yk x
(1)
14: end for
Discussion: ACVI Vs. v-ACVL. Relative to Algorithm 1, the subproblem for solving in line 7 in Algorithm: 3 becomes more complex, whereas the subproblem for becomes simpler. Hence, in cases when the inequality constraints simpler, there inequality constraints Alg. 3 may be more suitable, as that simplifies the x subproblem. However, Algorithm I balances better the complexities of the subproblems, hence it may be simpler to use for general problems.
Convergence of V-ACVI. By analogous proofs to those in App. B, we can get similar convergence results for Algorithm 1, that Theorems and Specifically, Theorem and 3 hold for Algorithm 3, provided that we replace the assumption "F' is monotone on C_ with "F' is monotone on Cg in Theorems and 3.
C.2 PROOF OF PROPOSITION
To prove proposition 3, we will use the following lemma.
Lemma 11. vb R., Vo Ce, | blß =m log( log(-sp(<=)) +00,11=0122 to0
Proof of Lemma 11. We denote Φ : C. + by
((x)
2 x - b1l
1
(x)())
3
39

---

Published as a conference paper at ICLR 2023
let B(x) - log(-<p(<z)). We choose arbitrary zo Cs. Then by the convexity of
(xx) we deduce that
Vo E Ce, ((x:) > x bl2 + ((xo) + VB(xa) vo) + ||a|| - +00
In the remaining, we prove Proposition which guarantees that (X-CF) has a unique solution.
Proof of Proposition 3: uniqueness of the solution of (X-CF). Let C. - IR denote:
((x) 2 211x + B (F(ww) + xx)1l
/
Σ i=1
log( (p)()))
B
We choose zo E C.e. By Lemma 11, Ve E Ce, d(x) + t00, |011
toc.
So there exists M > such that to E B(0, M) and Va E S, (()) S x(x)), a must belong to (00 M) where
B(0, = {æ E R" x S M }
It's clear that there exists > such that for every a Ca that satisfies ((x) S ((xo), x must belong to where
C. = {o B(O, M) (p)(())) & - - CC
(53)
And can make small enough so that wo Cr. C. nonempty compact and is continuous, so there exists xt E C, such that ((x*) S o(x), Vo E EC.
Note that Vo E Cz \C, (xx) 2 ((x))) ((x*). Therefore, x* is global minimizer of cb db is
strongly-convex thus Øk+1 = x² is its unique minimizer. So = xx+1 if and only if VΦ(ω) = 0.
Therefore, # the unique solution of yn + (F(w)) + Au Σズ (i(
(.(( 0.
40

---

Published as a conference paper at ICLR 2023
D DETAILS ON THE IMPLEMENTATION
In this section, we provide the details on the implementation of the experiments shown in the main part 2D and higher dimension bilinear game, see D.I and $ D.2, respectively. We also provide here in $ D.3 the details of the MNIST experiments presented later in App. E. In addition, we provide the source code through the following link: https: /tgi/tgthhh com/ Chavdarova/ACVV.
D.I EXPERIMENTS IN 2D
We first state the considered problem fully, then describe the setup what includes the hyperparameters. Problems. We consider the following constrained bilinear game (for the same experiment shown in Fig. I and 5):
min max 0.05zi + 2102 - 0.05x2.
(cBG)
Ti 2 #
The Von Neumann's ratio game (Von Neumann, 1971) (results in Fig. (a)) is follows:
(0, Ry)
min max- mEA' (x, Sy)
(RG)
-0.6 0.6
-0.3)
0.9 0.5
where 2 {z E R2|z - R
-0. and S
0.8
0.4
The so called Forsaken (Hsieh et al., 2021) game uunee-usedin in Fig. 2(b) and in App. E-is as follows:
min max z (xg - 0.45) - h(z1) - hx22), 21
(Forsaken)
where h(2) = - 1 12 the constraint = + x² < 4, and in App. E we use two other constraints: æ1 2 0.08 and x2 2 0.4.
6 62 The original version unconstrained X' = R.. In Fig. 2(b) we use
For the toy GAN experiments, shown in Fig. 2(c), the problem is as follows:
minmax 9 @
E
(xx²)
2~~N(0.1) (x002²)
E
(toy-GAN)
s.t. +2 <
In the experiment, look finite sum (sample average) approximation, which we then solve deterministically in a full batch fashion.
Setup. For all the 2D problems, we set the step size of GDA, EG and OGDA to 0.1, we use k
and a = 0.5 for LA-GDA, we set 3 = 0.08, 11-1 = 10-5, 8 = 0.5 and A = 0 for ACVI; and run for 50 iterations. For ACVI, set the number of outer loop iterations to T 20. In the first 19 outer loop iterations, we only run one inner loop iteration, and in the last outer loop iteration, we run 30 inner loop iterations (for total of 50 updates). In Fig. and Fig. (c), we set the starting point for all algorithms. In Fig. 2(a) and (b), we set the starting point to be (0.5, 0.5) for all algorithms.
D.2 HIGH -IGH-DIMENSION BILINEAR GAME
We set the step size of GDA, EG, and OGDA to 0.1, using & = 4 and a = 0.5 for LA-GDA. For ACVI, set 3 0.5, 1 10 6, 8 0.5 and X 0 for ACVI.
The solution of (HBG) is x* = 500
1 e, where e E 1000 As a metric of the experiments on this
problem, use the relative error: E, ( || In Fig.3(b), set 0.02 and compute the number of iterations of ACVI needed to reach the relative error given different rotation "strength"l -1), 77 E (0, 1). Here we set the maximum number of iterations to be 50 for all algorithms. In Fig. 3(a), we set = 0.05 and compute CPU times needed for ACVI, EG, OGDA, and LA4-GDA to reach different relative emrors. Here set the maximum
time 1500 seconds for all algorithms. In Fig. 7 in App. E on the other hand, we fix 7) = 0.05, and for varying CPU time limits, we compute the relative error of the last iterates of ACVI, GDA, EG, OGDA, and LA4-GDA.
More general HD-BG game (g-HBG). Since (HBG) has perfect conditioning (that is, the interactive term no Bag, is with B = I), in App. E.2 present results the following more general high
41

---

Published as a conference paper at ICLR 2023
dimensional bilinear game:
! 2
Ax + 1j) 1 Baz ! ar Caz
min max #1 EA
2
(g-HBG)
A=
a E R 500
and e eTar: = 0}.
Where A, B and C are randomly generated 500 x 500 matrices, and A, C are positive semi semi-defnitt.
The solution of (g. (g-HBG) is 0, where E
10000 As a metric of the experiments on this problem, we use the error =(xx)) = || The remaining settings are identical to those of (HBG), explained above.
Comparison with the Frank- Wolfe algorithm on general HD-BG (g-HBG) and (gg-HBGi) HBG), In App. E, we compare with the FW method (see A.4) on two problems: (i) (g- HBG), and (ii) (gg-HBB)) where the objective is the same (g-HBG) but the constraint set becomes more general, in which C; is a randomly generated 10 x 500 matrix, i = {1,2). In both experiments, we implement FW as in Algorithm 2, where we choose constraint set of (g-Huu (g-HBG) is a "shifted simplex". hence its vertices are easy to compute. This allows us solve the linear minimization problem in Algorithm 2 of (Gidel et al., 2017a) much faster, and we refer to this implementation as fast-FW. In contrast, for the (gg-HBG) problem, we cannot apply this, and in that case, use the standard linear programming routine covopt.solvers.lp in Python referred herein as FW.
be 2/(2 t) at the t-th iterate, t 0.... T. For (i), the
? x x|Aæ + (1 - 1)) x B2² - " - Ca2,
min max 2 12
(gg-HBG)
Ui a= E R 500
100e S x; 100e, and C, 0}. 1,2.
The solution of both (g-HBG) and (gg-HBG) is 0. As metric of the experiments on this problem, we use the error <(xx)) = || | ||- The remaining settings are identical to those of (HBG), explained above.
D.3 MNIST AND FASHION- -NIST EXPERIMENTS
For the experiments on the MNIST dataset 1 we the source code of Chavdarova et al. (2021b) for the baselines and we build on it to implement ACVI. For completeness, we provide an overview of the implementation.
Models. We used the DCGAN architectures (Radford et al., 2016), listed in Table 1, and the parameters of the models initialized using PyTorch default initialization. For experiments this dataset, we used the non-saturating GAN loss as proposed in (Goodfellow et al., 2014):
LD = EE log (D(za)) + E log (1 D(G(E))) aampa
(L-D)
Σ<p,
La log (D(G(z)))
(L-G)
EmP.
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 ACVI implementation. When implementing ACVI on MNIST, we "remove" the T 1), and fix μ to be small number, in particular, we select = 10-9. We randomly initialize æ and y and initialize À to zero. For lines 8 and of Algorithm 1, we run I steps of (unconstrained) EG and GD, respectively. For the update of (using EG), we use step-size Ta = 0.001, whereas for y (using GD), we use step-size Tyy = 0.2. We present results when E (1, 10). At every iteration, we update using the expression in line 11 of Algorithm 1, with B 0.5.
outer loop of Algorithm (that is
Because the problem in step 8 of Algorithm I does not change a lot over the iterations (as well as when computing y), when we implement Algorithm 1 we do not reinitialize the variable æ. We
Provided under Creative Commons Attribution-Sha Alike 3.0.
42

---

Published as a conference paper at ICLR 2023
Generator
Discriminator
Input: 2 = R ~ I))
Input: R 1xx28228
transposed conv. (ker: 3x3, 128 512; stride:
conv. (ker: 4x4, 1 1 64; stride: 2: pad:
Batch Normalization
LeakyReLU (negative slope: 0.2)
ReLU
conv. (ker: 4x4, 64 + 128; stride: pad:1)
transposed conv. (ker: 4x4, 512 256,
stride:
Batch Normalization
Batch Normalization
LeakyReLU (negative slope: 0.2)
ReLU
conv. (ker: 4x4, 128 - 256; stride: 2; pad:1)
transposed conv. (ker: 4x4, 256 128, stride:
Batch Normalization
Batch Normalization
LeakyReLU (negative slope: 0.2)
ReLU
transposed conv. (ker: 4x4, 128 1, stride: 2, pad: 1)
conv. (ker: 3x3, 256 1; stride: 1)
Tanh(-)
Sigmoid(.)
Table DCGAN architectures (Radford al., 2016) used for experiments on MNIST. With "conv." we denote convolutional layer and "transposed conv" transposed convolution layer (Radford al., 2016). We use ker and pad denote kernel and padding for the (transposed) convolution layers, respectively. With hxw we denote the kernel size. With Gin yout denote the number of channels of the input and output, for (transposed) convolution layers. The models use Batch Normalization (loffe & Szegedy, 2015) layers.
instead use the one from the previous iteration as initialization and update times. The full details of the training when using inner optimizer for step 8 of Algorithm are provided in Algorithm 4, where we recall that G(x) is defined as:
1 P.F(a)) - Payk + P.A. de +
G(æ) - x.
(G-FQ)
Note that in the case of MNIST, we consider only inequality constraints (and there are equality constraints), therefore, the matrices P. and de are identity and zero, respectively. Thus, there is no need for lines and 4 in Algorithm 4.
Algorithm 4 Pseudocode for ACVI when using an inner optimizer (MNIST experiments).
1: Input: operator F : X + R" equality Cr = d and inequality constraints (xx()) < 0, [m]. hyperparameters μ4, 3 > 0, 8 E (0, 1), inner optimizer (e.g. EG, GDA, OGDA), number of steps for the inner-optimizer, number of iterations K.
2: Initialize: Eg E R", y/o E R", Ao E R"
3: P. I (CCC))-
where P. E R
4: d, A CC(CC)-
where d, R
5: for k O....., - do
6: To obtain #x+1: run steps of A solving VI(R", G). where G defined in (G-EQ)
7:
To obtain 1 run l steps of GD to find yk+1 that minimizes:
F Σn log - (1)) + y 0b+1 - 1 Ax
8: A&+1
> + B(x - 11+1
9:
end for
10:
Return: ØK
The implementation details for the Fashion-MNIST experiment are identical to those of the MNIST experiment.
Setup 1: MNIST. The MNIST experiment Fig. 4 in the main part (and Fig. 11, 12) has 100 randomly generated linear inequality constraints for the Generator and 100 for the Discriminator.
Setup 1: projection details. Suppose the linear inequality constraints for the Generator are A0 < b, where 0 R is the vector of all parameters of the Generator, A (a..... a T E R 100 (b...... b1on) e R100 We use the greedy projection algoritim described in (Beck, 2017). A
greedy projection algorithm is essentially projected gradient method, it is easy implement in
43

---

Published as a conference paper at ICLR 2023
high-dimension problems, and it has convergence rate of O(1/VK). See Chapter 8.2.3 in (Beck, 2017) for more details. Since the dimension n is very large, at each step the projection, one could only project 0 to one hyperplane a. x b, for some E I()), where
I(0) - tila30 > by}.
For every j E (1. 100), let
Sj _ | - bj}.
The greedy projection method chooses so that E arg max (0,)), Note that as long as is not in the constraint set Cs {=|Arr I b), i would be in I(0). Algorithm 5 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.
Algorithm 5 Greedy projection method for the baseline.
1: Input: 0 R A
(a], . a T
10000xm b (bI...., (ui...,bio0)) b100) IR100 >
2: while True do
I(0) _ [jla] b,}
0-:b;
4: if I(0) = 0 or max
< then
(EI(O)
|a
5: break
6: end if
a 0-yy
7: choose E arg max
a,l
jEI(O)
8:
0 0
|a.1|
9:
end while
10:
Return: 0
Setup 2: MNIST & Fashion-MNIST. We add two constraints for the MNIST experiment: set the squared sum of all parameters of the Generator and that of the Discriminator (separately) to be less than or equal to hyperparameter M. We select large number for M; in particular, we set M 50.
Metries. We describe the metrics for the MNIST experiments shown later in App. E. We use the two standard GAN metrics, Inception Score (IS, Salimans al., 2016) and Fréchet Inception Distance (FID, Heusel et al., 2017). Both FID and IS rely on a pre-trained classifier and take a finite set of in samples from the generator compute these. Since MNIST has greyscale images, we used classifier trained on this dataset and used m = 5000.
Metrics: IS. Given sample from the generator ig ~ Py---y-a- where Pg denotes the data distribution of the generator- IS uses the softmax output of the pre-trained network p( 2 which represents the probability that ã. is of class C₁ i E 1... . i.c., p()(ū,) e [0, _] It then computes the marginal class distribution p(ğ) between the predicted conditional label distribution p())ū,)) and the marginal class distribution p(ū). More precisely, it is computed as follows:
J& p(g) a (ū.g). IS measures the Billback-Leibles divergence 1
p(ue (5,) log p(yel(E)) p(u=)
TS(G) exp
E P.
D (P(0),
exp
(IS)
aims at estimating (i) if the samples look realistic i.e., p())(g)) should have low entropy, and (ii) the samples diverse (from different ImageNet classes), i.c., p(ğ) should have high entropy. As these are combined using the Kullback-Leibler divergence, the higher the score is, the better the performance.
Metrics: FID. Contrary to IS, FID compares the synthetic samples ā. ~ Py with those of the training dataset Hd Pa in feature space. The samples are embedded using the first several layers of pre-trained classifier. It assumes P, and pa are multivariate normal distributions and estimates the means my and m. and covariances C, and Ca, respectively, for Py and pa in that feature space.
44

---

Published as a conference paper at ICLR 2023
Finally, FID is computed as:
(p) Re Ds (mmms Ca), (my: Cg)) || - m + Tr + C. -(C,C)))
(FID)
where B2 denotes the Fréchet Distance. Note that as this metric distance, the lower is, the better the performance.
Hardware. We used the Colab platform cattps://colss research, google com/) and Tesla P100 GPUs. The running times are reported in App. E.
45

---

Published as a conference paper at ICLR 2023
E ADDITIONAL EMPIRICAL ANALYSIS
In this section, we provide some omitted plots/analyses of the results in the main paper as well as addi- tional experiments. In particular, (i) App. E. lists results in 2D, (ii) App. E.2 on (HBG) and (g-HBG), whereas (iii) App. E.3 provides more detailed plots of those experiments summarized in Fig. 4 and presents additional results on other constraints on MNIST where we compare computationally with unconstained baselines.
E.1 ADDITIONAL EXPERIMENTS IN 2D, ON HBG AND ON G-HBG
Depicting the omitted baselines of Fig. 1. While Fig. lists solely EG and ACVI for clarity, Fig. depicts all the considered baselines in this paper the cBG problem for completeness.
GDA
EG
OGDA
LA5-GDA
ACVI
Figure 5: addition to Fig. 1, here we depict all the considered baselines on the cBG problem. The solution at (0, 0) is denoted with red star (+), and the vector field of this problem with gray arrows. See App. D.1 for details on the implementation.
Additional experiments: varying constraints on the Forsaken problem. The Forsaken game was first pointed out in (Hsieh et al., 2021) and is particularly relevant because it has limit cycles, despite that is in 2D. Since we are missing a tool to detect we are limit cycle when in higher dimensions, this example is popular benchmark in many recent works. Interestingly, in Fig. 2(b) we observe that ACVI is the only method that escapes the limit cycle. However, since in those simulations, given the initial point the constraints not active throughout the training, in this section, we run experiments with additional constraints. Fig. depicts the baseline methods and ACVI the Forsaken problem with different constraints than that considered in Fig. (that x7 + x3 I 4). Since this game is non-monotone, we observe that for some constraints the baseline -eathods-GDA, EG, OGDA, LA4-GDA-SKe near the constraint (and do converge). This may indicate that ACVI may have better chances of converging for broader problem classes than monotone VIs, relative baseline methods whose convergence may depend on the constraints, and when hitting constraint may be significantly slower (as Fig. illustrates).
46

---

Published as a conference paper at ICLR 2023
1.50
1.2
ACVI
1.25
1.0
GDA
1.00
EG
0.8
OGDA
0.75
LA4GDA
0.6
0.50
0.4
0.0
0.2
0.4
0.6
-1
0
(a) 21 2 0.08
(b) x2 2 0.4
Figure 6: Forsaken game with different constraints: we consider two additional (to that Fig. 2) constraints: (a) that 2 0.08, and (b) that 22 2 0.4. See App. D. for details on the implementation, and App. E.1 for discussion.
E.2 ADDITIONAL EXPERIMENTS HBG AND G-HBG
Complementary analysis to those in Fig. 3. Similar to Fig. 3, in Fig. 7 we run experiments on the HBG problem. However, here for a given fixed CPU time, we depict the relative error of the considered baselines and ACVI.
10
GDA
relative emor
10-2
EG
OGDA
10
LA4-GDA
ACVI
10
10-5
100
200
CPU time (s)
Figure Given varying CPU time (in seconds), depicting the relative error (see App. D.2) of GDA, EG, OGDA, LA4-GDA, and ACVI (Algorithm 1) on the HBG problem where 77 is fixed to 7) = .05 (hence the vector field highly rotational). This experiment complements those Fig. in the main paper. For the details on the implementation, see App. D.2.
Additional experiments on (g- HBG). In Fig. 8 we run experiments on the generalized HBG problem (g-HBG). In figure 8(a), we compute the number of iterations needed to reach e-distance to solution for varying intensity of the rotational component (1 - 7): in figure 8(b), we compute the error of the last iterate given fixed CPU time. We observe that despite the highly rotational monotone vector field, ACVI converges significantly faster in terms wall clock time in higher dimensions as well.
Comparison with Frank-Waa algorithm on (g- HBG) and HBG). Similar to Fig. 8, in Fig. also run experiments (g- (BB), but here we compare ACVI with FW. We observe that ACVI outperforms FW even when we make use the special structure of the simple constraint set when solving the linear minimization problem in FW fast FW method). Similar Fig. 9(b), in Fig. 10
47

---

Published as a conference paper at ICLR 2023
10a
50
mumber of iterations
GDA
40
FG
OGDA
10
error
LA4-GDA
20
ACVI
10
10
0.5
1.0
50
100
1
CPU time (+)
(a) Varying rotational intensity (1 7))
(b) Achieved error given varying fixed CPU time
Figure 8: General high-ddmeensioal bilinear game (g-HBG); comparison of ACVI with the GDA, EG, OGDA, and LA4-GDA baselines (described in App. A.4). Left: number of iterations (y-axis) needed to reach an c-distance to the solution, for varying intensity of the rotational component 1 (n) is the z-axis) of the vector field (the smaller the 7) the higher the rotational component). We fix a threshold of the maximum number of iterations, and we stop the experiment. Right: distance to the solution (see App. D.2) of the last iterate (y-axis) for varying wall-clock CPU time allowed to run each experiment (æ-axis); in this experiment is fixed to = 0.05. See App. E.2 and D.2 for discussion and details on the implementation, respectively.
we run experiments on the (gg-HBG) problem, where we fix CPU time and depict the relative error of ACVI and FW.
10a
mumber of iterations
10
ACVI
30
ACVI
error
FW
10
FW
20
fast FW
fast FW
10-1
10
10
0.0
0.5
1.0
50
100
"
opu time (s)
Varying rotational intensity (1 17)
Achieved error given varying fixed CPU time
Figure 9: General high-dimensional bilinear game (B-H comparison of ACVI with FW baseline (Algorithm 2). Left: number of iterations (y-axis) needed to reach an e-distance to the solution, for varying intensity of the rotational component y the higher the rotational component). We fix threshold of the maximum number of iterations, and we stop the experiment. Right: distance to the solution (see App. D.2) of the last iterate (y-axis) for varying wall-clock CPU time allowed run each experiment (æ-axis); in this experiment is fixed to 0.05. See App. E.2 and D.2 for discussion and details on the implementation, respectively.
17 (17 the r-axis) of the vector field (the smaller the
Since FW (and variants, such as approximate and accelerated) rely on a specific structure of the constraints, FW can be extremely slow when those assumptions met-see discussion by Jaggi
48

---

Published as a conference paper at ICLR 2023
(2013) in $3 as well as examples in $4 therein. In contrast, the herein-presente ACVI Algorithm focuses on constraints of a general form, and further variants can be derived out of to also exploit the structure of the constraints. We leave exploiting such constraint structure- stuuutue-including extending FW to VIs and deriving variants of ACVI-for future work.
10a
10
eTTOT
ACVI
10
FW
50
100
cpu time (s)
Figure 10: Given varying CPU time (in seconds), depicting the relative error (see App. D.2) of FW and ACVI (Algorithm 1) on the HBG problem where 1) is fixed to l .05 (hence the vector field is highly rotational). For the details on the implementation, see App. D.2.
E.3 EXPERIMENTS ON MNIST AND FASHION-MNIST
E.3.1 SETUP EXPERIMENTS ON MNIST WITH LINEAR INEQUALITIES
In this section, we present more detailed results of the summarizing plot in Fig. 4 of the main paper. For this experiment, we used linear inequalities as described in & D.3. Unlike in subsection E.3.2, here all the baselines are projected methods (that is, the same problem setting applies to ACVI and the baselines).
Fig. 11 and 12 depict the comparisons with projected GDA and projected EG, respectively. We observe that ACVI converges fast relative the corresponding baseline. When choosing a larger number of steps for the inner problem I = 10 (see Algorithm 4) the wall-clock time per iteration increases, and interestingly the ACVI steps compensate for that and overall converge fast as when I 1=1. 1.
E.3.2 SETUP 2: EXPERIMENTS ON (FASIIINN)MNISS WITH QUADRATIC INEQUALITIES
In this section, we consider the MNIST and Fashion-MNIST datasets, which are unconstrained problems so as to make use of the well-established performance metrics (which are otherwise unclear in the non-monotone settings, where we do not know the optimal solution apriori). We augment the problem with mild constraint which requires that the norm of the per-player parameters does not exceed a certain value (see App. D.3). We compare ACVI with inconstrained baselines, which sets ACVI a disadvantage as the projection requires additional computation. However, the primary purpose of these experiments is to observe if Algorithm I is competitive computationally--ue lines 8 and are non-trivial and require an (unconstrained) solver. However note that since MNIST relatively casy problem, it may not answer the natural question if ACVI has advantages problems augmented with constraints over standard unconstrained methods. We leave such analyses for future work. The implementation and the used metrics described in App. D.3.
when
Fig. 13 summarizes the experiments in terms of the obtained FID score over time. We observe that ACVI (although it uses two solvers at each iteration) is yet performing competitively to uncon- strained GDA and EG. Figures 14-19 provide in addition samples of the Generator and scores, separately for each method. Figures 20 and 21 depict samples generated by the different methods,
49

---

Published as a conference paper at ICLR 2023
10a
Projected CDA
ACVI w/ GDA, 1
8
ACVI w/ GDA,
101
FID
2
4
10a
Projected GDA
ACVI w/ GDA.
10
ACVI w/ GDA, 1=
1000
2000
1000
time (socouds)
time (scoonds)
(a) FID (lower is better)
(b) IS (higher is better)
Figure 11: Serup 1: Comparison between ACVI and GDA, and the projected GDA MNIST with linear inequalities (described in D.3). denotes the number of steps for the inner problems, see Algorithm 4. The depicted results are over multiple seeds. The FID and IS metrics as well as the implementation details are described in App. D.3. See App. E.3. for discussion.
10a
Projectod BG
ACVI w/ DG,
8
ACVI w/ EG, 10
10a
6-
FID
4-
10"
Projected FG
2
ACVI w/ EG,
ACVI w/ EG. I= 10
10-1
1000
2000
1000
2000
time (scconds)
time (seconds)
(a) FID (lower is better)
(b) IS (higher is better)
Figure 12: Setup 1: Comparison between ACVI and EG, and the projected EG on MNIST with linear inequalities (described D.3). denotes the number steps for the inner problems, see Algorithm 4. The depicted results are over multiple seeds. The FID and IS metrics as well as the implementation details are described in App. D.3. See App. E. for discussion.
when trained on the Fashion-MNIST dataset. We believe that further exploring the type of constraints to be added, or the implementation options (e.g., step-size) may be proven fruitful even for problems that are originally unconstrained as such an approach may reduce the rotational component of the original vector field, what in turn causes faster convergence or may help in escaping limit cycles for problems beyond monotone ones.
50

---

Published as a conference paper at ICLR 2023
GDA
FG
10a
10a
ACVI+GDD GDA step
ACVI+EG stop
ACVI GDA 10 step
ACVI EG 10 step
10
10
FID
FID
109
10-1
10
500
1000
1500
2000
1000
2000
3000
(seconds)
(seconds)
(a) GDA, and ACVI with GDA
(b) EG, and ACVI with EG
Summary of the experiments on MNIST, using FID (lower is better). 13(a): GDA and ACVI with GDA, and 13(b): EG and ACVI with EG, using = {1, 10) for ACVI Using step size of 0.001. The depicted results are over multiple seeds. See App. D.3 and E.3 for details on the implementation and discussion, resp.
Figure 13:
3
9
0
5
4
3
55
2
/
6
9
5
03
7
7
1
3
0
4
2
2
6
6
2
4 60
055
4
3
3
9
4
9 5 0 2
0 2 7
5.5
6.0
2
7
S
5
7
6
8
a
200
5
7
9
3
4
25
9
5
4/
6
7 3
15
750
10
4
4
2
0
5
7
2
8
05
Figure 14: GDA on MNIST. Left: samples ā, Py of the last iterate of the Generator. Right: FID and IS of GDA, depicted blue and red, respectively. Using step size of 0.001.
51

---

Published as a conference paper at ICLR 2023
5
2
4
3
85
8
3
0
3
8
6
7 ( 5 6
9 7
85
6
5
3
5
44 4
8.0
15
100
3
2
9 4 7 4.
3
a
3
(
6
10
4
9
150
4
a
5
6
7 3
1
35
290
3
3
5
4
4
4
5
25
10
18
3
5
2
1
6
5
1
5
15
250
30
3
/
3
O
8
6
50
200
250
Figure 15: ACVI (Algorithm 1) with GDA steps on MNIST. Left: samples 2g ~ Pg of the last iterate of the Generator. Right: FID and IS of GDA, depicted in blue and red, respectively. Using step size of 0.001 for æ and 0.2 for y. and I 10 both for æ and y.
2
5
7
5
93
5
3
0
7
6
6
6
90
85
6
4
1
4
3
/ 4
4
A 5' 4/
2)
80
100
8
5
7
7
5
9
8
7
3
43
50
150
9
0
3
3 3
5
4.
0
5
O
5
6
52
4.0
35
30
2
1
8
0
5
4
4
S
25
6
6
5
9
2
5
0
1
8
28
0
5
0
4
2
9
00
50
100
L50
260
250
500
2008
1500
2000
Time (sec)
Figure 16: ACVI (Algorithm with GDA step on MNIST. Left: samples ag Py of the last iterate of the Generator. Right: FID and IS of GDA, depicted in blue and red, respectively. Using step size of 0.001 for and 0.2 for y, and both for x and y.
5
9
2
9
7
/
10.0
35
8
7
3
9
3
9
0
2
50
85
50
Q
5
4
à
4 2
9
9
100
4
2
6
8
3
0
1
7
9
f
5
5
50
130
0
4
8
Q
9
4
0 4 0 f
45
1
5
4
4
7
G
0
2
40
7
5
Y
2
3
3
4
0
0
6
9
6
8
5
3
8
9
00
10
10C
113
760
350
500
10000
1500
7000
7500
3000
3500
Time [tec]
Figure 17: EG MNIST. Left: samples mg Pg of the last iterate of the Generator, Right: FID and IS EG, depicted blue and red, respectively. Using step size of 0.001.
52

---

Published as a conference paper at ICLR 2023
6
4/
4
2
5
4
9
93
4
2
5
6
8
3
8
5 1 7 9 0 6
5
90
8.5
2
2
8
7
7
4
3
0
8.0
15
100
7
9
J
0
4
/
8
7
3
2
4
6
3
7
9
50
150
3
5
3
2
9
4.
0
4
2
5
9
f 0 A
4.0
35
4
8
5
6
P
5
5
25
30
5
3
8
8
A
A 2
2.
0
4
8
6
4
Q
00
50
100
L50
200
250
500
1000
1500
2005
2500
2000
3500
Time (sec)
Figure 18: ACVI (Algorithm with 10 EG steps on MNIST. Left: samples 2g Py of the last iterate of the Generator. Right: FID and IS of GDA, depicted in blue and red, respectively. Using step size of 0.001 for and 0.2 for y, and I both for x and y.
0
/
4
3
2 09 9
85
6
2
/ 7
7 9 4 8
4
8
5 0
6
5
75 6
85
7 9 903
9 8
6.0
150
3 3 3
Q
0 4 2
q
5
9
8
200
0
/ 1
3
8
15
6
5 3
4
4
3
8
10
15
250
5
3
6
3
5
6
0
7
(
05
10
Figure 19: ACVI (Algorithm 1) with 1 EG step on MNIST. Left: samples á, of the last iterate of the Generator. Right: FID and IS of GDA, depicted in blue and red, respectively. Using step size of 0.001 for and 0.2 for y, and [ = both for and y.
(a) EG
(b) ACVI+EG step
(c) ACVI+EG 10 step
Figure 20: Generated images at fixed wall-clock computation time (3000s) by: the baseline EG, and by ACVI with 1 (1, 10} on the Moshion-MNIST (Xiao et al., 2017) dataset. See App. D.3 and E.3 for details on the implementation and discussion, resp.
53

---

Published as a conference paper at ICLR 2023
(a) GDA
(b) ACVI+GDA 1 step
(c) ACVI+-GD 10 step
Figure 21: Generated images at fixed wall-clock computation time (3000s) by: the baseline GDA, and by ACVI with {1, 10) on the Pashion-MNIS' (Xiao al., 2017) dataset. See App. D.3 and E.3 for details on the implementation and discussion, resp.
54


Reviews:
[{"review_id": "XJEXpwKeLe", "reviewer": "Reviewer_WuKs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper aims to solve constrained monotone variational inequality when the projection step on the constraint is not simple. In particular, it uses the interior point method to handle the constraint, and then reformulate it to a form that can be solved by ADMM. For the convergence result, it provides guarantees for two settings: (a) star-$\\xi$-monotone operator; (b) monotone and not purely rotational. ", "summary_of_the_review": "Please see above. \n\n\n\n--------------------------------------\nThanks for the authors' response! I will keep my score.", "strength_and_weaknesses": "### Strength\n1. The method helps to alleviate the problem in minimax optimization when the projection is not cheap.\n2. The idea seems novel to me.\n3. In the experiments, in some problems, the method has obvious gains.\n\n\n### Weaknesses\n1. The method brings a couple of subproblems to solve for the primal variables in Lagrangian, e.g., (Y-EQ) and (W-EQ). But I also think it might not be a big problem. (Y-EQ) seems to be strongly convex, so it can be well-solved. (W-EQ) is associated with a strongly-monotone variational inequality, so it can also be solved fast. \n2. Even though the paper claims the algorithm is parameter-free, we may need access to problem parameters when solving the subproblems mentioned above. \n\nQuestions:\n1. In the design of the algorithm, why in the equation (1) we want to introduce a new variable y = x in order to use ADMM? Can this problem be solved directly before we replace x = y?\n2. In Section 4.2, it mentioned that in the monotone case, (some) constraints need to be active. Where does this assumption appear in Theorem 3?\n3. Why not compare the algorithm with Frank-Wolfe type of algorithm in the experiment?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SfvcrP_lMbJ", "reviewer": "Reviewer_9sD3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper considers variational inequalities whose feasible sets include linear equality and convex inequality constraints. \n\nWhen the VI operator is monotone, there are known globally convergent methods (such as Korpelevich's projected extragradeint) for solving these problems, with known averaged and last-iterate convergence rates. However, these methods require metric projections onto the feasible set, or Jacobian computations for the VI ooperation, which can be quite costly. \n\nThe goal of the paper is to develop an interior-point method that bypasses the need for projections, at the cost of requiring \n\n(i) a single matrix inversion at the beginning;\n(ii) that the (W-EQ) problem in the text be efficiently solvable (this is the case eg. for linear VI's as those occurring in classical zero-sum games);\n(iii) also, properties stronger than strict monotonicity, plus that the VI operation $F$ be \"non-rotational.\"\n\nUnder these strong assumptions, averaged and last-iterate convergence rates are proven. The method itself is a variant (in some sense) alternating direction method of multipliers. In particular, it is purely first-order. Additionally, its interior nature means that it requires no projections. \n\nSome experiments suggest that the new method compares favorably with alternatives in the literature. Intriguingly, this seems to hold even when the VI operation is very \"rotational.\"\n\n", "summary_of_the_review": "This paper offers a novel method for solving VIs that circumvents some of the limitations of projection-based approaches and second order methods. The method is globally convergent under strong assumptions, and shoing this requires a nontrivial analysis. Moreover, it seems to perform well in experiments. ", "strength_and_weaknesses": "*Strengths* \n\n- VIs form a very important family of problems. \n- The method proposed seems genuinely new.\n- Empirical performance in the (small) experiments is promising.\n- The theoretical analysis is quite interesting.\n\n*Weaknesses*\n\n- The assumptions required on the VI are quite strong. However, it is conceivable that they can be weakened significantly.\n- The main theorems \"hide\" the dependence of constants; this is standard in the literature, but can in principle hide important factors depending on the dimension, on the conditioning of $C$ or any other such important information.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Lztjc-Z7XbK", "reviewer": "Reviewer_2xGb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers variational inequality (VI) problems where complex constraints exist. They use the framework of the interior point method with log-barriers to handle the constraints. They merge this framework with the ADMM algorithm to provide the final design of the algorithm which is a two-loop algorithm. The outer loop decreases the penalty parameter progressively which is similar to traditional IP methods for optimization. The inner loop is for implementing the ADMM algorithm.They provide convergence rate for each outer loop (t) in various settings including monotonicity, strong/\\xi monotonicity, their \"star\" (or generalized) versions.", "summary_of_the_review": "Overall, I believe the paper is studying an important and quite general framework. But it falls short on many fronts as explained in the weakness part. ", "strength_and_weaknesses": "The paper is considering a challenging problem to solve. VI is an important topic of study and including complex constraints seems to be a completely unexplored area. However, there are some problems with the existing results which I would like to point out:\n\n1. My main concern is in the update step of x. It seems that to solve every single step, one requires to solve a system of nonlinear equations, which is a VI problem itself. This problem is challenging and for many applications, one may need a separate solver to get such soltions. However, in the analysis, it seems to be solved exactly. Current complexity results take this as an oracle. Effectively, the theoretical results don't capture the actucal computational complexity of the problem and hence, they are deceptive in nature. Note that this oracle needs to be called in every inner iteration. This makes the technical implementation to be a three-loop algorithm. \n\n2. Update of y may not be easy for general \\phi. Hence, even though the starting framework is general, the method is restrictive in nature.\n\n3. The paper claims that Lipschitz smoothness (Assumption 1) is not required in general. However, if I am not ignoring anything, the reason is precisely that x updated solve F as VI exactly for each inner look. If subproblem solvers are taken into consideration then solving such VI for arbitrary F may already be difficult.\n\n4. The paper in the main part does not discuss how to large T (number of outer loops) needs to be? The convergence rate results are devoid of T. I believe we must have a small mu to get to a good soltuion. However, the error introduced by mu is not characterized in the discussion. \n \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0CzKayRwAb", "reviewer": "Reviewer_P1Mi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper derives a first-order algorithm for constrained variational inequalities based on the interior point method and ADMM. Convergence rates of the algorithm for both $\\xi$-monotone and monotone cases are provided. Numerical experiments show its excellent behavior in practice compared to existing works.", "summary_of_the_review": "The contributions are enough for acceptance.", "strength_and_weaknesses": "**Strength:**\n\nThe paper provides the first first-order interior point method for constrained variational inequalities with a global convergence guarantee. A clear roadmap toward how the algorithm is built as well as its theoretical analysis is provided. Extensive numerical experiments are presented to demonstrate the clear advantage of the algorithm. It is surprising to see that the proposed algorithm can efficiently approach the optimal point while others cycle around the optimal or zigzag near the constraints.\n\n**Weaknesses:**\n\n1. The outer loop $T$ of Algorithm 1 is not discussed precisely, which might cause some confusion. I guess the role of $T$ is to ensure that $\\mu_t$ (line 9) is sufficiently small to handle the constraints $\\varphi$. The complexity should also take into account $T$ and the subproblems, which will contribute additional terms, and thus the lower bounds are only matched up to logarithmic factors. The algorithm can be difficult to implement, also because of this unavoidable triple-loop structure.\n\n2. I am a little bit confused about how to compare the results in Theorem 2 ($\\xi$-monotone) and 3 (monotone). The rates in Theorem 2 are strictly worse than in Theorem 3 when $\\xi>1$, but $\\xi$-monotonicity should be a stronger assumption.\n\n3. Could the author comment why assumption $(iii)$ is needed in Theorem 3? Why does it require $F(x^*)\\neq 0$, i.e., some constraints are active at $x^*$? I think this is implied by the condition $\\inf F(x^*)^\\top \\cdots>0$ that is used for the average guarantee.\n\n4. Minor: In Section 2, the term \"MVI\" is not introduced; In Section 3, typos in eq. (AL-CVX); In Section 4, the notation $\\perp$ is not defined in eq.(KKT); The paper states that the algorithm approaches the solution from the analytic center, which is the reason why cyclical behavior is reduced. Could the author explain why?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%