# High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise

arXiv: https://arxiv.org/abs/2503.19091 · HTML: https://mlsanity.com/paper/2503.19091/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 69 references that are in the map.
- First posted on arXiv 24 Mar 2025.

## Builds on (most cited first, 30 of 34)

- [Scientific Machine Learning through Physics-Informed Neural Networks: Where we are and What's next](https://mlsanity.com/paper/2201.05624/) (2022)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2007.10525/) (2020)
- [Stochastic Optimization Using a Trust-Region Method and Random Models](https://mlsanity.com/paper/1504.04231/) (2015)
- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians](https://mlsanity.com/paper/2106.13015/) (2021)
- [Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems](https://mlsanity.com/paper/2211.15943/) (2022)
- [Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2112.14799/) (2021)
- [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021)
- [Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot](https://mlsanity.com/paper/1507.05854/) (2015)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Accelerating Stochastic Sequential Quadratic Programming for Equality Constrained Optimization using Predictive Variance Reduction](https://mlsanity.com/paper/2204.04161/) (2022)
- [An Adaptive Sampling Sequential Quadratic Programming Method for Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2206.00712/) (2022)
- [Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees](https://mlsanity.com/paper/2409.09906/) (2024)
- [Convergence of trust-region methods based on probabilistic models](https://mlsanity.com/paper/1304.2808/) (2013)
- [Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming](https://mlsanity.com/paper/2205.13687/) (2022)
- [Sequential Quadratic Optimization for Stochastic Optimization with Deterministic Nonlinear Inequality and Equality Constraints](https://mlsanity.com/paper/2302.14790/) (2023)
- [First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles](https://mlsanity.com/paper/2205.03667/) (2022)
- [A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2301.00477/) (2023)
- [A Sequential Quadratic Programming Method for Optimization with Stochastic Objective Functions, Deterministic Inequality Constraints and Robust Subproblems](https://mlsanity.com/paper/2302.07947/) (2023)
- [A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems](https://mlsanity.com/paper/2304.14907/) (2023)
- [Constrained Optimization in the Presence of Noise](https://mlsanity.com/paper/2110.04355/) (2021)
- [Sample Complexity Analysis for Adaptive Optimization Algorithms with Stochastic Oracles](https://mlsanity.com/paper/2303.06838/) (2023)
- [An Adaptive Sampling Augmented Lagrangian Method for Stochastic Optimization with Deterministic Constraints](https://mlsanity.com/paper/2305.01018/) (2023)
- [Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization](https://mlsanity.com/paper/2308.03687/) (2023)
- [Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models](https://mlsanity.com/paper/2409.15734/) (2024)
- [Adaptive sampling strategies for risk-averse stochastic optimization with constraints](https://mlsanity.com/paper/2012.03844/) (2020)

## Built on by (most cited first, 4 of 4)

- [Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2602.13413/) (2026)
- [A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method](https://mlsanity.com/paper/2603.10230/) (2026)
- [TRSVR: An Adaptive Stochastic Trust-Region Method with Variance Reduction](https://mlsanity.com/paper/2601.14647/) (2026)
- [TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2609.30732/) (2026)

## Abstract (arXiv)

In this paper, we consider nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We propose a Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) method and establish its high-probability iteration complexity bounds for identifying first- and second-order ε-stationary points. In our algorithm, we assume that exact objective values, gradients, and Hessians are not directly accessible but can be estimated via zeroth-, first-, and second-order probabilistic oracles. Compared to existing complexity studies of SSQP methods that rely on a zeroth-order oracle with sub-exponential tail noise (i.e., light-tailed) and focus mostly on first-order stationarity, our analysis accommodates biased (also referred to as irreducible in the literature) and heavy-tailed noise in the zeroth-order oracle, and significantly extends the analysis to second-order stationarity. We show that under heavy-tailed noise conditions, our SSQP method achieves the same high-probability first-order iteration complexity bounds as in the light-tailed noise setting, while further exhibiting promising second-order iteration complexity bounds. Specifically, the method identifies a first-order ε-stationary point in O(ε-2) iterations and a second-order ε-stationary point in O(ε-3) iterations with high probability, provided that ε is lower bounded by a constant determined by the bias magnitude (i.e., the irreducible noise) in the estimation. We validate our theoretical findings and evaluate practical performance of our method on CUTEst benchmark test set.