# Online Convex Optimization with Sublinear Noisy Probes

arXiv: https://arxiv.org/abs/2606.14640 · HTML: https://mlsanity.com/paper/2606.14640/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 38 references that are in the map.
- First posted on arXiv 12 Jun 2026.

## Builds on (most cited first, 23 of 23)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Online Learning with Abstention](https://mlsanity.com/paper/1703.03478/) (2017)
- [Fast Rates for Online Prediction with Abstention](https://mlsanity.com/paper/2001.10623/) (2020)
- [The Price of Information in Combinatorial Optimization](https://mlsanity.com/paper/1711.00405/) (2017)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [A Stochastic Probing Problem with Applications](https://mlsanity.com/paper/1302.5913/) (2013)
- [Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions](https://mlsanity.com/paper/1608.00673/) (2016)
- [The Extended Littlestone's Dimension for Learning with Mistakes and Abstentions](https://mlsanity.com/paper/1604.06162/) (2016)
- [Pandora's Problem with Nonobligatory Inspection](https://mlsanity.com/paper/1905.01428/) (2019)
- [Online Selective Classification with Limited Feedback](https://mlsanity.com/paper/2110.14243/) (2021)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Online Learning and Bandits with Queried Hints](https://mlsanity.com/paper/2211.02703/) (2022)
- [Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS](https://mlsanity.com/paper/2212.01524/) (2022)
- [Submodular Norms with Applications To Online Facility Location and Stochastic Probing](https://mlsanity.com/paper/2310.04548/) (2023)
- [Online Learning with Sublinear Best-Action Queries](https://mlsanity.com/paper/2407.16355/) (2024)
- [Multi-Armed Bandits With Best-Action Queries](https://mlsanity.com/paper/2605.08287/) (2026)

## Abstract (arXiv)

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.