# Non-asymptotic bounds for stochastic optimization with biased noisy gradient oracles

arXiv: https://arxiv.org/abs/2002.11440 · HTML: https://mlsanity.com/paper/2002.11440/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2020.

## Built on by (most cited first, 6 of 6)

- [Online Estimation and Optimization of Utility-Based Shortfall Risk](https://mlsanity.com/paper/2111.08805/) (2021)
- [Optimization of utility-based shortfall risk: A non-asymptotic viewpoint](https://mlsanity.com/paper/2310.18743/) (2023)
- [A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization](https://mlsanity.com/paper/2208.00290/) (2022)
- [A Stochastic Gradient Descent Approach to Design Policy Gradient Methods for LQR](https://mlsanity.com/paper/2602.18933/) (2026)
- [Adversary-Robust Learning from Fully Asynchronous Directional Derivative Estimates](https://mlsanity.com/paper/2605.09337/) (2026)
- [On the Oracle Complexity of Interpolation-Based Gradient Descent](https://mlsanity.com/paper/2606.19878/) (2026)

## Abstract (arXiv)

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.