# Logarithmic High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback

arXiv: https://arxiv.org/abs/2603.25029 · HTML: https://mlsanity.com/paper/2603.25029/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 11 references that are in the map.
- First posted on arXiv 26 Mar 2026.

## Builds on (most cited first, 3 of 3)

- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)

## Abstract (arXiv)

We study online convex optimization (OCO) with two-point bandit feedback against a non-anticipating adaptive adversary. In this setting, a learner competes with an adversarial sequence of convex losses while observing each loss only through two function evaluations. For strongly convex losses, Agarwal, Dekel, and Xiao~citeyearparagarwal2010optimal proved a comparator-wise logarithmic regret bound in expectation. Consequently, by minimizing outside the probability space, their result yields a pseudo-regret guarantee of the form EB AT-minx∈mathcal KEB LT(x), where AT is the algorithm's two-query cumulative loss and LT(x) is the comparator's cumulative loss. They asked whether a logarithmic high-probability guarantee is achievable in the same two-point strongly convex setting. Our main theorem provides the corresponding fixed-comparator high-probability statement: for any comparator x∈mathcal K fixed independently of the algorithmic random directions, the standard two-point projected gradient method guarantees, with probability at least 1-δ, a two-query regret bound of order [ Oleft(fracdG2μleft(log T+log(1/δ)right)+dGDlog(1/δ)+Glog Tleft(1+fracDrright)right). ] At the comparator-wise level, our leading horizon-dependent term is linear in d, compared with the d2-type term in the original analysis of Agarwal, Dekel, and Xiao. The key ingredient is a high-confidence analysis that simultaneously absorbs the martingale error into strong convexity and preserves the linear-in-dimension estimator control of the two-point method. A deterministic covering argument then yields a realized full-comparator guarantee against minx∈mathcal KLT(x), preserving logarithmic dependence on T at the cost of the standard covering-number factor.