mlsanityData to 13 Oct 2026

Solving Constrained Variational Inequalities via a First-order Interior Point-based Method

arXiv 2206.10575 ↗First posted 21 Jun 2022stat.ML cs.LG math.OCcited by 3

Not on the map. Why?

Abstract (arXiv)

We develop an interior-point approach to solve constrained variational inequality (cVI) problems. Inspired by the efficacy of the alternating direction method of multipliers (ADMM) method in the single-objective context, we generalize ADMM to derive a first-order method for cVIs, that we refer to as ADMM-based interior-point method for constrained VIs (ACVI). We provide convergence guarantees for ACVI in two general classes of problems: (i) when the operator is xi-monotone, and (ii) when it is monotone, some constraints are active and the game is not purely rotational. When the operator is, in addition, L-Lipschitz for the latter case, we match known lower bounds on rates for the gap function of O(1/√K) and O(1/K) for the last and average iterate, respectively. To the best of our knowledge, this is the first presentation of a first-order interior-point method for the general cVI problem that has a global convergence guarantee. Moreover, unlike previous work in this setting, ACVI provides a means to solve cVIs when the constraints are nontrivial. Empirical analyses demonstrate clear advantages of ACVI over common first-order methods. In particular, (i) cyclical behavior is notably reduced as our methods approach the solution from the analytic center, and (ii) unlike projection-based methods that zigzag when near a constraint, ACVI efficiently handles the constraints.

Key facts. Cited by 3 papers in the map (data through 13 Oct 2026). Builds on 36 of its 86 references that are in the map. First posted on arXiv 21 Jun 2022.

Builds on

36 of 86 references.

References · 36

  1. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,991
  2. 2022Generative Adversarial Networkscited by 5,614
  3. 2013Intriguing properties of neural networkscited by 5,137
  4. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,328
  5. 2016Improved Techniques for Training GANscited by 2,946
  6. 2021Convex optimizationcited by 2,488
  7. 2015Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networkscited by 2,051
  8. 2019Lookahead Optimizer: k steps forward, 1 step backcited by 335
  9. 2017Training GANs with Optimismcited by 217
  10. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  11. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  12. 2018The Mechanics of n-Player Differentiable Gamescited by 118
24 more
  1. 2018Anchor regression: heterogeneous data meets causalitycited by 116
  2. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  3. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  4. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  5. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  6. 2020A causal framework for distribution generalizationcited by 68
  7. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  8. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  9. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  10. 2020The limits of min-max optimization algorithms: convergence to spurious non-critical setscited by 50
  11. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  12. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  13. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  14. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  15. 2015A General Analysis of the Convergence of ADMMcited by 22
  16. 2016Frank-Wolfe Algorithms for Saddle Point Problemscited by 18
  17. 2020Taming GANs with Lookahead-Minmaxcited by 16
  18. 2014Convergence rate analysis of several splitting schemescited by 13
  19. 2022Principal-Agent Hypothesis Testingcited by 13
  20. 2020Minimax Classification with 0-1 Loss and Performance Guaranteescited by 11
  21. 2018An ADMM-Based Interior-Point Method for Large-Scale Linear Programmingcited by 10
  22. 2022Fast Optimistic Gradient Descent Ascent (OGDA) method in continuous and discrete timecited by 10
  23. 2021Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationscited by 8
  24. 2015On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problemscited by 3

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 1.

3 papers.

  1. 2024Primal Methods for Variational Inequality Problems with Functional Constraintscited by 3
  2. 2024Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicitycited by 1
  3. 2026Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizescited by 1