← All setups

Stochastic Surjective Inequality Constraints

Descriptions may be stale. Consult the linked Lean sources.

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¯)|≤ε.

Results

Minimize f(x) subject to c(x)≤0 in a finite-dimensional real inner-product space, with m≥1, H≥1, σ,Δ≥0, 0<ε≤1. Globally, ∥∇f∥,∥J∥F≤H, ∇f,J are H-Lipschitz, and ∥λ∥≤H∥J(x)⊤λ∥ for every x,λ. The penalty Φ=f+4H(H+1)∑i[ci]+ satisfies Φ(x0)−infΦ≤Δ. Jointly measurable, integrable oracle triples Z=(g,v,D) have mean (∇f,c,J), summed variance at most σ2, and ∫∥Z(x,ω)−Z(y,ω)∥2dp≤H2∥x−y∥2. Samples are IID with law p under probability law P; paired evaluations share a sample. Target: output (x,λ≥0) such that, with P-probability at least 3/4, ∥∇f(x)+J(x)⊤λ∥≤ε, ∥[c(x)]+∥≤ε, and ∑i|λici(x)|≤ε.

Stochastic nonlinear inequalities: StochasticSurjectiveInequalities.
Result Oracle complexity Novelty Limitations
(1) SurjectiveStochasticInequalityKkt (Ours) (⋆⋆⋆) (review) O(1+m2H10Δ+m4H18σ2ε2+m4H19Δσε3) evaluations of each primitive, including batches and paired calls.
(2) SARAH Gauss–Newton (Tran-Dinh et al. 2020), Thm. 4.3 Values: O(1+σ2/ε4+Δ/ε5); gradients/Jacobians: O(1+σ2/ε2+Δ/ε3). Fixed m,H; their polynomial factors are unquantified. Target: E∥G~M∥2≤ε2 for the hinge-penalty composite. (1): Value exponent ε−5→ε−3 for fixed m,H,σ,Δ>0 as ε→0; gradient/Jacobian exponent matched. Accuracy targets differ. (1) requires global surjectivity. Conversion of (2) to KKT accuracy is unestablished; no identical-target speedup asserted. Large proved constants can dominate at moderate accuracy.
(3) Recursive momentum (Shi and Wang 2025), Thm. 7; linear-slack subclass only Total O(ε−5(1+log⁡(1/ε))2), dominated by values; gradient/Jacobian cost O(ε−3(1+log⁡(1/ε))2). Other parameters fixed; confidence 1−ε. Requires Strong MFCQ, bounded noise, samplewise smoothness, bounded c and lower-bounded f on the iterate region. (1): On the common slack subclass, value exponent 5→3 as ε→0. Finite variance and mean-square smoothness replace bounded noise and samplewise smoothness; only penalty lower bound needed. (1) has fixed 3/4 confidence; (3) has 1−ε. Global all-row surjectivity is stronger than Strong MFCQ.
(4) SmALM (Cui et al. 2026), Thm. 4.2; equality constraints only O(ε−3) expected evaluations of each primitive, other parameters fixed; expected stochastic ε-KKT accuracy. Requires bounded c, lower-bounded f, uniform full rank and Lipschitz Hessians on the iterate region. (1) covers inequalities with C1,1 data; (4) treats equalities with Lipschitz ∇2f,∇2c. Rates are not comparable: no valid KKT-preserving reduction established. (1) does not cover (4)’s equality problems; replacing c=0 by ±c≤0 violates surjectivity.

Abbr: J is the constraint Jacobian; [c]+ is the componentwise positive part; ∥⋅∥F is the Frobenius norm. Product norms square-sum the three oracle errors. A primitive evaluation means one evaluation of g, v, or D; each paired query evaluates each twice. G~M is the stochastic prox-linear gradient mapping. IID means independent and identically distributed; KKT means Karush–Kuhn–Tucker; MFCQ means Mangasarian–Fromovitz constraint qualification.

Cui, Yawen, Qiankun Shi, Xiao Wang, and Xiantao Xiao. 2026. A Fletcher’s Augmented Lagrangian-Based Stochastic First-Order Method for Nonconvex Equality-Constrained Optimization. Optimization Online preprint. https://optimization-online.org/wp-content/uploads/2026/06/SmALM-5.pdf.
Shi, Qiankun, and Xiao Wang. 2025. Adaptive Directional Decomposition Methods for Nonconvex Constrained Optimization. https://doi.org/10.48550/arXiv.2511.03210.
Tran-Dinh, Quoc, Nhan H. Pham, and Lam M. Nguyen. 2020. “Stochastic Gauss–Newton Algorithms for Nonconvex Compositional Optimization.” Proceedings of the 37th International Conference on Machine Learning, Proceedings of machine learning research, vol. 119: 9572–82. https://proceedings.mlr.press/v119/tran-dinh20a.html.

Lean setup