Unifying Trust-region Algorithms with Adaptive Sampling for Nonconvex Simulation Optimization

Abstract

Continuous simulation optimization is challenging due to its derivative-free and often nonconvex noisy setting. Trust-region methods have proven remarkable robustness for this class of problems. Each iteration of a trust-region method involves constructing a local model via interpolation or regression within a neighborhood of the current best solution that helps verify sufficient reduction in the function estimate when determining the next iterate. When the local model approximates the function well, larger neighborhoods are advantageous for faster progress. Conversely, unsuccessful approximations can be corrected by contracting the neighborhood. Traditional trust-region methods can be slowed down by incremental contractions that lead to numerous unnecessary iterations and significant simulation cost towards convergence to a stationary point. We propose a unified regime for adaptive sampling trust-region optimization (ASTRO) that can enjoy faster convergence in both iteration count and sampling effort by employing quadratic regularization and dynamically adjusting the trust-region size based on gradient estimates. This unification with other regularization frameworks enables almost sure $\mathcal{O}(\epsilon^{-1.5})$ iteration complexity and $\tilde{\mathcal{O}}(\epsilon^{-4.5})$ sample complexity compared with the state-of-the-art $\mathcal{O}(\epsilon^{-2})$ and $\tilde{\mathcal{O}}(\epsilon^{-6})$, respectively.