Online Convex Optimization with Sublinear Noisy Probes Simone Di Gregorio∗
Anupam Gupta†
Stefano Leonardi∗
Matteo Russo‡
arXiv:2606.14640v1 [cs.LG] 12 Jun 2026
Abstract We study Online Convex Optimization (OCO) over a convex set K ⊆ 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 [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 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 √ dT ln T dT ln T , , RegT ≤ O min 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].
1
Introduction
Online convex optimization (OCO) is a general framework for sequential decision-making in which, over a horizon of T rounds, a learner repeatedly selects a decision xt from a convex set K ⊆ Rd , incurs an adversarially chosen convex loss ft (xt ), and receives feedback at the end of each round [Shalev-Shwartz, 2012, Hazan, 2016, Orabona, 2019]. The learner’s performance is measured by regret, defined as the gap between its cumulative loss and that of the best fixed comparator x⋆ ∈ K in hindsight: T T X X RegT = ft (xt ) − inf ft (x). x∈K
t=1
t=1
In the full-information variant, the entire loss function ft (or equivalently a subgradient oracle at every point) is revealed after each round;√classical methods such as Online Gradient Descent and Follow-the-Regularized-Leader achieve Θ( T ) regret (up to problem-dependent geometry factors). In the bandit version, only ft (xt ) is revealed for the played point xt . ∗
Sapienza University of Rome, Italy ([email protected], [email protected]) New York University, USA ([email protected]) ‡ EPFL, Switzerland ([email protected]) †
1
The OCO framework subsumes Online linear optimization (OLO), where losses are linear and expressed as ft (x) = ft⊤ x for vector ft ∈ Rd . As a further special case, we have the classical online learning with finitely many actions/experts: taking ∆d−1 (the d − 1-dimensional simplex) and linear losses, the regret against the best vertex recovers the usual notion of regret in the experts problem. In this discrete specialization, full feedback reveals all coordinates of ft , while bandit feedback reveals only ft (xt ) for the played expert xt . Motivated by the recent surge of algorithms augmented by external predictions, hints, or sideinformation [Mitzenmacher and Vassilvitskii, 2020], we study a model in which the learner may occasionally obtain limited advance information about the losses before committing to its decision on that round. Most relevant to our setting are Bhaskara et al. [2023b] and Russo et al. [2024], who show that even very restricted query access can dramatically reduce regret. In Bhaskara et al. [2023b], the learner is allowed pairwise comparison probes: at the beginning of each round t, before choosing the decision xt , the learner may choose two candidate decisions and learn which one will incur smaller instantaneous loss in this round, without revealing the loss values themselves. They obtain time-independent regret bounds for online linear optimization and improved rates for OCO under additional curvature assumptions. In the discrete bandits setting, they show that pairwise comparisons can yield regret of order O(d ln T ) in the stochastic case. Complementarily, Russo et al. [2024] allow best-expert probes (which they call queries) in the experts special case only, which reveal the identity of the minimizing expert in the current round t (before the decision xt is played); however, n√only k ≤ T such o queries can be made. In this setting, they show a regret bound of T ln d O min T ln d, /k . These results raise the following natural question: If the learner is able to issue only a sublinear number k ≪ T of (possibly noisy) pairwise probes, √ how much can the OCO regret be improved with respect to the base T rate? To address this question, we first formalize an OCO-with-probing model that unifies both discrete and continuous settings, and then state our results.
1.1
Our Model
We present a probing-augmented online optimization protocol. The OCO and prediction with expert advice settings arise as two specializations. 1.1.1
Online convex optimization with noisy probing
Let K ⊂ Rd be either a compact convex set or a finite set. The interaction proceeds for T rounds against an oblivious adversary who pre-commits to a sequence of loss functions bounded in [0, 1]: {ft : K → [0, 1]}Tt=1 . At each round t ∈ {1, . . . , T }, the learner picks xt ∈ K, incurs loss ft (xt ), and then receives feedback ft (x) for all x ∈ K. Moreover, for appropriate functions f and g we define R ⟨f, g⟩ = K f (x)g(x)µ(dx), where the base measure µ is explicit or clear from the context. Probing budget. In addition to the feedback, the learner may issue probes in at most k rounds. Let Q ⊆ {1, . . . , T } denote the set of probed rounds, decided (possibly randomly and adaptively) by the learner, with |Q| ≤ k. If t ∈ Q, before selecting xt , the learner may specify a (possibly randomized) finite set of C candidate points Pt = {yt,1 , . . . , yt,C } ⊆ K, and the probe returns the identity of the candidate with minimal instantaneous loss in Pt , possibly corrupted by noise. In this paper we focus on the least powerful nontrivial probes, namely pairwise comparisons with C = 2. 2
To model noise, we assume that the probe returns the candidate with the maximal (instead of minimal) loss with probability δ, but our results clearly apply to less challenging noise: for example, the oracle could return, with probability δ, any of the two probed points, which is better than returning the arg max, and our regret bounds still hold. Moreover, any probe model with general C > 2 can be reduced to the pairwise case by constructing Pt as multiset made up of yt,1 repeated C − 1 times and yt,2 once: our upper bounds thus extend for general C > 2. Definition 1.1 (Noisy comparison probe). Fix δ ∈ [0, 1] and an integer C ≥ 1. A δ-noisy (comparison) probe at round t is a (possibly randomized) set Pt = {yt,1 , . . . , yt,C } ⊆ K together with an outcome: ( yt⋆ ∈ arg miny∈Pt ft (y), with probability 1 − δ, ŷt = yt− ∈ arg maxy∈Pt ft (y), with probability δ. Whenever the minimizer or maximizer is not unique, ties are broken uniformly at random. When δ = 0, we call the probe noiseless. Moreover, a probe is global when Pt = K and δ = 0, that is the probe outcome is yt⋆ ∈ arg miny∈K ft (y) with probability 1, assuming the minimum is achieved.1 Protocol. Formally, first an oblivious adversary pre-commits to a sequence of convex loss functions f1 , . . . , fT bounded in [0, 1], and then, in each round t = 1, . . . , T : 1. The learner decides if t ∈ Q: if so, it chooses Pt ⊆ K and observes ŷt ∈ Pt . 2. The learner chooses xt ∈ K (possibly as a randomized function of ŷt and the past). 3. The learner incurs loss ft (xt ) and observes full feedback {ft (x)}x∈K . PT Regret. For any point x ∈ K, define the cumulative loss LT (x) = t=1 ft (x). Similarly, let PT LT (Alg) = t=1 ft (xt ) be the cumulative loss of a learner Alg whose decisions over rounds are x1 , . . . , xT , each belonging to K. In turn, these points are sampled from the probability measures induced by the densities p1 , . . . , pT set by the learner Alg across rounds. In the following, for any time t > 0, we abuse notation and write x ∼ pt for x being sampled from the probability measure induced by pt and the base measure µ. Moreover, P let vt = Vx∼pt [ft (x)] be the variance of the function at time t according to pt , and let Vt = τ ≤t vτ be the cumulative variance up until time t. The (worst-case) expected regret of an algorithm Alg is ( " T # ) T X X E [RegT (Alg)] = sup E ft (xt ) − inf ft (x) , f
t=1
x∈K
t=1
where the expectation is with respect to the learner’s internal randomness and the probe noise, and the supremum ranges over all obliviously chosen sequences f = {ft }Tt=1 of admissible losses bounded in [0, 1]; for online convex optimization, we restrict to convex losses. Our goal is sublinear regret, i.e., E [RegT (Alg)] = o(T ), while leveraging at most k noisy comparison probes.
1.2
Our Results and Technical Challenges
Our main contribution is to show that even a sublinear number of pairwise comparison probes can substantially reduce regret. We unify the two probing paradigms of Bhaskara et al. [2023b], Russo 1
If the minimum is not achieved, one may model the notion of global probe by letting it return any point in a sublevel set characterized by a function value arbitrary close to the minimum.
3
et al. [2024] into a single framework in which the learner is granted a budget of k ≤ T pairwise (possibly noisy) probes over a horizon of T rounds, and we analyze the resulting regret tradeoffs for full feedback OCO and prediction with experts. Regret guarantees. With k pairwise δ-noisy probes, we prove that one can achieve √ dT ln T , RegT ≤ O min dT ln T , k |1 − 2δ|
(1)
for general convex losses bounded in [0, 1] (see Theorem 3.1). In the special case of experts (i.e., linear losses over the vertices of the simplex ∆d−1 ), we can replace a factor of d ln T by ln d for both terms of the min in (1) to get an improved bound of √ T ln d RegT ≤ O min . (2) T ln d, k |1 − 2δ| A key takeaway is that the regret bounds of (2) match those obtained in Russo et al. [2024] under best-expert probes, where in each queried round the learner effectively “looks ahead” and learns the globally optimal action x⋆t . In the special case of experts only, they leverage a crucial property of best-expert probes: on a probed round, the learner can guarantee the minimum possible loss, since it knows the expert with lowest loss at that round. This yields a non-positive (and potentially negative) contribution to regret during probing rounds. Combined Hedge bound √ with a standard T ln d on the remaining rounds, this leads to worst-case regret O k once k ≥ Ω( T ln d). Making this argument with pairwise probes runs into a basic obstacle even just for the special case of experts: to benefit, one must compare against (or identify) a near-best expert with sufficiently large probability. One approach to doing this is adapting the arguments from Russo et al. [2024] and mix a uniformly random probe with probes from the distribution of the Hedge algorithm, to avoid hurting the baseline performance. In Appendix B, we carry over this analysis, attaining suboptimal rates even in the noiseless case. In contrast, our algorithms manage to get the (optimal) bounds in Equation (2) using only (noisy) pairwise probes, moreover getting the rate in Equation (1) for general bounded convex losses over an arbitrary convex body K! Our approach and the main technical insight. Our main theorem (Theorem 3.1) simultaneously handles (i) general convex losses over general convex bodies, (ii) sublinear probe budgets, and (iii) noisy probes, recovering essentially tight (in terms of T, k and δ) bounds on the regret rate. The algorithm is a direct and adaptive probe-augmented version of continuous exponential weights: it maintains a density pt over K and samples points accordingly (e.g., Bubeck [2011]). This route avoids differential privacy machinery and dispenses with curvature/gradient assumptions [Bhaskara et al., 2023b]. For noiseless probing, the key insight is that a pairwise comparison drawn from pt yields an advantage that can be measured by the variance of the losses under pt . Concretely, on a probing round t, comparing two i.i.d. samples from pt and playing the better one decreases the expected loss by Vx∼pt [ft (x)], the variance of the function according to the density pt : Ept [ft (xt ) | t ∈ Q] ≤ Ept [ft (xt )] − Vpt [ft (xt )] . We then couple this with a variance-based analysis of continuous exponential weights (following the less standard “second-order” style guarantees of de Rooij et al. [2014]), which relates the baseline regret to the same variance term. This alignment is what enables the T/k-type improvement without an additional factor in d, nor making assumptions about gradient norms or curvature. 4
Noisy probes and learning when to trust them. Noisy probes introduce a further challenge: the noise level δ is unknown, so the learner must also infer whether to trust the probe outcome. We cast this as a lightweight meta-learning layer that, on probed rounds, decides whether to follow the probe’s suggestion or invert it. Instantiating this meta-problem with an adaptive two-action learner allows us to recover the bound in (1) with the correct dependence on |1 − 2δ|. Lower bounds. Finally, we show that the rates in (2) are tight in all parameters for prediction with expert advice, and those in (1) are tight in T, k and δ (up to logarithmic factors in T ) for general convex losses over arbitrary convex sets; we give these results in Appendix A.
1.3
On the Power of the Adversary and the Definition of Noisy Probes
The protocol above requires the adversary to fix the loss ft before the learner decides whether to probe at time t. It is crucial that the adversarial loss construction is not coupled with the probing decision. If the adversary could anticipate a probe, she could set√ft ≡ 0 for that round, rendering the probe useless. This would degrade the optimal regret to Θ( T − k), preventing the faster Θ̃(T/k) rates we achieve. This constraint distinguishes our work from the “adversarially noisy” probes considered in the literature [Bhaskara et al., 2020, 2021a, 2023a, 2021b, 2023b]. In those settings, the adversary effectively knows when probing occurs. For instance, Bhaskara et al. [2023b] √ derive a lower bound of Ω( T − k) by constructing an instance where the adversary sets losses to (0, 0) specifically during noiseless probes (and (0, 1) vs. (1, 0) each with probability 1/2 otherwise). This contradicts our results because their model assumes the adversary has access to the learner’s internal randomization (knowing when a probe happens), whereas our model does not.
2
Related Work
The model of learning-augmented algorithms [Mitzenmacher and Vassilvitskii, 2020] has been most recently considered in the context of Online Linear Optimization (OLO) over a convex polytope [Shalev-Shwartz, 2012]. Here, the learner has access to a query mechanism that returns vectors correlated with the true loss vectors. When the optimization domain is the d-dimensional unit sphere and √ the algorithm has full feedback, this additional information enables √ a reduction in regret from O( T ) to O(ln T ), even if the learner only receives such hints on O( T ) rounds √ [Bhaskara et al., 2020, 2021a,b]. Interestingly, this is not possible with bandit feedback, and a Ω( T ) regret is unavoidable even if the hint vectors are well correlated with the true ones [Bhaskara et al., 2023a]. The same work shows that active queries to specific points at which to evaluate the loss function are enough to guarantee regret rates of the form O(d3/2 ln T ), where d is the dimension of the ambient space. Their techniques do not directly apply to our setting, since their probes are defined differently from ours and those from [Bhaskara et al., 2023b]. Moreover, in subsequent work, Bacchiocchi et al. [2026] show that under bandit feedback,√even in the experts setting and with access to best-arm probes, the worst-case regret remains Ω( T − k). Regarding pairwise probes for OCO in particular, the closest work to ours is Bhaskara et al. [2023b], who obtain a Θ(Hd + Gd3/2 ) regret bound in the full feedback setting when probing is available every round (k = T ), under uniform bounds G, H on gradient norms and curvature. Their analysis relies on a differential-privacy-based reduction to Be-The-Regularized-Leader (BTRL), and the dependence on curvature and gradient bounds appears intrinsic to their arguments, which we avoid using our techniques. Techniques developed in this work, as well as in prior ones, aim to adapt to structure in the loss sequence during non-probing rounds, leading to regret guarantees that depend on the "easiness" 5
of the instance. These forms of easiness include stochastic losses or small effective loss ranges. In full-information settings, such structure can be leveraged by algorithms like Hedge to achieve regret depending on the easiness of the instance, without degrading worst-case performance [Cesa-Bianchi et al., 2007, Gaillard et al., 2014, Koolen and van Erven, 2015, Luo and Schapire, 2015]. Another relevant direction is the predictable sequences framework, which focuses on scenarios where the loss sequence follows a regular pattern or is correlated with past observations [Rakhlin and Sridharan, 2013]. Algorithms in this line adjust their learning dynamics to exploit such predictability and achieve improved regret when it exists [Steinhardt and Liang, 2014, Wei and Luo, 2018]. Limited supervision has also been studied through the abstention learning framework, where learners may choose not to predict and instead defer to an oracle, thereby trading off prediction effort with access to external feedback [Li et al., 2011, Sayedi et al., 2010, Zhang and Chaudhuri, 2016, Cortes et al., 2018, Neu and Zhivotovskiy, 2020, Gangrade et al., 2021]. Our work is also connected to stochastic probing, where the learner acts under uncertainty and can selectively probe the environment to obtain partial feedback [Gupta and Nagarajan, 2013, Gupta et al., 2017, Singla, 2018]. This model has applications in problems like Pandora’s Box [Weitzman, 1979, Beyhaghi and Kleinberg, 2019, Beyhaghi and Cai, 2023], online matching [Singla, 2018], and submodular optimization [Patton et al., 2023]. A central challenge in these settings is deciding when and what to probe to optimize long-term performance under uncertainty, and recent algorithms address this by carefully balancing exploration with exploitation [Agarwal et al., 2024].
3
Main Algorithm and Regret Guarantees
In this section, we show how a sublinear number of (noisy) probes enables a significant drop in regret rates. To do so, we recall a generic algorithmic template based on Continuous Exponential Weights with different priors p1 over the domain K. This template has been used by, e.g., de Rooij et al. [2014] for prediction with expert advice, and by Bubeck [2011] for OCO: we augment it with a Meta-Learner and k pairwise comparison probes issued uniformly at random throughout the time horizon (see below). Different instantiations of Algorithm 1 guarantee regret bounds for general convex classes and stronger bounds for the experts setting (see Section 3.5). Meta-Learner. To handle the noisy case with unknown δ, the idea is to run a meta-learner on the “follow the oracle” and the “invert the oracle” actions, succinctly denoted as F and I respectively. Essentially, on probing rounds, we do what the Meta-Learner says: if the routine Meta-Learner returns F , the algorithm follows the probe and plays ŷt , otherwise it plays the other probed point. After receiving feedback, the Meta-Learner is updated based on the value of ft in the probed points. Here, the Meta-Learner is simply AdaHedge (see Theorem 5 in Cesa-Bianchi et al. [2007] and Theorem 6 in de Rooij et al. [2014]) run on the two actions F, I and for rounds Q ⊆ [T ] only (see pseudocode in Algorithm 1 for convenience). AdaHedge is a standard Hedge routine with a time-adaptive learning rate, which allows getting variance-based regret bounds. The losses for F and I are simply the values of ft obtained by either following or inverting the oracle. Theorem 3.1. Consider the problem of online convex optimization with full feedback and k pairwise comparison probes: K ⊂ Rd is convex and compact, with non-empty interior. Then, for an unknown noise parameter δ ∈ [0, 1] and for any sequence of convex functions {ft }Tt=1 bounded in [0, 1], when instantiated with p1 being the uniform density over K and Λ = d ln T , Algorithm 1 has regret √ dT ln T E [RegT (Algk )] ≤ O min dT ln T , . k|1 − 2δ| 6
Algorithm 1: Probe-Augmented Continuous Exponential Weights with Noisy Probes Input: Sequence of measurable functions ft , domain K ⊆ Rd , prior density p1 with respect toRbase measure µ over K, probe budget k ≤ T , parameter Λ Let Z1 = K p1 (x)µ(dx) = 1, V0 = 0. Uniformly sample k out of T rounds, obtaining Q for t = 1, . . . , T do if t ∈ Q then Probe 2 points yt,1 , yt,2 ∼ pt independently and observe ŷt if Meta-Learner(·) = F then Play ŷt else Play yt,1 if yt,1 ̸= ŷt else play yt,2 else Play xt ∼ pt ; Observe loss function ft (x) for all x ∈ K; q Set Vt = Vt−1 + vt and ηt+1 = min 21 , VtΛ+1 Update density for all x ∈ K as Z p1 (x) · exp (−ηt+1 Lt (x)) pt+1 (x) = where Zt+1 = p1 (x) · exp (−ηt+1 Lt (x)) µ(dx) Zt+1 K Update Meta-Learner using {ft (yt,1 ), ft (yt,2 )} if t ∈ Q In order to prove the above theorem, let us first write the following decomposition that holds for any fixed density q over K and any fixed point x⋆ ∈ K: " T # " T # T T T T X X X X X X ft (xt ) − ft (x⋆ ) = E ft (xt ) − ⟨q, ft ⟩ + ⟨q, ft ⟩ − ft (x⋆ ) . (3) E t=1
t=1
t=1
t=1
{z
|
(A)
}
|t=1
{z t=1
(B)
}
We bound term (A) and (B) separately; convexity of ft ’s is used only for bounding (B).
3.1
Loss during non-probing rounds
In this subsection, we compare the performance of Algorithm 1 without considering probes against any distribution q over the domain K. We assume that q ≪ p1 , i.e. q is absolutely continuous w.r.t. p1 , where by this we mean that the property is satisfied by the two underlying measures. The analysis is similar in spirit to the one present in Cesa-Bianchi et al. [2007], de Rooij et al. [2014]. Before proceeding, we bound the average loss using the log-partition function and a variance term. Lemma 3.2. It holds that ⟨pt , ft ⟩ ≤
1 ηt 1 ln Zt − ln Zt+1 + · vt ηt ηt+1 2(1 − ηt )
Proof. For this proof, we recall the following bound (e.g. Wainwright [2019, Proposition 2.10]): Proposition 3.3 (Bernstein Subexponential Tail Bound). For a bounded random variable X with |X − E [X] | ≤ 1, it holds that: ln E [exp (−ηX)] ≤ −η · E [X] +
η2 · V [X] 2(1 − |η|) 7
∀ η : |η| < 1.
To use the above, we define an intermediate normalizer, which uses the same learning rate ηt but after observing ft ; conventionally, in what follows, we let η1 = 1/2: Z Z e pt (x) · exp (−ηt ft (x)) µ(dx) p1 (x) · exp (−ηt Lt (x)) µ(dx) = Zt · Zt+1 = K
K
= Zt · Ext ∼pt [exp (−ηt ft (xt ))] . Applying Proposition 3.3 to the bounded random variable ft (xt ) with density pt , we then obtain: ! et+1 Z ηt2 ln = ln Ext ∼pt [exp (−ηt ft (xt ))] ≤ −ηt · Ext ∼pt [ft (xt )] + · Vxt ∼pt [ft (xt )] Zt 2(1 − ηt ) = −ηt · ⟨pt , ft ⟩ +
ηt2 · vt . 2(1 − ηt )
Hence, using that ηt ≤ 1 and rearranging: 1 ⟨pt , ft ⟩ ≤ ln ηt
Zt e Zt+1
! +
ηt · vt . 2(1 − ηt )
Let us now write Z Z η Zt+1 = p1 (x) · exp (−ηt+1 Lt (x)) µ(dx) = p1 (x) · exp (−ηt Lt (x)) t+1/ηt µ(dx) K
K
Z ≤
ηt+1/ηt p1 (x) · exp (−ηt Lt (x)) µ(dx)
K
et+1 )ηt+1/ηt , = (Z where the inequality follows by Jensen’s inequality since the function y 7→ y ηt+1/ηt is concave in y as ηt+1 ≤ ηt . Combining the above two displays, we have: ! Zt ηt 1 1 ηt 1 + · vt ≤ ln Zt − ln Zt+1 + · vt , ⟨pt , ft ⟩ ≤ ln ηt 2(1 − ηt ) ηt ηt+1 2(1 − ηt ) Zet+1 as desired. Lemma 3.4. Let q be an absolutely continuous density with respect to p1 . If Λ ≥ max(1, KL(q||p1 )), it holds that Algorithm 1 without probes, referred to as Alg0 , satisfies: T X
p ⟨pt − q, ft ⟩ ≤ 2Λ + 5 Λ(1 + VT ).
t=1
Proof. First, we use Lemma 3.2 and obtain via a telescopic sum throughout t: T X t=1
⟨pt , ft ⟩ ≤
T
T
t=1
t=1
X X 1 ηt ηt 1 1 ln Z1 − ln ZT +1 + · vt = − ln ZT +1 + · vt , η1 ηT +1 2(1 − ηt ) ηT +1 2(1 − ηt )
R where we have observed that Z1 = K p1 (x)µ(dx) = 1 by definition, so that ln Z1 = 0. We next bound the two terms separately. Now, for all q ≪ p1 , we have the following: 8
Z
Z
p1 (x) q(x) exp (−ηT +1 LT (x)) µ(dx) q(x) x∈K: q(x)>0 q(x) = Ex∼q exp −ηT +1 LT (x) − ln p1 (x) q(x) ≥ exp Ex∼q −ηT +1 LT (x) − ln , p1 (x)
p1 (x)exp (−ηT +1 LT (x)) µ(dx) ≥
ZT +1 = x∈K
where the first and third inequalities hold because the integrand is positive and because of Jensen’s inequality, respectively. The expectation is well-defined since q ≪ p1 . We thus have: −
1 ηT +1
ln ZT +1 ≤
1 ηT +1
Second, choosing ηt = min
1 2,
(Ex∼q [ηT +1 LT (x)] + KL(q||p1 )) =
T X t=1
q
Λ 1+Vt−1
⟨q, ft ⟩ +
KL(q||p1 ) . ηT +1
ηt , we have that 2(1−η ≤ ηt and also (e.g., Lemma 14 in t)
Gaillard et al. [2014]): T
T X
T
X √ X v ηt √ t · vt ≤ 1 + η t vt ≤ 1 + Λ · 2(1 − ηt ) 1 + Vt−1 t=2 t=2 t=1 T T √ X √ X vt 1 1 √ = 1+ Λ· vt · √ −√ + Λ· 1 + Vt−1 1 + Vt 1 + Vt t=2 t=2 T T √ X √ X 1 v 1 √ t √ −√ ≤1+ Λ· + Λ· 1 + Vt−1 1 + Vt 1 + Vt t=2 t=2 ! Z VT T X √ √ vt dx √ √ ≤1+ Λ 1+ ≤1+ Λ 1+ 1 + Vt 1+x V1 t=2 p ≤ 1 + 3 Λ(1 + VT ).
Combining the derivations above, we obtain, using our assumption on Λ ≥ max(1, KL(q||p1 )): T X t=1
⟨pt − q, ft ⟩ ≤
p p KL(q||p1 ) + 1 + 3 Λ(1 + VT ) ≤ 2Λ + 5 Λ(1 + VT ), ηT +1
as desired.
3.2
Loss during probing rounds
We decompose the loss for probing rounds in two components: (i) the loss assuming δ is known (Lemma 3.5)—corresponding to the loss suffered by the superior action between F and I; and (ii) the excess regret incurred relative to that superior action (Lemma 3.6). In the subsequent lemmas, we denote the instantaneous losses of actions F and I by ℓt (F ) and ℓt (I), and their cumulative losses over the rounds in Q by LQ (F ) and LQ (I), respectively. These losses are random variables contingent on the sampling of the outer algorithm and the Bernoulli noise variables governing the probe responses (Definition 1.1). To avoid conditioning on Q before it is needed, we extend the definition of ℓt (F ) and ℓt (I) to rounds t ∈ / Q by considering the necessary Bernoulli noise and pairs yt,1 , yt,2 , which are completely excluded from the learning protocol. 9
Lemma 3.5. The following holds: Ept [ℓt (F )] ≤ ⟨pt , ft ⟩ − (1 − 2δ)vt
if δ ≤ 1/2
Ept [ℓt (I)] ≤ ⟨pt , ft ⟩ + (1 − 2δ)vt
if δ > 1/2.
Therefore, accounting for the choice of Q ⊆ [T ], the expected cumulative loss accumulated by the better of the two actions F and I is: ! T X k min{E [LQ (F )] , E [LQ (I)]} ≤ · ⟨pt , ft ⟩ − |1 − 2δ| · VT . T t=1
Proof. First, assume δ ≤ 1/2. By definition, we have that the action “follow the oracle” incurs loss: Z pt (u)pt (y) · (1 − δ) · min(ft (u), ft (y)) Ept [ℓt (F )] = K×K
+ δ · max(ft (u), ft (y)) µ(du) µ(dy) ft (u) + ft (y) − (1 − 2δ) · |ft (u) − ft (y)| = pt (u)pt (y) · µ(du) µ(dy) 2 K×K Z (ft (u) − ft (y))2 ≤ ⟨pt , ft ⟩ − (1 − 2δ) · pt (u)pt (y) · µ(du) µ(dy) 2 K×K Z = ⟨pt , ft ⟩ − (1 − 2δ) · pt (u)ft2 (u) µ(du) − ⟨pt , ft ⟩2 Z
K
= ⟨pt , ft ⟩ − (1 − 2δ)vt . P P Summing over t ∈ Q, we have E [LQ (F ) | Q] ≤ . Similarly, if t∈Q ⟨pt , ft ⟩ − (1 − 2δ) · t∈Q vtP 1 δ > /2, we P have, via a derivation almost identical to the one above: E [LQ (I) | Q] ≤ t∈Q ⟨pt , ft ⟩ + (1 − 2δ) t∈Q vt , thus getting a bound for the action “invert the oracle”. Hence, taking another expectation over Q and combining the two cases depending on the sign of 1 − 2δ, we get: ! T T X X k min{E [LQ (F )] , E [LQ (I)]} ≤ · ⟨pt , ft ⟩ − |1 − 2δ| · vt , T t=1
t=1
which concludes the proof. Lemma 3.6. The Meta-Learner has expected cumulative loss bounded by r 2k E [LQ (Meta-Learner)] ≤ min{E [LQ (F )] , E [LQ (I)]} + VT + 3. T Proof. First, recall that the Meta-Learner runs Hedge with adaptive learning rate (i.e., AdaHedge from de Rooij et al. [2014] run on the two actions F, I and for rounds Q ⊆ [T ] only). For any t ∈ Q, let p̃t,F , p̃t,I be the probabilities maintained by the Meta-Learner over F, I. Similarly, let ṽt be the instantaneousP variance induced by p̃t,F , p̃t,I of the Meta-Learner, i.e., ṽt = p̃t,F p̃t,I (ℓt (F )−ℓt (I))2 , and let ṼQ = t∈Q ṽt . Observe that 1 ṽt = p̃t,F p̃t,I (ℓt (F ) − ℓt (I))2 ≤ (ℓt (F ) − ℓt (I))2 . 4 P Also note that |ℓt (F ) − ℓt (I)| = |ft (yt,1 ) − ft (yt,2 )| = ∆t , which means that ṼQ ≤ 41 t∈Q ∆2t . In particular, sincei yt,1 and yt,2 are i.i.d. and taking the difference outputs a centered random variable, hP PT 2 E t∈Q ∆t | Q = t=1 2vt I {t ∈ Q}, where vt is the variance at t of the original learning task. 10
In addition, Theorem 6 in [de Rooij et al., 2014] gives a regret of the Meta-Learner (AdaHedge) with respect to the better of F, I of at most, letting G be the sigma-algebra generated by Q, the noise variables and the sampling from pt : q q 4 ln 2 E [LQ (Meta-Learner) − min{LQ (F ), LQ (I)} | G] ≤ 2 ṼQ ln 2 + + 2 ≤ 2 ṼQ + 3. 3 Combining the above and taking expectations, we obtain E [E [LQ (Meta-Learner) | G]] ≤ E [min{LQ (F ), LQ (I)}] + 2E
q ṼQ + 3 r h i
≤ min{E [LQ (F )] , E [LQ (I)]} + 2 E ṼQ + 3 v u u X u ≤ min{E [LQ (F )] , E [LQ (I)]} + tE E ∆2t Q + 3 t∈Q
v u T uX 2v P [t ∈ Q] + 3 = min{E [L (F )] , E [L (I)]} + t Q
t
Q
t=1
r = min{E [LQ (F )] , E [LQ (I)]} +
2k VT + 3, T
where the second inequality holds by using Jensen’s inequality twice, and the second-to-last equality by using standard properties of conditional expectations.
3.3
Proving the regret bound
We can finally prove the claimed regret bound from Theorem 3.1, and we start by bounding term (A) in Equation (3) using the results from the previous two subsections. Lemma 3.7. Let q be a probability density function on the domain K, such that q ≪ p1 . Then, for an unknown noise parameter δ ≥ 0 and for any sequence of measurable functions ft bounded in [0, 1], Algorithm 1 guarantees, provided Λ ≥ max(1, KL(q||p1 )): E [LT (Algk )] −
T X t=1
√ 25ΛT ⟨q, ft ⟩ ≤ min 12 ΛT , + 4. k|1 − 2δ|
Proof. Let us decompose the loss suffered by Algk into probing and non-probing rounds: E [LT (Algk )] = E LT \Q (Algk ) + E [LQ (Algk )] . In particular, note that the loss suffered by Algk during the probing rounds is equal to that of the Meta-Learner. Since we have the same type P of update to pt in both probing and non-probing rounds, we have that E LT \Q (Algk ) | Q = Tt=1 I {t ∈ / Q} E [ft (xt )], and since Q is uniform: E LT \Q (Algk ) =
T k X 1− ⟨pt , ft ⟩ . T t=1
11
By Lemma 3.5 and Lemma 3.6, it also holds that: r E [LQ (Algk )] = E [LQ (Meta-Learner)] ≤ min{E [LQ (F )] , E [LQ (I)]} + ! r T X k 2k ≤ · VT + 3. ⟨pt , ft ⟩ − |1 − 2δ| · VT + T T
2k VT + 3 T
t=1
Therefore, combining the two above displays, we get T X
r
2k k|1 − 2δ| VT + 3 − · VT T T t=1 r T X p 2k k|1 − 2δ| VT +3 − · VT ≤ ⟨q, ft ⟩ + 2Λ + 5 Λ(1 + VT ) + T } T | {z t=1 √
E [LT (Algk )] ≤
⟨pt , ft ⟩ +
≤7
≤
T X t=1
Λ(1+VT )
√ 23ΛT ⟨q, ft ⟩ + min 10 ΛT , + 4 + 2Λ, k|1 − 2δ|
where the second inequality holds by Lemma 3.4, while the third because VT ≤ T and the maximizing 2Λ VT is VT = 4k249T 2 − 1. To get the final bound for the first argument of the minimum, notice (1−2δ) √ √ that Λ ≤ ΛT if Λ ≤ T , while if Λ > T , then the loss is trivially bounded by T < ΛT . The bound for the second argument follows since T/k|1−2δ| ≥ 1, with the convention of setting it to ∞ when δ = 1/2. We now prove Theorem 3.1 by removing the dependency of the previous analysis on q. Proof of Theorem 3.1. First, define S(x⋆ , r) = (1 − r)x⋆ + rK, for a generic x⋆ ∈ K. Now fix any 1 ⋆ t ∈ [T ] and let q be the uniform density over S(x⋆ , r), i.e. q(x) = Vol(S(x ⋆,r)) I {x ∈ S(x , r)}: the base measure in Algorithm 1 is thus in this case the Lebesgue measure. By definition of Minkowski sum, for any y ∈ S(x⋆ , r) there exists x ∈ K such that y = (1 − r)x⋆ + rx. By convexity of ft , ft (y) ≤ (1 − r)ft (x⋆ ) + rft (x) ≤ (1 − r)ft (x⋆ ) + r, since ft (x) ≤ 1. Rearranging then gives ft (y) − ft (x⋆ ) ≤ r for all y ∈ S(x⋆ , r). This addresses the (B) term in Equation (3). To address the (A) term, notice that q ≪ p1 and KL(q||p1 ) = d ln(1/r) = Λ, since: vol(K) vol(K) 1 KL(q||p1 ) = ln = ln = d ln . vol(S(x⋆ , r)) r rd vol(K) Plugging the equality in the bound from Lemma 3.7, then yields: E [LT (Algk )] −
T X t=1
p 25dT ln(1/r) ft (x⋆ ) ≤ min 12 dT ln(1/r), + 4 + rT, k|1 − 2δ|
and setting r = 1/T gives the claimed bound.
12
3.4
Prediction with Expert Advice
In the prediction with expert advice setting, Equation (3) and Lemma 3.7 imply a regret bound, with the proof relying on the fact that the convexity of domains and functions was only used when proving Theorem 3.1. We thus have to appropriately switch to the discrete setting: P the domain is d−1 d finite, where the experts can be seen as the d vertices of ∆ = {x ∈ R | xi ≥ 0 ∀ i, di=1 xi = 1}, the (d − 1)-dimensional simplex. Recall that its set of vertices is {e1 , . . . , ed }.2 Theorem 3.8. Consider the problem of prediction with expert advice with full feedback and k pairwise comparison probes, with the domain K = {e1 , . . . , ed }. Then, for an unknown noise parameter δ ≥ 0 and for any sequence of functions {ft }Tt=1 in [0, 1], when instantiated with p1 being the mass function of the uniform distribution over {e1 , . . . , ed } and Λ = ln d, Algorithm 1 has regret √ T ln d E [RegT (Algk )] ≤ O min . T ln d, k|1 − 2δ| Proof. For this result, the base measure of Algorithm 1 is the counting measure over {e1 , . . . , ed }, while p1 is the probability mass function of the uniform distribution over the same set. Consider the mass function q(x) = I {x = x⋆ }, thus corresponding to a Dirac on x⋆ , here the minimizing expert, so that Ex∼q [ft (x)] = ft (x⋆ ), and term (B) in Equation (3) is null. Clearly, q ≪ p1 . For term (A), we have: X q(x) KL(q||p1 ) = q(x) · ln = ln d. p1 (x) x∈{e1 ,...,ed }
Therefore, since we set Λ = ln d, Lemma 3.7 gives: E [LT (Algk )] −
T X t=1
√ 25T ln d ft (x ) ≤ min 12 T ln d, k|1 − 2δ|
⋆
+ 4,
which was to be shown.
4
Concluding Remarks
In this work, we analyze Online Convex Optimization (OCO) with a sublinear budget of pairwise probes. This generalizes Bhaskara et al. [2023b], which requires pairwise probes at every step, as well as Russo et al. [2024], which focuses on the stronger best-expert probes. Our main finding is that pairwise probes are as informative as best-expert probes and that our algorithms are robust to noise. In Theorem 3.1, we establish the following regret rates, which are tight in T, k and δ up to logarithmic factors in T , and for experts completely tight also in d: √ dT ln T E [RegT (Algk )] ≤ O min . dT ln T , k|1 − 2δ| Among the remaining open questions, one concerns understanding the benefit of probes in the special case of exp-concave functions, as opposed to general convex ones. Another relates to the trade-off between computational efficiency and improved regret: our main CEW algorithm requires computing an integral over a convex set, which is hard in general. It would therefore be interesting to develop efficient algorithms that achieve comparable guarantees. 2
We stress that we are using this notation for finite sets of points to match the notation used in the lower bounds in Appendix A.
13
Acknowledgments A.G. was supported in part by NSF awards CCF-2422926 and CCF-2608359. S.D.G. and S.L. were supported in part by the PNRR MUR project IR0000013-SoBigData.it project, by the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society) and by the FAIR (Future Artificial Intelligence Research) project PE0000013, funded by the NextGenerationEU program within the PNRR- PE-AI scheme (M4C2, investment 1.3, line on Artificial Intelligence). S.D.G. was also supported in part by the Institute for Complex Systems (Italian National Research Council).
References Arpit Agarwal, Rohan Ghuge, and Viswanath Nagarajan. Semi-bandit learning for monotone stochastic optimization. In FOCS, pages 1260–1274. IEEE, 2024. Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Francesco Emanuele Stradi. Multi-armed bandits with best-action queries. CoRR, abs/2605.08287, 2026. Hedyeh Beyhaghi and Linda Cai. Pandora’s problem with nonobligatory inspection: Optimal structure and a PTAS. In STOC, pages 803–816. ACM, 2023. Hedyeh Beyhaghi and Robert Kleinberg. Pandora’s problem with nonobligatory inspection. In EC, pages 131–132. ACM, 2019. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In ICML, Proceedings of Machine Learning Research, pages 822–831. PMLR, 2020. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Power of hints for online learning with movement costs. In AISTATS, Proceedings of Machine Learning Research, pages 2818–2826. PMLR, 2021a. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Logarithmic regret from sublinear hints. In NeurIPS, pages 28222–28232, 2021b. Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Bandit online linear optimization with hints and queries. In ICML, Proceedings of Machine Learning Research, pages 2313–2336. PMLR, 2023a. Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, and Kamesh Munagala. Online learning and bandits with queried hints. In ITCS, volume 251 of LIPIcs, pages 16:1–16:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023b. Sebastien Bubeck. Introduction to online optimization. In Lecture Notes Princeton University, 2011. Nicolò Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Mach. Learn., 66(2-3):321–352, 2007. Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention. In ICML, volume 80 of Proceedings of Machine Learning Research, pages 1067– 1075. PMLR, 2018.
14
Steven de Rooij, Tim van Erven, Peter D. Grünwald, and Wouter M. Koolen. Follow the leader if you can, hedge if you must. J. Mach. Learn. Res., 15(1):1281–1316, 2014. Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119–139, 1997. Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-order bound with excess losses. In COLT, volume 35 of JMLR Workshop and Conference Proceedings, pages 176–196. JMLR.org, 2014. Aditya Gangrade, Anil Kag, Ashok Cutkosky, and Venkatesh Saligrama. Online selective classification with limited feedback. In NeurIPS, pages 14529–14541, 2021. Robert D. Gordon. Values of mills’ ratio of area to bounding ordinate and of the normal probability integral for large values of the argument. The Annals of Mathematical Statistics, 12(3):364–366, 1941. Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In IPCO, volume 7801 of Lecture Notes in Computer Science, pages 205–216. Springer, 2013. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic probing: Submodular and XOS functions. In SODA, pages 1688–1702. SIAM, 2017. Elad Hazan. Introduction to online convex optimization. Found. Trends Optim., 2(3-4):157–325, 2016. Wouter M. Koolen and Tim van Erven. Second-order quantile methods for experts and combinatorial games. In COLT, volume 40 of JMLR Workshop and Conference Proceedings, pages 1155–1175. JMLR.org, 2015. Lihong Li, Michael L. Littman, Thomas J. Walsh, and Alexander L. Strehl. Knows what it knows: a framework for self-aware learning. Mach. Learn., 82(3):399–443, 2011. Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: Adanormalhedge. In COLT, volume 40 of JMLR Workshop and Conference Proceedings, pages 1286–1304. JMLR.org, 2015. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Beyond the WorstCase Analysis of Algorithms, pages 646–662. Cambridge University Press, 2020. Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In COLT, volume 125 of Proceedings of Machine Learning Research, pages 3030–3048. PMLR, 2020. Francesco Orabona. A modern introduction to online learning. CoRR, abs/1912.13213, 2019. Kalen Patton, Matteo Russo, and Sahil Singla. Submodular norms with applications to online facility location and stochastic probing. In APPROX/RANDOM, LIPIcs, pages 23:1–23:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In COLT, volume 30 of JMLR Workshop and Conference Proceedings, pages 993–1019. JMLR.org, 2013.
15
Matteo Russo, Andrea Celli, Riccardo Colini-Baldeschi, Federico Fusco, Daniel Haimovich, Dima Karamshuk, Stefano Leonardi, and Niek Tax. Online learning with sublinear best-action queries. In NeurIPS, 2024. Amin Sayedi, Morteza Zadimoghaddam, and Avrim Blum. Trading off mistakes and don’t-know predictions. In NIPS, pages 2092–2100. Curran Associates, Inc., 2010. Shai Shalev-Shwartz. Online learning and online convex optimization. Found. Trends Mach. Learn., 4(2):107–194, 2012. I. G. Shevtsova. On the absolute constants in the Berry-Esseen inequality and its structural and nonuniform improvements. Inform. Primen., 7(1):124–125, 2013. I. G. Shevtsova. On the absolute constants in the berry-esseen-type inequalities. Doklady Mathematics, 89(3):378–381, May 2014. Sahil Singla. The price of information in combinatorial optimization. In SODA, pages 2523–2532. SIAM, 2018. Jacob Steinhardt and Percy Liang. Adaptivity and optimism: An improved exponentiated gradient algorithm. In ICML, JMLR Workshop and Conference Proceedings, pages 1593–1601. JMLR.org, 2014. Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In COLT, volume 75 of Proceedings of Machine Learning Research, pages 1263–1291. PMLR, 2018. Martin L. Weitzman. Optimal search for the best alternative. Econometrica, 47(3):641–654, 1979. Chicheng Zhang and Kamalika Chaudhuri. The extended littlestone’s dimension for learning with mistakes and abstentions. In COLT, volume 49 of JMLR Workshop and Conference Proceedings, pages 1584–1616. JMLR.org, 2016.
16
Appendix A
Lower Bounds
In this appendix, we recall and (slightly) generalize a result of (see Russo et al. [2024, Section 3]), which shows that the regret rates from Theorem 3.1 are tight in T, k and δ, up to logarithmic factors in T . Their result can indeed be extended to work for linear (and, thus, general convex) functions. In particular, these lower bounds hold for a learner that has access to the more powerful global probes, i.e., it observes the global minimum of the function at that round, and the probe is noiseless. Before stating and proving the result, we stress that it shows complete tightness (also in d) of the rate in Theorem 3.8, since the proof below reduces to a lower bound on the problem of prediction with expert advice on the vertices of ∆d−1 . Theorem A.1. There exists a family of instances defined as linear functions bounded in [0, 1] over 2 3/2 T ln d d the (d − 1)-dimensional simplex ∆d−1 such that for k ≤ O and T ≥ O ln2 d :3 d (1) Any algorithm equipped with k global probes must suffer regret √ T ln d T ln d, ; E [RegT (Alg)] ≥ Ω min k (2) Any algorithm equipped with k pairwise comparison δ-noisy probes must suffer regret √ T ln d E [RegT (Alg)] ≥ Ω min T ln d, . k|1 − 2δ| Proof. The proof uses Yao’s Minimax principle, so we need to prove a hardness result for a deterministic algorithm against a randomized sequence of losses. The family of instances is described as the following linear function ft (x) = ft⊤ x defined on the (d − 1)-dimensional simplex ∆d−1 : each coordinate of the vector ft is 1 with probability ξ independently from all other coordinates and across rounds. P P Let us first observe that minx∈∆d−1 Tt=1 ft⊤ x ≤ minx∈{e1 ,...,ed } Tt=1 ft⊤ x since the vertices are P part of the simplex. In addition, since di=1 xi = 1 for all x ∈ ∆d−1 and the vertices {ei }di=1 form the canonical basis in Rd , we have ! T T X d d T X X X X ⊤ min ft x = min fti xi = min fti xi x∈∆d−1
t=1
x∈∆d−1
≥ min
x∈∆d−1
t=1 i=1 d X
x∈∆d−1
d
min
i=1
j=1
T X
! ftj
t=1
i=1
t=1
d
T X
xi = min j=1
t=1
ftj =
min
x∈{e1 ,...,ed }
T X
ft⊤ x.
t=1
P P Therefore, minx∈∆d−1 Tt=1 ft⊤ x = minx∈{e1 ,...,ed } Tt=1 ft⊤ x and we can restrict our attention to vertices {e1 , . . . , ed } of the simplex, as the minimal cumulative loss is P achieved at one of them. By the above for each x ∈ {e1 , . . . , ed }, it holds that Tt=1 ft⊤ x ∼ Bin(T, ξ), which hP construction, i T ⊤ means that E t=1 ft x = T ξ. Hence, the expected minimal loss among vertices is, by Lemma A.3 3
We require this to satisfy the sufficient condition in Equation (5) needed to apply Lemma A.3: in particular, 2 3/2 T ≥ 200d /ln d and k ≤ T ln d/700d suffices.
17
(below) with d sufficiently large (so that 2 ln d − 3 ln ln d ≥ ln d): " # T X 1p E min ft⊤ x ≤ T ξ − T ξ(1 − ξ) ln d 25 x∈{e1 ,...,ed } t=1
Furthermore, by linearity and independence of ft from the past, we have that for all xt ∈ ∆d−1 : " d # d d h i X X X E ft⊤ xt = E fti xti = E [fti ] xti = ξ · xti = ξ, i=1
i=1
i=1
P since di=1 xti = 1. Therefore the expected cumulative loss of the algorithm on the T −k non-probing rounds is exactly (T − k)ξ. We can now proceed with the proof of (1): the algorithm’s expected loss during probing rounds is kξ d because we need all vertices to have loss 1 for the minimum to be 1. Thus, the overall expected loss of the algorithm reads (T − k)ξ + kξ d = T ξ − kξ(1 − ξ d−1 ). The regret reads 1 p d−1 T ξ(1 − ξ) ln d − 25kξ(1 − ξ ) E [RegT (Alg)] ≥ 25 √ T ln d 1 min T ln d, , ≥ 5 · 103 k √ 1 T ln d 1 where we have chosen ξ = 12 for k ≤ 50 T ln d and ξ = 5·10 3 k 2 < 2 otherwise. We conclude with the proof of (2): at any time step, let us condition on the past randomness of the loss functions and let us assume that, given this conditioning, the deterministic learner chooses to probe: fix the two queried points. Since the current loss vector is independent of the past, its coordinates are still i.i.d. Bernoulli(ξ). Now, the pairwise probe outcome is a single noisy binary signal about the current loss vector and a Bernoulli(1/2) random bit handling tie breaking. Moreover, since the learner is allowed to know δ, if δ > 1/2 it may invert the probe outcome. Thus the effective probability that this binary signal is incorrect is min{δ, 1 − δ}. By Lemma A.2 applied with ρ = min{δ, 1 − δ}, even if the learner is allowed to play an arbitrary point of ∆d−1 after observing this signal, its expected loss on the probed round is at least 2 min{δ, 1 − δ} · ξ + (1 − 2 min{δ, 1 − δ}) · ξ 2 = ξ − |1 − 2δ|ξ(1 − ξ). Therefore, if the learner uses k ′ ≤ k probes, then E [LT (Alg)] ≥ (T − k ′ )ξ + k ′ (ξ − |1 − 2δ|ξ(1 − ξ)) ≥ T ξ − k|1 − 2δ|ξ(1 − ξ). Consequently, E [RegT (Alg)] ≥
1 p T ξ(1 − ξ) ln d − 25k|1 − 2δ|ξ(1 − ξ) . 25 √
We split into two cases: first, if |1 − 2δ| ≤ T ln d/50k, we choose ξ = 1/2, and then 1 1√ 25 3 √ E [RegT (Alg)] ≥ T ln d − k|1 − 2δ| ≥ T ln d. 25 2 4 200 18
Otherwise, |1 − 2δ| >
√
T ln d/50k, and we choose ξ ∈ (0, 1/2] such that
ξ(1 − ξ) =
T ln d 104 k 2 |1 − 2δ|2
,
which is feasible because the case assumption implies the right-hand side is at most 1/4. With this choice, T ln d 25T ln d T ln d 1 − 4 ≥ . E [RegT (Alg)] ≥ 25 100k|1 − 2δ| 10 k|1 − 2δ| 4 · 103 k|1 − 2δ| Combining the two cases yields E [RegT (Alg)] ≥ min
3 √ T ln d T ln d, 200 4 · 103 k|1 − 2δ|
,
with the convention that the second term is ∞ when δ = 1/2. As promised in the earlier proof, we are left to show that one noisy binary signal cannot reduce Bernoulli loss too much. We then also have to bound the expected minimum of i.i.d. binomials. We begin with the first claim: the uniform tie breaking convention after Definition 1.1 ensures that the probe outcome is only a noisy binary signal of the comparison and a Bernoulli(1/2) random bit which settles ties. Lemma A.2. Let A = (A1 , . . . , Ad ), where the coordinates are independent Bernoulli(ξ) random variables, and let U ∼ Bernoulli(1/2), independently of A. Let S ∈ {0, 1} be any binary random variable measurable with respect to (A, U ). Consider B ∈ {0, 1} to be a noisy version of S defined as S with probability 1 − ρ and 1 − S otherwise, where the random choice above is independent of (A, U ), and where ρ ∈ [0, 1/2]. Letting zB = f (B), for a function f : {0, 1} → ∆d−1 , it holds that: h i E A⊤ zB ≥ 2ρξ + (1 − 2ρ)ξ 2 . Proof. As for the proof of Theorem A.1, we have that since the function f maps to the simplex ∆d−1 , it suffices to prove the lower bound for f mapping to {ei }di=1 ⊆ ∆d−1 . Let f (0) = z0 and f (1) = z1 , for z0 , z1 ∈ {ei }di=1 . We want to lower bound the following: h i h i E A⊤ zB = E I {B = 0} A⊤ z0 + I {B = 1} A⊤ z1 h i = (1 − ρ)E I {S = 0} A⊤ z0 + I {S = 1} A⊤ z1 h i + ρE I {S = 0} A⊤ z1 + I {S = 1} A⊤ z0 (4) Disregarding the convex combination, summing the two expectations above gives E A⊤ (z0 + z1 ) = 2ξ, since A is a Bernoulli vector and z0 , z1 ∈ {ei }di=1 . This means that: h i h i E I {S = 0} A⊤ z1 + I {S = 1} A⊤ z0 = 2ξ − E I {S = 0} A⊤ z0 + I {S = 1} A⊤ z1 . ⊤ z + I {S = 1} A⊤ z Letting ζ = E I {S = 0} A and plugging the above in Equation (4) we get: 0 1 E A⊤ zB = (1 − ρ)ζ + ρ(2ξ − ζ) = 2ρξ + ζ(1 − 2ρ).4 To prove the claim, it thus suffices to prove ζ ≥ ξ2. 4
On the event that the coordinates corresponding to z0 and z1 are both equal to 1, the quantity inside the expectation defining ζ equals 1 regardless of whether S = 0 or S = 1. Thus the argument is insensitive to how ties are broken; it only uses that S is a binary random variable measurable with respect to (A, U ).
19
The first case is z0 = z1 , and the lower bound follows simply because ζ = E A⊤ z0 = ξ ≥ ξ 2 . Now suppose that z0 ̸= z1 : the event {A⊤ z0 = 1} ∩ {A⊤ z1 = 1} has probability ξ 2 , since A is a vector of independent Bernoulli variables and the event happens if and only if the entries in A corresponding to the two non-null entries in z0 and z1 are non-null. Therefore, h i ζ = E I {S = 0} A⊤ z0 + I {S = 1} A⊤ z1 h n o i ≥ E I {A⊤ z0 = 1} ∩ {A⊤ z1 = 1} I {S = 0} A⊤ z0 + I {S = 1} A⊤ z1 h i = P A⊤ z0 = 1 ∧ A⊤ z1 = 1 = ξ 2 , as desired. We return to bounding the expected minimum of i.i.d. binomials from above. The following result is arguably folklore, but in the absence of a convenient source we provide a proof for completeness. Lemma A.3. Let d ≥ 2 be an integer, let ξ ∈ (0, 1) and T ∈ N, and let X1 , . . . , Xd be i.i.d. Bin(T, ξ). Define σ 2 = V [X1 ] = T ξ(1 − ξ),
µ = E [X1 ] = T ξ, Let
ud =
√
2 ln d − 3 ln ln d ,
ψ(s) = P [X1 ≤ µ − s]
(s ≥ 0).
sd = σ u d .
Assume the following: 0.4690 ln d p ≤ √ . 8 πd T ξ(1 − ξ) Then
E
min Xi
1≤i≤d
√ ≤ T ξ − sd 1 − d−1/(8 π) .
(5)
(6)
In particular, since d ≥ 2, we also have the weaker bound: √ 1p E min Xi ≤ T ξ − T ξ(1 − ξ) 2 ln d − 3 ln ln d . 1≤i≤d 25 Proof. Let us first define M = max (µ − Xi ) ≥ 0, 1≤i≤d
so that then mini Xi = µ − M , and hence E min Xi = µ − E [M ] . 1≤i≤d
(7)
The proof proceeds in steps: Step 1. We give a general lower bound on E [M ] in terms of ψ: for any s ≥ 0, by independence, P [M < s] = P [µ − Xi < s ∀i] =
d Y i=1
20
P [µ − Xi < s] = (1 − ψ(s))d .
Therefore P [M ≥ s] = 1 − (1 − ψ(s))d .
(8)
P [M ≥ t] dt, we obtain for any s ≥ 0, Z s Z s P [M ≥ s] dt = s P [M ≥ s] = s 1 − (1 − ψ(s))d . P [M ≥ t] dt ≥ E [M ] ≥
(9)
Using E [M ] =
R∞ 0
0
0
Combining Equations (7) and (9) gives, for any s ≥ 0, E min Xi ≤ µ − s 1 − (1 − ψ(s))d .
(10)
1≤i≤d
Step P 2. Next, we lower-bound ψ(sd ) via Berry–Esseen and a Mills-ratio PTbound: let us expand T X1 = j=1 Bj where Bj ∼ Bern(ξ) i.i.d.. Let Yj = Bj − ξ, so that ST = j=1 Yj = X1 − µ. By the classical Berry–Esseen inequality with the upper bound C0 < 0.4690 for i.i.d. summands with finite third moment [Shevtsova, 2013, 2014], one has E |Y1 |3 ST 1 2 sup P ≤ x − Φ(x) ≤ 0.4690 · (11) ·√ , 3/2 σ (E Y1 ) T x∈R where Φ is the standard normal CDF. For centered Bernoulli variables, E Y12 = ξ(1 − ξ) and E |Y1 |3 = ξ(1 − ξ)3 + (1 − ξ)ξ 3 = ξ(1 − ξ) ξ 2 + (1 − ξ)2 ≤ ξ(1 − ξ). p Hence E |Y1 |3 /(E Y12 )3/2 ≤ 1/ ξ(1 − ξ), and Equation (11) yields ST 0.4690 sup P ≤ x − Φ(x) ≤ p . σ T ξ(1 − ξ) x∈R Also notice that
(12)
ST ψ(sd ) = P [X1 ≤ µ − sd ] = P ≤ −ud , σ
since sd = σud by definition. By Equation (12) we then have: 0.4690 ψ(sd ) ≥ Φ(−ud ) − p . T ξ(1 − ξ)
(13)
We next lower-bound Φ(−ud ). To do this, we use the Mills-ratio lower bound (see Gordon [1941]): for all u > 0, 1 u 2 e−u /2 . (14) Φ(−u) ≥ √ · 2 2π 1 + u ud 1 Since d ≥ 2, we have u2d = 2 ln d−3 ln ln d > 1, so ud ≥ 1. Therefore 1+u2d ≤ 2u2d , hence 1+u 2 ≥ 2u , d d
and Equation (14) gives 1 1 −u2 /2 Φ(−ud ) ≥ √ · e d . 2π 2ud Moreover, 2
e−ud /2 = e−(2 ln d−3 ln ln d)/2 =
21
(ln d)3/2 , d
(15)
and also u2d ≤ 2 ln d implies ud ≤
√
2 ln d, i.e. u1d ≥ √21ln d . Plugging these into Equation (15),
1 1 (ln d)3/2 1 ln d Φ(−ud ) ≥ √ · · √ · = √ . d 4 πd 2π 2 2 ln d Insert this into Equation (13) and use the assumption in Equation (5) to obtain ψ(sd ) ≥
ln d ln d ln d √ − √ = √ . 4 πd 8 πd 8 πd
(16)
Step 3. We apply Equation (10) with s = sd . Using (1 − x)d ≤ e−dx for x ∈ [0, 1], we get 1 − (1 − ψ(sd ))d ≥ 1 − e−dψ(sd ) . With Equation (16), dψ(sd ) ≥ 8ln√dπ , hence 1−e
−dψ(sd )
√ ln d ≥ 1 − exp − √ = 1 − d−1/(8 π) . 8 π
Substituting into Equation (10) yields √ E min Xi ≤ µ − sd 1 − d−1/(8 π) , 1≤i≤d
which is exactly Equation (6).
B
A Strawman Algorithm for Experts: a Uniform and a Hedge Probe
In this appendix, we focus on the case of experts. We show how a uniform probe together with a Hedge probe (Algorithm 2) can yield non-trivial regret rates in the noiseless case, albeit losing an additional factor d. This algorithm is a simple adaptation of Hedge [Freund and Schapire, 1997] (subsequently denoted as Alg0 ), which, during probing rounds Q, probes one expert uniformly at random and one expert according to the Hedge distribution pt at round t ∈ Q. We set the learning p ln d/T , k/dT +k . rate to η = max Before stating the theorem, we first recall that, in prediction with expert advice, instances are described by linear functions ft (x) = ft⊤ x, for some vector ft , where x ∈ {e1 , . . . , ed } is one of the vertices of the (d − 1)-dimensional simplex ∆d−1 , i.e., K = {e1 , . . . , ed }: coordinate i of vector ft therefore represents the loss of expert ei . Theorem B.1. Consider the problem of prediction with expert advice with full feedback and k pairwise comparison probes, with domain K = {e1 , . . . , ed }. Then, for any sequence of functions {ft }Tt=1 in [0, 1], Algorithm 2, denoted as Algk , guarantees regret √ T d ln d E [RegT (Algk )] ≤ O min T ln d, . k To prove the theorem, we state a useful lemma from Russo et al. [2024], which bounds the regret of the probeless version Alg0 of Algk ; it directly follows from Lemma 2.1 in Russo et al. [2024] shifting losses, denoting x⋆t = arg minx∈{ei }d ft (x): i=1
22
Algorithm 2: Uniform Probe Hedge Input: Sequence of gradient vectors ft , probe budget k ≤ T Sample k outof T rounds uniformly at random and denote this random set by Q q ln d k Set η = max T , dT +k Initialize w1 (x) = 1 for all x ∈ {e1 , . . . , ed } for t ∈ {1, . . . , T } do P t (x) Let Wt = x∈{e1 ,...,ed } wt (x) and pt (x) = wW t if t ∈ Q then Probe y1 ∼ pt and y2 ∼ Unif({e1 , . . . , ed }) Play point yt⋆ = arg min{ft⊤ y1 , ft⊤ y2 } else Select x ∼ pt Observe ft⊤ x ∀ x ∈ {e1 , . . . , ed } Update wt+1 (x) = wt (x) · exp −ηft⊤ x ∀ x ∈ {e1 , . . . , ed }
Lemma B.2. For the problem of prediction with expert advice with full feedback and domain K = {e1 , . . . , ed }, it holds that the expected regret of Alg0 with η < 1 is bounded above as T
E [RegT (Alg0 )] ≤
ln d η X ⊤ ⋆ + ft (x − x⋆t ). η(1 − η) 1 − η
(17)
t=1
Proof of Theorem B.1. First, we relate the regret of Algk to that of Alg0 . To this end, observe that, since Algk is provided with full feedback, then, the distribution pt Hedge keeps over experts is not affected by earlier probes or earlier decisions taken by the algorithm. Let zt denote the point/expert played by the algorithm in (probing or non-probing) round t. During non-probing rounds t ∈ Q = {1, . . . , T } \ Q, the expected loss Algk suffers is h i X pt (x) · ft⊤ x. E ft⊤ zt | t ∈ Q = x∈{e1 ,...,ed }
Moreover, in rounds t ∈ Q, Algk probes the expert of minimum loss with probability 1/d. In the event that the expert of minimum loss is not probed, we have that, in expectation, the algorithm Algk suffers at most the loss Alg0 (Hedge) would have suffered. Hence, the expected instantaneous loss of Algk at round t ∈ Q is h i X 1 f ⊤ x⋆ ⊤ E ft zt | t ∈ Q ≤ 1 − pt (x) · ft⊤ x + t t . d d x∈{e1 ,...,ed }
23
Summing over all t, by linearity of expectation, we have that the expected loss of the algorithm is: # " T T T h i X h i X X ⊤ ⊤ E ft zt · I t ∈ Q + E ft⊤ zt · I {t ∈ Q} E [LT (Algk )] = E ft zt = t=1
t=1
=
T X
t=1
T h i h i X E ft⊤ zt | t ∈ Q · P t ∈ Q + E ft⊤ zt | t ∈ Q · P [t ∈ Q]
t=1
≤
1−
t=1
k T
X T
+ =
k 1− dT
X
pt (x) · ft⊤ x
t=1 x∈{e1 ,...,ed } T kX
T
t=1
1− 1 d
X
pt (x) · ft⊤ x +
x∈{e1 ,...,ed }
ft⊤ x⋆t d
T
E [LT (Alg0 )] +
k X ⊤ ⋆ ft xt . dT t=1
Combining the above with Equation (17), we have T k k X ⊤ ⋆ E [RegT (Algk )] ≤ 1 − E [RegT (Alg0 )] − ft (x − x⋆t ) dT dT t=1 T ln d η k X ⊤ ⋆ k + − ft (x − x⋆t ) ≤ 1− dT η(1 − η) 1 − η dT t=1 √ 2T d ln d ≤ min 4 T ln d, , k q PT ln d k ⋆ ⊤ ⋆ by assuming T ≥ 4 ln d and choosing η = max t=1 ft (x − xt ) ≤ T . If T , dT +k , since T < 4 ln d, the regret guarantee is satisfied since η = dTk+k and the regret is bounded by T .
24