WorksComputer Science
Self-Directed Apple Tasting
Abstract
We study the classical apple-tasting setting, a partial feedback model in which the learner observes the true label only when it predicts . A combinatorial characterization for the rates of this problem in the online adversarial setting has been studied by Raman et al. (2024). We study the self-directed setting, in which the learner can adaptively choose the order of the points it predicts on. In the realizable setting, we establish a tetrachotomy on the expected minimax number of mistakes made by any learner. Depending on the VC dimension, the -centered star number, and the self-directed dimension, we show that the rates could possibly be , , , or . In the agnostic setting, the minimax regret is or , depending on the VC dimension.
Introduction
Imagine visiting a fruit vendor to buy apples: you pick one, taste it, and learn whether it is good; you then pick another, taste it, and so on. We call this self-directed online classification under apple-tasting feedback, an analogue of the model introduced by Helmbold et al. [ [19]. In this model, the learner observes the correct label only when it predicts 1 (i.e. eats the apple), in contrast to standard online learning, where the correct label is revealed after every prediction.
We believe that this self-directed formulation is arguably the natural way to model literal apple tasting: the defining feature of the problem is that the learner controls which point it exposes itself to risk on, and self-direction simply takes this control to its logical conclusion by letting the learner choose the point itself, rather than having it imposed by an adversary. Prior work on apple tasting [[23, 10]] instead studies the setting in which the point in each round is chosen by the environment or adversary, and the learner only controls its prediction. While this adversarial formulation is a natural starting point for worst-case analysis, it discards exactly the element of agency that makes apple tasting a distinctive feedback model to begin with — after all, no one is forced to buy a particular apple at the market.
A more practical instance of this problem can be seen in the hiring process at a company. They first review applications and then decide which candidates to interview. As interviewing is more informative but more resource-intensive than simply reading applications, the company might want to adaptively decide which candidates to interview in order to learn what features in applications are most desirable.
Formally, self-directed online classification with apple-tasting feedback is a repeated game between an adversary and a learner played over rounds. At the start of the game, the adversary provides a set of points. In round , the learner selects one of these points and makes a prediction . The adversary then assigns a label , unknown to the learner, and the learner incurs loss . If , the adversary reveals the true label ; otherwise, the learner receives no feedback. We allow both the learner and the adversary to use randomized strategies. In most cases, however, we show that deterministic strategies would give essentially the same results.
We study both the realizable and the agnostic settings in our paper. We adopt the perspective of Raman et al. [ [23] and identify the combinatorial dimensions that govern the minimax number of mistakes and regret4 respectively. Our main contributions are as follows:
The Vapnik-Chervonenkis (VC) Dimension [26] characterizes the minimax expected regret in the agnostic setting as .
On the other hand, VC dimension alone is not enough to characterize the realizable setting. There are easier regimes characterized by the -centered star number of [16], denoted , and the self-directed dimension of [11] denoted by .
Consequently, in the realizable setting, we obtain a tetrachotomy on the mistake bound. (i) when , ; (ii) when but ; (iii) when but ; (iv) when .
We additionally establish several auxiliary results.
We show that for any , there exists a concept class such that and the optimal number of mistakes made by any algorithm is .
In the realizable setting, if the adversary may choose labels adaptively, our upper and lower bounds on the mistake bound differ by a factor of . This gap vanishes when the adversary must instead commit to an unknown true concept before the game begins.
It is straightforward to find concept classes that fit in cases (i), (iii), and (iv) of our tetrachotomy. We show that case (ii), where and , is also nonempty by adapting a construction of Kuhlmann [ [20].
Finally, we prove a purely combinatorial identity that may be of independent interest. For any concept class , letting denote its union closure, we have .
Literature Review
Apple Tasting: Apple tasting is a partial feedback model. It is a special case of partial monitoring [3] and of sequential prediction with graph feedback [1]. Online learning with apple-tasting feedback was initially studied in Helmbold et al. [ [19], via randomized algorithms and an analysis of expected regret. Raman et al. [ [23] provide a combinatorial characterization for online apple tasting, via the Littlestone dimension in the agnostic case, and show an upper bound of on the expected regret. They provide a tighter combinatorial characterization using the effective width in the realizable case where they show that the minimax mistake bound exhibits a trichotomy: , , or . Our tetrachotomy (Theorem 4.1) is a self-directed counterpart of this result, where the rates are instead governed by the VC dimension, -centered star number, and the self-directed dimension.
Chase and Mehalel [ [10] study deterministic algorithms and show a gap between randomized and deterministic learners in the realizable case. This gap could also appear in our setting; all of our upper bounds in § 4.1 are achieved by deterministic learners, while our lower bounds in § 4.5 hold against randomized ones.
Self-Directed Learning: Self-directed learning was studied for special classes in Goldman and Sloan [ [14]. In more generality, Devulapalli and Hanneke [ [11] provide a dimension to characterize the mistake bound for self-directed learning. Our work considers self-directed learning with apple-tasting rather than full-information feedback. Ben-David et al. [ [4] and Kuhlmann [ [20] provide separations between the number of mistakes in self-directed learning and offline learning. We use the intersection-closed property of Kuhlmann [ [20]’s construction in Theorem 7.1.
The Star Number: Hanneke and Yang [ [17] introduced the star number to characterize the minimax label complexity in active learning under low noise regimes under the noise model of Tsybakov [ [25]. It has since appeared in several other roles: Wiener et al. [ [29] provide a version space compression scheme of size , and Hanneke [ [15] analyze its role in the sample complexity of empirical risk minimization (ERM). Bousquet et al. [ [5] study a related variant, the hollow star number, in connection with the Helly number and an optimal SVM bound. Hanneke [ [16] collects elementary observations about the star number, such as equivalence with the VC dimension of the version space class.
Our work uses the -centered star number, introduced by Hanneke [ [16], as one of the parameters to analyze mistake bounds for self-directed apple tasting. Intuitively, star number measures the worst-case deviation from a particular central concept. Apple tasting’s asymmetry makes the zero concept especially important. Using it as the center yields the -centered star number.
Prediction with Expert Advice: Prediction with expert advice [7, 28, 27] is a sequential framework for making predictions. A learner receives predictions from experts in each of rounds and must make few mistakes relative to the best-performing expert. Multiplicative weights gives a regret bound of . Tighter first- and second-order bounds were studied, such as the second-order bounds in Cesa-Bianchi et al. [ [8]. We specifically use the expert advice algorithm with an apple-tasting variant EXP4.AT of Raman et al. [ [23].
Other tools: Two results are used directly. We use the one-inclusion graph predictor of Haussler et al. [ [18], whose leave-one-out guarantee bounds the expected error of predicting an unseen point by given training points. We also use progress on the union-closed set conjecture, which guarantees that some point must be labeled 1 by a constant fraction of a union-closed concept class. See Proposition 1 and Bruhn and Schaudt [ [6] for a survey of the conjecture.
Formal Setup and Definitions
In this section, we formally present the setup and definitions used throughout the paper.
Let denote an arbitrary non-empty set, referred to as the instance space, and the label space. Let denote an arbitrary non-empty set of concepts , called the concept class.
Our framework, self-directed online learning under apple-tasting feedback, combines two existing models. As in the self-directed online learning model of Ben-David et al. [ [4], the learner chooses which point to query in each round. As in the apple-tasting model of Helmbold et al. [ [19], feedback is partial: the learner observes the true label when it predicts 1, and receives no feedback when it predicts 0.
Unlike in full-information settings, the adversary may benefit by presenting the learner with multiple copies of the same point. Conversely, the learner may benefit from labeling different copies of the same point differently. We therefore allow the learner to choose points from a multiset and use the notation to mean that every is also in .
Self-directed online learning under apple-tasting feedback setting
We describe the learning protocol. Given a non-empty concept class and a finite multiset , one round of self-directed online learning under apple-tasting feedback proceeds as follows.
The learner chooses some .
The learner predicts a label for .
If , the learner receives the true label from the environment. If , the learner receives no feedback.
Rounds proceed in this fashion until the learner has labeled every point in . For brevity we say the learner eats a point if they predict 1 on it.
Definitions
Because feedback is partial under apple tasting, the histories available to the learner and to the adversary differ. When the learner predicts 0, no true label is revealed, so the learner records the symbol in its history in place of a label.
Definition 3.1. Given a finite multiset , we formalize an adaptive learner as a pair of functions
Where and are the sets of distributions over and , respectively. The adversary is a function
In round , is used in the first step to choose a distribution from which the queried instance is sampled. is used in the second step to determine the prediction of the learner. is used in the third step to determine the correct label .
Definition 3.2. We say a labeled sequence is realizable under a concept class if
Let be the learner’s history. Let be adversary’s history. We say an adversary is consistent with if every history that could arise under their strategy is realizable under .
We now define the optimal mistake bound against consistent adversaries, commonly known as the realizable setting.
Definition 3.3. For a learner and an adversary , let and denote the respective histories at the start of round and let
denote, the instance selected by the learner, the label chosen by the adversary, and the label predicted by the learner in round respectively.
Let a finite multiset of size be given to the learner. Let the game last for rounds. We define the expected number of mistakes the learner makes against the adversary by
The learner’s history evolves as
and the adversary’s history evolves as
where .
We define the optimal mistake bound of against an adversary providing apple-tasting feedback on by
where the supremum is taken over all adversaries which are consistent with .
Finally, we define the optimal mistake bound over over all finite submultisets of of size at most by
Definition 3.4. We say that a concept class is learnable under the realizable setting of self-directed online learning with apple-tasting feedback (or learnable, in short) if , and not learnable if .
If the adversary is not consistent with the concept class then we try to do as well as the best concept in the concept class. This setting is commonly known as a the agnostic setting. As a result, we define expected regret as the number of mistakes made by an algorithm in comparison to the best concept in the concept class.
Definition 3.5. The learner , the adversary , the history of the learner , the history of the adversary , the instance selected by the learner , the label chosen by the adversary and the label predicted by the learner in round are exactly the same as in Definition 3.3.
For a given finite multiset of size , let the game go on for rounds. We define the expected regret of the learner against the adversary as
We define the optimal expected regret of against an adversary providing apple-tasting feedback on by
where the supremum is taken over all adversaries.
Finally, we define the optimal mistake bound over all finite submultisets of of size at most by
Definition 3.6. We say that a concept class is learnable under self-directed online learning with apple-tasting feedback in the agnostic setting (or agnostic learnable, in short) if , and not agnostic learnable if .
For the sake of completeness, we restate the definition of VC dimension, -centered star number, and self-directed dimension.
Definition 3.7 (VC dimension Vapnik and Chervonenkis, [26]). A set is VC-shattered by a concept class if the projection of onto , i.e., , has size . The VC dimension of , denoted , is the size of the largest set that VC-shatters, or if no such largest set exists.
Definition 3.8 (∅-centered star number Hanneke and Yang, [17], Hanneke, [16]). A set is ∅-centered star-shattered by a concept class if:
There exists a concept such that for all ; and
For every , there exists a concept such that and for all .
The ∅-centered star number of , denoted , is the size of the largest set that ∅-centered star-shatters, or if no such largest set exists.
For an ∅-centered star-shattered set, we say that the concept realizing (1) is the center and the concepts realizing (2) are the witnesses.
The self-directed dimension is the dimension that characterizes the self-directed online learning learning with full-information setting.
Definition 3.9 (Self-directed dimension Devulapalli and Hanneke, [11]). For a concept class on a finite multiset , let . We define by whenever , and otherwise
The recursion terminates since strictly decreases. The dimension of self-directed learning of is , the supremum over finite multisets .
When , Devulapalli and Hanneke [ [11] provide a deterministic algorithm that makes at most mistakes on any input. We call this the SDSolver algorithm and use it as a black box.
Definition 3.10 (Union-closure). Let be a nonempty concept class. For a subset , let denote the concept for which if and only if for some . Then the union-closure of is .
Unless stated otherwise, , , hide universal constants which do not depend on any parameter of the problem. Notation such as indicates that the implied constants depend on the concept class .
Tetrachotomy in the realizable setting
In this section, we focus on the realizable setting. The following theorem is the main result of this work. It expresses a fundamental tetrachotomy: there are exactly four possibilities for optimal learning rates.
Theorem 4.1. For every concept class exactly one of the following holds:
is not learnable, i.e. .
is learnable with .
is learnable with .
is learnable with .
A second main result of this work provides a detailed description of which of these four cases any given concept class belongs to, by specifying complexity measures to distinguish the cases.
We use the well-known Vapnik Chervonenkis dimension denoted as defined in Vapnik and Chervonenkis [ [26], the ∅-centered star number, denoted as defined in Hanneke and Yang [ [17], and the self-directed dimension as defined in Devulapalli and Hanneke [ [11] to characterize the various cases.
Theorem 4.2. Every concept class falls into one of the following four cases:
If then is not learnable, i.e. .
If and then is learnable with .
If and then is learnable with .
If and then is learnable with .
Since Theorem 4.1 follows immediately from Theorem 4.2, the focus of this work will be to prove Theorem 4.2. The proof of this theorem, and many related results, are presented in the remainder of this paper.
As a warm-up we consider the simplest case.
Theorem 4.3. If then is not learnable, i.e. .
Proof. Let and let be a shattered set of size . The adversary then gives to the learner and chooses its labels uniformly at random. Since is shattered by , these labels are realizable. The learner then averages half a mistake per round, so .
Upper Bounds
We now consider the interesting regimes of , , or .7 We first show the upper bounds.
VC finite
Algorithm 1 PRUNE-AND-EAT
, ▷ version space: projection of onto
while is not empty:
▷ sparse concepts
if then break
▷ best apple
Predict on and receive the true label
if then predict on every remaining . ▷ no further feedback
We first consider the regime in which . We design an algorithm that helps the learner select relatively safe points to query while progressively eliminating concepts that are either inconsistent with the true concept or which can be safely ignored.
At a high level, PRUNE-AND-EAT alternates between two steps. First, it discards any concepts in the current version space that label too few of the remaining points as 1. This is safe because if the true concept labels almost all remaining points as 0, the learner can afford to predict 0 on all of them and still make few mistakes. Second, among the surviving hypotheses, the algorithm greedily selects the point on which the largest fraction of the concepts predicts 1, and queries its label by predicting it label to be 1. Pruning guarantees that this point is labeled 1 by a -fraction of the version space for . Hence, whenever eating it results in a mistake, that entire -fraction of concepts is inconsistent with the revealed label and is eliminated. We now state and prove this formally.
Theorem 4.4. Let be a concept class with . Then is learnable by algorithm PRUNE-AND-EAT. Furthermore, we obtain a bound on the optimal number of mistakes
Proof. Let be the points chosen by the adversary. Let denote the (unknown) true labeling concept. Let be the initial version space, and for let denote the version space at the start of round and its state immediately after the pruning step of that round. Let denote the data set in the th round. Every mistake the algorithm makes is of exactly one of two types, according to its prediction:
: mistakes on points the algorithm eats, i.e. while ;
: mistakes on points the algorithm defaults to 0 on after exiting the loop i.e. while .
Since the algorithm predicts 1 exactly on the points it eats inside the loop and 0 on every point remaining at exit, these two classes partition the mistake rounds, so the total number of mistakes is .
Key observation. Fix a round and consider the version space before pruning. We remove the concepts that are sparse: i.e., if the number of points in a concept labels as 1 is less than , then we remove that concept to obtain . We note that by construction every satisfies
Summing over all and exchanging the order of summation,
Since , averaging over the points of show that some satisfies
Therefore after pruning, some point in is labeled 1 by at least a fraction of the surviving hypotheses. In particular, the point chosen by the algorithm, which maximizes this count, satisfies this bound as well. Note that we can assume ; if , then , so the claimed mistake bound is trivial.
Bounding . Suppose the algorithm eats in round and makes a mistake, so the revealed label is . By the key observation, more than a -fraction of labels as 1; every such concept is inconsistent with and is removed. Hence
using . Version spaces are non-increasing across all other rounds, so we can chain this inequality over the rounds on which an eating mistake occurs. Let denote the last round completed before the loop terminates. The loop breaks only upon detecting that is empty, so the version space at the start of that round i.e. is nonempty, giving . Hence,
We now use Sauer’s Lemma, giving , and take logarithms to obtain
Using for ,
Bounding . If the loop terminates with then every point was eaten, no point receives the default prediction, and . So suppose the loop terminates with in some round . Since is consistent with every revealed label, it stays in the version space; the only step that can remove it is pruning. Hence if , then at some round , which means . The points receiving the default prediction 0 are exactly those remaining at termination, and since only shrinks. Each such mistake occurs at a point with , so
Total mistakes. Combining the two bounds,
We now consider the case where . The following theorem will help us resolve the and regimes at the same time.
Theorem 4.5. For a concept class ,
We will prove Theorem 4.5 in two cases: and .
SDDim infinite
We will prove Theorem 4.5 in two cases: and .
SDdim() = ,
Algorithm 2 UNION-AND-EAT($\mathcal{H},S$)
1: $\mathcal{V}\leftarrow\mathcal{U}(\mathcal{H})|_S$ ▷ Projection of the union closure $\mathcal{U}(\mathcal{H})$ as in Def. {xref}`Def. 3.10` onto $S$
2: while there exists $x\in S$, $h\in\mathcal{V}$ with $h(x)=1$:
3: $a\leftarrow\arg\max_{x\in S}\sum_{h\in\mathcal{V}}h(x)$ ▷ Best apple
4: Predict $\widehat{y}=1$ on $a$ and receive the true label $y$
5: $S\leftarrow S\setminus\{a\}$
6: $\mathcal{V}\leftarrow\{h\in\mathcal{V}:h(a)=y\}|_S$
7: if $|S|>0$ then predict $\widehat{y}=0$ on every remaining $x\in S$
In this case, rather than working with directly, we pass to its union closure , obtained by taking all pointwise-OR combinations of subsets of . Learning is no harder than learning since , so any mistake bound for upper bounds the mistake bound for . The advantage of passing to is that it is union-closed by construction, and union-closed families enjoy a useful averaging property: some point must be labeled 1 by a constant fraction of the family. Consequently, greedily querying this point guarantees constant multiplicative progress on every mistake, in contrast to Algorithm Algorithm 1, where progress was only guaranteed after a pruning step. We now prove a few lemmas which will be helpful to prove an upper bound based on .
Lemma 4.6. For any concept class , .
Proof. Let , and let be -centered star-shattered in . Let be the center: i.e. for all . Let be the witnesses: i.e. for all , we have and for all .
We claim that also -centered star-shatters . For the center, write for some . Because for every , and a union of concepts is 0 at a point only if every concept in the union is 0 there, each satisfies for all .
We can similarly extract the witnesses from the other . Fix and write for some . Since for every , each satisfies for all . Since , at least one satisfies . Combining these two facts, agrees with everywhere on except at , where it equals 1. Repeating this for every produces concepts that, together with , -centered star-shatter . Hence .
Since contains the singleton union of each concept in , we have . Hence any set -centered star-shattered by is also shattered by , so .
Lemma 4.7. If is a union-closed concept class then .
Proof. Let , and let be -centered star-shattered by center and witnesses : labels every point of as 0, and agrees with except that .
We claim that shatters . The concept realizes the all-zero labeling of . For any nonzero target labeling of , let . Let . Because is union-closed and is nonempty, we have . Since each labels only as 1 among , if and only if which is if and only if . Hence realizes every labeling of , so .
Let , and let be shattered by . By shattering, for each there is a concept realizing the labeling that assigns and for . There is also a concept realizing the all-0 labeling. Then is -centered star-shattered by center and witnesses , so .
Proposition 1. There is a universal constant such that for every finite union-closed class of concepts (other than the trivial class), some point satisfies
We use as a placeholder for the best constant available. At the time of writing Gilmer [ [13] establish , Chase and Lovett [ [9], Pebody [ [22], Sawin [ [24], Alweiss et al. [ [2] establish , and finally Liu [ [21] establish . Please refer to Bruhn and Schaudt [ [6] for the history of union-closed set conjecture (also known as Frankl's conjecture) which suggests . The exact value is not relevant for our purposes as long as .
Theorem 4.8. Let be a concept class with . Then is learnable by algorithm Union-And-Eat. Furthermore, we obtain a bound on the optimal number of mistakes
where is the universal constant from the union-closed set conjecture (Proposition 1).
Proof. For , let denote the version space at the start of the th iteration of the while loop. Since we only ever remove concepts for being inconsistent with the true concept, there is always a concept consistent with the true concept in . As we only exit the while loop once the remaining concepts label all remaining points as 0, we make no mistakes when labeling the remaining points 0 in step 7.
That leaves the false positive mistakes made when predicting 1 in step 4. We use Proposition 1 to bound these mistakes, so we need to make sure that the version spaces are all union-closed. We show this by induction on . As a base case, the initial version space is the projection of the union-closed concept class onto , so it is union-closed. Now assume is union-closed for some fixed . The next version space is constructed in two steps:
First, it is restricted to the concepts which map to the true label . Let be two such concepts. Since is union-closed, we have . Moreover, since , it remains in the version space.
Second, it is projected onto . As in the base case, this projection preserves union-closure.
Therefore we can guarantee that the point selected in each round of UNION-AND-EAT satisfies , where is the constant in Proposition 1. Whenever the algorithm makes a mistake at its true label is , so every with is inconsistent and is discarded from the next round’s version space. Let be the number of mistakes made in total. Since no is empty, we have:
By Lemmas 4.6 and 4.7, we have , so by Sauer’s Lemma:
Taking logarithms and using , we obtain
So algorithm UNION-AND-EAT makes at most mistakes as desired.
SDDim finite
Algorithm 3 FIRST-MISTAKE
if then
Predict for and obtain the true label .
if then return .
,
Let for all , with .
while there is some such that do
Let
Predict at and obtain the true label .
if then
if then return else return
Algorithm 4 SIMULATE-AND-EAT($\mathcal{H}$, $S$, SDSolver)
1: $\mathcal{V} \leftarrow \mathcal{H}|_{S}$
2: while $\mathcal{V}$ contains concepts that disagree at a point in $S$ do:
3: Let $n \leftarrow |S|$, $S^{0} \leftarrow \varnothing$, $x_{\mathrm{mis}} \leftarrow \bot$
4: Simulate a run of SDSolver($\mathcal{V}$, $S$) assuming all predictions are correct.
5: Let the order and the predictions in the previous step be $\sigma$, $(\widehat{y}_{\sigma(1)}, \ldots, \widehat{y}_{\sigma(n)})$ resp.
6: Let $x_{\sigma(n+1)} = \bot$, $\widehat{y}_{\sigma(n+1)} = 1$.
7: for $i$ goes from 1 to $n + 1$ do
8: if $\widehat{y}_{\sigma(i)} = 0$ then $S^{0} \leftarrow S^{0} \circ \{x_{\sigma(i)}\}$
9: if $\widehat{y}_{\sigma(i)} = 1$ then
10: $x_{\mathrm{mis}} \leftarrow$ FIRST-MISTAKE($\mathcal{V}$, $S^{0}$, $x_{\sigma(i)}$)
11: if $x_{\mathrm{mis}} \ne \bot$ then
12: Let $R$ be the set of points before $x_{\mathrm{mis}}$ in $S$ w.r.t. order $\sigma$.
13: Label all the points in $R$ according to the labels given by SDSolver.
14: $S \leftarrow S \setminus (R \cup \{x_{\mathrm{mis}}\})$
15: $\mathcal{V} \leftarrow \{h \in \mathcal{V} : h(x_i) = \widehat{y}_i \text{ for all } x_i \in R \text{ and } h(x_{\mathrm{mis}}) = 1 - \widehat{y}_{\mathrm{mis}}\}$
16: break
17: if $x_{\mathrm{mis}} = \bot$ then
18: Label all the points in $S$ according to the labels given by SDSolver and break
19: Predict all remaining points according to the concepts in $\mathcal{V}$
In this case, the idea is a kind of reduction from apple-tasting feedback to the full-information case. We make mistakes to recognize the first position at which the full-information learner makes a mistake. We know that in full-information, we can obtain the true concept in mistakes. Therefore, we obtain the true concept in at most mistakes with apple-tasting feedback.
The following lemma shows that we can obtain the first position where the full-information (self-directed) learner makes a mistake using apple-tasting feedback with at most mistakes.
Lemma 4.9. Let be points provided to FIRST-MISTAKE. Let be a version space such that and there exists such that for all and, if , then . Let
Then one of these three cases occurs:
If then FIRST-MISTAKE returns and makes no mistakes.
If then FIRST-MISTAKE returns and makes at most mistakes.
If then FIRST-MISTAKE returns if and otherwise. It also makes at most mistakes.
Proof. Throughout, every update is of the form where is the true label revealed at ; hence at all times, and only shrinks. Note also that depends only on , so it is unaffected by these updates.
Case 1: . In this case, the lemma statement is immediate from the algorithm: line 3 predicts at and the revealed label is , so line 4 returns immediately and we make no mistakes.
In the other two cases, the algorithm does non-trivial work. We first make two observations about this work by linking the variable mis to .
when : is lowered only at line 11, upon a probe at revealing , and then forces . In case 2 the initial value satisfies this since and in case 3 the initial value is .
The loop cannot terminate while : if then satisfies , so condition for the loop at line 7 holds.
Combining the two, the loop terminates with whenever .
Correctness in cases 2 and 3.
Case 2: . Line 3 incurs one mistake, line 5 sets , and the loop runs. If the observations give on termination, and line 12 returns . If , no probe can reveal (that would force ), so remains and line 12 returns . Therefore, the returned point is .
Case 3: . Here on entry to the loop. If , then on termination and line 12 returns . If , then no probe reveals , so remains and line 12 returns .
Mistake bound for cases 2 and 3.
A probe is a mistake exactly when the revealed label is 0. Let be the indices in of the loop probes revealing 0, and in Case 2 put additionally , the index of the failed initial probe. Set , over in Case 2 and in Case 3. The number of mistakes is exactly , so it suffices to show that the initial -centered star-shatters .
The center. Each was a probe revealing the true label 0, so for every , and by hypothesis. Hence labels every point of as 0.
The witnesses. For (case 2 only) take , which by hypothesis lies in , satisfies , and satisfies for every , hence in particular at .
For , let denote the version space immediately before the -th failed loop probe. By the selection rule at line 8 there is with . Then
, directly from .
for every , since and is the least index of at which takes the value 1.
for every , including in case 2, since and each of those earlier probes revealed the label 0, after which line 10 (respectively line 5) discarded every concept taking the value 1 there.
So is 1 at and 0 on , and because .
Together with the center , these witnesses -centered star-shatter , hence and the algorithm makes at most mistakes.
Theorem 4.10. Let be a concept class with and . Then is learnable by algorithm \textsc{Simulate-and-Eat}. Furthermore, we also obtain a bound on the optimal number of mistakes
Proof. We use induction on . As a base case, if , then contains only one concept, so the main loop terminates immediately and predicts all points correctly.
Now assume that, for some , \textsc{Simulate-and-Eat} is correct and achieves the desired mistake bound on all concept classes with . Let be an arbitrary concept class with , let be a multiset, and let be the true labeling concept.
We now run \textsc{Simulate-and-Eat} on and . Let be the order in which \textsc{SDSolver} probes the points in and let denote the labels provided by \textsc{SDSolver} assuming that all the predictions it made are correct. We will use Lemma 4.9 to characterize the behavior of the calls to \textsc{First-Mistake}, so we need to show that its conditions hold:
We always have since .
Since SDSolver is consistent, the concept it follows satisfies for all and for all such that . This concept satisfies the condition of in Lemma 4.9.
We now briefly handle the case where all labels provided by SDSolver are correct. Here, the only call to FIRST-MISTAKE which can make a mistake is the final one with . By case 3 of Lemma 4.9, this call will make at most mistakes and return . Line 17 then correctly labels all points as SDSolver did. Since , we make at most mistakes as desired.
Now that at least one is incorrect, let be the first index for which . We claim that will be set to , so that the updates on lines 14 and 15 correctly assign labels to . Let be the first index for which the call FIRST-MISTAKE does not fall into case 1 of Lemma 4.9; such an index exists because . We have because if , then . We then have two cases based on :
If , then we have , so . The call to FIRST-MISTAKE therefore falls under case 2 of Lemma 4.9. At this time, the true labels of all points in are 0, so FIRST-MISTAKE returns as desired and makes at most mistakes.
If , then is the first incorrectly labeled point in . We may be in either case 2 or 3 of Lemma 4.9, but in either case this guarantees that is returned and at most mistakes are made.
Therefore, lines 14 and 15 correctly label the prefix and update the version space accordingly. Let be this new version space. By the construction of SDSolver, we have . The next iteration of the loop is indistinguishable from running SIMULATE-AND-EAT with as the starting concept class, so by the inductive hypothesis it makes at most more mistakes. Adding in the mistakes from the first iteration we get at most mistakes, completing the proof. □
Proof of Theorem 4.5. We can combine Theorem 4.8 and Theorem 4.10 to obtain . □
Lower Bounds
We now take a look at the lower bounds. Most of our lower bounds are based on an extension of the singletons concept class which we call block singletons. Suppose a concept class satisfies for some . We then make a multiset of instances by including copies of each of the elements of an -centered star-shattered set. This set is given by the adversary to the learner at the beginning of the game. By definition, for each of these blocks of apples there exists a concept in that labels only that block as 1. Intuitively, any self-directed learner with apple-tasting feedback should make roughly mistakes on this multiset of instances: either they eat apples from few blocks (and miss the that are labeled 1), or they eat apples from many blocks (including about that are labeled 0).
Theorem 4.11. Let and let be a concept class. If , then there exists a multiset of size on which any randomized self-directed learner with apple-tasting feedback makes at least mistakes in expectation.
Proof. Let be a set that -centered star-shatters. Let be a multiset consisting of copies of each of . This multiset is given by the adversary to the learner at the beginning of the game. By definition, there exist concepts such that, for each , we have and for . Each of those concepts has one good block labeled 1 and bad blocks labeled 0. There also exists a concept for which every block is bad. We have the adversary choose the following distribution over these concepts at the beginning of the game:
With probability , choose one of uniformly at random.
With probability , choose .
We claim that under this distribution no randomized learner can make fewer than mistakes on average.
Let be an arbitrary randomized learning algorithm. We make a few observations which will aid our analysis.
We can assume without loss of generality that samples one point from each of the blocks in an arbitrary order and predicts 1 on them until it either finds a good block or decides to stop; any other strategy makes unnecessary mistakes.
If the algorithm stops because it found a good block, then it will predict 1 for all the apples in that block and then predict 0 for all other apples. This corresponds to the learner’s discovery that the true concept is in .
If the algorithm stops because it decided to terminate, then it will predict 0 for all other apples. This corresponds to the learner’s belief that the true concept is .
Since the only feedback gets before stopping is a series of bad blocks, we can further assume that before making any samples it chooses some (possibly random) number of bad blocks to sample before stopping.
We now compute the expected number of mistakes makes for each fixed choice of which denotes the number of bad blocks the learner sampled from. There are three possibilities, whose probabilities and mistake counts depend on :
In the first case the algorithm finds a good block at some . This indicates the true concept is in . In this case, the algorithm makes mistakes.
In the second case the algorithm does not find a good block but the adversary had chosen the true concept from . In this case, the algorithm makes mistakes.
In the third case the algorithm does not find a good block and the adversary chose as the true concept. In this case, the algorithm makes mistakes.
We now combine these three cases to compute the expected number of mistakes made by the algorithm.
Since , , so we have:
Since this inequality holds for all , it holds for any distribution over , and therefore makes at least mistakes in expectation. □
Note that the adversary in Lemma 4.11 commits to a distribution over the true concepts before beginning the game with the learner. This adversary is weaker than the general case, since our model allows choosing the labels adaptively. We call this an oblivious adversary. We also refer readers to section 6 where we obtain a tight upper bound for a game against an oblivious adversary when .
Since this block singleton structure exists in any concept class with , it is especially powerful when . We use this idea to show the following theorem.
Theorem 4.12. For any concept class , if then .
Proof. Let be a concept class with . For any fixed , let . Then , so by Lemma 4.11 there exists a sample set of size at most on which any randomized self-directed learner with apple-tasting feedback makes at least mistakes.
When , Lemma 4.11 yields only a constant lower bound. We supplement it with a bound based on . Because apple-tasting feedback is less useful than full-information feedback, the only difficulty is in showing that also lower-bounds the performance of randomized algorithms. A full proof would involve retreading much of the ground of Devulapalli and Hanneke [ [11], so we refer the reader to that paper for a more complete description of the trees involved.
Theorem 4.13. Let be a concept class such that and are both finite. Then for all sufficiently large we have . Moreover, if , then .
Informal proof Apple-tasting feedback is strictly weaker than full-information: a full-information learner can simulate any apple-tasting learner by discarding the labels it would not have observed. Any lower bound for the full-information setting therefore transfers to the apple-tasting setting, so we consider the performance of a full-information learner. Devulapalli and Hanneke [ [11] characterize self-directed learning through the dimension , which they show equals the optimal deterministic mistake bound . Combinatorially, can be constructed as the largest for which there is a set and a realizable -tree on : a tree whose nodes are subsets , in which every carries two outgoing edges labeled with distinct labels , every root-to-leaf path has length at least , and every branch is realized by some concept of .
In an analogous way to how Filmus et al. [ [12] show bounds on randomized adversarial online learning using the Littlestone tree, we use a maximum -tree to bound randomized self-directed learning. Here the adversary observes the learner’s choice of point and distribution over predicted labels, but only sees the realized prediction after committing to the true label.
If , fix a realizable -tree for and let the adversary play down it. Whenever the learner selects a point of the current node , two labels are available, and at least one of them receives probability at most under the learner’s distribution; the adversary answers with that label, forcing a mistake with probability at least , and the play descends one level. Since the learner must eventually predict on every point of , and the points outside the current node are already determined by the tree, at least such descents occur. Hence any randomized learner suffers at least mistakes in expectation, giving . If then we can take arbitrarily large for sufficiently large , yielding the bound.
For the remainder of the lemma statement, Lemma 4.11 gives a lower bound of . Combining these two results give us the desired bound. ∎
Concluding the tetrachotomy result
We can now prove our previously stated theorem on dimension to characterize the rates.
Proof of Theorem 4.2. Let a concept class be given. We note that,
By Theorem 4.3, if then .
By Theorems 4.4 and 4.12, if and then .
By Theorems 4.5 and 4.13, if and then .
By Theorem 4.10, if and then .
Proof of Theorem 4.1. Let a concept class be given. By Definitions 3.7, 3.8, and 3.9 we have and , so exactly one of the following holds: ; or and ; or and ; or and . Theorem 4.2 assigns to each of these cases the rates , , and respectively. Hence every concept class attains one of the four rates, and no class attains two, since the cases are mutually exclusive.
Remark 1. Self-directed online learning with apple-tasting feedback can be shown to allow learnability of more concept classes than its adversarial counterpart. For instance, the combinatorial characterization given by Raman et al. [ [23] shows that mistakes can be forced for thresholds in the adversarial online setting, but the VC-dimension and -centered star number are finite for this class.
Remark 2. We note that and could be finite or infinite, independent of each other. Singletons on have infinite but finite . In section 7 we show that there also exists a class with finite but infinite .
Agnostic Learning
In the agnostic case, we obtain the same bounds that Devulapalli and Hanneke [ [11] did for full-feedback self-directed learning. Our lower bound is implied by theirs. Our upper bound uses the same strategy, but with the implementation of online learning with expert advice from Raman et al. [ [23] that works with apple-tasting feedback. We state both of these prior results here.
Proposition 2 (Theorem 17 from Devulapalli and Hanneke [ [11]). Let be a concept class with finite VC dimension. Then for all , there exists an instance space of size on which any self-directed learning algorithm, with full-information feedback, has expected regret .
Proposition 3 (Theorem 16 from Raman et al. [ [23]). Let and let be experts. For expert , let be their predictions in rounds . Let be the sequence of true labels. Then there exists an online learning algorithm that receives only apple-tasting feedback and outputs predictions that satisfy:
Theorem 5.1. Let be a concept class with finite VC dimension. The optimal expected regret of learning in the self-directed, apple-tasting, agnostic setting satisfies:
Proof. The lower bound is implied by Proposition 2, since apple-tasting feedback is weaker than full-information feedback.
For the upper bound, we use the algorithm of Proposition 3. After receiving the initial set of points , the learner instantiates one expert for each projection of the concept class onto . The performance of the best expert is then equal to the performance of the best concept, and by Sauer’s lemma we have . The learner chooses an arbitrary order of the points in and commits to predicting on them in that order. The regret is therefore .
Oblivious adversaries
Throughout our paper, we have been considering the most powerful adversary possible in the self-directed setting. Not only do they choose which points the learner can see, they can adaptively choose true labels in response to the learner’s queries. In this section, we consider a weaker variant of the realizable setting in which the adversary decides the true labels at the start of the game. This setting is colloquially called the oblivious adversary setting.
For non-oblivious adversaries in the regime where , Theorem 4.4 gives the deterministic algorithm PRUNE-AND-EAT which achieves mistakes. In this section we show that the factor can be removed for oblivious adversaries and that the resulting bound is tight.
Since the true concept is now chosen at the start of the game, the most natural predictor is the one-inclusion graph of Haussler et al. [1994]. We take a sample of size from the provided set of points and treat it as training data to construct the one-inclusion graph. Using this predictor, we generalize to the other points in .
| Algorithm 5 SAMPLE-AND-EAT() |
| 1: Draw uniformly at random among all subsets of of size |
| 2: |
| 3: Query the points in in any order and predict for all these points |
| 4: Obtain ▷ Projection of the true concept onto |
| 5: Construct the one-inclusion graph |
| 6: For each : |
| 7: Predict ▷ the one-inclusion graph prediction |
| 8: Ignore any feedback |
| 9: |
Table 5.
Theorem 6.1. Let be a concept class with and assume the adversary is oblivious. Then is learnable by algorithm SAMPLE-AND-EAT with at most mistakes in expectation.
Proof. The algorithm makes mistakes in two phases, which we bound separately:
: Mistakes made while predicting 1 for all points in . We can naively bound .
: Mistakes made by the one-inclusion graph predictor. We know the one-inclusion graph makes a mistake with probability at most on an unseen point. Therefore, .
Combining the two bounds, we get as desired. □
The upper bound of Theorem 6.1 still has a factor. We now show that in general, this factor cannot be removed. We use several independent copies of the structure from Lemma 4.11.
Theorem 6.2. For all , there exists a concept class such that and , even against an oblivious adversary.
Proof. Let be the infinite singleton concept class. That is, let be its instance space and include one concept for each , where and for all . We then let consists of independent copies of . Since , we have as desired.
We now show that . Since , by Lemma 4.11 for any we can construct instance spaces of size on which an oblivious adversary can force mistakes in expectation. Let be arbitrary. We partition into blocks of size each, then fill each block with the construction of Lemma 4.11 using the copies of in . By playing independently on each block, the adversary can therefore force mistakes on all blocks, for a total of . □】【。
A class in the gap
Three of the four regimes that Theorem 4.2 classifies include common concept classes:
The class containing all concepts has infinite VC dimension;
The infinite singletons concept class has finite VC dimension but infinite ; and
Finite concept classes have finite and SDdim.
The remaining regime has finite but infinite SDdim. In this section, we show that it too is nonempty. We use a combination of Lemma 4.7 and a construction of Kuhlmann [ [20], whose relevant details are summarized by the following proposition.
Proposition 4 (Sub-claims of Theorem 2 from Kuhlmann [ [20]). Let be an intersection-closed concept class on an instance space . Suppose . Then there exists an intersection-closed concept class on an instance space such that:
, and
For all and , the version space contains a copy of .
Furthermore, if is finite, then one can take .
Theorem 7.1. There exists a concept class for which , and .
Proof. We use the construction of Proposition 4 recursively. It produces intersection-closed concept classes, but by reversing the labels we can produce union-closed concept classes instead. Then Lemma 4.7 allows us to relate their VC-dimension to their -centered star number.
Specifically, let be a set of size 2 and let be the set of all concepts on . We then have and that it is union-closed. Recursively apply the construction of Proposition 4 but with inverted labels to produce instance spaces and union-closed concept classes that still satisfy for all . Each contains copies of , so by identifying with one of these copies we can turn this infinite sequence of concept classes into a single infinite concept class. We take this limiting concept class to be and the limiting instance space to be .
We first show that . Because is union-closed, by Lemma 4.7 we have . Since contains a copy of we have , and since any shattered set of size 3 would be contained in some finite we have . Therefore, .
We now show that . As a stepping stone, we show by induction that , recalling that denotes the expected number of mistakes an adversary can force when presenting the instance space to the learner. The base case is trivial. For the inductive step, suppose for some . When the learner is presented with , the adversary can choose the true label for the learner’s first point uniformly at random. This forces half a mistake on average. By construction, there then exists a copy of that agrees with this random label, so by the inductive hypothesis the adversary can force more mistakes on average. They can therefore force in total, completing the inductive step.
For , the adversary chooses the largest such that and uses their optimal strategy for . The learner then incurs mistakes on average. Since for all , in terms of we have . Since the adversary’s strategy works even for full-information feedback, we have as well.
AI Disclosure
We used GPT 5.6 Pro, GPT 6 Astra, and Opus 5.5 to produce some of our arguments. Our initial hypothesis was that there was a trichotomy defined by and , and we spent a long time without AI assistance trying to show a constant upper bound for classes with finite . This, of course, turned out to be incorrect, and prompting GPT 5.6 Pro directed us to the construction of Kuhlmann [1999] as the basis for a counterexample. Prompting with GPT 5.6 Pro and GPT 6 Astra provided the upper bounds of Theorem 4.5. A more general prompting with Opus 5.5 produced the oblivious-adversary upper bound of Theorem 6.1, which was not a setting we were considering. All writing in this paper is our own.
Conclusion and Future Work
We introduced self-directed online classification under apple-tasting feedback and determined its minimax rates in both the realizable and the agnostic settings. In the realizable setting, we obtain a tetrachotomy where the expected number of minimax mistakes can be , and , , or . We suspect, however, that the log factors in the and regimes might hide more fundamental characterizations.
In the regime, if we assume the adversary is oblivious then Theorem 6.1 attains a mistake bound of . We also obtain a matching lower bound attained by a specific class. Is the extra factor in Theorem 4.4 an artifact of the adaptive adversary, the deterministic algorithm, or both? There are also classes with large VC dimension that do not have proportionally larger mistake bounds. For instance, a concept class consisting of the infinite singletons concept class plus a shattered set of size has VC dimension but behaves almost identically to the infinite singletons concept class. Is there a combinatorial dimension that captures this nuance?
References
- [1]Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Proceedings of The 28th Conference on Learning Theory, volume 40, pages 23–35. PMLR, 2015. URL https://proceedings.mlr.press/v40/Alon15.html.arxiv.org/abs/1502.07617
- [2]Ryan Alweiss, Brice Huang, and Mark Sellke. Improved lower bound for frankl’s union-closed sets conjecture, 2024. URL https://arxiv.org/abs/2211.11731.
- [3]Gábor Bartók, Dean P. Foster, Dávid Pál, Alexander Rakhlin, and Csaba Szepesvári. Partial monitoring—classification, regret bounds, and algorithms. Mathematics of Operations Research, 39 (4):967–997, 2014. doi: 10.1287/moor.2014.0663.DOI
- [4]Shai Ben-David, Nadav Eiron, and Eyal Kushilevitz. On self-directed learning. In Proceedings of the Eighth Annual Conference on Computational Learning Theory, COLT ’95, page 136–143, New York, NY, USA, 1995. Association for Computing Machinery. ISBN 0897917235. doi: 10.1145/225298.225314. URL https://doi.org/10.1145/225298.225314.
- [5]Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, helly number, and an optimal svm bound. In Conference on Learning Theory, pages 582–609. PMLR, 2020.arxiv.org/abs/2005.11818
- [6]Henning Bruhn and Oliver Schaudt. The journey of the union-closed sets conjecture, 2013. URL https://arxiv.org/abs/1309.3297.
- [7]Nicolo Cesa-Bianchi, Gábor Lugosi, et al. Prediction, learning, and games, volume 1. Cambridge university press Cambridge, 2006.
- [8]Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66(2):321–352, 2007.
- [9]Zachary Chase and Shachar Lovett. Approximate union closed conjecture, 2022. URL https://arxiv.org/abs/2211.11689.
- [10]Zachary Chase and Idan Mehalel. Deterministic apple tasting, 2025. URL https://arxiv.org/abs/2410.10404.
- [11]Pramith Devulapalli and Steve Hanneke. The dimension of self-directed learning. In Proceedings of the 35th International Conference on Algorithmic Learning Theory, volume 237, pages 544–573, 2024.arxiv.org/abs/2402.13400
- [12]Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. Optimal prediction using expert advice and randomized littlestone dimension, 2025. URL https://arxiv.org/abs/2302.13849.
- [13]Justin Gilmer. A constant lower bound for the union-closed sets conjecture, 2022. URL https://arxiv.org/abs/2211.09055.
- [14]Sally A Goldman and Robert H Sloan. The power of self-directed learning. Machine Learning, 14(3):271–294, 1994.DOI
- [15]Steve Hanneke. Refined error bounds for several learning algorithms. Journal of Machine Learning Research, 17(135):1–55, 2016.arxiv.org/abs/1512.07146
- [16]Steve Hanneke. The star number and eluder dimension: Elementary observations about the dimensions of disagreement. In Proceedings of the Thirty Seventh Conference on Learning Theory, volume 247, pages 2308–2359, 2024.
- [17]Steve Hanneke and Liu Yang. Minimax analysis of active learning. Journal of Machine Learning Research, 16(109):3487–3602, 2015. URL http://jmlr.org/papers/v16/hanneke15a.html.
- [18]D. Haussler, N. Littlestone, and M.K. Warmuth. Predicting 0, 1-functions on randomly drawn points. Information and Computation, 115(2):248–292, December 1994. ISSN 0890-5401. doi: 10.1006/inco.1994.1097. URL http://dx.doi.org/10.1006/inco.1994.1097.
- [19]David P. Helmbold, Nicholas Littlestone, and Philip M. Long. Apple tasting. Information and Computation, 161(2):85–139, 2000. ISSN 0890-5401. doi: 10.1006/inco.2000.2870. URL http://dx.doi.org/10.1006/inco.2000.2870.
- [20]Christian Kuhlmann. On teaching and learning intersection-closed concept classes. In Paul Fischer and Hans Ulrich Simon, editors, Computational Learning Theory (EuroCOLT 1999), pages 168–182. Springer Berlin Heidelberg, 1999.DOI
- [21]Jingbo Liu. Improving the lower bound for the union-closed sets conjecture via conditionally iid coupling, 2023. URL https://arxiv.org/abs/2306.08824.
- [22]Luke Pebody. Extension of a method of gilmer, 2022. URL https://arxiv.org/abs/2211.13139.
- [23]Vinod Raman, Unique Subedi, Ananth Raman, and Ambuj Tewari. Apple tasting: Combinatorial dimensions and minimax rates. In Proceedings of the Thirty Seventh Conference on Learning Theory, volume 247, pages 4358–4380, 2024.arxiv.org/abs/2310.19064
- [24]Will Sawin. An improved lower bound for the union-closed set conjecture, 2023. URL https://arxiv.org/abs/2211.11504.
- [25]Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166, 2004.DOI
- [26]V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, January 1971. ISSN 1095-7219. doi: 10.1137/1116025. URL http://dx.doi.org/10.1137/1116025.
- [27]Vladimir G Vovk. A game of prediction with expert advice. In Proceedings of the eighth annual conference on Computational learning theory, pages 51–60, 1995.
- [28]Volodimir G Vovk. Aggregating strategies. In Proceedings of the third annual workshop on Computational learning theory, pages 371–386, 1990.
- [29]Yair Wiener, Steve Hanneke, and Ran El-Yaniv. A compression technique for analyzing disagreement-based active learning. The Journal of Machine Learning Research, 16(1):713–745, 2015.arxiv.org/abs/1404.1504