  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.
