Online Convex Optimization with Sublinear Noisy Probes

We study Online Convex Optimization (OCO) over a convex set Ksubseteq mathbb Rd, where in each round t the learner selects xt∈ K and then observes a convex loss ft:K→[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≤ 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 δ-noisy pairwise probes, we obtain: RegT ≤ Oleft(minleft√dTln T,; fracdTln Tk|1-2δ|rightright) , which is tight (up to logarithmic factors in T) across T, k and δ. Specifically regarding the noise parameter δ ∈ [0,1], the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., δ is close to frac12. 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.