  We consider a step search method for continuous optimization under a
stochastic setting where the function values and gradients are available only
through inexact probabilistic zeroth- and first-order oracles. Unlike the
stochastic gradient method and its many variants, the algorithm does not use a
pre-specified sequence of step sizes but increases or decreases the step size
adaptively according to the estimated progress of the algorithm. These oracles
capture multiple standard settings including expected loss minimization and
zeroth-order optimization. Moreover, our framework is very general and allows
the function and gradient estimates to be biased. The proposed algorithm is
simple to describe and easy to implement. Under fairly general conditions on
the oracles, we derive a high probability tail bound on the iteration
complexity of the algorithm when it is applied to non-convex, convex, and
strongly convex (more generally, those satisfying the PL condition) functions.
Our analysis strengthens and extends prior results for stochastic step and line
search methods.
