{"ID":2866146,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.21484","arxiv_id":"2509.21484","title":"High-probability zeroth-order online convex optimisation beyond Euclidean geometry","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 $q\\in[1,2]$ under appropriate sampling geometry, and expose a gap for $q\u003e2$ that appears intrinsic to the estimators themselves.","short_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...","url_abs":"https://arxiv.org/abs/2509.21484","url_pdf":"https://arxiv.org/pdf/2509.21484v3","authors":"[\"David Janz\",\"El-Mahdi El-Mhamdi\",\"Arya Akhavan\"]","published":"2025-09-25T19:44:57Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}