# Stochastic Trust-Region Methods for Over-parameterized Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 40 references that are in the map.
- First posted on arXiv 15 Apr 2026.

## Builds on (most cited first, 26 of 26)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013)
- [SGD Converges to Global Minimum in Deep Learning via Star-convex Path](https://mlsanity.com/paper/1901.00451/) (2019)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models](https://mlsanity.com/paper/1505.06070/) (2015)
- [Stochastic Optimization Using a Trust-Region Method and Random Models](https://mlsanity.com/paper/1504.04231/) (2015)
- [A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians](https://mlsanity.com/paper/2106.13015/) (2021)
- [Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities](https://mlsanity.com/paper/2001.07819/) (2020)
- [Subspace Fitting Meets Regression: The Effects of Supervision and Orthonormality Constraints on Double Descent of Generalization Errors](https://mlsanity.com/paper/2002.10614/) (2020)
- [First-order methods for constrained convex programming based on linearized augmented Lagrangian function](https://mlsanity.com/paper/1711.08020/) (2017)
- [A Fully Stochastic Second-Order Trust Region Method](https://mlsanity.com/paper/1911.06920/) (2019)
- [Trust Region Methods For Nonconvex Stochastic Optimization Beyond Lipschitz Smoothness](https://mlsanity.com/paper/2310.17319/) (2023)
- [A Stochastic Trust Region Method for Non-convex Minimization](https://mlsanity.com/paper/1903.01540/) (2019)
- [Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models](https://mlsanity.com/paper/1904.03342/) (2019)
- [Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses](https://mlsanity.com/paper/2207.06452/) (2022)
- [Complexity of Zeroth- and First-order Stochastic Trust-Region Algorithms](https://mlsanity.com/paper/2405.20116/) (2024)
- [Trust-Region Stochastic Optimization with Variance Reduction Technique](https://mlsanity.com/paper/2412.00673/) (2024)

## Abstract (arXiv)

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(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(varepsilon-4 log(1/varepsilon)) to reach an varepsilon-stationary point of the penalized problem, corresponding to an 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.