Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities

Authors: zaiwei  chen
eric  mazumdar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 05:19:51

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.

Main paper: 
 introduction: 
 A constrained monotone variational inequality (MVI) problem consists of solving for an x * ∈ X ⊆ R d such thatmax s∈X (x * -s) ⊤ F (x * ) ≤ 0,where F : X → R d is a monotone operator [56, 37] and X is 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 as 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 or 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 Halpern iteration method [19] . These algorithms, particularly the extragradient and optimistic gradient methods-which can be viewed as approximating proximal point algorithms [46] -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 have garnered the most attention in the literature, with recent breakthroughs in the constrained regime where X is 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 [5, 61] , and learning in games [25, 43] .There is a rich literature analyzing MVI problems and their solutions [8, 54] . In this section, we 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 to their connection with gradient descent in optimization, 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 O(T -1/2 ) last-iterate convergence rate for the smooth convex-concave saddle-point problem (a special case of MVI). In [17] , the authors also studied saddle-point problems and proposed an algorithm called mirror-prox conditional gradient sliding, which comes with strong complexity guarantees. However, their analysis required a strong concavity assumption on the objective function, which corresponds to a strong monotonicity assumption in the variational inequality formulation. In [29] , the authors studied unconstrained variational inequality problems and showed that the extragradient algorithm achieves an O(T -1 ) last-iterate convergence rate under the assumptions of monotonicity and Lipschitz continuity of F (•). Finally, in [15] , the authors established the tight O(T -1/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 a natural Lyapunov argument.The Halpern Iteration Method. The Halpern iteration method was originally proposed to find the fixed points of non-expansive mappings [31] . More recently, algorithms based on the Halpern iteration have been applied to solving MVI problems with a fast O(T -1 ) convergence rate [19, 58] . However, to the best of our knowledge, there are no results showing that the Halpern iteration method, or the algorithms proposed in [19, 58] , have provable convergence in the stochastic 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 is 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 for MVIs.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] , we 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 O(T -1/6 ) rate of convergence we derive for this algorithm is slower than the known O(T -1/2 ) convergence rate for the averaged iterates of the mirror-prox algorithm [36] , it is important to note that the mirror-prox 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] .We introduce and analyze a generalized FW algorithm for solving MVI problems. This algorithm is a 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 O(T -1/2 ), matching the rates of optimistic gradient and extragradient algorithms. As a consequence of our analysis, we derive a finite-time bound for smooth FP in 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 to 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 O(T -1/6 ). 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 in the unconstrained setting [14] or under curvature assumptions on F (•), such as strong (quasi)-monotonicity or coercivity [8] .Question: Do the main claims made in 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 or NA answer to 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 as motivation as long as it is clear that these goals are not attained by the paper. 
problem formulation: 
 Let F : X → R d be a (possibly nonlinear) operator, where X is a convex and compact subset of R d . The associated variational inequality problem consists of solving for an x * ∈ X such thatEQUATIONAlthough such problems canonically arise in optimization [54] and machine learning [39] , where the operator F (•) is usually the gradient of 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.Example 1: The Policy Evaluation Problem in Reinforcement Learning. Consider an infinite horizon discounted Markov decision process (MDP) with a finite state space S, a finite action space A, a set of action-dependent transition probability matrices {P a ∈ R |S|×|S| | a ∈ A}, a reward function R : S × A → R, and a discount factor γ ∈ (0, 1). The transition probabilities and the reward function are unknown to the agent. Given a policy π : S → ∆(A), where ∆(A) denotes the probability simplex on A, its value function V π ∈ R |S| is defined asV π (s) = E π ∞ t=0 γ t R(S t , A t ) | S 0 = sfor all s ∈ S, where E π [ • ] 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 a 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 = T π (V ), where T π : R |S| → R |S| is the Bellman operator [50] . Therefore, solving the policy evaluation problem is equivalent to solving the unconstrained variational inequality problem V -T π (V ) = 0.Example 2: Multi-Player Convex-Concave Games. Consider an n-player game where each player i ∈ {1, 2, • • • , n} has a compact convex action set X i ⊆ R di and a loss function f i :n j=1 X j → R such that f i (x i , x -i ) is convex in x ifor all x -i ∈ j̸ =i X j . 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 a point x * ∈ X := n j=1 X j such that max s∈X (x * -s) ⊤ F (x * ) ≤ 0, whereF (x) = [∇ x1 f 1 (x 1 , x -1 ), • • • , ∇ xn f n (x n , x -n )], ∀ x ∈ X .Indeed, by convexity, we have for anyx ∈ R d that max s∈X (x -s) ⊤ F (x) ≥ n i=1 {f i (x i , x -i ) -min si∈Xi f i (s i , x -i )} ≥ 0,where the equality is achieved if and only if a joint strategyx * = (x * 1 , • • • , x * n ) satisfies f i (x * i , x * -i ) = min si∈Xi f i (s i , x * -i) 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 F : X → R d is said to be monotone if and only ifEQUATIONDespite this additional structure, designing algorithms for solving constrained MVI problems efficiently 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, 15] .Further generalizations of the MVI problem that are 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 to estimate gradients [61, 48, 16] .The rest of this paper is organized as follows. To motivate the generalized FW algorithm for MVI problems, we first present the smoothed FP, a 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 a two-timescale structure, where we construct a variance-reduced estimator of F (x) on the fast timescale and implement the generalized FW algorithm on the slow timescale.3 Warm-Up: Smoothed Fictitious PlayIn this section, we present the problem of finding a Nash equilibrium of a 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 set of pure strategies1 for player i (where i ∈ {1, 2}) is denoted by A i . When players play over mixed strategies, we can write this game as the min-max optimization problem minπ 2 ∈∆(A 2 ) max π 1 ∈∆(A 1 ) (π 1 ) ⊤ Rπ 2 , where R ∈ R |A 1 |×|A 2 |is 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(π 1 , π 2 ) = max π1 ∈∆(A 1 ) (π 1 ) ⊤ Rπ 2 -min π2 ∈∆(A 2 ) (π 1 ) ⊤ Rπ 2 .Suppose that a pair of strategies (π 1 * , π 2 * ) satisfies NG(π 1 * , π 2 * ) = 0. Then, each player is playing the best response to their opponent's strategy, thereby having no incentive to deviate from their current strategy. This situation defines a Nash equilibrium [47] .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 of their opponents' actions. Subsequently, a generalization of that algorithm, smoothed FP, was introduced as it was found to be a better model of human play, accounting for "trembling-hand" 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 ∈ R d such that x i ≥ 0 for all i, let ν(x) = -d i=1 x i log(x i ) be the entropy function [55] . Given i ∈ {1, 2} and a i ∈ A i , we use e(a i ) to denote the |A i |-dimensional vector with its a i -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 1's perspective) 1: Input: Integer T , temperature τ > 0, and initializationπ 2 0 ∈ ∆(A 2 ) 2: for t = 0, 1, • • • , T -1 do 3: v 1 t = arg max v∈∆(A 1 ) v ⊤ Rπ 2 t + τ ν(v) 4:PlayA 1 t ∼ v 1 t (•) and observe A 2 t 5: π 2 t+1 = π 2 t + 1 t+1 (e(A 2 t ) -π 2 t ) 6: end forIn smoothed FP, with an arbitrary initial estimate of the opponent's policy π 2 0 , in each round, player 1 plays the smoothed best response to its latest estimate of the opponent's policy (cf. Algorithm 1 Line 4), and updates the estimate π 2 t according to Algorithm 1 Line 5, which is an iterative way of computing the empirical average of the opponent's historical strategies.Despite its canonical nature and its connection to classic algorithms in online learning, such as Follow-The-Regularized-Leader (FTRL) [40] , the algorithm lacks a 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 v 2 t and does not know R, but has payoff-based feedback of the form r t such thatE[r t | A 1 t , A 2 t ] = R(A 1 t , A 2 t ).In this case, smoothed FP reduces to FTRL or forms of FTRL with bandit feedback due to 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 v 2 t . Therefore, previous approaches for analyzing FTRL do not apply, and, to the best of our knowledge, finite-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 1 follows as a 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 a 1 ∈A 1 ,a 2 ∈A 2 |R(a 1 , a 2 )| ≤ 1. Theorem 3.1. Suppose that both players use smoothed FP in finite zero-sum games and τ ∈ (0, 1]. Then, we have for any t ≥ 0 thatE[NG(π 1 t , π 2 t )] ≤ 4 |A 1 | + |A 2 | t + 1 + 36|A 1 ||A 2 | log(t + 1) τ (t + 1) + τ log(|A 1 ||A 2 |).The proof of Theorem 3.1 is presented in Appendix A. In view of Theorem 3.1, given a time horizon T , by choosing τ = O T -1/2 , we have an Õ 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 E[NG(π 1 t , π 2 t )] ≤ ϵ, the iteration complexity is Õ(|A 1 ||A 2 |/ϵ 2 ).To identify Algorithm 1 for zero-sum games as a special case of generalized FW for MVI problems, observe that the Nash gap NG(•, •) can be rewritten asEQUATIONwherex = (x 1 , x 2 ) ∈ X := ∆(A 1 ) × ∆(A 2 ) and F (x) = M x with the matrix M defined as M = [0 |A 1 |×|A 2 | , -R; R ⊤ , 0 |A 2 |×|A 1 | ]. Since M + M ⊤ = 0, it is clear that F (•) is a monotoneoperator. In addition, when both players follow smooth FP as presented in Algorithm 1, the joint update equation can be equivalently written asEQUATIONwhere f (s) = -ν(s 1 ) -ν(s 2 ) for any s = (s 1 , s 2 ) ∈ X , and w t is a zero-mean random variable. In smoothed FP, the random variable w t corresponds to the difference between the softmax distribution (cf. Algorithm 1 Line 3) and a sample from the softmax distribution (cf. Algorithm 1 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 to be analyzed, to the best of our knowledge, in the context of more general MVI problems. In the next section, we show that this algorithm has strong convergence properties.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The limitations are 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 (e.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 or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a 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 it 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 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 theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 
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 τ > 0, and initializationx 0 ∈ R d 2: for t = 0, 1, • • • , T -1 do 3: s t = arg min s∈X {s ⊤ F (x t ) + τ f (s)} 4: x t+1 = x t -α t (x t -s t + w t ) 5: end forIn Algorithm 2 Line 3, the function f : X → [0, ∞) serves as a 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 σ f -strongly convex for some σ f > 0. In addition, lim x→∂X ∥∇f (x)∥ 2 = +∞, where ∂X = X \ relint R d X denotes the boundary of the convex compact subset X of R d .Differentiability and strong convexity are standard requirements when choosing regularizers. The condition that lim x→∂X ∥∇f (x)∥ 2 = +∞ ensures that the generalized FW direction s t from Algorithm 2 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 τ = 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 a 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 s t is the softmax operator.To derive our convergence guarantees, we impose the following assumptions on the operator F (•) and the stochastic process {w t }. Assumption 4.1. The operator F (•) is Lipschitz continuous, i.e., there exists L F > 0 such that∥F (x 1 ) -F (x 2 )∥ 2 ≤ L F ∥x 1 -x 2 ∥ 2 , ∀ x 1 , x 2 ∈ X .Assumption 4.2. The operator F (•) has a Lipschitz continuous Jacobian matrix J(•), i.e., there existsL J > 0 such that ∥J(x 1 ) -J(x 2 )∥ 2 ≤ L J ∥x 1 -x 2 ∥ 2 , ∀ x 1 , x 2 ∈ 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 t ≥ 0 that (1)s t -w t ∈ X , (2) E[w t | F t ] = 0, (3) E[∥w t ∥ 2 2 | F t ] ≤ σ w , where σ w > 0 and F t is the σ-algebra generated by {x 0 , w 0 , w 1 , • • • , w t-1 }.When σ w = 0, Algorithm 2 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 is 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 D X = max x∈X ∥x∥ 2 , F = max x∈X ∥F (x)∥ 2 , and f = max x∈X f (x), 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 {x t } updated according to Algorithm 2. Suppose that F (•) is a monotone operator on X , and Assumptions 4.1, 4.2, and 4.3 are satisfied. Then, when the regularizer f (•) satisfies Condition 4.1, we have for all t ≥ 0 thatE max s∈X (x t -s) ⊤ F (x t ) ≤    2D X F (1 -α) t + c 1 α + τ f , when α t ≡ α ≤ 1, 2D X F t + 1 + c 1 log(t + 1) t + 1 + τ f , when α t = 1 t + 1,where c 1 = (L F + L 2 F /(2τ σ f ) + D X L J )(σ w + 4D 2 X ).The proof of Theorem 4.1 is presented in Appendix B.2. Note that for a given time horizon T , choosingτ = O(T -1/2 ) results in an overall Õ(T -1/2) last-iterate convergence rate to a solution to the MVI problem. The problem-dependent constants D X , 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 E[max s∈X (x t -s) ⊤ F (x t )] ≤ ϵ, the iteration complexity is Õ(ϵ -2 ).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-aided proofs such as the sum of squares programming [15] or performance estimation problems [29] , our proof follows from a simple Lyapunov argument on the regularized gap V (•), which is defined asEQUATIONA key step in proving Theorem 4.1 is the following lemma, which shows the smooth evolution of the generalized FW directions {s t }. For notation convenience, let s(x) = arg min s∈X {s ⊤ F (x)+τ f (s)} for all x ∈ X . Lemma 4.1. It holds for allx 1 , x 2 ∈ X that ∥s(x 1 ) -s(x 2 )∥ 2 ≤ L F τ σ f ∥x 1 -x 2 ∥ 2 .The proof of Lemma 4.1 is presented in Appendix B.1. As a last comment, note that while the Õ(T -1/2 ) convergence rate is known to be tight for extragradient and optimistic gradient algorithms [15, 25] (since they both can be seen as instantiations of p-stationary canonical linear iterative algorithms), 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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 a detailed description of our experimental setup. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a 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 to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be 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. 
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 w t in Algorithm 2 Line 4, which captures the stochasticity in choosing the FW direction.In general, incorporating stochasticity into FW algorithms in optimization is known to be nontrivial when the variance of the noise, though bounded, is not sufficiently small. When there is only access to a noisy oracle for F (x t ), the stochasticity enters the algorithm in a 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 t ) + z t (where z t represents the noise) in place of F (x t ) in Algorithm 2 Line 3 to compute the FW direction s t . Despite replacing the hardmin with a softmin (by introducing a regularizer), the FW direction s t remains highly sensitive to the noise z t because the FW direction computed from the exact F (x t ) and its noisy counterpart F (x t ) + z t 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 F (•) 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 a 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 3 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 τ , and initialization x 0 ∈ X andy 0 ∈ R d . 2: for t = 0, 1, • • • , T -1 do 3:y t+1 = y t + β(F (x t ) + z t -y t ) 4:s t = arg min s∈X {s ⊤ y t+1 + τ f (s)} 5:x t+1 = x t -α(x t -s t ) 6: end forThe key step in Algorithm 3 is Line 3, where we build a sequence of estimators {y t } for {F (x t )} by averaging the newly observed noisy estimate F (x t ) + z t with past information. To illustrate, since y t+1 is a convex combination (with parameter β) of the previous iterate y t and F (x t ) + z t , we see that for any t, y t is essentially a convex combination (hence a weighted average) of {F (x i ) + z i } 0≤i≤t-1 . Suppose that x t were stationary (i.e., x t ≡ x for some x), then y t effectively becomes a variancereduced estimator of F (x). To extend this idea to time-varying x t , we choose the stepsizes α and β such that β ≫ α, creating a two-timescale structure [9] . This ensures that, from the perspective of y t , x t is nearly stationary, allowing y t to converge to F (x t ) on a faster timescale. As a result, the x t iterates should behave similarly to 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, we first formally state our assumption on the noise sequence {z t }.Assumption 5.1. It holds for all t ≥ 0 that E[z t | F t ] = 0 and E[∥z t ∥ 2 2 | F t ] ≤ σ z for some σ z > 0, where F t is the σ-algebra generated by {x 0 , y 0 , z 0 , z 1 , • • • , z t-1 }.The next lemma bounds the distance between the estimator y t and the desired target F (x t ). The proof is presented in Appendix C.1.Lemma 5.1. Suppose that Assumptions 4.1 and 5.1 are satisfied and β ∈ (0, 1). Then, we have for any t ≥ 0 thatEQUATION)In view of the last term on the right-hand side of Eq. ( 7), to make E[∥y t -F (x t )∥ 2 2 ] sufficiently small, we need the ratio between the stepsizes, i.e., α/β, 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. Then, when choosing β = 8α 2/3 /3 ∈ (0, 1), we have for any t ≥ 0 thatE max s∈X (x t -s) ⊤ F (x t ) ≤ c1 t (1 -α) t + c2 α 1/3 τ + c3 α 2/3 τ + c4 α τ + c5 α + τ f ,where {c i } 1≤i≤5 are problem-dependent constants. See Appendix C.2 for their explicit expressions.A proof sketch of Theorem 5.1 is presented in Section 6, and the complete proof can be found in Appendix C.2. Based on Theorem 5.1, we have the following iteration complexity.Corollary 5.1.1. To achieve E[max s∈X (x t -s) ⊤ F (x t )] ≤ ϵ, the iteration complexity is Õ(ϵ -6 ).Once again, we remark that, to the best of our knowledge, this appears to be the first algorithm with a last-iterate convergence guarantee in constrained stochastic MVI problems. The guarantees for variants of gradient-based algorithms are on the averaged iterate or under strong curvature assumptions on F (•) or X [8] . Numerical simulations are provided in Appendix D to verify the last-iterate convergence of our proposed algorithm.Our iteration complexity of Õ(ϵ -6 ) is slower than the O(ϵ -2 ) 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 O(ϵ -3 ) 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 of the estimated FW direction s t , which results in a suboptimal relationship between the hyperparameter τ and E[∥y t -F (x t )∥ 2 2 ] in our analysis.6 Proof Sketch of Theorem 5.1Here, we present an outline of the proof of Theorem 5.1, which uses Lyapunov-based arguments. The proof of Theorem 4.1 follows a similar approach.The first step in proving Theorem 5.1 is to establish Lemma 5.1, which shows that our constructed estimator y t indeed keeps track of the desired target F (x t ).6.1 Proof Sketch of Lemma 5.1We will use ∥y t -F (x t )∥ 2 2 as a Lyapunov function to study the evolution of y t . To begin with, for any t ≥ 0, we have by Algorithm 3 Line 3 that∥y t+1 -F (x t+1 )∥ 2 2 = ∥(1 -β)y t + β(F (x t ) + z t ) -F (x t+1 )∥ 2 2 = ∥(1 -β)(y t -F (x t )) + βz t + F (x t ) -F (x t+1 )∥ 2 2 = (1 -β) 2 ∥y t -F (x t )∥ 2 2 + β 2 ∥z t ∥ 2 2 + ∥F (x t ) -F (x t+1 )∥ 2 2 + 2(1 -β)β(y t -F (x t )) ⊤ z t + 2βz ⊤ t (F (x t ) -F (x t+1 )) + 2(1 -β)(y t -F (x t )) ⊤ (F (x t ) -F (x t+1 )).Taking expectations conditioned on F t on both sides of the previous inequality, and using Assumption 5.1 for the noise sequence {z t }, along with some algebraic manipulations, we obtainE[∥y t+1 -F (x t+1 )∥ 2 2 | F t ] ≤ 1 - 3β 4 ∥y t -F (x t )∥ 2 2 + 2β 2 σ z + 6 β E[∥F (x t ) -F (x t+1 )∥ 2 2 | F t ].The details are presented in Appendix C.1. By the Lipschitz continuity of F (•) (cf. Assumption 4.1), we haveE[∥F (x t ) -F (x t+1 )∥ 2 2 | F t ] ≤ L F E[∥x t+1 -x t ∥ 2 2 | F t ] = L F α 2 E[∥s t -x t ∥ 2 2 | F t ] ≤ 4L F D 2 X α 2 ,where the equality follows from Algorithm 3 Line 5. Combining the previous two inequalities together, we obtainE[∥y t+1 -F (x t+1 )∥ 2 2 | F t ] ≤ 1 - 3β 4 ∥y t -F (x t )∥ 2 2 + 2β 2 σ z + 24L F D 2 X α 2 β .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 y t of F (x t ), we now give an overview of the proof of Theorem 5.1. Let s * t = arg min s∈X {s ⊤ F (x t+1 ) + τ f (s)}. Using V (•) defined in Eq. ( 6) as our Lyapunov function, we have, after some algebra, that for any t ≥ 0:EQUATIONwhere L V is a problem-dependent constant (cf. Lemma B.1). See Appendix C.2 for more details. It remains to bound the term F (x t ) ⊤ (s t -s * t-1 ). Using Lemma 4.1, we haveF (x t ) ⊤ (s t -s * t-1 ) ≤ ∥F (x t )∥ 2 ∥s t -s * t-1 ∥ 2 ≤ F L F τ σ f ∥y t+1 -F (x t )∥ 2 ≤ F L F τ σ f (∥y t+1 -y t ∥ 2 + ∥y t -F (x t )∥ 2 ) ≤ F L F τ σ f (β∥F (x t ) -y t ∥ 2 + β∥z t ∥ 2 + ∥y t -F (x t )∥ 2 ) (Algorithm 3 Line 3) ≤ F L F τ σ f (β∥z t ∥ 2 + 2∥y t -F (x t )∥ 2 ),where the last inequality follows from β ∈ (0, 1). Using the upper bound we obtained for the term F (x t ) ⊤ (s t -s * t-1 ) in Eq. ( 8) and then taking total expectation on both sides of the resulting inequality, we haveE[V (x t+1 )] ≤ (1 -α)E[V (x t )] + F L F βα τ σ f σ 1/2 z + 2 F L F α τ σ f E 1/2 [∥y t -F (x t )∥ 2 2 ] + 2L V D 2 X α 2 .Finally, substituting the upper bound we obtained for E[∥F (x t+1 ) -y t+1 ∥ 2 2 ] in Lemma 5.1 into the previous inequality and then repeatedly using it, we obtain the desired finite-time bound. The details are presented in Appendix C.2.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 to understand the results?Answer: [Yes]Justification: We have provided a detailed description of our experimental setup.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of 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. 
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 proximal point algorithms and consequently can be seen as discretizations of the ODE ẋ = F (x), FW algorithms and consequently generalized FW algorithms are not necessarily related to this ODE and can thus be viewed as a new class of algorithms for such problems.An interesting future direction of this work is to develop results for the case where τ = 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 on X besides convexity, this case seems fundamentally more difficult due to the potential non-uniqueness and non-smoothness of the FW direction s = arg min s∈X s ⊤ F (x).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. Therefore, there is no need for error bars. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: 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, or scraped datasets)?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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or 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 a 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 a 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 are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.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 of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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 new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 applicable), such as the institution conducting the review. 
 
 Appendix: Observe that Algorithm 1 is a special case of Algorithm 2 withF (x) = F (π 1 , π 2 ) = 0 -R R ⊤ 0 π 1 π 2 , J(x) = 0 -R R ⊤ 0 ⊤ , f (x) = f (π 1 , π 2 ) = -ν(π 1 ) -ν(π 2 ) + log(|A 1 ||A 2 |), w t = e(A 1 t ) -v 1 t e(A 2 t ) -v 2 t .In addition, since maxa 1 ,a 2 |R(a 1 , a 2 )| ≤ 1 we have L F ≤ |A 1 ||A 2 |, L J = 0, F ≤ |A 1 | + |A 2 |, f ≤ log(|A 1 ||A 2 |), σ f = 1, σ w ≤ 8,and D X ≤ 2. Now, applying Theorem 4.1 with α t = 1/(t + 1), since τ ≤ 1, we haveNG(π 1 , π 2 ) ≤ 4 |A 1 | + |A 2 | t + 1 + 36|A 1 ||A 2 | τ log(t + 1) t + 1 + τ log(|A 1 ||A 2 |).B.1 Proof of Lemma 4.1Since s ⊤ F (x) + τ f (s) as a function of s is τ σ f -strongly convex uniformly for all x ∈ X and the feasible set X is convex and compact, there is a unique global minimizer to the optimization problem min s∈X {s ⊤ F (x) + τ f (s)}. Moreover, since f (•) is chosen such that lim s→∂X ∥∇f (s)∥ = +∞ (cf. Condition 4.1), the unique optimal solution to min s∈X {s ⊤ F (x) + τ f (s)} must lie in the interior of the feasible set X . Therefore, for any x 1 , x 2 ∈ X , we have by the first-order optimality condition that F (x 1 ) + τ ∇f (s(x 1 )) = 0, F (x 2 ) + τ ∇f (s(x 2 )) = 0.It follows thatF (x 1 ) -F (x 2 ) = τ (∇f (s(x 2 )) -∇f (s(x 1 ))).Using the σ f -strong convexity of f (•) and Assumption 4.1, we haveτ σ f ∥s(x 1 ) -s(x 2 )∥ 2 ≤ τ ∥∇f (s(x 2 )) -∇f (s(x 1 ))∥ 2 = ∥F (x 1 ) -F (x 2 )∥ 2 ≤ L F ∥x 1 -x 2 ∥ 2 , which implies ∥s(x 1 ) -s(x 2 )∥ 2 ≤ L F τ σ f ∥x 1 -x 2 ∥ 2 .Recall that we use V : X → R defined as V (x) = max s∈X {(x -s) ⊤ F (x) -τ f (s)} as our Lyapunov function. The goal here is to show that x t updated according to Algorithm 2 produces a negative drift with respect to V (•). The following lemma is needed to establish the result.Lemma B.1. The Lyapunov function V (•) is L V -smooth with respect to ∥ • ∥ 2 , where L V = 2L F + L 2 F τ σ f + 2D X L J .Proof of Lemma B.1. 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 theorem [7] and we have∇V (x) = F (x) + J(x) ⊤ (x -s(x)), ∀ x ∈ X ,where we recall that s(x) = arg max s∈X {(x -s) ⊤ F (x) -τ f (s)}. For any x 1 , x 2 ∈ X , we have∇V (x 1 ) -∇V (x 2 ) = F (x 1 ) + J(x 1 ) ⊤ (x 1 -s(x 1 )) -F (x 2 ) -J(x 2 ) ⊤ (x 2 -s(x 2 )) = F (x 1 ) -F (x 2 ) + J(x 1 ) ⊤ (x 1 -x 2 + s(x 2 ) -s(x 1 )) + (J(x 1 ) -J(x 2 )) ⊤ (x 2 -s(x 2 )).Using triangle inequality, Assumption 4.1, Assumption 4.2, and Lemma 4.1, we obtain∥∇V (x 1 ) -∇V (x 2 )∥ 2 ≤ ∥F (x 1 ) -F (x 2 )∥ 2 + ∥J(x 1 )∥ 2 (∥x 1 -x 2 ∥ 2 + ∥s(x 2 ) -s(x 1 )∥ 2 ) + ∥J(x 1 ) -J(x 2 )∥ 2 ∥x 2 -s(x 2 )∥ 2 ≤ L F ∥x 1 -x 2 ∥ 2 + L F 1 + L F τ σ f ∥x 1 -x 2 ∥ 2 + 2D X L J ∥x 1 -x 2 ∥ 2 = 2L F + L 2 F τ σ f + 2D X L J ∥x 1 -x 2 ∥ 2 = L V ∥x 1 -x 2 ∥ 2 .Now, we are ready to prove Theorem 4.1. Using the smoothness of V (•), the explicit expression of ∇V (x t ) (both established in Lemma B.1), and the update equation in Algorithm 2 Line 3, we have for any t ≥ 0 thatV (x t+1 ) ≤ V (x t ) + ∇V (x t ) ⊤ (x t+1 -x t ) + L V 2 ∥x t+1 -x t ∥ 2 2 = V (x t ) -α t (F (x t ) + J(x t ) ⊤ (x t -s t )) ⊤ (x t -s t + w t ) + L V α 2 t 2 ∥x t -s t + w t ∥ 2 2 = V (x t ) -α t F (x t ) ⊤ (x t -s t + w t ) -α t (x t -s t ) ⊤ J(x t )(x t -s t + w t ) + L V α 2 t 2 ∥x t -s t + w t ∥ 2 2 .Taking expectations on both sides of the previous inequality, since {w t } is a martingale difference sequence, we haveEQUATIONNext, we bound each term on the right-hand side of the previous inequality.For the first term on the right-hand side of Eq. ( 9), observe thatF (x t ) ⊤ (s t -x t ) ≤ -F (x t ) ⊤ (x t -s t ) + τ f (s t ) = -V (x t ).Therefore, we haveEQUATIONFor the second term on the right-hand side of Eq. ( 9), since F (•) is monotone, the Jacobian matrix J(•) is positive semidefinite. Therefore, we haveEQUATIONFor the third term on the right-hand side of Eq. ( 9), using Assumption 4.3, we haveEQUATIONCombining Eqs. ( 10), (11) , and (12) with Eq. ( 9), we haveE[V (x t+1 )] ≤ (1 -α t )E[V (x t )] + L V (4D 2 X + σ w )α 2 t 2 = (1 -α t )E[V (x t )] + c 1 α 2 t, where we denote c 1 = L V (4D 2 X + σ w )/2 for simplicity of notation. Repeatedly using the previous inequality, we have for all t ≥ 0 thatE[V (x t )] ≤ t-1 j=1 (1 -α j )V (x 0 ) + c 1 t-1 i=0 α 2 i t-1 j=i+1 (1 -α j ) . Finally, since max s∈X (x -s) ⊤ F (x) -τ f ≤ V (x) ≤ max s (x -s) ⊤ F (x) ≤ 2D X F , ∀ x ∈ X ,we have for all t ≥ 0 thatEQUATION)Constant Stepsizes. When α t ≡ α, we havet-1 j=0 (1 -α j ) = (1 -α) t , and t-1 i=0 α 2 i t-1 j=i+1 (1 -α j ) ≤ α.It follows from Eq. ( 13) thatE max s∈X (x t -s) ⊤ F (x t ) ≤ 2D X F (1 -α) t + c 1 α + τ f .Diminishing Stepsizes. When α t = 1/(t + 1) for all t ≥ 0, we havet-1 j=1 (1 -α j ) = t-1 j=1 j j + 1 = 1 t + 1 and t-1 i=0 α 2 i t-1 j=i+1 (1 -α j ) = t-1 i=0 1 (i + 1) 2 t-1 j=i+1 j j + 1 = 1 t + 1 t-1 i=0 1 (i + 1) ≤ log(t + 1) t + 1 .It follows thatE max s∈X (x t -s) ⊤ F (x t ) ≤ 2D X F t + 1 + c 1 log(t + 1) t + 1 + τ f .C.1 Proof of Lemma 5.1For any t ≥ 0, we haveEQUATION)Using Cauchy-Schwarz inequality, we haveE 1 = (y t -F (x t )) ⊤ (F (x t ) -F (x t+1 )) ≤ ∥y t -F (x t )∥ 2 ∥F (x t ) -F (x t+1 )∥ 2 ≤ β 8 ∥y t -F (x t )∥ 2 2 + 2 β ∥F (x t ) -F (x t+1 )∥ 2 2 ,where the last inequality follows from a 2 + b 2 ≥ 2ab for any a, b ∈ R. Similarly, we also haveE 2 = z ⊤ t (F (x t ) -F (x t+1 )) ≤ ∥z t ∥ 2 ∥F (x t ) -F (x t+1 )∥ 2 ≤ β 2 ∥z t ∥ 2 2 + 1 2β ∥F (x t ) -F (x t+1 )∥ 2 2 .Combining the previous two inequalities with Eq. ( 14) and then taking expectations on both sides, we obtainE[∥y t+1 -F (x t+1 )∥ 2 2 ] ≤ (1 -β) 2 E[∥y t -F (x t )∥ 2 2 ] + β 2 E[∥z t ∥ 2 2 ] + E[∥F (x t ) -F (x t+1 )∥ 2 2 ] + β 4 E[∥y t -F (x t )∥ 2 2 ] + 4 β E[∥F (x t ) -F (x t+1 )∥ 2 2 ] + β 2 E[∥z t ∥ 2 2 ] + E[∥F (x t ) -F (x t+1 )∥ 2 2 ] + 2(1 -β)βE[(y t -F (x t )) ⊤ E[z t | F t ]] ≤ 1 - 3β 4 E[∥y t -F (x t )∥ 2 2 ] + 2β 2 σ z + 6 β E[∥F (x t ) -F (x t+1 )∥ 2 2 ] :=E3, where the last line follows from Assumption 5.1 and the fact that β ∈ (0, 1).It remains to bound the term E 3 on the right-hand side of the previous inequality. Observe thatE[∥F (x t ) -F (x t+1 )∥ 2 2 ] ≤ L F E[∥x t+1 -x t ∥ 2 2 ] (Assumption 4.1) = L F α 2 E[∥s t -x t ∥ 2 2 ] (Algorithm 3 Line 5) ≤ 4L F D 2 X α 2 . Therefore, we have E[∥y t+1 -F (x t+1 )∥ 2 2 ] ≤ 1 - 3β 4 E[∥y t -F (x t )∥ 2 2 ] + 2β 2 σ z + 24L F D 2 X α 2 β .Repeatedly using the previous inequality, we obtainE[∥y t -F (x t )∥ 2 2 ] ≤ 1 - 3β 4 t ∥y 0 -F (x 0 )∥ 2 2 + 8βσ z 3 + 32L F D 2 X α 2 β 2 .C.2 Proof of Theorem 5.1Recall that s * t := arg min s∈X {s ⊤ F (x t+1 ) + τ f (s)}. Using the smoothness of V (•), the explicit expression of ∇V (x t ) (both established in Lemma B.1), and the update equation in Algorithm 3 Line 5, we have for any t ≥ 0 thatEQUATION)where the last line follows from the definition of V (•). To proceed, observe thatF (x t ) ⊤ (s t -s * t-1 ) ≤ ∥F (x t )∥ 2 ∥s t -s * t-1 ∥ 2 ≤ F L F τ σ f ∥y t+1 -F (x t )∥ 2 (Lemma 4.1) ≤ F L F τ σ f (∥y t+1 -y t ∥ 2 + ∥y t -F (x t )∥ 2 ) ≤ F L F τ σ f (β∥F (x t ) -y t ∥ 2 + β∥z t ∥ 2 + ∥y t -F (x t )∥ 2 ) (Algorithm 3 Line 3) ≤ F L F τ σ f (β∥z t ∥ 2 + 2∥y t -F (x t )∥ 2 ),where the last line follows from β ∈ (0, 1). Combining the previous inequality with Eq. ( 15), we haveV (x t+1 ) ≤ (1 -α)V (x t ) + F L F βα τ σ f ∥z t ∥ 2 + 2 F L F α τ σ f ∥y t -F (x t )∥ 2 + 2L V D 2 X α 2 .Taking expectations on both sides of the previous inequality, we haveE[V (x t+1 )] ≤ (1 -α)E[V (x t )] + F L F βα τ σ f σ 1/2 z + 2 F L F α τ σ f E 1/2 [∥y t -F (x t )∥ 2 2 ] + 2L V D 2 X α 2 ,where we usedE[∥z t ∥ 2 ] ≤ E 1/2 [∥z t ∥ 2 2 ] = E 1/2 [E[∥z t ∥ 2 2 | F t ]] ≤ σ 1/2 z and E[∥y t -F (x t )∥ 2 ] ≤ E 1/2 [∥y t -F (x t )∥ 2 2 ]. Using Lemma 5.1 to bound E[∥y t -F (x t )∥ 2 2 ],we haveE[V (x t+1 )] ≤ (1 -α)E[V (x t )] + F L F βα τ σ f σ 1/2 z + 2L V D 2 X α 2 + 2 F L F α τ σ f 1 - 3β 4 t/2 ∥y 0 -F (x 0 )∥ 2 + 3β 1/2 σ 1/2 z + 6L 1/2 F D X α β ,where we use√ a + b + c ≤ √ a + √ b + √ cfor any a, b, c ≥ 0. Repeatedly using the previous inequality, since choosing β = 8α 2/3 /3 implies 1 -3β/4 ≤ (1 -α) 2 , we haveE[V (x t )] ≤ (1 -α) t V (x 0 ) + F L F β τ σ f σ 1/2 z + 2 F L F α τ σ f t (1 -α) t-1 ∥y 0 -F (x 0 )∥ 2 + 2 F L F τ σ f 3β 1/2 σ 1/2 z + 6L 1/2 F D X α β + 2L V D 2 X α.Using β = 8α 2/3 /3 ∈ (0, 1) (which also implies α ≤ 1 -α) and the explicit expression of L V from Lemma B.1 in the previous inequality, we haveE[V (x t )] ≤ (1 -α) t V (x 0 ) + 8 F L F σ 1/2 z α 2/3 3τ σ f + 2 F L F τ σ f t (1 -α) t ∥y 0 -F (x 0 )∥ 2 + 18 F L F τ σ f σ 1/2 z + L 1/2 F D X 4 α 1/3 + 4(L F + D X L J )D 2 X α + 2L 2 F D 2 X τ σ f α Recall that max s∈X (x -s) ⊤ F (x) -τ f ≤ V (x) ≤ max s (x -s) ⊤ F (x) ≤ 2D X F , ∀ x ∈ X .Therefore, we obtain the following finite-time bound:E max s∈X (x t -s) ⊤ F (x t ) ≤ 2D X F (1 -α) t + 8 F L F σ 1/2 z α 2/3 3τ σ f + 2 F L F τ σ f t (1 -α) t ∥y 0 -F (x 0 )∥ 2 + 18 F L F τ σ f σ 1/2 z + L 1/2 F D X 4 α 1/3 + 4(L F + D X L J )D 2 X α + 2L 2 F D 2 X τ σ f α + τ f = c1 t (1 -α) t + c2 α 1/3 τ + c3 α 2/3 τ + c4 α τ + c5 α + τ f , where c1 = 2D X F + 2 F L F τ σ f ∥y 0 -F (x 0 )∥ 2 , c2 = 18 F L F σ f σ 1/2 z + L 1/2 F D X 4 , c3 = 8 F L F σ 1/2 z 3σ f , c4 = 2D 2 X L 2 F σ f , c5 = 4(L F + D X L J )D 2 X .The proof is complete.In this section, we conduct numerical simulations to empirically verify the performance of our proposed algorithms.We compare the performance of Algorithm 2 with the extragradient method, both of which provably enjoy an O(T -1/2 ) rate of last-iterate convergence.Recall that the MVI problem aims to find anx * ∈ R d such that max s∈X (x * -s) ⊤ F (x * ) ≤ 0.According to [15] , the extragradient algorithm initializes an x 0 ∈ X and update x k iteratively according to the following formula:x t+1/2 = Π X (x t -αF (x t )), x t+1 = Π X (x t -αF (x t+1/2 )),where Π X (•) the projection operator onto X with respect to ∥ • ∥ 2 .The Rock-Paper-Scissors game is a classic example of a zero-sum game, where each player has three actions: Rock, Paper, or Scissors. The rules are such that Rock beats Scissors, Scissors beat Paper, and Paper beats Rock. If both players choose the same move, the game results in a tie. The payoff matrix for the player 1 (i.e., the row player) can be represented as follows:Rock Paper Scissors Rock 0 -1 1 Paper 1 0 -1 Scissors -1 1 0The results for implementing generalized FW and the extragradient method are reported in Figure 1 .The Burglar-Policeman 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 1 Burglar Switch 1 -1The results for implementing generalized FW and the extragradient method are reported in Figure 2 .In either the Rock-Paper-Scissors Game or the Burglar-Policeman Matrix Game, both algorithms seem to have similar performance. However, the extragradient method seems to be more stable. In this experiment, we choose F (x) = M x and X = ∆ 100 × ∆ 100 , where ∆ 100 denotes the 100dimensional probability simplex. The matrix M is chosen to beM = [0 100×100 , -R; R ⊤ , 0 100×100 ],where R ∈ R 100×100 is a 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 outperform the extragradient algorithm in 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 τ . The numerical simulations verify that the generalized FW algorithm indeed holds practical potential. Since none of the existing algorithms (e.g., the extragradient method, the optimistic gradient method, and the Halpern iteration method) have provable convergence in the stochastic setting, we will only verify the convergence of our algorithm here. The experiment setup is the same as in Appendix D.1.3 except that F (x) is replaced by F (x) + z, where z is a bounded random variable. In the stochastic setting, we choose τ = 0.1, α = 0.1, and β = 0.01 in Algorithm 3. The result is reported in Figure 4 . From Figure 4 , we see that Algorithm 3 indeed converges, but not to zero due to the stochasticity and the fact that we are using constant stepsizes, which agrees with Theorem 5.1. The fact that our algorithm is stable in the stochastic setting highlights one of its main advantages compared with the existing methods.NeurIPS Paper ChecklistJustification: 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.• 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, at least for the experiments that support the main claims of 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 a 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 or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• 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). • If 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.Justification: This is a 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.• If 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 is a special consideration due to laws or regulations in their jurisdiction).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.• If 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., deployment 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).We will use strategy and policy interchangeably. 


Decision: The reviewers are unanimous in favor of this submission.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Typos and notation related remarks:
- page 1, line 19: \to is more convenient than \mapsto
- 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?
- page 3, line 106: in phrase "in either the uncontrained regime [13 ] or under", "in" should be after "either", and "uncontrained" has typo
- page 4, line 146: subscript and superscript for A are confused
- 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
- page 6, line 228: "make ... assumptions" or "impose ... requirements" 

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.
limitations: limitations: The limitations are clear from reading.
paper_summary: paper_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.
strength_weakness: strength_weakness: I think there's no apparent weaknesses. I suspect the analysis for the stochastic case might not be tight, leaving room for improvement.
questions: questions: -
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: See the Questions part.
questions: 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? 

* 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.

* 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?

[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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. There are some major issues with the proofs in the paper, as follows
- 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.
- 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$. 
- 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.
2. Empirically, there is a gap between extragradient and the proposed algorithm.
questions: questions: Could the authors address my questions mentioned above? I would be happy to increase my score if these concerns are addressed adequately.
limitations: limitations: Yes

Comments: title: Follow-Up Comments by Authors
Follow-Up Comments by Authors
Rebuttal Feedback
Rebuttal Feedback
Rebuttal Feedback
Rebuttal (Continued)
Rebuttal (Continued)
Rebuttal (Continued)
Rebuttal (Continued)
Author's Response
comment: We are glad to hear that our response addresses some of the reviewer’s concerns, especially regarding the proof gap, and we greatly appreciate the reviewer for raising the score. Next, we would like to further justify our newly imposed assumption, which does not undermine the contributions of this work. First, it does not imply any strong curvature properties (such as strong monotonicity of the operator or strong convexity of the feasible set). Moreover, our original motivation for allowing the update to be noisy in Algorithm 2 is that it can directly be used to obtain the convergence bound of smoothed fictitious play, where the newly imposed assumption is automatically satisfied due to the linear structure of the operator $F(\cdot)$. In either the completely deterministic setting (where $w_t=0$) or the more challenging stochastic setting (where $F(x_t)$ is noisy), both our original approaches work.
We are glad to hear that our response addresses some of the reviewer's concerns, and we greatly appreciate the reviewer for raising the score.

The new proof has been presented in full detail in the previous response, and it will be included in the next version of this work. Next, we would like to provide justification for our newly imposed assumption, which does not undermine the contributions of this work. First, it does not imply any strong curvature properties (such as strong monotonicity of the operator or strong convexity of the feasible set). Moreover, our original motivation for allowing the update to be noisy in Algorithm 2 is that it can directly be used to obtain the convergence bound of smoothed fictitious play, where the newly imposed assumption is automatically satisfied due to the linear structure of the operator $F(\cdot)$. In either the completely deterministic setting (where $w_t=0$) or the more challenging stochastic setting (where $F(x_t)$ is noisy), both our original approaches work.
Thank you for the response. I appreciate the rebuttal, as it has effectively addressed some concerns, particularly regarding the gap in the proof. I will adjust the score accordingly. However, I believe more effort is needed to remove the new introduced assumption.
I thank the authors for the response. The authors have addressed some parts of my concerns, I have raised the score accordingly. However, I also think that the paper needs extra work to address the proof gap and the new assumption as well as justifications for existing condition/assumptions.
We greatly appreciate the reviewer’s time and effort in evaluating our work. Please let us know if our response addresses the concerns raised, or if further clarification is needed.
We greatly appreciate the reviewer’s time and effort in evaluating our work. Please let us know if our response addresses the concerns raised, or if further clarification is needed.
We greatly appreciate the reviewer’s time and effort in evaluating our work. Please let us know if our response addresses the concerns raised, or if further clarification is needed.
>Comment: Lemma 4.1: The optimality condition here is usually considered very strong, ie, there exists a point such that the gradient = 0, especially when the function considered changes according to $x$.

**Response:** To clarify, the optimality condition is actually a natural consequence of our analysis rather than an assumption. To elaborate, note that the function $s^\top F(x)+\tau f(s)$ as a function of $s$ is $\tau \sigma_f$-strongly convex uniformly for all $x\in\mathcal{X}$. The strongly convex property comes from the regularizer $\tau f(s)$ and is independent of where $x$ is. Therefore, since the optimization problem $\arg\min_{s\in\mathcal{X}}\{s^\top F(x)+\tau f(s)\}$ of finding the Frank-Wolfe direction is a strongly convex problem on a convex and compact feasible set, there is a unique global minimizer. Moreover, since $f(\cdot)$ is chosen such that $\lim_{s\rightarrow\partial \mathcal{X}}\vert|\nabla f(s)\vert|=+\infty$ (cf. Condition 4.1), the optimal solution of $\arg\min_{s\in\mathcal{X}}\{s^\top F(x)+\tau f(s)\}$ must lie in the interior of the feasible set $\mathcal{X}$ (otherwise we can easily argue a contradiction), which leads to the first-order optimality condition stated in the beginning of the proof of Lemma 4.1. In the next version, we will provide a more detailed illustration in the proof of Lemma 4.1 to support stating the optimality conditions this way.


>Comment: The assumption that there exists $\bar{F}=\max\vert|F(x)\vert|_2$ seems unusual and strong and the dependence of the convergence on $\bar{F}$ is not convincing to me.

**Response:** To clarify, this is also not an assumption but a natural consequence of our analysis. Since the feasible set $\mathcal{X}$ is compact, and the function $F(\cdot)$ is Lipschitz continuous (hence continuous), the quantity $\bar{F}:=\max_{x\in\mathcal{X}}\vert|F(x)\vert|$ is well-defined and finite according to the extreme value theorem. We will clarify this point in the next version of this work. In our convergence bound, $\bar{F}$ only appears as a constant, hence does not impact the overall convergence rate.

>Comment: Empirically, there is a gap between extragradient and the proposed algorithm.

**Response:** In Figure 1, it is not completely clear which algorithm has the better rate of convergence as Frank-Wolfe seems to decay faster in the beginning while EG has a better convergence rate afterward. Theoretically, both generalized Frank-Wolfe and EG have a comparable $O(1/\sqrt{T})$ rate of convergence. In the stochastic setting, EG fails to converge while our variant of Frank-Wolfe (i.e., Algorithm 3) has provable last-iterate convergence. 

That 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.
Combining Eqs. (2) and (3) with Eq. (1), assuming without loss of generality that the regularization parameter $\tau$ is chosen to be less than $1$, we have
$$
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))$$
$$\leq -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+\left(\frac{2L_JD_{\mathcal{X}}}{2}+\frac{L^2}{\tau \sigma_f}\right)\vert|x_{t+1}-x_t\vert|^2$$
$$\leq -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+\left(\frac{2L_JD_{\mathcal{X}}}{2}+\frac{L^2}{\sigma_f}\right)\frac{1}{\tau}\vert|x_{t+1}-x_t\vert|^2$$
$$= -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+ \frac{M}{\tau}\vert|x_{t+1}-x_t\vert|^2,\qquad\qquad\qquad(4)
$$
where we denote $M=\frac{2L_JD_{\mathcal{X}}}{2}+\frac{L^2}{\sigma_f}$ in Eq. (4) for simplcity of notation. To proceed, using the same line of analysis as we did from the third inequality to the last inequality in Line 808, we have
$$
E_1
\leq -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+\frac{M}{\tau}\vert|x_{t+1}-x_t\vert|^2\qquad\qquad\qquad$$
$$\leq -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+\frac{8\alpha_t^2MD_{\mathcal{X}}^2}{\tau} +\frac{2M\alpha_t^2}{\tau}\vert|w_t\vert|^2.
$$
In view of the previous inequality, the first term on the right-hand side is mean zero due to $\{w_t\}$ being a martingale difference sequence (cf. Assumption 4.2), and the rest of the terms are the same (up to a multiplicative constant that is independent of $\tau$) as the terms on the right-hand side of the last inequality in Line 808. Following the same analysis starting from Line 809, the overall finite-time bound (with the same rate of convergence) can be reproduced. 

**In summary**, the convergence analysis for Algorithm 2 can be reproduced with the additional assumption that the Jacobian matrix of $F(\cdot)$ is Lipschitz continuous. The analysis of Algorithm 1 for zero-sum games remains intact since the operator $F(\cdot)$ in that case is linear, hence the Jacobian is a constant, which is automatically Lipschitz. The analysis for Algorithm 3 remains intact as it does not require the additional assumption.

It is an interesting future direction to investigate whether the additional Lipschitz continuity assumption on the Jacobian matrix is necessary for the convergence of Algorithm 2. Intuitively, when there is stochasticity in the algorithm, we need some form of smoothness in the update to control the stochastic error. For Algorithm 3, this is achieved through the algorithm design (by creating a timescale separation between the variance reduced stochastic estimate $y_t$ and the main iterate $x_t$). In Algorithm 2, since the noise is directly added to the update equation, we imposed the additional Lipschitz continuity assumption for the analysis.
>Comment: 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?

**Response:**  Algorithm 3 Line 3 is indeed a key step in the algorithm design and is essential for the convergence analysis. In the following, we first consider the case without the variance-reduced gradient estimation step, illustrate the potential issues, and then elaborate on why introducing Algorithm 3 Line 3 addresses this issue. 

Suppose that we directly use the noisy estimate $F(x_t)+z_t$ in Algorithm 3 Line 4 to compute the Frank-Wolfe direction (instead of going through Algorithm 3 Line 3 to construct the variance-reduced estimate $y_t$). Note that, despite replacing the hardmin with a softmin (by introducing the regularizer), the algorithm is extremely sensitive to the noise $z_t$ because the Frank-Wolfe direction computed from the accurate $F(x_t)$ and the noisy version $F(x_t)+z_t$ could be completely different. As a result, due to the lack of control on the noise, there is no convergence of $\{x_t\}$. 

Now, consider Algorithm 3 Line 3. Recall that we created a timescale separation between $y_t$ and $x_t$ by choosing $\beta\gg \alpha$. Therefore, from the perspective of $y_t$, $x_t$ is close to being stationary. For the purpose of illustration and for understanding the update equation of $y_t$, suppose that $x_t$ is completely stationary (which corresponds to $\alpha=0$). In this case, we will drop the subscript $t$ and just write $x_t$ as $x$. Given a sequence of noisy estimates ${(F(x)+z_i)}$, $0\leq i\leq t$, of $F(x)$, by running Algorithm 3 Line 3, $y_t$ is essentially a convex combination (hence a weighted average) of all the historical noisy estimates $( F(x)+z_i )_{0\leq i\leq t}$. Therefore, $y_t$ is an unbiased estimate of $F(x)$ with a much smaller variance compared with $F(x)+z_t$. As a result, compared with directly using $F(x)+z_t$, the Frank-Wolfe direction computed from using $y_t$ in Algorithm 3 Line 4 is a much more accurate estimate of the Frank-Wolfe direction computed from using the accurate $F(x)$, which eventually leads to the convergence of Algorithm $3$. 

As a final remark, we assumed $x_t$ being stationary from the perspective of $y_t$ in the above illustration, while both $x_t$ and $y_t$ are moving simultaneously (while at different rates) in Algorithm 3. Therefore, the proof consists of a rigorous two-timescale analysis by studying both the estimation error $\vert|y_t-F(x_t)\vert|^2$ and the gap of the Lyapunov function $V(\cdot)$ at the same time.

>Comment: 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.

**Response:** The introduction of the regularizer is indeed crucial for the analysis. When $\tau=0$, even in the case of fictitious play for zero-sum games (which is a special case of our setup), establishing the $O(1/\sqrt{T})$ rate of convergence has been an open problem for more than 60 years. This is called the Karlin’s weak conjecture [1].  Resolving this open problem (and extending it to Frank-Wolfe for solving general MVI problems) is the ultimate goal of this line of research.

>[1] Karlin, S. (2003). Mathematical methods and theory in games, programming, and economics (Vol. 2). Courier Corporation.
Combining Eqs. (2) and (3) with Eq. (1), assuming without loss of generality that the regularization parameter $\tau$ is chosen to be less than $1$, we have
$$
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))$$
$$\leq -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+\left(\frac{2L_JD_{\mathcal{X}}}{2}+\frac{L^2}{\tau \sigma_f}\right)\vert|x_{t+1}-x_t\vert|^2$$
$$\leq -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+\left(\frac{2L_JD_{\mathcal{X}}}{2}+\frac{L^2}{\sigma_f}\right)\frac{1}{\tau}\vert|x_{t+1}-x_t\vert|^2$$
$$= -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+ \frac{M}{\tau}\vert|x_{t+1}-x_t\vert|^2,\qquad\qquad\qquad(4)
$$
where we denote $M=\frac{2L_JD_{\mathcal{X}}}{2}+\frac{L^2}{\sigma_f}$ in Eq. (4) for simplcity of notation. To proceed, using the same line of analysis as we did from the third inequality to the last inequality in Line 808, we have
$$
E_1
\leq -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+\frac{M}{\tau}\vert|x_{t+1}-x_t\vert|^2\qquad\qquad\qquad$$
$$\leq -\alpha_tw_t^\top J(x_t)^\top (x_t-s_t)+\frac{8\alpha_t^2MD_{\mathcal{X}}^2}{\tau} +\frac{2M\alpha_t^2}{\tau}\vert|w_t\vert|^2.
$$
In view of the previous inequality, the first term on the right-hand side is mean zero due to $\{w_t\}$ being a martingale difference sequence (cf. Assumption 4.2), and the rest of the terms are the same (up to a multiplicative constant that is independent of $\tau$) as the terms on the right-hand side of the last inequality in Line 808. Following the same analysis starting from Line 809, the overall finite-time bound (with the same rate of convergence) can be reproduced. 

**In summary**, the convergence analysis for Algorithm 2 can be reproduced with the additional assumption that the Jacobian matrix of $F(\cdot)$ is Lipschitz continuous. The analysis of Algorithm 1 for zero-sum games remains intact since the operator $F(\cdot)$ in that case is linear, hence the Jacobian is a constant, which is automatically Lipschitz. The analysis for Algorithm 3 remains intact as it does not require the additional assumption.

It is an interesting future direction to investigate whether the additional Lipschitz continuity assumption on the Jacobian matrix is necessary for the convergence of Algorithm 2. Intuitively, when there is stochasticity in the algorithm, we need some form of smoothness in the update to control the stochastic error. For Algorithm 3, this is achieved through the algorithm design (by creating a timescale separation between the variance reduced stochastic estimate $y_t$ and the main iterate $x_t$). In Algorithm 2, since the noise is directly added to the update equation, we imposed the additional Lipschitz continuity assumption for the analysis.
We thank all reviewers for carefully reading our work. In the following, we provide a point-by-point response to all reviewers' comments.