Online Convex Optimization with Sublinear Noisy Probes

Technical Summary: Online Convex Optimization with Sublinear Noisy Probes

Problem Formulation
This paper investigates Online Convex Optimization (OCO) over a convex set $K \subseteq \mathbb{R}^d$. In the standard setting, a learner selects a decision $x_t \in K$ at each round $t$, incurs an adversarially chosen convex loss $f_t(x_t)$, and receives full feedback (the function $f_t$ or its subgradients). The objective is to minimize regret against the best fixed decision in hindsight.

The authors 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 feedback in OCO [Bhaskara et al., 2023b]. In this framework, the learner is granted a budget of $k \le T$ pairwise probes. On a probed round, before selecting $x_t$, the learner may query two points $\{y_{t,1}, y_{t,2}\} \subseteq K$ and receive an indication of which point incurs the smaller loss. Crucially, these probes are noisy: with probability $\delta$, the oracle returns the point with the higher loss (the "wrong" answer), and with probability $1-\delta$, it returns the correct minimizer. The noise parameter $\delta \in [0, 1]$ is unknown to the learner.

The protocol assumes an oblivious adversary who pre-commits to the sequence of loss functions $\{f_t\}_{t=1}^T$ before the learner decides whether to probe at any specific round. This constraint is vital; if the adversary could adapt to the probing decision, the probe could be rendered useless (e.g., by setting losses to 0 on probe rounds), degrading the regret bound to $\Theta(\sqrt{T-k})$.

Methodology
The proposed algorithm is an adaptive, probe-augmented version of Continuous Exponential Weights (CEW). The core technical insight relies on a variance reduction effect combined with a second-order (variance-based) analysis of the CEW algorithm.

1. Variance Reduction via Probing:
   On a probing round, the algorithm samples two points independently from the current density distribution $p_t$. By playing the point with the lower observed loss (or the one suggested by the probe), the expected loss decreases by an amount proportional to the variance of the loss function under $p_t$, denoted $v_t = \text{Var}_{x \sim p_t}[f_t(x)]$. Specifically, for noiseless probes, the expected loss is reduced by $v_t$.

2. Handling Noisy Probes (Meta-Learner):
   Since $\delta$ is unknown, the algorithm employs a lightweight Meta-Learner (specifically AdaHedge) to decide whether to "follow" the probe's suggestion or "invert" it. The Meta-Learner operates on two actions: $F$ (follow) and $I$ (invert). It updates its weights based on the losses incurred by these two hypothetical actions on the probed rounds. This allows the algorithm to adaptively trust the probe when it is informative ($\delta$ far from $1/2$) and ignore it when it is uninformative.

3. Regret Decomposition:
   The regret analysis decomposes the total loss into two components:

   • Non-probing rounds: The algorithm follows the standard CEW update. The regret is bounded using a second-order analysis (following de Rooij et al., 2014) that relates the baseline regret to the cumulative variance $V_T = \sum v_t$.
   • Probing rounds: The loss is bounded by the loss of the better of the two Meta-Learner actions ($F$ or $I$), plus a regret term for the Meta-Learner itself. The analysis shows that the "better" action achieves a loss reduction proportional to $|1-2\delta|v_t$.

Key Results
The paper establishes that a sublinear budget of noisy pairwise probes can provably improve the worst-case regret in the full-feedback OCO regime.

• General Convex Losses: For general convex losses bounded in $[0, 1]$ over a convex set $K \subseteq \mathbb{R}^d$, the expected regret is:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{dT \ln T}, \frac{dT \ln T}{k |1 - 2\delta|} \right\} \right)$$
  This bound is tight (up to logarithmic factors in $T$) with respect to the horizon $T$, the probe budget $k$, and the noise parameter $\delta$. The regret smoothly degrades as $\delta \to 1/2$ (coin flip).

• Prediction with Experts: In the special case of the experts setting (linear losses over the vertices of the simplex $\Delta^{d-1}$), the bound improves to:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{T \ln d}, \frac{T \ln d}{k |1 - 2\delta|} \right\} \right)$$
  These rates are completely tight in all parameters, including the dimension $d$.

Significance and Contributions
The authors claim several significant contributions:

1. Unification: The work unifies the discrete "best-expert" probing model and the continuous "pairwise comparison" model into a single framework, demonstrating that pairwise probes are as informative as best-expert probes for achieving optimal regret rates.
2. Robustness to Noise: Unlike previous works that often assume noiseless or specific noise models, this framework handles unknown noise levels $\delta$ and achieves optimal dependence on $|1-2\delta|$.
3. Technical Novelty: The analysis avoids differential privacy machinery and assumptions regarding gradient norms or curvature (which were required in prior works like Bhaskara et al., 2023b). Instead, it leverages a variance-based reduction argument.
4. Optimality: The paper provides matching lower bounds (in Appendix A) showing that the derived rates are tight for the experts setting and tight in $T, k, \delta$ for general convex sets.

The authors note that while the theoretical guarantees are strong, the main algorithm requires computing integrals over convex sets, which may be computationally hard in general. They identify the development of efficient algorithms achieving comparable guarantees as an open direction.