Research map / Optimization / Nonconvex and smooth optimization
A Primal-Dual Approach to Solving Variational Inequalities with General Constraints
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.
Shows that ACVI's last iterate has O(1/sqrt(K)) gap-function rate for monotone VIs without Lipschitz assumption, and proposes inexact ACVI with warm-starting plus a projection-based P-ACVI for simple inequality constraints.
Problem
Solving general constrained variational inequalities (VIs) with first-order, projection-free methods; existing ACVI analysis needed L-Lipschitz operators and exact subproblem solutions.
Approach
Relate the gap function's reference point to a KKT point that ACVI implicitly targets, giving a last-iterate O(1/sqrt(K)) rate for monotone operators without Lipschitzness; warm-start subproblems inside ACVI so they can be solved approximately; and for simple inequalities replace the barrier subproblem with a projection (P-ACVI).
Key results
- Last iterate of exact ACVI has O(1/sqrt(K)) gap-function rate for monotone VIs without L-Lipschitz assumption.
- Inexact ACVI with warm-starting recovers the O(1/sqrt(K)) rate under summable error conditions and converges faster in wall-clock time than exact ACVI on high-dimensional bilinear games.
- PI-ACVI converges faster than projected GDA, EG and other projected baselines when training a constrained GAN on MNIST.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Warm-start the approximate subproblems with the previous iteration's solutions | I-ACVI · High-dimensional bilinear game | CPU wall-clock convergence speed | Helped |
| Use a larger number of inner-loop iterations at the initial step (ablation) | I-ACVI · High-dimensional bilinear game | iterations to reach a fixed relative error | Helped |
| Increase the initial subproblem iteration count from \ell_0=100 to \ell_0=500, keeping \ell_+=20 (ablation) | PI-ACVI · MNIST constrained GAN | convergence speed | Helped |
| Use PI-ACVI instead of projected GDA | PI-ACVI · MNIST constrained GAN | FID | Helped |
| Use PI-ACVI instead of projected GDA | PI-ACVI · MNIST constrained GAN | Inception Score | Helped |
| Reduce the inner-loop iteration count and subproblem-solving steps (ablation) | I-ACVI · 2D bilinear game | convergence | Hurt |
Surprising findings
- Using many inner iterations only at the first outer step (warm-up) is enough for fast convergence, with later inner-loop iterations mattering less.
Limitations
- Inexact convergence requires summable approximation errors, which constrains the inner iteration schedule.
- P-ACVI relies on inequality constraints being cheap to project onto.
- Experiments are on small or synthetic games plus one constrained GAN setting.
Experimental setup
Datasets: MNIST
Benchmarks: 2D bilinear game high-dimensional bilinear game MNIST constrained GAN
Metrics: relative error CPU wall-clock time number of iterations FID Inception Score
Baselines: ACVI P-GDA P-EG P-OGDA P-LA (Lookahead-Minmax)
Builds on: ACVI (Yang et al., 2023) ADMM interior point methods extragradient proximal gradient warm-start analysis
Closest papers by meaning
- Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes (ICML 2024 · similarity 0.89)
- Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations (NeurIPS 2024 · similarity 0.88)
- Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates (NeurIPS 2026 · similarity 0.86)
- Extragradient Method for $(L_0, L_1)$-Lipschitz Root-finding Problems (NeurIPS 2025 · similarity 0.86)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.86)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.85)
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.