← All setups

Stochastic Constrained Generalized Monotone — Stochastic Constrained Monotone Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Constrained Monotone Inclusions · Lean proof

Stochastic Constrained Monotone Inclusions

We consider a variational inequality for a continuous monotone operator F:E→E on a convex set X in a finite-dimensional real Hilbert space E. The operator satisfies a segmentwise generalized Lipschitz bound with constants L0>0 and L1≥0. A given x0∈X lies within distance R>0 of a solution x⋆ with ∥F(x⋆)∥≤G, where G≥0. Two oracles return independent unbiased estimates of F(x) with variance at most σ2, where σ≥0, and exact projections onto X. For ε>0 and δ∈(0,1), the goal is a feasible output x¯ admitting a normal vector v, meaning ⟨v,w−x¯⟩≤0 for all w∈X, with ∥F(x¯)+v∥≤ε, with probability at least 1−δ.

The variational inequality is to find x⋆∈X such that ⟨F(x⋆),w−x⋆⟩≥0for every w∈X. The norm is induced by the inner product on E. The algorithm receives E, the measurable sample space Ω, x0, and the parameters L0,L1,R,G,σ,ε,δ; it accesses F and X through the two oracles. Both oracles accept queries at any point of E, and their calls are counted separately.

Our assumptions:

Assumption 1 (Constraint set and nearby solution). The set X is convex and contains x0. There exists a solution x⋆ of the variational inequality satisfying ∥x0−x⋆∥≤R,∥F(x⋆)∥≤G. The projection oracle returns ΠX(z) at z∈E, where Π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 all x,y∈E and M∈R, the segment bound ∥F(x+θ(y−x))∥≤Mfor every θ∈[0,1] implies ∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Stochastic operator oracle). There is a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable and ∥g(x,⋅)−F(x)∥2 is integrable under ν, with EZ∼ν[g(x,Z)]=F(x),EZ∼ν[∥g(x,Z)−F(x)∥2]≤σ2. Let (Zk)k≥0 be measurable, mutually independent samples with common law ν, independent of the algorithm’s randomness. At the kth call across both oracles, a stochastic operator query at x returns g(x,Zk), while a projection query returns ΠX(x).

The output x¯∈E must be measurable. For x∈X, define the normal cone NX(x)={v∈E:⟨v,w−x⟩≤0 for every w∈X}. The required accuracy is P(x¯∈X and ∃v∈NX(x¯):∥F(x¯)+v∥≤ε)≥1−δ, where P is the joint law of the algorithm’s randomness and the independent sample sequence.

Proved result

Oracle 0:⌈2128⋅((L0+L1⋅G)⋅(1+L1⋅R)2⋅Rε+(1+L1⋅R)4+σ2ε2)⋅(1+log⁡(2+(L0+L1⋅G+L1⋅ε)⋅(1+L1⋅R)⋅Rε))3⋅(1+log⁡(2+(L0+L1⋅G+L1⋅ε)⋅(1+L1⋅R)⋅Rεδ))⌉+ Oracle 1:⌈2128⋅((L0+L1⋅G)⋅(1+L1⋅R)2⋅Rε+(1+L1⋅R)4+σ2ε2)⋅(1+log⁡(2+(L0+L1⋅G+L1⋅ε)⋅(1+L1⋅R)⋅Rε))3⋅(1+log⁡(2+(L0+L1⋅G+L1⋅ε)⋅(1+L1⋅R)⋅Rεδ))⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticConstrainedGeneralizedMonotone.spec
  OracleTemplate.StochasticConstrainedGeneralizedMonotone.budget

Relevant previous results

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