Non-asymptotic bounds for stochastic optimization with biased noisy gradient oracles
This work addresses optimization problems in risk-sensitive reinforcement learning and simulation, but it is incremental as it extends existing algorithms to biased oracles.
The paper tackles stochastic optimization with biased gradient oracles, where estimation error is controlled by batch size, and derives non-asymptotic bounds for convergence rates in both non-convex and convex settings.
We introduce biased gradient oracles to capture a setting where the function measurements have an estimation error that can be controlled through a batch size parameter. Our proposed oracles are appealing in several practical contexts, for instance, risk measure estimation from a batch of independent and identically distributed (i.i.d.) samples, or simulation optimization, where the function measurements are `biased' due to computational constraints. In either case, increasing the batch size reduces the estimation error. We highlight the applicability of our biased gradient oracles in a risk-sensitive reinforcement learning setting. In the stochastic non-convex optimization context, we analyze a variant of the randomized stochastic gradient (RSG) algorithm with a biased gradient oracle. We quantify the convergence rate of this algorithm by deriving non-asymptotic bounds on its performance. Next, in the stochastic convex optimization setting, we derive non-asymptotic bounds for the last iterate of a stochastic gradient descent (SGD) algorithm with a biased gradient oracle.