← All setups

Surjective Stochastic Inequality Kkt — Stochastic Surjective Inequality Constraints

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Surjective Inequality Constraints · Lean proof

Stochastic Surjective Inequality Constraints

We study minimizing a differentiable function f:E→R subject to differentiable inequalities ci(x)≤0, i=1,…,m, on a finite-dimensional real inner-product space E. Objective and constraint gradients are bounded and Lipschitz, the constraint derivative is uniformly surjective, and a given point has bounded initial penalty gap. Each oracle call returns unbiased stochastic objective gradients, constraint values, and constraint gradients at two points using one shared sample; successive samples are independent, with bounded variance and mean-square Lipschitz dependence on the points. For ε>0, the goal is a measurable pair (x¯,λ¯)∈E×Rm satisfying λ¯≥0, ∥∇f(x¯)+∑iλ¯i∇ci(x¯)∥≤ε, ∥(max{ci(x¯),0})i=1m∥2≤ε, and ∑i|λ¯ici(x¯)|≤ε simultaneously with probability at least 3/4.

The optimization problem is minx∈E: ci(x)≤0, i=1,…,mf(x). Write c=(c1,…,cm):E→Rm and J(x)=(∇ci(x))i=1m∈Em,J(x)⊤λ=∑i=1mλi∇ci(x). We use the inner-product norm on E, the Euclidean norm on Rm, and the product norm ∥A∥2=∑i=1m∥Ai∥2 on Em. In particular, all norms of J below are product norms. Fix m∈N,m≥1,H≥1,σ≥0,Δ≥0,0<ε≤1, and a given point x0∈E. The algorithm receives E, the measurable sample space Ω, and m,H,σ,Δ,ε,x0.

Our assumptions:

Assumption 1 (Regularity and surjectivity). The functions f and ci, i=1,…,m, are differentiable everywhere. For every x,y∈E, ∥∇f(x)∥≤H,∥J(x)∥≤H,∥∇f(x)−∇f(y)∥≤H∥x−y∥,∥J(x)−J(y)∥≤H∥x−y∥. Moreover, for every x∈E and λ∈Rm, ∥λ∥2≤H∥J(x)⊤λ∥.

Assumption 2 (Initial penalty gap). Define the penalty function Φ(x)=f(x)+4H(H+1)∑i=1mmax{ci(x),0}. The given point satisfies Φ(x0)−Φ(x)≤Δfor every x∈E.

Assumption 3 (Stochastic primitive estimates). There is a probability measure ν on Ω and jointly measurable maps g:E×Ω→E,v:E×Ω→Rm,D:E×Ω→Em. For each x∈E, these maps are Bochner integrable in their sample argument and satisfy Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[v(x,ξ)]=c(x),Eξ∼ν[D(x,ξ)]=J(x). For every x,y∈E, the nonnegative random variables inside the following expectations are integrable, and Eξ∼ν[∥g(x,ξ)−∇f(x)∥2+∥v(x,ξ)−c(x)∥22+∥D(x,ξ)−J(x)∥2]≤σ2, Eξ∼ν[∥g(x,ξ)−g(y,ξ)∥2+∥v(x,ξ)−v(y,ξ)∥22+∥D(x,ξ)−D(y,ξ)∥2]≤H2∥x−y∥2.

A query is any pair (x,y)∈E×E. At call k, the oracle returns ((g(x,ξk),v(x,ξk),D(x,ξk)),(g(y,ξk),v(y,ξk),D(y,ξk))). The measurable samples (ξk)k≥0 are mutually independent with common law ν, and are independent of the algorithm’s randomness. Thus both points in one query share a sample, and each paired reply counts as one oracle call.

After the allotted calls, the output (x¯,λ¯) must be measurable. Under P, the joint law of the algorithm’s randomness and the sample sequence, the following conditions must hold simultaneously with probability at least 3/4: λ¯i≥0(i=1,…,m),∥∇f(x¯)+J(x¯)⊤λ¯∥≤ε,‖(max{ci(x¯),0})i=1m‖2≤ε,∑i=1m|λ¯ici(x¯)|≤ε.

Proved result

⌈69+229⋅m2⋅H10⋅Δ+244⋅m4⋅H18⋅σ2ε2+248⋅m4⋅H19⋅Δ⋅σε3⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticSurjectiveInequalities.spec
  LongTails.Theorems.SurjectiveStochasticInequalityKkt.budget

Relevant previous results

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