Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities
Authors: Zaiwei Chen
Eric Mazumdar
Venue: NeurIPS 2024 poster (2024)
Keywords: Monotone variational inequalities
generalized Frank-Wolfe method
last-iterate convergence
smoothed fictitious-play
Primary area: optimization
TL;DR: This paper establishes last-iterate convergence rate for a generalized Frank-Wolfe algorithm for solving monotone variational inequality problems.

Abstract: We study the convergence behavior of a generalized Frank-Wolfe algorithm in constrained (stochastic) monotone variational inequality (MVI) problems. In recent years, there have been numerous efforts to design algorithms for solving constrained MVI problems due to their connections with optimization, machine learning, and equilibrium computation in games. Most work in this domain has focused on extensions of simultaneous gradient play, with particular emphasis on understanding the convergence properties of extragradient and optimistic gradient methods. In contrast, we examine the performance of an algorithm from another well-known class of optimization algorithms: Frank-Wolfe. We show that a generalized variant of this algorithm achieves a fast $\mathcal{O}(T^{-1/2})$ last-iterate convergence rate in constrained MVI problems. By drawing connections between our generalized Frank-Wolfe algorithm and the well-known smoothed fictitious play (FP) from game theory, we also derive a finite-sample convergence rate for smoothed FP in zero-sum matrix games. Furthermore, we demonstrate that a stochastic variant of the generalized Frank-Wolfe algorithm for MVI problems also converges in a last-iterate sense, albeit at a slower $\mathcal{O}(T^{-1/6})$ convergence rate.

Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities
Zaiwei Chen Purdue IE West Lafayette, IN 47907 chen5252@purdue edu
Eric Mazumdar
Caltech CMS Pasadena, CA 91125
mazumdar@caltech.cco edu
Abstract
We study the convergence behavior of generalized Frank-Wolic algorithm in constrained (stochastic) monotone variational inequality (MVI) problems. re- cent years, there have been numerous efforts to design algorithms for solving constrained MVI problems due to their connections with optimization, machine learning, and equilibrium computation in games. Most work in this domain has focused on extensions of simultaneous gradient play, with particular emphasis on understanding the convergence properties of extragradient and optimistic gradient methods. In contrast, we examine the performance of an algorithm from another well-known class of optimization algorithms: Wolfe. We show that gener- alized variant of this algorithm achieves fast ((2-1/2) last-iterate convergence rate in constrained MVI problems. By drawing connections between our gener- alized Frank- Wolfe algorithm and the from game theory, we also derive a finite-sample convergence rate for smoothed FP in zero-sum matrix games. Furthermore, demonstrate that stochastic variant of the generalized Frank- Wolfe algorithm for MVT problems also converges in a last-iterate sense, albeit at a slower 1166 convergence rate.
smoothed fictitious play (FP)
Introduction
constrained monotone variational inequality (MVI) problem consists of solving for x² X C Rd such that
max (x" - FF)))(=) S 0, SE.
where F X Rd is a monotone operator [56. 37] and X' a convex set. MVIs arise in many foundational and emerging problems. In particular, many problems in optimization [10, 1, 39], equilibrium computation [43, 42), reinforcement learning [57, 38), and learning in games [13] can be formulated MVI problems.
Due to their wide applicability, recent years have seen significant advances in developing efficient algorithms to solve these problems. Despite the structure provided by the monotone mapping, MVI problems are well-known to be challenging to solve, as simple first-order algorithms may diverge exhibit complex limiting behaviors such as chaos [3, 27, 18). This has motivated the analysis of algorithms such as the extragradient method [37], the optimistic gradient method [51], and the Halpem iteration method [19]. These algorithms, particularly the extragradient and optimistic gradient methods- which can be viewed as approximating proximal point algorithms [46]-hane have been the focus of numerous recent works, with matching upper and lower bounds established under various assumptions about the feasible set X' and the operator F(.) [29, 30, 15, 26, 41). Due to their connection with gradient descent and various extensions in convex optimization, these algorithms
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

have garnered the most attention in the literature, with recent breakthroughs in the constrained regime where X a compact convex set [15]. See Section 1.1 for more details about related work.
In this paper, we take an orthogonal approach by analyzing the performance of another optimization algorithm for solving constrained MVI problems: Frank-Wolfe (FW) [21]. Although the FW algorithm was first proposed for solving MVI problems decades ago [32] and has been analyzed in the context of min-max optimization problems [24], its convergence rate for general MVI problems remains less understood. To address this, we provide an analysis of a smoothed version of FW for solving constrained MVI problems, even considering the case where one only has access to noisy estimates of the operator F(-). This case is particularly relevant to problems in machine learning [23], distributionally robust optimization [S, 61], and learning in games [25, 43].
1.1 Related Literature
There is a rich literature analyzing MVI problems and their solutions [8. 54]. In this section, give an overview of the most related works.
Gradient-Based Methods. Work on solving MVI problems has largely focused on understanding
the behavior of gradient-based algorithms due their connection with gradient descent optimiza-
tion, though other algorithms have also been proposed in the literature (see, e.g.. [60]]. Although straightforward generalizations of gradient descent can fail in MVI problems [42, 43], proximal point algorithms [52] and related methods such as the extragradient [37] and optimistic gradient [18] algorithms have been shown to provide much stronger convergence guarantees. Specifically, [26]
showed that the extragradient algorithm achieves a tight (TT-1/2) last-iterate convergence rate for the smooth convex-concaye saddle-point problem (a special case of MVI). In [17], the authors also studied addte- problems and proposed an algorithm called mirror-prox conditional gradient sliding, which comes with strong complexity guarantees. However, their analysis required strong concavity assumption on the objective function, which corresponds to strong monotonicity assump- tion in the variational inequality formulation. In [29], the authors studied unconstrained variational inequality problems and showed that the extragradient algorithm achieves an ((T-1) last-iterate convergence rate under the assumptions of monotonicity and Lipschitz continuity of F(-). Finally, in [15], the authors established the tight (TT))/2) last-iterate convergence of both the extragradient and optimistic gradient descent-ascent algorithms for constrained MVIs. However, the approach in [15) relies on computer-aided proofs, whereas our proof uses natural Lyapunov argument.
The Halpern Iteration Method. The Halpern iteration method was originally proposed to find the fixed points of non-expane con-expansive mappings [31]. More recently, algorithms based on the Halpern iteration have been applied to solving MVI problems with a fast OT convergence rate [19, 58). However, to the best of our knowledge, there are no results showing that the Halpem iteration method, or the algorithms proposed in [19, 58), have provable convergence in the stochastie setting.
Frank-Wolfe Methods. The closest work to ours in this area is [24], which analyzes FW in deterministic convex-concave saddle-point problems. They prove last-iterate convergence rates by making curvature assumptions on the operator F(-) and on the underlying space X' (i.e., assuming X' strongly convex or F(-) is strongly monotone). Additionally, they show a slow convergence rate for FW on polytopic sets without these curvature assumptions. In contrast, we analyze a smoothed version of FW, also known as the generalized conditional gradient algorithm [2, 12], in MVIs. We demonstrate that this generalized version of FW achieves fast convergence without imposing strong curvature assumptions on either the operator or the underlying space. Crucially, the smoothing technique allows us to bypass issues that arise with vanilla FW in saddle-point problems. Another application of FW in MVIs is presented in [35], where FW is used to compute the iterates in mirror-prox prox for MVIs.
Stochastic Monotone Variational Inequality Problems. There has been considerable recent work on solving stochastic MVI problems, where one can only obtain noisy estimates of the operator F(-). Such problems arise in multi-agent reinforcement learning [62] and distributionally robust supervised learning [61], among other domains. However, the literature is sparser for this class of problems, particularly regarding last-iterate convergence in constrained problems. Under curvature assumptions (on F(-) and/or X'), stronger guarantees (both in expectation and with high probability) exist for variants of extragradient and optimistic gradient algorithms [8, 28, 44]. Inspired by recent results using FW for stochastic optimization [45, 20], extend our smoothed FW algorithm to

---

stochastic MVI problems and, to the best of our knowledge, provide the first last-iterate convergence guarantee for an algorithm in constrained stochastic MVI problems without curvature assumptions on the monotone operator. While the (TT-1/6) rate of convergence we derive for this algorithm slower than the known (TT-1/2) convergence rate for the averaged iterates of the mirror-pro prox algorithm [36], it is important to note that the mirror-prov algorithm has been shown to diverge in stochastic monotone problems [16]. Furthermore, in MVI problems, it has been demonstrated that the averaged iterates can exhibit fundamentally faster convergence rates than the last iterate [26].
1.2 Our Contributions
We introduce and analyze a generalized FW algorithm for solving MVI problems. This algorithm natural extension of the classic smoothed fictitious play (FP) algorithm for learning in games [22], applied to monotone games and, by extension, to MVI problems. We show that the algorithm achieves a fast last-iterate convergence rate of ((T-1/2), matching the rates of optimistic gradient and extragradient algorithms. As consequence of our analysis, we derive finite-time bound for smooth FP finite zero-sum games.
We also consider the case of stochastic MVI problems, where only noisy estimates of F()) are available. We demonstrate that, by designing estimators similar those used in stochastic FW for optimization, it is possible to achieve last-iterate convergence in constrained MVI problems using generalized FW, though at a slower rate of ( Although this rate is not optimal, it appears to be the first last-iterate convergence rate for solving constrained stochastic MVI problems without assuming strong curvature properties of the operator F(-) or the set X', Indeed, previous algorithms have provided last-iterate guarantees either the unconstrained setting [14] or under curvature assumptions on F-)), such as strong (quasi)- monotniiitt or coercivity [8].
2 Problem Formulation
Let F: X' Rd be a (possibly nonlinear) operator, where X' is a convex and compact subset of TR. The associated variational inequality problem consists of solving for xx X such that
max (a* - 8) F(x*))))))))))))))))) < "
(1)
Although such problems canonically arise in optimization [54] and machine learning [39], where the operator F(-) usually the gradient some objective function, the formulation is general enough to capture other problems such as reinforcement learning [38] and learning in games [13]. Next, we provide two illustrative examples.
The Policy Evaluation Problem in Reinforcement Learning. Consider infinite horizon discounted Markov decision process (MDP) with a finite state space S, a finite action space A, set action-dependent transition probability matrices {Pa E RR(S) | a E A), a reward function R S A + R, and discount factor 7 E 1). The transition probabilities and the reward function are unknown to the agent. Given a policy ग : S + ((A), where A ((A) denotes the probability simplex on A, its value function V e giS! defined as
Example 1:
20 Σ
(*(s)= - En
('R(S,, So
for all s E S. where [-] means that the actions are chosen according to the policy л. The policy evaluation problem in reinforcement learning refers to the problem of estimating V= for given policy [57]. To solve this problem, it has been shown that V is the unique solution of a fixed-point equation known as the Bellman equation V = TV(V), where 7 R| - R [ is the Bellman operator [50]. Therefore, solving the policy evaluation problem is equivalent solving the unconstrained variational inequality problem -T=((VV) =
Example 2: Multi-Player Convex-Concave Games. Consider an n- n-player game where each player i E {1,2, ... n .m. has compact convex action set X; C R4 and a loss function fi Iī Xj + IR such that fa x) is convex in z; for all _ 11 Xy. Such games have been well analyzed

---

in the literature in economics [53] and more recently in machine learning [42]. Solving for a Nash
equilibrium [47] in this game can be formulated as solving for point X == [T- X such that
max,Ex (x" -5) S F(x*) - O, where
F(x) = a. fi (21, 2-11, Van fa V.
Indeed, by convexity, we have for any E IR that
max (x - s)) 2 E(f(Eno SEX
- min fi(s;, x x<1)] 20, s.E,
where the equality is achieved and only if a joint strategy x" (x , satisfies fi x min,,ex, (s, x")) for all i, which implies that x" is a Nash equilibrium of the game.
An important class of variational inequality problems is MVI problems where the operator F(.) is monotone over X. Note that an operator X Rd is said to be monotone if and only if
(F(z1) - F(xa)) T2) 2 O, V 22 E
(2)
Despite this additional structure, designing algorithms for solving constrained MVI problems effi ciently and with strong convergence guarantees has been an open problem until recently [15], with most work focused on analyzing approximations of proximal point algorithms such as extragradient and optimistic gradient approaches [29, 30, 15J.
Further generalizations of the MVI problem that of particular interest for applications in machine learning are stochastic MVI problems, where one only has access to a noisy estimator of F(x). Such situations arise in, e.g., reinforcement learning (where the agent learns by interacting with the environment) [57] and problems of distributionally robust optimization where one seeks to solve a zero-sum game using mini-batches estimate gradients [61, 48, 16).
The rest of this paper is organized as follows. To motivate the generalized FW algorithm for MVI problems, first present the smoothed FP, canonical algorithm for learning in games, which we view as the instantiation of generalized FW in zero-sum matrix games. We then introduce the generalized FW algorithm for solving MVI problems and present its last-iterate convergence rate. Moving to the stochastic setting, we propose a stochastic variant of the generalized FW algorithm also with last-iterate convergence guarantees. Notably, the algorithm employs timesceecale structure, where we construct a variance- reduced estimator of F F(r) on the fast timescale and implement the generalized FW algorithm the slow timescale.
3 Warm-Up: Smoothed Fictitious Play
In this section, we present the problem of finding Nash equilibrium of zero-sum game and reformulate it as an MVI problem. In addition, we present the smoothed FP algorithm for zero-sum games, which also motivates our algorithm for the MVI problem (1) in the next section.
Consider a two-player finite zero-sum game where the of pure strategies' for player i (where i E (1,2)) denoted by A'.. When players play over mixed strategies, we can write this game as the min-max optimization problem minA2EA(AP) ma(A)) ) Ro²,, where R E @gl4"x|/'' the payoff matrix. A canonical measure of the performance of algorithms for learning in such games is the Nash gap, which measures how far each player is from their best response:
NG NG
max ( ( Rx #'EA(A?)
min #PEA(A")
(mr²) R
Suppose that pair of strategies best response to their opponent's strategy, thereby having no incentive to deviate from their current strategy. This situation defines a Nash equilibrium [47].
(m = satisfies NG m.) = 0. Then, each player is playing the
Solving for a Nash equilibrium in such games has been a focus of interest in economics and the literature on learning in games, dating back to [59]. One of the most canonical algorithms for learning in games from that literature is FP, where players play the best responses to the empirical history
We will use strategy and policy interchangeably.

---

of their opponents' actions. Subsequently, generalization of that algorithm, smoothed FP, was introduced as it was found to be better model of human play, accounting for "trembling-hnde strategies in games [22]. In smoothed FP, players again keep track the empirical history of their opponents' play but instead sample an action from a smoothed best-response strategy rather than playing the exact best response.
More concretely, for any x E R4 such that æ; 2 0 for all i, let v(x) - di log(s;) be the entropy function [55]. Given i E (1,2) and a² E A', we use e(a') to denote the IA' dimmensioonll vector with its a'-th entry being one and zero everywhere else. Then, players make use of the algorithm presented in Algorithm 1 for repeatedly playing the finite zero-sum games.
Algorithm 1 Smoothed Fictitious Play (from Player I's perspective)
1: Input: Integer T, temperature >> 0, and initialization a E AAA2)
2: for 0, 1,.. T
do
3: of arg ((A)) (uTRri + TT(U)}
4: Play A] (-) and observe A3
5: m Ti + FI (e(A)) - x?)
6: end for
In smoothed FP, with an arbitrary initial estimate of the opponent's policy T in each round, player 1 plays the smoothed best response to its latest estimate of the opponent's policy (cf. Algorithm I Line 4), and updates the estimate n? according to Algorithm Line 5, which is an itcrative way of computing the empirical average of the opponent's 's historical strategies.
Despite its canonical nature and its connection classic algorithms in online learning, such as hew.--The-Regullrizee-----
(FTRL) [40], the algorithm lacks finite-time convergence rate guarantee, although it has been well analyzed in its continuous-time limit [33, 6]. To connect with FTRL, suppose that player 1 observes o² and does not know R, but has payoff-based feedback of the form 7t such that E(r, A]] = [(A} A In this case, smoothed FP reduces to FTRL or forms of FTRL with bandit feedback due the linear structure of the losses. However, smoothed FP assumes an unusual feedback structure (for online learning algorithms) in which each player is assumed to know the payoff matrix R, but can only observe the realized actions of their opponent, not the entire strategy o?? Therefore, previous approaches for analyzing FTRL do not apply, and, to the best of our knowledge, unite-time analysis of smoothed FP is still lacking in the literature, although it has been shown to be asymptotically no-regret [6].
The following convergence rate of Algorithm follows consequence of our more general results of generalized FW. Since we are dealing with a finite game, we assume, without loss of generality, that max, EA), A RR(a a²)l 1.
Theorem 3.1. Suppose that both players use smoothed FP in finite zero-sum games and E (0, 1]. Then, we have for any 2 that
4/ A
A2
36|A 36]A'|1442 log + 1) + + Tog([A (14431)))))
E|NG(Tt =3)1
t+1
T(t+
The proof of Theorem 3.1 is presented in Appendix A. In view of Theorem 3. given time horizon T. by choosing O (/2,,2), we have Ô (T-1/2) rate of convergence of the empirical history of the play. Equivalently, we have the following iteration complexity for the algorithm.
Corollary 3.1.1. To achieve [[NG(T],= < the iteration complexity is O(IA'||A314
To identify Algorithm for zero-sum games as a special case of generalized FW for MVI problems, observe that the Nash gap NG(..)) can be rewritten
NG(11,z2) ) = max (a - F
sE.
where & = (2), E X = A(A") x A(A?) and F(x) = Mæ with the matrix M defined as
M 1x -R; RT, 01441x1d'1) Since M + T 0, it is clear that F(-) is monotone
5

---

operator. In addition, when both players follow smooth FP as presented in Algorithm 1, the joint update equation can be equivalently written as
8t arg min sex (s + Tf(s))
(4)
1++1 = It - 04( - 8t + ww),
(5)
82) X, and w, is zero-mean random variable. In smoothed FP, the random variable Wy corresponds to the difference between the softmax distribution (ef. Algorithm Line 3) and a sample from the softmax distribution (cf. Algorithm Line 4). In view of Eqs. (3), (4), and (5), we see that smoothed FP for zero-sum matrix games is simply a generalization of FW for MVI problems. Although this algorithm has been well analyzed in the optimization literature (i.e., when F(.) is the gradient of some objective function) [2, 11, 12], it has yet be analyzed, to the best of our knowledge, in the context of more general MVT problems. In the next section, we show that this algorithm has strong convergence properties.
where f(s) [-0))=-(ss]) v(22) for any
4 Generalized Frank- Wolfe for Monotone Variational Inequalities
Motivated by the smoothed FP for zero-sum games, we next present our algorithm and convergence guarantees for solving general MVI problems.
Algorithm 2 Generalized Frank- Wolfe for Monotone Variational Inequalities
1: Input: Integer T, tunable parameter T > 0, and initialization zo RRd
2: for t = 0, 1, T do
3: 8t = arg min,ex Fxx) + fs))
4: Øt+11 2t (zi 8t Wt)
5: end for
In Algorithm 2 Line 3, the function f X + [0, oo) serves regularizer (analogous to the entropy function in smoothed FP), for which we impose the following requirement.
Condition 4.1. The function f(-) is continuously differentiable and stsonogyyy convex for some of > O. In addition, lim |/ [=((2) = +o0, where 0x' = X' relint denotes the boundary of the convex compact subset X' of R44
Differentiability and strong convexity are standard requirements when choosing regularizers. The condition that lim--ax [V)())) 222 = +oo ensures that the generalized FW direction 8t from Algorithm Line 3 always lies in the relative interior of X. These conditions are satisfied by, e.g.. the sum of negative entropies when the compact convex set X' is the product of probability simplicies. Note that when 7 = 0, the algorithm recovers the vanilla version of FW analyzed in [24] for saddle point problems. Although the use of regularization precludes the use linear minimization oracles (LMOs), which is one of the main features that make FW algorithms so appealing [34, 49), we remark that it does not add additional complexity to the algorithm when compared to projected extragradient and optimistic gradient methods. Specifically, note that the subproblem that appears in Algorithm 2 Line 3 is strongly convex optimization problem and can be solved efficiently or even admits closed-form solutions. For example, when X' the probability simplex and f(-) is the negative entropy, the FW direction is the softmax operator.
To derive our convergence guarantees, we impose the following assumptions on the operator F(-) and the stochastic process {wr}.
Assumption 4.1. The operator F(-) is Lipschitz continuous, i.e., there exists LF > 0 such that [[((z)) F(x2) ll < Lr||æ1 =22122 Væi, E X' Assumption 4.2. The operator F(-)) has Lipschitz continuous Jacobian matrix J(-), i.c. there exists L > 0 such that
[J(z))- < Ls|l= x2ll2, V01, X
In zero-sum games, due to the linear structure of F(.), the Jacobian matrix is the zero matrix. Therefore, Both Assumptions 4.1 and 4.2 are automatically satisfied. In optimization, F(.) is the

---

gradient of the objective function that we aim to optimize, and Assumptions 4.1 and 4.2 are equivalent to assuming the smoothness of the objective function [4] and the Lipschitz continuity of the Hessian matrix.
Assumption 4.3. It holds for all 2 that (1) 8 - We E X, (2) uu | Fi] - 0, (3) B w
Fi] S Iw where ow 0 and F, is the o-algebra generated by {zo, Wo. W1:"" (.--1)
When ow = 0, Algorithm is a deterministic algorithm. More generally, we allow for this additive martingale difference noise to capture the potential stochasticity in choosing the FW direction, which present in, e.g., smoothed FP, due to sampling an action according to the smoothed best response.
To state our main result for generalized FW in MVI problems, the following notation is needed. Let Dx max,ex ||=]|2, F maX [=) and f maX f(z). all of which are well defined and finite due to the Weierstrass extreme value theorem because F(() and f(-) are continuous functions and X' is a compact set. Next, we present the convergence guarantee on the iterates of Algorithm 2 when using stepsizes of various decay rates.
Theorem 4.1. Consider {ir} updated according to Algorithm Suppose that F()) is a monotone operator on X, and Assumptions 1,1, 4.2, and 4.3 are satisfied. Then, when the regularizer f(-) satisfies Condition 4.1, we have for all 2 0 that
12 F(1-a) + +2a++1 Tf, when ar = S 1,
max (5+ - -)) FF(F)))) S EEN
E
2Dx
ci log(t +
1 +Tf, when at t+1
t+1
t+1
where 01 (I.p 12z/(2TO)) + DxL,)(lw 4D2).
The proof Theorem 4.1 is presented in Appendix B.2. Note that for a given time horizon T, choosing T (TT11/2) results in an overall ((T-1/2) last-iterate convergence rate to a solution to the MVI problem. The problem-dependent constants Dx, F, and f appear additively or multiplicatively in the bound but do not impact the overall Ó(T-1/2) rate of convergence.
Corollary 4.1.1. To achieve Elmaxxex(xx s) F(x:)] e, the iteration complexity is ((--)).
This convergence rate matches the last-iterate convergence rate recently proved for extragradient and optimistic gradient algorithms for constrained MVI problems [15]. In contrast to the analyses of those algorithms which requires computer-aide aided proofs such as the sum of squares programming [15] or performance estimation problems [29], our proof follows from simple Lyapunov argument on the regularized gap ((),, which is defined as
((z-s) V(x)= max {(x ()--s) F(x) - [s(s))
(6)
A key step in proving Theorem 4.1 is the following lemma, which shows the smooth evolution of the generalized FW directions } J. For notation convenience, let s(x) = arg exn, ((()) for all x E X. Lemma 4.1. It holds for all x1, E X that [|a())) - -5(22) < ter || x2l12-
The proof of Lemma 4.1 is presented in Appendix B.1. As a last comment, note that while the O(2- convergence rate is known to be tight for extragradient and optimistic gradient algorithms [15, 25] (since they both can be seen as instantiations p-stationary canonical linear iterative algo- rithms), it is unclear whether this rate is tight for FW-type algorithms. We leave further explorations of fundamental lower bounds to future work. We also carried out experiments to numerically compare the performance of our algorithm with those proposed in the literature. Due to space limitation, the results are reported in Appendix D.
Generalized Frank Wolfe for Stochastic Monotone Variational Inequalities
We now analyze the case where instead of having an accurate F(-), we only have access to a noisy estimator of F(-). This happens often in optimization and machine learning, where we sometimes do not have enough information or enough computational power to fully evaluate the operator F(.). Note that this is different from the additive noise we in Algorithm 2 Line 4, which captures the stochasticity in choosing the FW direction.
7

---

In general, incorporating stochasticity into FW algorithms in optimization is known to be nontrivial when the variance of the noise, though bounded, not sufficiently small. When there is only access to noisy oracle for (z))), the stochasticity enters the algorithm in nonlinear manner through the computation of the smoothed FW direction. Consequently, developing algorithms with strong convergence guarantees becomes fundamentally more challenging. To illustrate this, suppose that we directly use a noisy estimate F(x:) + 2t (where &t represents the noise) in place of F((+)) in Algorithm 2 Line 3 to compute the FW direction st. Despite replacing the hardmin with a softmin (by introducing a regularizer), the FW direction 8t remains highly sensitive to the noise āt because the FW direction computed from the exact F(z,) and its noisy counterpart F(xz) + 2 could differ significantly. As a result, due to the lack of control over the noise, it has been observed that using a noisy estimator of the operator (.) in place of F-)) can lead to the divergence of the algorithm [16].
To overcome this issue, existing approaches to stochastic FW often build reduced-variance estimators of the operator F..). One of the most common methods to achieve this is by averaging the estimates. Inspired by this approach, we develop stochastic generalized FW algorithm for constrained MVI problems, where we first average the noisy estimates of F(()) through an iterative framework. This results in Algorithm presented in the following. For ease of exposition, we only present the algorithm with constant stepsizes.
Algorithm 3 Stochastic Frank- Wolfe for Monotone Variational Inequalities
1: Input: Integer T, tunable parameter T, and initialization 2a X and you RR..
2: for = 0, 1, ... T - do
3: 1/+11 y/+ + (xF(x)) + 2t y13
4: St arg min M1+1 + Ts(s)}
5: 2t+1 = 2t alx, - st)
6: end for
The key step in Algorithm 3 is Line 3, where we build sequence of estimators {8r} } for {F(x)) by averaging the newly observed noisy estimate F(xx) + 2 with past information. To illustrate, since Yt+1 is convex combination (with parameter 3) of the previous iterate yt and F(x;) + 22, see that for any t. y, is essentially a convex combination (hence a weighted average) of (F(z,) + 2; 2osisee-- Suppose that dı were stationary (i.e., 3y for some 2),, then y/2 effectively becomes variance- reduced estimator of F(r).. To extend this idea to time-varying Tt, we choose the stepsizes a and B such that B >> o, creating two-timescale structure [9]. This ensures that, from the perspective of yt. Te is nearly stationary, allowing to converge to F(xx) on a faster timescale. As result, the æt iterates should behave similarly the case where we have an accurate estimate of F(-). In Lemma 5.1, we show that this is indeed the case for the y-process.
To present the lemma, first formally state our assumption the noise sequence {2e}. Assumption 5.1. It holds for all 2 0 that B[2, Fi) = 0 and E = l Fi] 0g for some o; > 0, where F, is the o-algebra generated by {xo. yo, 20, 21, ... 1
The next lemma bounds the distance between the estimator ye and the desired target F(x:). The proof is presented in Appendix C.I.
Lemma 5.1. Suppose that Assumptions 4.1 and 5.1 are satisfied and 3 E 1). Then, we have for any 2 0 that
Ellly- F < (1 33 ) llvo F(x0)1++ 830 32T D2
(7)
g2
In view of the last term on the right-hand side of Eq. (7), to make Ellyy F(x, [|3] sufficiently small, we need the ratio between the stepsizes, i.e., a/3. to be sufficiently small. This mathematically justifies the two-timescale structure in Algorithm 3. Notably, Lemma 5.1 holds irrespective of the monotonicity of F-)) and only makes use of its assumed Lipschitz continuity. Using this lemma allows us to prove the following result for stochastic FW in constrained MVI problems.
Theorem 5.1. Consider (xt) generated by Algorithm 3. Suppose that P(.) a monotone operator on X, Assumptions 4.1, 4.2, and 5.1 are satisfied, and the regularizer f() satisfies Condition 4.
8

---

Then, when choosing B 882/3/3 (0,1), we have for any t 2 0 that
E max (s+- -)) S (1-(1aa)) 2202/3
oza2/3
Csca + ē5a + T
T
where fashsiss are problem-dependent constants. See Appendix C.2 for their explicit expressions.
proof sketch of Theorem 5.1 is presented in Section 6, and the complete proof can be found in Appendix C.2. Based Theorem 5.1, we have the following iteration complexity.
Corollary 5.1.1. To achieve Elmaxxexxar -s) F(z)) & c, the iteration complexity is Ö(c-))
Once again, we remark that, to the best of our knowledge, this appears to be the first algorithm with last-iterate convergence guarantee constrained stochastic MVI problems. The guarantees for variants of gradient-based algorithms are the averaged iterate under strong curvature assumptions on F() or X [8]. Numerical simulations are provided Appendix D to verify the last-iterate convergence of our proposed algorithm.
Our iteration complexity of Ō(E=") is slower than the O enjoyed by stochastic mirror-prox algorithms in an averaged-iterate sense [36]. Despite the fact that we have last-iterate convergence, we believe that the above bound is not tight since using the same estimator in convex optimization problems results in an Ō rate of convergence [45]. The reason for the potential looseness in our analysis is due to the fact that F-)) is not the gradient of a function and as such we must rely on the smoothness the estimated FW direction 8t, which results in a suboptimal relationship between the hyperparameter and E Bl[ly+ F(xx)) [
in our analysis.
6 Proof Sketch of Theorem 5.1
Here, we present an outline of the proof of Theorem 5.1, which uses Lyapunov-based arguments. The proof of Theorem 4.1 follows similar approach.
The first step in proving Theorem 5.1 is to establish Lemma 5.1, which shows that our constructed estimator indeed keeps track of the desired target F(x,).
6.1 Proof Sketch of Lemma 5.1
We will use llye F(ax)) 11 as Lyapunov function to study the evolution of yr. To begin with, for any 2 0, we have by Algorithm 3 Line 3 that
llve+1 F( I1 = [1(1 B)y. + + F(x++1)11
= [[(1 ()+ F(x.)) + + - 12
= (1 - -3)
|F(x)) +
F F(
+ 21 - B) F 4 + 232, (F(x)) - F(x++1))
+ 2(1 - B)(v -F(z))
F(I++1)).
Taking expectations conditioned on F, on both sides of the previous inequality, and using Assumption 5.1 for the noise sequence { along with some algebraic manipulations, we obtain
33 4) 1 F(a.))13 2,8
Elllu++1 F( 1) F
6 z E(1 - -
F(x++1)1 Fi).
The details are presented in Appendix C.I. By the Lipschitz continuity of F(-) (cf. Assumption 4.1),
we have
F F(x)) - F(
Fr) < Lr [ - x211 F
= LF 1e
Fd
- 4 D2.a?

---

where the equality follows from Algorithm 3 Line 5. Combining the previous two inequalities together, we obtain
3
11ve - F(x:)11 2 D
Bllly+1 F( [F) <
B
The final result follows by first taking total expectations on both sides of the previous inequality and then repeatedly using the resulting inequality.
6.2 Proof Sketch of Theorem 5.1.
Given the proof of convergence for our estimator 1/2 of F(x:), of Theorem 5.1. Let st arg min F(x++1) [s)). Using V--) defined in Eq. (6) as Lyapunov function, we have, after some algebra, that for any 2 0:
give overview of the proof
((*+1) & - (z) + (F())
(st - f + 2L, D'x
(8)
where Lv a problem-dependenn constant (cf. Lemma B.1). See Appendix C.2 for more details. remains to bound the term (xx)) (st 5t-1). Using Lemma 4.1, we have
F(x)) ( - S (1)))))
122lls -i-1ll2
FLF |1 - F(xx))l2
T
FLF (1lV+1 - Vell2 + l1ve - F(x:)ll2)
Toz
FLF (31[F(x++) vell2 + :11121112 + 11ve F(x))ll2 (Algorithm Line 3)
Taz
FLF (51121122 + 2// F(x))12))
I To,
where the last inequality follows from 3 1). Using the upper bound we obtained for the term F(x;)T (st 1) Eq. (8) and then taking total expectation on both sides of the resulting inequality, we have
FLrBa 01/² + Taz
2FLFa [1 F(x.)1 + D
E[V (Z)+1)) (1 - (V)(V(
Finally, substituting the upper bound we obtained for F[I(F( y 11 in Lemma 5.1 into the previous inequality and then repeatedly using it, we obtain the desired unite-time bound. The details are presented Appendix C.2.
Conclusion
In this work, we study generalized FW algorithms in constrained MVI problems. We show that the algorithm enjoys last-iterate convergence guarantees. As a consequence of our results, we prove the rate of convergence for smoothed FP. We believe that this class of algorithms warrants further exploration. While extragradient and optimistic gradient algorithms can be seen as approximations to be
proximal point algorithms and consequently FW algorithms and consequently generalized FW algorithms are not necessarily related to this ODE and can thus be viewed
discretizations of the ODE & = F(x).
class of algorithms for such problems.
An interesting future direction of this work is to develop results for the case where 7 = 0. This corresponds to the regime in which FW algorithms are particularly useful since they require no projection and instead only an LMO. However, as commented on in [24], without additional curvature assumptions X' besides convexity, this case seems fundamentally more difficult due to the potential non-uniqueness and non smoothnossss of the FW direction arg min F(x).
10

---

Acknowledgements
Z. Chen acknowledges support from the PIMCO Postdoctoral Fellowship. Mazumdar acknowl- edges support from NSF Award 2240110.
References
[1] Azizian, W. lutzeler, F., Malick, J., and Mertikopoulos, P. (2021). The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities. In Conference on Learning Theory, pages 326-358. PMLR.
[2] Bach, F. (2012). Duality between subgradient and conditional gradient methods. SIAM Journal on Optimization, 25.
[3] Bailey, J. P. and Piliouras, G. (2018). Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 321-338.
[4] Beck, A. (2017). First-Order Methods in Optimization, volume 25. SIAM.
[5] Ben-Tal, A., Ghaoui, L. E., and Nemirovski, A. (2009). Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press.
[6] Benaïm, M. and Faure, M. (2013). Consistency of vanishingly smooth fictitious play. Mathematics Operations Research, 38(3)4437-450.
[7] Bertsekas, D. (2016). Nonlinear Programming, volume 4. Athena Scientific.
[8] Beznosikov, A., Polyak, B., Gorbunov, E.,, Kovalev, D., and Gasnikov, A. (2023). Smooth monotone stochastic variational inequalities and saddle point problems: A survey. Eur. Math. Soc. Mag., 127:15-28.
[9] Borkar, V. (2009). Stochastic Approximation: A Dynamical Systems Viewpoint, volume 48. Springer.
[10] Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge university press.
[11] Bredies, K. and Lorenz, D. A. (2008). Iterated hard shrinkage for minimization problems with sparsity constraints. SIAM Journal on Scientific Computing. 30(2):657-683.
[12] Bredies, K., Lorenz, D. A., and Maass, P. (2009). A generalized conditional gradient method and its connection to an iterative shrinkage method. Computational Optimization and Applications, 42(2):173-19)) 193.
[13] Brown, G. W. (1951). Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374.
[14] Cai, X., Song, C., Guzmán, C., and Diakonikolas, J. (2022a). Stochastic Halpern iteration with variance reduction for stochastic monotone inclusions. In Advances in Neural Information Processing Systems, volume 35, pages
[15] Cai, Y., Oikonomou, A., and Zheng, W. (2022b). Tight last-iterate convergence of the extragra- dient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. Preprint 2rXiv:2204.09228.
[16] Chavdarova, T., Gidel, G., Fleuret, F., and Lacoste-Julien, (2019). Reducing noise in GAN training with variance reduced extragradient. Advances in Neural Information Processing Systems, 32.
[17] Chen, C., Luo, I.., Zhang, W., and Yu, Y. (2020). Efficient projection-free algorithms for saddle point problems. Advances in Neural Information Processing Systems, 13:10799-10808.
[18] Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, (2018). Training GANs with Optimism.
In International Conference Learning Representations.

---

[19] Diakonikolas, J. (2020). Halpern iteration for near-optimal and parameter- parameter-free monotone inclusion and strong solutions to variational inequalities. In Conference on Learning Theory, pages 1428-1451. PMLR.
[20] Dubois-Taine, B., Bach, F., Berthet, Q. and Taylor, A. (2022). Fast stochastic composite minimization and an accelerated Frank- Frank-Wolfe algorithm under parallelization.
[21] Frank, M., Wolfe, P., et al. (1956). An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):55-10.
[22] Fudenberg, D. and Levine, D. (1995). Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 1965):0065-189.
[23] Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S. (2019). A variational inequality perspective on generative adversarial networks. 7th International Conference on Learning Representations, ICLR 2019.
[24] Gidel, G., Jebara, T., and Lacoste-Julins S. (2017). Frank-Wore algorithms for saddle point problems. Artificial Intelligence and Statistics, pages 362-371. PMLR.
[25] Golowich, N., Pattathil, S., and Daskalakis, C. (2020a). Tight last-iterate convergence rates for no-regret learning in multi-player games. In Advances Neural Information Processing Systems, volume 33, pages 10766-207777
[26] Golowich, N., Pattathil, S., Daskalakis, C., and Ozdaglar, A. (2020b). Last iterate is slower than averaged iterate in smooth manvex-concave saddle point problems. In Conference on Learning Theory, pages 1758-1784. PMLR.
[27] Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2020). Generative adversarial networks. Communications of the ACM, 63(11):139-11)
[28] Gorbunov, E., Berard, H., Gidel, G., and Loizou, N. (2022a). Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pages 7865-7901. PMLR.
[29] Gorbunov, E., Loizou, N., and Gidel, G. (2022h). Extragradient method: (1/kk) last-iterate con- vergence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics, pages 366-402. PMLR.
[30] Gorbunov, E., Taylor, A., and Gidel, G. (2022c). Last-iterate convergence of optimistic gradient method for monotone variational inequalities. Advances in neural information processing systems, 35:21858-2188
[31] Halpem, B. (1967). Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6)9557 961.
[32] Hammond, J. H. (1984). Solving asymmetric variational inequality problems and systems of equations with generalized nonlinear programming algorithms. PhD thesis, Massachusetts Institute of Technology.
[33] Hofbauer, J. and Sandholm, W. H. (2002). On the global convergence of stochastic fictitious play. Econometrica, 206)22265-
[34] Jaggi, M. (2013). Revisiting Frank-Wolfe. Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pages 427- 435.
[35] Juditsky, A. and Nemirovski, A. (2016). Solving variational inequalities with monotone opera- tors on domains given by linear minimization oracles, Mathematical Programming, 156(1):221 256.
[36] Juditsky, A., Nemirovski, A., and Tauvel, C. (2011). Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17- -8.
12

---

[37] Korpelevich, G. (1977). Extragradient method for finding saddle points and other problems. Matekon, 13(4):35-49
[38] Kotsalis, G., Lan, G., and Li, T. (2022). Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning. SIAM Journal on Optimization, 32(2):1120-11 1055.
[39] Lan, G. (2020). First-Order and Stochastic Optimization Methods for Machine Learning. Springer.
[40] Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
[41] Lin, T., Zhou, Z.., Mertikopoulos, P., and Jordan, M. (2020). Finite-time last-iterate convergence for multi-agent learning in games. In Proceedings of the 37th International Conference on Machine Learning, pages 6161-6171.
[42] Mazumdar, E., Ratliff, L. J., and Sastry, S. S. (2020). On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131.
[43] Mertikopoulos, P., Papadimitriou, C., and Piliouras, G. (2018), Cycles in adversarial regular- ized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, page 2703-2717, USA. Society for Industrial and Applied Mathematics.
[44] Mishchenko, K., Kovalev, D., Shulgin, E., Richtárik, P., and Malitsky, Y. (2020). Revisiting stochastic extragradient.
[45] Mokhtari, A., Hassani, H., and Karbasi, A. (2018). Conditional gradient method for stochastic submodular maximization: Closing the gap. International Conference on Artificial Intelligence and Statistics, pages 1886-1895, PMLR.
[46] Mokhtari, A., Ozdaglar, A., and Pattathil, S. (2020). A unified analysis of extra extra-gradee grrriaagrddenttt and optimistic gradient methods for saddle point problems: Proximal point approach. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages 1497-1507.
[47] Nash, (1951). Non-cooperative games. Annals of mathematics, pages 286-295.
[48] Palaniappan, B. and Bach, F. (2016). Stochastic variance reduction methods for saddle-poin problems. Advances in Neural Information Processing Systems, 29.
[49] Pokutta, S. (2023). The Wolfe algorithm: A short introduction. Jahreshericht der Deutschen Mathematiker- Gathematiker-Veeriiniuug
[50] Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Program- ming. John Wiley & Sons.
[51] Rakhlin, A. and Sridharan, K. (2013). Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019. PMLR.
[52] Rockafellar, R. T. (1976). Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5)88778898.
[53] Rosen, B. (1965). Existence and uniqueness of equilibrium points for concave n- n-person games. Econometrica, 3303):520-534.
[54] Ryu, E. K. and Boyd, S. (2016). Primer on monotone operator methods. Appl. Comput. Math, 15(1)33433.
[55] Shannon, C. E. (1948). A mathematical theory of communication. The Bell system technical journal, 27(3):379 423.
[56] Stampacchia, G. (1964). Formes bilineaires coercitives sur les ensembles convexes. Académie des Sciences de Paris, 258:4413-444
[57] Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT press.
13

---

[58] Tran-Dinh, Q. and Luo, Y. (2021), Halpern-tyy type accelerated and splitting algorithms for monotone inclusions. Preprint arXiv:2110.08150.
[59] Von Neumann, J. and Morgenstem, O. (2007). Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition). Princeton university press.
[60] Yang. T., Jordan, M., and Chavdarova, T. (2022). Solving constrained variational inequalities via a first-order interior point-based method. In The Eleventh International Conference on Learning Representations.
[61] Yu, Y., Lin, T., Mazumdar, E. V., and Jordan, M. (2022). Fast distributionally robust learning with variance-reduced min-max optimization. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics.
[62] Zhang, K., Yang. Z., and Başar, (2021). Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321-384.
14

---

Appendices
A Proof of Theorem 3.1
Observe that Algorithm is a special case of Algorithm 2 with
R
n
F(x) = F( x
R
- R
J(x) = R
f(z) f( T -v(TT) - -v( ((())+++ + 1114(1
(((A)) 1
c(A)) - 2t
In addition, since max .² | a²)l < we have LF S VIA4IAA L, =
V [ f I log (1 of 1, ow S 8, and Dx S Now, applying Theorem 4.1 with or = 1/(1 + 1), since I 1, we have
| + |
36 36 log(1 + 1)
NG S
++1 + rog((AA*)
t+1
t
B Proof of All Technical Results in Section 4
B.1 Proof of Lemma 4.1
Since ST F(x) + fs(ss as a function of is To -stronngyy convex uniformly for all x E X' and the feasible set X' is convex and compact, there is a unique global minimizer to the optimization problem min {s + +f(s)) Moreover, since f()) is chosen such that limg-+ax [V)(s) = too (cf. Condition 4. the unique optimal solution to m F(x: [x))) must lie in the interior of the feasible set X. Therefore, for any æ1, 22 E X, we have by the first-order optimality condition that
F(a))+ +V((()))((( = 0, F(z2) + +V(((())) = 0.
follows that
F(z1) - F(x2) = - (V V
Using the a strongg convexity of (()) and Assumption 4.1, we have
tayl1s(<1) - s(x2))12 {=()V -V//(((
= =[]((x)) - F(22)ll2 < Lplla1 - 22112
which implies [|s(mr) s(x2))12 S tep || - 12l12-
B.2
Proof of Theorem 4.1
defined as V(x) = max,ex((> - F(x) rf(s)} - as our Lyapunov function. The goal here is to show that H, updated according Algorithm 2 produces negative drift with respect to V(.). The following lemma needed to establish the result.
Recall that we use V : x'' +
Lemma B.1. The Lyapunov function V--) Ly-smooth with respect to l|2. where Lv
2LF + LE + 2DxLJ.
To;
Proof of Lemma B.I. To show the smoothness of V(),, it is enough to show that the gradient operator (V is Lipschitz continuous. To compute the gradient of V-),, apply Danskin's 's theorem [7] and we have
VV(x) = =(x)) + [(x)
s(x)), V
15

---

where we recall that s(z) = arg max.ex - - F(z) - rs(s)) For any 21, E X' we have
- - - p(2)) - ((22) (22- - s(x2)) - - ((2)) + (zz) (z) 22 s(22) s(x1))
+ ((1))
+ - (x2 s(x2)).
Using triangle inequality, Assumption 4.1, Assumption 4.2, and Lemma 4.1, we obtain
[V()) VV(x2)ll2 < (1)())) F222)1l2 + || x2ll2 + [s(Ø2) s(11)ll2)
+ +1][(z1) - (zz2 )222) |||2||222222 - s(22)]l2
L - x2l12 + LF [1+ LF
- - + 2Dx ||= x2lle
TO,
2Lp + 12
+ +2DxIs ||] 111--221 x2ll2
To,
= Lv||z1 - 12
Now, we are ready to prove Theorem 4.1. Using the smoothness of V(.). the explicit expression of VV (az) (both established in Lemma B.1), and the update equation in Algorithm 2 Line 3, have for any & 2 0 that
((*+1) (V(x) VV(x)) (1 -xt) + Lv
x++1 - -xell2
=V(x,) (F(((z)) + ((x)) (aee))(z) (xx -s)) ( (Ire st + we) Lva?
|| - 8: + well2
= =V(x)) (xte) T (xx - st + wi) - ailxz 80) T [axe + wt)
Lv
+ 2
|| St + w/ 11..
Taking expectations on both sides of the previous inequality, since {w²) is a martingale difference sequence, have
E[V(4+)) S [x:()))] + (xEE(F(xx))
T(: 2.)1 a.E(( 82) ((x) st)l
Lva
Bl w [
2
Next, we bound each term on the right-hand side the previous inequality.
For the first term the right-hand side of Eq. (9), observe that
xx) < - F(xx)) (xz - st) + +T((s)) = (ax))
Therefore, we have
E (F)) (st -x:]]= - (x))]
(10)
For the second term on the right-hand side of Eq. (9), since F(.) is monotone, the Jacobian matrix J(-) is positive semidefinite. Therefore, we have
B[( st) J(xe)( st) 2 0.
(11)
For the third term on the right-hand side of Eq. (9), using Assumption 4.3, we have
E E| St + w. [
E El| 22 seli ||w +((x, ss) we] < <DD> + Tw.
(12)
Combining Eqs. (10), (11), and (12) with Eq. (9), we have
B[V(z.41) < - -VV + Lv Lv(ADz +w ow
16

---

= (1 a. [VV + qaaz
where we denote 0₁ = Lv + 2 2 for simplicity of notation. Repeatedly using the previous inequality, have for all 2 0 that
([V(
II - (z))) + Σ
o
II (1-a)).
j=1
1=0
J=i+1
Finally, since
max 8) F((x) - Tf VVxx < max(# 8) -ax(x= F((x) = 2DDx VxEd, #EA
we have for all 2 that
E
max (2+ s) T) F(xi) < 22Dx a1)+ Σ ai
2
II (1- 1
+ (13)
=EX
j=l
j=i+1
Constant Stepsizes.
When a₁ = we have
--1 II a5) (1) and
t-1
Σ of II (1-a;)sa
1=0
j=1+1
follows from Eq. (13) that
m) F(zi)) $2Dx - a +ca+rf.
E
max
EEN
Diminishing Stepsizes.
When at 1/(t+ 1) for all 0, we have
j 1
0.)
j+1 t+1
and
Σ
II
(1-
1
log(l 1)
+ 1)²
j j+11
(i+1)
++1
t=
j=++
==0
j=it1
It follows that
2DxF
log(t + 1)
E max(x: EEX
8) F(xx)
+ Tf.
t+1
t+1
C Proof of All Technical Results in Section 5
C.1 Proof of Lemma 5.1
For any t 2 0, we have
|| F(I++ 1l1 = 1[(11 B)y, + ((F(x.) + 2.) - F(I++))1
= =|[(1 () F(xi)) B2, + F(xz) - F(
(1 8))1ly: F(xx))l 11 + ||((x)))
F(
+ 2(1 - B) (yx - F(x.)) ((rr) ((F(tt) - -F(x++1)
28 2 (F(x.) F(141) +2(1 B) F(x:)) z. (14)
:=B2
Using Cauchy-Schwarz inequality, have
E1 (y:- F(xi)) (F(z)) ((Fx))((((I)) - F(z441))
17

---

1 ((21))221F((1) F(
IA
8
11 F + 3 [F(())) - F(241))l
where the last inequality follows from a² 12 2 2ab for any a, b R. Similarly, also have
E2 = (F(x)) - F(2++1))
< $ (xx))
F(x++1)ll2
8
1
2 2 1
28 F(
F
Combining the previous two inequalities with Eq. (14) and then taking expectations both sides, we obtain
Ellve++ F ((
112)
(1 B)l ((:))) + B + (()) - F(x++))
3
Bllly= F(xr))1ll B[1 ((.)) - 1(
4
+ -+ + Bl|l (2+) F( )
+ 211 - 3) F(x))) T FiI]
38
Billy= - F(x))l 2 + B
(())) - F( 1
4
where the last line follows from Assumption 5.1 and the fact that B E 1). It remains to bound the term Eg on the right-hand side of the previous inequality. Observe that (()) F F(x++1) 1 I|
- L [|[ 21+1 221
(Assumption 4.1)
2 B[[ss xel1a)
(Algorithm Line 5)
< 4 Di.aa.
Therefore, we have
3,3
24
E[llu++ F(+++)))) <
E El F(x:) +88
Repeatedly using the previous inequality, we obtain
3 ) 1lvo F( +
830
32T D2 D2
E [llee F(x+)11)] <
g2
C.2 Proof of Theorem 5.1
Recall that s = arg min F((+21)))))))))))))))))))))))()) (s))- Using the smoothness of V(+), the explicit expression of Vz,,), (both established in Lemma B. 1), and the update equation in Algorithm 3 Line 5, we have for any 2 0 that
((z+11) & (xx) + VV(x:) [(1+1 - xx) + Ly
| - xell2
2
Iv
= =v(x)) a(F(z)) + [(z) Tx:= - ss)) T -si) +
||: - sell2
2
Lva² 2
=V(x,) aF(x)) (x, st) a(æ, - J -s)
|| 1
2
<V(x;) aF(x)) T (z, - 3t) + 2Lv D2aa²
(J(-) is positive semidefinite)
V (w+) (f (x, - s - af af [s - + 2L, Dz
< (1 (x,) + af (s, . + 2Ly Dz
(15)
where the last line follows from the definition of V-). To proceed, observe that F(xx) [st
18

---

FLF
11t+11 - F2
(Lemma 4.1)
T0z
FLF (1ye+1 - yell2 + llve - F(x))ll2)
TOz
FLF (311F((z)) - Vell2 12 + 311=x112 + llve F(x))l12 (Algorithm 3 Line 3)
rØz
FLF (3112:112 2 F()))l2),
where the last line follows from 3 E (0. 1). Combining the previous inequality with Eq. (15), we have
FL ((I++1) s -1- aV)
2FLFa
11ye F(x:) + 2Lv a
Tos
Taking expectations both sides of the previous inequality, we have
FLyBa 1/2 +
2F 2F 11/2 LF
[[((4++1) -1 (1-aa)
F(x;) + 2L Dz
Toz
TO,
where we used 2 I 11
+1:2 E E | Fill I 02 and Ell F(xe)11a) s
El/lIl - Fxx)) [. Using Lemma 5.1 to bound Bllle 11)) we have
FLrßa 1/2
E[V (1- (xx))
2Lv 0=
Taz
2FLFa Toz
33
f/2
11yo F(xo)]12 + /2//2 6L 1/2 Dxa
4
where we use va+b+c S Va + vb + ve for any a, b,c 2 Repeatedly using the previous inequality, since choosing 2/3 /3 implies 33/4 S (1 a33,, we have
FL 1/2
2F 2F t (1 a)'-1 I1y0 F(20)l12
To
To,
2FLF
6LF
1/2
Dxa
381/2 1/22
2Lv D2
TØ
Using 3 S/2/3/3 E (0, 1) (which also implies
a) and the explicit expression of Ly from
Lemma B.1 in the previous inequality. we have
8FL 1/2
2/3
2FLF t11 a)¹ 1l80 F(ro)ll2
((- +
3TOS
18FLF TOJ
LF Dx
1/2
D
1/2
2/3 + +ALF D²a+
To₁
Recall that
SEX (ax F(x) V(x) < max(x- s) s 22Dx VxE..
Therefore, obtain the following finite-time bound:
E max(x, -8) 3)FF(x,)) SEX
8FL 1/2 2/3
2FLF (1- | a -((o))la
< <2Dx 22DxF(1-o) (1- a)²
3raj
Toz
18FLF
1 Dx
212 D2
0
1/2
1/3 + +4(FF + D2
a + of
T0
4
To
19

---

C20///3
Cza2/3 E
=ā (1 aa) a)*
+ Ezat + TS,
where
2F Toz
18FLF
LF
1/2 Dx
8F F 1/2
C1 12=
1130 - F(xo)ll2
02
01/2
83
of
4
30
2
44
25 = 4(LF + Dx
of
The proof is complete.
D Numerical Simulations
In this section, conduct numerical simulations to empirically verify the performance of our proposed algorithms.
D.1 Generalized Frank-Wolfs
We compare the performance of Algorithm 2 with the extragradient method, both of which provably enjoy an (T-1//2 rate of last-iterate convergence.
Recall that the MVI problem aims to find an x¹ E Rd such that max,ex(<* - F) < According to [15], the extragradient algorithm initializes zo X' and update I iteratively according to the following formula:
1++1/2 = (x - aF)))), 2++1 = [x - aF (Fx+1/2))
where (-x(-) the projection operator onto X' with respect to || 112.
D.1.1 Rock-Paper-Scissorr Game
The Rock-Paper-Seisson game is classic example of a zero-sum game, where each player has three actions: Rock, Paper, Scissors. The rules are such that Rock beats Scissors, Scissors beat Paper, and Paper beats Rock. both players choose the same move, the game results tie. The payoff matrix for the player (i.e., the row player) can be represented follows:
Rock
Paper
Scissors
Rock
0
-1
Paper
1
0
-1
Scissors
-1
The results for implementing generalized FW and the extragradient method are reported in Figure 1.
D.1.2 The Burglar-Policeman Matrix Game
The Burglar-Policemaat matrix game is another classic zero-sum game. The burglar wants to avoid being caught, while the policeman wants to catch the burglar. In this game, the actions available to both players are to either "Stay" at their current position or "Switch" to another location. The payoff matrix for the burglar can be represented as follows:
Policeman Stay
Policeman Switch
Burglar Stay
1
Burglar Switch
-1
The results for implementing generalized FW and the extragradient method reported in Figure 2. In either the Rock-Paper- Paper-Scissors Game the Ponglar-Policeman Matrix Game, both algorithms seem to have similar performance. However, the extragradient method seems to be more stable.
20

---

2
Generalized Frank-Wolte
1.8
Extragradient Mathod
1.6
1.4
Nash Gap
1.2
0.8
0.6
0.4
0.2
50
100
150
200
Number of Iterations
Figure 1: Convergence Rate Comparison for the Pape---apes Game
Generalized Frank-Walfe
0.9
Extragradient Mathod
0.8
0.7
Nash Gap
0.6
0.5
0.4
0.3
0.2
0.1
0
100
200
Number Iterations
Figure 2: Convergence Rate Comparison for the
Matrix Game
D.1.3 A Randomly Generated Matrix Game
In this experiment, we choose F(x) = Mr and = 100 x 100 where A 100 denotes the 100- dimensional probability simplex. The matrix M is chosen be M 10000100 -R; R 100xx100] where R. E R 1000x00d is randomly generated matrix. The MVI problem can alternatively be interpreted as a zero-sum game with the payoff matrix being R. The results are reported in Figure 3.
From the numerical simulations, we see that the generalized FW algorithm seems to slightly outper- form the extragradient algorithm the beginning. However, asymptotically, the extragradient method seems to perform better. This makes intuitive sense as using the softmax in the generalized FW algorithms results in a bias that depends on r. The numerical simulations verify that the generalized FW algorithm indeed holds practical potential.
21

---

0.9
Frank-Wolte
0.8
Extragradienl Method
0.7
0.6
Nash Gap
0.5
0.4
0.3
0.2
0.1
200
400
600
800
1000
Number of Iterations
Figure 3: Convergence Rate Comparison for
D.2 Stochastic Generalized Frank- Wolfe
Since none of the existing algorithms (e.g., the extragradient method, the optimistic gradient method, and the Halpem iteration method) have provable convergence in the stochastic setting, we will only verify the convergence of our algorithm here. The experiment setup the same as in Appendix D.1.3 except that F(z) is replaced by F(x)) + where is bounded random variable.
1.2
Stochastic Generalized Frank-Wolfe
Standard Deviation
Gap(ar) max, (a a) ((())
0.8
0.6
0.2
0
200
400
600
800
1000
Number of Iterations
Figure 4: Convergence of Algorithm
In the stochastic setting, we choose = 0.1, = 0.1, and 8 = 0.01 in Algorithm 3. The result is reported in Figure 4. From Figure 4, we see that Algorithm indeed converges, the stochasticity and the fact that we are using constant stepsizes, which agrees with Theorem 5.1. The fact that our algorithm stable in the stochastic setting highlights one of its main advantages compared with the existing methods.
zero due to
22

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
This paper develops theoretical guarantees for a generalized variant of Frank-Wolfe
in solving monotone variational inequality problems, which is clearly stated in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations discussed throughout the paper along with the presentation of the results.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory Assumptions and Proofs
Question: For each thcoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
23

---

Justification: A short proof sketch of the main results is presented in the main paper to provide intuition. The complete proof of each theoretical result is presented in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have provided detailed description of our experimental setup.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
example, if the contribution
While NeurlPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily architecture clearly and fully.
model architecture, the paper should describe the
(c) the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users). but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: This paper is a theoretical work, and the numerical simulations are conducted on synthetic examples to demonstrate the effectiveness of the proposed algorithm.

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (tttps:://iis..c
guides/ Luiiee/CooeSuumit htte//ooeSubiiiseeee oassoniccyc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed the results. See the NeurIPS code and data submission guidelines (https: //iiss.p.oo///// wttppp.cpppuiiipettteeeteepppppp pubbic/ Priides/CodeSubee issi onPolicy) for more details.
reproduce
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We have provided detailed description of our experimental setup.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The algorithms used in numerical simulations are deterministic algorithms. There- fore, there no need for error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard enror of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
25

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [No]
Justification: This paper is theoretical work, and the numerical simulations are conducted synthetic examples to demonstrate the effectiveness of the proposed algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics https://neurips
Answer: [Yes]
Justification:
This is theoretical work and does not have societal impact or harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there a special consideration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point out that
26

---

The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license the derived asset (if it has changed) should be provided.
If this information
available online, the authors are encouraged reach out the asset's
creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release assets.
Guidelines:
The answer NA means that the paper does not release assets.
27

---

Researchers should communicate the details of the dataset/code/mmodl as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/revieww based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
28


Reviews:
[{"review_id": "6d1OfgChk0", "reviewer": "Reviewer_BD4Y", "summary": "This paper proposes a Frank-Wolfe algorithms for solving monotone VI problems, for both deterministic and stochastic settings, proof that the first one matches the optimal convergence rate, and provide last-iterate convergence guarantees for the second one, which is a novelty if no curvature requirement is imposed on neither set nor operator.", "questions": "Typos and notation related remarks:\n- page 1, line 19: \\to is more convenient than \\mapsto\n- page 2, sentence at line 91: \"the algorithm has been shown to diverge\" is unclear, you have just mentioned the algorithm you have proposed, and it does not diverge, so which one does?\n- page 3, line 106: in phrase \"in either the uncontrained regime [13 ] or under\", \"in\" should be after \"either\", and \"uncontrained\" has typo\n- page 4, line 146: subscript and superscript for A are confused\n- Condition 4.1 allows one to remove limit s \\in X of max in line 3 of Algorithm 2, at least in accordance with line 217\n- page 6, line 228: \"make ... assumptions\" or \"impose ... requirements\" \n\nBesides, the \"shadow\" indicating the std of function's values from multiple random runs should be added to the plots with stochastic Frank-Wolfe method.", "limitations": "The limitations are clear from reading.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The analogy between classical game theory algorithm and Frank-Wolfe is simple yet creative and fruitful for providing theoretical guarantees for the former one. The operator smoothing approach in the design of the stochastic algorithm is also elegant and effective. I consider this paper worth reading thanks to these theoretical findings. Numerical experiments are also needed, but they show no significant advantage over alternative approaches, so the contribution of the paper seems only theoretical.", "weaknesses": "Despite the theoretical focus of the paper, it is recommended to make experiments more contentful by considering other problems, at least games like Burglar-Policeman matrix game, or some more advanced example of VI, maybe involving the adversarial NN. Regarding the theory, I see no significant flaws.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Comment: Despite the theoretical focus of the paper, it is recommended to make experiments more contentful by considering other problems ...\n\n**Response:** We thank the reviewer for the suggestion. In the next version, we will include an additional numerical example to demonstrate the performance of the generalized Frank-Wolfe algorithm relative to other algorithms.\n\n>Comment: Typos and notation related remarks.\n\n**Response:** We thank the reviewer for carefully reading our work. We will fix the typos and notation-related problems on pages 1, 3, 4, Condition 4.1, and page 6 as pointed out by the reviewer. Regarding the sentence ‘the algorithm has been shown to diverge’ in line 91 of page 2, it refers to the extragradient algorithm. We will clarify this in the next version of our work. \n\n\n>Comment: Besides, the \"shadow\" indicating the std of function's values from multiple random runs should be added to the plots with stochastic Frank-Wolfe method.\n\n**Response:** We will plot the standard deviation for the stochastic Frank-Wolfe algorithm in our numerical simulations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A6h4GGSVsY", "reviewer": "Reviewer_EbDg", "summary": "This paper presents combines Frank-Wolfe algorithm and entropy regularization trick to propose a generalized Frank-Wolfe algorithm for solving MVI problems. The paper proves $O(T^{-1/2})$ last-iterate convergence rate for the deterministic case. And it extends the algorithm to stochastic MVIs with $O(T^{-1/6})$ last-iterate convergence rate.", "questions": "-", "limitations": "Yes.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. I think it's a good idea to combine entropy regularization with FW algorithm.\n\n2. The paper is very well written and easy to follow. The intuition for the proposed algorithms is well explained. The assumptions are standard and clearly listed. The dependence of the convergence rates on everything is explicitly written out.\n\n3. Strong theoretical guarantees are provided in this paper. For example, it gives the first last-iterate convergence guarantee for constrained stochastic MVIs without strong curvature assumptions. It also gives the first finite-time analysis of smoothed FP.\n\n4. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.", "weaknesses": "I think there's no apparent weaknesses. I suspect the analysis for the stochastic case might not be tight, leaving room for improvement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Comment: I think there's no apparent weaknesses. I suspect the analysis for the stochastic case might not be tight, leaving room for improvement.\n\n**Response:** We greatly appreciate the reviewer acknowledging the contributions of our work. We agree with the reviewer that the convergence rate of $O(1/T^{1/6})$ in the stochastic setting is likely sub-optimal. Improving the convergence rate (by algorithm design or by analysis) is an immediate future direction of this work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lYQa2YM0Mf", "reviewer": "Reviewer_UPhr", "summary": "This paper focuses on solving the monotone MVI. To address this problem, the authors propose a new algorithm, which is a generalized variant of the Frank-Wolfe method. They also investigate the $O(T^{-½})$ last-iterate convergence, which matches the best-known results in this context. Additionally, they present an $O(T^{-⅙})$ last-iterate convergence in the stochastic setting, which is, to their knowledge, the first last-iterate convergence result for solving constrained stochastic MVI problems.", "questions": "* From my understanding, the key idea of the Frank-Wolfe method lies in the linear minimization oracle (LMO), which has been shown to be more efficient in computation [1]. In the proposed generalized Frank-Wolfe method, the additional regularizer disrupts the linear structure of the minimization problem. If we choose the regularizer to be a quadratic function, then line 3 of your algorithm reduces to the projection onto the feasible set $\\mathcal{X}$. Therefore, I would like to know if there are any advantages compared to those projection-based algorithms, such as EG/OGDA? Would it be possible to provide an explanation of it from both theoretical aspect and empirical performance? \n\n* In line 808 of your proof, the second equality is from the update of $x^{t+1}$. I think it lost the $w^t$ part. I am not sure whether this ignored part will influence the convergence rate you derived.\n\n* Could you please elaborate more on the introduction of the momentum step for gradient estimation $y^t$ in Algorithm 3? Is it essential for the convergence in the stochastic version? If so, could you provide the motivation for how it guarantees convergence?\n\n[1] Combettes, Cyrille W., and Sebastian Pokutta. \"Complexity of linear minimization and projection on some sets.\" Operations Research Letters 49.4 (2021): 565-571.", "limitations": "The convergence analysis heavily depends on the regularizer to ensure the Lipschitz property of the solutions of the minimization problem (see Lemma 4.1). When $\\tau=0$, it reduces to the FW algorithms, and its analysis is not provided. The authors also mention this in the conclusion.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written and easy to follow.\n\n* The authors establish the first last-iterate convergence result for solving constrained stochastic MVI problems.\n\n* They demonstrate the last-iterate convergence result for the proposed generalized Frank-Wolfe method. Instead of using computer-aided proofs such as SOS and performance estimation, their analysis primarily relies on the Lyapunov argument.", "weaknesses": "See the Questions part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Comment: From my understanding, the key idea of the Frank-Wolfe method lies in the linear minimization oracle (LMO) ...\n\n**Response:** We agree with the reviewer that by adding a regularizer, one can no longer use an LMO to find the Frank-Wolfe direction. However, also due to the regularizer, the problem of finding the Frank-Wolfe direction becomes a strongly convex optimization problem, which can be solved efficiently, or even admits closed-form solutions (such as in zero-sum games). Therefore, the additional computational challenge in obtaining the Frank-Wolfe direction is not an issue.\n\nCompared with related projection gradient-based algorithms, such as EG, in the deterministic setting, we do not see any clear advantage, as they both achieve the same rate of convergence and similar empirical performance (see Appendix E Figure 1). In the stochastic setting, our method has a clear advantage since it is provably convergent while EG is shown to be unstable in general (see reference [15] in our work). In the next version of this work, we will provide a more extensive numerical study to compare the performance of generalized Frank-Wolfe to EG and OG.\n\nThat being said, the goal of this paper was not to propose an algorithm that outperforms existing benchmarks. In recent years, existing studies of monotone variational inequalities have primarily focused on gradient-based algorithms such as EG and OG. On the other hand, Frank-Wolfe is also a natural algorithm (but is, to some extent, overlooked), and has a nice connection with fictitious play in zero-sum games. We study this algorithm and show that with a simple modification (that is, adding a regularizer), the convergence rate of Frank-Wolfe matches with that of EG and OG in the deterministic setting and is provably convergent in the stochastic setting.\n\n>Comment: In line 808 of your proof, the second equality is from the update of $x_{t+1}$. I think it lost the $w_t$ part. I am not sure whether this ignored part will influence the convergence rate you derived.\n\n**Response:** We greatly appreciate the reviewer for carefully reading our work. The missing $w_t$ in Line 808 was indeed a typo. Next, we present a fix to this issue. We start with the decomposition of the term $E_1$ in Line 808:\n\n$$E_1=(s_t-s_{t+1})^\\top (F(x_{t+1})-F(x_t))+(x_t-s_t)^\\top (F(x_{t+1})-F(x_t))\\quad\\qquad (1)$$\n\nFor the first term on the right-hand side of the previous inequality, we have by Assumption 4.1 and Lemma 4.1 that\n$$\n(s_t-s_{t+1})^\\top (F(x_{t+1})-F(x_t))\\leq \\vert|s_t-s_{t+1}\\vert|\\vert|F(x_{t+1})-F(x_t)\\vert|\n\\leq \\frac{L^2}{\\tau \\sigma_f}\\vert|x_{t+1}-x_t\\vert|^2.\\quad (2)\n$$\nThis is the same as what we did in Line 808 (from the first inequality to the third inequality). \n\nThe typo was with our approach in bounding the second term on the right-hand side of Eq. (1). Next, we present a different approach to bound it, which requires the following additional but mild assumption.\n\n**Assumption:** The Jacobian matrix $J(\\cdot)$ of the operator $F(\\cdot)$ is Lipschitz continuous.\n\nSince $F(\\cdot)$ is Lipschitz continuous (Assumption 4.1), its Jacobian matrix is well-defined almost everywhere. Assumption imposes a mild smoothness condition on the Jacobian matrix, which is automatically satisfied in the zero-sum game setting, where the operator $F(\\cdot)$ is a linear operator. Note that the monotonicity of $F(x)$ implies that $J(x)+J(x)^\\top$ is a positively semidefinite matrix for any $x\\in\\mathcal{X}$. \n\n\nDenote the Lipschitz constant of $J(\\cdot)$ as $L_J$. To proceed, in view of the second term on the right-hand side of Eq. (1), for a given $v\\in\\mathbb{R}^d$, consider the function $g_v(x)=v^\\top F(x)$. Since\n$$\\vert|\\nabla g_v(x_1)-\\nabla g_v(x_2)\\vert|=\\vert|(J(x_1)-J(x_1))^\\top v\\vert|\\leq L_J\\vert|v\\vert|\\vert|x_1-x_2\\vert|,$$\nthe function $g_v(x)$ is an $L_J\\vert|v\\vert|$-smooth function with respect to $x$. Therefore, using the descent lemma, we have for any $x_1,x_2\\in\\mathcal{X}$:\n$$g_v(x_2)-g_v(x_1)\\leq (x_2-x_1)^\\top J(x_1)^\\top v+\\frac{L_J\\vert|v\\vert|}{2}\\vert|x_1-x_2\\vert|^2.$$\nIdentifying $v=x_t-s_t$, $x_1=x_t$, and $x_2=x_{t+1}$ in the above inequality, the second term on the right-hand side of Eq. (1) can be bounded as follows:\n$$(x_t-s_t)^\\top (F(x_{t+1})-F(x_t))\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad$$\n$$\\leq (x_{t+1}-x_t)J(x_t)^\\top (x_t-s_t)+\\frac{L_J\\vert|x_t-s_t\\vert|\\vert|x_{t+1}-x_t\\vert|^2}{2}\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad$$\n$$= -\\alpha_t(x_t-s_t+w_t)J(x_t)^\\top (x_t-s_t)+\\frac{L_J\\vert|x_t-s_t\\vert|\\vert|x_{t+1}-x_t\\vert|^2}{2}\\qquad\\qquad\\qquad\\qquad\\qquad$$\n$$\\leq -\\alpha_t(x_t-s_t)^\\top \\left[\\frac{J(x_t)+J(x_t)^\\top}{2}\\right] (x_t-s_t)-\\alpha_tw_t^\\top J(x_t)^\\top (x_t-s_t)+\\frac{2L_JD_{\\mathcal{X}}}{2}\\vert|x_{t+1}-x_t\\vert|^2$$\n$$\\leq -\\alpha_tw_t^\\top J(x_t)^\\top (x_t-s_t)+\\frac{2L_JD_{\\mathcal{X}}}{2}\\vert|x_{t+1}-x_t\\vert|^2\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad(3)\n$$\nwhere the first equality follows from the update equation for $x_t$, the second inequality follows from $\\vert|x_t-s_t\\vert|\\leq \\vert|x_t\\vert|+\\vert|s_t\\vert|\\leq 2D_{\\mathcal{X}}$ (recall that $D_{\\mathcal{X}}$ is the radius of the feasible set), and the last inequality follows from $J(x_t)+J(x_t)^\\top$ being a positively semidefinite matrix (due to the monotonicity of $F(\\cdot)$).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tLzPqsstjt", "reviewer": "Reviewer_3YVN", "summary": "The paper presents a regularized version of Frank-Wolfe algorithm for monotone variational inequalities for which the authors an $\\tilde{O}(T^{-1/2})$ convergence rate of the last iterate. In the stochastic case, using the variance reduction technique, the authors show an algorithm that enjoys $\\tilde{O}(T^{-1/6})$ last-iterate convergence.", "questions": "Could the authors address my questions mentioned above? I would be happy to increase my score if these concerns are addressed adequately.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The presentation and the analysis of the paper are mostly straightforward and easy to follow.\n- Using regularization and variance reduction is a simple idea but it appears to work quite well.", "weaknesses": "1. There are some major issues with the proofs in the paper, as follows\n- In Line 808, second equation, $w_t$ does not appear. How would the authors fix this issue? It seems non-trivial to me, although in the easier case when $w_t=0$, the proof will work.\n- Lemma 4.1: The optimality condition here is usually considered a very strong, ie, there exists a point such that the gradient = 0, especially when the function considered changes according to $x$. \n- The assumption that there exists $\\bar{F} = \\max ||F(x)||_2$ seems unusual and strong and the dependence of the convergence on $\\bar{F}$ is not convincing to me.\n2. Empirically, there is a gap between extragradient and the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Comment: In Line 808 second equation, $w_t$ does not appear. How would the authors fix this issue? It seems non-trivial to me, although in the easier case when $w_t=0$, the proof will work.\n\n**Response:** We greatly appreciate the reviewer for carefully reading our work. The missing $w_t$ in Line 808 was indeed a typo. Next, we present a fix to this issue. We start with the decomposition of the term $E_1$ in Line 808:\n\n$$E_1=(s_t-s_{t+1})^\\top (F(x_{t+1})-F(x_t))+(x_t-s_t)^\\top (F(x_{t+1})-F(x_t))\\quad\\qquad (1)$$\n\nFor the first term on the right-hand side of the previous inequality, we have by Assumption 4.1 and Lemma 4.1 that\n$$\n(s_t-s_{t+1})^\\top (F(x_{t+1})-F(x_t))\\leq \\vert|s_t-s_{t+1}\\vert|\\vert|F(x_{t+1})-F(x_t)\\vert|\n\\leq \\frac{L^2}{\\tau \\sigma_f}\\vert|x_{t+1}-x_t\\vert|^2.\\quad (2)\n$$\nThis is the same as what we did in Line 808 (from the first inequality to the third inequality). \n\nThe typo was with our approach in bounding the second term on the right-hand side of Eq. (1). Next, we present a different approach to bound it, which requires the following additional but mild assumption.\n\n**Assumption:** The Jacobian matrix $J(\\cdot)$ of the operator $F(\\cdot)$ is Lipschitz continuous.\n\nSince $F(\\cdot)$ is Lipschitz continuous (Assumption 4.1), its Jacobian matrix is well-defined almost everywhere. Assumption imposes a mild smoothness condition on the Jacobian matrix, which is automatically satisfied in the zero-sum game setting, where the operator $F(\\cdot)$ is a linear operator. Note that the monotonicity of $F(x)$ implies that $J(x)+J(x)^\\top$ is a positively semidefinite matrix for any $x\\in\\mathcal{X}$. \n\n\nDenote the Lipschitz constant of $J(\\cdot)$ as $L_J$. To proceed, in view of the second term on the right-hand side of Eq. (1), for a given $v\\in\\mathbb{R}^d$, consider the function $g_v(x)=v^\\top F(x)$. Since\n$$\\vert|\\nabla g_v(x_1)-\\nabla g_v(x_2)\\vert|=\\vert|(J(x_1)-J(x_1))^\\top v\\vert|\\leq L_J\\vert|v\\vert|\\vert|x_1-x_2\\vert|,$$\nthe function $g_v(x)$ is an $L_J\\vert|v\\vert|$-smooth function with respect to $x$. Therefore, using the descent lemma, we have for any $x_1,x_2\\in\\mathcal{X}$:\n$$g_v(x_2)-g_v(x_1)\\leq (x_2-x_1)^\\top J(x_1)^\\top v+\\frac{L_J\\vert|v\\vert|}{2}\\vert|x_1-x_2\\vert|^2.$$\nIdentifying $v=x_t-s_t$, $x_1=x_t$, and $x_2=x_{t+1}$ in the above inequality, the second term on the right-hand side of Eq. (1) can be bounded as follows:\n$$(x_t-s_t)^\\top (F(x_{t+1})-F(x_t))\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad$$\n$$\\leq (x_{t+1}-x_t)J(x_t)^\\top (x_t-s_t)+\\frac{L_J\\vert|x_t-s_t\\vert|\\vert|x_{t+1}-x_t\\vert|^2}{2}\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad$$\n$$= -\\alpha_t(x_t-s_t+w_t)J(x_t)^\\top (x_t-s_t)+\\frac{L_J\\vert|x_t-s_t\\vert|\\vert|x_{t+1}-x_t\\vert|^2}{2}\\qquad\\qquad\\qquad\\qquad\\qquad$$\n$$\\leq -\\alpha_t(x_t-s_t)^\\top \\left[\\frac{J(x_t)+J(x_t)^\\top}{2}\\right] (x_t-s_t)-\\alpha_tw_t^\\top J(x_t)^\\top (x_t-s_t)+\\frac{2L_JD_{\\mathcal{X}}}{2}\\vert|x_{t+1}-x_t\\vert|^2$$\n$$\\leq -\\alpha_tw_t^\\top J(x_t)^\\top (x_t-s_t)+\\frac{2L_JD_{\\mathcal{X}}}{2}\\vert|x_{t+1}-x_t\\vert|^2\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad(3)\n$$\nwhere the first equality follows from the update equation for $x_t$, the second inequality follows from $\\vert|x_t-s_t\\vert|\\leq \\vert|x_t\\vert|+\\vert|s_t\\vert|\\leq 2D_{\\mathcal{X}}$ (recall that $D_{\\mathcal{X}}$ is the radius of the feasible set), and the last inequality follows from $J(x_t)+J(x_t)^\\top$ being a positively semidefinite matrix (due to the monotonicity of $F(\\cdot)$).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers are unanimous in favor of this submission.
Decision: Accept (poster)