← All setups

Variance Reduced Weak Minty Inclusion — Finite-Sum Weak Minty Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Finite-Sum Weak Minty Inclusions · Lean proof

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.

Proved result

⌈4398046511104⋅log⁡(21−ρ⋅L)1−ρ⋅L⋅min{n⋅(1+L2⋅R2(1−ρ⋅L)2⋅ε2),n+Λ2L2+(n⋅Λ⋅L+Λ2)⋅R2(1−ρ⋅L)2⋅ε2(1−ρ⋅L)3}⌉+

OracleTemplate.Convergence LongTails.Setups.FiniteSumWeakMintyInclusion.spec
  OracleTemplate.VarianceReducedWeakMintyInclusion.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.