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

Jul 16, 2026

Online convex optimization with two-point bandit feedback is studied against a nonanticipating adaptive adversary, where each round reveals only two function evaluations rather than gradients. For strongly convex losses, prior work established comparator-wise logarithmic regret in expectation, yielding pseudo-regret via minimizing outside the probability space. The main result proves a fixed-comparator high-probability two-query regret bound of logarithmic order in T and 1/δ, using high-confidence martingale-to-strong-convexity analysis and deterministic covering to extend to a realized full-comparator guarantee.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages23

Reading Time58 min

Introduction

Problem setting and regret notions

Motivation from bandit feedback and strong convexity

Related work and missing ingredient

arXiv :2603 .25029v4 [ cs .LG] 9 Jul 2026 Logarithmic High-Probability Regret for Strongly Convex Online Convex Optimization with Two-Point Bandit Feedback Haishan Ye School of Management Xi’an Jiaotong University hsye [cs@outlook.com](cs@outlook.com) Abstract We study online convex optimization (OCO) with two-point bandit feedback against a nonanticipating 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 (2010) 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 EAT −minx∈K ELT (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 ∈ 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 O 􀀒 dGµ2 (log T + log(1/δ)) + dGD log(1/δ) + Glog T 􀀒 1 + Dr􀀓􀀓 . 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∈K LT (x), preserving logarithmic dependence on T at the cost of the standard covering-number factor. 1 Introduction Online convex optimization (OCO) is a repeated decision problem between a learner and an adversary. At each round t = 1 , ... , T, the learner chooses an action xt from a fixed convex set K ⊂ Rd. A non-anticipating adaptive adversary then selects a convex loss function ℓ t : K → R using the past history and, in the two-point protocol studied here, before the learner’s fresh random direction at round t is sampled. While full-information OCO is well understood, the bandit feedback setting, where only function values of ℓt are observed, remains substantially more challenging because gradients are unavailable. Two-point feedback is the minimal zeroth-order interface that permits an unbiased gradient estimate of a smoothed loss, making it a natural test case for whether bandit feedback can match full-information fast rates. Strong convexity is the canonical assumption under which full-information OCO improves from √T-type regret to logarithmic regret. High-probability guarantees are also important in online decision problems: an expected logarithmic bound may still allow rare but large deviations, whereas a high-confidence bound controls almost every realization of the learner’s randomization. The main difficulty is that the two-point gradient estimator is noisy, and this noise is coupled with the learner’s trajectory under an adaptive adversary. Consequently, the usual full-information logarithmic-regret proof and a direct Azuma-type concentration argument do not by themselves yield the desired rate. For compactness, write T T AT := Xt=1 ℓt(xt+~~ ~~αut)~~ ~~+2~~ ~~ℓt(xt~~ ~~−~~ ~~αut), LT (x) := Xt=1 ℓt(x) . For a fixed comparator x ∈ K, the two-point protocol analyzed in this paper measures performance by R2ptT(x) = AT−LT(x) . We distinguish three comparator semantics. A comparator-wise expected bound has the form ∀x ∈ K, E [AT − LT(x)] ≤ B. Since x⋆exp ∈ arg minxELT(x) is deterministic, one may minimize outside the probability space and obtain the pseudo-regret bound EAT

FAQs

What feedback model does the paper study in online convex optimization?

It studies a two-point bandit protocol where the learner observes each convex loss only through two function evaluations (two-point queries) rather than full gradients.

What is the main theorem’s guarantee?

For any fixed comparator x in the convex set K, the standard two-point projected gradient method achieves a two-query regret bound with probability at least 1−δ, with logarithmic dependence on T and 1/δ.

How does the result differ between comparator-wise and realized full-comparator regret?

Comparator-wise statements hold for a fixed x and may depend on x through the high-probability event, while realized full-comparator regret requires a single guarantee over all x, obtained via a deterministic covering argument.

Jul 16, 2026

Upload by Lucas Martin