← All setups

Constrained Generalized Monotone Inequalities

Descriptions may be stale. Consult the linked Lean sources.

Constrained Generalized Monotone Inequalities

We consider a variational inequality for a continuous monotone operator F:E→E on a convex set X in a real inner product space E. The operator satisfies a segmentwise generalized Lipschitz condition with constants L0>0 and L1≥0. A given point x0∈X has bounded distance to a solution, with operator norms bounded at both points. Two exact oracles return F(x) and the projection of x onto X. For ε>0, the goal is a feasible output x¯ admitting ξ∈E with ⟨ξ,w−x¯⟩≤0 for every w∈X and ∥F(x¯)+ξ∥≤ε, almost surely under P, the law of the algorithm’s randomness.

The variational inequality asks for x⋆∈X such that ⟨F(x⋆),w−x⋆⟩≥0for every w∈X. The norm ∥⋅∥ is induced by the inner product on E. The parameters satisfy L0>0,L1≥0,R>0,G≥0,G0≥0,ε>0. The algorithm receives only E, L0, L1, and x0; the parameters R, G, G0, and ε may enter the oracle-call budgets but are not algorithm inputs.

Our assumptions:

Assumption 1 (Convex constraints and projection). The set X⊆E is convex. There exists a map ΠX:E→E satisfying, for every z∈E, ΠX(z)∈X,⟨z−ΠX(z),w−ΠX(z)⟩≤0for every w∈X.

Assumption 2 (Monotonicity and generalized Lipschitz continuity). The operator F is continuous on E and satisfies ⟨F(x)−F(y),x−y⟩≥0for all x,y∈E. For every x,y∈E and M∈R, the segment bound ∥F(x+θ(y−x))∥≤Mfor all θ∈[0,1] implies ∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Initial point and solution bounds). The given starting point satisfies x0∈X and ∥F(x0)∥≤G0. There exists a solution x⋆ of the variational inequality such that ∥x0−x⋆∥≤R,∥F(x⋆)∥≤G.

Queries to either oracle may be made at any point of E. The operator oracle returns F(x) at x, and the projection oracle returns ΠX(z) at z. Calls to these two oracles are counted separately.

For a feasible point x, define its normal cone by NX(x)={ξ∈E:⟨ξ,w−x⟩≤0 for every w∈X}. After the allotted oracle calls, the output must satisfy the normal-cone residual criterion x¯∈X,∃ξ∈NX(x¯):∥F(x¯)+ξ∥≤εP-a.s.

Results

In a real inner-product space E, X is convex with an exact projection oracle. The continuous, monotone operator F:E→E satisfies ∥F(x)−F(y)∥≤(L0+L1supz∈[x,y]∥F(z)∥)∥x−y∥ for all x,y∈E. Here L0,R,ε>0, L1,G,G0≥0, x0∈X, and there is a VI solution x⋆∈X with ∥x0−x⋆∥≤R, ∥F(x⋆)∥≤G, and ∥F(x0)∥≤G0. Target: x∈X and some ξ∈NX(x) with ∥F(x)+ξ∥≤ε, using exact F and projection calls.

Constrained generalized monotone variational inequalities: ConstrainedGeneralizedMonotone.
Result Oracle complexity Novelty Limitations
(1) ConstrainedGeneralizedMonotone (Ours) (⋆⋆⋆) (review) O((L0+L1G)(1+L1R)Rε+(1+L1R)2ℓ) total calls; two F calls and one projection per iteration.
(2) PF-NE-EG (Shen and Kılınç-Karzan 2026), App. A, Prop. 2, Lemma 10. Locally Lipschitz F on closed convex X⊆Rd. Derived bound: O(1+R2η∗2ε2+log⁡η0η∗) total F/projection calls, including rejected trials; implicit η∗>0, fixed backtracking factors. (1): ε−1 instead of ε−2 as ε→0 with other parameters fixed; explicit polynomial growth constants, with logarithmic G0 dependence. (1) needs known L0,L1 and global generalized smoothness and monotonicity; (2) needs only local Lipschitz continuity and monotonicity on X.
(3) Composite-EAG (Cai et al. 2024), Thm. 3.2. Special case: globally L-Lipschitz F on Rd, A=NX. O(1+LR/ε) total F/projection calls. (1): Scope extends to operators without a finite global Lipschitz constant. Matches known rate when L1=0 and L=L0. (1) can lose factors 1+L1R and logarithmic overhead for nearly Lipschitz operators; does not cover general proximal inclusions or negative comonotonicity covered by (3).
(4) EG (Choudhury and Loizou 2025), Thm. 3.6. Unconstrained special case: X=E=Rd, G=0. O(1+L02R2ε2+L12R2) F calls. (1): ε−1 instead of ε−2 for fixed remaining parameters and small ε; last instead of best iterate. Scope extends to constraints and F(x⋆)≠0. (1) can lose a logarithmic factor when the L12R2 term dominates (4).
(5) Repository anchored extragradient (LongTails, n.d.). Unconstrained special case: X=E, G=0. O(1+L0Rε+(1+L1R)log(1+(L0+L1G0)Rε)) F calls. (1): Scope extends to constrained VIs with F(x⋆)≠0. (1) loses a factor 1+L1R in the leading term on X=E, and has larger constants.

Abbr: NX(x)={ξ:⟨ξ,w−x⟩≤0 ∀w∈X}; [x,y] is the line segment; ℓ=1+log⁡(1+(L0+L1G0)R/ε). L is a global Lipschitz constant. η0 is the initial step and η∗=inftηt>0 the accepted-step infimum for (2). Total calls sum operator evaluations and projections; projection is the identity when X=E.

Cai, Yang, Argyris Oikonomou, and Weiqiang Zheng. 2024. “Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion.” Proceedings of the 41st International Conference on Machine Learning, Proceedings of machine learning research, vol. 235: 5312–47. https://proceedings.mlr.press/v235/cai24f.html.
Choudhury, Sayantan, and Nicolas Loizou. 2025. Extragradient Method for (L0,L1)-Lipschitz Root-Finding Problems. https://doi.org/10.48550/arXiv.2510.22421.
LongTails: AnchoredGeneralizedMonotone.lean. n.d. Lean theorem in the LongTails repository. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/AnchoredGeneralizedMonotone.lean.
Shen, Lingqing, and Fatma Kılınç-Karzan. 2026. Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities. https://doi.org/10.48550/arXiv.2604.07662.

Lean setup