Trust-region methods have proven highly effective for unconstrained nonconvex stochastic optimization problems where objective and gradient information are available only through noisy stochastic oracles. ASTRO is a class of adaptive sampling trust-region methods that dynamically determine sampling effort while constructing local quadratic models from noisy function and gradient observations. By exploiting dependence among samples and the stochastic structure of the problem, ASTRO achieves strong convergence and complexity guarantees. Its derivative-free variant, ASTRO-DF, relies solely on noisy function evaluations and also enjoys almost-sure convergence guarantees.

In this work, we develop a new adaptive regularization framework for ASTRO and ASTRO-DF that improves both iteration and sample complexity. The proposed methods incorporate enhanced adaptive sampling rules and refined success criteria, enabling more efficient progress with fewer oracle evaluations while preserving almost-sure convergence to stationarity. We further analyze the benefits and trade-offs of quadratic regularization and establish improved sample complexity guarantees under common random numbers, assuming stronger conditions on model Hessians. Numerical experiments on synthetic benchmarks and simulation-based optimization problems under various noise regimes demonstrate substantial gains in sample efficiency relative to existing approaches.

Personal website of Sara Shashaani