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

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.

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:

$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)$

For the first term on the right-hand side of the previous inequality, we have by Assumption 4.1 and Lemma 4.1 that

This is the same as what we did in Line 808 (from the first inequality to the third inequality).

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

Assumption: The Jacobian matrix $J(\cdot)$ of the operator $F(\cdot)$ is Lipschitz continuous.

Since $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}$.

Denote 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 $\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|,$ the 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}$: $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.$ Identifying $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: $(x_t-s_t)^\top (F(x_{t+1})-F(x_t))\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ $\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$ $= -\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$ $\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$

where 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)$).

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

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

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

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

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

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

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: From my understanding, the key idea of the Frank-Wolfe method lies in the linear minimization oracle (LMO) ...

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.

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

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.

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.

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:

$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)$

For the first term on the right-hand side of the previous inequality, we have by Assumption 4.1 and Lemma 4.1 that

This is the same as what we did in Line 808 (from the first inequality to the third inequality).

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

Assumption: The Jacobian matrix $J(\cdot)$ of the operator $F(\cdot)$ is Lipschitz continuous.

Since $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}$.

Denote 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 $\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|,$ the 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}$: $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.$ Identifying $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: $(x_t-s_t)^\top (F(x_{t+1})-F(x_t))\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ $\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$ $= -\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$ $\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$

where 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)$).

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: I think there's no apparent weaknesses. I suspect the analysis for the stochastic case might not be tight, leaving room for improvement.

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.

Comment: Despite the theoretical focus of the paper, it is recommended to make experiments more contentful by considering other problems ...

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.

Comment: Typos and notation related remarks.

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.

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.

Response: We will plot the standard deviation for the stochastic Frank-Wolfe algorithm in our numerical simulations.

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.