探测可降低在线学习遗憾
论文研究在线凸优化（OCO），其中学习者每轮使用一次δ-噪声成对探测比较两个点的损失。主要定理给出遗憾界O(min{√(dT ln T), (dT ln T)/(k|1-2δ|)})，该界对T、k和δ紧。即使探测预算k子线性，也能改进最坏情况遗憾。对于专家设置，在有限决策集上得到完全紧的速率。分析通过方差减少效应和二阶指数权重方法揭示探测收益。
Online Convex Optimization with Sublinear Noisy Probes
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$ $δ$-noisy pairwise probes, we obtain: $ \text{Reg}_T \le O\left(\min\left\{\sqrt{dT\ln T},\; \frac{dT\ln T}{k|1-2δ|}\right\}\right) $, which is tight (up to logarithmic factors in $T$) across $T$, $k$ and $δ$. Specifically regarding the noise parameter $δ\in [0,1]$, the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., $δ$ 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.