← All setups

Safe Stochastic Mfcq Kkt — Stochastic Inequality-Constrained Optimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Inequality-Constrained Optimization · Lean proof

Stochastic Inequality-Constrained Optimization

We consider minimizing a possibly nonconvex differentiable function f:E→R subject to differentiable inequalities ci(x)≤0, i=1,…,m, on a finite-dimensional real inner product space E. Gradients are globally Lipschitz and bounded on the feasible set, which satisfies a uniform constraint qualification near active constraints; a given feasible starting point has bounded objective gap. Each oracle call returns stochastic objective gradients, constraint values, and constraint gradients at two points using a shared sample, with independent samples across calls, unbiasedness, bounded variance, and mean-square Lipschitz continuity on feasible points. For ε>0 and ρ∈(0,1), the goal is a feasible output x¯ with multipliers λ¯≥0 satisfying ∥∇f(x¯)+∑i=1mλ¯i∇ci(x¯)∥≤ε and ∑i=1m|λ¯ici(x¯)|≤ε with probability at least 1−ρ.

Write c=(c1,…,cm):E→Rm and define the feasible set F={x∈E:ci(x)≤0 for all i}. The problem is minx∈Ff(x). Let J(x)=(∇ci(x))i=1m∈Em, with transpose action J(x)⊤λ=∑i=1mλi∇ci(x). The norm on E is induced by its inner product; Rm and Em carry their Euclidean product norms. For triples in V=E×Rm×Em, use ∥(a,b,C)∥V2=∥a∥2+∥b∥2+∑i=1m∥Ci∥2. The parameters satisfy m∈N,m≥1,H≥1,σ,L≥0,0<μ≤H,τ>0,Δ≥0,ε>0,0<ρ<1. The algorithm receives E, the measurable sample space Ω, m, H, σ, L, μ, τ, Δ, ε, ρ, and the starting point x0∈E.

Our assumptions:

Assumption 1 (Differentiability and gradient bounds). The functions f and ci, i=1,…,m, are Fréchet differentiable everywhere. For every x∈F and every i, ∥∇f(x)∥≤H,∥∇ci(x)∥≤H. For every x,y∈E and every i, ∥∇f(x)−∇f(y)∥≤H∥x−y∥,∥∇ci(x)−∇ci(y)∥≤H∥x−y∥.

Assumption 2 (Uniform band constraint qualification). For every x∈F, there exists z∈E with ∥z∥≤1 such that, simultaneously for all i, ci(x)≥−τ⟹⟨∇ci(x),z⟩≤−μ.

Assumption 3 (Initial feasibility and objective gap). The given point x0 belongs to F, and f(x0)−f(x)≤Δ,x∈F.

Assumption 4 (Stochastic primitive estimates). There is a probability measure ν on Ω and jointly measurable maps g:E×Ω→E,v:E×Ω→Rm,D:E×Ω→Em. Define S(x,ξ)=(g(x,ξ),v(x,ξ),D(x,ξ)) and s(x)=(∇f(x),c(x),J(x)). For every x∈F, the three components of S(x,⋅) are Bochner integrable under ν, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[v(x,ξ)]=c(x),Eξ∼ν[D(x,ξ)]=J(x). The squared error is integrable and satisfies Eξ∼ν[∥S(x,ξ)−s(x)∥V2]≤σ2,x∈F. For every x,y∈F, the squared difference below is integrable, and Eξ∼ν[∥S(x,ξ)−S(y,ξ)∥V2]≤L2∥x−y∥2.

At call k, a query is any pair (x,y)∈E×E. The oracle returns (S(x,ξk),S(y,ξk)), using the same sample for both points and all components. The measurable samples (ξk)k≥0 are mutually independent with common distribution ν, and are independent of the algorithm’s randomness. One such paired reply counts as one oracle call. The moment conditions above apply to feasible query points.

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

Proved result

⌈3500⋅(1600⋅H2⋅σ2μ2⋅(min{ε,min{1,τ}})2+(2+3200⋅H3⋅Δμ2⋅(min{ε,min{1,τ}})2)⋅(1+40⋅σ⋅Lμ⋅min{ε,min{1,τ}}))⌉+⋅(1+⌈log⁡(2+3200⋅H3⋅Δμ2⋅(min{ε,min{1,τ}})2ρ)log⁡(4)⌉+)

OracleTemplate.Convergence LongTails.Setups.StochasticMfcqInequalities.spec
  LongTails.Theorems.SafeStochasticMfcqKkt.budget

Relevant previous results

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