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

2025/09/25 by David M. Janz, Akhavan, Arya, Janz, David +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2509.21484

openalex publication_date 2025/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization
• Bandit Convex Optimisation
• Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance
• Time-Uniform Self-Normalized Concentration for Vector-Valued Processes
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Scale-Free Online Learning
• Optimal rates for zero-order convex optimization: the power of two\n function evaluations
• On the Complexity of Bandit and Derivative-Free Stochastic Convex\n Optimization
• A probabilistic approach to the geometry of the ℓpn-ball
• Online convex optimization in the bandit setting: gradient descent without a gradient
• On the volume of the intersection of two L_pⁿ balls
• Stochastic Estimation of the Maximum of a Regression Function

Related

• Federated Online and Bandit Convex Optimization
• Second-Order Guarantees in Federated Learning
• FedZeN: Towards superlinear zeroth-order federated learning via incremental Hessian estimation
• Zeroth-Order Federated Methods for Stochastic MPECs and Nondifferentiable Nonconvex Hierarchical Optimization
• Converge Faster, Talk Less: Hessian-Informed Federated Zeroth-Order Optimization