← All setups

Stochastic Regular Equality Kkt — Stochastic Regular Equality Constraints

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Regular Equality Constraints · Lean proof

Stochastic Regular Equality Constraints

We consider minimizing a differentiable function f:Rd→R subject to differentiable equalities c:Rd→Rm with c(x)=0. The gradient is Lipschitz, the constraint Jacobian is bounded and Lipschitz, and its adjoint is uniformly bounded below. The objective is lower bounded, with controlled initial gap and constraint residual. The oracle returns unbiased estimates of the gradient, constraints, and adjoint Jacobian, with bounded variance and mean-square Lipschitz dependence; consecutive call pairs share independent samples. For ε∈(0,1], the goal is (x¯,λ¯)∈Rd×Rm satisfying E[∥∇f(x¯)+∇c(x¯)⊤λ¯∥2+∥c(x¯)∥2]≤ε2, where expectation includes oracle and independent algorithm randomness.

The optimization problem is minx∈Rd: c(x)=0f(x). Here 1≤m≤d. Vector norms are Euclidean, and matrix norms ∥⋅∥F are Frobenius norms. Write A(x)=∇c(x)⊤∈Rd×m for the matrix of the adjoint derivative of c. The algorithm receives d,m,x0,Lf,Lc,LJ,ν,σ,Lnoise,Δ,C0,ε, where x0∈Rd, ν>0, and all listed scalar parameters other than ν and ε are nonnegative.

Our assumptions:

Assumption 1 (Smoothness and regularity). The functions f and c are differentiable everywhere. For all x,y∈Rd and v∈Rm, ∥∇f(y)−∇f(x)∥≤Lf∥y−x∥,∥A(x)∥F≤Lc,∥A(y)−A(x)∥F≤LJ∥y−x∥,ν∥v∥≤∥A(x)v∥.

Assumption 2 (Initial bounds). There exists flow∈R such that flow≤f(x)for every x∈Rd,f(x0)−flow≤Δ,∥c(x0)∥≤C0.

Assumption 3 (Stochastic oracle). Let μ be a probability law on a measurable sample space Ω. The jointly measurable maps g:Rd×Ω→Rd,h:Rd×Ω→Rm,H:Rd×Ω→Rd×m are Bochner integrable in the sample argument at every fixed point. For W∼μ and every x, E[g(x,W)]=∇f(x),E[h(x,W)]=c(x),E[H(x,W)]=A(x). Define the nonnegative random quantities V(x,W)=∥g(x,W)−∇f(x)∥2+∥h(x,W)−c(x)∥2+∥H(x,W)−A(x)∥F2,D(x,y,W)=∥g(y,W)−g(x,W)∥2+∥h(y,W)−h(x,W)∥2+∥H(y,W)−H(x,W)∥F2. For every x,y, these quantities are integrable and satisfy E[V(x,W)]≤σ2,E[D(x,y,W)]≤Lnoise2∥y−x∥2. Let (Wk)k≥0 be measurable, mutually independent samples, each with law μ, independent of the algorithm’s randomness. At call n≥0, a query x∈Rd returns (g(x,W⌊n/2⌋),h(x,W⌊n/2⌋),H(x,W⌊n/2⌋)). Thus calls 2k and 2k+1 use the same sample, including across the three components of each reply.

Queries may be made at any point of Rd. The output (x¯,λ¯) must be measurable, and its squared stationarity and feasibility residual must be integrable and satisfy EP[∥∇f(x¯)+A(x¯)λ¯∥2+∥c(x¯)∥2]≤ε2, where P is the joint law of the oracle samples and the independent algorithm randomness.

Proved result

⌈1047⋅((2+Lf+Lc+LJ+ν+1ν+Δ+C0+Lnoise)38+(2+Lf+Lc+LJ+ν+1ν+Δ+C0+Lnoise)48⋅σ2+(2+Lf+Lc+LJ+ν+1ν+Δ+C0+Lnoise)60⋅σε)⋅(1+log⁡(2+Lf+Lc+LJ+ν+1ν+Δ+C0+Lnoiseε))+(2+Lf+Lc+LJ+ν+1ν+Δ+C0+Lnoise)14⋅σ2⋅(1+log⁡(2+Lf+Lc+LJ+ν+1ν+Δ+C0+Lnoiseε))2ε2⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticRegularEqualities.spec
  LongTails.Theorems.StochasticRegularEqualityKkt.budget

Relevant previous results

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