2025 journal article

Iteration complexity and finite-time efficiency of adaptive sampling trust-region methods for stochastic derivative-free optimization

Ha, Y., & Shashaani, S. (2024, April 3). IISE TRANSACTIONS, Vol. 4.

By: Y. Ha  n & S. Shashaani n 

topics (OpenAlex): Stochastic Gradient Optimization Techniques; Markov Chains and Monte Carlo Methods; Sparse and Compressive Sensing Techniques
TL;DR: It is proved that the adaptive sampling with interpolation-based trust regions or ASTRO-DF has a canonical iteration complexity of $\mathcal{O}(\epsilon^{-2})$ almost surely, which is the first guarantee of its kind without placing assumptions on the quality of function estimates or model quality or independence between them. (via Semantic Scholar)
Source: ORCID
Added: April 1, 2024

ASTRO-DF is a prominent trust-region method using adaptive sampling for stochastic derivative-free optimization of nonconvex problems. Its salient feature is an easy-to-understand-and-implement concept of maintaining "just enough" replications when evaluating points throughout the search to guarantee almost-sure convergence to a first-order critical point. To reduce the dependence of ASTRO-DF on the problem dimension and boost its performance in finite time, we present two key refinements, namely, (i) local models with diagonal Hessians constructed on interpolation points based on a coordinate basis and (ii) direct search using the interpolation points whenever possible. We demonstrate that the refinements in (i) and (ii) retain the convergence guarantees while matching existing results on iteration complexity. Uniquely, our iteration complexity results match the canonical rates without placing assumptions on iterative models' quality and their independence from function estimates. Numerical experimentation on a testbed of problems and comparison against existing popular algorithms reveals the computational advantage of ASTRO-DF due to the proposed refinements.