← All setups

Stochastic Inequality-Constrained Optimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Minimize smooth, possibly nonconvex f subject to ci≤0, m≥1, in a finite-dimensional real inner-product space. Globally, ∇f,∇ci are H-Lipschitz; their norms are at most H on the feasible set. Here H≥1, 0<μ≤H, τ,ε>0, σ,L,Δ≥0, and every feasible x admits ∥z∥≤1 with ⟨∇ci(x),z⟩≤−μ whenever ci(x)≥−τ. The feasible start may be on the boundary; f(x0)−f(x)≤Δ for every feasible x. Jointly measurable, integrable, unbiased samples of (∇f,c,J) have joint variance at most σ2 and same-sample mean-square differences at most L2∥x−y∥2 on feasible points; successive samples are IID. Parameters are supplied. Target: with probability at least 1−ρ, 0<ρ<1, output (x,λ) satisfies c(x)≤0, λ≥0, ∥∇f(x)+J(x)⊤λ∥≤ε, and ∑i|λici(x)|≤ε. The constructed execution also keeps every query feasible on this event.

Sufficient oracle budgets for stochastic inequality KKT points under StochasticMfcqInequalities.
Result Oracle complexity Novelty Limitations
(1) SafeStochasticMfcqKkt (Ours) (⋆⋆⋆) (review) O([H2σ2μ2e2+K(1+σLμe)]⋅[1+log⁡(K/ρ)]) vector primitives, counting evaluations at each point of every paired request.
(2) LB-SGD (Usmanova et al. 2024), Theorem 8 O((m+1)ε−7polylog(ε−1,ρ−1)) per-function value/gradient calls. Reported accuracy dependence; remaining problem parameters fixed. Componentwise complementarity. (1): ε−7→ε−3 up to logs, for ε≤min{1,τ} and fixed positive other parameters on bounded, interior-start, sub-Gaussian paired overlap. Scope: boundary starts, finite variance, unbounded sets; sum complementarity. (1) needs same-sample paired, mean-square-smooth feedback and globally smooth derivatives; (2) uses one-point feedback and feasible-set smoothness.
(3) SafePD (Usmanova and Levy 2025), Theorem 17; m=1 only O(ε−6θ−1polylog(ε−1,ρ−1)) one-point value/gradient samples, including inner solves and batches. Remaining problem parameters fixed. Strict start margin α>0; sub-Gaussian noise. (1): ε−6→ε−3 up to logs for m=1, ε≤min{1,τ}, fixed positive other parameters, and paired sub-Gaussian overlap. Scope: arbitrary m, including redundant constraints; boundary starts. (1) additionally needs same-sample paired mean-square smoothness and global derivative smoothness.
(4) (Shi and Wang 2025), Theorem 7; equality-plus-bounds class O(ε−5ℓ2) total evaluations, including O(ε−3ℓ2) gradients; constraint values dominate. Fixed other parameters; bounded noise, samplewise smoothness, strong MFCQ everywhere on the bound-feasible set. Success probability 1−ε; approximate feasibility. (1): finite variance, near-active MFCQ, exact feasibility, safe queries, independently tunable ρ. Rates not comparable: a valid slack reduction between (1) and (4) is not established. (1) excludes equality constraints and needs known H,μ,τ.
(5) (Lu et al. 2025), Corollary 1(i), θ=1, and Section 5; deterministic constraints only O(ε−3ℓ3) samples and exact constraint evaluations, for fixed other parameters under a global error bound. Surely ε-feasible, with expected stationarity residual at most ε; inequality extension stated in Section 5. (1): stochastic c,J, exact feasibility, safe queries, high-probability KKT certificate with complementarity. Matches polynomial ε−3 order; differing regularity and accuracy criteria preclude a total-cost ranking. (1) needs near-active MFCQ rather than (5)’s error bound; feasibility is high probability rather than sure.

Abbr: Ji=∇ci; e=min{ε,1,τ}; K=1+H3Δ/(μ2e2); ℓ=1+log+⁡(1/ε); log+⁡t=max{0,log⁡t}. σ2 is joint variance, L joint mean-square smoothness, Δ the feasible objective gap. A vector primitive is one evaluation of ∇f, c, or J; a paired request uses at most six such primitives, or 2+4m scalar rows. In (3), θ is the MFCQ band width. polylog denotes unspecified polynomial factors in logarithms.

Lu, Zhaosong, Sanyou Mei, and Yifeng Xiao. 2025. Variance-Reduced First-Order Methods for Deterministically Constrained Stochastic Nonconvex Optimization with Strong Convergence Guarantees. https://doi.org/10.48550/arXiv.2409.09906.
Shi, Qiankun, and Xiao Wang. 2025. Adaptive Directional Decomposition Methods for Nonconvex Constrained Optimization. https://doi.org/10.48550/arXiv.2511.03210.
Usmanova, Ilnura, Yarden As, Maryam Kamgarpour, and Andreas Krause. 2024. “Log Barriers for Safe Black-Box Optimization with Application to Safe Reinforcement Learning.” Journal of Machine Learning Research 25 (171): 1–54. https://www.jmlr.org/papers/v25/22-0878.html.
Usmanova, Ilnura, and Kfir Yehuda Levy. 2025. Safe Primal-Dual Optimization with a Single Smooth Constraint. https://doi.org/10.48550/arXiv.2505.09349.

Lean setup