  Motivated by multiple emerging applications in machine learning, we consider
an optimization problem in a general form where the gradient of the objective
function is available through a biased stochastic oracle. We assume a
bias-control parameter can reduce the bias magnitude, however, a lower bias
requires more computation/samples. For instance, for two applications on
stochastic composition optimization and policy optimization for
infinite-horizon Markov decision processes, we show that the bias follows a
power law and exponential decay, respectively, as functions of their
corresponding bias control parameters. For problems with such gradient oracles,
the paper proposes stochastic algorithms that adjust the bias-control parameter
throughout the iterations. We analyze the nonasymptotic performance of the
proposed algorithms in the nonconvex regime and establish their sample or
bias-control computation complexities to obtain a stationary point. Finally, we
numerically evaluate the performance of the proposed algorithms over three
applications.
