Data Subset Selection via Machine Teaching
Authors: Stephen Mussmann
Alex Fang
Ludwig Schmidt
Kevin Jamieson
Venue: Submitted to ICLR 2023 (2023)
Keywords: Data pruning
data selection
machine teaching

Abstract: We study the problem of data subset selection: given a fully labeled dataset and a training procedure, select a subset such that training on that subset yields approximately the same test performance as training on the full dataset. We propose an algorithm, inspired by recent work in machine teaching, that has theoretical guarantees, compelling empirical performance, and is model-agnostic meaning the algorithm's only information comes from the predictions of models trained on subsets. Furthermore, we prove lower bounds that show that our algorithm achieves a subset with near-optimal size (under computational hardness assumptions) while training on a number of subsets that is optimal up to extraneous log factors. We then empirically compare our algorithm, machine teaching algorithms, and coreset techniques on six common image datasets with convolutional neural networks. We find that our machine teaching algorithm can find a subset of CIFAR10 of size less than 16k that yields the same performance (5-6% error) as training on the full dataset of size 50k.

Under review as a conference paper at ICLR 2023
DATA SUBSET SELECTION VIA MACHINE TEACHING
Anonymous authors
Paper under double-blind review
ABSTRACT
We study the problem of data subset selection: given fully labeled dataset and a training procedure, select a subset such that training on that subset yields approx- imately the same test performance as training on the full dataset. We propose an algorithm, inspired by recent work in machine teaching, that has theoretical guar- antees, compelling empirical performance, and model-agnostic meaning the al- gorithm's 's only information comes from the predictions of models trained on sub- sets. Furthermore, we prove lower bounds that show that our algorithm achieves a subset with near-optimal size (under computational hardness assumptions) while training on a number of subsets that is optimal up to extraneous log factors. We then empirically compare algorithm, machine teaching algorithms, and core- set techniques on six common image datasets with convolutional neural networks. We find that machine teaching algorithm can find subset of CIFAR 10 of size less than 16k that yields the same performance (5-6% error) as training on the full dataset of size 50k.
INTRODUCTION
Machine learning has made tremendous progress in the past two years with large models such as GPT-3 and CLIP (Brown et al.) 2020 Radford et al. [021). A key ingredient in these milestones is increasing the amount of training data to Internet scale. However, large datasets come with a cost, and not all or maybe not even most training data is useful. Data subset selection addresses this practical issue with the goal of finding subset of dataset so that training on the subset yields ap- proximately the same test performance as training on the full dataset (Wei et al.) 2015). Applications of data subset selection include continual learning (Aljundi et al., 2019 Borsos et al. 2020 Yoon al. 202T), experience replay (Schaul et al.. 2016 Hu et al.] (021), curriculum learning (Bengio et al. 2009 Wang et al. 2021]. and data-efficient learning (Killamsetty et al. (202a)). Additionally, data subset selection is closely related to active learning (Settles) [2009] Sener & Savarese 2018) and
to fundamental questions about the role of data in learning (Toneva et al. 2018)).
Data subset selection has been studied two quite different contexts. First, perhaps the more popular approaches are found in the coreset literature (Sener & Savarese, 2018 Coleman et al. 2020 Mirzasolciman et al. 2020 Paul et al., 2021), an empirically driven (Guo et 2022)) research area that includes a variety of techniques to select important and diverse points, often with eye towards minimal computational cost of subset selection. Second, machine teaching (Goldman &
Kearns 1995 Shinohara & Miyano 1991] focuses on minimizing the number of examples teacher must present to a learner and can be reframed as data subset selection in some settings. As machine teaching has mostly been studied from a conceptual or theoretical viewpoint, black-box models such as modern neural networks present practical challenge for machine teaching. However, recently, theoretical breakthrough in the machine teaching literature (Dasgupta al.) 20199] Cicalese al.) 2020) formalizes and provides algorithms with analysis for teaching black-box learners. Although these works are mainly theoretical, they also include some limited empirical evaluation, though with implementations that include unjustified heuristics. Furthermore, Dasgupta al. (2019) includes no basclines and Cicalese et al. (2020) only includes random sampling as a baseline. As of yet, the two algorithms have not been compared in the literature, much less to other coreset methods.
In this work, we bring together these two lines of research, through both theoretical analysis and empirical evaluation. We make clear connection between a particular machine teaching setting and data subset selection, use this insight to introduce an algorithm with state of the art and near- optimal asymptotics, prove correctness of implementation heuristics from previous machine teaching work,

---

Under review as a conference paper at ICLR 2023
and empirically evaluate methods from both machine teaching and coreset selection standard set of benchmarks for the first time. The subset size returned by our machine teaching algorithm shaves off factor logarithmic in the dataset size compared existing work. Furthermore, through novel lower bounds, we show that the subset size of our algorithm is near-optimal (under computational hardness assumptions regarding the NP-complete class of problems) and that the expected number of times we must query the learner (train network) is optimal up to extraneous log factors.
Existing machine teaching algorithms from Dasgupta al. (2019); Cicalese et al. (0200) perform well when our learner fits labels perfectly (zero training error) but fail catastrophically if the learner makes few training errors. To address this issue, prior work (Cicalese et al., (020) removes the training emrors from the predictions provided to the teacher, a technique we refer to as error squash- ing- We provide a rigorous theoretical framework that explains why this technique of squashing errors is justified and effective, and furthermore, use it in our algorithm.
Finally, and perhaps most importantly, we compare machine teaching algorithms, including ours, to state-of-the-ard coreset selection techniques and random sampling. We perform experiments with three convolutional neural network architectures on six image datasets (CIFARIO, CIFAR 100, CINICIO, MNIST, Fashion MNIST, SVHN). We find that the machine teaching algorithms all per- form roughly the same and consistently match or outperform the coreset selection techniques.
In summary, main contributions are:
Proposing a machine teaching subset selection algorithm with analysis and lower bounds, showing that the algorithm achieves optimal asymptotic performance up to extraneous log factors.
Providing the first analysis for the justification of error squashing.
Experimentally comparing machine teaching algorithms and coreset techniques using three convolutional neural network architectures on six image datasets.
In Sections 2 and
we introduce the classification setting and present algorithm with its guar- antee. Next, we show our main thcoretical results in Section| and experimental results Section Finally, we discuss work within the context of related work in Sections 6 and
2 SETTING
We work in a classification setting with an input space X' and finite output space V. Given distribution over x y, we wish to find a classifier X' + y with low (test) error: err(h) ((rx))>[((()))) # v).
In this work, we assume we have a hypothesis class H and a learner L, where each h H is function h X + y and the learner is a function: L (X' x 3 + H.
We assume we have a pool of m labeled data points, {xx4, y: ) C (X x y)m The objective of data subset selection is to select subset S C [m]] of small size [S] such that er((((((2 91) i {})) low; perhaps as low as the error training on all data: em(((((I,,,))) u)) : E [m]))).
METHOD
Although our ultimate objective low test error, without a comprehensive understanding of gener- alization for models such as neural networks, we instrumentally focus on achieving low error on the pool of m datapoints. Zhang et al. (202I) show that modern neural networks can exactly fit arbitrary (even random) ground truth labels. Following previous machine teaching work, we initially assume that the leamer makes no errors on the training subset, and refer to these learners as interpolating learners. Note that for interpolating learners, we can always achieve zero pool error if we train with the entire pool. However, it may be possible to select a smaller subset that yields zero pool error. Later, relax this assumption it only approximately true in practice.
2

---

Under review as a conference paper at ICLR 2023
3.1 MAIN ALGORITHM
In this section, we present our algorithm (see Algorithm [ for pseudo-code). Our algorithm is an iterative algorithm, where each iteration is composed of three steps: sampling a subset of the pool, training on that subset, and using the results of training to update the subset sampling distribution. The intuitive principle behind our algorithm is that if we train a subset S C [m]] and receive a hypothesis h E H. we want to emphasize the points (i.e., include some of the points in future subsets) where the hypothesis makes errors with respect to the ground truth labels. Then, in future iterations, that same hypothesis will not be returned by an interpolating learner since the hypothesis would make error the subset.
At each iteration, the algorithm samples a subset St and trains on that subset to yield a hypothesis hT- For sampling subset the 8t iteration, the algorithm independently samples Bernoulli random variables with probability pr,s, and upon success, includes the 7th point. The success probability of the Bernoulli variable for the 8th point at the 1 iteration is Pt,; and we sample a set S such that Pr(S. = S) = (TTss) (Ilee(m))ss (1(( - pr.)). Thus, in order to emphasize errors, the algorithm sets the next iteration's Bernoulli to have higher success probability (Pt-1,; > Pt.))
While there are variety of ways to increase the probabilities, our algorithm calculates the errors E, == Es, (where En {i [m] : h(x;)) * yı on the entire pool made by the hypothesis ht and sequentially doubles the probabilities corresponding to the errors until Eig E, Pt.i is suffi- ciently large (larger than a hyperparameter, {). Since a probability might exceed after this step, we subsequently clip the probabilities to 1.
Because the algorithm only updates probabilities via doubling, a natural choice is to initialize Pr, as a (negative) power of 2-ko ko for some integer kn- Then, Pt, is always power of two, since doubled powers of 2 are powers of 2.
The final aspect of the algorithm is that we periodically halve all probabilities. This step key to improving the guarantee on the size of the subset from previous work (Dasgupta et al., [2019] Cicalese et al., 2020) to the asymptotically near-optimal subset size in this work. Note that without this halving step, the probabilities only increase with the number of iterations.
Our algorithm has two hyperparameters, d and Ñ, which are used to set the doubling limit & the initial power kn, and the number of iterations between halving the probabilities. The algorithm will succeed with high probability if the two hyperparameters are upper bounds on d", the size of the smallest subset that yields zero pool errors, and N, the size of the induced hypothesis set, a set will define in the next section. Conveniently, in the cases where the algorithm fails, it returns whether was too small Ñ was too small. We can set d and Ñ be arbitrarily large to yield valid subsets, but the size of the resulting subsets will be very large. See Algorithm I for pseudo-code.
3.2 ALGORITHMIC ANALYSIS
For the analysis, we begin by assuming that our learner is interpolating, meaning that it makes no errors on the subset it is trained on. More precisely, if he = [(( yt) i E S}} where S C [m], then Vi E S : (xx) = ye- Note that this implies that if we train on the entire dataset, a hypothesis that makes zero pool errors is returned.
Define Ht as the induced hypothesis class, that is, all hypotheses that can be returned by training on a subset: H (L(( 31) i E S}) S C [m]]. Note that the size of H could be as large as n (the number of subsets) but can be much smaller if the data has structure that can be leveraged by the model. Our framework technically requires a deterministic learner and we can fix the random seed for training, however, this is not a practical issue as it is extremely unlikely that we will train a model on the exact same subset at two different iterations.
We now define d' and N. Let E, be the errors of a hypothesis h: E, = (i E [m] A(x;) + ). Let E be the set of possible errors: E = (E, h E H.) {0). We say a set S "fully intersects" if for all E,, E, [S Esl 2 1. Note that an interpolating learner trained subset will yield 0 pool error; if not, then the returned hypothesis h, would have non-zen training error on the subset S, which contradicts the interpolating assumption. Let d' be the size of smallest.
fully intersecting
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1
Input: examples {(Ti, u)s C (A' ") failure probability 6, e E+, N E Z+
An [logg(m/d
{- I (m)
Vi: k1, ko
for 2, ... 4dkg do
Sample St such that E St independently with probability Pt, = Ke.s
Train h, L( [ vess)
Calculate the errors of h on the pool: E, := ER, = {i E [m]] (xx)))) # ys)
if | = 0 then
return SUCCESS: S St else
if LiEE, Pt,i 2 & then return FAILURE TYPE 1: Ñ is too small
else
A log2
EieE Pr..
1, max(0, (0, ke.s
A Ed] + 1 (mod) 2d 0))
end if
end if end for return FAILURE TYPE 2: is too small
fully intersecting set, that is, d' arg minsc/m] [S] subject |Sn 2 YE, With these definitions, we are ready to give our algorithmic analysis theorem.
Suppose à 2 dr and Ñ 2 N := [7). Then, with probability at least 1 6, Algorithm returns successfully within O(d log(m/ /d" queries to the learner and the size of the returned set |$| Odd(log + log log m + log (1/5)).
Theorem 1.
The proof of Theorem 1 in Appendix D Note that the log log m term negligible, for example, it can be ignored (subsumed in the constants) if m < 2 which is true in reasonable cases. In Sec- tion we provide lower bounds showing that the number of queries to the learner asymptotically optimal up to extraneous log factors and that the size of the returned subset is asymptotically optimal (with a computational hardness assumption) if we assume log log is low-order term compared to log N and that 8 a small constant. To choose the hyperparameters and & = O(log N), we can doubling approach to find constant factor approximation d' and log N.
3.3 NON-INTERPOLATING LEARNERS
For non-interpolating learners, Algorithm T might never return successfully even for a single training error. To remedy this, we can "squash" the training errors, that is, remove the points from E, that also appear in St. More precisely, when we calculate errors on the pool, instead of defining E. {i E i] h (z) * y:). define E, (i e [m] hx(x) + y/s A & S.). For the experiments, we run Algorithm with this edit. This error squashing technique is used beyond our algorithm. This technique explicitly used for the experiments in [iialleee et al. (2020) and likely similar approach is used for Dasgupta et al. (2019) as we found experimentally that the algorithm dramatically fails, as written, without error squashing. Similar to this paper. the algorithmic analysis of Cicalese et al. 2020) assumes interpolating learners, but the practical algorithm includes error squashing.
4 THEORY
In this section, first cover notation definitions. particular class of learners, and the equivalence between machine teaching and the classic set cover problem. Next, we cover our lower bounds and results for the error squashing technique.
4

---

Under review as a conference paper at ICLR 2023
4.1 NOTATION DEFINITIONS
Let & denote the set of integers and 2, denote the set of positive integers. Let [k] For S. let ((S) denote the power set of S. For S, let S be the repeated Cartesian product: for example, 5 = S x S. Let Ö()) denote (-)) where extraneous log factors are ignored. In particular, (n) log (f(n)) = (n)))).
{1, ..., kj.
4.2 RANKED MINIMAL ERROR LEARNERS
Here, we define a type learner that appears in the constructions for our lower bounds and given as example in the error squashing framework. Intuitively, a ranked minimal error learner is learner with a hypothesis class H and a ranking such that the learner returns the lowest ranked hypothesis that has minimal error.
Definition 1. Let X' and y be finite. We say learner L is ranked minimal error learner if there exists a (finite) hypothesis class H and bijection H - [[H]]] such that for any D C PPx x V), with k = minsCH H(z, y) E D h(z) # y)), L(D) = arg IiDDaal(e..)EEDDMccceee
(h))
Note that since we focus on fixed datasets and classification in this work, finite X' and y are not a restriction for our purposes. we assume the ground truth labels are generated by a member of the hypothesis class, 3h E H V(x v) E D: ht" (x), then the learner is an interpolating learner.
4.3 LOWER BOUNDS
We present two lower bounds that are query-based lower bounds proved using similar techniques. In particular, we construct ranked minimal error learner with special structure that depends random "key" (e.g., a random vector). We show that even if the teacher knew all the structure of the learner except the random key, any teaching algorithm will not be able to return subset of size Xd" (a X-approximation) with few queries and probability greater than 1/2.
Theorem 2. Fix any À and m 2X. There exists a distribution over interpolating ranked minimal error learners and an m-sized dataset with optimal subset size d', such that any teaching algorithm requires (mmm) queries to achieve at most Ad" subset size with probability at least 1/2.
This would appear to be very bad news: we require an exponential number queries to even achieve a valid subset that is factor À larger than the optimal subset. For- tunately, shown later, (asymptotically strictly better than log N). Furthermore, N is very large in the construction for The- orem 2 so large that log N O(m). Thus, if we content with approximation guarantee of Olog N), then far fewer queries to the learner are required, as the existence of Algorithm | shows.
The proof is in Appendix E.I
not in general approximate the optimal subset to factor of o(lo N)
Theorem 3. Fix any k 2 L, L L, and X L. There exists a distribution over interpolating ranked minimal error learners and a dataset of size m = k[[eA]}e with optimal subset size d' k and queries to
N = Okk hn(m/k)/ In(A)), such that any teaching algorithm requires In(mm/d)) In
achieve at most Xd subset size with probability at least 1/2.
The proof is in Appendix F.2 Note that this implies achieving approximation ratio of Ollo N) or O(log m log N (as found in Cicalese et al. (2020): Dasgupta et al. (2019) requires (dd" In(m/d*)) queries.
We now present a computational hardness lower bound on finding a subset with a small o(log N) approximation ratio optimal, even with unlimited learner queries so that could be explicitly constructed. This result is straightforward application of the following theorem to the set cover equivalence of machine teaching.
Theorem 4 ((Theorem 4.4 from Feige (198)). If there some 0 such that a polynomial time algorithm can approximate set cover within (1 In n, then NP C TIME(n log n)).
Let us interpret this result. For set cover instances, the "size" n of a problem measured in terms of the number of elements, our N. Feige| (1998) defines TIME(f(T)) to be the set of problems solvable in (n) (determnistic) time. The conclusion NP TIME(n Ollog log*)) n)) is slightly weaker
5

---

Under review as a conference paper at ICLR 2023
than NP C (IME(n which would imply the famous P P= NP. All the same, if it were to be shown that NP C. TIME(n log")) it would revolutionize complexity theory, and thus, it is doubtful that such a statement can be shown to be true without significant obstacles.
Then, direct result of set cover equivalence (Goldman & Kearns, 1995) and Theorem Feige (1998) is that approximating machine teaching to within 2 In would imply NP TIME Ollog log m)).
4.4 ERROR SQUASHING FRAMEWORK
In nutshell, our framework consists of defining a general condition for learner, defining a teaching definition for con-interpolating learners, then showing that achieving such teaching set reduces, by way of еπгоr squashing, to standard set cover problem (if the learner meets the condition). This means that the eтror squashing technique effortlessly converts any machine teaching algorithm for interpolating learners to machine teaching algorithm for non-interpolating learners, which inherits the same theoretical guarantees, albeit with larger hypothesis class.
4.4.1 LEARNERS INVARIANT TO CONSISTENT ADDITIONS
In this section, we first define general condition on a learner: learner trained on dataset correctly predicts point, then additionally including that point in the dataset does not change the the learner's predictions.
Definition (Invariant consistent additions). We say learner invariant to consistent additions i' C. P(X x y). C. X, y y: L(D)(z)= y = L(D) = L(D u {(x, b)}).
Intuitively, for models that minimize erro, adding point with zero loss will not change the model. In particular, have the following proposition:
Proposition 1. A ranked minimal error learner is invariant consistent additions.
The proof of Proposition 1 can be found in Appendix F. The invariance to consistent additions is more general than ranked minimal error learners: see an example Appendix F.7.I
4.4.2 ERROR INCLUSIVE TEACHING SETS
Recall that eтror squashing with machine teaching means that when the learner is passed a subset S, and returns hypothesis h4, the teacher acts as if the hypothesis makes errors on the subset S Machine teaching algorithms only terminate when the returned hypothesis makes no errors on the pool, which means that all the emror of ht are squashed with respect to St- For a fixed dataset and learner, we say a set S is "error inclusive" if all errors L(S) are inside S. Formally, for fixed dataset {(z, y/ y define L (em), P[[m]) + P(mm) as the set of indices of points where errors are made by learner trained on a subset S: L (S) = {i E [m] L([(x,, we) : (x;))) + ).
Definition 3. For a fixed dataset, we say set S "error inclusive" " if (S) S.
Error inclusivity means that S contains the points useful for generalization outside S, well the (presumably) nuisance points that are hard or impossible to classify correctly, such as incorrectly labeled ground truth. An error squashing machine teaching algorithm, if it returns successfully, must return an error inclusive set. An important consequence of error inclusivity is that, for learner invariant to consistent additions, the learner trained on the will yield the same result as training on the entire dataset.
Proposition 2. Suppose a learner L is invariant to consistent additions. If set S is error inclusive, (S) ( (Im]).
The proof of Proposition 5 is in Appendix F.6
Interpreted further, emor inclusivity implies that the
number errors from training on is the same as the number of errors from training on the entire dataset, (() = ( ([m])) Furthermore, eтror inclusivity implies (((m(mm C S, meaning that S contains the errors of training on the full dataset. Error inclusivity is condition on a set that will use as the teaching condition for non-interpolating learners.

---

Under review as a conference paper at ICLR 2023
Note that Cicalese et al. (2020) introduce another teaching set condition for non non- non-interpolating learn- ers, k-extended teaching sets. In Appendix F we compare k-extended teaching sets and error inclu- sive teaching sets for ranked minimal errors. We find they are remarkably similar, though neither is stronger than the other: there exist examples where the smallest k-extended teaching set is of size (mm) but there exists error inclusive set of size (1)), and vice versa. However, we show error inclusive sets are much easier to design algorithms for.
4.4.3 EXTENDED ERROR SETS
Recall that the context of machine teaching with interpolating learners, we define the errors of a hypothesis as E, {i E [m]] h(x,,) + M4 and let E = [E, h - be the error sets. Then a set S C [m]] is a valid teaching set 5 fully intersects & (intersects each element of E). Similarly, blx machine teaching is like game where elements of & are revealed by learner queries and a solution 5 C [ma]] must intersect every element. In fact, there is an equivalence between these two views, observed in Goldman & Kearns (1995) the relationship between set cover and machine teaching. For a more complete exposition, see Appendix F]
Define the extended error sety as 8+ = [L (S) S C [m]] (0). For interpolating models, E+ = E. If we find a set S C [m] that fully intersects E+, we are guaranteed that when the learner trained on S, there will be no errois outside of S: is error inclusive. Not only this, we show that, in fact, fully intersecting E- is equivalent to error inclusivity.
Proposition 3. Fix a dataset. If learner is invariant to consistent additions, S fully intersects & if and only if S is error inclusive.
Thus, we show that (for learners invariant to consistent additions) the error squashing technique converts machine teaching with non-interpolating learners to set cover, though of expanded set. Then, black-bor box machine teaching algorithms (which are online set cover algorithms in disguise) can be run with the same theoretical guarantees, though with a larger N. Note that the same is not true k-extended teaching sets (Cicalese et at. 2020)) which require solving "generalized set cover" that is harder design algorithms for (e.g. Cicalese (2020) does not implement any).
EXPERIMENTS
We evaluate 7 subset selection methods: Random sampling. Entropy sampling (Lewis & Gale 1994.. Forgetting events (Toneva et al.] 2018). GraNd (Paul et al.] 2021). DHPZ Dasgupta et al, CFLM (Cicalese et al. 2020), and our introduced algorithm. Although there are many core- set selection techniques, we focused on the methods that achieve the highest accuracy regardless of computation cost. We compare to Entropy, Forgetting, and GraNd as the coreset selection methods because they perform the best in the evaluation on CIFARIO 10 by Guo et al.] (2022) in our dataset subset size regime (20% to 60% of CIFAR10). More details can be found in Appendix B
2019
We compare results on 6 common image datasets (all but CINICIO retrieved using torchvision) and use the predefined train/test splits. The six datasets are: CIFARIO (Krizhessky| 2009). CIFAR100 (Krizhevsky 2009), CINIC1O (Darlow et al. (0118) FashionMNIST (FMNIST) (Xiao et al. 2017). MNIST (LeCun) 1998), and SVHN (Netzer et al. 2011).
We evaluate using three architectures: Myrtle, VGG, and ResNet10. Myrtle was created by Page (018) by stripping away parts of ResNet and modifying the training procedure while balancing between training speed and accuracy on CIFAR-10. The end result is a network that achieves 96%
on CIFAR-I0 in three minutes of training time. VGG (Simonyan & Zisserman) (2055) and ResNet10
(He et al. 2016) are created according to a common pytorch library for the CIFAR dataset More
details including training hyperparameters can be found in Appendix
5.1 RESULTS
1 for the seven methods on all six datasets with one of the architec- tures, ResNet10. We note that there is a variety of performances from the coreset methods though the
We first show results (see Figure
'INICC0 downloaded http:aotoooooot/aaaaaaeaee CCM.C//ooooonaaaiiiieareeeesreee http:/aawaareeeee.....oca.aaaaaa wwwhwhk/hh/////eee
https:://itthbb.com htt.://ww.cooooouaggggggggttrrrr
7

---

Under review as a conference paper at ICLR 2023
CIFARIO with 1e
CIFAR100 ResNet10
0.7
CINICI0 with ResNet10
Test
0.15
0.29
Entropy
CFLM
Ours
GraNd
Forgetting
Random
Text Error
0.4
0.6
Random
Forgetting
Grald
Entropy
CFLM
Ours
DHPZ
Test
0.5
0.3
GraNd
Forgetting
Entropy
CFLM
Ours
DHFZ
Random
0.10
0.3
0.2
0
10000 20000 30000 40000 50000 Subset Size
10000
30000
40000 50.000
20000
40000
60000
90000
Subset
Subset Size
SVHN with ResNet10
FMNIST with ResNet10
0.05
MNIST with ResNet10
0.07
Random
Random
0.06
Forgetling
GraNd
0.07
GraNd
Forgetting
0.04
GraNd
Forgetting
Entropy
Test Emar
Entropy
0.03
Entropy
Text
DHFZ
CRLM
0.02
CFLM
DHPZ
0.04
Ours
Ours
0.01
0.03
20000
20000
40000
Size
Subset Size
Figure 1: Plots for ResNet10 across six datasets. Error bars are from training with 10 replications on subset.
CI with Myrtle
CIFAR10 with VGG
CIFAR10 with ResNNtt1
0.175
Random
Forgetting
0.25
Random
Forgetting
0.25
Forgetting
Random
0.150
GraNd
GraNd
Grald
Entropy
Ereer
0.20
Entrap
Teet Enerr
0.20
Entroy
0.125
CHLM
CFLM
CFLM
DHPZ
0.15
DHPZ
0.15
DHiPZ
Durs
Ours
Ours
0.10
0.10
0.050
10000
20000
30000 40000
50000
10000
20000 30000
Figure 2: Plots for CIFARIO across three model architectures. Error bars are from training with 10 replications a subset.
forgetting events technique consistently performs the best (lower test error). The machine teaching approaches behave similarly to each other, and outperform all coreset methods.
Note that in few cases (SVHN and FMNIST), achieving near-zero pool error is insufficient to achieve minimal test error with the data. This is surprising because the models trained on the ma- chine teaching subsets get less than 0.01 % error on the pool outside of the subset, meaning that every point is either seen or predicted correctly by the model.
Next, we study how varying the model architecture impacts performance. We show results for the seven methods with the three architectures on CIFARIO in Figure 2 We can draw approximately the same conclusions, though surprisingly, Entropy performs worse than random on Res-ResNet architectures. We note that while Entropy performs better than random in Guo et al. (2022) and Coleman et al. (2020), both these papers use ResNet architectures.
Full results for all combinations of datasets and architectures can be found in Appendix Although we do not measure or report wall clock time, a proxy the number of times the model trained. For Entropy and Forgetting, the model is trained once, for GraNd, the model is trained ten times, and the number of iterations for the machine teaching methods are shown in Table [
Finally, we perform cross-architectrre experiments where model architecture used during subset selection is different from the model architecture used for evaluation. Interestingly, the behavior of the machine teaching methods differers dramatically, from transferring well as random to transferring as well as the full dataset. See Figure an example. All 54 combinations of datasets, subset selection architectures, and evaluation architectures can be found in Appendix
8

---

Under review as a conference paper at ICLR 2023
Table 1: This table shows the number of queries the learner for the machine teaching methods with the ResNet10 architecture. Results for the other architectures can be found in Appendix
Dataset
CIFARIO
CIFARI00
CINICIO
SVHN
FMNIST
MNIST
DHPZ
147
142
192
99
111
39
CFLM
116
139
205
82
36
Ours
141
159
197
122
110
34
CIFAR1O from Myrtle VGG
CIFARIO from VGG Myrtle
0.30
0.14
Random
Random
0.25
Forgetting
0.12
Forgetting
Entrapy
Test Errer
Entropy
CFLM
0.10
CFLM
DHIP
OLrs
0.08
Ours
0.06
10000 20000 Subset Size
30000
50000
10000
20000
30000
40000
Subset
Figure 3: Example cross-architecture plots where the subset selection architecture differs from the evaluation architecture. Error bars are from training on subset with 10 replications.
6 RELATED WORK
We note a number of works, sometimes known as coreset methods, focus on reducing the time to train a model once by training with less data, perhaps with drop in performance (Coleman al. 2020 Mirzasoleiman et al. 2020; Paul et al.) 2021 Killamsetty et al., a). A key challenge in that formulation creating data selection algorithm that is computationally fast enough to avoid negating the computational gain of training
less data. In this work, we focus on data selection when we will train multiple times on the data subset (curriculum learning, continual learning, etc), computational cost is less of an issue.
Data subset selection without knowing the labels of the datapoints before point is selected is known as active learning (Settles) 2209). strictly harder problem. Note that optimal data subset col- lected with full knowledge of the labels is an upper bound on how well an active learning algorithm perform.
As mentioned throughout this work, machine teaching (Goldman & Kearns 1995 Zhu et al. 2018 closely related to subset selection; especially Dasgupta et al. (2019) and Cicalese et al. (020) In these works, the specification for machine teaching with black-box models is a bit different from formulation. In particular, those works require the teaching set to be built up iteratively
that the queried subsets form a nested sequence. While natural from a machine teaching perspective, this requirement is unnecessary for subset selection as we can train on arbitrary subsets before returning an arbitrary subset. This less restrictive specification is likely why the log m factor can be trimmed from our algorithm subset size; see Allon et al. (2099) for more details on a related lower bound.
An adjacent problem setting is that of " DDataset Distillation" (Wang et al. 2018 Nguyen et al. 2021) or "Dataset Condensation" (Zhao et al. 2020 /hao Bilen] (021) where a very small (e.g. 100 images) dataset of synthetic images yields decent, but markedly sub-par, performance. Additionally, the optimized synthetic images can be very far from the natural data distribution.
DISCUSSION
In this work, we bring together the neural network coreset algorithm and recent machine teaching literature in data subset selection. At the same time, we streamline the theory for machine teaching by proving the correctness of an effective heuristic used in machine teaching implementations and by closing theoretical gaps in the asymptotic number of leamner queries and size of the returned subset. More broadly, we hope the insights produced in this work will spur further research in selecting informative datasets and the role of data in learning.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning. Advances Neural Information Processing Systems, 2019.
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM Journal Computing, 2009.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston, Curriculum learning. ternational Conference on Machine Learning, 2009.
Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in Neural Information Processing Systems, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal,
Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 2020.
Ferdinando Cicalese, Eduardo Laber, Marco Molinaro, et al. Teaching with limited information on the learner's behaviour. International Conference on Machine Learning, 2020.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. International Conference on Learning Representations, 2020.
Luke Darlow, Elliot Crowley, Antreas Antoniou, and Amos Storkey. Cinic-10 is not imagenet or cifar-10. arXiv preprint arXiv:1810.03505. 2018.
Sanjoy Dasgupta, Daniel Hsu, Stefanos Poulis, and Xiaojin Zhu. Teaching a black-box learner. International Conference Machine Learning, 2019.
Uriel Feige. A threshold of for approximating set cover. Journal of the ACM, 1998.
Sally Goldman and Michael Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 1995.
Chengeheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: comprehensive library for coreset selection in deep learning. arXiv preprint arXiv:2204.066. 084999 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEF conference on computer vision and pattern recognition, 2016.
Guannan Hu, Wu Zhang, and Wenhao Zhu. Prioritized experience replay for continual learning. International Conference on Computational Intelligence and Applications, 2021.
Richard Karp. Reducibility among combinatorial problems. Complexity of computer computations, 1972.
Krishnateja Killamsetty, Sivasubramanian Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. International Conference Machine Learning, 2021a.
Krishnateja Killamsetty, Durga Sivasubramanian. Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based data subset selection for efficient and robust learning, AAAI Conference on Artificial Intelligence, 2021b.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Yann LeCun. The mnist database of handwritten digits. 1998.
David Lewis and William Gale. sequential algorithm for training classifiers. SIGIR, 1994.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. International Conference Machine Learning, 2020.
10

---

Under review as a conference paper at ICLR 2023
Yuval Netzer, Tao Wang. Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Timothy Nguyen, Roman Novak, Lechao Xiao, and Jaehoon Lee. Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 2021.
David Page.
myrtle.ai,
2018.
URL
https://myrtle..
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Find- ing important examples early in training. Advances in Neural Information Processing Systems, 2021.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. International Conference on Machine Learning, 2021.
Tom Schaul, John Quan, Toannis Antonoglou, and David Silver. Prioritized experience replay. In- lernational Conference on Learning Representations, 2016.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. International Conference Learning Representations, 2018.
Burr Settles, Active learning literature survey. 2009.
Ayumi Shinohara and Satoru Miyano. Teachability in computational learning. New Generation Computing, 1991.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference on Learning Representations, 2015.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning, International Conference on Learning Representations, 2018.
Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei Efros. Dataset distillation. arXiv 2018
preprint 1e1
Xin Wang, Yudong Chen, and Wenwu Zhu, A survey on curriculum learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. International Conference on Machine Learning, 2015.
Han Xiao, Kashif Rasul, and Roland Vollgraf. aushion-mnist A novel image dataset for bench- 2017.
marking machine learning algorithms. arXiv preprint arXiv:
Jaehong Yoon, Divyam Madaan, Eunho Yang, and Sung Hwang. Online coreset selection for rehearsal-basee continual learning. International Conference on Learning Representations, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 2021.
Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmentation. Inter- national Conference on Machine Learning. 2021.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. arXiv preprint arXiv:2006.05929, 2020.
Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna Rafferty. An overview of machine teaching. arXiv preprint arXiv: 180100997, 2018.
11

---

Under review as a conference paper at ICLR 2023
Table 2:
This table shows the value of the parameters that are related log N estimate. For example, À for DHPZ, for ours, and the number of sampling repetitions for CFLM. All parameters the minimal element from the set (2 10 2 such that the algorithm returns successfully.
Dataset
À (DHPZ)
Sampling Repeats (CFLM)
(Ours)
CIFARIO
1000
2000
1000
CIFARI00
8000
16000
4000
CINICIO
8000
16000
8000
SVHN
1000
2000
500
FMNIST
1000
2000
500
MNIST
125
250
125
A
APPENDIX OVERVIEW
This appendix split into sections:
Additional Experimental Results
Experimental Details
Upper Bound Proofs
Lower Bound Proofs
Error Squashing Framework Exposition and Proofs
A.1 NOTATION DEFINITIONS
Let E denote the set of integers and E4 denote the set of positive integers. Let [A] For set 5, let ((S) denote the power set S. For set S, let S the repeated Cartesian product; for example, S
... 2,, k).
S S.
Let Ó() denote O(-) where extraneous log factors are ignored. For example, if an algorithm has On log n) runtime, it also has a ((n) runtime. Note that we cannot ignore log terms (otherwise can drop everything: O(n) (1)g(e)x(()))), only log factors where the non-log version of an expression also appears.
B EXPERIMENTAL DETAILS
B.1 MACHINE TEACHING IMPLEMENTATION DETAILS
The machine teaching techniques, including ours, have three implementation adaptations. First, all methods are run with error squashing. Second, instead of terminating when no pool errors (outside of the training errors) are made, the algorithms return when the number pool errors is less than 10-4m. Third, to avoid training on very small subsets where training instabilities occur, when machine teaching algorithm attempts to query a subset with fewer than 10a points, we randomly sample enough points that the total number of points is exactly 10 Because MNIST requires significantly fewer points, we randomly sampled to 10 points.
All machine teaching algorithms include hyperparameter that roughly corresponds to log N. For each method and dataset, we tuned over the set (2* 10 & E Z} to find the minimal hyperparameter value where the algorithm returned successfully. See Table 2 Our proposed algorithm additionally has the hyperparameter d which 1
10 for all experiments except for MNIST it was to
B.2 CORESET IMPLEMENTATION DETAILS
Forgetting scores were calculated while training the subset selection model once. Ten different subset selection models were trained for the ten different runs.
12

---

Under review as a conference paper at ICLR 2023
Table 3: This table shows the number of queries the learner for the machine teaching methods with the Myrtle architecture.
Dataset
DHPZ
CFLM
Ours
CIFARIO 10
128
108
125
CIFARIO0
126
150
146
CINICIO
144
197
201
SVHN
76
87
FMNIST
105
73
102
MNIST
47
42
Entropy calculated using the softmax probability distribution after training until completion. Ten different subset selection models were trained for the ten different runs.
GraNd calculated the 1.2 norm of the gradient of cross entropy loss with respect the last layer's 's weights and biases, averaged over ten runs. All ten replications used the same GraNd scores (averaged from ten runs).
B.3 MYRTLE DETAILS
Details for the Myrtle architecture can be found here https:///ttthiiiii http:/ttuw.ooooaaaaiiiieeeeeeeee cifar10- fast Specifically, we use the updated version that uses preprocessing whitening block and a weighted KL and cross entropy loss, well as tricks such Ghost BatchNorm, two sets of SGD optimizers, and exponential moving averages. Note that we use neither CutOut aug- mentation
test time augmentation, keep most hyperparameters the same as the default ones, except we train for 50 50000 steps and set the base learning rate 0.4.
stick to training augmentation with crops and flips. We
B.4 VGG AND RESNETIO DETAILS
The code for the VGG and ResNet10 can be found at https:///ittust cww/ koon/uuagglu// pytorch-cifar VGG was created with the command VGG VGG13') and ResNet10 was created with the command ResNet (Bas cBlockk, occ, [1, 1, 1, 1]). ) Both architectures were trained using SGD with momentum of 0.9 and weight decay 0.0005, and a triangular learning rate schedule with maximum learning rate of 0.1. Cross entropy loss and gradient scaler were also used. The number of gradient steps was set to be 50 x m (i.e. 50 epochs for the full training, more for subsets).
C ADDITIONAL EXPERIMENTS
We first present the number of iterations for the machine teaching methods with Myrtle and VGG in TableBlank Table
This appendix includes the full experimental plots. In the first figure (Figure all three architec- tures are run with all six datasets. The following three figures are cross-architecture experiments and grouped by the evaluation architecture. See Figure 5 for Myrtle evaluation, Figure (6) for VGG evaluation, and Figure for ResNetl0 evaluation. "CIFARIO with Myrtle" means Myrtle was used for both subset selection and evaluation, while "CIFARIO 10 from VGG ResNet10" means VGG was used for subset selection and ResNet10 was used for evaluation.
13

---

Under review as a conference paper at ICLR 2023
CIFARIO with Myrtle
0.30
CIFAR1O
CI with ResNet10
Random
Random
0.175
Forgetting
0.25
Forgetting
0.55
Forgetting
0.150
GraNd
GraNd
Entrayy
Entropy
Test Erer
0.20
Entropy
0.125
CFLM
CFLM
CFLM
0.100
DHFZ
DIIPZ
Ours
0.15
DHIPZ
Ours
0.075
0.10
0.050
10000 20000
30000 40000 50000
10000 20000
30000 40000 50000
10000
20000
30000 40000 S0000
Subset Size
Subset Sizo
Subset Size
CIFARI00 with Myrtle
CIFARIOO with VGG
CIFARI00 with ResNe:10
0.7
Random
Random
0.6
Random
0.6
Forgetting
Forgetting
Forgetting
GraNd
Grald
0.5
Entropy
Error
Entropy
Error
Entropy
CFLM
CFLM
CFLM
0.4
DHFZ
DHFZ
DHPZ
Ours
0.3
0.3
10000 20000 30000
40000 50000
10000 20000 30000 40000 50000
10000 20000
30000 40000 50000
Subset
Subset
Subset Size
CINIC1O with Myrtle
CINICIO with VGG
CINICIO with ResNet10
0.6
0.7
Random
Ra Randomm
Random
0.6
GraNd
Forgetting
0.5
Forgetting
GraNd
0.6
GraNd
Forgetting
0.5
Entropy
Test Eroor
Entropy
Entropy
CFLM
0.4
DHPZ
DHPZ
DHPZ
Ours
0.3
Ours
0.3
0.2
0.2
0.2
20000
40000
60000 80000
0
20000
40000
60000 80000
0
20000
40000
60000 80000
Subset Size
Subset Size
Subset
SVHN Myrtle
10
0.08
Random
Random
0.07
Rondom
Forgetting
Forgetting
Forgetting
0.06
GraNd
Entropy
Text Error
GraNd
Entropy
Text Emar
0.06
GraNd
Entropy
0.05
CFLM
DHIP
DHIZ
CFLM
0.05
CFLM
DHPZ
Durs
Ours
0.04
0.03
0.03
20000
40000
60008
0
20000
40000
60000
20000
40000
60000
Subset Size
Sub Size
Subset Size
FMNIST with Myrtle
FMNIST with VGG
FMNIST with ResNet10
0.10
Random
0.09
Random
Random
Forgetting
Forgelting
Forgetting
0.09
GraNd
0.08
Gra.d
0.07
GraNd
0.08
Entmpy
Entmpy
Test Ertor
Entrpy
Teat
0.07
CRLM
Teat
0.07
CRLM
0.06
CFLM
0.06
Ours
0.06
Ours
Ours
0.05
20000
40000
60000
20000
40000
80000
20000
40000
60000
Subset Size
Subset Size
MNIST with Myrtle
MNIST with VGG
0.05
MNIST with ResNet10
0.125
Random
Random
Random
Forgatting
Forgetting
Forgetting
0.300
GraNd
Entrapy
Test Eroor
0.06
GraNd
Entrapy
Text Enerr
0.03
GraNd
Entrapy
0.075
CFLM
CFLM
0.060
Ours
DHIPZ
0.04
Ours
0.02
Ours
0.025
0.02
0.01
1.000
0.00
0
2000
4000
6000
2000
4000
6000
2000
4000
6000
Subsot Size
Subset Size
Subset Size
Figure 4: Plots for three architectures by six datasets.
14

---

Under review as a conference paper at ICLR 2023
CIFARIO with Myrtle
CIFARIO from VGG Myrtie
CIFAR1O from ResNet10 to Myrtle
0.14
0.175
Forgetting
0.12
Forgetting
Random
9.12
Random
Forgetting
0.150
0.125
GraNd
Entrayy
CFLM
Test Erer
0.10
Entropy
CFLM
GraNd
Test Ereer
0.10
Entropy
CFLM
0.100
DHFZ
DIIPZ
Ours
0.08
DHIPZ
Ours
0.075
0.06
0.06
0.050
10000 20000
30000 40000 50000
0
10000
20000
30000
40000 50000
10000
20000
30000 40000 50000 Subset Size
Subset Size
Subset Sizo
0.7
CIFARI00 with Myrtle
CIFARIGO from VGG Myrtle
CIFAR100 from ResNet1 to Myrtle
Random
0.50
Random
Random
0.6
GraNd
Forgetting
0.45
GraNd
Forgetting
0.50
0.45
Grald
Forgetting
0.5
CFLM
Entropy
0.40
CFLM
Entropy
0.40
Entropy
CFLM
0.4
DHFZ
0.35
DHPZ
0.35
DHIP
Ours
Ours
Ours
0.30
0.30
0.3
0.25
0.5
10000 20000 30000
40000 50000
20000
20000
Subset
Size
CINIC1O with Myrtle
CINIC1O from VGG to Myrtle
CINIC10 from ResNet10 to Myrtle
0.7
Random
Forgetting
0.5
Ra Raidom
Forgetting
0.6
Forgetting
Random
0.6
GraNd
GraNd
GraNd
0.5
Entropy
Error
Entropy
Entropy
0.4
CFLM
DHPZ
0.3
DHPZ
DHPZ
Ours
Ours
0.2
0.2
0.2
20000
40000
60000 80000
0
20000
40000
60000
80000
20000
40000
60000
80000
Subset Size
Subset Size
Subset Size
0.08
SVHN Myrtle
SVHN from VGG to Myrlle
0.06
ResNet10 Myrtle
Random
Random
Rondom
Forgetting
Forgetting
Forgetting
GraNd
0.050
GraNd
0.05
GraNd
0.06
Entropy
0.045
Entropy
Test Errrr
Entropy
0.05
CFLM
DHIP
CFLM
DHPZ
0.04
CFLM
DHPZ
0.035
Ours
Ours
0.03
0.030
0.03
0.025
20000
40000
60000
20000
40000
60000
20000
40000
60000
Subset Size
Subset Size
Subset Size
FMNIST with Myrtle
FMNIST from VGG Myrtle
FMNIST from ResNet10 Myrtle
0.10
Random
Random
0.08
Random
Forgetting
Forgetting
Forgetting
0.09
GraNd
Grald
GraNd
0.08
Entmpy
Entmpy
Test Ermor
0.07
Entrpy
CRLM
CRLM
CFLM
Teat
0.07
0.06
Ours
Ours
Ours
0.06
0.05
20000
40000
60000
20000
40000
60000
20000
40000
60000
Subset Size
Subset Size
Subset
MNIST with Myrtle
MNIST from VGG to Myrtle
MNIST from ResNet10 to Myrtle
0.125
Random
0.08
Random
0.12
Forgatting
Forgetting
Forgetting
0.300
GraNd
0.06
GraNd
0.10
GraNd
Entrapy
Toat Eroor
Entrapy
0.08
Entrapy
0.075
CFLM
CFLM
0.060
Ours
DHPPZ
Ours
DHI2
0.06
Ours
DHPZ
0.025
0.02
0.02
1.000
0.00
0.00
0
2000
4000
6000
2000
4000
6000
2000
4000
6000
Subsot Size
Subset Size
Subset Size
Figure 5: Cross-architecture evaluation on Myrtle.
15

---

Under review as a conference paper at ICLR 2023
CIFAR10 Myrtle
CIFAR1O
CI from ResNet10
0.30
Random
Random
Random
0.25
Forgetting
0.25
Forgetting
0.25
Forgetting
GraNd
GraNd
0.20
Entropy
Entropy
Erer
0.20
Entropy
CTLM
CFLM
CFLM
0.15
DiIPZ
DHIPZ
0.15
DHIPZ
Ours
Ours
Ours
0.10
0
10000 20000 30000
40000 50000
10000 20000
30000 40000 50000
10000
20000
30000 40000 50000
Subset Size
Subset Sizo
Subset Size
CIFAR100 from Myrtle to VGG
CIFARIOO with VGG
CIFAR100 from ResNet10 to VGG
0.7
Random
0.6
Random
Random
Forgetting
Forgetting
Forgetting
0.6
GraNd
Grald
Entropy
Emrer
Entropy
Test Ermor
0.5
Entropy
0.5
CFLM
CFLM
CFLM
DHFZ
DHPZ
DHPZ
0.4
Ours
0.3
0.3
10000 20000 30000
40000 50000
10000 20000 30000 40000 50000
10000
20000
30000
40000 50000
Subset
Subset
Subset Size
CINICIO from Myrtle to VGG
CINICIO with VGG
CINIC10 from ResNet10 to VGG
0.6
0.7
Random
Ra Randomm
Random
Forgetting
0.5
Forgetting
0.6
Forgetiigg
0.6
GraNd
GraNd
GraNd
0.5
Entropy
Test Eror
Entropy
Entropy
CTLM
CFLM
0.4
DHPZ
DHPZ
0.4
DHPZ
Ours
0.3
Ours
0.3
0.2
0.2
0.2
20000
40060
60000
80000
0
20000
40000
60000 80000
0
20000
40000
60000 80000
Subset Size
Subset Size
Subset
Myrtle
VGG
ResNet10
Random
Random
Rondom
Forgetting
0.06
Forgetting
0.07
Forgetting
0.08
GraNd
GraNd
GraNd
Entropy
Text Error
Entropy
Test Emer
0.06
Entropy
CFLM
CFLM
CFLM
0.06
DHPZ
DHIZ
0.05
DHPZ
Ours
Durs
Ours
0.04
0.04
20000
40000
60008
0
20000
40000
60000
20000
40000
60000
Subset Size
Sub Size
Subset Size
FMNIST from Myrtle VGG
FMNIST with VGG
FMNIST from ResNet10 VGG
0.09
Random
0.09
Random
Random
Forgetting
Forgetting
Forgetting
0.10
GraNd
0.08
Gra.d
0.08
GraNd
Entmpy
Entmpy
Test Ertor
Entrpy
0.08
CRLM
0.07
CRLM
0.07
CFLM
Ours
0.06
Ours
0.06
Ours
0.05
0
20000
40000
60000
20000
40000
80000
20000
40000
60000
Subset Size
Subset Size
Subset
MNIST from Myrtle to VGG
MNIST with VGG
MNIST from ResNet10 10 to VGG
0.150
Forgatting
Random
Forgetting
Random
0.08
Random
Forgetting
0.125
0.300
GraNd
Entrapy
Test Eroor
0.06
GraNd
CFLM
Entrapy
Ted Error
0.06
CFLM
GraNd
Entrapy
0.075
DHIPZ
0.04
0.04
0.060
Ours
Ours
Ours
0.02
0.02
0.005
0.000
2000
4000
6000
0.00
2000
4000
6000
0.00
2000
4000
6000
Subsot Size
Subset Size
Subset Size
Figure 6: Cross-architecture evaluation on VGG.
16

---

Under review as a conference paper at ICLR 2023
CIFAR1O from Myrtie ResNet10
CIFAR10
ResNet10
CI with ResNet10
Random
Random
Random
Forgetting
Forgetting
0.5
Forgetting
GraNd
GraNd
0.20
Entropy
Eree
Entropy
Test Erer
0.20
Entropy
CFLM
CFLM
CFLM
Test
0.15
DHIPZ
0.15
DIIPZ
0.15
DHIPZ
Ours
Ours
Ours
0.10
0.10
0.10
0
10000 20000 30000
40000 50000
10000
20000
30000
40000 50000
10000
20000
30000 40000 S0000
Subset Size
Subset Sizo
Subset Size
CIFAR100 from Myrtie ResNet10
CIFAR100 from VGG ResNet10
CIFARI00 with ResNe:10
0.6
0.7
Random
Random
0.6
Random
Forgetting
Forgetting
Forgetting
0.6
GraNd
Grald
Entropy
Deet Emoor
Entropy
Test Error
Entropy
0.5
CFLM
CFLM
CFLM
DHFZ
DHPZ
DHFZ
0.4
Ours
0.3
0.3
0.3
10000 20000 30000
40000 50000
10000
20000 30000
40000 50000
10000 20000
30000 40000 50000
Subset
Subset
Subset Size
CINIC1O from Myrtle to ResNet10
CINIC1O from VGG to ResNet10
CINICIO with ResNet10
0.6
0.7
Random
Rando
Random
0.6
Forgetting
GraNd
0.5
Forgetting
GraNd
0.6
GraNd
Forgetting
0.5
Entropy
Test Eror
0.4
Entropy
Entropy
CTLM
CFLM
0.4
DHPZ
DHPZ
0.4
DHPZ
0.3
Ours
0.3
Ours
0.3
0.2
0.2
0.2
20000
40000
60000
80000
0
20000
40000
60000
80000
0
20000
40000
60000 80000
Subset Size
Subset
Subset
SVHN from Myrtle to ResNet10
SVHN VGG to ResNet10
SVHN 10
Random
0.06
Random
0.07
Rondom
Forgetting
Forgetting
Forgetting
0.08
GraNd
GraNd
0.06
GraNd
Entropy
Text Error
0.05
Entropy
Taxt Emar
Entropy
0.06
CFLM
DHIP
DHIZ
CFLM
0.05
CFLM
DHPZ
Ours
0.04
Durs
Ours
0.04
0.04
0.03
20000
40000
60008
0
20000
40000
60000
20000
40000
60000
Subset Size
Subset Size
Subset Size
FMNNIST from Myrtle to ResNNtl0
FMNIST from VGG to ResNet10
FMNIST with ResNet10
Random
0.09
Random
Random
Forgetting
Forgetting
Forgetting
GraNd
0.08
Grald
0.07
GraNd
Entmpy
Ermer
Entmpy
Test Ermor
Entrpy
CRLM
0.07
CRLM
CFLM
Teat
0.06
0.05
Ours
0.06
Ours
Ours
0.05
0.05
20000
40000
60000
0
20000
40000
60000
20000
40000
60000
Subset Size
Subset Size
Subset
MNIST from Myrtle to ResNet10
MNIST from VGG to 1e
MNIST with ResNet10
0.10
Random
Random
0.05
Random
Forgetting
0.05
Forgetting
Forgetting
0.08
GraNd
GraNd
GraNd
0.06
CFLM
Entmpy
0.03
0.04
CFLM
Entrapy
Text Eneer
0.03
CFLM
Entrapy
DHP2
Ours
0.02
Ours
0.02
Ours
0.02
0.01
2000
4000
6000
0.00
2000
4000
6000
2000
4000
6000
Subset Size
Subset Size
Subset Size
Figure 7: Cross-architecture evaluation on ResNet10.
17

---

Under review as a conference paper at ICLR 2023
Table 4: This table shows the number of queries the learner for the machine teaching methods with the VGG architecture.
Dataset
DHPZ
CFLM
Ours
CIFAR 10
143
158
116
CIFARIO0
123
123
143
CINICIO
202
158
195
SVHN
90
113
FMNIST
87
99
96
MNIST
42
45
38
D UPPER BOUND PROOFS
In this section, we prove the following theorem through sequence of lemmas.
Theorem I Suppose d 2 d' and Ñ Z [7).. Then, with probability at least 8, Algorithum returns successfully within (d log(m/ )) queries to the learner and the size of the returned set is [$| Oddlog N + log log m +
Throughout this section, implicitly assume d d d' and N 2 N.
D.1 HIGHI PROBABILITY EVENT
Set T 2N [logz m| and recall that & = In(4N2 logz (m))6)
G
S 21 Σ Pt, <
(I)
G
unu Gn.t El
(2)
Lemma 1. Event G holds with probability 1 6
Proof.
Fix any H and t T. Note -G = nIS Es - ΣieF, Pt,i 2 5}
Examine the random variable J.S n Eal ΣieE, Bernoulli(p..). Set Pr. EiEg, Pt,s- By Chernoff bound and taking the limit 5-1
- Pa.s
Pr([S E.l < (1 -1- P).)) < (1 (1
(3)
Pr([S, Eyl 0) S exp((-Pr.t) Ph,)))
Therefore,
Pr(-Gr.) S exp(-E)
(5)
18

---

Under review as a conference paper at ICLR 2023
Then, by union bound,
Pr(-G) = Pr
U U
-Gn.t
(6)
tml NEW
T
Pr( Pr(-Gn,t)
1=1 h
TN exp(-E)
(8)
I 2N log)(m)
4 log,(())
(10)
Lemma 2. If holds, then for t S T, Lier, Pr.i <.
Proof. By definition of the interpolating model, [S, O Edl 0, therefore, since G holds, EiE,, Ptş E.
Note this implies that if G holds and the algorithm terminates before T, we won't return FAILURE TYPE
D.2 BOUND ON NUMBER ITERATIONS
Lemma 3. If G holds and & < 2d", then the algorithm returns successfully within Ñ S 2d ko iterations.
Proof. First note that T 2N logg (m) 2 N.
Note that, under and if the probabilities are not halved, a hypothesis cannot be returned twice by the learner. This is because when learner returns h,, for the next iterations, the weight will be at least & and under G, by Lemma 2 h, cannot be returned again. Thus, if N < N 2d, the learner will return all hypotheses before halving.
Lemma 4, I holds and Ñ 2 2d", Algorithm returns successfully within 2d ko + iterations.
Proof. Fix subset solution S* that has the optimal size d².
Let = 2d ki + 1. Note that T s (m)g < N [mg)(m)] < T.
Suppose we have not returned by iteration T: then, by assumption Vt S T: E, > 1.
Note that E, E E, so 1S* n Egj 1.
e E,] 2 1
(1I)
ΣΣ RES
lie E, TT T
(12)
Note that at every iteration, ky for in E, decrease by at least one. By holding, E, < &. Thus, A, 1. And further, if k = 0, then Pt; 1, S,, and g F..
19

---

Under review as a conference paper at ICLR 2023
I
T
KT+14 S ko-
Σ
1 E E.] +
Σ
1 (mod) 2d - 0]
(13)
t=1
1=1
But since k741, 2 0,
T
Kg Σ
l Ei}
20
(14)
2d
1=1
d' Σ Σ
1li E.
d'
20
(15)
2d
168 t=1
T
d'
T
20
(16)
2d
d'
ko 2
1
T
(17)
2d
ko 2
(18)
2
2d Ko 2 T
(19)
which is a contradiction. So the algorithm must have returned before T.
Thus, in either case (Ñ- < 2d or 2 2d), the algorithm terminates before T iterations and within 2d ko 1 iterations.
D.2.1 SIZE OF RETURNED SUBSET
We now analyze the size of the returned set ($]. First, note that at every iteration, E[[S,]] = EE Pt. We can think bounding the size S as bounding the size each [S,] which involves bounding the mean (E Pt,s) and the deviation from the mean. First bound the deviation.
Lemma 5. 1/ Pt, T. for all t T, then, with 5 probability, |Se| S max(e T,, (nT / for each < T with probability at least $
Proof. Note that |S&] = Σm Bernoull((p..).
Define P. Σm Pt,i. Note P. < L.
Fix t. By Chernoff bound, for any k > 0.
P (1+x))(tm)
Pr||S| 2 (1 k)) <
(20)
(21)
Define max(e², In( L).
Let (1 Px cl., cf. 1.
20

---

Under review as a conference paper at ICLR 2023
Pr[[S,] 2 cLl v
(22)
(cL/ P.)(ot)
eck
S (c)
(23)
-
(24)
S E cl
(25)
Pr[[Sp] 2 max(e? L, (n /0)) 2
(26)
2T
Finally, union bound over all iterations & S T yields the result.
Lemma 6. If event holds, for t < T,
Σ 7=
Pt. S sdg
(27)
Proof. We will show something slightly stronger, for t S T,
Pt. S (2d ((t 1) (mod) (2
(28)
We prove this by induction. As a base case, for = 1,
12
P1ùi = m2- ko
(29)
(m/)+)(m
(30)
2d
(31)
< (2d ()
(32)
For the inductive case, we examine two cases: (mod) (2d) + and (mod) (2d) = 0. In both cases, rely on Lemma and event G holding. For the first case,
21

---

Under review as a conference paper at ICLR 2023
Σ Pt+1,
2
(33)
2
(cllEEE)
(34)
1=1
2 Kui + Σ
2
2
(35)
1=1
iE
Pcs + 24,
Σ
Pt,
(36)
E
Pt. + 2
Σ
Ptç
(37)
LiER, Pe,i ieE.
1=1
Pt, + 2
(38)
1=1
< (2d + ((t - 1) (mod) (2d))2 + 25
(39)
- (2d + (((t 1) 1) (mod) r))2
(40)
For the second case,
P+t1.
Σ
2 M
(41)
i=1
(42)
i=1
2 ke, + Σ
2 +
(43)
iEE:
PL, + 2
(44)
i=1
(2d + ((2d - 1 1)2c)
(45)
2
4de
(46)
1)) (2d ((t + 1)-1) 1) (mod) (2d) 2
(47)
Putting the bound on the mean and deviation of the mean, we achieve bound on [S.| and thus |$]
Proposition 4. With probability 1 6,
|$| < max (2T)
(48)
S 2815
(49)
o (d(loE(N) + log log m + log(1/8))
(50)
E LOWER BOUNDS
In this section, we prove three lower bounds.
22

---

Under review as a conference paper at ICLR 2023
E.1 PROOF OF QUERY LOWER BOUND FOR LARGE N
Theorem 2 Fix any À 2 and m 2 2A. There exists a distribution over interpolating ranked minimal error learners and m-sized dalaset with optimal subset size d², such that any leaching algorithm requires 2m/m) queries to achieve at most Ad subset size with probubility at least 1/2.
Proof. Let the dataset include m points that are all labeled O.
Let K C [m]] be randomly chosen such that K C [m]] and |K| Lmm/(2)] 2 1. K is the random "key".
LID, (iE - {1 s
(51)
otherwise
We show that the learner can be written as a ranked minimal error learner. Define
h5(2,) = 1i & S] H (hs S [m] K SAAS mm/2) U [h(m))
(52)
(53)
and let R(hs) R(hs) if ||| |S (i.e. the learner prefers hy with smaller S).
Note that this learner is an interpolating learner because L(K') has zero errors. Furthermore, d"
|K] [m/[)
Note that any set of size [S] = m/2++ + achieves no errors (error inclusive) but the size is more than d" A.
Furthermore, to achieve d' X, a necessary condition for any algorithm to query a subset where |S| < m/2 2 A K S. Otherwise, there will be many errors (2 m/2) and information will be gained on K. This is not sufficient, but is necessary.
Furthermore, for any subset |S| < m/2, the probability that K C S is at most 1/2
Thus, by union bound, in 2 2 iterations, there is a 1/2 chance that the algorithm has not met the necessary condition and thus is not done. Thus, the expected number of iterations is at least
2| 21m/12A11 20(mmAA)
(54)
E.2 QUERY LOWER BOUND FOR SMALL N
Just for this section, define [n] = {0, 1, .,, - 1}. In other words, we start at zero rather than one.
Here we describe a ranked minimal error learner that requires ÿddd log(m/d")) iterations (queries) even achieve even rough upproximation of the optimal subset.
Fix any C,É,K k E E4. Let there be a randomly chosen vector ZE [C]ke, Index ab [k]].
For simplicity let the ground truth labels all be 0.
Let x E [k] x [
Let there be kl + hypotheses where one hypothesis is hypothesis that makes no mistakes h* hoo. For the other kl hypotheses, index the hypotheses by [kE].
1x(2) = {1 i//l= A = C.
(55)
otherwise
23

---

Under review as a conference paper at ICLR 2023
where // signifies integer division and % signifies modulo.
Let R(h,) = and R(h = kf. So ho is preferred, and we must rule out all but the last hypothesis to achieve zero error.
We assume the teacher knows everything about the structure of the hypotheses except for the ran- domness in defining e (the random "key").
Note that we can cover all non-optimal hypotheses with & points, so d' =
We now describe the dynamics of making queries. At every iteration t, the teacher can keep track of an uncertainty set for each element of ट. In particular, let Vi, E P([C)) be an uncertainty set particular, each uncertainty set begins as [C].
such that we know 2 E V1, at the 4hh iteration. the 7th hypothesis is returned by the learner, the teacher knows Vi, = {ā). we know that we covered h, with a query set Xe (by knowing the ranked order of hypotheses), then know that & E Uzexmmiif/e 22,8%
Given the above, A, E [C]ke, and randomness Rg E [k.f] U (2o).
refine the problem to the following problem with states Z, [C]kt, actions
Let Zt,; V2,aa be the size of the uncertainty set.
Let
(
Ar,
22,%
nVe.
(56)
xEXe:n=i///
be the number of elements within the certainty set that we cover with X,.
Finally, let Rg be the hypothesis returned from the learner to the teacher at the t iteration.
Given state Ze, the teacher chooses X, which be converted to A such that 0 < A.i < Z For any query set X, that the teacher queries, we convert this to an A, where [X, En EiE(N) max A
The learner gives the teacher hypothesis (and thus R₂) that is random with respect the random- ness in e such that
Aud
Ac. Ze,i
Pr(Rt =)
1
(57)
Ze,j
j=1
Ard
Pr(R: = =0)
(58)
Ze.j
j=1
In other words, h; is returned by the learner if the query X, covers the first hypotheses, but fails to cover the tth hypothesis. Finally, we return lo if the rest the hypotheses are covered.
Then, on state Z. action A,, and learner's hypothesis RG, we can generate the next state as
Asss < R
Zee1.
1
i R
(59)
ZzS
i > R
E.2.1 ANALYSIS FOR LOWER BOUND
The analysis hinges examining the potential function:
24

---

Under review as a conference paper at ICLR 2023
C
P(Z)) In
(60)
First, note that the potential function is monotone increasing (not strictly) with the number of itera- tions. Further note that P(Z1) since Z1, = C.
Note that at any iteration & and state Zz, the teacher can cover all possible (with respect to the uncertainty sets) hypotheses with exactly
(
Σ max t 1
(61)
(e((()
points. Furthermore, all uncertainty sets cannot be covered with fewer points. For an algorithm to achieve final subset of size of most Ak, must be the case that Q(zi) S Ak.
Lemma 7. For algorithm achieve a final subset at iteration of size most Ak, it must be the case that
P(Z+) 2 In (i)
(62)
Proof. This follows from solving the relaxed optimization problem where Ze and & Z,, S
C.
min P(Z.) such that Q(2,) S Ak
(63)
which has a global solution where all elements of Ze are equal: Ze,i = A
Lemma 8.
- 21
(64)
Proof.
Zz
E(P((++)) P(Zx) = In
(65)
Zet1,
8
1--
Σ
Pr(Re Rr =r)
Σ in
In
(66)
AA,i
r-1
Zr,
$ (C(()) + Σ Pr(Re = r) Σ
In
(67)
A
1=0
1=0
kt-1
Zeeé
= Inn(C) + Σ
Pr(Re =r)nn
(68)
At,i
1=0
r=1+1
kt-1
Zzs
IIn(C) +
Σ
Pr(Re > in
(69)
1
1=0
ke-1
A Z
Zeui
In(CC) +
Σ
In
(70)
A
1=0
y=0
Define ı E Bi where A.: upper bound the expression.
so 0 < n. < 1. We can solve the relaxed problem of maximizing Z.,
25

---

Under review as a conference paper at ICLR 2023
kt-1
E[P(Z++1) - In()))
+
Σ
II f=0
In
(71)
Define /=(d) n (In (#) + +o). Then,
kf-1
1 In
1 To
+ क In (1) (1) + + nT
j
To In
The-1 In
Thk--
2
==0
(72)
= fn (fa, (... ( (0))...))
(73)
Note that if a I 1, then f=(0) I for any 0 S π < 1. So, by induction,
kt-
j
In
S 1
(74)
1=0
and we get the result.
Intuitively, if an algorithm can only increase P(Z)) (in expectation) by + In(C) for every iteration and the algorithm isn't done until P(Z,) 2 kn (f). we have a lower bound.
Lemma 9, For any algorithm that returns subset of size at most Ak at random iteration T,
2(1 + In(()) |] <
kt (C/A(
1
Pr 7
(75)
Proof.
Noting that P(Z)) for any T,
T
E(P(Z++1) = Σ P(Z,)
(76)
1=1
$ <(11+In(C))
(77)
By Markov's inequality,
Pr(r ST) < Pr P(ZT+1) klln CC)
(78)
5
BIP(ZT-1))
(79)
kl In (i)
T(1 + in(C))
(80)
kl In (2)
we set T
(C/AA 2(1+au(C
J. then Pr(7 T) < }/ Or equivalently,
Pr 72 keln(C/A)) 2(1 ((++)((C))
1
(81)
26

---

Under review as a conference paper at ICLR 2023
Finally, we convert this bound into something more usable.
Note that d" ki m kCc and N kl + Thus, lm(m/k)
In(C)
Set = [eA].
Then, with probability at least 1/2, T is at least,
ke kLIn(C/2)
kln(m/k) In(e)
(82)
2(1 + In()))
2(1 + In(ed + ())(
k: kln(m/k)
(83)
2(2 + In(A) + (1 + InA) + 1/e)
A: (mmm/k))
(84)
2(3 + In()))²
d' lmm/d")
(85)
2(3 + In(A))²
If X S X (oloo(m) (Ng(N)= I X log(m) log(k: (mm)/k) (for constant X), then, the expected number of iterations is 22dd log(m/d")))
F ERROR SQUASHING
F.1
BACKGROUND
In this subsection, we review related theoretical work in more detail background framework and algorithms.
F.1.1 SETCOVER AND INTERACTIVE VARIANTS
Setcover is classic computer science problem (Karp 1972). While there many similar and
equivalent formulations, for this work, we formulate the problem in terms of m binary decision variables and N elements, where each element represented by the decision variables that would
"cover" the element: Z: C [m]] for each i E [N]. A solution is a subset S C [m]] such that
Vi [N] 3s S s E Z, In other words, we choose subset S C [m]] of the decision variables so that all elements Z, intersect S. We wish to find solution of smallest size [S].
In the standard non- con-interactiv version of setcover, all elements and sets are known, and there exist algorithms that return solution of size Ollgg(N)Con where COPT is the size of the optimal solution set. In an interactive variant known as online set cover (Alon et al., 2009), the elements are not known at the beginning, only the number of decision variables m. The algorithm is initialized with So = 0. Then, for each iteration = ......., an adversary chooses an element it E [N] that is not intersected by S, (i.e. S, Z, 0) and reveals the decision variables that would cover (i.e. Z,,). ). The algorithm then chooses a set s such that $; E Z,, is permanently added to the solution: S, S U {s.}. This process continues until all elements no possible elements to choose. Note that the online set cover problem is harder than the standard cover problem: if we were given all elements, we can simulate adversary. Furthermore, the number of iterations is exactly the size of the final set. Alon et al. (2099) provides an algorithm that returns solution of size O(log(N) log(m) COPT) where COPT is the optimal (offline) solution.
covered and the adversary has
In this work, we examine another interactive set cover variant that is harder than standard set cover but is a relaxed version of online set cover. We call this exploratory set cover. Like online set cover, the elements are not known at the beginning; the algorithm is only given the number of decision variables m. The algorithm has access to an adversarial oracle which takes a potential solution S, C [m]] and reveals either that S, is valid solution, or chooses an element i, such that Zi, has an empty intersection with S, and reveals Z,,- However, unlike the online set cover version, the sets S, are arbitrary; for example, they need not be nested. At any iteration, the algorithm can return final solution Š that must intersect all Z. An algorithm is evaluated by two evaluation aspects, the number of exploratory iterations and the size of the final solution ($).
27

---

Under review as a conference paper at ICLR 2023
F.1.2 SET COVER HARDNESS
Additionally, approximating set cover with an approximation factor of o(log n) is computationally hard. To be specific, unless NP problems can be solved in n Olog loga) time (a slightly weaker statement than P = NP), there is <) COPT. where COPt
Set cover is one of Karp's 21 NP-hard problems (Karp 1972).
no algorithm for set cover that always returns a cover of size - is the optimal set cover size (Feige 1998). Alon et al. (2009) shows that approximating online set cover requires a larger approximation factor; any algorithm must return solutions of size at least ((In(N) (m(m) Copr) where Corr is the optimal (offline) solution (Alon et al. 2009). Note that the exploratory set cover problem is harder than standard set cover but easter than online set cover.
F.1.3 MACHINE TEACHING
Machine teaching Shhnohara & Miyano, 1991 Goldman & Kearns 1995) is machine learning task where a teacher provides data points to the larner. In the most classic setting, the learner has a finite hypothesis class H. where each hypothesis is mapping from X' to V the teacher knows the learner's hypothesis class and which hypothesis is correct, and provides a teaching set S C X' which uniquely determines the correct hypothesis. In particular, for hypothesis class H and correct hypothesis h.," a set S is a teaching set if
vh H (h") 3r S: :)x))))))))))))))))))(( + (x)
(86)
Intuitively, if the teacher provides {(x, ho (x)) E 8) to the learner, then the only remaining consistent hypothesis is h²
Machine teaching in this setting, where the teacher knows the entire hypothesis class of the learner, has straightforward reduction cover. In particular, identify each hypothesis h E H. \ {h*) as an element to be covered and
Ex tx E X h(x) h" (x))
(87)
as the decision variables (datapoints in subset) that cover h.
An important quantity is the size the smallest teaching set d", which a function of both hypothesis class H. and the true hypothesis h²' E H. Note that the "teaching dimension" (Goldman & Kearns 1995). the maximum d' over all E H.
For the general non-realizable setting, Cicalese al. (2020) defines k-extended teaching set. For hypothesis class H and true hypothesis h" if h- makes & errors on dataset, then 5 is k-extended teaching set if |SS n Cal 2 l + for any hypothesis that makes least I + errors.
F.2 INVARIANCE TO CONSISTENT ADDITIONS
Suppose we have hypothesis class H and a learner J., where each h E H. is function h. X - y and the learner a function:
L: P(X x y) + 7
(88)
Throughout this work, we make the following assumption about the learner.
Definition (Invariant to consistent additions). We say learner invariant to consistent additions ifVD C P(X }), C CX,, y C.:
((D)(z)=1) - L(D) L(D U ((x,))))
(89)
simple example of learne that meets this condition is a "ranked minimal error learner". To avoid handling infinite hypothesis classes, assume X' is finite for this example. Fix hypothesis class H
28

---

Under review as a conference paper at ICLR 2023
(note |H| I ) and bijective ranking H [[H]]. A ranked minimal enror learner returns the highest ranked hypothesis among the hypotheses in achieving minimal error on the dataset:
L(D) =
arg min
(h)
(90)
bal(=sghEDDKc)))))llmmnnng en I(
Proposition 1 A ranked minimal error learner is invariant to consistent additions.
The proof of Proposition ! can be found in Appendix F. The invariance to consistent additions is more general than ranked minimal error learners: see an example Appendix F7.1
F.3 INDUCED HYPOTHESIS CLASSES
Fix an size m dataset {z 9:) (X x m) Note that the learner might have very large hypothesis class, maybe even large enough to arbitrary labels for m-sized dataset (7-) [)/()) However, we can define the induced hypothesis class as
7 (L(((((( Ui): : S}) S [m])
(91)
which could be significantly smaller, depending on the structure of the model and data. Then, we can define the error sets
E {fili ((x,)(()))))))) + we : h 7. - {0}
(92)
(93)
where Es E & is the set of datapoints that eliminate hypothesis h.
For notational convenience, define [(em) P[[m]) P[[m] the set of errors when trained subset S:
(S) = {i: I(((xe, : :'' ())(()) # w
(94)
then, simply,
= (S) SC [m]] {0}
(95)
F.4 ERROR INCLUSIVITY
We wish to find set such that makes as few errors as if trained on the entire dataset: (S) = ([ However, this condition is bit general as we might happen to have test points.
@ is perhaps unlikely to generalize Instead, we might wish to find a set S that, when trained on, yields no errors outside of S. Definition 5. For a fixed dataset, we say set is "error inclusive" " if the following holds:
[T(em( (0) ([a (ma)). in which case
(m C S
(96)
Note that [mi] is always error inclusive. Furthermore, if learner is invariant to consistent additions. ((e = -(em) ([m)).
Proposition 5. Suppose learner L is invariant consistent additions. If S is error inclusive,
I ((m))
(97)
The proof of Proposition 5 is in Appendix F.6 Interpreted further, ( = [L and
(.ee(((m)) C SS, meaning that S contains the emror of training on the full dataset.
29

---

Under review as a conference paper at ICLR 2023
F.4.1 INTERPOLATING LEARNERS
(S) We say learner is "interpolating" if makes no training errors: (S) ns 0. In this case, we can achieve errors on the entire dataset. Furthermore, note that for interpolating learners, error inclusivity of a set S implies that training on S results in zero error on the entire dataset.
F.4.2 RESULTS
Define the extended ervor sets
g+ (T, AS: S c [m]} - {0}
(98)
Proposition
3 Fix a dataset. If learner is invariant to consistent additions,
S fully intersects E < S is error inclusive
(99)
The proof can be found in Appendix
F.6
Define
d'
min S fully intersects g+
|S|
(100)
Note that in the case of interpolating learners, E+ = E, and d' is the size the optimal teaching set.
Thus, as in the machine teaching case, we have reduced the problem of finding good subset to finding minimal setcover, though of an expanded set.
Note that we can convert a data subset selection algorithm with interpolating learners (online or exploratory set cover algorithm) into subset selection algorithm without assuming interpolating learner, simply by acting as training errors don't exist. In particular, if we train on a subset S, and receive hypothesis hy, rather than intersecting {i he(())) # W: A i & S. Put another way, when using a realizable algorithm on non-interpolating learner, can "squash" the training errors and pretend they don't exist. In fact, this technique is used as a heuristic in [Cicalese et al. (2020) to make the algorithm work in practice. Thus, we provide framework justifying the use of this technique previously used as heuristic.
intersect (i (x,)) *
F.5 COMPARISON TO K-EXTENDED TEACHING DIMENSION
Cicalese et al. 2020 introduces the concept of k-extended teaching set for hypothesis class H and
a dataset {(,,, y/ H == C (X' x y) particular, let k = mingeR Ki E [m] h(x;)) # y: be the minimal number of errors of hypothesis in H. A set S is k-extended teaching set, if for any E 7 such that {i E [m] h(x;)) * y:Hl 2 l + 1, [ E S h(x;) + y 2 k+ 1. In other words, any hypothesis that makes k errors (more than the optimal number) the entire dataset, makes + errors on the selected subset S.
Here, for ranked minimal error learners, we compare k-extended teaching sets (and thus sets that fully intersect ++). Fix a dataset, hypotheses H. and ranking a. Let be the minimal number of errors for hypothesis h E 7 for D. For ranked minimal error learner, [L ([m]) k, so an error inclusive set must make ie errors. Therefore any hypothesis where (h)) < (L((((;; JK) ; [m]))) = a² must incur at least k + 1 errors on S, and any hypothesis where a (h) > o (L(((z) y1) : E [m]))) = a² must incur at least k errors on comparison of the two concepts is shown in Table 5
inclusive
Note that error inclusivity requires one less error on Type II hypotheses and more errors on Type III (error optimal) hypotheses. We can construct cases where the smallest error inclusive subset is of size m but the smallest k-extended teaching set is of size (see Appendix E.7.). In the other direction, there cases where the smallest error inclusive subset is of size 2 while the smallest k-extended teaching set is of size m 1 (see Appendix (.7.4). Thus, the two notions of optimality similar but neither is stronger condition than the other.
30

---

Under review as a conference paper at ICLR 2023
Table A comparison between k-extended teaching sets and error inclusive sets. The three columns correspond to three types of hypotheses separated by two attributes: whether hypothesis is ranked higher or lower than ( ((ml), and whether the total number of errors for hypothesis is optimal, k, or sub-optimal, 2 1. Note that L ([m]) is the highest ranked hypothesis with optimal errors k, so there are no hypotheses with & errors and rank lower than o²
Hypothesis type
Type <0"
Type Il
Type III
(h)
> a²
> 0
Total errors
2 +1
+1
Errors for k-extended
2 ck11
k x+1
Errors for error inclusive
2 11
2
2
F.6 FRAMEWORK PROOFS
Proposition 1
A ranked minimal error learner is invariant to consistent additions.
Proof. Suppose L is a ranked minimal error learner with hypothesis class H. and ranking a. Fix
dataset D C ( J), input x E X, and output y E y. It suffices to show that L(D)(x)
implies L(D) = L(D (x,y)).
Define D D U {(a, v)}. Define E P(X )) H Σ+ as E(D. = K(x, v) E D
h(x) * yHl.
E min E(D h))
(101)
KEH
E+ min E(D+ hh)
(102)
kCH
M {h: Nd:E(D, hi) = =}
(103)
M = (h: E(D+ - E+)
(104)
note that
L(D) = arg min o (h) NEM
(105)
L(D*) arg min or (h) be NEA+
(106)
Define
σ min o (h)
(107)
REM
min a (h)
(108)
REM
Because I.(D) M, L(D)) E.
Because (zD)(x)) - y and ((D,L(D) = B(D+ E EDD S.
Because D C D+, s0 E > E.
Therefore, Æ+ = E.
Because E(D,h) h)) < E(D+, h) and E+ = E, M C M. Furthermore, E(D+ L(D)) = E Et so L(D) E Mt
a (L(D)) min (h)
min a(h) S a(h) hEM
(LL())
(109)
heM
31

---

Under review as a conference paper at ICLR 2023
Because a is bijective, it has unique argmax.
so L(D+) = arg m (fi) L(D).
Lemma 10. Suppose learner is invariant to consistent additions. Then, for a fixed dataset {(z,, Vr) E [m]], and for any subsets S, S' C [m].
(S) n S'
I T.(or)
(110)
Proof. We prove by induction on the size of S'. As the base case, if |S"| 0, the statement trivially holds.
Suppose the lemma holds for any |S"| = Now, we must show L (S) = L ( 5*) = L ((( (S) for |S"| +
Choose s and s" with |S = & such that S' = = (S) S" 0 and thus (S S")) (S).
U {s}. Then, (S) n S' 0 implies
Furthermore, L [ (S) n S = 0 implies of (iem) (S)) = (SU")) Therefore,
: =
(111)
since the learner invariant consistent additions.
(((a),)::i "(( Li {(x,. (())))))))))) ((t,))))))(((() {s}})
(112)
L = = "" L
(113)
Proposition 5
Suppose learner L is invariant to consistent additions. If a set S is error inclusive,
(S) ( ([m])
(114)
Proof. Note that since (S) S, I [0m] (S) [[m] \)
By Lemma 10 this implies L(S) = L(SU ([m) \ S)) L((m)). Then, (S) = L ((m)) n
Lemma 11. Suppose a learner L is invariant to consistent additions. For any sets S C [m], if S" is error inclusive, then either
(() (8)
(115)
or
((em) = (S)
(116)
Proof. By the assumption of error inclusivity, ( S* 0.
Thus (S*) n -5* ns = and I (S*) (S*) [m ( (*
(S \ 5*) = 6. Since is invariant to consistent
additions, (( (S* (S)
Suppose the first conclusion is not satisfied: (L) ((S) = 0. then Liem (S) 5) = 0. Since the learner invariant consistent additions, (S) (S
T. (S(S)))
32

---

Under review as a conference paper at ICLR 2023
Thus, (S) L (S (S))
Proposition a learner L, is invariant to consistent additions, then,
S fully intersects 8 is error inclusive
(117)
Proof. +: Suppose fully intersects E Then, for any set S', either (())) S' or (() n)
Set S" = Then, because (S) \ S) thus S is error inclusive.
must be the case that L (S) \ 0 and
<- Suppose a set S is error inclusive.
Pick any set S' C [m]. It suffices to show that either L (S') = or (5))))))))) ns) 2 1.
By Lemma there are two cases:
Case 1: (L S') 1.
We done.
Case 2: (e) (S" and (')
(am (S)) (5)) ns 0
71
(118)
(S' (ani
(Sn) n - 0
(119)
(
(sn unn -S' Ø
n
(120)
(S) - 0
(121)
(ST) U - = 0
(122)
I .5 0
(123)
(124)
where the third to last line follows from the error inclusivity of S.
F.7 EXAMPLES
F.7.1 EXAMPLE OF LEARNER THAT IS NOT MINIMAL ERROR LEARNER, BUT IS INVARIANT TO CONSISTENT ADDITIONS
We examine a situation with three datapoints and binary labels. The dataset is {x11, 0), (x2, 0), (z3, 0)} and the learner L has two hypotheses f and h2 where
h (x1)
(125)
h (x2) = 0
(126)
h 0
(127)
h2(21) = 0
(128)
h2(22)
(129)
h2(23) =
(130)
the learner has the following mapping:
33

---

Under review as a conference paper at ICLR 2023
L(0) = h2
(131)
L(((z1, 0}}) h2
(132)
L({(22, 0}}} h1
(133)
([((,,)0]) h1
(134)
= h2
(135)
((((z),)), fı2
(136)
L([(22, (z,,0) h1
(137)
L(((21, (x2 (zs, fı
(138)
Note that f2 has two errors on D, while h1 only has one enror. However, L(D) = h2. Thus, the learner does not return the hypothesis with minimal error.
However, a simple examination yields invariance to consistent additions. For example, L(((22, (zs) ys and L(((22, 0)}) [({(22, 0), (zz,
F.7.2 COMPARISON BETWEEN INDUCED HYPOTHESIS CLASS AND EXTENDED ERROR SETS
Here show that 8 can be larger than &
We examine a situation with three datapoints and binary labels. The dataset is ((x1, 0), (22, 0), (za, 0}} and the learner L has two hypotheses h and hg where
hn (m)) 1
(139)
In (x 0
(140)
h (Ir) 0
(141)
h2(21) = 0 h2(22)
(142)
(143)
h2(x3) =
(144)
L(0) h2
(145)
L({(z),))} ha
(146)
L(((x2,)) 0)}) = hn
(147)
L([(xa;)] 0)}) hn
(148)
(22, = h2
(149)
[(( h2 (1, = h1 L(((21, 0), (x2, 0), (xa,0)) h1
(150)
(151)
(152)
Then, E+ {{1), (2,3), (2), (3)} while & = {{1), (2,3))
F.7.3 K-EXTENDED TEACHING SET SUPERIORITY
In the following example, H (hh); and a (h+)
34

---

Under review as a conference paper at ICLR 2023
= 0...0.....00.0
(153)
h1 (a.) (1.0,0,0,0.....0.1)
(154)
(x.)) - (0.1.0.0.0.....0000
(155)
hz(x)) (0.0,1,0,0,....000
(156)
ha(x.) = (0.0.0,1,0.....00.0)
(157)
(158)
(x.) = (0.0,0.0.0......
(159)
In this case, the smallest 1-extended teaching set 0 while the smallest error inclusive set is
(1,2....,m). m)..
F.7.4 ERROR INCLUSIVITY SUPERIORITY
In the following example, H {hi} and (1h;) = i.
y. (0.000.0.0.....000..00
(160)
hn (z. (1.00000.00....0000.00)
(161)
h2 (a:) (0.1.0,0,00..,,0000.0
(162)
(a.) 0,001.00.0....000...1
(163)
h4(2. (0.0,0.1.0.....0.0...
(164)
(165)
(2.1 10.0,0,0,0.....000.. .,,00
(166)
In this case, the smallest 1-extended teaching set is (2. . while the smallest error inclusive set is {1, m].
35


Reviews:
[{"review_id": "cRNb9M31lrf", "reviewer": "Reviewer_YuUz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Paper presents theoretical and experimental analysis of a machine teaching algorithm for data subset selection. ", "summary_of_the_review": "Somewhat minor improvement, but some good theoretical and empirical analysis. Improvements to exposition would assist. I think this is below the threshold for acceptance due to the lack of significant novelty here.", "strength_and_weaknesses": "Strengths\n- Proves upper and lower bounds for performance of subset selection algorithm\n- Good evaluation with 6 baselines tested alongside the introduced algorithm, tested on 6 datasets and ablated on 3 NN architectures.\n- Provides theoretical analysis of error squashing which was missing from Cicalese et al 2020, when they introduced error squashing.\n\nWeaknesses\n- Seems to be a minor improvement on Cicalese et al. (2020); and the experimental results suggest the same-- with roughly the same performance (sometimes slightly worse and sometimes slightly better) as Cicalese's and Dasgupta's work.\n\nMinor comments & questions\n- Notation: \n-- In section 2/3: use of '[m]' describe set of all pool points is non-standard and would be nice to keep to the nomenclature in the subfield (e.g. notation used in Cicalese 2020, SVP by Coleman 2020 or Kilmasetty 2020).\n-- Switching of notation of error on hypothesis classes from err[h] to E interchangebly.\n-- Is E_{t} just shorthand for E_{h_t}\n- More clarity on improvements as compared to Cicalese\n- Add standard deviation bounds to experimental results based on multiple runs.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BcJ30vtmfuf", "reviewer": "Reviewer_zPDn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the author(s) considered the problem of data subset selection. The author(s) proposed a machine teaching subset selection algorithm with theoretical guarantees. Through empirical experiments, the author(s) showed the advantage of the proposed algorithm.\n\n---", "summary_of_the_review": "The work in this paper is interesting; However, there are some unclear aspects in the description (including experiments) of this paper. Maybe it needs the author(s) to clarify them.\n\nIn addition, in this paper, the author(s) performed empirical experiments, but I am not sure the empirical description/experiments would be enough to reproduce because no code of this paper seems to be provided. Thanks.\n\n---\n", "strength_and_weaknesses": "### Strength:\n\n1. Selecting an informative subset from a dataset is significant in practice. An obvious advantage is that the training/computation time of algorithms based on such data can be largely reduced.\n\n2. Theoretical analysis and empirical experiments are both performed for validating the proposed algorithm.\n\n---\n\n### Weaknesses:\n\n1. Maybe some technique assumptions in this paper are not so reasonable.\n\n2. Some descriptions (including experimental details) in this paper are not clear.\n\nFor more details, please see the section of \"Clarity, Quality, Novelty And Reproducibility\".\n\n\n---\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A23Hp_WCg3P", "reviewer": "Reviewer_3ZRi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper identifies theoretical gaps in the existing literature on data subset selection in machine teaching, and analysis the justification of the error-squashing heuristics adopted in the previous works. With that, the authors propose a data subset selection algorithm with near-optical guarantees on the query complexity and the size of the returned subset. The paper also shows empirical experiments on 6 datasets, 6 baseline methods and 3 model architectures to demonstrate the effectiveness of the proposed algorithm.", "summary_of_the_review": "I am majorly concerned with the novelty of the paper. As discussed above, the algorithm mainly adopts existing techniques with an addition of a probability halving phase that allows drops in selection probability. The improvement in the theoretical guarantee of the algorithm is also likely due to this trick which essentially relaxes the problem setting. The second part on the theoretical understanding of error squashing is nice to have, but I wonder how much theoretical and empirical insights it could have to impact the community to move forward. The practicability of the method is also largely limited by its time and computational overhead. The authors could probably explain more about the significance of the theoretical understandings presented.", "strength_and_weaknesses": "Strengths:\n1. A solid theoretical analysis of the algorithm is given, alongside a detailed theoretical section for justifying the use of error squashing.\n2. Theorems and propositions are explained well with interpretations. \n3. Rather extensive experiments are conducted across multiple baseline methods, datasets and model architectures.\n\nWeaknesses:\n1. The novelty of the paper needs further justification.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject