← All setups

Stochastic Regular Equality Constraints

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Minimize f subject to c=0 on Rd, with 1≤m≤d, differentiable f,c, globally Lf-Lipschitz gradient, LJ-Lipschitz Jacobian, ∥J∥HS≤Lc, and ∥Dc(x)∗v∥≥ν∥v∥. The objective is bounded below, f(x0)−inff≤Δ, and ∥c(x0)∥≤C0. Jointly measurable, unbiased, integrable oracle triples have joint variance at most σ2 and same-sample mean-square Lipschitz constant Lnoise. Independent samples are reused for paired queries. For 0<ε≤1, the returned (X,λ^) satisfies ∫(∥∇f(X)+Dc(X)∗λ^∥2+∥c(X)∥2)dP≤ε2, with measurable output and integrable residual.

Stochastic regular equalities: StochasticRegularEqualities.
Result Oracle complexity Novelty Limitations
(1) StochasticRegularEqualityKkt (Ours) (⋆⋆) (review) O((Σ38+Σ48σ2+Σ60σ/ε)ℓε2) deterministic triple calls
(2) Fletcher AL (Cui et al. 2026), Thm. 4.2 O(ε−3) expected calls per oracle; other parameters fixed. Expected-norm KKT accuracy. (1): No Hessian Lipschitzness or assumed containment with bounded ∇f,c; deterministic budget and mean-square accuracy with returned multiplier. Matches fixed-noise polynomial order. (1): Global LICQ and oracle bounds instead of regional bounds; extra logarithms, geometry powers up to Σ60, and large constants.
(3) Exact penalty (Cui et al. 2025), Thm. 4.1 O(ε−5) total triple-equivalent calls: constraint values dominate O(ε−3) gradient/Jacobian calls; other parameters fixed. Expected-norm KKT accuracy. (1): On overlap, fixed-noise cost ε−5 to ε−3 up to logarithms. Removes assumed bounded-region containment and lower singular-value bounds on random Jacobian estimates; mean-square accuracy. (1): Requires LICQ and uniform oracle bounds globally rather than along a containing region; large geometry polynomials.
(4) (Alacaoglu and Wright 2023), Thm. 3.1 (case III) O(ε−5(1+log⁡(1/ε))2) sampled calls; other parameters fixed. Expected-norm stationarity and feasibility on convex X. (1): Allows unbounded c,∇f. Rates not comparable: bounded c on X=Rd contradicts global LICQ. (1): No general convex-set constraint X; global LICQ replaces regularity required only along iterates.

Abbr: J=Dc∗; Σ=2+Lf+Lc+LJ+ν+ν−1+Δ+C0+Lnoise; ℓ=1+log⁡(Σ/ε). P is the execution law induced by IID samples. One triple call returns noisy (∇f,c,J); paired evaluations, batches, and validation are counted. LICQ denotes the displayed uniform singular-value condition.

Alacaoglu, Ahmet, and Stephen J. Wright. 2023. Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints. https://arxiv.org/abs/2311.00678v1.
Cui, Yawen, Qiankun Shi, Xiao Wang, and Xiantao Xiao. 2025. An Exact Penalty Method for Stochastic Equality-Constrained Optimization. https://optimization-online.org/wp-content/uploads/2025/11/Fully_Sto_DLA-8.pdf.
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. https://arxiv.org/abs/2606.28230v1.

Lean setup