Stochastic Optimization Algorithms for Problems with Controllable Biased Oracles

Understand

Motivated by 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, in 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.