Research map / Optimization / Nonconvex and smooth optimization
Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes a smoothed (entropy-regularized) generalized Frank-Wolfe algorithm for constrained monotone variational inequalities, proving O(T^-1/2) last-iterate convergence, linking it to smoothed fictitious play, and extending to stochastic MVIs with a two-timescale variance-reduced estimator achieving O(T^-1/6).
Problem
Last-iterate convergence of algorithms for constrained (stochastic) monotone variational inequality problems without curvature assumptions on the operator or the feasible set; also finite-time rates for smoothed fictitious play in zero-sum matrix games.
Approach
Replace the linear Frank-Wolfe oracle with an entropy-style strongly convex regularized oracle (softmin direction), giving a generalized FW update x_{t+1}=x_t-α(x_t-s_t+w_t) analyzed via a regularized-gap Lyapunov function; for stochastic operators, a two-timescale running average y_t of noisy F estimates feeds the FW direction.
Key results
- Generalized FW achieves O(T^-1/2) last-iterate convergence for constrained MVIs with tau = O(T^-1/2), matching extragradient and optimistic gradient rates.
- Smoothed fictitious play in finite zero-sum games has E[Nash gap] bound of order sqrt(|A1|+|A2|)/t plus log terms, giving ~O(|A1||A2|/eps^2) iteration complexity.
- Stochastic generalized FW (Algorithm 3) attains last-iterate guarantee with iteration complexity ~O(eps^-6), i.e., O(T^-1/6) rate, without curvature assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use generalized Frank-Wolfe with regularization instead of vanilla Frank-Wolfe | Frank-Wolfe for constrained monotone MVI · Constrained monotone MVI | last-iterate convergence rate: O(T −1/2) | Helped |
| Use stochastic generalized Frank-Wolfe with averaged operator estimates | Generalized Frank-Wolfe · Constrained stochastic monotone MVI | last-iterate convergence rate: O(T −1/6) | Helped |
| Use smoothed fictitious play | Learning in finite zero-sum games · Finite zero-sum games | expected Nash gap: ˜O(T −1/2) | Helped |
| Replace exact operator values with direct noisy estimates when computing the Frank-Wolfe direction | Generalized Frank-Wolfe · Stochastic MVI | convergence | Hurt |
| Use stochastic generalized Frank-Wolfe rather than stochastic mirror-prox | Stochastic MVI algorithms · Stochastic monotone MVI | convergence rate: O(T −1/6) versus O(T −1/2) | Mixed |
| Use generalized Frank-Wolfe instead of extragradient | MVI algorithms · Random 100×100 matrix game | Nash gap | Mixed |
Surprising findings
- Numerical experiments show the generalized FW slightly outperforms extragradient early on but extragradient performs better asymptotically due to softmax bias depending on tau.
Limitations
- Regularization (tau>0) introduces bias, so the rate depends on tau and the method does not recover vanilla FW (tau=0) guarantees.
- Stochastic rate O(T^-1/6) is slower than the O(T^-1/2) averaged-iterate rate of stochastic mirror-prox and is likely not tight.
- Experiments are small synthetic matrix games only; lower-bound tightness for FW-type methods is unknown.
Experimental setup
Benchmarks: Rock-Paper-Scissors matrix game Burglar-Policeman matrix game random 100x100 zero-sum matrix game
Metrics: convergence of gap/iterates over iterations
Baselines: extragradient optimistic gradient mirror-prox vanilla Frank-Wolfe
Builds on: Frank-Wolfe smoothed fictitious play extragradient optimistic gradient
Closest papers by meaning
- Frank-Wolfe Beyond 1/t Convergence (NeurIPS 2026 · similarity 0.88)
- Monotone Inclusion Approach to Weakly Monotone Discrete-Time Finite-Horizon Mean-Field Games (NeurIPS 2026 · similarity 0.88)
- Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity (ICML 2024 · similarity 0.87)
- Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions (ICLR 2024 · similarity 0.87)
- Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features (ICML 2024 · similarity 0.86)
- Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.