Adaptive Regularization within Trust Region Methods for Stochastic Nonconvex Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918473815293952 |
|---|---|
| author | Ha, Yunsoo Shashaani, Sara Tran-dinh, Quoc |
| author_facet | Ha, Yunsoo Shashaani, Sara Tran-dinh, Quoc |
| contents | We propose a stochastic nonconvex optimization algorithm that achieves almost sure $\tilde{\mathcal{O}}(ε^{-1.5})$ iteration complexity for problems with smooth objective functions and gradients only observable with noise. The mean-zero stochastic noise is decision-dependent and has unbounded support with subexponential tail, allowing our framework to cover a broad class of problems. The improved almost sure iteration complexity is achieved with a new variant of the adaptive sampling trust-region optimization (ASTRO) augmented with an adaptively regularized local model, which we term Reg-ASTRO. Adaptive sampling ensures that the estimation precision is aligned with a measure of stationarity, so that iterates closer to stationarity trigger higher accuracy requirement for sampling. A key analytical challenge arises because the trust-region radius and regularization are coupled and not determined prior to gradient estimation at each iteration. We further establish an almost sure $\tilde{\mathcal{O}}(ε^{-4.5})$ sample complexity for Reg-ASTRO, which improves to $\tilde{\mathcal{O}}(ε^{-3.5})$ under stronger regularity conditions and use of common random numbers, substantially outperforming first-order methods in theory and numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15457 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Adaptive Regularization within Trust Region Methods for Stochastic Nonconvex Optimization Ha, Yunsoo Shashaani, Sara Tran-dinh, Quoc Optimization and Control We propose a stochastic nonconvex optimization algorithm that achieves almost sure $\tilde{\mathcal{O}}(ε^{-1.5})$ iteration complexity for problems with smooth objective functions and gradients only observable with noise. The mean-zero stochastic noise is decision-dependent and has unbounded support with subexponential tail, allowing our framework to cover a broad class of problems. The improved almost sure iteration complexity is achieved with a new variant of the adaptive sampling trust-region optimization (ASTRO) augmented with an adaptively regularized local model, which we term Reg-ASTRO. Adaptive sampling ensures that the estimation precision is aligned with a measure of stationarity, so that iterates closer to stationarity trigger higher accuracy requirement for sampling. A key analytical challenge arises because the trust-region radius and regularization are coupled and not determined prior to gradient estimation at each iteration. We further establish an almost sure $\tilde{\mathcal{O}}(ε^{-4.5})$ sample complexity for Reg-ASTRO, which improves to $\tilde{\mathcal{O}}(ε^{-3.5})$ under stronger regularity conditions and use of common random numbers, substantially outperforming first-order methods in theory and numerical experiments. |
| title | Adaptive Regularization within Trust Region Methods for Stochastic Nonconvex Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.15457 |