Last-Iterate Convergence of Frank--Wolfe for Nonlinear Variational Inequalities on Polytopes

Abstract

We consider the Frank--Wolfe algorithm for solving variational inequalities over compact polytopes under a monotone C¹ operator Φ. The linear minimization oracle returns vertices, and we assume a coercivity condition on the Jacobian of Φ at a solution. We prove last-iterate convergence to the unique solution at rate O(k^−min{α,1}) for step sizes γ_k=α/(k+β) with β≥α>0. The bound holds uniformly over starting points and vertex tie-breaking. In particular, both 1/(k+1) and 2/(k+2) give O(k⁻¹) distance. A matching lower bound shows that this distance guarantee is worst-case order-optimal among prescribed admissible step-size schedules. We also obtain rates O(k^−min{α,1}) for the Frank--Wolfe gap and O(k^−min{α,2}) for the dual gap. These yield O(ε⁻¹) and O(ε^−1/2) calls to each oracle for sustained gap accuracy ε when α≥1 and α≥2, respectively, with instance-dependent constants. We also treat more general prescribed step-size schedules.

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
Jun-Hyun Kim, Ahmet Alacaoglu
arXiv24 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Neural-Manifold Primal-Dual Model Order Reduction and Hyper-Reduction for Nonlinear Parametric Variational Inequalities
Sofiane Ezzehi, Virginie Ehrlacher, Guillaume Enchéry +1
arXiv26 Oct 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems
Kevin Kurian Thomas Vaidyan, Ahmet Alacaoglu, Michael P. Friedlander
arXiv5 Nov 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
Last-Iterate Convergence of Clipped SGD with Linear Decay
Wei Jiang, Haomin Bai, Zechao Li
arXiv13 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
Zijun Chen, Zihan Zhang
arXiv14 Oct 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{harks2026lastiterate,
  title = {{Last-Iterate Convergence of Frank--Wolfe for Nonlinear Variational Inequalities on Polytopes}},
  author = {Tobias Harks},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17127},
  eprint = {2610.17127},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17127},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Last-Iterate Convergence of Frank--Wolfe for Nonlinear Variational Inequalities on Polytopes
AU  - Tobias Harks
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.17127
UR  - https://arxiv.org/abs/2610.17127
AB  - We consider the Frank--Wolfe algorithm for solving variational inequalities over compact polytopes under a monotone C^1 operator Φ. The linear minimization oracle returns vertices, and we assume a coercivity condition on the Jacobian of Φ at a solution. We prove last-iterate convergence to the unique solution at rate O(k^−min{α,1}) for step sizes γ_k=α/(k+β) with β≥α>0. The bound holds uniformly over starting points and vertex tie-breaking. In particular, both 1/(k+1) and 2/(k+2) give O(k^−1) distance. A matching lower bound shows that this distance guarantee is worst-case order-optimal among prescribed admissible step-size schedules. We also obtain rates O(k^−min{α,1}) for the Frank--Wolfe gap and O(k^−min{α,2}) for the dual gap. These yield O(ε^−1) and O(ε^−1/2) calls to each oracle for sustained gap accuracy ε when α≥1 and α≥2, respectively, with instance-dependent constants. We also treat more general prescribed step-size schedules.
ER  -

Abstract

Related

Cite