Optimal High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917383559446528 |
|---|---|
| author | Ye, Haishan |
| author_facet | Ye, Haishan |
| contents | We consider the problem of Online Convex Optimization (OCO) with two-point bandit feedback.
In this setting, a player attempts to minimize a sequence of adversarially generated convex loss functions, while only observing the value of each function at two points.
While it is well-known that two-point feedback allows for gradient estimation, achieving tight high-probability regret bounds for strongly convex functions still remained open as highlighted by \citet{agarwal2010optimal}. The primary challenge lies in the heavy-tailed nature of bandit gradient estimators, which makes standard concentration analysis difficult.
In this paper, we resolve this open challenge and provide the first high-probability regret bound of $O(d(\log T + \log(1/δ))/μ)$ for $μ$-strongly convex losses. Our result is minimax optimal with respect to both the time horizon $T$ and the dimension $d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_25029 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback Ye, Haishan Machine Learning We consider the problem of Online Convex Optimization (OCO) with two-point bandit feedback. In this setting, a player attempts to minimize a sequence of adversarially generated convex loss functions, while only observing the value of each function at two points. While it is well-known that two-point feedback allows for gradient estimation, achieving tight high-probability regret bounds for strongly convex functions still remained open as highlighted by \citet{agarwal2010optimal}. The primary challenge lies in the heavy-tailed nature of bandit gradient estimators, which makes standard concentration analysis difficult. In this paper, we resolve this open challenge and provide the first high-probability regret bound of $O(d(\log T + \log(1/δ))/μ)$ for $μ$-strongly convex losses. Our result is minimax optimal with respect to both the time horizon $T$ and the dimension $d$. |
| title | Optimal High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2603.25029 |