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

arXiv:2509.21484v3 Announce Type: replace Abstract: We study online convex optimisation with ell_q-Lipschitz losses, ell_p-regularised FTRL, and randomised two-point finite-difference gradient estimators based on cone-measure sampling from ell_r-spheres. For random Lipschitz losses whose mean is convex, we prove unified high-probability regret bounds for all p,q,r in [1,infty]. 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 qin[1,2] under appropriate sampling geometry, and expose a gap for q>2 that appears intrinsic to the estimators themselves.

Source: arXiv cs.LG | 2026-05-12