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

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.