📊 statistics

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

This paper proposes a Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) method that achieves high-probability iteration complexity bounds of $\mathcal{O}(\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-3})$ for first- and second-order stationary points, respectively, even under conditions of heavy-tailed and biased noise where exact objective information is unavailable.

Original authors: Yuchen Fang, Javad Lavaei, Sen Na

Published 2026-04-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuchen Fang, Javad Lavaei, Sen Na

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy, and bumpy landscape (a mountain range) to set up a camp. However, there are two major complications:

The Rules: You must stay on a specific, winding path (the "constraints"). You can't just walk off the trail into the woods.
The Fog: You can't see the ground clearly. Every time you ask a local guide, "How high is this spot?" or "Which way is down?", the guide gives you an answer that is slightly wrong. Sometimes they are just a little off; other times, they might shout a completely wild guess because they are having a bad day or are influenced by a heavy storm (this is the "noise").

This paper is about a new, smarter way to navigate this foggy, constrained landscape. The authors propose a method called Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP).

Here is the breakdown of their breakthrough using simple analogies:

1. The Problem with Previous Methods

In the past, scientists assumed that the "noise" from the guides was light-tailed.

The Analogy: Imagine the guides are mostly honest but occasionally make small mistakes. If they shout a number, it's usually close to the truth. Even if they scream "1000!" when the height is "10," it's a rare, tiny blip.
The Limitation: Previous math theories only worked if the noise behaved like this. They assumed the guides would never scream a "1000" unless the mountain was actually 1000 high.

But in the real world (like in finance or deep learning), noise can be heavy-tailed.

The Real World: Sometimes, a guide might be completely unreliable. They might shout "1,000,000!" because they saw a bird, or they might be biased and always say the mountain is higher than it is. These "wild guesses" happen more often than the old math allowed for.

2. The New Solution: "Trust-Region" with a Safety Net

The authors built a method that doesn't just trust the guides blindly. Instead, they use a Trust-Region approach.

The Metaphor: Imagine you are walking in the fog. Instead of taking giant leaps based on a single guide's shout, you say, "Okay, I will only take a small step within a circle of trust around me."
The Strategy:
1. Ask for a Map: You ask the guides for a rough map of the terrain inside your small circle.
2. Check the Path: You check if the path stays on the trail (the constraints).
3. The "Trust" Test: You take a small step. If the new spot is actually lower (better) than the map predicted, you say, "Great! The guide was trustworthy. I'll expand my circle and take a bigger step next time."
4. The "Doubt" Test: If the new spot is higher (worse) than predicted, you say, "The guide lied or the fog was too thick. I'll shrink my circle and take a tiny, cautious step next time."

3. Handling the "Heavy-Tailed" Noise (The Wild Guides)

This is the paper's biggest innovation. Previous methods would crash if a guide gave a "wild guess" (heavy-tailed noise). The authors' method uses special mathematical tools (like Burkholder-type inequalities and Martingale Fuk-Nagaev inequalities) to handle these wild guesses.

The Analogy: Think of the wild guesses as "outliers." If you average 100 guides, and one says "1,000,000," the average gets ruined.
The Fix: The authors' math is robust enough to say, "We know one guide is screaming nonsense, but we have enough other data points to ignore that scream and still find the right direction." They proved that even if the noise is heavy and biased (the guide is always slightly wrong), the method still works, provided you don't demand perfection (you accept a solution that is "close enough").

4. Two Types of "Good Enough"

The paper proves the method finds two types of solutions:

First-Order Stationary Point (The "Flat Spot"): You found a place where the ground is flat. You aren't going up or down.
- Result: The method finds this in roughly $1/\epsilon^2$ steps. (If you want to be twice as precise, you need 4 times the effort).
Second-Order Stationary Point (The "Valley Bottom"): You found a flat spot, but you also checked that it's a valley and not a saddle (a spot that is flat but goes up in one direction and down in another).
- Result: The method finds this in roughly $1/\epsilon^3$ steps. This is harder, but the method does it efficiently.

5. Why This Matters

Realism: Real-world data (stock prices, sensor readings, AI training data) is often "heavy-tailed." It has wild outliers. This method works in the real world, not just in a perfect, clean math lab.
Efficiency: It proves that even with bad data, you don't need to throw away your algorithm. You just need to be a bit more cautious (smaller steps) and use the right math to filter out the noise.
Validation: The authors tested this on 35 standard problems (like a driving test for algorithms) and showed it works in practice, even when the noise is crazy (like a Cauchy distribution, which is the "wildest" noise of all).

Summary

Imagine you are navigating a foggy mountain with a path you must follow, guided by people who sometimes lie or shout crazy numbers.

Old methods: "If the guide shouts a crazy number, we stop and panic."
This paper's method: "We take small, safe steps. We check if the guide was right. If they were wrong, we shrink our circle. Even if they scream '1,000,000!', our math knows how to ignore the scream and keep walking until we find the bottom of the valley."

The authors proved mathematically that this approach is fast, reliable, and works even when the "noise" is heavy and unpredictable.

1. Problem Formulation

The paper addresses nonlinear constrained stochastic optimization problems of the form:
$\min_{x \in \mathbb{R}^d} f(x) \quad \text{s.t.} \quad c(x) = 0$
where:

$f(x)$ is a stochastic objective function (its exact value, gradient, and Hessian are inaccessible).
$c(x) \in \mathbb{R}^m$ represents deterministic equality constraints.
The problem is solved using probabilistic oracles that provide estimates of the objective value ( $\bar{f}$ ), gradient ( $\bar{g}$ ), and Hessian ( $\bar{\nabla}^2 f$ ).

Key Challenge: Existing literature often assumes that estimation noise is unbiased and follows light-tailed distributions (e.g., sub-exponential). This paper tackles the more realistic and difficult scenario where:

Irreducible (Biased) Noise: Estimates contain a fixed bias (noise does not vanish even with infinite samples).
Heavy-Tailed Noise: The noise distribution has heavy tails, meaning it may only possess a finite $(1+\delta)$ -th moment (for small $\delta > 0$ ) rather than infinite moments required by sub-exponential assumptions.

2. Methodology: Trust-Region Stochastic SQP (TR-SSQP)

The authors propose a Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) algorithm. Unlike line-search methods, the trust-region approach computes the search direction and step size jointly, ensuring well-defined subproblems without requiring Hessian regularization.

Algorithm Components:

Probabilistic Oracles: The algorithm utilizes zeroth-, first-, and second-order oracles. Crucially, these oracles allow for irreducible noise (bias) and heavy-tailed noise (bounded $(1+\delta)$ -moment).
Step Computation: The trial step $\Delta x_k$ $Δ x_{k}$ is decomposed into a normal step ( $w_k$ $w_{k}$ ) to satisfy constraints and a tangential step ( $t_k$ $t_{k}$ ) to optimize the objective.
- Gradient Step: Used when the KKT residual is large to achieve first-order stationarity.
- Eigen Step: Used when the reduced Hessian has negative curvature to escape saddle points and achieve second-order stationarity.
Second-Order Correction (SOC): To mitigate the Maratos effect (where iterates stagnate near saddle points due to inaccurate linear constraint approximations), the algorithm computes a correction step $d_k$ when necessary.
Merit Function: An $\ell_2$ merit function $L_\mu(x) = f(x) + \mu \|c(x)\|$ is used to evaluate progress. The algorithm adaptively updates the penalty parameter $\mu$ and the trust-region radius $\Delta_k$ based on the ratio of actual to predicted reduction, adjusted for irreducible noise.

3. Key Contributions

The paper makes four primary theoretical and methodological contributions:

Relaxation of Noise Assumptions:
- Unlike prior works (e.g., Cao et al., 2023; Berahas et al., 2025) that require sub-exponential noise (infinite moments), this work assumes only a bounded $(1+\delta)$ -moment for the zeroth-order oracle noise. This covers a broad class of heavy-tailed distributions (e.g., $t$ -distributions with low degrees of freedom).
- It accommodates irreducible (biased) noise, meaning the estimates do not need to converge to the true value but can have a fixed error floor.
Second-Order Complexity Analysis:
- While previous constrained stochastic methods focused on first-order stationarity, this paper establishes the first non-asymptotic, high-probability complexity bounds for second-order stationarity in constrained stochastic optimization.
- It proves convergence to points that satisfy both KKT conditions and negative curvature conditions (avoiding saddle points).
Novel Technical Tools:
- The analysis employs Burkholder-type inequalities and martingale Fuk-Nagaev inequalities to quantify the tail behavior of accumulated oracle noise. These tools allow the derivation of high-probability bounds without assuming sub-exponential tails.
- A refined stopping time definition is introduced, based on deterministic KKT residuals and reduced Hessian eigenvalues, rather than model reduction.
Algorithm Design:
- The proposed TR-SSQP method is the first to combine trust-region strategies with heavy-tailed, biased noise assumptions for constrained problems, offering a robust alternative to line-search SSQP methods.

4. Main Results (Complexity Bounds)

The authors establish high-probability iteration complexity bounds. Let $\epsilon$ be the target stationarity level. The results hold provided $\epsilon$ is larger than a threshold determined by the magnitude of the irreducible noise ( $\epsilon_f, \epsilon_g, \epsilon_h$ ).

Stationarity Type	Iteration Complexity	Sample Complexity (Total)	Conditions on $\epsilon$
First-Order	$O(\epsilon^{-2})$	$O(\epsilon^{-6})$	$\epsilon \geq O(\sqrt{\epsilon_f} + \epsilon_g)$
Second-Order	$O(\epsilon^{-3})$	$O(\epsilon^{-9})$	$\epsilon \geq O(\sqrt[3]{\epsilon_f} + \sqrt{\epsilon_g} + \epsilon_h)$

Significance: These bounds match the best-known results for light-tailed noise (e.g., Berahas et al., 2025; Cao et al., 2023), demonstrating that heavy-tailed noise does not degrade the order of convergence, provided the noise has a finite $(1+\delta)$ moment.
Almost Sure Convergence: The analysis implies that for any $\delta > 0$ , the algorithm finds a stationary point in finite iterations almost surely. If irreducible noise is zero, it implies $\liminf$ -type almost sure convergence.

5. Numerical Experiments

The authors validated their theory using the CUTEst benchmark set (35 equality-constrained problems).

Noise Distributions: They tested six distributions: Normal (light-tailed), $t_4$ , $t_2$ , Log-normal, Weibull, and Cauchy (extremely heavy-tailed, no finite mean).
Findings:
- Robustness: The algorithm performed robustly across light-tailed and moderately heavy-tailed distributions ( $t_4, t_2$ , etc.).
- Heavy-Tailed Impact: Under Cauchy noise (violating the finite moment assumption), performance degraded significantly, confirming the necessity of the moment condition for theoretical guarantees.
- Hessian Approximation: Using an Averaged Hessian (AveH) strategy yielded the most stable and efficient performance compared to single-sample estimates or SR1 updates, particularly as $\epsilon$ decreased.
- Irreducible Noise: Experiments confirmed that increasing irreducible noise levels ( $\epsilon_f, \epsilon_g, \epsilon_h$ ) increased the number of iterations required, consistent with the theoretical lower bounds.

6. Significance and Impact

Bridging Theory and Practice: Real-world data in finance, engineering, and machine learning often exhibits heavy tails and bias. This paper provides the first rigorous theoretical framework for solving constrained stochastic problems under these realistic conditions.
Second-Order Guarantees: By extending complexity analysis to second-order stationarity, the method ensures the algorithm does not get stuck at saddle points, a critical feature for non-convex optimization.
Generalizability: The analytical techniques (Burkholder/Fuk-Nagaev inequalities) are independent of the specific trust-region design, suggesting that similar heavy-tailed relaxations could be applied to line-search methods and other stochastic optimization algorithms.

In summary, this work significantly advances the field of stochastic optimization by proving that Trust-Region SSQP remains efficient and theoretically sound even when faced with biased, heavy-tailed noise, provided the noise possesses a finite $(1+\delta)$ moment.