Monotone Variational Inequalities

Follow this topic Ask about this topic

Momentum

6 papers in the last four weeks, up 100% on the four weeks before. 0.1% of all new papers.

Jul 6Week of Sep 21

Latest papers 15

Sep 24, 2026math.OC

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

We study the deterministic oracle complexity of finding approximate solutions to composite monotone inclusion problems, formed by the sum of a smooth single-valued monotone operator and a maximally monotone set-valued operator, under the tangent-residual criterion. We introduce the Anchored Extra-Proximal (AEP) framework, which combines an anchored extrapolation step with an inexact anchored proximal update satisfying a relative-error condition. The framework recovers the composite Fast Extragradient method in the first-order setting and yields natural second- and higher-order extensions by replacing the operator in the implicit update with its Taylor approximation at the extrapolated point. For every

p\geq 2

, assuming that the

(p-1)

th derivative of the single-valued operator is Lipschitz continuous, we combine this construction with a bisection line search to obtain a

p

th-order method that finds a point with tangent residual at most

\varepsilon

in

\widetilde{O}(\varepsilon^{-2/(3p-1)})

oracle calls. This improves all prior upper bounds for

p

th-order methods: in particular, it improves the previous best-known

\widetilde{O}(\varepsilon^{-1/p})

tangent-residual complexity as well as the classical

O(\varepsilon^{-2/(p+1)})

bound of higher-order hybrid proximal extragradient methods under the weaker duality-gap criterion. We complement this result with a worst-case lower bound of

Ω(\varepsilon^{-2/(3p-1)})

for every deterministic algorithm in the

p

th-order oracle model, without restricting the algorithm to tensor steps or any other prescribed update structure. Thus, the proposed method attains the optimal dependence on

\varepsilon

, up to logarithmic factors, for all

p\geq2

.

Ruichen Jiang, TaeHo Yoon

Google Research · Johns Hopkins University

Monotone Variational Inequalities Proximal Operators First Order Oracle Complexity Upper Bounds

Sep 22, 2026math.OC

Polyak-Type Extragradient Methods for Monotone Root-Finding Problems

We study Polyak-type step-size selection for extragradient methods for solving deterministic and stochastic monotone root-finding problems. We show that the known projection-type correction for deterministic extragradient arises from minimizing an upper bound on the distance to a solution, paralleling the classical Polyak step-size construction. Using this viewpoint, we provide a unified deterministic analysis of the Polyak-type Extragradient Method (PolyakEG), based on a local critical condition controlling the variation of operator

F

along the extrapolation direction. This analysis does not require global Lipschitz continuity, and covers sublinear convergence under broader conditions such as Hölder continuity or

(L_0, L_1)

-Lipschitzness and linear convergence under additional strong monotonicity, all through a single framework. We then study the stochastic extensions of this approach. We first prove convergence of a direct stochastic variant, PolyakSEG, when all stochastic component operators share a common solution. We also show that, without this condition, PolyakSEG with nonvanishing step-sizes may fail to converge to a zero of the mean operator. To address this limitation, we propose DecPolyakSEG, which combines decreasing step-sizes with Polyak-type updates, and establish a sublinear residual convergence result without requiring a common solution across the component operators. These results parallel recent developments in stochastic Polyak step-sizes from the convex minimization literature and establish an analogous research avenue in the broader root-finding regime.

TaeHo Yoon, Sayantan Choudhury, Ezra Greenberg +1

Department of Applied Mathematics & Statistics Mathematical Institute for Data Science (MINDS) Johns Hopkins University

Monotone Variational Inequalities Convergence Convex Optimization

Sep 14, 2026math.OC

The fixed-point bundle method over product-of-simplex domains arising from game equilibria

This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, which is directly applicable to solving Nash equilibria. The fixed-point bundle for VIs on the product-of-simplex domain reveals a composite fiber bundle structure. The key innovation is to construct an equivalent VI on the simplex domain and establish the equivalence between the two fixed-point bundle frameworks via a fiber bundle isomorphism. Exploiting this geometric equivalence, the predictor-corrector path-following algorithm for the VI on the product-of-simplex domain is shown to inherit the convergence guarantee of the simplex-domain framework, namely, global convergence with linear gap reduction near solutions. Numerical experiments on 5600 randomly generated instances with dimensions ranging from 2-player 128-action to 128-player 2-action demonstrate robust performance. The algorithm converges in every tested instance.

Hongbo Sun

Hongbo Sun∗

Monotone Variational Inequalities Nash Equilibrium Fixed-Point Iteration Simplex Convergence

Sep 14, 2026math.OC

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

We analyze a stochastic algorithm with Halpern-type anchoring for constrained convex-concave problems and monotone variational inequalities. This single-loop and single-call algorithm uses one unbiased sample of the gradient operator at every iteration, to be applicable to monotone games with noisy feedback. With

t

denoting the iteration counter, we prove an anytime last-iterate convergence rate of

O(t^{-1/4})

for both the gradient-mapping norm and restricted gap, bypassing the

O(t^{-1/5})

constrained-anytime bottleneck in the literature. Specializing then to multi-point oracles, we use variance reduction to achieve the

O(t^{-1/2})

rate with an anytime single-loop algorithm using

2

samples per iteration. Our results allow constrained problems with a potentially unbounded feasible set; as well as a structured class of stochastic oracles whose variance need not be uniformly bounded.

Jun-Hyun Kim, Ahmet Alacaoglu

University of British Columbia, Vancouver. · Department of Mathematics, University of British Columbia, Vancouver.

Monotone Variational Inequalities Convergence First Order Oracle Complexity

Sep 9, 2026cs.LG

Nonmaximal sums of maximally monotone operators under Rockafellar's constraint qualification

We construct counterexamples to Rockafellar's sum conjecture in which two maximally monotone operators satisfy the interior-domain condition but their sum is not maximally monotone, thereby providing the complete disproof of the conjecture. We establish a general construction theorem that computes the entire monotone polar of a class of graphs, gives a necessary and sufficient condition for their maximal monotonicity, and shows how a positive rank-one perturbation yields a nonmaximal sum under this condition. We verify the theorem's hypotheses and its maximality criterion on

c_0

, thereby obtaining a counterexample to the conjecture. Furthermore, we construct a bounded linear surjection from

\ell^1

onto

c_0

and use it to obtain the counterexample on

\ell^1

. Lean formalizations of the

c_0

counterexample and the pullback lemma are also provided.

Weifeng Yang

Monotone Variational Inequalities Monotonicity Maximization Counterexample Open Problems Structural Constraints+1

Sep 8, 2026math.OC

How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond

We study the stochastic first-order oracle complexity for constrained or regularized convex-concave min-max optimization and stochastic monotone variational inequalities. We focus on the case when suboptimality is measured in terms of the gradient mapping, also known as, forward-backward or natural residual, an optimality notion that generalizes the gradient norm for unconstrained problems. In this setting, under standard unbiased oracle access with now-standard variance assumptions, the best-known complexity for making the norm of the gradient mapping less than

\varepsilon

is

\widetilde{O}(\varepsilon^{-4})

, compared to the near-optimal

\widetilde{O}(\varepsilon^{-2})

that is established in the unconstrained case. We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems to

\widetilde{O}(\varepsilon^{-2})

. We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.

Ahmet Alacaoglu

Department of Mathematics, University of British Columbia

Monotone Variational Inequalities Convex Optimization Stochastic Optimization First Order Oracle Complexity Stochastic

Aug 17, 2026cs.LG

Reference-free logged energy-oracle recovery for neural approximations of symmetric coercive variational problems: conforming Riesz reconstruction and archive-level selection

Neural PDE training yields a finite checkpoint archive, yet its logged energy errors are inaccessible without the exact solution, while loss-based selection does not necessarily recover the logged energy oracle. For admissible neural approximations of symmetric coercive variational problems, we introduce a reference-free selection rule based on minimizing a computable conforming Riesz monitor. The exact residual-energy identity and conforming projection make the monitor an unconditional lower bound converging monotonically to each logged energy error under nested conforming refinement; under saturation, hierarchical enrichment yields a computable upper estimate and hence a lower-upper bracket. A key finding is that archive selection is order-sensitive: unresolved checkpoint-dependent components can reverse the oracle-non-oracle ranking at finite resolution, so checkpointwise recovery alone is insufficient. For finite archives, we prove uniform recovery, yielding convergence to the logged-oracle error and, without saturation, logged-oracle selection at sufficiently fine auxiliary resolution. Under saturation, the bracket gives a computable near-oracle bound and certifies unique logged-oracle selection upon interval separation. We also bound logging-resolution loss and certify oracle inclusion over prescribed comparison trajectories. The resulting criterion replaces inaccessible exact-error minimization by computable, training-independent post-training selection on the intrinsic energy-error scale, requiring only the computed candidates and the variational problem. Experiments on diffusion and elasticity, including a non-manufactured perforated plate, demonstrate energy-scale calibration, oracle-level selection, and modest post-processing cost.

Karim Bounja, Lahcen Laayouni, Boujemaa Achchab +1

Laboratory for Analysis and Modeling of Systems and Decision Support (LAMSAD), Hassan 1st University of Settat, Settat 26000, Morocco. · Department of Computer Science, School of Science and Engineering, Al Akhawayn University in Ifrane, Ifrane 53000, Morocco.

Reconstruction Error Neural Approximations Variational Neural Partial Differential Equation Solvers Monotone Variational Inequalities Motion Reconstruction Branch+2

Aug 9, 2026math.OC

Halpern Iteration Achieves $\tilde{\mathcal{O}}(ε^{-1/p})$ $p$ th-Order Oracle Complexity for Monotone Variational Inequalities

We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at the rate of

\mathcal{O}(T^{-1.5})

. For convex-concave minimax optimization, a subset of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved the complexity to

\tilde{\mathcal{O}}( T^{-1.75})

. However, it is open whether the conjectured complexity for MVI can be improved. In this paper, by using a large-step inexact Halpern iteration, we propose a novel Halpern-NPE method that achieves an even faster rate of

\tilde{\mathcal{O}}(T^{-2})

for solving MVIs. We also provide the

p

th-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of

\mathcal{O}(T^{-(p-1)})

, and then combine it with the Halpern iteration to achieve a faster convergence rate of

\tilde{\mathcal{O}}(T^{-p})

. This improves all prior results for

p \ge 2

and matches the classical extragradient method for

p=1

.

Lesi Chen, Xinliang Zhang, Hengyu Wang +3

1IIIS, Tsinghua University · Apex Intelligence · School of Mathematical Sciences, Tongji University +2

Monotone Variational Inequalities First Order Oracle Complexity Newton Optimal Sample Complexity

Aug 6, 2026math.OC

On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities

We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independent-sample SEG (I-SEG) and assume either that the domain is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes.

TaeHo Yoon, Nicolas Loizou

Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science, Johns Hopkins University.

Monotone Variational Inequalities Convergence Lipschitz Continuity

Jul 25, 2026cs.LG

Directional Influence Function: Estimating Training Data Influence in Constrained Learning

As constrained learning becomes increasingly common, models are trained under explicit feasibility requirements to enforce fairness, safety, robustness, regulariza- tion, and physics or logic constraints. Understanding how training samples in- fluence the model solution (e.g., learned parameters) is crucial for interpretability and robustness. The classical influence function (IF) estimates sample contribu- tions via local sensitivity analysis, measuring how the solution changes when a specific training sample is perturbed or removed. However, IF becomes unreli- able in constrained settings: data perturbations can reshape both the objective and the feasible region, leading to estimates that violate feasibility. In response, we propose the Directional Influence Function (DIF), a novel estimator that explicitly incorporates these constraints into influence estimation. DIF formulates the opti- mality conditions of constrained learning as a variational inequality (VI) and ana- lyzes how perturbing training data affects this VI. We validate DIF on constrained linear regression and demonstrate that it recovers leave-one-out retraining results, whereas IF and penalty-based IF exhibit significant bias. We further apply DIF to fairness-constrained CNNs, where DIF accurately predicts test loss changes under data removal and aligns closely with actual retraining. Our results establish DIF as an efficient and reliable tool for data attribution in constrained learning.

Xin Wang, R. Tyrrell Rockafellar, Xuegang +1

Jeff · Department of Civil and Environmental Engineering University of Washington Seattle, WA, USA · Department of Mathematics University of Washington Seattle, WA, USA

Influence Function Uncoupled Learning Influence Algorithmic Fairness Monotone Variational Inequalities

Jun 19, 2026math.OC

Accelerated and Stable Convergence with Anchored Optimistic Method

We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradient queries per iteration, which limits their analysis and applicability in the online and stochastic settings. We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration. In the deterministic setting, GOMA achieves the optimal accelerated last-iterate rate

O(1/k^2)

on the squared gradient norm for monotone Lipschitz operators. In the stochastic setting with unbounded variance, a simplified single-call variant of GOMA achieves a last-iterate convergence rate of

O(1/\sqrt{k})

on the squared gradient norm. To the best of our knowledge, this is the first such guarantee for stochastic monotone Lipschitz variational inequalities in the unconstrained setting without variance reduction or growing batches.

Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien +2

Universit´e de Montr´eal · Mila - Quebec AI Institute · CIFAR AI Chair +1

Monotone Variational Inequalities Convergence Acceleration

May 29, 2026math.OC

A Unifying View of Anchoring via Operator-Side Tikhonov Regularization

Anchored fixed point and monotone equation methods, including Halpern iteration, extra anchored gradient, and their relatives, add a vanishing pull toward a reference point to obtain last-iterate guarantees. Existing anchored variants often achieve sharp last-iterate guarantees, but from the update-level perspective the placement of the anchor can be algorithm-specific and conceptually opaque. We show that anchoring admits a single operator-side construction: regularize the operator queried by the base method with a vanishing Tikhonov term, then run the unmodified base method. Applied to the Picard iteration, this recipe reproduces the Halpern iteration; applied to the forward step, extragradient (EG), and past extragradient (PEG, also known as Popov's method), it yields three variants whose anchor placements inherit the base method's query pattern. The forward-step instantiation gives a new residual convergence guarantee, while the EG and PEG instantiations give new regularized variants. The four analyses share a residual recurrence, recovering the

O(1/k)

Halpern residual-norm convergence rate, giving

O(1/\sqrt{k})

for the regularized forward step, and giving

O(1/k)

for the regularized EG and PEG variants in the unconstrained monotone Lipschitz setting.

Zihao Chen

UC Berkeley

Monotone Variational Inequalities Proximal Operators Newton Convergence Regularization Perspective

May 18, 2026math.OC

Efficient Gradient Methods for Distributed Saddle Problems

The distributed setting for Saddle Problems (SPs) has recently emerged as a framework for various modern applications in machine learning and multiagent systems. Despite its relevance, the theoretical foundations of this setting have not yet been thoroughly established. In this paper, we advance this research direction by formalizing the distributed setup for SPs and providing rigorous definitions of communication and computational costs. Our main result is a novel decoupled method that achieves optimal communication cost within the zero-respecting framework. Our method is based on a multi-stage reduction to the decoupled minimization of residual norms, which yields strict improvements over the best known communication cost for the class and the long-standing oracle cost of the Extragradient method. Further, we show by a matching lower bound that our method is communication-optimal within the family of gradient-span algorithms. Finally, we study the extension of distributed SP into Variational Inequality Problem (VIP), which generalizes two-player zero-sum games to multiplayer general-sum games. We show that our decoupled method achieves a new state-of-the-art communication complexity for this broader class.

Ruichen Luo, Anton Rodomanov, Sebastian U. Stich

Institute of Science and Technology Austria · CISPA Helmholtz Center

Decentralized Optimization Primal-Dual Methods Monotone Variational Inequalities Imperfect-Information Games Decoupling

May 12, 2026cs.LG

Approximation of Maximally Monotone Operators : A Graph Convergence Perspective

Operator learning has been highly successful for continuous mappings between infinite-dimensional spaces, such as PDE solution operators. However, many operators of interest-including differential operators-are discontinuous or set-valued, and lie outside classical approximation frameworks. We propose a paradigm shift by formulating approximation via graph convergence (Painlevé-Kuratowski convergence), which is well-suited for closed operators. We show that uniform and

L^p

approximation are fundamentally inadequate in this setting. Focusing on maximally monotone operators, we prove that any such operator can be approximated in the sense of local graph convergence by continuous encoder-decoder architectures, and further construct structure-preserving approximations that retain maximal monotonicity via resolvent-based parameterizations.

Takashi Furuya, Yury Korolev, Takaharu Yaguchi

Doshisha University, RIKEN AIP · Department of Mathematical Sciences, University of Bath, UK · Kyushu University, RIKEN AIP

Nonlinear Operators Monotone Variational Inequalities Convergence Approximation Decoder Layers

Apr 21, 2026cs.LG

An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$ -Regret Minimization

We give a Gordon-Greenwald-Marks (GGM) style black-box reduction from online learning to online multicalibration. Concretely, we show that to achieve high-dimensional multicalibration with respect to a class of functions H, it suffices to combine any no-regret learner over H with an expected variational inequality (EVI) solver. We also prove a converse statement showing that efficient multicalibration implies efficient EVI solving, highlighting how EVIs in multicalibration mirror the role of fixed points in the GGM result for

Φ

-regret. This first set of results resolves the main open question in Garg, Jung, Reingold, and Roth (SODA '24), showing that oracle-efficient online multicalibration with

\sqrt{T}

-type guarantees is possible in full generality. Furthermore, our GGM-style reduction unifies the analyses of existing online multicalibration algorithms, enables new algorithms for challenging environments with delayed observations or censored outcomes, and yields the first efficient black-box reduction between online learning and multiclass omniprediction. Our second main result is a fine-grained reduction from high-dimensional online multicalibration to (contextual)

Φ

-regret minimization. Together with our first result, this establishes a new route from external regret to Phi-regret that bypasses sophisticated fixed-point or semi-separation machinery, dramatically simplifies a result of Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC '25) while improving rates, and yields new algorithms that are robust to richer deviation classes, such as those belonging to any reproducing kernel Hilbert space.

Gabriele Farina, Juan Carlos Perdomo

MIT EECS · New York University

Variance Reduction Monotone Variational Inequalities