# High-probability zeroth-order online convex optimisation beyond Euclidean geometry

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 25 Sep 2025.

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

- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Bandit Convex Optimisation](https://mlsanity.com/paper/2402.06535/) (2024)
- [Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits](https://mlsanity.com/paper/2006.07862/) (2020)
- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance](https://mlsanity.com/paper/2310.18763/) (2023)
- [Time-Uniform Self-Normalized Concentration for Vector-Valued Processes](https://mlsanity.com/paper/2310.09100/) (2023)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)

## Abstract (arXiv)

We study online convex optimisation with ℓq-Lipschitz losses, ℓp-regularised FTRL, and randomised two-point finite-difference gradient estimators based on cone-measure sampling from ℓr-spheres. For random Lipschitz losses whose mean is convex, we prove unified high-probability regret bounds for all p,q,r ∈ [1,∞]. The analysis is driven by all-moment bounds for the gradient estimator in the dual FTRL norm, yielding time-uniform control of the quadratic variation. The algorithm is anytime and data-driven; in the special cases previously studied, its rates recover the known in-expectation guarantees while strengthening them to time-uniform high probability. Together with constant-probability lower bounds, these results establish optimality for q∈[1,2] under appropriate sampling geometry, and expose a gap for q>2 that appears intrinsic to the estimators themselves.