betaFeedback

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 11. 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 ∅\emptyset-centered star number, and the self-directed dimension, we show that the rates could possibly be Θ(1)Θ(1), O(log⁡n)∩ω(1)O(\log n) \cap ω(1), Θ~(n)\tilde Θ(\sqrt{n}), or Θ(n)Θ(n). In the agnostic setting, the minimax regret is Θ~(n)\tilde Θ(\sqrt{n}) or Θ(n)Θ(n), 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 nn rounds. At the start of the game, the adversary provides a set of nn points. In round ii, the learner selects one of these points xix_i and makes a prediction y^i∈{0,1}\widehat{y}_i \in\{0,1\}. The adversary then assigns a label yi∈{0,1}y_i \in\{0,1\}, unknown to the learner, and the learner incurs loss 1[y^i≠yi]\mathbb{1}[\widehat{y}_i \ne y_i]. If y^i=1\widehat{y}_i = 1, the adversary reveals the true label yiy_i; 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 Θ~(n⋅VC⁡(H))\widetilde{\Theta}\left(\sqrt{n\cdot\operatorname{VC}(\mathcal{H})}\right).

  • On the other hand, VC dimension alone is not enough to characterize the realizable setting. There are easier regimes characterized by the ∅\varnothing-centered star number of H\mathcal{H} [16], denoted s∅(H)s_{\varnothing}(\mathcal{H}), and the self-directed dimension of [11] denoted by SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}).

  • Consequently, in the realizable setting, we obtain a tetrachotomy on the mistake bound. (i) ΘH(1)\Theta_{\mathcal{H}}(1) when s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty, SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H}) < \infty; (ii) OH(log⁡n)∩ωH(1)O_{\mathcal{H}}(\log n) \cap\omega_{\mathcal{H}}(1) when s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty but SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty; (iii) Θ~H(n)\widetilde{\Theta}_{\mathcal{H}}(\sqrt{n}) when VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty but s∅(H)=∞s_{\varnothing}(\mathcal{H}) = \infty; (iv) Θ(n)\Theta(n) when VC⁡(H)=∞\operatorname{VC}(\mathcal{H}) = \infty.

We additionally establish several auxiliary results.

  • We show that for any d∈Nd \in\mathbb{N}, there exists a concept class Hd\mathcal{H}_d such that VC⁡(Hd)=d\operatorname{VC}(\mathcal{H}_d) = d and the optimal number of mistakes made by any algorithm is Ω(nd)\Omega(\sqrt{nd}).

  • 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 log⁡n\sqrt{\log n}. 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 s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty and SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty, 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 H\mathcal{H}, letting U(H)\mathcal{U}(\mathcal{H}) denote its union closure, we have s∅(H)=s∅(U(H))=VC⁡(U(H))s_{\varnothing}(\mathcal{H}) = s_{\varnothing}(\mathcal{U}(\mathcal{H})) = \operatorname{VC}(\mathcal{U}(\mathcal{H})).

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 LDim⁡(H)\operatorname{LDim}(\mathcal{H}) in the agnostic case, and show an upper bound of O(LDim⁡(H)Tlog⁡T)O\left(\sqrt{\operatorname{LDim}(\mathcal{H})T\log T}\right) 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: Θ(1)\Theta(1), Θ(T)\Theta(\sqrt{T}), or Θ(T)\Theta(T). Our tetrachotomy (Theorem 4.1) is a self-directed counterpart of this result, where the rates are instead governed by the VC dimension, ∅\varnothing-centered star number, and the self-directed dimension.

Chase and Mehalel [ [10] study deterministic algorithms and show a log⁡T\sqrt{\log T} 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 SDdim⁡\operatorname{SDdim} 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 s(H)s(\mathcal{H}) 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 s(H)s(\mathcal{H}), 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 ∅\emptyset-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 ∅\emptyset-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 NN experts in each of TT rounds and must make few mistakes relative to the best-performing expert. Multiplicative weights gives a regret bound of Tlog⁡N\sqrt{T \log N}. 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 VC⁡(H)/∣R∣\operatorname{VC}(\mathcal{H})/|R| given ∣R∣|R| 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 X\mathcal{X} denote an arbitrary non-empty set, referred to as the instance space, and Y={0,1}\mathcal{Y} = \{0,1\} the label space. Let H\mathcal{H} denote an arbitrary non-empty set of concepts h:X→Yh : \mathcal{X} \to\mathcal{Y}, 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 SS and use the notation S⊆XS \subseteq\mathcal{X} to mean that every x∈Sx \in S is also in X\mathcal{X}.

Self-directed online learning under apple-tasting feedback setting

We describe the learning protocol. Given a non-empty concept class H\mathcal{H} and a finite multiset S⊆XS \subseteq\mathcal{X}, one round of self-directed online learning under apple-tasting feedback proceeds as follows.

  1. The learner chooses some x∈Sx \in S.

  1. The learner predicts a label y^∈Y\hat{y} \in\mathcal{Y} for xx.

  1. If y^=1\hat{y} = 1, the learner receives the true label y∈Yy \in\mathcal{Y} from the environment. If y^=0\hat{y} = 0, the learner receives no feedback.

Rounds proceed in this fashion until the learner has labeled every point in SS. For brevity we say the learner eats a point xx 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 ⋆\star in its history in place of a label.

Definition 3.1. Given a finite multiset S⊆XS \subseteq\mathcal{X}, we formalize an adaptive learner as a pair of functions

Lrn⁡x:(S×(Y∪{⋆}))∗→Π(S),Lrn⁡y:(S×(Y∪{⋆}))∗×S→Π(Y),\operatorname{Lrn}_x : \left(S \times(\mathcal{Y} \cup\{\star\})\right)^* \to\Pi(S), \qquad\operatorname{Lrn}_y : \left(S \times(\mathcal{Y} \cup\{\star\})\right)^* \times S \to\Pi(\mathcal{Y}),

Where Π(S)\Pi(S) and Π(Y)\Pi(\mathcal{Y}) are the sets of distributions over SS and Y\mathcal{Y}, respectively. The adversary is a function

Adv⁡:(S×Y)∗×S→Π(Y)\operatorname{Adv} : (S \times\mathcal{Y})^* \times S \to\Pi(\mathcal{Y})

In round ii, Lrn⁡x\operatorname{Lrn}_x is used in the first step to choose a distribution from which the queried instance xix_i is sampled. Lrn⁡y\operatorname{Lrn}_y is used in the second step to determine the prediction y^i\hat{y}_i of the learner. Adv⁡\operatorname{Adv} is used in the third step to determine the correct label yi∈Yy_i \in\mathcal{Y}.

Definition 3.2. We say a labeled sequence Sn=((x1,y1),…,(xn,yn))S_n = ((x_1,y_1),\ldots,(x_n,y_n)) is realizable under a concept class H\mathcal{H} if

min⁡h∈H∑i=1n1[h(xi)≠yi]=0.(1)\min_{h\in\mathcal{H}} \sum_{i=1}^{n} \mathbb{1}[h(x_i) \ne y_i] = 0. \tag*{(1)}

Let FLrn⁡∈(S×(Y∪{⋆}))∗F_{\operatorname{Lrn}} \in(S \times(\mathcal{Y} \cup\{\star\}))^* be the learner’s history. Let FAdv⁡∈(S×Y)∗F_{\operatorname{Adv}} \in(S \times\mathcal{Y})^* be adversary’s history. We say an adversary is consistent with H\mathcal{H} if every history FAdv⁡F_{\operatorname{Adv}} that could arise under their strategy is realizable under H\mathcal{H}.

We now define the optimal mistake bound against consistent adversaries, commonly known as the realizable setting.

Definition 3.3. For a learner Lrn⁡\operatorname{Lrn} and an adversary Adv⁡\operatorname{Adv}, let FLrn⁡(i)F_{\operatorname{Lrn}}^{(i)} and FAdv⁡(i)F_{\operatorname{Adv}}^{(i)} denote the respective histories at the start of round ii and let

xi∼Lrn⁡x(FLrn⁡(i))yi∼Adv⁡(FAdv⁡(i),xi)y^i∼Lrn⁡y(FLrn⁡(i),xi)x_i \sim\operatorname{Lrn}_x\left(F_{\operatorname{Lrn}}^{(i)}\right) \qquad y_i \sim\operatorname{Adv}\left(F_{\operatorname{Adv}}^{(i)},x_i\right) \qquad \hat{y}_i \sim\operatorname{Lrn}_y\left(F_{\operatorname{Lrn}}^{(i)},x_i\right)

denote, the instance selected by the learner, the label chosen by the adversary, and the label predicted by the learner in round ii respectively.

Let a finite multiset S⊆XS \subseteq\mathcal{X} of size nn be given to the learner. Let the game last for mm rounds. We define the expected number of mistakes the learner makes against the adversary by

M(S,Lrn⁡,Adv⁡)=E[∑i=1m1[y^i≠yi]](2)M(S,\operatorname{Lrn},\operatorname{Adv}) = \mathbb{E}\left[\sum_{i=1}^{m} \mathbb{1}[\hat{y}_i \ne y_i]\right] \tag*{(2)}

The learner’s history evolves as

FLrn⁡(i+1)={FLrn⁡(i)∘(xi,yi)if y^i=1,FLrn⁡(i)∘(xi,⋆)if y^i=0F_{\operatorname{Lrn}}^{(i+1)} = \begin{cases} F_{\operatorname{Lrn}}^{(i)} \circ(x_i,y_i) & \text{if } \hat{y}_i = 1,\\ F_{\operatorname{Lrn}}^{(i)} \circ(x_i,\star) & \text{if } \hat{y}_i = 0 \end{cases}

and the adversary’s history evolves as

FAdv⁡(i+1)=FAdv⁡(i)∘(xi,yi)F_{\operatorname{Adv}}^{(i+1)} = F_{\operatorname{Adv}}^{(i)} \circ(x_i,y_i)

where FLrn(0)=FAdv(0)=∅F_{\mathrm{Lrn}}^{(0)} = F_{\mathrm{Adv}}^{(0)} = \emptyset.

We define the optimal mistake bound of H\mathcal{H} against an adversary providing apple-tasting feedback on SS by

M(H,S)=inf⁡Lrnsup⁡AdvM(S,Lrn,Adv)(3)M(\mathcal{H},S) = \inf_{\mathrm{Lrn}} \sup_{\mathrm{Adv}} M(S,\mathrm{Lrn},\mathrm{Adv}) \tag*{(3)}

where the supremum is taken over all adversaries which are consistent with H\mathcal{H}.

Finally, we define the optimal mistake bound over over all finite submultisets of X\mathcal{X} of size at most nn by

Moptimal(H,n)=sup⁡S⊆X,∣S∣≤nM(H,S)(4)M_{\mathrm{optimal}}(\mathcal{H},n) = \sup_{S \subseteq\mathcal{X}, |S| \le n} M(\mathcal{H},S) \tag*{(4)}

Definition 3.4. We say that a concept class H\mathcal{H} is learnable under the realizable setting of self-directed online learning with apple-tasting feedback (or learnable, in short) if Moptimal(H,n)∈o(n)2M_{\mathrm{optimal}}(\mathcal{H},n) \in o(n)^2, and not learnable if Moptimal(H,n)∈Ω(n)M_{\mathrm{optimal}}(\mathcal{H},n) \in\Omega(n).

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 Lrn\mathrm{Lrn}, the adversary Adv\mathrm{Adv}, the history of the learner FLrn(i)F_{\mathrm{Lrn}}^{(i)}, the history of the adversary FAdv(i)F_{\mathrm{Adv}}^{(i)}, the instance selected by the learner xix_i, the label chosen by the adversary yiy_i and the label predicted by the learner y^i\hat{y}_i in round ii are exactly the same as in Definition 3.3.

For a given finite multiset S⊆XS \subseteq\mathcal{X} of size nn, let the game go on for mm rounds. We define the expected regret of the learner against the adversary as

R(S,Lrn,Adv)=E[∑i=1m1[y^i≠yi]−inf⁡h∈H∑i=1m1[h(xi)≠yi]](5)R(S,\mathrm{Lrn},\mathrm{Adv}) = \mathbb{E}\left[\sum_{i=1}^{m} \mathbf{1}[\hat{y}_i \ne y_i] - \inf_{h \in\mathcal{H}} \sum_{i=1}^{m} \mathbf{1}[h(x_i) \ne y_i]\right] \tag*{(5)}

We define the optimal expected regret of H\mathcal{H} against an adversary providing apple-tasting feedback on SS by

R(H,S)=inf⁡Lrnsup⁡AdvR(S,Lrn,Adv)(6)R(\mathcal{H},S) = \inf_{\mathrm{Lrn}} \sup_{\mathrm{Adv}} R(S,\mathrm{Lrn},\mathrm{Adv}) \tag*{(6)}

where the supremum is taken over all adversaries.

Finally, we define the optimal mistake bound over all finite submultisets of X\mathcal{X} of size at most nn by

Roptimal(H,n)=sup⁡S⊆X,∣S∣≤nR(H,S)(7)R_{\mathrm{optimal}}(\mathcal{H},n) = \sup_{S \subseteq\mathcal{X}, |S| \le n} R(\mathcal{H},S) \tag*{(7)}

Definition 3.6. We say that a concept class H\mathcal{H} is learnable under self-directed online learning with apple-tasting feedback in the agnostic setting (or agnostic learnable, in short) if Roptimal(H,n)∈o(n)R_{\mathrm{optimal}}(\mathcal{H},n) \in o(n), and not agnostic learnable if Roptimal(H,n)∈Ω(n)R_{\mathrm{optimal}}(\mathcal{H},n) \in\Omega(n).

For the sake of completeness, we restate the definition of VC dimension, ∅\emptyset-centered star number, and self-directed dimension.

Definition 3.7 (VC dimension Vapnik and Chervonenkis, [26]). A set SS is VC-shattered by a concept class H\mathcal{H} if the projection of H\mathcal{H} onto SS, i.e., H∣S\mathcal{H}|_S, has size 2∣S∣2^{|S|}. The VC dimension of H\mathcal{H}, denoted VC(H)\mathrm{VC}(\mathcal{H}), is the size of the largest set that H\mathcal{H} VC-shatters, or ∞\infty if no such largest set exists.

Definition 3.8 (∅-centered star number Hanneke and Yang, [17], Hanneke, [16]). A set SS is ∅-centered star-shattered by a concept class H\mathcal H if:

  1. There exists a concept h∈Hh \in\mathcal H such that h(x)=0h(x) = 0 for all x∈Sx \in S; and

  2. For every y∈Sy \in S, there exists a concept h∈Hh \in\mathcal H such that h(y)=1h(y) = 1 and h(x)=0h(x) = 0 for all x∈S∖{y}x \in S \setminus\{y\}.

The ∅-centered star number of H\mathcal H, denoted s∅(H)s_{\emptyset}(\mathcal H), is the size of the largest set that H\mathcal H ∅-centered star-shatters, or ∞\infty 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 H\mathcal H on a finite multiset SS, let V⊆H\mathcal V \subseteq\mathcal H. We define M(V,S)M(\mathcal V,S) by Mfull(V,S)=0M_{\mathrm{full}}(\mathcal V,S)=0 whenever ∣V∣S∣≤1|\mathcal V|_S| \le1, and otherwise

Mfull(V,S)=min⁡x∈Smin⁡y^∈{0,1}max⁡y∈{0,1}[1[y^≠y]+Mfull(Vx→y,S∖{x})].M_{\mathrm{full}}(\mathcal V,S)=\min_{x\in S}\min_{\hat y\in\{0,1\}}\max_{y\in\{0,1\}}\left[\mathbb{1}[\hat y \ne y]+M_{\mathrm{full}}(\mathcal V_{x\to y},S\setminus\{x\})\right].

The recursion terminates since ∣S∣|S| strictly decreases. The dimension of self-directed learning of H\mathcal H is SDdim⁡(H)=sup⁡SMfull(H∣S,S)\operatorname{SDdim}(\mathcal H)=\sup_S M_{\mathrm{full}}(\mathcal H|_S,S), the supremum over finite multisets SS.

When SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal H)<\infty, Devulapalli and Hanneke [ [11] provide a deterministic algorithm that makes at most SDdim⁡(H)\operatorname{SDdim}(\mathcal H) mistakes on any input. We call this the SDSolver algorithm and use it as a black box.

Definition 3.10 (Union-closure). Let H\mathcal H be a nonempty concept class. For a subset T⊆H\mathcal T \subseteq\mathcal H, let hTh_{\mathcal T} denote the concept for which hT(x)=1h_{\mathcal T}(x)=1 if and only if h(x)=1h(x)=1 for some h∈Th\in\mathcal T. Then the union-closure U(H)\mathcal U(\mathcal H) of H\mathcal H is U(H)={hT:T⊆H,T≠∅}\mathcal U(\mathcal H)=\{h_{\mathcal T}:\mathcal T\subseteq\mathcal H,\mathcal T\ne\emptyset\}.

Unless stated otherwise, OO, Ω\Omega, Θ\Theta hide universal constants which do not depend on any parameter of the problem. Notation such as ΘH\Theta_{\mathcal H} indicates that the implied constants depend on the concept class H\mathcal H.

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 H\mathcal H exactly one of the following holds:

  • H\mathcal H is not learnable, i.e. Moptimal(H,n)∈Ω(n)M_{\mathrm{optimal}}(\mathcal H,n)\in\Omega(n).

  • H\mathcal H is learnable with Moptimal(H,n)∈Θ~H(n)M_{\mathrm{optimal}}(\mathcal H,n)\in\widetilde{\Theta}_{\mathcal H}(\sqrt n).

  • H\mathcal H is learnable with Moptimal(H,n)∈OH(log⁡n)∩ωH(1)M_{\mathrm{optimal}}(\mathcal H,n)\in O_{\mathcal H}(\log n)\cap\omega_{\mathcal H}(1).

  • H\mathcal H is learnable with Moptimal(H,n)∈ΘH(1)M_{\mathrm{optimal}}(\mathcal H,n)\in\Theta_{\mathcal H}(1).

A second main result of this work provides a detailed description of which of these four cases any given concept class H\mathcal H belongs to, by specifying complexity measures to distinguish the cases.

We use the well-known Vapnik Chervonenkis dimension denoted VC⁡(H)\operatorname{VC}(\mathcal H) as defined in Vapnik and Chervonenkis [ [26], the ∅-centered star number, denoted s∅(H)s_{\emptyset}(\mathcal H) as defined in Hanneke and Yang [ [17], and the self-directed dimension SDdim⁡(H)\operatorname{SDdim}(\mathcal H) as defined in Devulapalli and Hanneke [ [11] to characterize the various cases.

Theorem 4.2. Every concept class H\mathcal{H} falls into one of the following four cases:

  • If VC⁡(H)=∞\operatorname{VC}(\mathcal{H}) = \infty then H\mathcal{H} is not learnable, i.e. Moptimal⁡(H,n)∈Ω(n)M_{\operatorname{optimal}}(\mathcal{H}, n) \in\Omega(n).

  • If VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty and s∅(H)=∞s_{\varnothing}(\mathcal{H}) = \infty then H\mathcal{H} is learnable with Moptimal⁡(H,n)∈Θ~H(n)M_{\operatorname{optimal}}(\mathcal{H}, n) \in\widetilde{\Theta}_{\mathcal{H}}(\sqrt{n}).

  • If s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty and SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty then H\mathcal{H} is learnable with Moptimal⁡(H,n)∈OH(log⁡n)∩ωH(1)M_{\operatorname{optimal}}(\mathcal{H}, n) \in O_{\mathcal{H}}(\log n) \cap\omega_{\mathcal{H}}(1).

  • If s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty and SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H}) < \infty then H\mathcal{H} is learnable with Moptimal⁡(H,n)∈ΘH(1)M_{\operatorname{optimal}}(\mathcal{H}, n) \in\Theta_{\mathcal{H}}(1).

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 VC⁡(H)=∞\operatorname{VC}(\mathcal{H}) = \infty then H\mathcal{H} is not learnable, i.e. Moptimal⁡(H,n)∈Ω(n)M_{\operatorname{optimal}}(\mathcal{H}, n) \in\Omega(n).

Proof. Let n∈Nn \in\mathbb{N} and let SS be a shattered set of size nn. The adversary then gives SS to the learner and chooses its labels uniformly at random. Since SS is shattered by H\mathcal{H}, these labels are realizable. The learner then averages half a mistake per round, so Moptimal⁡(H,n)≥n/2∈Ω(n)M_{\operatorname{optimal}}(\mathcal{H}, n) \ge n/2 \in\Omega(n).

Upper Bounds

We now consider the interesting regimes of VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty, s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty, or SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H}) < \infty.7 We first show the upper bounds.

VC finite

Algorithm 1 PRUNE-AND-EAT(H,S)(\mathcal{H}, S)

  1. V←H∣S\mathcal{V} \leftarrow\mathcal{H}|_S, n←∣S∣n \leftarrow|S| ▷ version space: projection of H\mathcal{H} onto SS

  2. while SS is not empty:

  3. J←{h∈V:∑x∈Sh(x)≤VC⁡(H) nlog⁡n}\mathcal{J} \leftarrow\{h \in\mathcal{V} : \sum_{x \in S} h(x) \le\sqrt{\operatorname{VC}(\mathcal{H})\,n\log n}\} ▷ sparse concepts

  4. V←V∖J\mathcal{V} \leftarrow\mathcal{V} \setminus\mathcal{J}

  5. if V=∅\mathcal{V} = \varnothing then break

  6. a←arg⁡max⁡x∈S∑h∈Vh(x)a \leftarrow\arg\max_{x \in S}\sum_{h \in\mathcal{V}} h(x) ▷ best apple

  7. Predict y^=1\hat{y} = 1 on aa and receive the true label yy

  8. S←S∖{a}S \leftarrow S \setminus\{a\}

  9. V←{h∈V:h(a)=y}∣S\mathcal{V} \leftarrow\{h \in\mathcal{V}: h(a) = y\}|_S

  10. if ∣S∣>0|S| > 0 then predict y^=0\hat{y} = 0 on every remaining x∈Sx \in S. ▷ no further feedback

We first consider the regime in which VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty. 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 tt-fraction of the version space for t=VC⁡(H)log⁡n/nt = \sqrt{\operatorname{VC}(\mathcal{H})}\log n/n. Hence, whenever eating it results in a mistake, that entire tt-fraction of concepts is inconsistent with the revealed label and is eliminated. We now state and prove this formally.

Theorem 4.4. Let H\mathcal{H} be a concept class with VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty. Then H\mathcal{H} is learnable by algorithm PRUNE-AND-EAT. Furthermore, we obtain a bound on the optimal number of mistakes

Moptimal(H,n)≤2VC⁡(H) nlog⁡n+1.M_{\mathrm{optimal}}(\mathcal{H}, n) \le2\sqrt{\operatorname{VC}(\mathcal{H})\,n\log n}+1.

Proof. Let S=(x1,…,xn)S=(x_1,\ldots,x_n) be the points chosen by the adversary. Let h∗∈Hh^*\in\mathcal{H} denote the (unknown) true labeling concept. Let V0=H∣S\mathcal{V}_0=\mathcal{H}|_S be the initial version space, and for i≥1i\ge1 let Vi\mathcal{V}_i denote the version space at the start of round ii and Vipruned\mathcal{V}_i^{\mathrm{pruned}} its state immediately after the pruning step of that round. Let SiS_i denote the data set in the iith round. Every mistake the algorithm makes is of exactly one of two types, according to its prediction:

  • M1M_1: mistakes on points the algorithm eats, i.e. y^=1\hat{y}=1 while h∗(a)=0h^*(a)=0;

  • M2M_2: mistakes on points the algorithm defaults to 0 on after exiting the loop i.e. y^=0\hat{y}=0 while h∗(x)=1h^*(x)=1.

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 M1+M2M_1+M_2.

Key observation. Fix a round ii and consider the version space Vi\mathcal{V}_i before pruning. We remove the concepts that are sparse: i.e., if the number of points in SS a concept labels as 1 is less than VC⁡(H)nlog⁡n\sqrt{\operatorname{VC}(\mathcal{H})n\log n}, then we remove that concept to obtain Vipruned\mathcal{V}_i^{\mathrm{pruned}}. We note that by construction every h∈Viprunedh\in\mathcal{V}_i^{\mathrm{pruned}} satisfies

∑x∈Sh(x)>VC⁡(H)nlog⁡n.\sum_{x\in S}h(x)>\sqrt{\operatorname{VC}(\mathcal{H})n\log n}.

Summing over all h∈Viprunedh\in\mathcal{V}_i^{\mathrm{pruned}} and exchanging the order of summation,

∑x∈Si∑h∈Viprunedh(x)=∑h∈Vipruned∑x∈Sih(x)>∣Vipruned∣⋅VC⁡(H)nlog⁡n.\sum_{x\in S_i}\sum_{h\in\mathcal{V}_i^{\mathrm{pruned}}}h(x) =\sum_{h\in\mathcal{V}_i^{\mathrm{pruned}}}\sum_{x\in S_i}h(x) >\left|\mathcal{V}_i^{\mathrm{pruned}}\right|\cdot\sqrt{\operatorname{VC}(\mathcal{H})n\log n}.

Since ∣Si∣≤n|S_i|\le n, averaging over the points of SiS_i show that some x∈Six\in S_i satisfies

∑h∈Viprunedh(x)>∣Vipruned∣n⋅VC⁡(H)nlog⁡n=∣Vipruned∣⋅VC⁡(H)log⁡nn.\sum_{h\in\mathcal{V}_i^{\mathrm{pruned}}}h(x)> \frac{\left|\mathcal{V}_i^{\mathrm{pruned}}\right|}{n}\cdot\sqrt{\operatorname{VC}(\mathcal{H})n\log n} =\left|\mathcal{V}_i^{\mathrm{pruned}}\right|\cdot\sqrt{\frac{\operatorname{VC}(\mathcal{H})\log n}{n}}.

Therefore after pruning, some point in SS is labeled 1 by at least a t=VC⁡(H)log⁡nnt=\sqrt{\frac{\operatorname{VC}(\mathcal{H})\log n}{n}} fraction of the surviving hypotheses. In particular, the point aa chosen by the algorithm, which maximizes this count, satisfies this bound as well. Note that we can assume t<1t<1; if t≥1t\ge1, then n≤VC⁡(H)nlog⁡nn\le\sqrt{\operatorname{VC}(\mathcal{H})n\log n}, so the claimed mistake bound is trivial.

Bounding M1M_1. Suppose the algorithm eats aa in round ii and makes a mistake, so the revealed label is y=0y=0. By the key observation, more than a tt-fraction of Vipruned\mathcal{V}_i^{\mathrm{pruned}} labels aa as 1; every such concept is inconsistent with yy and is removed. Hence

∣Vi+1∣≤(1−t)∣Vipruned∣≤(1−t)∣Vi∣,|\mathcal{V}_{i+1}|\le(1-t)|\mathcal{V}_i^{\mathrm{pruned}}|\le(1-t)|\mathcal{V}_i|,

using Vipruned⊆Vi\mathcal{V}_i^{\mathrm{pruned}}\subseteq\mathcal{V}_i. Version spaces are non-increasing across all other rounds, so we can chain this inequality over the M1M_1 rounds on which an eating mistake occurs. Let i∗i^* denote the last round completed before the loop terminates. The loop breaks only upon detecting that V\mathcal{V} is empty, so the version space at the start of that round i.e. Vi∗\mathcal{V}_{i^*} is nonempty, giving ∣Vi∗∣≥1|\mathcal{V}_{i^*}|\ge1. Hence,

1≤∣Vi∗∣≤(1−t)M1−1∣V0∣.1\le|\mathcal{V}_{i^*}|\le(1-t)^{M_1-1}|\mathcal{V}_0|.

We now use Sauer’s Lemma, giving ∣V0∣≤nVC⁡(H)|\mathcal{V}_0|\le n^{\operatorname{VC}(\mathcal{H})}, and take logarithms to obtain

VC⁡(H)log⁡n+(M1−1)log⁡(1−t)≥0.\operatorname{VC}(\mathcal{H})\log n+(M_1-1)\log(1-t)\ge0.

Using log⁡(1−t)≤−t\log(1-t) \le-t for t∈(0,1)t \in(0,1),

VC⁡(H)log⁡n≥(M1−1)t=(M1−1)VC⁡(H)log⁡nn⟹M1≤VC⁡(H)nlog⁡n+1.\operatorname{VC}(\mathcal{H}) \log n \ge(M_1-1)t = (M_1-1)\sqrt{\frac{\operatorname{VC}(\mathcal{H})\log n}{n}} \quad\Longrightarrow\quad M_1 \le\sqrt{\operatorname{VC}(\mathcal{H})n\log n}+1.

Bounding M2M_2. If the loop terminates with S=∅S=\varnothing then every point was eaten, no point receives the default prediction, and M2=0M_2=0. So suppose the loop terminates with V=∅V=\varnothing in some round jj. Since h∗h^* is consistent with every revealed label, it stays in the version space; the only step that can remove it is pruning. Hence if M2>0M_2>0, then h∗∈Jh^*\in\mathcal{J} at some round k≤jk\le j, which means ∑x∈Skh∗(x)≤VC⁡(H)nlog⁡n\sum_{x\in S_k}h^*(x)\le\sqrt{\operatorname{VC}(\mathcal{H})n\log n}. The points receiving the default prediction 0 are exactly those remaining at termination, and Sj⊆SkS_j\subseteq S_k since SS only shrinks. Each such mistake occurs at a point xx with h∗(x)=1h^*(x)=1, so

M2=∑x∈Sjh∗(x)≤∑x∈Skh∗(x)≤VC⁡(H)nlog⁡n.M_2=\sum_{x\in S_j}h^*(x)\le\sum_{x\in S_k}h^*(x)\le\sqrt{\operatorname{VC}(\mathcal{H})n\log n}.

Total mistakes. Combining the two bounds,

Moptimal⁡(H,n)≤M1+M2≤2VC⁡(H)nlog⁡n+1.M_{\operatorname{optimal}}(\mathcal{H},n)\le M_1+M_2\le2\sqrt{\operatorname{VC}(\mathcal{H})n\log n}+1.

We now consider the case where s∅(H)<∞s_{\varnothing}(\mathcal{H})<\infty. The following theorem will help us resolve the O(log⁡n)O(\log n) and O(1)O(1) regimes at the same time.

Theorem 4.5. For a concept class H\mathcal{H},

Moptimal⁡(H,n)≤min⁡{s∅(H)⋅SDdim⁡(H),1cs∅(H)log⁡n}.M_{\operatorname{optimal}}(\mathcal{H},n)\le\min\left\{s_{\varnothing}(\mathcal{H})\cdot\operatorname{SDdim}(\mathcal{H}),\frac{1}{c}s_{\varnothing}(\mathcal{H})\log n\right\}.

We will prove Theorem 4.5 in two cases: SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H})=\infty and SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H})<\infty.

SDDim infinite

We will prove Theorem 4.5 in two cases: SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H})=\infty and SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H})<\infty.

SDdim(H\mathcal{H}) = ∞\infty, s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty
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 V\mathcal{V} directly, we pass to its union closure U(V)\mathcal{U}(\mathcal{V}), obtained by taking all pointwise-OR combinations of subsets of V\mathcal{V}. Learning H\mathcal{H} is no harder than learning U(H)\mathcal{U}(\mathcal{H}) since H⊆U(H)\mathcal{H}\subseteq\mathcal{U}(\mathcal{H}), so any mistake bound for U(H)\mathcal{U}(\mathcal{H}) upper bounds the mistake bound for H\mathcal{H}. The advantage of passing to U(H)\mathcal{U}(\mathcal{H}) 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 s∅(H)s_{\varnothing}(\mathcal{H}).

Lemma 4.6. For any concept class H\mathcal{H}, s∅(H)=s∅(U(H))s_{\varnothing}(\mathcal{H})=s_{\varnothing}(\mathcal{U}(\mathcal{H})).

Proof. (≥)(\ge) Let s=s∅(U(H))s=s_{\emptyset}(\mathcal{U}(\mathcal{H})), and let P={p1,…,ps}P=\{p_1,\ldots,p_s\} be ∅\emptyset-centered star-shattered in U(H)\mathcal{U}(\mathcal{H}). Let g0∈U(H)g_0\in\mathcal{U}(\mathcal{H}) be the center: i.e. g0(pj)=0g_0(p_j)=0 for all j∈[s]j\in[s]. Let g1,…,gs∈U(H)g_1,\ldots,g_s\in\mathcal{U}(\mathcal{H}) be the witnesses: i.e. for all i∈[s]i\in[s], we have gi(pi)=1g_i(p_i)=1 and gi(pj)=0g_i(p_j)=0 for all j≠ij\ne i.

We claim that H\mathcal{H} also ∅\emptyset-centered star-shatters PP. For the center, write g0=h0,1∨⋯∨h0,m0g_0=h_{0,1}\vee\cdots\vee h_{0,m_0} for some h0,1,…,h0,m0∈Hh_{0,1},\ldots,h_{0,m_0}\in\mathcal{H}. Because g0(pj)=0g_0(p_j)=0 for every j∈[s]j\in[s], and a union of concepts is 0 at a point only if every concept in the union is 0 there, each h0,kh_{0,k} satisfies h0,k(pj)=0h_{0,k}(p_j)=0 for all j∈[s]j\in[s].

We can similarly extract the witnesses from the other gig_i. Fix i∈[s]i\in[s] and write gi=hi,1∨⋯∨hi,mig_i=h_{i,1}\vee\cdots\vee h_{i,m_i} for some hi,1,…,hi,mi∈Hh_{i,1},\ldots,h_{i,m_i}\in\mathcal{H}. Since gi(pj)=0g_i(p_j)=0 for every j≠ij\ne i, each hi,kh_{i,k} satisfies hi,k(pj)=0h_{i,k}(p_j)=0 for all j≠ij\ne i. Since gi(pi)=1g_i(p_i)=1, at least one hi,ki∈Hh_{i,k_i}\in\mathcal{H} satisfies hi,ki(pi)=1h_{i,k_i}(p_i)=1. Combining these two facts, hi,ki∈Hh_{i,k_i}\in\mathcal{H} agrees with g0g_0 everywhere on PP except at pip_i, where it equals 1. Repeating this for every i∈[s]i\in[s] produces concepts h1,k1,…,hs,ks∈Hh_{1,k_1},\ldots,h_{s,k_s}\in\mathcal{H} that, together with h0,1∈Hh_{0,1}\in\mathcal{H}, ∅\emptyset-centered star-shatter PP. Hence s∅(H)≥s=s∅(U(H))s_{\emptyset}(\mathcal{H})\ge s=s_{\emptyset}(\mathcal{U}(\mathcal{H})).

(≤)(\le) Since U(H)\mathcal{U}(\mathcal{H}) contains the singleton union of each concept in H\mathcal{H}, we have H⊂U(H)\mathcal{H}\subset\mathcal{U}(\mathcal{H}). Hence any set ∅\emptyset-centered star-shattered by H\mathcal{H} is also shattered by U(H)\mathcal{U}(\mathcal{H}), so s∅(U(H))≥s∅(H)s_{\emptyset}(\mathcal{U}(\mathcal{H}))\ge s_{\emptyset}(\mathcal{H}).

Lemma 4.7. If H\mathcal{H} is a union-closed concept class then VC⁡(H)=s∅(H)\operatorname{VC}(\mathcal{H})=s_{\emptyset}(\mathcal{H}).

Proof. (≥)(\ge) Let s=s∅(H)s=s_{\emptyset}(\mathcal{H}), and let P={p1,…,ps}P=\{p_1,\ldots,p_s\} be ∅\emptyset-centered star-shattered by center h0h_0 and witnesses h1,…,hs∈Uh_1,\ldots,h_s\in\mathcal{U}: h0h_0 labels every point of PP as 0, and hih_i agrees with h0h_0 except that hi(pi)=1h_i(p_i)=1.

We claim that H\mathcal{H} shatters PP. The concept h0h_0 realizes the all-zero labeling of PP. For any nonzero target labeling y=(y1,…,ys)∈{0,1}sy=(y_1,\ldots,y_s)\in\{0,1\}^s of PP, let W={hi:yi=1}⊆{h1,…,hs}W=\{h_i:y_i=1\}\subseteq\{h_1,\ldots,h_s\}. Let hW=⋁h∈Whh_W=\bigvee_{h\in W}h. Because H\mathcal{H} is union-closed and WW is nonempty, we have hW∈Hh_W\in\mathcal{H}. Since each hih_i labels only pip_i as 1 among PP, hW(pi)=1h_W(p_i)=1 if and only if hi∈Wh_i\in W which is if and only if yi=1y_i=1. Hence H\mathcal{H} realizes every labeling of PP, so VC⁡(H)≥s\operatorname{VC}(\mathcal{H})\ge s.

(≤)(\le) Let v=VC⁡(H)v=\operatorname{VC}(\mathcal{H}), and let S′={q1,…,qv}S'=\{q_1,\ldots,q_v\} be shattered by H\mathcal{H}. By shattering, for each i∈[v]i\in[v] there is a concept gi∈Hg_i\in\mathcal{H} realizing the labeling that assigns qi↦1q_i\mapsto1 and qj↦0q_j\mapsto0 for j≠ij\ne i. There is also a concept g0∈Hg_0\in\mathcal{H} realizing the all-0 labeling. Then S′S' is ∅\emptyset-centered star-shattered by center g0g_0 and witnesses g1,…,gvg_1,\ldots,g_v, so s∅(H)≥vs_{\emptyset}(\mathcal{H})\ge v.

Proposition 1. There is a universal constant c>0c>0 such that for every finite union-closed class H\mathcal{H} of concepts (other than the trivial class), some point xx satisfies

∣{h∈H:h(x)=1}∣≥c⋅∣H∣.\left|\{h\in\mathcal{H}:h(x)=1\}\right|\ge c\cdot|\mathcal{H}|.

We use cc as a placeholder for the best constant available. At the time of writing Gilmer [ [13] establish c=0.01c=0.01, Chase and Lovett [ [9], Pebody [ [22], Sawin [ [24], Alweiss et al. [ [2] establish c=3−52≈0.38197c=\frac{3-\sqrt{5}}{2}\approx0.38197, and finally Liu [ [21] establish c=0.38271c=0.38271. Please refer to Bruhn and Schaudt [ [6] for the history of union-closed set conjecture (also known as Frankl's conjecture) which suggests c=12c=\frac{1}{2}. The exact value is not relevant for our purposes as long as c>0c>0.

Theorem 4.8. Let H\mathcal{H} be a concept class with s∅(H)<∞s_{\emptyset}(\mathcal{H})<\infty. Then H\mathcal{H} is learnable by algorithm Union-And-Eat. Furthermore, we obtain a bound on the optimal number of mistakes

Moptimal(H,n)≤1cs∅(H)log⁡n,M_{\mathrm{optimal}}(\mathcal{H},n)\le\frac{1}{c}s_{\emptyset}(\mathcal{H})\log n,

where c∈(0,1/2]c\in(0,1/2] is the universal constant from the union-closed set conjecture (Proposition 1).

Proof. For i≥1i\ge1, let Vi\mathcal{V}_i denote the version space at the start of the iith 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 Vi\mathcal{V}_i. 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 Vi\mathcal{V}_i are all union-closed. We show this by induction on ii. As a base case, the initial version space V1\mathcal{V}_1 is the projection of the union-closed concept class U(H)\mathcal{U}(\mathcal{H}) onto SS, so it is union-closed. Now assume Vi\mathcal{V}_i is union-closed for some fixed ii. The next version space Vi+1\mathcal{V}_{i+1} is constructed in two steps:

  • First, it is restricted to the concepts which map aa to the true label yy. Let h1,h2h_1,h_2 be two such concepts. Since Vi\mathcal{V}_i is union-closed, we have h1∨h2∈Vih_1 \lor h_2 \in\mathcal{V}_i. Moreover, since (h1∨h2)(a)=h1(a)∨h2(a)=y∨y=y(h_1 \lor h_2)(a) = h_1(a) \lor h_2(a) = y \lor y = y, it remains in the version space.

  • Second, it is projected onto S∖{a}S \setminus\{a\}. As in the base case, this projection preserves union-closure.

Therefore we can guarantee that the point aa selected in each round of UNION-AND-EAT satisfies ∣{h∈Vi:h(a)=1}∣≥c⋅∣Vi∣|\{h \in\mathcal{V}_i : h(a) = 1\}| \ge c \cdot|\mathcal{V}_i|, where cc is the constant in Proposition 1. Whenever the algorithm makes a mistake at aa its true label is 00, so every h∈Vih \in\mathcal{V}_i with h(a)=1h(a) = 1 is inconsistent and is discarded from the next round’s version space. Let MM be the number of mistakes made in total. Since no Vi\mathcal{V}_i is empty, we have:

(1−c)M⋅∣V1∣≥1,(1-c)^M \cdot|\mathcal{V}_1| \ge1,

By Lemmas 4.6 and 4.7, we have VC⁡(V1)=s∅(V1)=s∅(H∣S)≤s∅(H)\operatorname{VC}(\mathcal{V}_1) = s_{\emptyset}(\mathcal{V}_1) = s_{\emptyset}(\mathcal{H}|_S) \le s_{\emptyset}(\mathcal{H}), so by Sauer’s Lemma:

∣V1∣≤nVC⁡(V1)≤ns∅(H).|\mathcal{V}_1| \le n^{\operatorname{VC}(\mathcal{V}_1)} \le n^{s_{\emptyset}(\mathcal{H})}.

Taking logarithms and using log⁡(1−c)≤−c\log(1-c) \le-c, we obtain

0≤s∅(H)log⁡n−cM⟹M≤1cs∅(H)log⁡n.0 \le s_{\emptyset}(\mathcal{H}) \log n - cM \Longrightarrow M \le\frac{1}{c}s_{\emptyset}(\mathcal{H})\log n.

So algorithm UNION-AND-EAT makes at most 1cs∅(H)log⁡n\frac{1}{c}s_{\emptyset}(\mathcal{H})\log n mistakes as desired.

SDDim finite

Algorithm 3 FIRST-MISTAKE(V,(x1,x2,…,xb),xb+1)(\mathcal{V},(x_1,x_2,\ldots,x_b),x_{b+1})

  1. mis⁡←∞\operatorname{mis} \leftarrow\infty

  2. if xb+1≠⊥x_{b+1} \ne\perp then

  3. &nbsp;&nbsp;&nbsp;&nbsp;Predict y^=1\hat{y}=1 for xb+1x_{b+1} and obtain the true label yy.

  4. &nbsp;&nbsp;&nbsp;&nbsp;if y=1y=1 then return ⊥\perp.

  5. &nbsp;&nbsp;&nbsp;&nbsp;V←Vxb+1→0\mathcal{V} \leftarrow\mathcal{V}_{x_{b+1}\to0}, mis⁡←b+1\operatorname{mis} \leftarrow b+1

  6. Let f(h)=min⁡{j∈[b]:h(xj)=1}f(h)=\min\{j\in[b]:h(x_j)=1\} for all h∈Vh\in\mathcal{V}, with min⁡∅=∞\min\varnothing=\infty.

  7. while there is some h∈Vh\in\mathcal{V} such that f(h)<mis⁡f(h)<\operatorname{mis} do

  8. &nbsp;&nbsp;&nbsp;&nbsp;Let j=max⁡{f(h):h∈V,f(h)<mis⁡}j=\max\{f(h):h\in\mathcal{V},f(h)<\operatorname{mis}\}

  9. &nbsp;&nbsp;&nbsp;&nbsp;Predict y^=1\hat{y}=1 at xjx_j and obtain the true label yy.

  10. &nbsp;&nbsp;&nbsp;&nbsp;V←Vxj→y\mathcal{V} \leftarrow\mathcal{V}_{x_j\to y}

  11. &nbsp;&nbsp;&nbsp;&nbsp;if y=1y=1 then mis⁡←j\operatorname{mis}\leftarrow j

  12. if mis⁡=∞\operatorname{mis}=\infty then return ⊥\perp else return xmis⁡x_{\operatorname{mis}}

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 s∅(H)s_{\varnothing}(\mathcal{H}) 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 SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}) mistakes. Therefore, we obtain the true concept in at most s∅(H)×SDdim⁡(H)s_{\varnothing}(\mathcal{H}) \times\operatorname{SDdim}(\mathcal{H}) 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 s∅(H)s_{\varnothing}(\mathcal{H}) mistakes.

Lemma 4.9. Let (x1,…,xb),xb+1(x_1, \ldots, x_b), x_{b+1} be points provided to FIRST-MISTAKE. Let V\mathcal{V} be a version space such that h∗∈Vh^* \in\mathcal{V} and there exists hb∈Vh^b \in\mathcal{V} such that hb(xi)=0h^b(x_i) = 0 for all i∈[b]i \in[b] and, if xb+1≠⊥x_{b+1} \ne\bot, then hb(xb+1)=1h^b(x_{b+1}) = 1. Let

j∗=min⁡{j∈[b]:h∗(xj)=1} or ∞ if no such point existsj^* = \min\{j \in[b] : h^*(x_j) = 1\} \text{ or } \infty\text{ if no such point exists}

Then one of these three cases occurs:

  • If h∗(xb+1)=1h^*(x_{b+1}) = 1 then FIRST-MISTAKE returns ⊥\bot and makes no mistakes.

  • If h∗(xb+1)=0h^*(x_{b+1}) = 0 then FIRST-MISTAKE returns xmin⁡{j∗,b+1}x_{\min\{j^*,b+1\}} and makes at most s∅(V)s_{\varnothing}(\mathcal{V}) mistakes.

  • If xb+1=⊥x_{b+1} = \bot then FIRST-MISTAKE returns xj∗x_{j^*} if j∗<∞j^* < \infty and ⊥\bot otherwise. It also makes at most s∅(V)s_{\varnothing}(\mathcal{V}) mistakes.

Proof. Throughout, every update is of the form V←Vx→y\mathcal{V} \leftarrow\mathcal{V}_{x \to y} where yy is the true label revealed at xx; hence h∗∈Vh^* \in\mathcal{V} at all times, and V\mathcal{V} only shrinks. Note also that f(h)=min⁡{j∈[b]:h(xj)=1}f(h) = \min\{j \in[b] : h(x_j) = 1\} depends only on hh, so it is unaffected by these updates.

Case 1: h∗(xb+1)=1h^*(x_{b+1}) = 1. In this case, the lemma statement is immediate from the algorithm: line 3 predicts y^=1\widehat{y} = 1 at xb+1x_{b+1} and the revealed label is h∗(xb+1)=1h^*(x_{b+1}) = 1, so line 4 returns ⊥\bot 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 j∗j^*.

  1. mis⁡≥j∗\operatorname{mis} \ge j^* when j∗<∞j^* < \infty: mis⁡\operatorname{mis} is lowered only at line 11, upon a probe at xjx_j revealing y=1y = 1, and then h∗(xj)=1h^*(x_j) = 1 forces j≥j∗j \ge j^*. In case 2 the initial value mis⁡=b+1\operatorname{mis} = b + 1 satisfies this since j∗∈[b]j^* \in[b] and in case 3 the initial value is ∞\infty.

  1. The loop cannot terminate while mis⁡>j∗\operatorname{mis} > j^*: if j∗<∞j^* < \infty then h∗∈Vh^* \in\mathcal{V} satisfies f(h∗)=j∗<mis⁡f(h^*) = j^* < \operatorname{mis}, so condition for the loop at line 7 holds.

Combining the two, the loop terminates with mis⁡=j∗\operatorname{mis} = j^* whenever j∗<∞j^* < \infty.

Correctness in cases 2 and 3.

Case 2: h∗(xb+1)=0h^*(x_{b+1}) = 0. Line 3 incurs one mistake, line 5 sets mis⁡←b+1\operatorname{mis} \leftarrow b + 1, and the loop runs. If j∗≤bj^* \le b the observations give mis⁡=j∗\operatorname{mis} = j^* on termination, and line 12 returns xj∗x_{j^*}. If j∗=∞j^* = \infty, no probe can reveal y=1y = 1 (that would force j≥j∗=∞j \ge j^* = \infty), so mis⁡\operatorname{mis} remains b+1b + 1 and line 12 returns xb+1x_{b+1}. Therefore, the returned point is xmin⁡{j∗,b+1}x_{\min\{j^*, b+1\}}.

Case 3: xb+1=⊥x_{b+1} = \bot. Here mis⁡=∞\operatorname{mis} = \infty on entry to the loop. If j∗<∞j^* < \infty, then mis⁡=j∗\operatorname{mis} = j^* on termination and line 12 returns xj∗x_{j^*}. If j∗=∞j^* = \infty, then no probe reveals y=1y = 1, so mis⁡\operatorname{mis} remains ∞\infty and line 12 returns ⊥\bot.

Mistake bound for cases 2 and 3.

A probe is a mistake exactly when the revealed label is 0. Let j1>j2>⋯>jkj_1 > j_2 > \cdots> j_k be the indices in [b][b] of the loop probes revealing 0, and in Case 2 put additionally j0:=b+1j_0 := b + 1, the index of the failed initial probe. Set P={xji}P = \{x_{j_i}\}, over i∈{0,1,…,k}i \in\{0, 1, \ldots, k\} in Case 2 and i∈{1,…,k}i \in\{1, \ldots, k\} in Case 3. The number of mistakes is exactly ∣P∣|P|, so it suffices to show that the initial V\mathcal{V} ∅\varnothing-centered star-shatters PP.

The center. Each jij_i was a probe revealing the true label 0, so h∗(xji)=0h^*(x_{j_i}) = 0 for every ii, and h∗∈Vh^* \in\mathcal{V} by hypothesis. Hence h∗h^* labels every point of PP as 0.

The witnesses. For i=0i = 0 (case 2 only) take hbh^b, which by hypothesis lies in V\mathcal{V}, satisfies hb(xb+1)=1h^b(x_{b+1}) = 1, and satisfies hb(xj)=0h^b(x_j) = 0 for every j∈[b]j \in[b], hence in particular at xj1,…,xjkx_{j_1}, \ldots, x_{j_k}.

For i≥1i \ge1, let Vi⊆V\mathcal{V}_i \subseteq\mathcal{V} denote the version space immediately before the ii-th failed loop probe. By the selection rule at line 8 there is hi∈Vih_i \in\mathcal{V}_i with f(hi)=jif(h_i) = j_i. Then

  • hi(xji)=1h_i(x_{j_i}) = 1, directly from f(hi)=jif(h_i) = j_i.

  • hi(xji′)=0h_i(x_{j_{i'}}) = 0 for every i′>ii' > i, since ji′<ji=f(hi)j_{i'} < j_i = f(h_i) and f(hi)f(h_i) is the least index of [b][b] at which hih_i takes the value 1.

  • hi(xji′)=0h_i(x_{j_{i'}}) = 0 for every i′<ii' < i, including i′=0i' = 0 in case 2, since hi∈Vih_i \in\mathcal{V}_i 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 hih_i is 1 at xjix_{j_i} and 0 on P∖{xji}P \setminus\{x_{j_i}\}, and hi∈Vh_i \in\mathcal{V} because Vi⊆V\mathcal{V}_i \subseteq\mathcal{V}.

Together with the center h∗h^*, these witnesses ∅\varnothing-centered star-shatter PP, hence ∣P∣≤s∅(V)|P| \le\mathfrak{s}_{\varnothing}(\mathcal{V}) and the algorithm makes at most s∅(V)\mathfrak{s}_{\varnothing}(\mathcal{V}) mistakes.

Theorem 4.10. Let H\mathcal{H} be a concept class with s∅(H)<∞\mathfrak{s}_{\varnothing}(\mathcal{H}) < \infty and SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H}) < \infty. Then H\mathcal{H} is learnable by algorithm \textsc{Simulate-and-Eat}. Furthermore, we also obtain a bound on the optimal number of mistakes

Moptimal(H,n)≤s∅(H)⋅SDdim⁡(H)M_{\mathrm{optimal}}(\mathcal{H}, n) \le\mathfrak{s}_{\varnothing}(\mathcal{H}) \cdot\operatorname{SDdim}(\mathcal{H})

Proof. We use induction on SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}). As a base case, if SDdim⁡(H)=0\operatorname{SDdim}(\mathcal{H}) = 0, then H\mathcal{H} contains only one concept, so the main loop terminates immediately and predicts all points correctly.

Now assume that, for some d≥0d \ge0, \textsc{Simulate-and-Eat} is correct and achieves the desired mistake bound on all concept classes H\mathcal{H} with SDdim⁡(H)≤d\operatorname{SDdim}(\mathcal{H}) \le d. Let H′\mathcal{H}' be an arbitrary concept class with SDdim⁡(H′)=d+1\operatorname{SDdim}(\mathcal{H}') = d + 1, let SS be a multiset, and let h∗∈H′h^* \in\mathcal{H}' be the true labeling concept.

We now run \textsc{Simulate-and-Eat} on H′\mathcal{H}' and SS. Let σ\sigma be the order in which \textsc{SDSolver} probes the points in SS and let ((xσ(1),y^σ(1)),…,(xσ(n),y^σ(n)))((x_{\sigma(1)}, \widehat{y}_{\sigma(1)}), \ldots, (x_{\sigma(n)}, \widehat{y}_{\sigma(n)})) 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 h∗∈Vh^* \in\mathcal{V} since h∗∈H′h^* \in\mathcal{H}'.

  • Since SDSolver is consistent, the concept hh it follows satisfies h(x)=0h(x) = 0 for all x∈S0x \in S^0 and h(xσ(i))=1h(x_{\sigma(i)}) = 1 for all ii such that y^σ(i)=1\widehat{y}_{\sigma(i)} = 1. This concept satisfies the condition of hbh^b 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 xσ(n+1)=⊥x_{\sigma(n+1)} = \perp. By case 3 of Lemma 4.9, this call will make at most s∅(H′)s_{\emptyset}(\mathcal{H}') mistakes and return ⊥\perp. Line 17 then correctly labels all points as SDSolver did. Since d+1≥1d + 1 \ge1, we make at most s∅(H′)⋅SDdim⁡(H′)s_{\emptyset}(\mathcal{H}') \cdot\operatorname{SDdim}(\mathcal{H}') mistakes as desired.

Now that at least one y^σ(i)\widehat{y}_{\sigma(i)} is incorrect, let i∗i^* be the first index for which h∗(xσ(i∗))≠y^σ(i∗)h^*(x_{\sigma(i^*)}) \ne\widehat{y}_{\sigma(i^*)}. We claim that xmisx_{\mathrm{mis}} will be set to xσ(i∗)x_{\sigma(i^*)}, so that the updates on lines 14 and 15 correctly assign labels to xσ(1),…,xσ(i∗)x_{\sigma(1)}, \ldots, x_{\sigma(i^*)}. Let ii be the first index for which the call FIRST-MISTAKE(V,S0,xσ(i))(\mathcal{V}, S^0, x_{\sigma(i)}) does not fall into case 1 of Lemma 4.9; such an index exists because xσ(n+1)=⊥x_{\sigma(n+1)} = \perp. We have i≥i∗i \ge i^* because if i≤ni \le n, then h∗(xσ(i))=0≠y^σ(i)h^*(x_{\sigma(i)}) = 0 \ne\widehat{y}_{\sigma(i)}. We then have two cases based on y^σ(i∗)\widehat{y}_{\sigma(i^*)}:

  • If y^σ(i∗)=1\widehat{y}_{\sigma(i^*)} = 1, then we have i≤i∗i \le i^*, so i=i∗i = i^*. The call to FIRST-MISTAKE therefore falls under case 2 of Lemma 4.9. At this time, the true labels of all points in S0S^0 are 0, so FIRST-MISTAKE returns xσ(i∗)x_{\sigma(i^*)} as desired and makes at most s∅(H′)s_{\emptyset}(\mathcal{H}') mistakes.

  • If y^σ(i∗)=0\widehat{y}_{\sigma(i^*)} = 0, then xσ(i∗)x_{\sigma(i^*)} is the first incorrectly labeled point in S0S^0. We may be in either case 2 or 3 of Lemma 4.9, but in either case this guarantees that xσ(i∗)x_{\sigma(i^*)} is returned and at most s∅(H′)s_{\emptyset}(\mathcal{H}') mistakes are made.

Therefore, lines 14 and 15 correctly label the prefix xσ(1),…,xσ(i∗)x_{\sigma(1)}, \ldots, x_{\sigma(i^*)} and update the version space accordingly. Let H\mathcal{H} be this new version space. By the construction of SDSolver, we have SDdim⁡(H)≤SDdim⁡(H′−1)=d\operatorname{SDdim}(\mathcal{H}) \le\operatorname{SDdim}(\mathcal{H}' - 1) = d. The next iteration of the loop is indistinguishable from running SIMULATE-AND-EAT with H\mathcal{H} as the starting concept class, so by the inductive hypothesis it makes at most s∅(H)⋅SDdim⁡(H)≤s∅(H′)⋅ds_{\emptyset}(\mathcal{H}) \cdot\operatorname{SDdim}(\mathcal{H}) \le s_{\emptyset}(\mathcal{H}') \cdot d more mistakes. Adding in the s∅(H′)s_{\emptyset}(\mathcal{H}') mistakes from the first iteration we get at most s∅(H′)⋅SDdim⁡(H′)s_{\emptyset}(\mathcal{H}') \cdot\operatorname{SDdim}(\mathcal{H}') mistakes, completing the proof. □

Proof of Theorem 4.5. We can combine Theorem 4.8 and Theorem 4.10 to obtain Moptimal(H,n)≤min⁡{s∅(H)SDdim⁡(H),1εs∅(H)log⁡n}M_{\mathrm{optimal}}(\mathcal{H}, n) \le\min\{s_{\emptyset}(\mathcal{H})\operatorname{SDdim}(\mathcal{H}), \frac{1}{\varepsilon}s_{\emptyset}(\mathcal{H}) \log n\}. □

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 H\mathcal{H} satisfies s∅(H)≥ds_{\emptyset}(\mathcal{H}) \ge d for some d∈Nd \in\mathbb{N}. We then make a multiset of instances SS by including dd copies of each of the dd elements of an ∅\emptyset-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 dd apples there exists a concept in H\mathcal{H} that labels only that block as 1. Intuitively, any self-directed learner with apple-tasting feedback should make roughly dd mistakes on this multiset of instances: either they eat apples from few blocks (and miss the dd that are labeled 1), or they eat apples from many blocks (including about dd that are labeled 0).

Theorem 4.11. Let d∈Nd \in\mathbb{N} and let H\mathcal{H} be a concept class. If s∅(H)≥ds_{\emptyset}(\mathcal{H}) \ge d, then there exists a multiset SS of size d2d^2 on which any randomized self-directed learner with apple-tasting feedback makes at least 2d23d+1\frac{2d^2}{3d+1} mistakes in expectation.

Proof. Let {x1,…,xd}\{x_1, \ldots, x_d\} be a set that H\mathcal{H} ∅\emptyset-centered star-shatters. Let SS be a multiset consisting of dd copies of each of x1,…,xdx_1, \ldots, x_d. This multiset is given by the adversary to the learner at the beginning of the game. By definition, there exist concepts h1,…,hd∈Hh_1, \ldots, h_d \in\mathcal{H} such that, for each i∈{1,…,d}i \in\{1, \ldots, d\}, we have hi(xi)=1h_i(x_i) = 1 and hi(xj)=0h_i(x_j) = 0 for j≠ij \ne i. Each of those concepts has one good block labeled 1 and d−1d - 1 bad blocks labeled 0. There also exists a concept h0h_0 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 2d3d+1\frac{2d}{3d+1}, choose one of h1,…,hdh_1,\ldots,h_d uniformly at random.

  • With probability d+13d+1\frac{d+1}{3d+1}, choose h0h_0.

We claim that under this distribution no randomized learner can make fewer than 2d23d+1\frac{2d^2}{3d+1} mistakes on average.

Let A\mathcal{A} be an arbitrary randomized learning algorithm. We make a few observations which will aid our analysis.

  • We can assume without loss of generality that A\mathcal{A} 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 {h1,…,hd}\{h_1,\ldots,h_d\}.

  • 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 h0h_0.

  • Since the only feedback A\mathcal{A} gets before stopping is a series of bad blocks, we can further assume that before making any samples it chooses some (possibly random) number kk of bad blocks to sample before stopping.

We now compute the expected number of mistakes A\mathcal{A} makes for each fixed choice of k∈{0,…,d}k \in\{0,\ldots,d\} which denotes the number of bad blocks the learner sampled from. There are three possibilities, whose probabilities and mistake counts depend on kk:

  • In the first case the algorithm finds a good block at some i≤ki \le k. This indicates the true concept is in {h1,…,hd}\{h_1,\ldots,h_d\}. In this case, the algorithm makes i−1i-1 mistakes.

  • In the second case the algorithm does not find a good block but the adversary had chosen the true concept from {h1,…,hd}\{h_1,\ldots,h_d\}. In this case, the algorithm makes d+kd+k mistakes.

  • In the third case the algorithm does not find a good block and the adversary chose h0h_0 as the true concept. In this case, the algorithm makes kk mistakes.

We now combine these three cases to compute the expected number of mistakes made by the algorithm.

E[A’s mistakes∣k]=2d3d+1⋅1d⋅∑i=1k(i−1)+2d3d+1⋅d−kd⋅(d+k)+d+13d+1⋅k=2d23d+1+k(d−k)3d+1\begin{aligned} \mathbb{E}[\mathcal{A}\text{’s mistakes}\mid k] = \frac{2d}{3d+1}\cdot\frac{1}{d}\cdot\sum_{i=1}^{k}(i-1) + \frac{2d}{3d+1}\cdot\frac{d-k}{d}\cdot(d+k) + \frac{d+1}{3d+1}\cdot k \\ &= \frac{2d^2}{3d+1}+\frac{k(d-k)}{3d+1} \end{aligned}

Since 0≤k≤d0 \le k \le d, k(d−k)≥0k(d-k) \ge0, so we have:

E[A’s mistakes∣k]≥2d23d+1\mathbb{E}[\mathcal{A}\text{’s mistakes}\mid k]\ge\frac{2d^2}{3d+1}

Since this inequality holds for all kk, it holds for any distribution over kk, and therefore A\mathcal{A} makes at least 2d23d+1\frac{2d^2}{3d+1} 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 VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty.

Since this block singleton structure exists in any concept class with s∅(H)≥ds_{\emptyset}(\mathcal{H}) \ge d, it is especially powerful when s∅(H)=∞s_{\emptyset}(\mathcal{H}) = \infty. We use this idea to show the following theorem.

Theorem 4.12. For any concept class H\mathcal{H}, if s∅(H)=∞s_{\emptyset}(\mathcal{H}) = \infty then Moptimal(H,n)∈Ω(n)M_{\mathrm{optimal}}(\mathcal{H}, n) \in\Omega(\sqrt{n}).

Proof. Let H\mathcal{H} be a concept class with s∅(H)=∞s_{\emptyset}(\mathcal{H}) = \infty. For any fixed n∈Nn \in\mathbb{N}, let m=⌊n⌋m = \lfloor\sqrt{n}\rfloor. Then s∅(H)≥ms_{\emptyset}(\mathcal{H}) \ge m, so by Lemma 4.11 there exists a sample set of size at most m2≤nm^2 \le n on which any randomized self-directed learner with apple-tasting feedback makes at least 2m23m+1∈Ω(n)\frac{2m^2}{3m+1} \in\Omega(\sqrt{n}) mistakes.

When s∅(H)<∞s_{\emptyset}(\mathcal{H}) < \infty, Lemma 4.11 yields only a constant lower bound. We supplement it with a bound based on SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}). Because apple-tasting feedback is less useful than full-information feedback, the only difficulty is in showing that Ω(SDdim⁡(H))\Omega(\operatorname{SDdim}(\mathcal{H})) 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 H\mathcal{H} be a concept class such that s∅(H)s_{\emptyset}(\mathcal{H}) and SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}) are both finite. Then for all sufficiently large nn we have Moptimal(H,n)≥12max⁡{s∅(H),SDdim⁡(H)}M_{\mathrm{optimal}}(\mathcal{H}, n) \ge\frac{1}{2}\max\{s_{\emptyset}(\mathcal{H}),\operatorname{SDdim}(\mathcal{H})\}. Moreover, if SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty, then Moptimal(H,n)∈ω(1)M_{\mathrm{optimal}}(\mathcal{H}, n) \in\omega(1).

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 SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}), which they show equals the optimal deterministic mistake bound Msd(H)M_{\mathrm{sd}}(\mathcal{H}). Combinatorially, SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}) can be constructed as the largest kk for which there is a set SS and a realizable kk-tree on (H,S)(\mathcal{H}, S): a tree whose nodes are subsets V⊆SV \subseteq S, in which every x∈Vx \in V carries two outgoing edges labeled with distinct labels yx≠yx′y_x \ne y'_x, every root-to-leaf path has length at least kk, and every branch is realized by some concept of H\mathcal{H}.

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 kk-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 SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H}) < \infty, fix a realizable kk-tree for k=SDdim⁡(H)k = \operatorname{SDdim}(\mathcal{H}) and let the adversary play down it. Whenever the learner selects a point xx of the current node VV, two labels yx≠yx′y_x \ne y'_x are available, and at least one of them receives probability at most 1/21/2 under the learner’s distribution; the adversary answers with that label, forcing a mistake with probability at least 1/21/2, and the play descends one level. Since the learner must eventually predict on every point of SS, and the points outside the current node are already determined by the tree, at least kk such descents occur. Hence any randomized learner suffers at least k/2k/2 mistakes in expectation, giving Moptimal≥12SDdim⁡(H)M_{\mathrm{optimal}} \ge\frac{1}{2}\operatorname{SDdim}(\mathcal{H}). If SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty then we can take kk arbitrarily large for sufficiently large nn, yielding the ω(1)\omega(1) bound.

For the remainder of the lemma statement, Lemma 4.11 gives a lower bound of 2s∅(H)23s∅(H)+1≥12s∅(H)\frac{2s_{\emptyset}(\mathcal{H})^2}{3s_{\emptyset}(\mathcal{H})+1} \ge\frac{1}{2}s_{\emptyset}(\mathcal{H}). 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 H\mathcal{H} be given. We note that,

  • By Theorem 4.3, if VC⁡(H)=∞\operatorname{VC}(\mathcal{H}) = \infty then Moptimal(H,n)∈Ω(n)M_{\mathrm{optimal}}(\mathcal{H}, n) \in\Omega(n).

  • By Theorems 4.4 and 4.12, if VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty and s∅(H)=∞s_{\emptyset}(\mathcal{H}) = \infty then Moptimal(H,n)∈Θ~H(n)M_{\mathrm{optimal}}(\mathcal{H}, n) \in\widetilde{\Theta}_{\mathcal{H}}(\sqrt{n}).

  • By Theorems 4.5 and 4.13, if s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty and SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty then Moptimal⁡(H,n)∈OH(log⁡n)∩ωH(1)M_{\operatorname{optimal}}(\mathcal{H}, n) \in O_{\mathcal{H}}(\log n) \cap\omega_{\mathcal{H}}(1).

  • By Theorem 4.10, if s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty and SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H}) < \infty then Moptimal⁡(H,n)∈ΘH(1)M_{\operatorname{optimal}}(\mathcal{H}, n) \in\Theta_{\mathcal{H}}(1).

Proof of Theorem 4.1. Let a concept class H\mathcal{H} be given. By Definitions 3.7, 3.8, and 3.9 we have VC⁡(H)≤s∅(H)\operatorname{VC}(\mathcal{H}) \le s_{\varnothing}(\mathcal{H}) and VC⁡(H)≤SDdim⁡(H)\operatorname{VC}(\mathcal{H}) \le\operatorname{SDdim}(\mathcal{H}), so exactly one of the following holds: VC⁡(H)=∞\operatorname{VC}(\mathcal{H}) = \infty; or VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty and s∅(H)=∞s_{\varnothing}(\mathcal{H}) = \infty; or s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty and SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty; or s∅(H)<∞s_{\varnothing}(\mathcal{H}) < \infty and SDdim⁡(H)<∞\operatorname{SDdim}(\mathcal{H}) < \infty. Theorem 4.2 assigns to each of these cases the rates Ω(n)\Omega(n), Θ~(n)\widetilde{\Theta}(\sqrt{n}), OH(log⁡n)∩ωH(1)O_{\mathcal{H}}(\log n) \cap\omega_{\mathcal{H}}(1) and ΘH(1)\Theta_{\mathcal{H}}(1) 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 Ω(n)\Omega(n) mistakes can be forced for thresholds in the adversarial online setting, but the VC-dimension and ∅\varnothing-centered star number s∅s_{\varnothing} are finite for this class.

Remark 2. We note that SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}) and s∅(H)s_{\varnothing}(\mathcal{H}) could be finite or infinite, independent of each other. Singletons on R\mathbb{R} have infinite s∅(H)s_{\varnothing}(\mathcal{H}) but finite SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}). In section 7 we show that there also exists a class with finite s∅(H)s_{\varnothing}(\mathcal{H}) but infinite SDdim⁡(H)\operatorname{SDdim}(\mathcal{H}).

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 H\mathcal{H} be a concept class with finite VC dimension. Then for all n∈Nn \in\mathbb{N}, there exists an instance space of size nn on which any self-directed learning algorithm, with full-information feedback, has expected regret Ω(nVC⁡(H))\Omega(\sqrt{n\operatorname{VC}(\mathcal{H})}).

Proposition 3 (Theorem 16 from Raman et al. [ [23]). Let N,T∈NN, T \in\mathbb{N} and let E1,…,EN\mathcal{E}^{1}, \ldots, \mathcal{E}^{N} be experts. For expert Ei\mathcal{E}^{i}, let E1i,…,ETi\mathcal{E}^{i}_{1}, \ldots, \mathcal{E}^{i}_{T} be their predictions in rounds 1,…,T1, \ldots, T. Let y1,…,yTy_{1}, \ldots, y_{T} be the sequence of true labels. Then there exists an online learning algorithm that receives only apple-tasting feedback and outputs predictions y^1,…,y^T\widehat{y}_{1}, \ldots, \widehat{y}_{T} that satisfy:

E[∑t=1T1{y^t≠yt}]≤(inf⁡j∈[N]∑t=1T1{Etj≠yt})+3Tln⁡N\mathbb{E}\left[\sum_{t=1}^{T}\mathbf{1}\{\widehat{y}_{t} \ne y_{t}\}\right] \le\left(\inf_{j \in[N]} \sum_{t=1}^{T}\mathbf{1}\{\mathcal{E}^{j}_{t} \ne y_{t}\}\right) + \sqrt{3T\ln N}

Theorem 5.1. Let H\mathcal{H} be a concept class with finite VC dimension. The optimal expected regret of learning H\mathcal{H} in the self-directed, apple-tasting, agnostic setting satisfies:

Roptimal⁡(H,n)∈Ω(nVC⁡(H))andRoptimal⁡(H,n)∈O(nVC⁡(H)log⁡n)R_{\operatorname{optimal}}(\mathcal{H}, n) \in\Omega(\sqrt{n\operatorname{VC}(\mathcal{H})}) \qquad\text{and} \qquad R_{\operatorname{optimal}}(\mathcal{H}, n) \in O(\sqrt{n\operatorname{VC}(\mathcal{H})\log n})

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 SS, the learner instantiates one expert for each projection of the concept class onto SS. The performance of the best expert is then equal to the performance of the best concept, and by Sauer’s lemma we have log⁡N∈O(VC⁡(H)log⁡n)\log N \in O(\operatorname{VC}(\mathcal{H})\log n). The learner chooses an arbitrary order of the points in SS and commits to predicting on them in that order. The regret is therefore O(nlog⁡N)=O(nVC⁡(H)log⁡n)O(\sqrt{n\log N}) = O(\sqrt{n\operatorname{VC}(\mathcal{H})\log n}).

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 VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty, Theorem 4.4 gives the deterministic algorithm PRUNE-AND-EAT which achieves O(VC⁡(H)nlog⁡n)O\left(\sqrt{\operatorname{VC}(\mathcal{H})}n\log n\right) mistakes. In this section we show that the log⁡n\sqrt{\log n} factor can be removed for oblivious adversaries and that the resulting bound is tight.

Since the true concept h∗h^* 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 ⌈VC⁡(H)n⌉\left\lceil\sqrt{\operatorname{VC}(\mathcal{H})n}\right\rceil from the provided set of points SS and treat it as training data to construct the one-inclusion graph. Using this predictor, we generalize to the other points in SS.

Algorithm 5 SAMPLE-AND-EAT(H,S\mathcal{H}, S)
1: Draw R⊆SR \subseteq S uniformly at random among all subsets of SS of size ⌈VC⁡(H)n⌉\left\lceil\sqrt{\operatorname{VC}(\mathcal{H})n}\right\rceil
2: S←S∖RS \leftarrow S \setminus R
3: Query the points in RR in any order and predict y^=1\hat{y}=1 for all these points
4: Obtain h∗∣Rh^*|_R ▷ Projection of the true concept onto RR
5: Construct the one-inclusion graph GH(R,h∗∣R)G_{\mathcal{H}}(R,h^*|_R)
6: For each x∈Sx \in S:
7: Predict y^=GH(R,h∗∣R;x)\hat{y}=G_{\mathcal{H}}(R,h^*|_R;x) ▷ the one-inclusion graph prediction
8: Ignore any feedback
9: S←S∖{x}S \leftarrow S \setminus\{x\}

Table 5.

Theorem 6.1. Let H\mathcal{H} be a concept class with VC⁡(H)<∞\operatorname{VC}(\mathcal{H}) < \infty and assume the adversary is oblivious. Then H\mathcal{H} is learnable by algorithm SAMPLE-AND-EAT with at most 2VC⁡(H)n+12\sqrt{\operatorname{VC}(\mathcal{H})n}+1 mistakes in expectation.

Proof. The algorithm makes mistakes in two phases, which we bound separately:

  • M1M_1: Mistakes made while predicting 1 for all points in RR. We can naively bound M1≤∣R∣≤VC⁡(H)n+1M_1 \leq|R| \leq\sqrt{\operatorname{VC}(\mathcal{H})n}+1.

  • M2M_2: Mistakes made by the one-inclusion graph predictor. We know the one-inclusion graph makes a mistake with probability at most VC⁡(H)∣R∣\frac{\operatorname{VC}(\mathcal{H})}{|R|} on an unseen point. Therefore, E[M2]≤∣S∖R∣⋅VC⁡(H)∣R∣≤VC⁡(H)n\mathbb{E}[M_2] \leq|S \setminus R|\cdot\frac{\operatorname{VC}(\mathcal{H})}{|R|} \leq\sqrt{\operatorname{VC}(\mathcal{H})n}.

Combining the two bounds, we get E[M1+M2]≤2VC⁡(H)n+1\mathbb{E}[M_1+M_2] \leq2\sqrt{\operatorname{VC}(\mathcal{H})n}+1 as desired. □

The upper bound of Theorem 6.1 still has a VC⁡(H)\sqrt{\operatorname{VC}(\mathcal{H})} 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 d∈Nd \in\mathbb{N}, there exists a concept class Hd\mathcal{H}_d such that VC⁡(Hd)=d\operatorname{VC}(\mathcal{H}_d)=d and Moptimal⁡(Hd,n)∈Ω(nd)M_{\operatorname{optimal}}(\mathcal{H}_d,n)\in\Omega(\sqrt{nd}), even against an oblivious adversary.

Proof. Let H1\mathcal{H}_1 be the infinite singleton concept class. That is, let X=N\mathcal{X}=\mathbb{N} be its instance space and include one concept hkh_k for each k∈Xk\in\mathcal{X}, where hk(k)=1h_k(k)=1 and hk(j)=0h_k(j)=0 for all j≠kj\ne k. We then let Hd\mathcal{H}_d consists of dd independent copies of H1\mathcal{H}_1. Since VC⁡(H1)=1\operatorname{VC}(\mathcal{H}_1)=1, we have VC⁡(Hd)=d\operatorname{VC}(\mathcal{H}_d)=d as desired.

We now show that Moptimal⁡(Hd,n)∈Ω(nd)M_{\operatorname{optimal}}(\mathcal{H}_d,n)\in\Omega(\sqrt{nd}). Since s(H1)=∞\mathfrak{s}(\mathcal{H}_1)=\infty, by Lemma 4.11 for any kk we can construct instance spaces of size k2k^2 on which an oblivious adversary can force Ω(k)\Omega(k) mistakes in expectation. Let n∈Nn\in\mathbb{N} be arbitrary. We partition nn into dd blocks of size n/dn/d each, then fill each block with the construction of Lemma 4.11 using the dd copies of H1\mathcal{H}_1 in Hd\mathcal{H}_d. By playing independently on each block, the adversary can therefore force Ω(n/d)\Omega(\sqrt{n/d}) mistakes on all dd blocks, for a total of Ω(nd)\Omega(\sqrt{nd}). □】【。

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 s∅s_{\emptyset}; and

  • Finite concept classes have finite s∅s_{\emptyset} and SDdim.

The remaining regime has finite s∅s_{\emptyset} 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 H\mathcal{H} be an intersection-closed concept class on an instance space X\mathcal{X}. Suppose 2≤VC⁡(H)<∞2 \le\operatorname{VC}(\mathcal{H}) < \infty. Then there exists an intersection-closed concept class H′\mathcal{H}' on an instance space X′\mathcal{X}' such that:

  • VC⁡(H′)=VC⁡(H)\operatorname{VC}(\mathcal{H}') = \operatorname{VC}(\mathcal{H}), and

  • For all x∈X′x \in\mathcal{X}' and y∈{0,1}y \in\{0,1\}, the version space {h∈H′∣h(x)=y}\{h \in\mathcal{H}' \mid h(x) = y\} contains a copy of H\mathcal{H}.

Furthermore, if X\mathcal{X} is finite, then one can take ∣X′∣=(∣X∣+1)⋅∣X∣|\mathcal{X}'| = (|\mathcal{X}| + 1) \cdot|\mathcal{X}|.

Theorem 7.1. There exists a concept class H\mathcal{H} for which s∅(H)=2s_{\emptyset}(\mathcal{H}) = 2, SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty and Moptimal(H,n)∈Ω(log⁡log⁡n)M_{\mathrm{optimal}}(\mathcal{H}, n) \in\Omega(\log\log n).

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 ∅\emptyset-centered star number.

Specifically, let X0\mathcal{X}_0 be a set of size 2 and let H0\mathcal{H}_0 be the set of all concepts on X0\mathcal{X}_0. We then have VC⁡(H0)=2\operatorname{VC}(\mathcal{H}_0) = 2 and that it is union-closed. Recursively apply the construction of Proposition 4 but with inverted labels to produce instance spaces X1,X2,…\mathcal{X}_1, \mathcal{X}_2, \ldots and union-closed concept classes H1,H2,…\mathcal{H}_1, \mathcal{H}_2, \ldots that still satisfy VC⁡(Hi)=2\operatorname{VC}(\mathcal{H}_i) = 2 for all ii. Each Hi\mathcal{H}_i contains copies of Hi−1\mathcal{H}_{i-1}, so by identifying Xi−1\mathcal{X}_{i-1} 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 H\mathcal{H} and the limiting instance space to be X\mathcal{X}.

We first show that s∅(H)=2s_{\emptyset}(\mathcal{H}) = 2. Because H\mathcal{H} is union-closed, by Lemma 4.7 we have s∅(H)=VC⁡(H)s_{\emptyset}(\mathcal{H}) = \operatorname{VC}(\mathcal{H}). Since H\mathcal{H} contains a copy of H0\mathcal{H}_0 we have VC⁡(H)≥2\operatorname{VC}(\mathcal{H}) \ge2, and since any shattered set of size 3 would be contained in some finite Xi\mathcal{X}_i we have VC⁡(H)≤2\operatorname{VC}(\mathcal{H}) \le2. Therefore, s∅(H)=VC⁡(H)=2s_{\emptyset}(\mathcal{H}) = \operatorname{VC}(\mathcal{H}) = 2.

We now show that Moptimal(H,n)∈Ω(log⁡log⁡n)M_{\mathrm{optimal}}(\mathcal{H}, n) \in\Omega(\log\log n). As a stepping stone, we show by induction that M(Hi,Xi)≥i/2M(\mathcal{H}_i, \mathcal{X}_i) \ge i/2, recalling that M(Hi,Xi)M(\mathcal{H}_i, \mathcal{X}_i) denotes the expected number of mistakes an adversary can force when presenting the instance space Xi\mathcal{X}_i to the learner. The base case M(H0,X0)≥0M(\mathcal{H}_0, \mathcal{X}_0) \ge0 is trivial. For the inductive step, suppose M(Hi,Xi)≥i/2M(\mathcal{H}_i, \mathcal{X}_i) \ge i/2 for some i≥0i \ge0. When the learner is presented with Xi+1\mathcal{X}_{i+1}, 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 Hi\mathcal{H}_i that agrees with this random label, so by the inductive hypothesis the adversary can force i/2i/2 more mistakes on average. They can therefore force (i+1)/2(i + 1)/2 in total, completing the inductive step.

For Moptimal(H,n)M_{\mathrm{optimal}}(\mathcal{H}, n), the adversary chooses the largest Xi\mathcal{X}_i such that ∣Xi∣≤n|\mathcal{X}_i| \le n and uses their optimal strategy for Hi\mathcal{H}_i. The learner then incurs i/2i/2 mistakes on average. Since ∣Xj+1∣=(∣Xj∣+1)⋅∣Xj∣|\mathcal{X}_{j+1}| = (|\mathcal{X}_j| + 1) \cdot|\mathcal{X}_j| for all jj, in terms of nn we have i/2∈Ω(log⁡log⁡n)i/2 \in\Omega(\log\log n). Since the adversary’s strategy works even for full-information feedback, we have SDdim⁡(H)=∞\operatorname{SDdim}(\mathcal{H}) = \infty 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 s∅(H)s_{\emptyset}(\mathcal{H}) and VC⁡(H)\operatorname{VC}(\mathcal{H}), and we spent a long time without AI assistance trying to show a constant upper bound for classes with finite s∅(H)s_{\emptyset}(\mathcal{H}). 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 Θ(1)\Theta(1), ω(1)\omega(1) and O(log⁡n)O(\log n), Θ~(n)\widetilde{\Theta}(\sqrt{n}), or Θ(n)\Theta(n). We suspect, however, that the log factors in the ω(1)∩O(log⁡n)\omega(1) \cap O(\log n) and Θ~(n)\widetilde{\Theta}(\sqrt{n}) regimes might hide more fundamental characterizations.

In the Θ~(n)\widetilde{\Theta}(\sqrt{n}) regime, if we assume the adversary is oblivious then Theorem 6.1 attains a mistake bound of O(VC⁡(H)n)O(\sqrt{\operatorname{VC}(\mathcal{H})n}). We also obtain a matching lower bound attained by a specific class. Is the extra log⁡n\sqrt{\log n} 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 d−1d - 1 has VC dimension dd but behaves almost identically to the infinite singletons concept class. Is there a combinatorial dimension that captures this nuance?

References

  1. [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. [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. [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. [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. [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. [6]Henning Bruhn and Oliver Schaudt. The journey of the union-closed sets conjecture, 2013. URL https://arxiv.org/abs/1309.3297.
  7. [7]Nicolo Cesa-Bianchi, Gábor Lugosi, et al. Prediction, learning, and games, volume 1. Cambridge university press Cambridge, 2006.
  8. [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. [9]Zachary Chase and Shachar Lovett. Approximate union closed conjecture, 2022. URL https://arxiv.org/abs/2211.11689.
  10. [10]Zachary Chase and Idan Mehalel. Deterministic apple tasting, 2025. URL https://arxiv.org/abs/2410.10404.
  11. [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. [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. [13]Justin Gilmer. A constant lower bound for the union-closed sets conjecture, 2022. URL https://arxiv.org/abs/2211.09055.
  14. [14]Sally A Goldman and Robert H Sloan. The power of self-directed learning. Machine Learning, 14(3):271–294, 1994.DOI
  15. [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. [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. [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. [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. [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. [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. [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. [22]Luke Pebody. Extension of a method of gilmer, 2022. URL https://arxiv.org/abs/2211.13139.
  23. [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. [24]Will Sawin. An improved lower bound for the union-closed set conjecture, 2023. URL https://arxiv.org/abs/2211.11504.
  25. [25]Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166, 2004.DOI
  26. [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. [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. [28]Volodimir G Vovk. Aggregating strategies. In Proceedings of the third annual workshop on Computational learning theory, pages 371–386, 1990.
  29. [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

Paper details

vlnc:W_u5f2ffdp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT 5.6 Pro, GPT 6 Astra, Opus 5.5

View statement
Looking for related papers…
Contents