Improved Complexity of Trust-region Optimization for Zeroth-order Stochastic Oracles with Adaptive Sampling

Abstract

We present an enhanced stochastic trust-region optimization with adaptive sampling (ASTRO-DF) in which optimizing an iteratively constructed local model on estimates of objective values with stochastic sample size guides the search. The noticeable feature is that the underdetermined quadratic model with a diagonal Hessian requires fewer function evaluations, which is particularly useful at high dimensions. This paper describes the enhanced algorithm in detail. It gives several theoretical results, including iteration complexity, and renders almost sure convergence guarantees. We report in our numerical experience the finite-time superiority of the enhanced ASTRO-DF over state-of-the-art using the SimOpt library.

Yunsoo Ha

Postdoctoral Researcher

My research interests include stochastic optimization, monte carlo simulation, quantum computing, and decision-focused learning.