Stochastic Optimization with Random Search
Not on the map. Why?
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.
Key facts. Cited by 1 paper 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
21 of 41 references.
References · 21
- 2022Training language models to follow instructions with human feedbackcited by 15,971
- 2017Deep reinforcement learning from human preferencescited by 3,912
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
- 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
- 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
- 2021Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020cited by 148
- 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
- 2018Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systemscited by 67
- 2019Gradientless Descent: High-Dimensional Zeroth-Order Optimizationcited by 43
- 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
- 2018Autotune: A Derivative-free Optimization Framework for Hyperparameter Tuningcited by 20
9 more
- 2022Optimization with Access to Auxiliary Informationcited by 13
- 2019Reducing the variance in online optimization by transporting past gradientscited by 12
- 2023Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methodscited by 12
- 2019A Stochastic Derivative-Free Optimization Method with Importance Sampling: Theory and Learning to Controlcited by 9
- 2019A Stochastic Derivative Free Optimization Method with Momentumcited by 9
- 2020An Empirical Study of Derivative-Free-Optimization Algorithms for Targeted Black-Box Attacks in Deep Neural Networkscited by 8
- 2022Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 6
- 2014Simple Complexity Analysis of Simplified Direct Searchcited by 4
- 2025On the Almost Sure Convergence of the Stochastic Three Points Algorithmcited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.