Adaptive Selective Sampling for Online Prediction with Experts
Authors: Rui M. Castro
Fredrik Hellström
Tim van Erven
Venue: NeurIPS 2023 poster (2023)
Keywords: Online learning
prediction with experts
selective sampling
active learning
TL;DR: Always guarantees the minimax regret, but adaptively queries (much) fewer labels when possible.

Abstract: We consider online prediction of a binary sequence with expert advice. For this setting, we devise label-efficient forecasting algorithms, which use a selective sampling scheme that enables collecting much fewer labels than standard procedures. For the general case without a perfect expert, we prove best-of-both-worlds guarantees, demonstrating that the proposed forecasting algorithm always queries sufficiently many labels in the worst case to obtain optimal regret guarantees, while simultaneously querying much fewer labels in more benign settings. Specifically, for a scenario where one expert is strictly better than the others in expectation, we show that the label complexity of the label-efficient forecaster is roughly upper-bounded by the square root of the number of rounds. Finally, we present numerical experiments empirically showing that the normalized regret of the label-efficient forecaster can asymptotically match known minimax rates for pool-based active learning, suggesting it can optimally adapt to benign settings.

Adaptive Selective Sampling for Online Prediction with Experts
Rui M. Castro
Fredrik Hellström University College London
Eindhoven University of Technology, Eindhoven Artificial Intelligence Systems Institute (EAISI) rmcastro@tue.nt nl
f. hellstrommucl. ac uk
Tim van Erven University of Amsterdam tin@timvanerven.u ml
Abstract
We consider online prediction of a binary sequence with expert advice. For this setting, we devise label-efficient forecasting algorithms, which sampling scheme that enables collecting much fewer labels than standard proce- dures. For the general case without perfect expert, we prove best-of-bott worh-worlds guarantees, demonstrating that the proposed forecasting algorithm always queries sufficiently many labels in the worst case to obtain optimal regret guarantees, while simultaneously querying much fewer labels in more benign settings. Specifically, for scenario where one expert is strictly better than the others in expectation, we show that the label complexity of the label-efficient forecaster is roughly upper- bounded by the square root the number of rounds. Finally, we present numerical experiments empirically showing that the normalized regret of the label-efficient forecaster can asymptotically match known minimax rates for pool-based active learning, suggesting it optimally adapt to benign settings.
selective
Introduction
This paper considers online prediction with expert advice in settings where collecting feedback might be costly or undesirable. the classical framework sequence prediction with expert advice, forecasting algorithm aims to sequentially predict stream of labels the basis of predictions issued by a number of experts (see, for instance, [1, 2, 3] and references therein). Typically, the forecaster receives the correct label after making prediction, and uses that feedback to update its prediction strategy. There are, however, situations where collecting labels costly and potentially unnecessary. In the context of online prediction, this naturally leads to the notion of selective sampling strategies, also called label-efficient prediction [4, 5, 6. 7. 8, 9]. In this line of work, there is natural tension between performance (in terms of regret bounds) and label complexity, i.c., the number of labels collected. For a worst-case scenario, the optimal label-efficient strategy amounts to "flipping a coin" decide whether or not to collect feedback, irrespective of past actions and performance [5]. Indeed, in the worst case, the number of labels that one has to collect is linear in the number of rounds for any algorithm [10]. This is a rather pessimistic perspective, and can miss the opportunity reduce label complexity when prediction is easy. With this in mind, the adaptive selective sampling algorithms we develop follow naturally from simple design principle: optimize the label collection probability any time while preserving worst-case regret guarantees. This principled perspective leads to general way to devise simple but rather powerful algorithms. These are endowed with optimal worst-case
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

performance guarantees. while allowing the forecaster to naturally adapt to benign scenarios and collect much fewer labels than standard (non-selective sampling) algorithms.
From a statistical perspective, the scenario above is closely related to the paradigm of active learning [11, 12, 13, 14, 15, 16]. For instance, in pool-based active learning, the learner has access to large pool of unlabeled examples, and can sequentially request labels from selected examples. This extra flexibility, when used wisely, can enable learning good prediction rule with much fewer labeled examples than what is needed in a passive learning setting, where labeled examples are uniformly sampled from the pool in an unguided way [17. 14, 15, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]. Our work is partly motivated by such active learning frameworks, with the aim of devising a simple and adaptive methodology that does not rely on intricate modeling assumptions.
The main contributions of this paper are novel label-efficient exponentially weighted forecasting algorithms, which optimally decide whether not to collect feedhack. The proposed approach confirms, in a sound way, the intuition that collecting labels is more beneficial whenever there is a lack of consensus among the (weighted) experts. The proposed algorithms are designed to ensure that, in adversarial settings, they retain the known worst-case regret guarantees for full-information forecasters (i.e., forecasters that collect all labels) while providing enough flexibility attain low label complexity in benign scenarios. To characterize the label complexity of the label-efficient forecaster, we focus on a scenario where the expected loss difference between the best expert and all other experts for all n rounds is lower-bounded by A. and show that the label complexity is roughly vn. A? ignoring logarithmic factors. This shows that the label-efficient forecaster achieves the "best of both worlds": it smoothly interpolates between the worst case, where no method can have optimal regret with less than O(n) queries, and the benign, stochastic case, where it is sufficient to make O (n) queries. Finally, to further examine the performance of the label-efficient forecaster, we conduct simulation study. We find that the performance of the label-efficient forecaster is comparable to its full-information counterpart, while collecting significantly fewer labels. Intriguingly, for a threshold prediction setting studied in [14], the numerical results indicate that the label-efficient forecaster optimally adapts to the underlying prediction problem, so that its normalized regret displays the same asymptotic behavior as known minimax rates for active learning.
Before formally introducing our setting, we discuss additional related work. Selective sampling for online learning was studied by [4, 5, 28), with a focus on probabilistic threshold functions and pargin-based sampling strategies. Similarly, [8] consider kernel-based linear classifiers, and base their sampling procedure on the estimated margin of the classifier. For the same setting as we consider, [29, 30] propose selective sampling approach based the maximum (unweighted) prediction disagreement among the experts, and numerically demonstrate its merits. Finally, results in a similar spirit to ours have recently been established in different settings. Namely, for strongly convex loss, [9] devised an algorithm for selective sampling with expert advice, which provably retains worst-case regret guarantees, where the sampling strategy is based on the variance of the forecaster's 's prediction. [31] study a setting with shifting hidden domains, and establish a tradeoff between regret and label complexity in terms of properties of these domains. For setting where the hypothesis class has bounded VC dimension and the data satisfies a Tsybakov noise condition, [32] devise a sampling strategy, with bounds on the regret and label complexity, based on a notion of disagreement where hypotheses are discarded based on their discrepancy relative to the empirical risk minimizer.
2 Setting
Throughout, we focus on a binary prediction task with the zero-one loss as performance metric. We refer to Yt as the outcome time E [n] == [l...., n). No assumptions are made on this sequence, which can potentially be created in an adversarial way. To aid in the prediction task, the forecaster has access to the predictions of N experts. The prediction of the forecaster at time can only be function of the expert predictions (up to time t) and the observed outcomes up to time t - 1. Furthermore, the algorithm can make use of internal randomization.
Formally, let J&, E {0, 1}. with i E [N] = (I...., N} and & E [n), denote the advice of the experts. At every time L E [m)] the forecasting algorithm must: (i) output a prediction ÿr of yı: (ii) decide whether or not to observe yt. Specifically, for each round L E [n]:
The environment chooses the outcome yt and the expert advice ( Only the expert advice is revealed to the forecaster.
2

---

The forecaster outputs (possibly randomized) prediction yr, based on all of the information that has observed so far.
The forecaster decides whether not to have y, revealed. We let Ze be the indicator of that decision, where Z, = if y/+ is revealed and Z = O otherwise.
A loss É ye) == 1 {&e * ye is incurred by the forecaster and a loss Ea == E(fr,,, y1) is incurred by expert regardless of the value of Zμ.
Our goal is to devise forecaster that observes as few labels as possible, while achieving low regret with respect to any specific expert. Regret with respect to the best expert time is defined
Rn == In min Li, iE(N]
where I, :t= E(ee, Mr) and Li, == -i= ((f,,; 3/)- Note that the regret R,, is, in general, random quantity. In this work, we focus mainly on the expected regret E [t.]
Clearly, when no restrictions are imposed on the number of labels collected, the optimal approach would be to always observe the outcomes (i.e., take Z₁ = 1 for all t E [n])). This is optimal in a worst-case sense, but there situations where fewer labels. The main goal of this paper is the development and analysis of methods that are able to capitalize such situations, while still being endowed with optimal worst-case guarantees.
can predict as efficiently while collecting much
2.1 Exponentially weighted forecasters
All proposed algorithms in this paper are variations of exponentially weighted forecasters [2]. For each time /. E in]. such algorithms assign weight wi,, 2 0 to the ith expert. The forecast prediction at time and decision whether to observe the outcome or not are randomized, and based exclusively on the expert weights and the expert predictions at that time. Therefore, are conditionally independent Bernoulli random variables given Pt and q.. Here, Pt and q depend on the past only via the weights {Wir-11 (e(()])je(() and the current expert predictions {ff., (v The exact specifications of pt and ge depend on the setting and assumptions under consideration.
~ Ber(p:) and Ze ~ Ber(g) )
After a prediction has been made, the weights for all experts are updated using the exponential weights update based on the importance-weighted losses K,,Z,//p Specifically,
W/2t Wi,t-1 4,
where 1 0 is the learning rate. To ensure that the definition in (1) is sound for any d. 2 0, we set Wi,t = Wi q: = O. Finally, we define the weighted average of experts predicting label at time as
Σ whec
A
(2)
Σ Wi,t-1
This quantity plays a crucial role in our sampling strategy. We will use the name exponentially weighted forecaster liberally to refer to any forecaster for which is function of A Throughout, we assume that the weights for all forecasters are uniformly initialized as wio0 1/N for i [M].
3 Regret bounds with perfect expert
In this section, we consider very optimistic scenario where one expert is perfect, in the sense that it does not make any mistakes. The results and derivation for this setting are didactic, and pave the way for more general scenarios where this assumption is dropped. We say that the ith expert is perfect f,, = 0 for all t E [n]. The existence of such an expert implics that min Li,- = 0. Therefore, the regret of forecaster is simply the number of errors it makes, that is, R. L,. In such a scenario, any reasonable algorithm should immediately discard experts as soon as they make single mistake. For exponentially weighted forecaster, this is equivalent setting 7 co. Due to the uniform weight initialization, the scaled weight vector N (Wi.t..... WN,)) is thus binary, and indicates which experts agree with all the observed outcomes up time
First, consider a scenario where the forecaster always collects feedback, that is, gt for all & [m]. A natural forecasting strategy at time is to follow the majority, that is, to predict according to the
3

---

majority of the experts that have not made mistake so far. When the forecaster predicts the wrong label, this implies that at least half of the experts still under consideration are not perfect. Since the number of experts under consideration is at least halved for each mistake the forecaster incurs, this strategy guaranteed make most logg N mistakes. Therefore, we have
R Ln S logz N.
(3)
Clearly, this implies the following bound on the expected cumulative loss, and thus the regret:
_ == E[L,] S log2 N
(4)
Here, the superscript (N) explicitly denotes the dependence on the number of experts. This bound tight when the minority is always right and nearly equal in size the majority.
natural question ask is if there exists an algorithm that achieves the expected cumulative loss bound (4) while not necessarily collecting all labels. This is, in fact, possible. The most naive approach is to not collect label if all experts still under consideration agree on their prediction, as in that case, they must all be correct due to the existence of perfect expert. However, more refined strategy that can collect fewer labels is possible, leading to the following theorem.
Theorem 1. Consider the exponentially weighted follow-the-
forecaster with n) co. Specifically, let Pt- = 1 {Ai, 2 1/2}. so that Ūt- = 1 {Ai, 2 1/23. Furthermore, let
A1, E {0,1),
qt
otherwise.
logg min AI. 1- AI.1)
For this forecaster, we have
I S log, N
Recall that AI, is simply the proportion of experts still under consideration that predict = 1. It is insightful to look at the expression for qt, as it somewhat intuitive. The bigger the disagreement between the experts' predictions, the higher the probability that we collect label. Conversely, when A1, approaches either or 1, qi quickly approaches zero, meaning we rarely collect a label. Theorem tells us that, remarkably, we can achieve the same worst-case bound as the full-information forecaster while sometimes collecting much less feedback. The proof of this result, in Appendix A, uses clean induction argument that constructively gives rise to the expression for qr- This principled way of reasoning identifies, in a sense, the best way to assess disagreement between experts: the specified qe is the lowest possible sampling probability that preserves worst-case regret guarantees.
A slightly better regret bound is possible by using variation of follow the majority, called the boosted majority of leaders. For this algorithm, the upper bound is endowed with a matching lower bound (including constant factors). In Appendix B, we devise label-efficient version of the boosted majority of leaders, retaining the same worst-case regret bound as its full-information counterpart.
4 General regret bounds without a perfect expert
In this section, we drop the assumption of the existence of a perfect expert. It is therefore no longer sensible to use an infinite learning rate v,, since this would discard very good experts based on their first observed error. We consider the general exponentially weighted forecaster described in Section 2.1, now simply with pt A1,--
For the scenario where q: for all a classical regret bound is well-known (see, for instance, [3, Thm 2.2)). Specifically, for the general exponentially weighted forecaster, with pt = A1,,, 9: 1, and uniform weight initialization, we have
m In N
R2 T [R.]] E Ln min T4j, xE[N]
(5)
17
8
In Theorem 2 below, we prove stronger version of (5) that allows for an adaptive label-collection procedure. As before, we focus on the expected regret, R. E R. As done Section 3 for the case of a perfect expert, we identify an expression for gr, which is not necessarily identically 1, but still ensures the bound in (5) valid. To state our main result, we need the following definition, which is guaranteed to be sound by Lemma 1.

---

0.5
08
0.8
0.1
0.6
0U6
(z, ()
0.1
9 (1, n))
0.4
0.3
0
0.2
0.4
0.6
11.
-10-2
(a)
(b)
Figure I: The function q (ar, v)) for various values of Panel (b) is zoomed version of panel (a).
Definition 1. For x E [0, and > 0, define
(x,,)) inf q (0, 1] + 9 In x. xe 1/9) mee-//)
7
S
(6)
8"
2 In x + (1 - x)e n
7
1 x
8
In the following theorem, we present the label-efficient version of (5). Theorem 2. Consider exponentially forecaster with pt A1, and
q: 2 q" (A1,..)) o.
For this forecaster, we have
In
n7
Rn = IE Ln
min Lin VE(N]
I
The proof, which is deferred to Appendix C, is similar to that used for Theorem 1, but with key modifications account for the lack of a perfect expert. In particular, we need account for the finite. importance- -eerrhhhee- weighted weight updates, and carefully select of accordingly. While the proof allows for non-uniform weight initializations,
focus on the uniform case, as this enables to optimally tune the learning rate. The result for general weight initializations is given in Appendix C.
Theorem 2 shows that the proposed label-efficient forecaster satisfies the same expected regret bound as the exponentially weighted forecaster with := 1. While the expression for q (æ, 1)) in (6) is somewhat opaque, the underlying motivation is constructive, and it arises naturally in the proof of the theorem. In fact, of is the smallest possible label-collection probability ensuring the regret bound (7). One may wonder if of is well defined, as it is the infimum of that may be empty. However, as shown in the following lemma, this set always contains the point 1, ensuring that S 1.
Lemma 1. For all 1) > and E [0, 1), we have
1 q (0.1): x 2 In 1 (1-x+ ze
The proof is presented in Appendix D, and is essentially a consequence of Hoeffding's inequality. While q" (x,7) .7) does not admit an analytic solution, its behavior as a function of x, depicted in Figure 1, rather intuitive. Since 77 = /8(In.N)/n minimizes the regret bound (7), we are primarily interested in small values of n7. When the learning rate 1) is not too large, the behavior of qf can be interpreted as follows: the larger the (weighted) disagreement of the experts is, the closer the value of A1, is to the point 1/2. In this case, of will be close to 1, and we collect label with high probability. When A1, is close to or 1, the (weighted) experts essentially agree, so the probability of collecting label will be small. For large learning rates, the behavior of 9r appears bit strange, but note that for 77 2 8, the regret bound is vacuous. Thus, for this case, q" (z. m) = 0 for all x E [0, 1].
The regret guarantee in Theorem 2 is valid provided one uses any choice 2 q. The following lemma provides both an asymptotic characterization of q;' as 1) - Ô, as well as a simple upper bound that can be used for both analytical purposes and practical implementations.
5

---

Lemma 2. For any E [0, 1]. we have
lim (2, = 4x(1 x)
4-0
Furthermore, for any 1j > 0 and x E [0.
q (x, n) S min(4x(1 - x)) + 1//,1)
The proof of this result is somewhat technical and tedious, and deferred to Appendix E. In the remainder of this paper, we will use this upper bound extensively.
5 Label complexity
We now examine the label complexity, defined as S, := Σr= Z, [10, Thm. 13], it is shown that there exists setting for which the expected regret of forecaster that collects m labels is lower-bounded by en cn/In(N - 11/m for some constant Hence, in the worst case, the number of collected labels needs to be linear in n in order to achieve an expected regret that scales at most as n.. However, since ot can be less than 1, it is clear that the label-efficient exponentially weighted forecaster from Theorem can collect fewer than n labels more benign settings. To this end, consider a scenario with unique best expert, which at each round is separated from the rest in terms of its expected loss. To state the condition precisely, we need to define E, = E Fi-1l as the expectation time t conditional on all possible randomness up time t - 1, that is, for )=........ With this, we assume that there is a unique expert i" E [N] such that, for all i o 8" and & [n).
Ft = o Zz, Vj J1.j...., [N.j) (y.j)-
E, - (- >>>0
almost surely.
The parameter A characterizes the difficulty of the given learning problem. If A is large, the best expert significantly outperforms the others, and is thus easily discernible, whereas if A is small, the best expert harder identify. In particular, if the vectors (yr,, fi,t.. SN.,) are independent and identically distributed over rounds f E [m²) A is just the difference in expected loss between the best and the second- best expert in single round, which is common measure of difficulty for stochastic bandits [33, Thm. 2.1]. This difficulty measure has also been used in the context of prediction with expert advice [34]. Similar stochastic assumptions are standard in (batch) active learning, and highly relevant in practical settings (see [14, 15, 18, 21, 27] and references therein). Strietly speaking, our result holds under a more general assumption where the best expert emerges after a time r* instead of being apparent from the first round. This means that the best expert is even allowed to perform the worst for some rounds, as long as performs well in sufficiently many other rounds. While we state and prove the result under this more general condition in Appendix F, we present the simpler assumption here for clarity.
We now state our main result for the label complexity.
Theorem 3. Consider the label-efficient exponentially weighted forecaster from Theorem 2 with qe = min(4A1,
A1,1) + n/3,, 1) and any r > O. Suppose that there exists a single best expert i" such that, for all o i and all [n].
EEi Le 2 A >
almost surely.
Then, for any 4, the expected label complexity is at most
50
Wn
B[S,
In
+ 37m + 1.
(9)
A
Proof sketch. Initially, the sampling probability is large, but as we collect more labels, it will become detectable that one of the experts better than the others. As this happens, 9r will tend to decrease until it (nearly) reaches its minimum value n/3. We therefore divide the forecasting process into time S and > r. With a suitable choice of R 1/(rA²) (up to logarithmic factors), we can guarantee that the sampling probability is at most ye S 4n/33 3 for all > 7 with sufficiently high probability. This is shown by controlling the deviations of the cumulative importance- weighted loss differences \ = Ej-((, (4. 4:- (/// for i + i" from their expected values by using an anytime version of Freedman's 's inequality. With this, we simply upper bound the label complexity for the first r rounds by r, and over the remaining rounds, the expected number of collected labels is roughly 7 - T) S 1yn. This leads to a total expected label complexity of 1/ 1/m)2?) + 1yn, up to logarithmic factors. The full proof is deferred to Appendix F.

---

As mentioned earlier, the learning rate optimizing the regret bound (7) is (/s///////))) For this particular choice, the label complexity in (9) is roughly vn A2 to constants and logarithmic factors. We have thus established that the label-efficient forecaster achieves the best of both worlds: it queries sufficiently many labels in the worst case to obtain optimal regret guarantees, while simultaneously querying much fewer labels in more benign settings. the label complexity dependence of 1/ 1/ on A is less benign than the dependence of the regret bound from, e.g., [34, Thm. 11], which is 1/A. The underlying reason for this is that, while the two are similar, the label complexity is not directly comparable to the regret. In particular, the label complexity has much higher variance.
interesting to note that
The bound of Theorem 3 relies on setting the sampling probability to be the upper bound on q² from Lemma 2. This bound is clearly loose when qi is approximately zero, and one may wonder the label complexity of the algorithm would be radically smaller when using a forecaster for which 2 instead. With the choice = /8 In(N)/n, which optimizes the bound in (7), it seems unlikely that the label complexity will substantially change, as numerical experiments suggest that the label complexity attained with set as 9t or the corresponding upper bound from (8) appear to be within constant factor. That being said, for larger values of 1), the impact of using the upper bound in (8) is likely much more dramatic.
6 Numerical experiments
To further assess the behavior of the label-efficient forecaster from Theorem 2, we consider classical active learning scenario in a batch setting. for which there are known minimax rates for the risk under both active and passive learning paradigms. We will set the sampling probability to be
qt mi,(441,, A1.)) + n/3,
Let D,, ((x,,,))) be an ordered sequence of independent and identically distributed pairs of random variables with joint distribution D. The first entry of (X,, Y.) represents a feature, and the second entry is the corresponding label. The goal is to predict the label Y; E {0. 1} based on the feature X,- Specifically, we want to identify a map (ar, D₂)) ++ 9n (ar, D2)) ) E {0, 1} such that, for a pair (X, D that is drawn independently from Dn, we have small (zero-one loss) expected risk
Risk(ā.) := P(2. YY.
Concretely, we consider the following scenario, inspired by the results in [14]. Let the features X; be uniformly distributed in [0, 1]. and Y. E (0, 1} be such that P(Y; 1|X; = x) = ((x). Specifically, let TO E [0, 1] such that ((x) 2 1/2 when x 2 and ((x) S 1/2 otherwise. Furthermore, assume
that for all [0, 1), ((x) satisfies
crr - -all & (c())) - 1/2 s C|. -po=~oll-1 -
for some e, C > and x > 1. If To is known, the optimal classifier is simply g²(x) = 1 (a 2 m) The minimum achievable excess risk when learning On from D,, in this type of problems has been studied in, e.g., [14, 35). For this setting, it is known that
inf sup Rūsk(ā.) Risk(g") Xn T0E
as n - 0o. However, rather than the classical supervised learning setting above, we can instead consider active learning procedures. Specifically, consider sequential learner that can generate feature-queries X and sample a corresponding label Y/. such that P(Y 1|X; 2) ((x). This is often referred to as pool-based active learning. At time t. the learner can choose x as function of the past ((X), y according to a (possibly random) sampling strategy A.,. This extra flexibility allows the learner to carefully select informative examples to guide the learning process. Similarly to the passive learning setting, the ultimate goal is to identify prediction rule (a., D',) + 9 (a. D,,) E (0,1) 1}, where D', = ((X,, Y?)), In [14], is shown that for this active learning setting, the minimax rates are also known, and given by
inf sup (is)( Risk(g") x x
0 A.. E00
7

---

Full information Label efficient
information
Label efficient
130
150
[[R]]
B
50
50
00
3
10
(a)
2
(b)
1.5
6,000
6,000
S.
4J000
B[S]
4.000
2,000
2,000
1 -10
-104
(c) 2
(d) K = 1.5
Figure 2: Numerical results for expected regret and label complexity when n = 50000 and 225. Panels (a) and (b) depict the expected regret E
function of for respectively. Panels (c) and (d) depict the expected label complexity of the label-efficient forecaster, E[S.). a function of for from 500 independent realizations of the process and the shaded areas indicate the corresponding pointwise 95% confidence intervals.
2 and 1.5
and 1.5 respectively. The expectations were estimated
This shows that there potentially massive gains for active learning, particularly when x is close to A natural question whether similar conclusions hold for streaming active learning. In this setting, instead of selecting which example X to query, the learner observes the features (X1...., Xn) sequentially, and decides at each time / whether or not should query the corresponding label. This is analogous the online prediction setting discussed in this paper.
We now study this setting numerically. For the simulations, we use the specific choice
1 ((x) +2+ sign(r ro)(= Tol k-1
to generate sequences (Y,,.... Y.), based on sequence of features (X1, X,) sampled from the uniform distribution on [0, 1]. Furthermore, we consider the class of N experts such that
i i-1 fx= = X,
N N-1
with E [N] and t E [n].
6.1 Expected regret and label complexity
In the simulations, we set To 1/2 and N = [vn] 1[[v]] even). This choice enforces that N is odd, ensuring the optimal classifier is one of the experts. Throughout, we set r = / 8 (u(N)/r which minimizes the regret bound (7). First, we investigate the expected regret relative to the optimal prediction rule for the label-efficient exponentially weighted forecaster with qe given by (8), and compare with the corresponding regret for the full- full-information forecaster that collects all labels. Specifically, the regret time of forecaster that predicts {Ý,) given by
E R. Bie(Ý, Y.) E(g" (X.).
8

---

10-1
10
E R
B[R
10-2
10
Full information
Full in information
Label efficient
Label efficient
10-3
10
10"
10
10
10'
10a
[[S]
[[S]]
(
R =
(b) K = 1.5
Figure 3: Numerical results for the normalized regret as function of the expected label complexity when 50000 and N 225. The straight dotted lines displayed for comparison, and have slopes given by -k/ 1) (full information) and -k/(2k - 2) (label efficient). The expectations were estimated from 500 independent realizations of the process and the shaded areas indicate the corresponding pointwise 95% confidence intervals.
Furthermore, to study the potential reduction in the number of collected labels, we also evaluate the expected label complexity E[S,] of the lafel-efficient forecaster. approximate the expectations above, we use Monte-Carlo averaging with 500 independent realizations. Further experimental details are given Appendix G. The results are shown Figure We see that the regret is comparable for the full-information and label-efficient forecasters, albeit slightly higher for the latter. Since (X) YY = <2 the expected cumulative loss of the optimal classifier grows linearly with f. For instance, when Æ. = 2, we have Σ₁= (X,) = 3t/8. Hence, the regret relative to the best expert is much smaller than the pessimistic (i.e.. worst- case for adversarial environments) bound in (7). We also observe that the expected label complexity grows sub-linearly with as expected, and that E[S,] < n, demonstrating that a good prediction rule can be learned with relatively few labels. When x 1.5, the number of collected labels is significantly smaller than when K = 2. This is in line with the known minimax rates for active learning from [14]. To further examine this connection, we now turn to normalized regret.
(X.),
6.2 Normalized regret relative to the number samples
To relate the results of the label-efficient forecaster with known minimax rates for active learning, we investigate the expected regret normalized by the number of samples. Specifically, let
1 r(t) = - E[RA] 7 Σ Ele e(g)
For the full-information forecaster, we expect that r(t) = (22-() as - co. The same holds for the label-efficient forecaster, but in this case, the relation between r(t) and the expected number of collected labels E[S.] is more interesting. If the label-efficient forecaster performs optimally, we expect r()) > [[S.)-=/(2xx2)) as + co. To examine this, we plot r(I) against [[SS]] (which equals / for the full-information forecaster) logarithmic scales, so the expected asymptotic behavior corresponds to a linear decay with slopes given by -x/(2xr - 1) for the full-information forecaster and (x/(2x 2) for the label-efficient forecaster. This shown in Figure for K = 1.5 and k =
We see that the observed behavior is compatible with the known asymptotics for active learning, and similar results arise when considering different values of k. More importantly, it appears that the label-efficient forecaster optimally adapts to the underlying setting. This is remarkable, as the label-efficient forecaster does not rely on any domain knowledge. Indeed, has no knowledge of the statistical setting, and in particular, it has no knowledge of the parameter K, which encapsulates difficulty of the learning task. Note that our regret bounds are too loose to provide a theoretical justification of these observations via an online-to-bateh conversion, and that such theoretical analyses will only be fruitful when considering non-parametric classes of experts, for which the asymptotics of the excess risk are w11/ /n).

---

7 Discussion and outlook
In this paper, we presented a set of adaptive label-efficient algorithms. These follow from a very straightforward design principle, namely, identifying the smallest possible label collection probability de that ensures that known worst-case expected regret bound satisfied. This leads to simple, yet powerful, algorithms, endowed with best-of- woofofooohwweee woth-worlds guarantees. We conjecture that a similar approach can used for broader class of prediction tasks and losses than what is considered in this paper. For instance, the results we present can be straightforwardly extended to setting where the expert outputs take values in 00, 1], as long as the label sequence and forecaster prediction remain binary and take values in {0, 1). In fact, the same inductive approach can be used when y: E [0, 1] and one considers a general loss function. However, the resulting label collection probability will be significantly more complicated than that of Definition 1. An interesting side effect of our analysis is that it leads to an inductive proof of the regret bound for standard, full-information algorithms. Extending the label complexity result, and in particular connecting it with known minimax theory of active learning in statistical settings, remains an interesting avenue for future research. Finally, another intriguing direction is to extend our approach to the bandit setting. In the setting we consider in this paper, we observe the losses of all experts when observing a label. In contrast, in the bandit setting, only the loss of the selected arm would be observed for each round. This would necessitate the forecaster to incorporate more exploration in its strategy, and the analysis of a label-efficient version seems like it would be quite different from what is used in this paper, although some of the ideas may transfer.
Acknowledgements
The authors would like to thank Wojeiech Kotlowski, Gábor Lugosi, and Menno van Eersel for fruitful discussions that contributed to this work. The algorithmic ideas underlying this work were developed when R. Castro was research fellow the University of Wisconsin Madison. This work was partly done while F. Hellström was visiting the Eindhoven University of Technology and the University of Amsterdam supported by EURANDOM and STAR visitor grant, the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, and the Chalmers AI Research Center (CHAIR). T. van Erven was supported by the Netherlands Organization for Scientific Research (NWO), grant number VI. Vidi. 192.095.
References
[1] Volodimir G. Vovk. Aggregating strategies. In Proc. Workshop on Computational Learning Theory (COLT), Rochester, NY, USA, 1990.
[2] N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Information and Compu- tation, 108(2):212-261, 1994.
[3] N. Cesa-Bianche and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[4] David Helmbold and Sandra Panizza. Some label efficient learning results. In Proc. Conference on Computational Learning Theory (COLT), Nashville, TN, USA, July 1997.
[5] N. Cesa-Bianchi, A. Conconi, and C. Gentile. Learning probabilistic linear-threshold classifiers via selective sampling. In Proc. Conference on Learning Theory (COLT), Washington, DC, USA, Aug. 2003.
[6] Bhuvesh Kumar, Jacob D Abernethy, and Venkatesh Saligrama. Activehedge: Hedge meets active learning. In Proc. International Conference on Machine Learning (ICML), Edinburgh, Scotland, June 2012.
[7] Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. The Journal of Machine Learning Research, 13(1):2655-266 2012.
[8] Francesco Orabona and Nicold Cesa-Bianchi: Better algorithms for selective sampling. In Proc. International Conference Machine Learning (ICML), Bellevue, WA, USA, June 2.11.
10

---

[9] Dirk van der Hoeven, Nikita Zhivotovskiy, and Nicoló in online learning. In Proc. Conference on Neural Information Processing Systems (NeurIPS), New Orleans, LA, USA, Nov. 2022.
A regret-variance trade-ofi
[10] N. Resa-Bianchi, G. Lugosi, and G. Stoltz. Minimizing regret with label efficient prediction. IEEE Transactions on Information Theory, 51(6): 2005.
[11] D. J. C. Mackay, Information-based objective functions for active data selection. Neural Computation, 4:698-714, 1991.
[12] D. Cohn, Ghahramani, and M. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, pages 129-145, 1996.
[13] Y. Freund, H. S. Seung, H. Shamir, and N. Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28(2-)):133-18,, Aug. 1997.
[14] Rui M. Castro and Robert D. Nowak. Minimax bounds for active learning. Transactions on Information Theory, 54(5):2339-2533 Apr. 2008.
[15] N. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. In Proc. International Conference Machine Learning (ICML), Pittsburgh, PA, USA, June 2006.
[16] Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In Proc. International Conference on Machine Learning (ICML), Montreal, June 2009.
[17] R. Castro, R. Willett, and R. Nowak. Faster rates in regression via active learning. In Proc. Conference on Neural Information Processing Systems (NeurIPS), 2005. extended version available at http://homepages.com wisc..ebu/-rraatt/EEEE------
[18) S. Dasgupta, A. Kalai, and C. Monteleoni. Analysis of perceptron- based active learning. In Proc. Conference on Learning Theory (COLT), Bertinoro, Italy, June 2005.
[19] S. Dasgupta. Coarse sample complexity bounds for active learning. In Proc. Conference on Neural Information Processing (NeurIPS), Vancouver, Canada, Dec. 2005.
[20] M. F. Balcan, C. Berlind, A. Blum, Cohen, K. Patnaik, and L. Song. Active learning and best- response dynamies. In Proc. Conference Neural Information Processing Systems (NeurIPS), Montreal, Canada, Dec. 2014.
[21] P. Awasthi, M. Balcan, and P. M. Long. The power of localization for efficiently learning linear separators with noise. In Proc. Annual ACM Symposium on Theory Computing (STOC), New York, NY, USA, June 2014.
[22] A. Krause and C. Guestrin. Nonmyopic active learning of Gaussian processes: An exploration- exploitation approach. Proc. International Conference on Machine Learning (ICML), 2007.
[23] X. Zhu, Lafferty, and Ghahramani. Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. In Workshop The Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining, ICML, Washington, D.C., USA, Aug. 2003.
[24] L. Williams, W. Fisher, and S. Willsky. Performance guarantees for information theoretic active inference. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), San Juan, Puerto Rico, Mar. 2007.
[25] B. Chen, R. Castro, and A. Krause. Joint optimization and variable selection of highh-dimensional gaussian processes. In Proc. International Conference Machine Learning (ICML), Edinburgh, Scotland, July 2012.
[26] A. Epshteyn, A. Vogel, and G. DeJong. Active reinforcement learning. In Proc. International Conference on Machine Learning (ICML), Helsinki, Finland, July 2008
[27] Steve Hanneke. Theory of disagreement-based active learning. Foundations and Trends in Machine Learning, 7(2-3):1313300 2014.

---

[28] Nicoló Cesa-Bianchi Claudio Gentile, and Luca Zaniboni. Worst-case analysis of selective sampling for linear classification. Journal of Machine Learning Research, 7(44):1205-122) 1230, 2006.
[29] Peilin Zhao, Steven Hoi, and Jinfeng Zhuang. Active learning with expert advice. In Proc. Uncertainty in Artificial Intelligence (UA!), Bellevue, WA, USA, July 2013.
[30] Shuji Hao, Peiying Hu, Peilin Zhao, Steven C. H. Hoi, and Chunyan Miao. Online active learning with expert advice. ACM Trans. Knowl. Discov. Data, 12(5), June 2018.
[31] Yining Chen, Haipeng Luo, Tengyu Ma, and Chicheng Zhang. Active online learning with hidden shifting domains. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), San Diego, CA, USA, Aug. 2021.
[32] Boshuang Huang, Sudeep Salgia, and Qing Zhao. Disagreement-hagee active learning online settings. IEEE Transactions on Signal Processing, 70:1947-1958, Mar. 2022.
[33] Sébastien Bubeck and Nicolò Desa-Bianchi. Regret analysis of stochastic and nonstochastic multi- bandit problems. Foundations and Trends in Machine Learning, 5(1), 2012.
[34] Pierre Gaillard, Gilles Stoltz, and Tim van Erven. second-order bound with excess losses. In Proc. Conference on Learning Theory (COLT), Barcelona, Spain, June 2014.
[35] A. B. Tsybakov. On nonparametric estimation of density level sets. Annals of Statistics, 25:948-969, 1997.
[36] A.R. Karlin and Y. Peres. Game Theory, Alive. American Mathematical Society, 2017.
[37] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization, 2011.
[38] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proc. International Conference Machine Learning (ICML), Edinburgh, Scotland, UK, June 2012.
12

---

A Proof of Theorem 1
Theorem 1. Consider the exponentially weighted follow the majority forecaster with 1J = co.
Specifically, let Pt {A1,t 1/2), so that y 1 (A1, 2 1/23. Furthermore, let
0
A1, E {0,1}, otherwise.
g:
log, mint mln A1.
For this forecaster, we have
[(N) n S loga N.
Proof.
The main idea is to proceed by induction on For n = 1, the result holds trivially, regardless of the choice for q.- Now, suppose that - < log2 N for all values [n - 1], any sequence of observations and expert predictions, and any number of experts N. Based on this assumption, we
will derive bound for L Let k Σ fi be the number of experts that make mistake when I == 1. Note that < s N - 1, as there is one perfect expert. When < N/2, the majority vote ý
necessarily equal yı- Therefore,
n
L ((((01181))
Bie(úe w:l1 Σ
Ble vt))
1=2
2 B(e(in y6) ve) +1 Vn E((((e vz) 21
0]
(N-
+ (1 - 2.)
"2m
< log, N
(10)
where I(N) denotes the expected cumulative loss in rounds 2,..., n with N experts. Because the internal state of the algorithm only consists of list of experts that have made no errors so far, the task task over rounds starting with the experts that remain after
in rounds 2, .,....17 n equivalent
round 1. Therefore, we can apply the induction hypothesis to obtain (N- S logg (N- -k) S log, N and T.(X) <log2 N, which justifies the last inequality. We conclude that, when l N/2, the bound holds regardless of the choice of q1-
On the other hand, if N/2 < k < N induction hypothesis and an analogous reasoning as above, we find that
the forecaster incurs an error at time 1. Using the
T.(N 1 + q I kN
(1
(11-))]2 (N) < 1 - ạ loga(N k) + (1 q1) loga (N)
(11)
2:n
To ensure that the right-hand-sich of (11) satisfies the desired bound, we need to select şi such that
+ 1og,((N - k) (1 21) logg S log, N,
which can be written equivalently as
log, N - logg --))
41
we do not observe a label, we do not know the value k. All we know that, since y1 (0, 1}, we Dn N
have I E { N1,,N
fe. Therefore, to ensure the induction proof works, need
4 log, min (A1,1, 1
where Al, = 1
St,1 Note that the case k N cannot oceur as there is always perfect expert, but to ensure that the above definition is sound, define 91 0 when A1,1 E {0. D
N ENN
13

---

B Label-efficient boosted majority of leaders
Through a variation of follow the majority, slightly better regret bound than the one in Theorem 1 can be obtained, as well as a matching lower bound. As shown by [36, Proposition 18. 1.33. there exists an adversarial strategy for the environment such that any forecaster will incur at least [log, / Z [log, N| errors in expectation. A matching upper bound can be obtained, when N is power of two, by considering forecaster that incorporates randomness in its predictions. This is referred as the boosted majority of leaders. As shown in the following theorem, this procedure can be made label-efficient while ensuring the same expected regret bound.
Theorem 4. Consider an exponentially forecasser for which 1 30 and
Af 1/4
+ log, A1, loga (1 A1.))
if A1, $ 1/2
if A1, 3/4
if > 3/4
and
0
if A1, =0
1/ 1og, A1,1
if0 < A1, < 1/4 if A1, $3/4 i <1 if A
9t
1/ loga (1 A1,1)
For this forecaster, we have
I(N) S log, N.
induction argument find a choice of qe that guarantees the desired regret bound. We will proceed by analyzing different cases, depending the value of A A First, assume that A1,1 1/4. If y1 0, then
Proof. The proof technique is analogous that of Theorem 1:
T,(N) + q1 12m
F(N((1 A1,1)) + (1 ②1 T.(N)
Thus, taking 4ı 2 0 suffices. If 1/1 1, then
[,(N) 1 + q1 T (NA1.)
21) (1)...). T.
2mn
and, using the same reasoning as before, it suffices to take
a 2 log, A1,1
An analogous reasoning applies when AI, > 3/4, so that for this case, it suffices take
91 2 log,(1 (1 - AI,1)
Now, consider the case 1/4 < A1,1 5 1/2 If y1 = 0, then
İ(N) 1 log, A1, + q I [ (1,1-11,1)) + (1 - 91)
< 1 + log, A1, + log.(N(( (N(1 A1,1) + (1 ς1) log, N,
which implies that Similarly, if y1 1, we must have
1+ log4 AI,1
91 2 log,(1 (1 - A1,1)
log, A1,1 1.
01 2 log, A
Since we do not know yı before the decision, the only possibility is to take 91 1.
similar reasoning applies the case 1/2 < AI,1 < 3/4. Therefore, the above relations determine the expression for in the theorem, while enforcing the desired regret bound.
14

---

C Proof of Theorem 2
As mentioned after Theorem 2, analogous result holds for non-uniform weight initializations. We will state and prove this more general result below, from which Theorem 2 as stated in the main text follows special case.
Theorem 2 (with non-uniform weight initialization). Consider an exponentially weighted forecaster with mitial weight vector w.o (11,0- ................................ WN.0) such that LiE[N] W4,0 = L. Pt AL, and
at 2 q' (A1,t. of
For this forecaster, we have
In W1o
) ny
E L (w.,o)
S min [EIN)
Li,
(12)
"
where the superscript in Ln (w.,o) = explicit. In particular, for the choice of initial weights w4,0 1/N for all [N], we have
-Et= -==
Elge We) makes the dependence on the initial weights
In + n
Ra [[ E
min Lin [EIN
Proof. The proof strategy is similar to that used in Theorem 1. We begin by noting that at time t, the internal state of the label-efficient exponentially weighted forecaster is determined by the weight vector u (wi,t-1;-.- WN,t-1). Therefore, it suffices to focus on the requirements for q for an arbitrary weight vector. As in Theorem 1, we proceed by induction on n.
For n 1, the theorem statement is trivially true, as this algorithm coincides with the ordinary exponentially weighted forecaster (also, the right-hand-side of (12) is bounded from below by 1/2). Proceeding by induction in n, suppose (12) holds for I,... 1 outcomes. Let L _
(w..o) denote the
expected cumulative loss of the forecaster given (y1, (fr, 1 i.e., the true label and the expert predictions for time 1:
[(w.,0) E E[ (o)
U1, fr,
a/1
Then, we have
L (w.,o) ))_ a|1
21, (f. E(e(21,81))
+ E
Σ E(ir, vt)
M1 (i
+1.1 9
elDe, v1) 11=1,31 (fa 1N Σ
1=2
+ (1 (1-91) QI
v1) Z1 -, 0, 1/1 (
A1. + (1 1A1 +
[(w..)) I(w + (1 - 91 21) 1
(w0
In order to prove the desired result, is enough to show that
++ Here, we let T.,2. = Er= ba,t and let i' denote the arg min of the right-hand side. Now, using the induction hypothesis, we obtain
7, (w)..o n|1
<E min [E[N]
E1,1 Li,2.
In WiD0
)} mn -E|
[[(2e)
+ Lu
nn In we
)]
"
F f((m..)) n|1
S AL, + 2A1,) + (n 1)4
8
-In W1,1
W1,11
In w3,0
+ E
min SE[N]
Li,2mn - 41
+ (1 - 91)
1
77
(n
1)m
< A1,1 + (1 2A
+
8
+ E
[2.20 +
-Inwy.1
+ (1 91)
In wa
1
17
15

---

In the last step, we used the fact that since the upper bound holds for the minimum i, it holds for i' in particular. To ensure that the bound in the theorem holds, is thus sufficient to select A1,1 such that it satisfies
(2 (In Wyr - In wy lx,
111 + (1 2)1,))
8
Notice that, after the first observation, are back in situation similar to that time t 1, but possibly with a different weight vector. Specifically, for í E [N]
W1.00 9f11//1
W1
21=1 Wr.0e
is important at this point that wi,1 depends on the choice qi, so we cannot simply solve the above equation for yı. To proceed, it is easier to consider the two possible values of yı separately.
Case y1 0: Note that
W3,0e Seoge--eeffae -1
Wi,1
1 A1,1 + -A,,11
Therefore, suffices to have
②1 In (1 A1, + A n//) 7
A
(13)
r)
Case 1/1 = Similarly as above,
Wi.06 -F((F1,1-1)//
W1,1 A1,1 + (1 -11,)e--//u
Therefore, suffices to have
91 In (A1. + (1 A1,1)e n/9/
A1,1 +
(14)
As we do not know the values of y1 when computing qı, we must simultaneously satisfy (13) and (14). Nevertheless, these two conditions involve only v) and AI, Thus, we can identify the range of values that q can take, as a function of 1/ and AI,1 while still ensuring the desired regret bound. Specifically, we require that q 2 oi where
oi (A1, inf q (0,1): A1,
A1, + A1,e v/2) 7 9 In (1
"
9 In (A1.1 + (1 A1,)) 1/9 17
1- Ar,1
"
At this point, it might be unclear if of is well defined, namely, if there always exists q [0, 1] satisfying both (13) and (14). This is indeed the case, as shown in Lemma 1. By noting that B|Z [,1|1
o)] I ,,
(w.,o) we have completed the induction step.
As stated at the beginning of the proof, looking 41 suffices to determine the general requirements for qt, concluding the proof. The statement given in (7) follows from instantiating the general result with uniform initial weights.
Li
D Proof of Lemmal 1
Lemma 1. For all nj > 0 and x E [0, 1}, we have
I fefae
(0. (0.1)=
2 In (1 - x + xe- n/9) S
71 8
Proof. Let B ~ Ber(x), with x [0, 1). Note that EBe-1B) (1 x>) + -" Note also that, by [3, Lem. A.1] we have In Ele nB < - + n/2 /8. Putting these two facts together we conclude that
T In (1 - x + De 7 E x x + n/8 = n/8
"
Therefore, the point is always contained in Definition 1, concluding the proof.
16

---

E Proof of Lemma 2
Lemma 2. For any [0, 1}, we have
lin (2, n)) = 4x0(1 - x).
n-40
Furthermore, for any rj > 0 and z E [0.
q (2,n) n) S min(4x(11 - 2) + 1//3,11))
Proof. As already shown in Lemma 1, we know that (=(x: 17 - 1. Let > be arbitrary. Note that q" (2r, v)) needs to be solution in q of the following equation:
1/2
+ q 1ln(111111111111
De
n/9
(15)
i=)(1)
Note that
= 0, so we can extend the definition of g to 0 by continuity, Specifically,
g(n) { no + gl([1 - x + 2/9 17 > 0
0
if 0
We proceed by using Taylor expansion of g(n) around 0. Tedious, but straightforward computations yields
0 g(()) s(() = x (1
g = On
x + (1 - x)enta) (n( -x(1 x)
(x + (1 x: 2))7/1/2
and
1
xe 2/q
9" (5)
(-r + 37 -270). with
q²
x + ze ze-5/1
where & > 0. In conclusion,
7
n²
s(n) = g(0) +0((0) + 50
+ +g" gg"(()
2
6
1 (1- 11 + g5 (5) q
n²
(
where & E [0, n]. At this point we can examine the structure of the solution of (15) when 17 - 0. Note that 9" (zI,7) necessarily satisfies
n g(n) 9r (z. 1) r01 x)²² + n
8
implying that q=(x, 17) > 4x(1 - x) as + 0. proving the first statement in the lemma.
For the second statement in the lemma, one needs to more carefully control the error term (E). We begin by noting that 7 E 20. This implies that -T + +3 2 x(1 x) (this can be checked by algebraic manipulation ). Therefore, (x, 17) S where q is the solution of
1 xx(1 x) 7
2 qa x(1 x 17 n
q
6
8
This is simple quadratic equation in yielding the solution
q 2=111 z) + y (2x x))== 20 x)n-
Although the above expression is valid upper bound q" (xx n). it is not very convenient one. A more convenient upper bound can be obtained by noting that
2x(1 x) + v (2x(11 - x))² + 50 (1- =x)m S 4x(1 - x)) + 1/3
4
(2x(1 - x))² + 4
3 5 x)y S (2x(1 x) + n/3)²
3 r1 x)n 3 -1 x) 7
Thus, have q 4x(1 - x) + n/3, concluding the proof.
It suffices to check that the solutions in of - 37 272 < x. if they exist, satisfy E [0,
17

---

Proof of Theorem 3
In the proof of Theorem we will require the following anytime version of Freedman's 's inequality: Lemma Let XI,...;X, be martingale difference sequence with respect to some filtration Fi C. .... Fn and with [x) I for all almost surely. Let E = B(3]1, Then, for any 1/e and n
4,
PP [
Σ X3 2 max {2v Ei ln(16),, (01111),bln(/ bln(1/0)} s In(n)ō. 1=1
proof of this result for the special case that J, oX1, X²) can be found [37, Lemma 3], which is an extended version of [38]. Their proof goes through unchanged for general filtrations.
We are now ready to prove Theorem 3. As aforementioned, we will prove the result under more general condition than given the theorem statement. Specifically, instead of assuming that the best expert in expectation is apparent from the first round. we only require the best expert emerge after a time T² This condition is given in a precise form in (17). Clearly, the assumption stated in the main text implies that the condition in (17) holds with 7" =.
Theorem 3 (with the best expert emerging after a time T*). Consider the label-efficient exponentially
weighted forecaster from Theorem with = min(4A1,(1 - A1,,) + n/3, 1) and any 1 > Define
48 (1(1/22)
In 1
(16)
n
Suppose that there exists single best expert i and time T S such that, for all i i it,
E.l lir
A>0
almost surely for & T".
(17)
Then, for any n 2 4, the expected label complexity is at most
50
Inn
B[S,] S In
+ 3mm +
7
Proof. Recall that the estimated losses are l, li, Zt. qt- Let A E) T ips denote the cumulative estimated loss relative to that of the best expert, and let Aqiin = min; Aj.
Our argument separates the analysis in two regimes: Regime 1, where t S т, and Regime 2, where t > т. The specific choice of 7 given above arises naturally later in the analysis. Regime 1, in simply upper-bound S, < т. It then remains to bound the number of collected labels in Regime 2. To this end, we need be chosen such that
which labels will be collected frequently, is expected to be relatively short,
q: S 4n for all t >T
(18)
with probability at least 1 - 61, where 81 E (0, 1] will be fixed later. Let E denote the event that (18) holds. It then follows that the expected number of labels collected in Regime 2 is at most
S - S,] = E Σ q.1 {&}
+ E
Σ 1=7+1
9e1 {
fm Pr(E) + Pr(E) s 3m + n81
1=++1
All together, arrive at the following bound the expected label complexity:
E[S.]
+ mm + nōj
(19)
It remains verify that the choice of r in (16) leads to d1 being sufficiently small. To this end, let
Σtt Wh--1
4 =
ΣN Wit-1
N
18

---

denote the weighted proportion of experts that agrees with the best expert at time t. Then
1 2 W
2 1+ Ne 1+Ne v
Σ Witt 1+ Lii e-
Note that AL. E (A141; - A4+1)- Consequently,
9t+1 44 +1 1)+1) + 7
4(1 - A7-1
4(1
4
+ /N
1 1 enAiin
3
The desired condition from (18) therefore satisfied if, for all i f
N
A
In
for all = T...., 1.
(20)
7
To study the evolution of Ai. we use a martingale argument. Consider any fixed i * i*, and define the martingale difference sequence
X. = -Ce,, BR, [l-, (L,, - ex-
TE k.+,)
qt
Without loss of generality, may assume that n S 3, because otherwise (19) holds trivially for any pair of and d1. Then ge 2 3/3, Xxl < 2/9c- qc E 6/17, and
E|x B (1= = E
Fr--1
S
3
qt
1f
Hence, by Lemma 3, we have
3t ln(1/62),
12
M Exllat lir,al max (4V 1
ln(1/62))
allal [n]
(21)
"
Using Assumption (17), it follows that
A カ max (AV 3t Im l11282))
12
In ln(1/62)) 17
for all t 2 r²
(22)
7
with probability least (In())62) for any 82 E (0, 1/e). By taking 82 min /N In n), 1/e) and applying the union bound, we can make (22) hold for all o i" simultaneously with probability least 1 5j. A sufficient condition for (22) imply (20) is then take
48 (1
In T
7A2
matching the definition in (16). We prove this claim Lemma 4 below. Note that our choice of n. then (19) still holds trivially, because S, < n. Evaluating (19) with the given choice of
and taking 8n = 7) (assuming rj < 1, since (19) holds trivially if 81 1), we arrive at the following
bound:
48 (11/2))
2
N
B[S.] <
+
4 3
mm + nd
7/A
48 IN 1n(1)//1)
2
N
+ $ rm
nōi
nA2
7
48 InNN In(n)/n)
2
N
In
3 np
mm +
7
17
50 (NI(()/)))
3mm
+
n
thus completing the proof.
19

---

Lemma 4. Assume that
3t
12
A 22 t2 max (4v
In (2)))
In
ln(1/52)3
for all S n
Then, with
48 481m(1/52)
N
In
n
nA
7
we have
N for all 1 -
N 2
In
Proof. We will consider the two possible outcomes the maximum separately. First, we consider the case where the first term is the maximum. Then, we need to find T such that for t 2 T.
N 2 0.
2 12 - 4V (n(1/22)
straightforward calculation shows that this is satisfied for
2
V (481n(1/62) + 441m((N/n) + 4 3A ln(1/2))
4n
Since (a b)2 < 2a² + 26 for a, b > 0, this is satisfied given the simpler condition
48 n
N
-
t 2
In(1 ln(1/52) +
In
A
Next, assume that the second term is the maximum. Then, have
12
A
(1
12
A
l1(1/82)
17
48 In(1 1
2
N
12
In
(
ln(1/2))
A
7
17
77
48 (1(1/82)
2
N
12
(1(6/2)
In
A
7
2
N
m
1
where used the assumption that 2 Thus, for this case, the desired condition holds with the specified т. Therefore, with the specified т, the desired statement holds for = T,..., n 1.
G Experimental details
In this section, we describe the simulation study in Section in detail. The full code, which can be executed in less than one hour on an MI processor, is provided in the supplementary material.
We consider sequential prediction problem with 50000 total rounds and N 225 experts. The number of experts is chosen to be higher than v and odd. Then, we repeat the following simulation for 500 independent runs. First, generate n independent features (X₂ heemj from the uniform distribution [0, 1]. Then, for each feature X,, we randomly generate a label Y,, where the probability P(Y; = 1|X; = x) = <(x), where
1 2 sign(r - 1/2)|x 11221= 1
<(x) Note that the optimal prediction of the label is simply (1: 1/2). We run simulations both for k 1.5 and 2.
20

---

We set the experts to be threshold classifiers, with thresholds uniformly spaced across [0, 1]. Specifi- cally, for all [N] and E [n].
Ju h==1 Xx N
In order to optimize the regret bound in (7), set 1 / /n)) For each time t [n], consider two different weight vectors: {wf corresponding to the passive, full-information forecaster, and (e(N) corresponding to the active, label-efficient forecaster. The weight for each expert for both forecasters is uniformly initialized as wr.0 = w/o0 = 1/N.
Then, for each timestep prediction the label 1 for each forecaster, given by pl for the full-information forecaster and p for the label-efficient forecaster, as
[n]. we proceed as follows. First, we compute the probability of
pf Af, EN Li E w
11=1 -1
P =
A
E W
where the expert predictions computed based on X,. Here, the weighted proportion of experts that predict the label 1 are given by Af, for the full-information forecaster and A for the label- efficient forecaster. On the basis of this, each forecaster issues prediction for the label, given by of ~ Ber(y;") for the full-information forecaster and ú ~ Ber(yς)) for the label-efficient one.
Finally, the weights for each forecaster updated follows. For the full-information forecaster, the weight assigned to each expert updated as
whe = whP-1 Wiiie
(23)
where l,, = 1 (Si, f Y.). In order to determine whether the label-efficient forecaster observes label or not, we compute qi min(4.4,e - A n/3, 1) and generate Ze ~ Ber(g)). Then, the weights of the label-efficient forecaster are updated
(24)
Hence, Z = 0, the weights of the label-efficient forecaster are not updated, since the label is not observed.
After all n rounds have been completed, we compute the regret the full-information forecaster R, and the label-efficient forecaster RA
R = Σ 1 CoP xY) - (Y)
RA
{36 A * Y. - tut Y.)
Here, for each & E [n]. the optimal prediction is given by yf = 1 (x, 2 1/2). Furthermore, we compute the label complexity S₂ as
S, = Σ 2,
The results of these simulations are presented in Figure 2 and
21


Reviews:
[{"review_id": "Jhw7zSJr3U", "reviewer": "Reviewer_1FCH", "summary": "This paper investigates the PEA problem in the context of online binary classification where the cost of obtaining labels for streaming data is high, necessitating selective label collection adaptively. To this end, the authors introduce a carefully designed label collection strategy based on the classical Hedge algorithm. The resultant label-efficient forecaster has a best-of-both-worlds theoretical guarantee. The authors further demonstrate that regret of their label-efficient forecaster asymptotically reaches the minimax rates of pool-based active learning.", "questions": "See Weaknesses above.", "limitations": "The paper should further clarify the method and theory part, see Weaknesses above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The paper is well-structured and easy to comprehend.\n* The theoretical analysis provided in the paper appears to be solid and sound.", "weaknesses": "* The primary conclusion of the paper, Theorem 3, relies on a core assumption that there exists a unique optimal expert whose expected loss in each round surpasses all other experts by a specific margin $\\Delta$. Is this assumption too strong? Are there real-world application scenarios that satisfy such an assumption? (To my knowledge, this assumption has only been used in the COLT'14 paper: A Second-order Bound with Excess Losses).\n\n* Does this specific PEA setting investigated in the paper relates to the bandit setting? Both are concerned with identifying the optimal expert (arm). How then do the setting and techniques used in this paper differ or relate to those in bandit scenarios? Does the problem studied in this paper present novel challenges in comparison to the bandit setting?\n\n\n* The paper states that the online prediction setting is similar to streaming active learning. If this is the case, should the numerical experiment compare the regret convergence rate of the proposed algorithm with that of the streaming active learning algorithm?\n\n\n* Some writing aspects could be improved:\n\n  * In line 227, the symbol $\\tilde l$ is undefined.\n  * In line 264, the regret bound (7) is termed \"pessimistic\" without explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and helpful comments.\n\n*Regarding the assumption in Theorem 3:*\n\nThe assumed setting is relatively benign, but it does include many practical i.i.d. settings, and the stated results do hold under a more general assumption (as detailed in Appendix F).\nPlease see the global response for more details, especially the point\nthat our algorithm still works when the assumption is violated.\n\n*Regarding the relation to the bandit setting:*\n\nThis is an interesting question.\nIn the setting considered in the paper, we observe the losses of *all* experts when observing a label. \nIn contrast, in the bandit setting, only the loss of the selected arm would be observed for each round.\nThis would necessitate the forecaster to incorporate more exploration in its strategy, and the analysis of a label-efficient version seems like it would be very different from what is used in this paper, although some of the ideas may transfer.\n\n*Regarding the comparison to active learning:*\n\nEssentially, streaming active learning can be seen as a special case of label-efficient online prediction, where the environment draws i.i.d. features and labels, and the expert predictions are determined by fixed functions of the features.\nNote that this is precisely the setting that we consider in the numerical experiments.\nThus, the comparison to batch active learning is a comparison between the following:\n\n1. minimax optimal batch active learning,\n\n2. streaming active learning based on our label-efficient algorithm for online learning.\n\nThe fact that these match asymptotically is an indication that, for the specific setting under consideration, the attainable performance with batch active learning and streaming active learning coincide asymptotically, and specifically, this is achieved by using our proposed label-efficient predictor for streaming active learning.\nHowever, as stated in the paper, this is an empirical observation which we did not establish theoretically. \n\n*Regarding aspects of the writing:*\n\nWe will rewrite Line 227 in terms of $\\ell_{i,j}/q_{j}$ (to avoid needing\nto introduce the short-hand $\\tilde \\ell$) and we will clarify that (7)\nis ‘‘pessimistic'' because it is a worst-case bound for adversarial environments."}, {"review_id": "HnjScRLkiC", "reviewer": "Reviewer_VgJf", "summary": "This paper proposes an interesting novel approach to prediction with expert advise. In the standard prediction with expert advise setup, the learner receives experts' predictions, commits to its own and then sees the true outcome as produces by the (possibly adversarial) nature. Suppose that obtaining the true outcome is costly; do we really need to do this all the time? Clearly, if all (or most) experts agreed on the same prediction, the value of the true outcome for adjusting our trust in them is negligible; in the standard weight-based algorithms with multiplicative update the contribution of this round will simply be eliminated by normalisation.\n\nThe paper takes an algorithm from Cesa-Bianchi and Lugosi (exponential weighting with fixed $\\eta$) and shows that its regret bound stands as it is if the true outcome is requested with certain probability.\n\nIt is then shown that the expectation of the number of outcomes actually requested is upper bounded by $3\\eta T + O(\\log\\log T)$, so for small $\\eta$ there is linear improvement in the number of requested outcomes. If $\\eta$ is chosen to minimise the regret bound using prior knowledge of $T$, we take $\\eta\\propto 1/\\sqrt{T}$ and thus the bound reduces to $O(\\sqrt{T})$. This results holds under some conditions on experts' behaviour  though and they seem restrictive.", "questions": "The authors chose to present the results in the probabilistic setup. Typically predicting $0$ or $1$ in a probabilistic setup is equivalent to predicting $\\gamma\\in [0,1]$ under a deterministic setup; the later seems more important to me (this is my judgement of course). Will the results of the paper stand?\n\nI think the final version would benefit from a better discussion of the $O(T)$ lower bound, which is mentioned but not discussed in detail.", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I think this is an interesting take on the well-known problem and should be published.", "weaknesses": "No obvious weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and helpful comments.\n\n*Regarding the restrictiveness of the conditions for the label complexity bound:*\n\nWhile the assumed setting in Theorem 3 is relatively benign, it includes many relevant settings, and the results hold under the more lenient assumption of cumulative separation after a certain time.\nPlease see Point 1 in the global response for more details.\n\n*Regarding extensions to predictions in $[0,1]$:*\n\nExtending our analysis to predictions in $[0,1]$ would be interesting, and we believe it may be possible to extend our approach.\nPlease see Point 2 in the global response for more details.\n\n*Regarding the label complexity lower bound:*\n\nWe will update the paper with further discussion of the lower bound.\nPlease see Point 3 in the global response for more details."}, {"review_id": "ZIzToptm5m", "reviewer": "Reviewer_G2NF", "summary": "The paper considers a binary prediction game on $0-1$ loss, it proposed efficient sampling scheme via an modification of the exponentiated weight forecaster, which selectively acquire labels $y_t$ based on $Ber(q_t)$, where the design of $q_t$ is correlated to the disagreement among experts’ predictions at each round for the exponentiated weight forecaster. \n\nUltimately, the proposed algorithms achieves the regret of the exponentiated weight forecaster $O(\\ln N \\sqrt{ n} )$ over time horizon $n$ and $N$ number of experts, the design labelling acquisition parameter $q_t$ resultant to a labelling complexity of $O( \\frac{\\sqrt{n}}{\\Delta^2} )$, where $0 < \\Delta \\le \\mathbb{E} [\\ell_{t,i} - \\ell_{t,i^{\\ast}}], \\forall t \\in [n], i \\neq i^{\\ast}$ represents the lower bound expected loss gap comparing to the optimal expert with index $i^{\\ast}$, which also signifies the difficulty of identifying the optimal experts.", "questions": "Appendix C: \nFrom line 437 to line 438, whether intermediate steps could be further elaborated. I am concerned about the proof, which seems primarily confused on the relationship of combining minimum values: $\\min_i (a_i + b_i)$ VS $\\min_i(a_i)+ \\min(b_i)$. \n\nMy understanding is that from the last equation line of line 437, we have \n$$ L_{n |1}^{w_{.,0} }  \\le \\frac{n \\eta }{ 8 }  \\underbrace{  - \\frac{\\eta}{8 } + A_{1,1} +  (1 - 2 A_{1,1})y_1  + \\mathbb{E} \\left[ \\min_{i} \\left( L_{i, n} + \\frac{\\ln w_{i,0}}{\\eta} + \\frac{q_1}{\\eta} ( \\ln w_{i,0} - \\ln w_{i,1} )  - \\ell_{i,1}  \\right)   \\right]}_{A} $$\n\nTo show the desired result claimed in the theorem, we aim to show \n$$ A \\le \\mathbb{E} \\left[ \\min_{i} \\left( L_{i,n} - \\frac{\\ln w_{i,0}}{\\eta} \\right) \\right] $$\n\nThat is to show \n$$  A_{1,1} +  (1 - 2 A_{1,1})y_1  + \\mathbb{E} \\left[ \\min_{i} \\left( L_{i, n} + \\frac{\\ln w_{i,0}}{\\eta} + \\frac{q_1}{\\eta} ( \\ln w_{i,0} - \\ln w_{i,1} )  - \\ell_{i,1}  \\right)   \\right]  \\le  \\frac{\\eta}{8 } + \\mathbb{E} \\left[ \\min_{i} \\left( L_{i,n} - \\frac{\\ln w_{i,0}}{\\eta} \\right) \\right] $$\n\nFrom the claim in line 438, it seems we need to show above inequality should hold even without expectation, that is:\n $$  A_{1,1} +  (1 - 2 A_{1,1})y_1  + \\min_{i} \\left( L_{i, n} + \\frac{\\ln w_{i,0}}{\\eta} + \\frac{q_1}{\\eta} ( \\ln w_{i,0} - \\ln w_{i,1} )  - \\ell_{i,1}  \\right) -  \\min_{i} \\left( L_{i,n} - \\frac{\\ln w_{i,0}}{\\eta} \\right)      \\le  \\frac{\\eta}{8 }  $$\n\nIt seems the paper used \n$$\\min_{i} \\left( L_{i, n} + \\frac{\\ln w_{i,0}}{\\eta} + \\frac{q_1}{\\eta} ( \\ln w_{i,0} - \\ln w_{i,1} )  - \\ell_{i,1}  \\right) -  \\min_{i} \\left( L_{i,n} - \\frac{\\ln w_{i,0}}{\\eta} \\right) \\le \\min_{i} \\left(  \\frac{q_1}{\\eta} ( \\ln w_{i,0} - \\ln w_{i,1} )  - \\ell_{i,1}  \\right) $$\nwhich doesn't seem to be true. These intermediate steps are just my personal guess. I wonder whether details to understand those two lines in the manuscript can be further explained.\n\n\n", "limitations": "yes", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and easy to follow. It first introduces the intuition of sampling parameter $q_t$ if there is a perfect expert, then extended to general case. The paper also provided an graphical illustration on the lower bound of $q_t$ which matches with expectation.\n\nThe result is novel comparing to previous result in two folds. (1) There is no assumption on how $y_t$ is generated. The proposed algorithm is able to attain the $O(\\ln N \\sqrt{n})$ regret without less labels. (2) In contrast to previous work on sampling by disagreement, the label complexity can be quantified as $O(\\frac{\\sqrt{n}}{ \\Delta^2})$. \n\n$q_t$ is easy to compute, numerical experiment with respect to time horizon $n$ shows the expected regret and expected number of labels which matches with theoretical results. Experiment with respect to number of label (number of weights update) shows labelling efficient algorithm proposed in the paper matches the minimax rate in active learning asymptotically.\n\n\n", "weaknesses": "It seems that the assumption $0 > \\Delta \\ge \\mathbb{E} [\\ell_{t,i} - \\ell_{t,i^{\\ast}}], \\forall t \\in [n], i \\neq i^{\\ast}$ is required only for bounding the labelling complexity, ( in order to track how $q_{t+1}$ evolves in line 493), without this assumption the regret still holds. \n\nI am a bit concern such assumption is very strong, it generally asks the best expert $i^{\\ast}$ is wining over every other expert at every round. In addition, the assumption is $\\ell_{t,i} \\in \\{ 0, 1\\}$, if we are at a specific iteration $t$ where $\\ell_{t,i^{\\ast}} = 1$, then what values  can $\\ell_{t,i}, \\forall i \\neq i^{\\ast}$ take in order to satisfy the condition for a strictly positive $\\Delta$? \n\nWhether labelling complexity can be bounded without this assumption?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and helpful comments.\n\n*Regarding the assumption that $\\Delta>0$:*\n\nPlease see Point 1 in the global response, where we also highlight the more general assumption in Appendix F.\nNote that, under the assumption stated in the main paper, it is allowed\nthat $\\ell_{i^*,t}=1$ with positive probability, as long as $E_{t}[\\ell_{i^*,t}]<1$.\nHowever, under the more general assumption in Appendix F, we even allow $E_t[\\ell_{i^*,t}]=1$ for some rounds, as long as the best expert performs well in sufficiently many other rounds.\nExtending the label complexity analysis to even more general settings is\ninteresting future work, but as mentioned in the paper, it is\nunavoidably linear in $n$ in the worst case (see also Point 3 in the global response).\n\n*Regarding line 437 to 438:*\n\nAs you correctly observe, there is a (minor) issue with the proof as\nstated. Thanks a lot for catching this! It can be fixed as follows:\n\nIn order to prove the desired result, it is enough to show that\n\n$$\\bar L_{n |1}^{w_{.,0} } \\leq \\mathbb{E}\\left[ \\min_{i\\in[N]} \\left( \\ell_{i,1} + L_{i,2:n} - \\frac{\\ln w_{i,0}}{\\eta}\\right) \\right] + \\frac{n \\eta}{8}  = \\mathbb{E}\\left[ \\left( \\ell_{i',1} + L_{i',2:n} - \\frac{\\ln w_{i',0}}{\\eta}\\right) \\right] + \\frac{n \\eta}{8} . $$\n\nHere, we let $i'$ denote the $\\mathrm{argmin}$ of the right-hand side.\nWhile we had separated out $\\ell_{i,1}$ in the submitted paper, this is not necessary.\nAs shown after line 437, we have\n\n$$ \\bar L_{n |1}^{w_{.,0} }  \\leq A_{1,1}+(1-2A_{1,1})y_1 +\\frac{(n-1)\\eta}{8} + \\mathbb{E}\\left[\\min_{i\\in[N]} \\left( L_{i,2:n}+q_1\\frac{-\\ln w_{i,1}}{\\eta} + (1-q_1)\\frac{-\\ln w_{i,0}}{\\eta}\\right)\\right] $$\n\n$$\\leq A_{1,1}+(1-2A_{1,1})y_1 +\\frac{(n-1)\\eta}{8} + \\mathbb{E}\\left[ \\left( L_{i',2:n}+q_1\\frac{-\\ln w_{i',1}}{\\eta} + (1-q_1)\\frac{-\\ln w_{i',0}}{\\eta}\\right)\\right] \\ .$$\n\nIn the last step, we used the fact that since the upper bound holds for the minimum $i$, it holds for $i'$ in particular.\nNow that everything has been recast in terms of $i'$, the rest of the argument follows as stated.\nTo ensure that the bound in the theorem holds, it is thus sufficient to select $A_{1,1}$ such that it satisfies\n\n$$A_{1,1}+(1-2A_{1,1})y_1+\\left(\\frac{q_1}{\\eta}\\left(\\ln w_{i',0}-\\ln w_{i',1}\\right)-\\ell_{i',1}\\right)\\leq \\frac{\\eta}{8}\\ ,$$\n\nafter which the proof continues as before.\nThank you for pointing this out!"}, {"review_id": "PMlscXLfln", "reviewer": "Reviewer_naDi", "summary": "This paper presents an adaptive label-efficient forecasting technique for online binary prediction with expert advice. The proposed approach implements a label querying probability that is a function of the observed scenario, rather than based on pessimistic conditions. This enables the method to adapt, i.e., have lower label complexity, to benign environments while remaining robust to adversarial ones, unlike prior approaches in this label-efficient forecasting. Sharp analyses of the regret and label complexity and results on synthetic scenarios are provided in support of the method.", "questions": "\n1. The authors mention that the same inductive approach can be used for general loss functions and $y_t \\in [0,1]$, but that the expression for the selective sampling probability would be really complicated. Do the authors conjecture that an efficiently-computable upper bound for the complicated function can be found as was done for the binary zero-one loss case?\n2. The authors mention active learning as a possible application in the introduction. Could this method (or its generalization) be applied to, e.g., a simple active learning scenario with a ResNet on CIFAR10?\n", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper is very well-written and organized.\n* The introduced algorithm is novel and intuitive. The regret and label complexity analyses of the approach seem sound.\n* The method remedies the shortcoming (lack of adaptivity) of prior label-efficient prediction approaches. This enables it to query fewer labels in benign scenarios while remaining robust to adversarial ones.\n* The authors present empirical evaluations that demonstrate the effectiveness of the method.\n", "weaknesses": "* The method only applies to binary prediction tasks with zero-one loss.\n* Additional details on prior work on label-efficient prediction would be helpful in contextualizing the benefit (adaptivity) of the proposed approach.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and helpful comments.\n\n*Regarding general losses and predictions:*\n\nAs you mention, applying the same approach to general losses would quickly lead to complications, but generalizing the analysis is an intriguing direction.\nPlease see Point 2 in the global response for more details.\n\n*Regarding prior work:*\n\nPlease see Point 3 in the global response. We will expand the discussion of related work in the paper along these lines.\n\n*Regarding active learning for e.g. CIFAR10:*\n\nThis is a potential application of our approach.\nGiven an ensemble of $N$ ResNets initialized with random weights, one could view them as experts and use the label-efficient forecaster to determine whether or not a given label should be observed, and used for training the ResNets.\nIn order for the approach to work off-the-shelf, one would need to consider a binary classification version of CIFAR10.\nExtending the applicability of our results and using them in this way is an intriguing direction."}]

Author rebuttal:
## Global response to all reviewers

We thank all reviewers for their careful reading and helpful comments.
We are happy that you consider the paper to be sound, novel, interesting, and well-written.

Below, we address three points that were raised by multiple reviewers:

*1. Regarding the assumption of a best expert with $\Delta>0$:*

The setting in Theorem 3, where there exists a single expert that is
best in expectation for all rounds, is satisfied for any static
stochastic environment with a unique minimizer, including many relevant
applications with i.i.d. data. The same assumption is standard in the
stochastic bandit setting, where it is nearly always assumed that there
exists a single best arm, and has also been used in the prediction with
expert advice setting. We therefore view it as relatively
uncontroversial. Moreover, note that our algorithm satisfies a
best-of-both-worlds result: it preserves regret guarantees, even if the $\Delta > 0$
assumption does not hold, but if the assumption does hold, the label complexity is much smaller than $n$. We further note that, as mentioned before the theorem statement, the same result holds under a more general assumption: the best expert does not need to surpass the others in each round.
Instead, it is sufficient that the normalized *cumulative* expected loss becomes separated by $\Delta$ sufficiently fast.
This is stated more precisely in Eq. (16) and (17) in Appendix F in the supplementary material.
Under the more general assumption, the ‘‘best'' expert is even allowed to be the worst for some rounds, as long as it performs well in sufficiently many other rounds.
Extending the label complexity analysis to even more general settings is interesting future work, but as mentioned in the paper, it is linear in $n$ in the worst case (Theorem 13 in [10], N. Cesa-Bianchi, G. Lugosi, and G. Stoltz: Minimizing regret with label efficient prediction).

*2. Regarding the extensions to general losses and predictions:*

While extending the results to losses and predictions in $[0,1]$ seems solvable by generalizing our approach, this will complicate the optimization problem in Eq. (13,14), leading to a more complicated (implicit) specification for $q_{t}$. 
It may be the case that an altered technique based on the same ideas would allow for efficiently handling more general losses and predictions.
As we have not fully established the details, this should be taken with a grain of salt, but it is an interesting avenue for future work.

*3. Regarding the worst-case label complexity:*

The label complexity being linear in $n$ in the worst case follows from Theorem 13 in [10] (N. Cesa-Bianchi, G. Lugosi, and G. Stoltz: Minimizing regret with label efficient prediction).
To clarify this point, we will alter the beginning of Section 5 as follows in the revised paper:

___

*We now examine the label complexity, defined as $S_{n}\equiv \sum_{t=1}^{n} Z_{t}$.
In [Thm. 13, 10], it is shown that there exists a setting for which the expected regret of a forecaster that collects $m$ labels is lower-bounded by $cn\sqrt{\ln(N-1)/m}$ for some constant $c$. Hence, in the worst case, the number of collected labels needs to be linear in $n$ in order to achieve an expected regret that scales at most as $\sqrt n$. However, since $q^{\*}_t$ can be less than $1$, it is clear that the label-efficient exponentially weighted forecaster from Theorem 2 can collect fewer than $n$ labels in more benign
settings. To this end, we consider a scenario with a unique best expert,
which at each round is separated from the rest in terms of its expected
loss.*

Meta-review: This work proposes label-efficient algorithms for binary prediction with expert advice. The algorithms employs a selective sampling scheme, and queries fewer labels in benign settings while having optimal worst-case regret guarantees. In the benign setting where an expert is strictly better than the rest, explicit label complexity is obtained. The paper is well-written and the proposed method is novel; while there were concerns about the assumption under which the explicit label complexity is obtained, there is a worst-case lower bound, and this work is the first to obtain a sublinear label complexity. I therefore recommend acceptance.
Decision: Accept (poster)