PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Haoxuan Wang, Yuchen Fang, Sen Na

arXiv:2609.30732v1math.OCcs.LGstat.COstat.ML

TL;DR

Constrained stochastic optimization must balance objective improvement with feasibility, while heavy-tailed gradient noise remains a challenge for theoretical guarantees. TR-SSQP combines trust-region SSQP steps with normalization and Polyak momentum, and establishes global almost-sure first-order convergence under finite p-th moment gradient noise.

  • Problem

    Constrained stochastic optimization must jointly reduce the objective and control feasibility, while heavy-tailed gradient noise remains an open challenge for convergence guarantees.

    Source: §1 · pp. 1–2

  • Method

    TR-SSQP combines a normal-tangential step decomposition with gradient normalization and Polyak momentum to handle heavy-tailed noise in a trust-region SSQP method.

    Source: §1 · pp. 2–3

  • Results

    TR-SSQP establishes global almost-sure first-order convergence under finite p-th moment gradient noise, the first such asymptotic guarantee for equality-constrained stochastic optimization.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The unified framework handles fixed and growing batch sizes, with a quantitative trade-off between sampling cost and the aggressiveness of trust-region and momentum updates.

    Source: §5 · p. 12

    The convergence analysis assumes uniformly bounded conditional p-th moments of gradient noise, although individual noise realizations may be unbounded.

    Source: §3.1 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

TR-SSQP addresses the difficulty of balancing feasibility and optimality in equality-constrained stochastic optimization, where heavy-tailed noise remains largely unexplored. The method combines trust-region and stochastic-SQP techniques and establishes global almost-sure convergence under heavy-tailed gradient noise.

1 Introduction

  • Prior constrained stochastic convergence analyses either assume bounded variance or require increasing batches and objective-value estimates, while heavy-tailed noise remains largely unexplored.The paper also notes that objective-value estimates force growing batches and increase per-iteration cost.Source: §1 · p. 2
  • TR-SSQP combines normal-tangential steps with radius normalization and Polyak momentum to balance feasibility and optimality and enable stable updates without gradient clipping.It also allows indefinite Hessian approximations without modification and requires no objective function evaluations.Source: §1 · pp. 2–3
  • The proposed method establishes global almost-sure first-order convergence, providing the first asymptotic convergence guarantee for equality-constrained stochastic optimization under finite p-th moment gradient noise.Source: §1 · p. 3
  • The unified framework handles fixed or growing batch sizes, with schedules for the trust-region radius and momentum that can be chosen without knowing p ∈ (1, 2].In the growing-batch regime, suitable polynomial batch growth permits slower decay of both schedules and more aggressive updates.Source: §1 · p. 3
  • TR-SSQP is evaluated on CUTEst benchmark problems and constrained regression tasks, with experiments reporting promising robustness and empirical performance under heavy-tailed noise.The paper also compares method variants and existing constrained stochastic optimization methods.Source: §1 · p. 3

2 TR-SSQP: Constrained Stochastic Optimization under Heavy-Tailed Noise

TR-SSQP constructs trust-region SQP steps by relaxing potentially infeasible linearized constraints and separating feasibility restoration from objective reduction. Its stochastic version uses Polyak momentum to estimate gradients.

2.1 Constraints infeasibility and relaxation

  • When the trust-region radius is too small for the linearized constraint to be feasible, TR-SSQP relaxes it to γ_k c_k + G_kΔx = 0 for γ_k ∈ (0, 1].The minimum-norm solution to the unrelaxed linearized constraint can exceed the radius; enlarging the radius would conflict with its trust-region role.Source: §2.1 · p. 4
  • The tangential subproblem need only achieve a fixed fraction η of the Cauchy reduction, using procedures such as exact minimization, dogleg, or projected conjugate gradients.The tangential step is represented in null-space coordinates and remains subject to the trust-region constraint.Source: §2.1 · p. 5
  • The normal step targets feasibility, while the tangential step lies in the constraints’ null space and reduces the objective along the linearized feasible manifold.The trial step combines a normal component in im(G_k⊤) and a tangential component in ker(G_k).Source: §2.1 · pp. 4, 6

2.2 TR-SSQP with Polyak momentum

  • TR-SSQP uses Polyak momentum for gradient estimation; its moving-average error admits finite p-th-moment control without clipping, and the trust-region bound prevents unbounded steps.The method takes the stochastic gradient estimate into the tangential model, while the normal step is independent of the samples.Source: §2.2 · pp. 6–7
  • The trust-region constraint permits B_k to be indefinite on the null space; the analysis requires only an upper bound, allowing several curvature-model choices.The paper considers identity, quasi-Newton updates, estimated Hessians, and averaged estimated Hessians.Source: §2.2 · p. 7

3 Convergence Analysis

Under standard regularity and bounded conditional p-th-moment noise assumptions, the analysis establishes global almost-sure convergence of the KKT residual from any initialization. The result allows fixed or growing batches, including one sample per iteration, under appropriate decay rates for the trust-region radius and momentum.

3.1 Assumptions

  • The analysis assumes smooth objective and constraints, boundedness and conditioning conditions, and unbiased gradient samples with uniformly bounded conditional p-th moments for p ∈ (1, 2].For p < 2, the stochastic gradient may have infinite variance.Source: §3.1 · pp. 7–8

3.2 Global almost-sure convergence

  • Normal and tangential steps reduce feasibility and optimality residuals, respectively, while shrinking trust-region radii control the second-order term.The remaining gradient-tracking error is controlled through the momentum recursion; with suitable radius, momentum, and batch sequences, its cumulative weighted contribution is finite.Source: §3.2 · p. 9
  • Theorem 3.6 establishes that the KKT residual converges to zero almost surely from any initialization when the sequences satisfy condition (17).The result uses an ℓ2-penalized Lyapunov function and the least-squares dual estimate.Source: §3 · p. 7, §3.2 · pp. 8, 10
  • The guarantee is stronger than liminf-type convergence from non-asymptotic analyses and does not require knowing the total iteration count or problem-dependent tuning constants.The paper contrasts its result with prior almost-sure guarantees that rely on bounded variance or increasing batches with objective-value estimates.Source: §3.2 · p. 10
  • Increasing batch sizes reduce the heavy-tailed martingale contribution and permit slower trust-region-radius decay, trading more samples per iteration for less conservative steps.When the batch size is fixed, N0 = 1 is allowed, and a1 = 1 with a2 ∈ (0, 1) works without knowing p ∈ (1, 2].Source: §3.2 · p. 10

4 Numerical Experiments

Across CUTEst and constrained logistic-regression experiments, increasing batches improve residuals and make curvature-based trial steps more effective under heavy-tailed noise. The online regime also operates with one stochastic gradient sample per iteration, while the logistic-regression comparison reports the lowest residuals for increasing-batch TR-SSQP among four competing methods in each setting.

Numerical experiments

  • The experiments cover CUTEst constrained nonlinear problems and synthetic constrained logistic regression, varying noise design, moment order, Bk construction, batch regime, and problem dimension.The reported section presents a subset of results; full details and additional comparisons are deferred to Appendix D.Source: §4 · pp. 11–12

CUTEst benchmark problems

  • With one sample per iteration, curvature can be obscured by heavy-tailed noise and the identity model remains competitive; batching makes curvature-aware choices more effective.In the most heavy-tailed CUTEst setting, p = 1.2, curvature-aware choices are particularly effective under increasing batches.Source: §4 · p. 11
  • Increasing batches substantially lower final KKT residuals across moment orders and all four Bk choices under Student-t noise, and solve more problems within a small iteration ratio at p = 1.8.Figure 1 compares online and increasing-batch residuals and performance profiles; increasing-batch results also show the curvature benefit most clearly at p = 1.2.Source: §4 · p. 11

Constrained logistic regression

  • At d = 100, an increasing-batch TR-SSQP variant attains the lowest residual in each setting among four competing methods.At d = 50, batching consistently improves performance across Bk choices, with Hessian-based strategies achieving the lowest residuals under Gaussian design.Source: §4 · p. 12

5 Conclusion

The paper proposes TR-SSQP for nonlinear equality-constrained stochastic optimization under heavy-tailed noise, combining normal-tangential steps, gradient normalization, and Polyak momentum. It establishes global almost-sure first-order convergence under standard assumptions and reports promising empirical performance across TR-SSQP variants and competing methods.

5 Conclusion

  • TR-SSQP combines normal-tangential steps, gradient normalization, and Polyak momentum to control objective reduction, feasibility restoration, and heavy-tailed noise.Both fixed and growing batch-size regimes fit within one algorithmic and theoretical framework.Source: §5 · p. 12
  • Under standard assumptions, the method achieves global almost-sure first-order convergence.The paper reports numerical comparisons among TR-SSQP variants and competing constrained stochastic optimization methods.Source: §5 · p. 12
  • The framework reveals a quantitative trade-off between per-iteration sampling cost and the aggressiveness of trust-region and momentum updates.Source: §5 · p. 12

A Related work

Prior heavy-tailed stochastic SQP methods differ in their noise assumptions and convergence guarantees, while prior normalization work largely treats unconstrained settings. TR-SSQP extends normalization to constrained trust-region SQP and reports asymptotic convergence without requiring increasing batch sizes.

A Related work

  • Unlike the discussed heavy-tailed SSQP methods, TR-SSQP assumes bounded p-th moments, requires no objective-value estimates, and establishes limit-type almost-sure convergence.The compared methods use adaptive accuracy conditions, and the cited p-th-moment method provides only non-asymptotic liminf guarantees.Source: A Related work · p. 17
  • TR-SSQP extends normalization to constrained trust-region optimization, where the step direction and stepsize are determined jointly.The paper identifies this joint determination as requiring more delicate treatment of normalization.Source: A Related work · p. 17
  • The paper reports the first convergence analysis for constrained stochastic nonlinear optimization under heavy-tailed noise without increasing batch sizes, and the first asymptotic result exploring stepsize, momentum, and batch-size interplay even in the unconstrained setting.Source: A Related work · p. 17
  • Earlier trust-region SQP methods commonly controlled the normal-tangential radius split with a user-chosen parameter, which could make either step overly conservative; later work proposed adaptive parameter-free rules.This paper follows that line and extends prior work to heavy-tailed gradients with momentum updates.Source: A Related work · p. 18

B.1 Proof of Lemma 2.1

The proof develops Cauchy-point and normal-tangential step bounds, then uses them to establish a local model-reduction bound and a one-step recursion.

B.1 Proof of Lemma 2.1

  • The Cauchy-point argument invokes Nocedal and Wright’s formula to combine two cases.The supplied proof passage does not state the resulting bound.Source: §B.1 · p. 18

C.1 Proof of Lemma 3.3

  • The normal step reduces the constraint residual by γ_k∥c_k∥, while the tangential estimate uses fractional Cauchy decrease.The normal-step argument also bounds its decrease using the trust-region radius and constraint-residual bounds.Source: §C.1 · p. 19

C.2 Proof of Lemma 3.4

  • The local model reduction bound follows from the step’s constraint relation and the normal and tangential estimates.The proof then uses this bound with Taylor’s theorem to derive a one-step recursion.Source: §C.2 · pp. 19–20

C.3 Proof of Lemma 3.5

The proof bounds the momentum gradient-estimation error using a martingale-difference inequality, then establishes summability under the prescribed decay schedules.

Proof of Lemma 3.5

  • The momentum recursion expresses estimation error through its previous error, gradient change, and stochastic gradient noise.The proof first bounds the initial error using the mini-batch noise bound and the gradient bound.Source: §C.3 · pp. 20–21
  • Conditionally unbiased, independent samples within each batch form a martingale-difference sequence for bounding gradient noise.The proof applies the vector-valued martingale-difference inequality to these terms.Source: §C.3 · pp. 20–21

Proof of the summability statement

  • The proof establishes summability of the error-related terms under the stated decay conditions on the trust-region radius and momentum parameter.The argument separately bounds initial-error, drift, and noise contributions.Source: §C.3 · pp. 21–22

C.4 Proof of Theorem 3.6

The proof uses descent and residual estimates to establish almost-sure convergence of the optimality and feasibility measures. The appendix also presents additional experiments, organized by CUTEst and constrained logistic regression.

C.4 Proof of Theorem 3.6

  • Summing the one-step bound uses the merit function’s lower bound to control the accumulated decrease.The proof also uses the divergent sum of trust-region radii to obtain a liminf result for the Lagrangian-gradient norm.Source: §C.4 · p. 22
  • The proof establishes that the optimality residual converges to zero almost surely using a crossing argument and bounds on residual changes.The residual change is bounded in terms of the step length, while variation in the projector is controlled using Lipschitz continuity of the constraint Jacobian.Source: §C.4 · pp. 22–23
  • The proof shows that the constraint residual has finite radius-weighted sum and liminf zero almost surely, then applies a crossing argument.The constraint residual changes by at most a quantity proportional to the step length.Source: §C.4 · p. 23

D Additional Experimental Results

  • The appendix reports additional experiments, presenting CUTEst results before constrained logistic regression results.The passage describes the appendix’s organization but provides no experimental outcomes.Source: D Additional Experimental Results · p. 23

D.1.1 Detailed experimental setup

The experiments use equality-constrained CUTEst problems and simulate heavy-tailed gradient noise. They vary curvature approximations and batch sizes, then evaluate final KKT residuals and iteration-based performance profiles.

D.1.1 Detailed experimental setup

  • The setup evaluates 25 equality-constrained CUTEst problems with non-constant objectives, dimensions below 1000, and at least one constraint.The experiments run five trials for each configuration, totaling 8000 runs.Source: §D.1.1 · pp. 23–24
  • Gradient noise uses symmetric Pareto-type or centered Student-t distributions with p in {1.2, 1.4, 1.6, 1.8}, where smaller p means heavier tails.The perturbation magnitude varies with the gradient norm, and the setup states the resulting noise satisfies the bounded-moment condition for moment orders q in (1, p).Source: §D.1.1 · p. 24
  • Four B_k constructions are compared: identity, SR1, estimated Lagrangian Hessian, and averaged estimated Lagrangian Hessian.The averaged Hessian uses a 100-estimate window; two batch-size schedules are tested, with the increasing batch capped at 500.Source: §D.1.1 · p. 24
  • Performance profiles compare iteration counts to reach the KKT tolerance, normalized by each problem’s best stopping iteration across the four methods.The boxplots show final KKT residuals averaged over five runs for each problem.Source: §D.1.1 · p. 24

D.1.2 Additional results and discussion

Increasing batches improve TR-SSQP’s robustness on CUTEst under Pareto and Student-t noise, especially for heavier tails. Larger batches also make curvature-aware models more effective, while performance profiles show broader gains in iteration efficiency.

D.1.2 Additional results and discussion

  • Increasing batches consistently improve robustness under Pareto and Student-t noise, with residuals shifting lower and concentrating near target accuracy especially at p = 1.2 and p = 1.4.The boxplots compare the four B_k constructions across moment orders.Source: §D.1.2 · pp. 24–25, Figure 2 · p. 25
  • Online, the four B_k choices often perform similarly and identity remains a strong baseline; with batching, SR1 and Hessian-based variants become more effective, especially under heavier tails.Estimated and averaged Hessians frequently produce lower residuals and tighter boxes once larger mini-batches stabilize stochastic estimates.Source: §D.1.2 · p. 25, Figure 2 · p. 25
  • Increasing-batch profiles generally solve a larger fraction of problems within small performance ratios, while curvature-aware variants often strengthen profiles and online remains competitive in several cases.Profiles use average stopping iterations over five runs, treating failed runs as infinite stopping times to reflect speed and reliability.Source: §D.1.2 · p. 25

D.2.1 Detailed experimental setup

The synthetic constrained logistic-regression experiments vary dimension, covariate tails, curvature models, and batch size. They evaluate terminal KKT residuals and convergence trajectories under a shared linear equality constraint setup.

D.2.1 Detailed experimental setup

  • The synthetic logistic-regression problem uses a target vector x⋆ and generates binary labels from a logistic model conditional on covariates.The centered ridge parameter is Θ = 0.05, chosen so regularization does not move x⋆ from being a population-problem KKT point.Source: §D.2.1 · p. 26
  • Covariates use a Gaussian light-tailed baseline or symmetric Pareto and centered Student-t designs; for heavy-tailed designs, smaller p means heavier tails and moments of order q < p are finite.Feature scale is one and covariates are mean-zero.Source: §D.2.1 · p. 26
  • Linear deterministic constraints use c(x) = Ax − b with a full-row-rank Gaussian A and b = Ax⋆, making x⋆ feasible by construction.The same A is reused across distributions, tail parameters, curvature and batch variants, and repetitions for each dimension.Source: §D.2.1 · p. 26
  • For d ∈ {10, 30, 50}, the study compares identity, SR1, estimated-Hessian, and averaged-Hessian B_k choices; at d = 100 it also tests a diagonal truncated-Fisher model.The truncated-Fisher model uses the gradient samples without extra stochastic first-order oracle evaluations and costs O(N_kd), versus O(N_kd^2) to form a dense Hessian estimate.Source: §D.2.1 · p. 26
  • At d = 100, the competing-method comparison includes PAIS-SQP, Proj-ClipSGD, Lu-TPM, and MLALM, with five runs per method and covariate setting.Proj-ClipSGD is adapted to affine equality constraints by clipping the stochastic gradient, taking a gradient step, and projecting onto the feasible set.Source: §D.2.1 · pp. 26–27
  • Experiments compare an online regime with N_k = 1 against increasing batches capped at 500, using a more conservative a_1 ≈ 0.906 for p = 1.2.TR-SSQP uses specified trust-region and momentum schedules, a 10^4 iteration budget, and a 100-iteration burn-in that resets gradient and Hessian histories but not iterates or global schedules.Source: §D.2.1 · p. 27
  • Terminal-residual comparisons use five runs per setting and an independent 5,000-sample evaluation set for diagnostics and stopping; d = 10 convergence plots average 25 runs.The reported terminal KKT residual is averaged over five runs.Source: §D.2.1 · p. 27

D.2.2 Additional results and discussion

In constrained logistic regression, increasing batches generally reduce KKT residuals, and curvature-aware models benefit from larger mini-batches. At d = 100, an increasing-batch TR-SSQP variant attains the lowest residual in every tested setting.

D.2.2 Additional results and discussion

  • For the Gaussian design, batching improves KKT residuals for every B_k choice and each reported dimension, with Hessian-based choices best or nearly best especially at d = 30 and d = 50.The result holds in this light-tailed baseline as well as the heavy-tailed settings considered separately.Source: §D.2.2 · p. 27, Table 2 · p. 28
  • At d = 50, curvature-aware models attain the lowest residuals in most batched Pareto and Student-t settings; SR1 leads for Pareto p = 1.2 and p = 1.4, while estimated Hessians lead for p = 1.6 and p = 1.8.For Student-t covariates, averaged-Hessian and SR1 variants are also competitive under batching, especially at smaller p.Source: §D.2.2 · pp. 27–28, Table 2 · p. 28
  • An increasing-batch variant attains the smallest residual in six of nine settings at d = 10, eight at d = 30, and all nine at d = 50.The authors relate the more consistent batching benefit at larger dimensions to a larger tangent space with m = 5 equality constraints.Source: §D.2.2 · p. 28, Table 2 · p. 28
  • For d = 10, increasing-batch trajectories are more favorable in the Gaussian case, while under Pareto and Student-t covariates larger batches stabilize curvature-based steps despite substantial residual fluctuations.Figures 4 and 5 show KKT residual trajectories averaged over 25 independent runs.Source: §D.2.2 · p. 28, Figure 4 · p. 32, Figure 5 · p. 32
  • In all nine d = 100 settings, an Increasing-Batch TR-SSQP variant attains the smallest mean terminal KKT residual; TF-Batch beats all four existing methods in seven settings.Table 3 reports mean terminal KKT residuals over five runs with a 10^4 iteration budget.Source: §D.2.2 · p. 29, Table 3 · p. 30
  • At d = 100, TF-Online residuals are close to SR1 and Hessian variants in all nine settings; TF under increasing batches matches or closely approaches the best in seven, but is less effective at p = 1.4 for both heavy-tailed designs.The paper presents the TF model as a less expensive alternative to Hessian-based constructions with comparable terminal residuals in most tested settings.Source: §D.2.2 · p. 29, Table 3 · p. 30
Loading 2609.30732v1…