Online Convex Optimization with Sublinear Noisy Probes

We study Online Convex Optimization (OCO) over a convex set K⸦ℝd, where in each round t the learner selects xtK 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 (Russo et al., 2024), and pairwise (comparison-based) feedback available every round in OCO (Bhaskara et al., 2023b). In our framework, the learner has a budget of kT 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 5-noisy pairwise probes, we obtainREGT O(min{dTlnT,dTlnT/k|1-2δ\}), 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 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 (Bubeck, 2011; de Rooij et al., 2014).