Research map / Optimization / Nonconvex and smooth optimization
Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes
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.
Proves first convergence guarantees for projection, Korpelevich, and Popov methods on structured non-monotone variational inequalities with α-symmetric (generalized smooth) operators, using adaptive stepsizes.
Problem
Variational inequalities arising in ML (GANs, adversarial and multi-agent training) typically violate strong monotonicity and Lipschitz continuity; existing VI convergence theory does not cover generalized smooth operators.
Approach
Combines p-quasi sharpness (structured non-monotonicity) with α-symmetric generalized smoothness and designs adaptive stepsizes normalized by operator values (and iterate distances) so that projection, Korpelevich and Popov methods converge with rates matching or improving smooth-VI results; also proposes clipped Korpelevich with backtracking that needs no problem constants.
Key results
- Projection, Korpelevich and Popov methods with adaptive stepsizes converge faster than Korpelevich with golden-ratio stepsizes on the synthetic α-symmetric, p-quasi sharp operator for all three (α, p) settings.
- Korpelevich and Popov achieve linear rates for p ≤ 2 and O(k^{-2/(p-2)}) rates for p > 2, improving the O(k^{-1/(p-1)}) rate of Wei et al. (2021) under more restrictive assumptions.
- Projection method with adaptive stepsizes converges linearly to a 1-neighborhood of the solution set for p ≥ 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive stepsizes instead of golden-ratio stepsizes | Korpelevich method · VI(R², F), α ≈ 0.09, 0.66, 0.86 | distance to solution | Helped |
| Increase α and p | Projection, Korpelevich, and Popov methods with adaptive stepsizes · VI(R², F) | distance to solution | Hurt |
| Use projection instead of Korpelevich or Popov with parameter-dependent adaptive stepsizes | VI(R², F) · VI(R², F), α ≈ 0.09, 0.66, 0.86 | distance to solution | Helped |
| Use clipping with backtracking | Korpelevich method · VI(R², F), α ≈ 0.09, 0.66, 0.86 | distance to solution | Helped |
| Use decreasing stepsizes | Korpelevich and Popov methods with clipping · VI(R², F), α ≈ 0.09, 0.66, 0.86 | distance to solution | Helped |
| Increase α and p | Korpelevich with clipping and backtracking · VI(R², F) | distance to solution | No clear effect |
| Use Korpelevich or Popov instead of projection with decreasing, parameter-independent adaptive stepsizes | Projection method · VI(R², F) | distance to solution | Helped |
| Use adaptive stepsizes for Korpelevich and Popov methods on p > 2 operators | Korpelevich and Popov methods · Generalized smooth VIs | convergence rate: O(k−2/(p−2)) vs O(k−1/(p−1)) | Helped |
Surprising findings
- Projection method, despite being the simplest, outperforms the Korpelevich and Popov methods in the experiments because the stepsizes in Theorems 5.3 and 6.3 shrink with problem constants while projection's stepsizes do not depend on them.
Limitations
- Analysis is deterministic; stochastic VIs are left to future work.
- Theoretical stepsizes depend on unknown problem constants (L0, L1, alpha, p), so practical tuning is needed.
- Experiments are limited to a single synthetic 2D operator in the main text.
Experimental setup
Benchmarks: synthetic 2D unconstrained VI operator from Proposition 2.5
Metrics: distance to solution set vs iterations
Baselines: Korpelevich with golden ratio stepsizes
Builds on: Korpelevich extragradient method Popov optimistic gradient method (L0,L1)-smoothness (Zhang et al., 2020) alpha-symmetric operators (Chen et al., 2023) p-quasi sharpness (Vankov et al., 2023) golden ratio stepsizes (Böhm, 2023)
Closest papers by meaning
- Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates (NeurIPS 2026 · similarity 0.94)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.90)
- Delving into the Convergence of Generalized Smooth Minimax Optimization (ICML 2024 · similarity 0.89)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.89)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.89)
- A Primal-Dual Approach to Solving Variational Inequalities with General Constraints (ICLR 2024 · similarity 0.89)
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.