# Stochastic Optimization with Random Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 41 references that are in the map.
- First posted on arXiv 17 Oct 2025.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020](https://mlsanity.com/paper/2104.10201/) (2021)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems](https://mlsanity.com/paper/1812.08305/) (2018)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [Autotune: A Derivative-free Optimization Framework for Hyperparameter Tuning](https://mlsanity.com/paper/1804.07824/) (2018)
- [Optimization with Access to Auxiliary Information](https://mlsanity.com/paper/2206.00395/) (2022)
- [Reducing the variance in online optimization by transporting past gradients](https://mlsanity.com/paper/1906.03532/) (2019)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [A Stochastic Derivative-Free Optimization Method with Importance Sampling: Theory and Learning to Control](https://mlsanity.com/paper/1902.01272/) (2019)
- [A Stochastic Derivative Free Optimization Method with Momentum](https://mlsanity.com/paper/1905.13278/) (2019)
- [An Empirical Study of Derivative-Free-Optimization Algorithms for Targeted Black-Box Attacks in Deep Neural Networks](https://mlsanity.com/paper/2012.01901/) (2020)
- [Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/2209.07883/) (2022)
- [Simple Complexity Analysis of Simplified Direct Search](https://mlsanity.com/paper/1410.0390/) (2014)
- [On the Almost Sure Convergence of the Stochastic Three Points Algorithm](https://mlsanity.com/paper/2501.13886/) (2025)

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

- [Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking](https://mlsanity.com/paper/2610.13871/) (2026)

## Abstract (arXiv)

We revisit random search for stochastic optimization, where only noisy function evaluations are available. We show that the method works under weaker smoothness assumptions than previously considered, and that stronger assumptions enable improved guarantees. In the finite-sum setting, we design a variance-reduced variant that leverages multiple samples to accelerate convergence. Our analysis relies on a simple translation invariance property, which provides a principled way to balance noise and reduce variance.