TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise

Haoxuan Wang; Yuchen Fang; Sen Na

math.OCSep 25, 2026

TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise

Authors: Haoxuan Wang, Yuchen Fang, Sen Na

Organizations: School of Industrial and Systems Engineering, Georgia Institute of Technology · Department of Mathematics, University of California, Berkeley

Abstract

We consider stochastic nonlinear optimization problems with deterministic equality constraints. While unconstrained stochastic optimization is well understood, the interplay between optimality and feasibility in the constrained setting poses significant challenges. Moreover, existing theoretical guarantees for constrained stochastic methods predominantly rely on bounded-variance assumptions, leaving the heavy-tailed noise regime largely unexplored. To address this gap, we propose a novel trust-region method within the stochastic sequential quadratic programming framework, termed TR-SSQP. Our method employs a normal-tangential decomposition in the step computation to balance optimality and feasibility. In addition, we incorporate a normalization mechanism in the design of the trust-region radius, together with Polyak momentum for gradient estimation, ensuring stable updates without gradient clipping. When the trust-region radius and the momentum parameter decay at appropriate rates, we establish global almost-sure convergence of the method. To the best of our knowledge, this is the first asymptotic convergence result for constrained stochastic optimization under heavy-tailed noise. We demonstrate the promising performance of the proposed method through extensive numerical experiments, including comparisons among its variants and with existing constrained stochastic optimization methods.

Figures & tables

Figure 1: CUTEst results under Student-

t

heavy-tailed noise. (a)–(b) show KKT residuals for the online and increasing-batch regimes. For each

\mathfrak{p}\in\{1.2,1.4,1.6,1.8\}

, the four boxes correspond to four choices of

B_{k}

. (c)–(d) show performance profiles with respect to iterations for

\mathfrak{p}=1.8

$d$	Noise	$\mathfrak{p}$	Identity		SR1		Estimated Hessian		Averaged Hessian
$d$	Noise	$\mathfrak{p}$	Online	Batch	Online	Batch	Online	Batch	Online	Batch
50	Gaussian	–	6.41	2.93	6.45	2.92	6.28	2.92	5.21	2.89
	Pareto	$1.2$	43.51	56.81	132.44	8.30	39.02	25.17	110.23	50.60
		$1.4$	103.28	80.24	95.75	10.84	96.24	81.75	97.04	78.74
		$1.6$	28.21	8.65	24.19	7.27	20.43	6.82	24.75	8.05
		$1.8$	16.29	5.34	15.45	5.34	11.32	5.15	11.79	5.25

Table 1: KKT residuals (

10^{-2}

) for the synthetic constrained logistic regression with

d=50

. Each entry reports the mean KKT residual over five runs. ”Online” and ”Batch” denote the single-sample and increasing-batch regimes, respectively. The smallest number on each row is shown in bold. The Gaussian design serves as a light-tailed baseline, while the symmetric Pareto and Student-

t

designs vary the degree of heavy-tailedness via

\mathfrak{p}

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: KKT residual boxplots for CUTEst problems under Pareto and Student- $t$ heavy-tailed noise. For each moment order $\mathfrak{p}\in\{1.2,1.4,1.6,1.8\}$ , the four boxes correspond to TR-SSQP with four choices of $B_{k}$ : identity, SR1, estimated Hessian, and averaged Hessian.

Panel of Figure 3 — Figure 3: Performance profiles for CUTEst problems under Pareto and Student- $t$ heavy-tailed noise. Rows correspond to noise distributions and batch-size settings, while columns correspond to moment orders $\mathfrak{p}\in\{1.2,1.4,1.6,1.8\}$ . The cost is the stopping iteration needed to reach the KKT tolerance.

$d$	Noise	$\mathfrak{p}$	Identity		SR1		Estimated Hessian		Averaged Hessian
$d$	Noise	$\mathfrak{p}$	Online	Batch	Online	Batch	Online	Batch	Online	Batch
10	Gaussian	–	1.79	1.27	1.76	1.57	1.74	1.30	1.54	1.30
	Pareto	$1.2$	22.10	16.02	39.30	18.84	40.37	35.69	35.26	22.80
		$1.4$	10.75	5.54	5.40	3.59	11.64	9.73	9.05	9.66
		$1.6$	5.59	5.38	4.39	5.77	5.45	5.92	5.31	4.18
		$1.8$	3.30	4.27	3.04	4.79	4.76	2.63	4.72	3.32

Appendix

Table 2: KKT residuals (

10^{-2}

) for the synthetic constrained logistic regression experiment with

d=10,30

. Each entry reports the mean KKT residual over five runs. ”Batch” denotes the increasing-batch regime. The smallest number on each row is shown in bold. The Gaussian design serves as a light-tailed baseline, while the symmetric Pareto and Student-

t

designs vary the degree of heavy-tailedness via

\mathfrak{p}

Panel of Figure 4 — Figure 4: Convergence plots for the synthetic constrained logistic regression experiment with $d=10$ under the Gaussian covariate design. Each curve shows the KKT residual averaged over $25$ runs.

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 210 papers

A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method
Mar 10, 2026Yuchen Fang, Jihun Kim, Sen Na +2Constrained Optimization Stochastic Optimization
Department of Mathematics, University of California, Berkeley · Department of IEOR, University of California, Berkeley · School of Industrial and Systems Engineering, Georgia Tech +1
Stochastic Trust-Region Methods for Over-parameterized Models
Apr 15, 2026Aike Yang, Hao WangTrust-Region Optimization Nonconvex Stochastic Optimization
ShanghaiTech University, Shanghai, China
In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise
May 30, 2026Zijian LiuStochastic Optimization Nonconvex Stochastic Optimization
Stern School of Business, New York University

Mar 10, 2026J/K move · Enter open · S save

A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method

Yuchen Fang, Jihun Kim, Sen Na, James Demmel+1

Department of Mathematics, University of California, Berkeley · Department of IEOR, University of California, Berkeley · School of Industrial and Systems Engineering, Georgia Tech+1

Constrained Optimization Stochastic Optimization Stochastic Optimization Convergence Trust-Region Optimization

Open paper AskPDF arXiv

In this paper, we propose a trust-region interior-point stochastic sequential quadratic programming (TR-IP-SSQP) method for solving optimization problems with a stochastic objective and deterministic nonlinear equality and inequality constraints. In this setting, exact evaluations of the objective function and its gradient are unavailable, but their stochastic estimates can be constructed. In particular, at each iteration our method builds stochastic oracles, which estimate the objective value and gradient to satisfy proper adaptive accuracy conditions with a fixed probability. To handle inequality constraints, we adopt an interior-point method (IPM), in which the barrier parameter follows a prescribed decaying sequence. Under standard assumptions, we establish global almost-sure convergence of the proposed method to first-order stationary points. We implement the method on a subset of problems from the CUTEst test set, as well as on logistic regression problems, to demonstrate its practical performance.

Abstract

Stochastic Optimization

Explore similar work

A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method

Stochastic Trust-Region Methods for Over-parameterized Models

In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise