# ASTRO-DF: A Class of Adaptive Sampling Trust-Region Algorithms for Derivative-Free Stochastic Optimization

arXiv: https://arxiv.org/abs/1610.06506 · HTML: https://mlsanity.com/paper/1610.06506/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2016.

## Built on by (most cited first, 7 of 7)

- [Enhancing Efficiency of Safe Reinforcement Learning via Sample Manipulation](https://mlsanity.com/paper/2405.20860/) (2024)
- [Smoothing Methods for Automatic Differentiation Across Conditional Branches](https://mlsanity.com/paper/2310.03585/) (2023)
- [Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization](https://mlsanity.com/paper/2109.12213/) (2021)
- [Enhanced Derivative-Free Optimization Using Adaptive Correlation-Induced Finite Difference Estimators](https://mlsanity.com/paper/2502.20819/) (2025)
- [Adaptive Replication Strategies in Trust-Region-Based Bayesian Optimization of Stochastic Functions](https://mlsanity.com/paper/2504.20527/) (2025)
- [Dimensional Peeking for Low-Variance Gradients in Zeroth-Order Discrete Optimization via Simulation](https://mlsanity.com/paper/2602.00075/) (2026)
- [Why and When Neural Networks Improve Local Approximation in Optimization](https://mlsanity.com/paper/2608.24963/) (2026)

## Abstract (arXiv)

We consider unconstrained optimization problems where only "stochastic" estimates of the objective function are observable as replicates from a Monte Carlo oracle. The Monte Carlo oracle is assumed to provide no direct observations of the function gradient. We present ASTRO-DF --- a class of derivative-free trust-region algorithms, where a stochastic local interpolation model is constructed, optimized, and updated iteratively. Function estimation and model construction within ASTRO-DF is adaptive in the sense that the extent of Monte Carlo sampling is determined by continuously monitoring and balancing metrics of sampling error (or variance) and structural error (or model bias) within ASTRO-DF. Such balancing of errors is designed to ensure that Monte Carlo effort within ASTRO-DF is sensitive to algorithm trajectory, sampling more whenever an iterate is inferred to be close to a critical point and less when far away. We demonstrate the almost-sure convergence of ASTRO-DF's iterates to a first-order critical point when using linear or quadratic stochastic interpolation models. The question of using more complicated models, e.g., regression or stochastic kriging, in combination with adaptive sampling is worth further investigation and will benefit from the methods of proof presented here. We speculate that ASTRO-DF's iterates achieve the canonical Monte Carlo convergence rate, although a proof remains elusive.