Primal Methods for Constrained Variational Inequalities: Optimal Rates, Feasibility Trade-offs, and Lower Bounds
Abstract
Since Zhang et al. \cite{Zhang2025} introduced the first purely primal methods for monotone variational inequalities subject to convex functional constraints, the field has lacked a complete understanding of the complexity limits of this oracle class. We develop a theory that resolves the critical gaps left by their pioneering framework. Our Optimal Primal Constrained Gradient Method (OPCGM) establishes convergence rates and lower bounds for algorithms restricted to local linear constraint approximations. For strongly monotone operators, we prove that a refined primal gradient method achieves the optimal 𝒪(1/T) rate for both optimality gap and constraint violation, eliminating the suboptimal exponent present in prior work. For Lipschitz monotone operators, we propose a primal extragradient variant that achieves the optimal 𝒪(1/ε) gap complexity using only quadratic programming oracles, at the cost of a constant asymptotic feasibility violation for the averaged iterate; we prove that the first half-step is necessarily infeasible for the natural class of constant-stepsize primal extragradient methods on smooth convex constraints with positive curvature. We establish lower complexity bounds for primal methods restricted to local linear approximations, proving Ω(1/ε2) for Lipschitz monotone variational inequalities with Lipschitz constant scaling as Θ(1/ε), and Ω(1/ε) for standard Lipschitz monotone variational inequalities. We design a single-loop primal method that achieves an 𝒪(1/√T) gap rate with only a domain-radius estimate, at the cost of a problem-dependent asymptotic feasibility constant that we prove is unavoidable. For strongly monotone problems, we prove that the last iterate converges at the optimal 𝒪(1/T) rate.
Related
- Optimal High-Order Methods for Solving Monotone Variational Inequalities
- Parameter-Free First-Order Method for Constrained Variational Inequalities
- Certified Residual Quasi-Newton Methods for Distributed Variational Inequalities
- Extragradient and Past Extragradient Methods for (L0,L1)-Lipschitz Variational Inequalities
- Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption
BibTeX
@misc{yao2026primal,
title = {{Primal Methods for Constrained Variational Inequalities: Optimal Rates, Feasibility Trade-offs, and Lower Bounds}},
author = {Yonghong Yao and Lateef O. Jolaoso and Yekini Shehu and Jen-Chih Yao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32981},
eprint = {2609.32981},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32981},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Primal Methods for Constrained Variational Inequalities: Optimal Rates, Feasibility Trade-offs, and Lower Bounds
AU - Yonghong Yao
AU - Lateef O. Jolaoso
AU - Yekini Shehu
AU - Jen-Chih Yao
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32981
UR - https://arxiv.org/abs/2609.32981
AB - Since Zhang et al. \cite{Zhang2025} introduced the first purely primal methods for monotone variational inequalities subject to convex functional constraints, the field has lacked a complete understanding of the complexity limits of this oracle class. We develop a theory that resolves the critical gaps left by their pioneering framework. Our Optimal Primal Constrained Gradient Method (OPCGM) establishes convergence rates and lower bounds for algorithms restricted to local linear constraint approximations. For strongly monotone operators, we prove that a refined primal gradient method achieves the optimal 𝒪(1/T) rate for both optimality gap and constraint violation, eliminating the suboptimal exponent present in prior work. For Lipschitz monotone operators, we propose a primal extragradient variant that achieves the optimal 𝒪(1/ε) gap complexity using only quadratic programming oracles, at the cost of a constant asymptotic feasibility violation for the averaged iterate; we prove that the first half-step is necessarily infeasible for the natural class of constant-stepsize primal extragradient methods on smooth convex constraints with positive curvature. We establish lower complexity bounds for primal methods restricted to local linear approximations, proving Ω(1/ε^2) for Lipschitz monotone variational inequalities with Lipschitz constant scaling as Θ(1/ε), and Ω(1/ε) for standard Lipschitz monotone variational inequalities. We design a single-loop primal method that achieves an 𝒪(1/√T) gap rate with only a domain-radius estimate, at the cost of a problem-dependent asymptotic feasibility constant that we prove is unavoidable. For strongly monotone problems, we prove that the last iterate converges at the optimal 𝒪(1/T) rate.
ER -