← All setups

Stochastic Inequalities with Surjective Jacobians

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Minimize f(x) subject to c(x)≤0 on a finite-dimensional real inner-product space. Globally, ∥∇f∥,∥J∥F,Lip(∇f),Lip(J)≤H and ∥λ∥≤H∥J(x)∗λ∥ for every x,λ, including inactive rows. The penalty F=f+4H(H+1)∑i[ci]+ satisfies F(x0)−infF≤Δ. Jointly measurable, integrable stochastic triples (g,v,D) have means (∇f,c,J), summed mean-square error at most σ2, and summed same-sample mean-square differences at most H2∥x−y∥2. Samples are IID under an abstract probability law P. Here m≥1, H≥1, Δ,σ≥0, 0<ε≤1, 0<δ<1. Target: a measurable pair (x,λ) with P{λ≥0, ∥∇f(x)+J(x)∗λ∥≤ε, ∥[c(x)]+∥≤ε, ∑i|λici(x)|≤ε}≥1−δ.

Comparison for ConfidentStochasticSurjectiveInequalities.
Result Oracle complexity Novelty Limitations
(1) ConfidentSurjectiveStochasticInequalityKkt (Ours) (⋆⋆⋆) (review) O(ℓ[1+m2H10Δε2+m4H19Δσε3]+ℓ2[1+m4H18σ2ε2]) paired triple calls, including replication and validation.
(2) Prox-linear (Zhang and Xiao 2021), Thm. 3; hinge-penalty specialization O(ε−5) total joint calls; values O(ε−5), Jacobians O(ε−3). Fixed remaining parameters; E∥GM∥2≤ε2. KKT conversion uses surjectivity. (1): Values ε−5→ε−3 for fixed positive m,H,Δ,σ and ℓ=o(ε−2). Explicit complementary KKT pair with confidence 1−δ, replacing expected prox-gradient accuracy. (1) requires global surjectivity, hence m≤dim⁡E; (2) permits broader composite objectives.
(3) Directional decomposition (Shi and Wang 2025), Thm. 7; bounded-constraint, level-bounded-objective, sample-smooth subclass O(ε−5(1+log⁡(1/ε))2) total calls; gradient/Jacobian calls O(ε−3(1+log⁡(1/ε))2). Fixed remaining parameters; KKT confidence 1−ε. (1): Value exponent 5→3 on the common subclass, fixed positive remaining parameters and ℓ=o(ε−2). Arbitrary δ; finite variance and mean-square smoothness replace bounded errors and sample-wise smoothness. No bounded c or level-bounded f required. (1) requires globally surjective whole Jacobians; (3) allows redundant rows and m>dim⁡E through slack-form strong MFCQ. Classes are incomparable.

Abbr: J=Dc; m is the constraint count; [⋅]+ is componentwise positive part; ℓ=1+log⁡(1/δ). One paired call evaluates (g,v,D) at two points with one fresh common sample; single-point primitive counts differ by universal factors. GM is the exact prox-linear gradient mapping. Prior-work constants are not mapped to m,H,Δ,σ.

Shi, Qiankun, and Xiao Wang. 2025. Adaptive Directional Decomposition Methods for Nonconvex Constrained Optimization. https://doi.org/10.48550/arXiv.2511.03210.
Zhang, Junyu, and Lin Xiao. 2021. Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization. https://doi.org/10.48550/arXiv.2004.04357.

Lean setup