← All setups

Gap Noise Constrained Generalized Monotone — Constrained Monotone Operators with Gap Noise

Descriptions may be stale. Consult the linked Lean sources.

Constrained Monotone Operators with Gap Noise · Lean proof

Constrained Monotone Operators with Gap Noise

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 generalized Lipschitz bound, and a given point x0∈X lies near a solution. Two oracles return independent-sample unbiased estimates of F on X, with variance controlled by an operator gap, and exact projections onto X. For ε>0 and δ∈(0,1), the goal is a measurable output x¯∈X admitting u∈E with ⟨u,w−x¯⟩≤0 for every w∈X and ∥F(x¯)+u∥≤ε, with probability at least 1−δ.

The underlying 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 parameters satisfy L0>0,L1≥0,R>0,G,σ,v≥0. The algorithm receives E, a measurable sample space Ω, x0, and all parameters L0,L1,R,G,σ,v,ε,δ; it accesses F and X through the two oracles.

Our assumptions:

Assumption 1 (Feasibility and reference solution). The set X⊆E is convex and contains x0. There exists a solution x⋆ of the variational inequality satisfying ∥x0−x⋆∥≤R,∥F(x⋆)∥≤G. An exact projection map ΠX:E→E is available and satisfies, for every z∈E, ΠX(z)∈X,⟨z−ΠX(z),w−ΠX(z)⟩≤0for every w∈X.

Assumption 2 (Monotonicity and generalized Lipschitz bound). The operator F is continuous on E, and for all x,y∈E, ⟨F(x)−F(y),x−y⟩≥0. For every 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 (Gap-dependent stochastic noise). There is a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈X, the random vector g(x,Z) is Bochner integrable and ∥g(x,Z)−F(x)∥2 is integrable for Z∼ν, with EZ∼ν[g(x,Z)]=F(x),EZ∼ν[∥g(x,Z)−F(x)∥2]≤σ2+v⟨F(x)−F(x⋆),x−x⋆⟩. The reference solution x⋆ is the same as above. The oracle samples (Zk)k≥0 are measurable, mutually independent, and each has law ν. This sequence is independent of the algorithm’s randomness.

Both oracles accept queries in E. At the kth oracle call, a stochastic query at x returns g(x,Zk), whereas a projection query at z returns ΠX(z). The stochastic moment conditions apply to queries in X. Stochastic-operator calls and projection calls are counted separately.

Define the normal cone at x∈X by NX(x)={u∈E:⟨u,w−x⟩≤0 for every w∈X}. After the allotted calls, the output x¯ must be measurable and satisfy P(¬[x¯∈X and ∃u∈NX(x¯):∥F(x¯)+u∥≤ε])≤δ, where P is the joint law of the oracle samples and the independent algorithm randomness.

Proved result

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

OracleTemplate.Convergence LongTails.Setups.GapNoiseConstrainedGeneralizedMonotone.spec
  OracleTemplate.GapNoiseConstrainedGeneralizedMonotone.budget

Relevant previous results

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