← All setups

Confident Surjective Stochastic Inequality Kkt — Stochastic Inequalities with Surjective Jacobians

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Inequalities with Surjective Jacobians · Lean proof

Stochastic Inequalities with Surjective Jacobians

We consider minimizing a differentiable function f:E→R subject to ci(x)≤0, where E is a finite-dimensional real inner product space and ci:E→R, i=1,…,m, are differentiable constraints. Gradients are bounded and Lipschitz, the constraint Jacobian is uniformly surjective, and the initial penalty gap is bounded. Each oracle call returns unbiased estimates of the objective gradient, constraint values, and constraint gradients at two points using a shared sample; samples across calls are independent, with bounded variance and mean-square smoothness. Given ε∈(0,1] and δ∈(0,1), the goal is a pair (x¯,λ¯)∈E×R+m satisfying ∥∇f(x¯)+∑iλ¯i∇ci(x¯)∥≤ε, ∥(max{ci(x¯),0})i∥≤ε, and ∑i|λ¯ici(x¯)|≤ε simultaneously with probability at least 1−δ.

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),λ∈Rm. The norm on E is induced by its inner product; Rm, Em, and their products carry Euclidean product norms. In particular, ∥J(x)∥2=∑i∥∇ci(x)∥2. The parameters satisfy m≥1,H≥1,σ≥0,Δ≥0,0<ε≤1,0<δ<1. The algorithm receives E, a measurable sample space Ω, m, H, σ, Δ, ε, δ, and a given starting point x0∈E.

Our assumptions:

Assumption 1 (Regularity and surjectivity). The functions f and ci are Fréchet differentiable everywhere. For every x,y∈E and λ∈Rm, ∥∇f(x)∥≤H,∥J(x)∥≤H,∥∇f(x)−∇f(y)∥≤H∥x−y∥,∥J(x)−J(y)∥≤H∥x−y∥,∥λ∥≤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 x0 satisfies Φ(x0)−Φ(x)≤Δfor every x∈E.

Assumption 3 (Stochastic estimates). There is a probability law ν on Ω and jointly measurable maps g:E×Ω→E,v:E×Ω→Rm,D:E×Ω→Em. Set F(x,ξ)=(g(x,ξ),v(x,ξ),D(x,ξ)),T(x)=(∇f(x),c(x),J(x)). For every fixed x∈E, the three components of F(x,⋅) are Bochner integrable under ν, and Eξ∼ν[F(x,ξ)]=T(x). For every x,y∈E, the random variables ∥F(x,ξ)−T(x)∥2 and ∥F(x,ξ)−F(y,ξ)∥2 are integrable and satisfy Eξ∼ν[∥F(x,ξ)−T(x)∥2]≤σ2,Eξ∼ν[∥F(x,ξ)−F(y,ξ)∥2]≤H2∥x−y∥2.

A query is any pair (x,y)∈E×E. At call k, the oracle returns (F(x,ξk),F(y,ξk)). The samples (ξk)k≥0 are measurable, mutually independent, and each has law ν. They are independent of the algorithm’s randomness. Thus one call provides both triples using the same sample, including when the query points are chosen adaptively.

After the allotted calls, the algorithm must return a measurable pair (x¯,λ¯)∈E×Rm. Define c+(x)=(max{ci(x),0})i=1m. The required accuracy is P(λ¯∈R+m,∥∇f(x¯)+J(x¯)⊤λ¯∥≤ε,∥c+(x¯)∥≤ε,∑i=1m|λ¯ici(x¯)|≤ε)≥1−δ, where P is the joint law of the algorithm’s randomness and the oracle samples.

Proved result

⌈(2⋅log⁡(2δ)+2)⋅(70+229⋅m2⋅H10⋅Δ+244⋅m4⋅H18⋅σ2ε2+248⋅m4⋅H19⋅Δ⋅σε3+(8⋅log⁡(2δ)+2)⋅(2+240⋅m4⋅H18⋅σ2ε2))⌉+

OracleTemplate.Convergence LongTails.Setups.ConfidentStochasticSurjectiveInequalities.spec
  LongTails.Theorems.ConfidentSurjectiveStochasticInequalityKkt.budget

Relevant previous results

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