Normalized-step stochastic SQP methods for nonconvex constrained optimization under heavy-tailed noise

In this paper, we study nonconvex constrained optimization with expectation equality constraints and non-negative bounds under heavy-tailed noise. The objective gradients, constraint values, and constraint Jacobian are accessed through stochastic oracles whose errors have bounded $p$th central moments for some $p\in(1,2)$. These conditions allow infinite-variance errors for the three types of stochastic oracles, rendering traditional variance-bounded frameworks inapplicable. To address this challenge, we propose a normalized-step stochastic sequential quadratic programming method, NS-SQP. Normalization recasts the descent analysis in terms of first-moment error bounds while retaining a controlled remainder. To handle possible loss of sampled constraint regularity, we combine local sensitivity estimates on sampling-accuracy events with uniform direction bounds and probability estimates on their complements. This yields first-moment direction perturbation bounds under geometric regularity conditions imposed solely on deterministic reference problems. Combining these estimates with sampled normal-step contraction, we establish the expected $\epsilon$-KKT guarantee conditional on the event that all prescribed iterations are completed, which occurs with high probability. We then derive separate sample-complexity bounds for the variants of NS-SQP with mini-batch estimation and with SPIDER-type recursive estimation under an additional mean $p$th-moment smoothness condition. We also apply the NS-SQP to semi-stochastic case and expectation equality-only case. Numerical results on a flood insurance risk-control problem, an importance-weighted constrained classification problem and CUTEst problems illustrate the promising performance of the proposed methods.

Article

Download

View PDF