  Adaptive sampling with interpolation-based trust regions or ASTRO-DF is a
successful algorithm for stochastic derivative-free optimization with an
easy-to-understand-and-implement concept that guarantees almost sure
convergence to a first-order critical point. To reduce its dependence on the
problem dimension, we present local models with diagonal Hessians constructed
on interpolation points based on a coordinate basis. We also leverage the
interpolation points in a direct search manner whenever possible to boost
ASTRO-DF's performance in a finite time. We prove that the algorithm 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.
Numerical experimentation reveals the computational advantage of ASTRO-DF with
coordinate direct search due to saving and better steps in the early iterations
of the search.

Optimization and Control;Probability