# (Bandit) Convex Optimization with Biased Noisy Gradient Oracles

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2016.

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

- [Generalizing Gaussian Smoothing for Random Search](https://mlsanity.com/paper/2211.14721/) (2022)
- [A Second-Order Method for Stochastic Bandit Convex Optimisation](https://mlsanity.com/paper/2302.05371/) (2023)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [Minimax Regret for Bandit Convex Optimisation of Ridge Functions](https://mlsanity.com/paper/2106.00444/) (2021)
- [Domain Generalization without Excess Empirical Risk](https://mlsanity.com/paper/2308.15856/) (2023)
- [Adaptive Bandit Convex Optimization with Heterogeneous Curvature](https://mlsanity.com/paper/2202.06150/) (2022)
- [A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization](https://mlsanity.com/paper/2208.00290/) (2022)
- [Bandit Convex Optimization with Gradient Prediction Adaptivity](https://mlsanity.com/paper/2605.22191/) (2026)
- [CONGO: Compressive Online Gradient Optimization](https://mlsanity.com/paper/2407.06325/) (2024)
- [Online Episodic Convex Reinforcement Learning](https://mlsanity.com/paper/2505.07303/) (2025)
- [Descend or Rewind? Stochastic Gradient Descent Unlearning](https://mlsanity.com/paper/2511.15983/) (2025)
- [Nonparametric Learning and Earning with One-Point Feedback under Nonstationarity](https://mlsanity.com/paper/2605.21263/) (2026)

## Abstract (arXiv)

Algorithms for bandit convex optimization and online learning often rely on constructing noisy gradient estimates, which are then used in appropriately adjusted first-order algorithms, replacing actual gradients. Depending on the properties of the function to be optimized and the nature of ``noise'' in the bandit feedback, the bias and variance of gradient estimates exhibit various tradeoffs. In this paper we propose a novel framework that replaces the specific gradient estimation methods with an abstract oracle. With the help of the new framework we unify previous works, reproducing their results in a clean and concise fashion, while, perhaps more importantly, the framework also allows us to formally show that to achieve the optimal root-n rate either the algorithms that use existing gradient estimators, or the proof techniques used to analyze them have to go beyond what exists today.