← All setups

Finite-Sum Weak Minty Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Weak Minty Inclusions

We consider finding x∈E with 0∈F(x)+T(x) in a real Hilbert space E, where F=n−1∑i=1nFi averages n≥1 component maps Fi:E→E and T:E⇉E is monotone. The average is Lipschitz, component differences satisfy a mean-square Lipschitz bound, and a weak Minty solution lies within a prescribed distance of the given starting point. The oracle returns exact component values and resolvent evaluations of T. For ε>0, the goal is a measurable pair (x¯,v¯)∈E×E with v¯∈T(x¯) almost surely and EP∥F(x¯)+v¯∥2≤ε2, where P is the law of the algorithm’s randomness.

More precisely, the inclusion is find x∈E such that 0∈F(x)+T(x),F(x)=1n∑i=1nFi(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The parameters satisfy n∈N,n≥1,0<L≤Λ,ρ≥0,ρL<1,R≥0,ε>0. The algorithm receives E,n,L,Λ,ρ,R,ε and the starting point x0∈E; the maps Fi and T are accessed through the oracle.

Our assumptions:

Assumption 1 (Monotonicity and resolvent access). For every x,y∈E, a∈T(x), and b∈T(y), ⟨a−b,x−y⟩≥0. There is a map J:R×E→E, written Jη(z), such that z−Jη(z)η∈T(Jη(z)),η>0,z∈E.

Assumption 2 (Finite-sum Lipschitz bounds). For all x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥,1n∑i=1n∥Fi(x)−Fi(y)∥2≤Λ2∥x−y∥2.

Assumption 3 (Weak Minty solution and initial distance). There exists x⋆∈E such that −F(x⋆)∈T(x⋆),∥x0−x⋆∥≤R, and, for every y∈E and v∈T(y), ⟨F(y)+v,y−x⋆⟩≥−ρ∥F(y)+v∥2.

A component query (i,x) returns Fi(x) for any i∈{1,…,n} and x∈E. A resolvent query (η,z) returns Jη(z) for any η∈R and z∈E; the stated resolvent condition applies when η>0. Each query of either kind counts as one call toward a common oracle-call budget.

After the allotted calls, the output (x¯,v¯) must be measurable, its squared residual must be integrable under P, and it must satisfy v¯∈T(x¯)P-a.s.,EP[∥F(x¯)+v¯∥2]≤ε2.

Results

In a real Hilbert space with its Borel measurable structure, F=n−1∑i=1nFi is L-Lipschitz and n−1∑i∥Fi(x)−Fi(y)∥2≤Λ2∥x−y∥2. The operator A is monotone with exact, everywhere-defined resolvents for every positive step size. There is x⋆ with 0∈F(x⋆)+A(x⋆), ∥x0−x⋆∥≤R, and ⟨F(y)+v,y−x⋆⟩≥−ρ∥F(y)+v∥2 for every v∈A(y). Here n≥1, 0<L≤Λ, ρ,R≥0, ρL<1, and ε>0. The target is a measurable pair (Y,V) with V∈A(Y) almost surely and integrable squared residual satisfying ∫∥F(Y)+V∥2dP≤ε2, where P is the execution law. Each component evaluation or resolvent evaluation costs one call.

Finite-sum weak-Minty inclusions: FiniteSumWeakMintyInclusion.
Result Oracle complexity Novelty Limitations
(1) VarianceReducedWeakMintyInclusion (Ours) (⋆⋆⋆) (review)

O(ℓδmin{n(1+T/δ2),n+Λ2/L2δ3+(nΛ/L+Λ2/L2)Tδ5})

Deterministic total-call budget.

(2) (Pethick et al. 2025, Cor. 6.3)

Full weak-Minty range; finite-dimensional setting.

O(nℓδ(1+Tδ2)) (1): For δ=1/2, Λ=L, costs O(n+nT) instead of O(n+nT). Generally, accuracy-term gain min{nδ3L/Λ,nδ3L2/Λ2} when n≳Λ2/(L2δ6) and T≳δ−1(1+Λ2/(nL2)). Exact fallback matches (2). (1): Variance-reduced branch needs known Λ; margin power δ−6 instead of δ−3. Conservative leading constant.

(3) (Tran-Dinh and Nguyen-Trung 2026, sec. 3.3, Corollaries 2–3)

Finite-dimensional; ρΛ<1/(242).

O(n+n2/3(R2/η2+r02)Cε2)

Expected component and resolvent calls; 8ρ≤η<1/(32Λ).

(1): Scope: ρL<1. On (3)’s range, accuracy coefficient (nΛL+Λ2)R2 instead of n2/3Λ2R^2, with gain at least min{n1/6Λ/L,n2/3}. Deterministic budget instead of expected calls. (1): Larger universal constants.

(4) (Cai et al. 2023, Cor. 4.5)

Special case: A=0, maximally pairwise ρ-cohypomonotone F in Rd.

O((n+nΛRε)[1+log(1+ΛRnε)])

For τ=n/Λ, ρ<τ/2, and ρτL2≤c<1 fixed; target ∫∥Pτ(u)∥2dP≤τ2ε2.

(1): Scope: graph weak Minty, arbitrary monotone A, and full ρL<1 range instead of (4)’s pairwise condition and restricted range. (1): ε−2 instead of ε−1 up to a logarithm. Different residual targets; no identical-output cost comparison established.

(5) (Alizadeh et al. 2025, Cor. 2, v3)

Euclidean special case: A=∂(h+IX), n>1, ρΛ<1/[32(1+2)].

Claimed O(n+Λ2R2ε2) component/proximal calls.

Existential iterate satisfying ∫dist(0,F(xt)+A(xt))dP≤ε.

(1): Full ρL<1 range; certified pair with expected squared residual instead of (5)’s existential expected-distance guarantee. (1): No cost saving against (5)’s claimed bound on this restricted range; accuracy criteria differ.

Abbr: δ=1−ρL, ℓ=1+log⁡(1/δ), T=L2R2/ε2. In (3), v0∈A(x0), r0=∥F(x0)+v0∥, C=1−18Λ2η2, and R^2=(R2/η2+r02)/(CΛ2); one may take η=(8ρ+1/(32Λ))/2. In (4), Pτ=Id−(Id+τF)−1 and c is a fixed constant below one. IX is the convex indicator of X; h is proper closed convex. Prior-work comparisons use the finite-dimensional overlap.

Alizadeh, Zeinab, Erfan Yazdandoost Hamedani, and Afrooz Jalilzadeh. 2025. Variance-Reduction for Variational Inequality Problems with Bregman Distance Function. https://doi.org/10.48550/arXiv.2405.10735.
Cai, Xufeng, Ahmet Alacaoglu, and Jelena Diakonikolas. 2023. Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions. https://doi.org/10.48550/arXiv.2310.02987.
Pethick, Thomas, Ioannis Mavrothalassitis, and Volkan Cevher. 2025. “Efficient Interpolation Between Extragradient and Proximal Methods for Weak MVIs.” The Thirteenth International Conference on Learning Representations. https://proceedings.iclr.cc/paper_files/paper/2025/file/7f44f98e5e70dea605d0c5baca231c58-Paper-Conference.pdf.
Tran-Dinh, Quoc, and Nghia Nguyen-Trung. 2026. Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions. https://doi.org/10.48550/arXiv.2603.15576.

Lean setup