# A gradient estimator via L1-randomization for online zero-order optimization with two point feedback

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 47 references that are in the map.
- First posted on arXiv 27 May 2022.

## Builds on (most cited first, 11 of 11)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Highly-Smooth Zero-th Order Online Optimization Vianney Perchet](https://mlsanity.com/paper/1605.08165/) (2016)
- [Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits](https://mlsanity.com/paper/2006.07862/) (2020)
- [Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions](https://mlsanity.com/paper/1501.07242/) (2015)
- [Distributed Zero-Order Optimization under Adversarial Noise](https://mlsanity.com/paper/2102.01121/) (2021)
- [Improved Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandit](https://mlsanity.com/paper/2101.03821/) (2021)

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

- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Accelerated zero-order SGD under high-order smoothness and overparameterized regime](https://mlsanity.com/paper/2411.13999/) (2024)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)
- [A simple and improved algorithm for noisy, convex, zeroth-order optimisation](https://mlsanity.com/paper/2406.18672/) (2024)
- [How to Boost Any Loss Function](https://mlsanity.com/paper/2407.02279/) (2024)
- [High-probability zeroth-order online convex optimisation beyond Euclidean geometry](https://mlsanity.com/paper/2509.21484/) (2025)

## Abstract (arXiv)

This work studies online zero-order optimization of convex and Lipschitz functions. We present a novel gradient estimator based on two function evaluations and randomization on the ℓ1-sphere. Considering different geometries of feasible sets and Lipschitz assumptions we analyse online dual averaging algorithm with our estimator in place of the usual gradient. We consider two types of assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise. We provide an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem. In the case of canceling noise that was previously studied in the literature, our guarantees are either comparable or better than state-of-the-art bounds obtained by Duchi et al. (2015) and Shamir (2017) for non-adaptive algorithms. Our analysis is based on deriving a new weighted Poincar'e type inequality for the uniform measure on the ℓ1-sphere with explicit constants, which may be of independent interest.