Online Convex Optimization with Sublinear Noisy Probes

Abstract

We study Online Convex Optimization (OCO) over a convex set $K\subseteq {\mathbb{R}}^d$, where in each round $t$ the learner selects $x_t\in K$ and then observes a convex loss $f_t:K\to [0,1]$, with the goal of minimizing regret to the best fixed decision in hindsight. We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise (comparison-based) feedback available every round in OCO. In our framework, the learner has a budget of $k\le T$ pairwise probes; on a probed round it may query two points and learn which one has smaller loss. Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime. With $k$ $\hat{I}´$-noisy pairwise probes, we obtain: ${\text{Reg}}_T\le O\left(\min \left\{\sqrt{dT\ln T},\frac{dT\ln T}{k|1-2\hat{I}´|}\right\}\right)$, which is tight (up to logarithmic factors in $T$) across $T$, $k$ and $\hat{I}´$. Specifically regarding the noise parameter $\hat{I}´\in [0,1]$, the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., $\hat{I}´$ is close to $\frac{1}{2}$. When applying the same techniques to a finite $K$ for the prediction with $d$ experts setting, the resulting rates are instead completely tight in all parameters, including $d$. Our analysis gives a streamlined treatment of pairwise probing in OCO by quantifying the benefit of probing via a variance reduction effect, combined with a second-order (variance-based) analysis of Continuous Exponential Weights.

Accepted at COLT '26