# Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 67 references that are in the map.
- First posted on arXiv 24 Sep 2021.

## Builds on (most cited first, 26 of 26)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [A Progressive Batching L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1802.05374/) (2018)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points](https://mlsanity.com/paper/1809.06474/) (2018)
- [A Multi-Batch L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1605.06049/) (2016)
- [Adaptive Sampling Strategies for Stochastic Optimization](https://mlsanity.com/paper/1710.11258/) (2017)
- [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models](https://mlsanity.com/paper/1505.06070/) (2015)
- [Stochastic Optimization Using a Trust-Region Method and Random Models](https://mlsanity.com/paper/1504.04231/) (2015)
- [Towards Gradient Free and Projection Free Stochastic Optimization](https://mlsanity.com/paper/1810.03233/) (2018)
- [Accelerated Stochastic Gradient-free and Projection-free Methods](https://mlsanity.com/paper/2007.12625/) (2020)
- [ASTRO-DF: A Class of Adaptive Sampling Trust-Region Algorithms for Derivative-Free Stochastic Optimization](https://mlsanity.com/paper/1610.06506/) (2016)
- [A Robust Multi-Batch L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1707.08552/) (2017)
- [Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods](https://mlsanity.com/paper/1803.10173/) (2018)
- [Conditional gradient type methods for composite nonlinear and stochastic optimization](https://mlsanity.com/paper/1602.00961/) (2016)
- [Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1902.06158/) (2019)
- [Derivative-free optimization methods](https://mlsanity.com/paper/1904.11585/) (2019)
- [Analysis of the BFGS Method with Errors](https://mlsanity.com/paper/1901.09063/) (2019)
- [Adaptive learning rates and parallelization for stochastic, sparse, non-smooth gradients](https://mlsanity.com/paper/1301.3764/) (2013)

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

- [AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methods](https://mlsanity.com/paper/2402.11215/) (2024)
- [Adaptive Batch Size Schedules for Distributed Training of Language Models with Data and Model Parallelism](https://mlsanity.com/paper/2412.21124/) (2024)
- [A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning](https://mlsanity.com/paper/2409.15955/) (2024)
- [ZoAQ: Adaptive Zeroth-Order Querying via Query-Reuse Coupling](https://mlsanity.com/paper/2609.22115/) (2026)

## Abstract (arXiv)

We consider unconstrained stochastic optimization problems with no available gradient information. Such problems arise in settings from derivative-free simulation optimization to reinforcement learning. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a stochastic function using finite differences within a common random number framework. We develop modified versions of a norm test and an inner product quasi-Newton test to control the sample sizes used in the stochastic approximations and provide global convergence results to the neighborhood of the optimal solution. We present numerical experiments on simulation optimization problems to illustrate the performance of the proposed algorithm. When compared with classical zeroth-order stochastic gradient methods, we observe that our strategies of adapting the sample sizes significantly improve performance in terms of the number of stochastic function evaluations required.