📊 statistics

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

This paper establishes unified high-probability regret bounds for zeroth-order online convex optimization with $\ell_q$ -Lipschitz losses and $\ell_p$ -regularized FTRL using cone-measure sampling, proving optimality for $q \in [1,2]$ while identifying an intrinsic gap for $q > 2$ .

Original authors: David Janz, El-Mahdi El-Mhamdi, Arya Akhavan

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Janz, El-Mahdi El-Mhamdi, Arya Akhavan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley (the "minimum" of a function). In a perfect world, you would have a map or a compass that tells you exactly which way is "down" (a gradient). But in this paper, the authors are dealing with a situation where you have no map and no compass. You can only take a step, feel the ground, and ask, "Is it higher or lower here?" This is called zeroth-order optimization.

The paper tackles a specific, tricky version of this problem: Online Convex Optimization.

"Online" means you are making decisions one by one, like playing a game where you don't know the next move in advance.
"Convex" means the valley has a nice, smooth bowl shape (no hidden hills or weird bumps), which makes finding the bottom theoretically possible.
"Zeroth-order" means you only get to taste the ground at two specific spots to guess the slope, rather than seeing the whole hill.

Here is the breakdown of their work using simple analogies:

1. The Problem: Guessing the Slope in the Dark

Usually, to find the bottom of a valley, you need to know the slope. Since you can't see the slope, you have to guess it. The standard way to do this is to poke the ground at two points close to each other (one step forward, one step back) and see the difference in height. This is called a two-point finite-difference estimator.

The authors ask: How do we guess the slope best if the ground is shaped differently?

Is the valley shaped like a circle (Euclidean)?
Is it shaped like a diamond (L1 norm)?
Is it shaped like a square (L infinity norm)?

They study how to guess the slope when the "ground" (the loss function) and the "rules of the game" (the geometry) can be any of these shapes.

2. The Innovation: The "Cone" Sampling Strategy

To guess the slope, you need to pick a direction to poke the ground.

Old way: Most people pick a direction randomly, like rolling a die to pick a direction on a perfect sphere (like a basketball).
This paper's way: The authors suggest picking a direction based on a "cone measure" on different shapes (like a diamond or a cube).

The Analogy: Imagine you are blindfolded in a room.

If the room is a sphere, you might spin around and point in a random direction.
If the room is a cube, pointing randomly at the corners might be better than pointing at the flat walls, depending on what you are trying to find.
The authors figured out that for certain shapes of the "valley," pointing toward the corners (or specific edges) of a cube or diamond gives you a much better guess of the slope than pointing randomly on a sphere.

3. The Big Claim: "High-Probability" Guarantees

Most previous studies said, "On average, over many tries, this method works well."
The authors say: "No, we can prove that almost every single time you run this, it will work well."

The Metaphor: Imagine a weather forecaster.
- Old method: "On average, it rains 50% of the time." (This doesn't help you if you need to know if it will rain today).
- New method: "We can guarantee with 99% certainty that it will not rain today."
The paper proves that their algorithm is reliable. It doesn't just work "on average"; it works consistently, even in the worst-case scenarios, provided the "fog" (the noise in the data) isn't too crazy.

4. The "Anytime" Feature

The algorithm is data-driven and anytime.

Analogy: Imagine you are playing a video game where you don't know how many levels there are. Some algorithms need you to tell them, "The game ends in 100 levels," so they can plan their moves.
This algorithm doesn't care. It can start playing, and if the game ends in 10 levels or 10,000 levels, it adapts on the fly. It doesn't need to know the "horizon" (the end of the game) to play optimally.

5. The "Gap" in the Results

The authors found a fascinating limitation.

For "smooth" valleys (q ≤ 2): Their method is the absolute best possible way to guess the slope. They proved you can't do better.
For "spiky" valleys (q > 2): There is a gap. Their method works, but it's not quite as perfect as the theoretical limit suggests.
The Metaphor: Imagine trying to find a needle in a haystack.
- If the haystack is soft and round (q ≤ 2), their tool finds the needle perfectly.
- If the haystack is made of sharp, jagged spikes (q > 2), their tool still finds the needle, but it seems the tool itself (the way they poke the ground) might be the problem, not their math. They suspect that for these "spiky" shapes, we might need a completely different kind of "poke" in the future.

Summary of What They Did

Created a new way to guess slopes by poking the ground in directions based on different geometric shapes (spheres, diamonds, cubes).
Proved it works almost every time (high probability), not just on average.
Made it flexible so it works without knowing how long the task will last.
Found a limit: It's perfect for some shapes, but for very "spiky" shapes, the current method of guessing slopes might be inherently flawed, leaving a puzzle for future researchers.

In short, they built a more reliable, adaptable, and mathematically proven "blindfolded explorer" for finding the bottom of complex, multi-shaped valleys.

Technical Summary: High-probability zeroth-order online convex optimisation beyond Euclidean geometry

Problem Setting
This work addresses the problem of online convex optimisation (OCO) in a zeroth-order setting where the learner has access only to function evaluations, not gradients. The specific setting involves a sequence of random Lipschitz losses $f_t$ drawn from a distribution $\mu$ . While the realizations $f_t$ need not be convex, their mean function $F_\mu(x) = \mathbb{E}_{f \sim \mu}[f(x)]$ is assumed to be convex. The learner operates over a compact, convex set $\Theta \subset \mathbb{R}^d$ and aims to minimise the pseudo-regret:
$R_n^\mu = \sup_{u \in \Theta} \sum_{t=1}^n \left( F_\mu(x_t) - F_\mu(u) \right)$
The feedback model allows the learner to query the function at two points per round, $x_t \pm h_t \zeta_t$ , where the direction $\zeta_t$ is sampled from the boundary of an $\ell_r$ -ball according to the cone measure. The losses are assumed to be $L$ -Lipschitz with respect to an $\ell_q$ norm, and the algorithm employs an $\ell_p$ -strongly convex regulariser within a Follow-The-Regularised-Leader (FTRL) framework.

Methodology
The paper proposes an adaptive, anytime algorithm (SOLO FTRL) that utilizes randomised two-point finite-difference gradient estimators. The core methodological innovations lie in the geometric generalisation and the probabilistic analysis:

Generalised Gradient Estimation: The gradient estimator is constructed using directions sampled from the cone measure on the boundary of an $\ell_r$ ball ( $\zeta \sim \partial B_d^r$ ). The estimator is defined as:
$g_t = \frac{d}{2h_t} \left( f_t(x_t + h_t \zeta_t) - f_t(x_t - h_t \zeta_t) \right) n_r(\zeta_t)$
where $n_r(\zeta)$ is the unit normal to the $\ell_r$ sphere at $\zeta$ . This generalises classical spherical estimators ( $r=2$ ) and allows for $\ell_1$ or $\ell_\infty$ sampling geometries.
Moment Analysis and Concentration: Unlike previous works that rely on in-expectation bounds (typically using second moments), this analysis establishes all-moment bounds for the gradient estimator in the dual norm $\ell_{p^*}$ . By proving that the sequence of dual norm squared errors satisfies a sequential Bernstein moment condition (SBM), the authors derive time-uniform high-probability concentration inequalities. This involves controlling the tail behavior of the gradient estimator using concentration of measure results for Lipschitz functions on $\ell_r$ spheres.
Adaptive Algorithm: The algorithm is fully data-driven and does not require knowledge of the time horizon $n$ or worst-case constants derived from the moment analysis. It only requires the specification of the geometry parameters ( $p, r$ ), the regulariser, and an upper bound on the domain size.

Key Contributions

Unified High-Probability Bounds: The paper provides the first unified high-probability regret bounds for zeroth-order OCO across all geometry combinations $p, q, r \in [1, \infty]$ . These bounds hold for random Lipschitz losses with a convex mean, strengthening previous in-expectation guarantees to time-uniform high-probability statements.
Gradient Estimator Moment Bounds: The authors prove novel moment bounds for $\ell_r$ -randomised two-point gradient estimators in the dual norm $\ell_{p^*}$ . These results track the dependence on the sampling geometry ( $r$ ) and the Lipschitz norm ( $q$ ), establishing that the cumulative squared dual norms behave as a subgamma process.
Algorithm-Independent Lower Bounds: The paper establishes constant-probability lower bounds for the same problem class. These bounds improve upon previous in-expectation results (specifically for $p=q=1$ by removing a $\sqrt{\log d}$ factor) and cover the full range of $p, q \in [1, \infty]$ with a single construction.
Identification of a Gap for $q > 2$ : The analysis reveals a discrepancy between the upper and lower bounds when $q > 2$ . The authors argue this is not an artifact of the proof but indicates an intrinsic suboptimality of standard randomised two-point gradient estimators in this regime, as they fail to exploit the sparsity inherent in high- $q$ Lipschitz functions.

Main Results
The primary theoretical result (Theorem 2.3) states that with probability at least $1-\delta$ , the regret satisfies:
$R_n^\mu \leq 22R\sqrt{\nu_r} \left( \sqrt{n \Lambda_n^*(\delta)} + 11 d^{\gamma_r} \log(32n/\delta)^{3/2} \right)$
where $\nu_r$ is a proxy variance depending on $L, d, p, q, r$ , and $\gamma_r = (1/p - 1/r)_+$ . The term $\sqrt{\log \log n}$ arises from the anytime nature of the bound.

The lower bound (Theorem 2.4) shows that for any two-point algorithm, there exists a problem instance where the regret is at least of the order $d^{(1/2 + 1/q - 1/p)_+} LR\sqrt{n}$ with constant probability.

Significance and Claims
The paper claims to provide the first unified treatment of zeroth-order online convex optimisation beyond the Euclidean setting ( $p=q=r=2$ ). By moving from in-expectation to high-probability analysis, the results offer stronger, time-uniform guarantees suitable for adaptive and anytime settings.

The work highlights a specific limitation in the current methodology: for $q > 2$ , the standard randomised gradient estimators appear to be suboptimal compared to the theoretical lower bound. The authors suggest that the gap arises because these estimators lack a mechanism to exploit the sparsity of the "hard" instances in the $q > 2$ regime, a property that the lower bound construction explicitly utilises. This finding suggests that future improvements in this regime may require fundamentally different estimator structures rather than just refined analysis of existing finite-difference methods.