← All setups

Stochastic Generalized Monotone — Stochastic Generalized Monotone Equations

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Generalized Monotone Equations · Lean proof

Stochastic Generalized Monotone Equations

We seek a zero of a continuous monotone operator F:E→E on a finite-dimensional real Hilbert space E. For L0,L1≥0, its Lipschitz constant along each segment is bounded by L0+L1M whenever M bounds the operator norm values on that segment. A given point x0∈E lies within distance R≥0 of a zero. The oracle returns unbiased estimates of F(x) with variance at most σ2, where σ≥0, using independent, identically distributed samples. Given ε>0 and δ∈(0,1), the goal is a measurable output x¯∈E with ∥F(x¯)∥≤ε with probability at least 1−δ over oracle and independent algorithm randomness.

The operator equation is F(x)=0,x∈E. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. Let Ω be the measurable sample space. The algorithm receives E, Ω, L0, L1, x0, R, σ, ε, and δ; it accesses F through the oracle.

Our assumptions:

Assumption 1 (Continuity and monotonicity). The operator F is continuous, and for every x,y∈E, ⟨F(x)−F(y),x−y⟩≥0.

Assumption 2 (Generalized Lipschitz condition). For every x,y∈E and M∈R, the following implication holds: ∥F(x+θ(y−x))∥≤Mfor all θ∈[0,1]⟹∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Nearby zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤R.

Assumption 4 (Stochastic operator oracle). There exist 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 Eξ∼ν[g(x,ξ)]=F(x),Eξ∼ν[∥g(x,ξ)−F(x)∥2]≤σ2. At call k≥0, a query x∈E receives g(x,ξk). The sample variables (ξk)k≥0 are measurable, mutually independent, and each has law ν. The algorithm’s randomness is independent of the entire sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable and satisfy PP(∥F(x¯)∥>ε)≤δ, where P is the joint law of the algorithm’s randomness and the oracle sample sequence.

Proved result

⌈260⋅(1+L0⋅Rε+(L1⋅R)2+σ2ε2)⋅(1+log⁡(2+L0⋅Rε+L1⋅R))3⋅(1+log⁡(2+L0⋅Rε+L1⋅Rδ))⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticGeneralizedMonotone.spec
  OracleTemplate.StochasticGeneralizedMonotone.budget

Relevant previous results

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