# Randomized Derivative-Free Optimization of Noisy Convex Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2015.

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

- [Generalizing Gaussian Smoothing for Random Search](https://mlsanity.com/paper/2211.14721/) (2022)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [A Structured Tour of Optimization with Finite Differences](https://mlsanity.com/paper/2505.19720/) (2025)

## Abstract (arXiv)

We propose STARS, a randomized derivative-free algorithm for unconstrained optimization when the function evaluations are contaminated with random noise. STARS takes dynamic, noise-adjusted smoothing step-sizes that minimize the least-squares error between the true directional derivative of a noisy function and its finite difference approximation. We provide a convergence rate analysis of STARS for solving convex problems with additive or multiplicative noise. Experimental results show that (1) STARS exhibits noise-invariant behavior with respect to different levels of stochastic noise; (2) the practical performance of STARS in terms of solution accuracy and convergence rate is significantly better than that indicated by the theoretical result; and (3) STARS outperforms a selection of randomized zero-order methods on both additive and multiplicative-noisy functions.