math.OCApr 15, 2026

Stochastic Trust-Region Methods for Over-parameterized Models

Authors: Aike Yang, Hao Wang

Organizations: ShanghaiTech University, Shanghai, China

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Under interpolation-type assumptions such as the strong growth condition, stochastic optimization methods can attain convergence rates comparable to full-batch methods, but their performance, particularly for SGD, remains highly sensitive to step-size selection. To address this issue, we propose a unified stochastic trust-region framework that eliminates manual step-size tuning and extends naturally to equality-constrained problems. For unconstrained optimization, we develop a first-order stochastic trust-region algorithm and show that, under the strong growth condition, it achieves an iteration and stochastic first-order oracle complexity of O(ε−2log⁡(1/ε))O(\varepsilon^{-2} \log(1/\varepsilon)) for finding an ε\varepsilon-stationary point. For equality-constrained problems, we introduce a quadratic-penalty-based stochastic trust-region method with penalty parameter μμ, and establish an iteration and oracle complexity of O(ε−4log⁡(1/ε))O(\varepsilon^{-4} \log(1/\varepsilon)) to reach an ε\varepsilon-stationary point of the penalized problem, corresponding to an O(ε)O(\varepsilon)-approximate KKT point of the original constrained problem. Numerical experiments on deep neural network training and orthogonally constrained subspace fitting demonstrate that the proposed methods achieve performance comparable to well-tuned stochastic baselines, while exhibiting stable optimization behavior and effectively handling hard constraints without manual learning-rate scheduling.

Figures & tables

 pk=arg⁡min⁡∥p∥≤Δk  mk(p).p_{k}=\arg\min_{\|p\|\leq\Delta_{k}}\;m_{k}(p). 
Algorithm 1 First-Order Stochastic Trust-Region Method
 pk=arg⁡min⁡∥p∥≤Δkmkϕ(p).p_{k}=\arg\min_{\|p\|\leq\Delta_{k}}m_{k}^{\phi}(p). 
Algorithm 2 Stochastic Trust-Region Method with Quadratic Penalty
Figure 1: Comparison of training loss and test accuracy for SGD, Adam, SLS, and STR on CIFAR-10.
Figure 2: Constrained orthogonal subspace fitting on synthetic spiked model data ( d=100d=100 , k=5k=5 , n=500n=500 ). Comparison of STR-P with projected SGD, Riemannian gradient descent, and stochastic augmented Lagrangian.
Figure 3: Constrained orthogonal subspace fitting on synthetic spiked model data ( d=500d=500 , k=10k=10 , n=1000n=1000 ). Comparison of STR-P with projected SGD, Riemannian gradient descent, and stochastic augmented Lagrangian.
More in this topic

Trust-Region Optimization

Trust-region optimization limits each update to a region where a local model is trusted, improving stability in difficult search problems.

See all 28 papers

Explore similar work

CardsList
Sep 25, 2026

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

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.

Haoxuan Wang, Yuchen Fang, Sen Na

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

Stochastic OptimizationStochastic Optimization ConvergenceHeavy-Tailed Stochastic OptimizationTrust-Region Optimization
AskPDF
Mar 10, 2026

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

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.

Yuchen Fang, Jihun Kim, Sen Na +2

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

Constrained OptimizationStochastic OptimizationStochastic Optimization ConvergenceTrust-Region Optimization
AskPDF
May 18, 2026

Stochastic Penalty-Barrier Method for Constrained Machine Learning

Constrained Machine Learning (CML) enables fairness-aware training, physics-informed neural networks, and integration of symbolic domain knowledge into statistical models. In this work, we introduce the Stochastic Penalty-Barrier Method (SPBM) for CML problems. SPBM extends classical penalty and barrier methods by incorporating an exponential averaging of the dual variables, a stabilized penalty schedule, and the Moreau envelope to handle non-smoothness. We analyze the bias that mini-batching introduces in the barrier function and show that the feasible set of the resulting transformed problem is contained within the original one. We compare SPBM with CML baselines across multiple fairness and physics informed neural networks experiments. We find that SPBM is competitive with state-of-the-art methods. We also observe, on our fairness-based computational benchmark, that the per-epoch runtime of CML methods is largely independent of the number of constraints, and within 1.3×1.3\times of the per-epoch runtime of regularized Adam, for a number of constraints ranging from 9090 to 99009900.

Adam Bosák, Andrii Kliachkin, Gilles Bareilles +4

Artificial Intelligence Center, CTU in Prague · CMAP, École Polytechnique, Palaiseau, France

Constrained Optimization
AskPDF