Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
Authors: J. Hyam Rubinstein
Benjamin I. P. Rubinstein
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sample compression
Vapnik Chervonenkis dimension
Ample classes
Extremal classes
Intersection-closed classes

Abstract: The sample compressibility of concept classes plays an important role in learning theory, as a sufficient condition for PAC learnability, and more recently as an avenue for robust generalisation in adaptive data analysis. Whether compression schemes of size $O(d)$ must necessarily exist for all classes of VC dimension $d$ is unknown, but conjectured to be true by Warmuth. Recently Chalopin, Chepoi, Moran, and Warmuth (2018) gave a beautiful unlabelled sample compression scheme of size VC dimension for all maximum classes: classes that meet the Sauer-Shelah-Perles Lemma with equality. They also offered a counterexample to compression schemes based on a promising approach known as corner peeling. In this paper we simplify and extend their proof technique to deal with so-called extremal classes of VC dimension $d$ which contain maximum classes of VC dimension $d-1$. A criterion is given which would imply that all extremal classes admit unlabelled compression schemes of size $d$. We also prove that all intersection-closed classes with VC dimension $d$ admit unlabelled compression schemes of size at most $11d$.

Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
J. Hyam Rubinstein
Benjamin I. P. Rubinstein School of Computing & Information Systems University Melbourne Parkville, VIC 3052, Australia brubinsttein@unimmlll edu.adddaa. au
School of Mathematics & Statistics University of Melbourne Parkville, VIC 3052, Australia joachimuuni edu. .uu
Abstract
The sample compressibility of concept classes plays an important role in learning theory, sufficient condition for PAC learnability, and more recently for robust generalisation in adaptive data analysis. Whether compression schemes of size (dd) must necessarily exist for all classes of VC dimension d is unknown, but conjectured to be true by Warmuth. Recently Chalopin. Chepoi, Moran, and Warmuth (2018) gave a beautiful unlabelled sample compression scheme size VC dimension for all maximum classes: classes that meet the Sauer-Shelah Perlees Lemma with equality. They also offered a counterexample compression schemes based promising approach known as corner peeling. In this paper simplify and extend their proof technique to deal with so-called extremal classes of VC dimension d which contain maximum classes of VC dimension d 1. A criterion is given which would imply that all extremal classes admit unlabelled compression schemes of size d. We also prove that all intersection-closed classes with VC dimension d admit unlabelled compression schemes of size at most 11d.
1 Introduction
Littlestone and Warmuth 1986) initiated the study of sample compression schemees as alternative characterisation of probably approximately correct (PAC) learnability, to finite (VC) dimension. Informally sample compression scheme for concept class comprises compressor and reconstructor: while the compressor represents samples labelled by the class as a labelled or unlabelled subsample, the reconstructor must be able to recover concept consistent with the original labelled sample given only this representation. Littlestone and Warmuth (1986) demonstrated remarkably simple proof of PAC learnability for any concept classes with labelled compression schemes provided compressed representations have bounded size, constant in the original sample size. They conjectured that bounded labelled compression schemes should also be necessary for PAC wtaobbiittycmompttii the characterisation -ppecffiiii that all VC-d concept classes (those having VC dimension d) have labelled compression schemes of size d. This conjecture, for size O(d). remains open now more than 35 years later, and stands as one of the oldest open problems in learning theory. addition proving PAC generalisation bounds (von Luxburg, Bousquet, and Schölkopf [004] Langford] 2205), compression has found important connections to generalisation in the adaptive data analysis setting (Cummings, Ligett, Nissim, Roth, and Wu 2016).
While Littlestone and Warmuth ( (1986) conjectured the existence of labelled schemes of size d for all VC-d classes, Warmuth (2003) later relaxed this to Odd), while Kuzmin and Warmuth (007 conjectured size ((d) unlabelled compression schemes. (In unlabelled schemes, the compressor representations omit labels; such schemes of size & imply labelled schemes of size k.) Indeed VC-d classes are known that cannot be unlabelled compressed to size (Pálvölgyi and Tardos 2020
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Notable progress towards resolving the sample compression conjecture has involved compressing familiee of concept classes. Shortly after the original conjecture Floyd (1989) proved that all maximum concept classes C (those meeting the Sauer-Shelah-P Perles Lemma with equality) can be label compressed to size VC (C) (Floyd and Warmuth| 1995). Chalopin et al. (2018) recently proved the same bound but with unlabelled compression, while also providing an elegant counter example to the same result for so-called corner peeling schemes. This shows that the constructions of corner peeling schemes by Kuzmin and Warmuth (2007) and Rubinstein and Rubinstein (2012) are incorrect. Moran and Yehudayoff (2016) proved that all VC-d classes can be label compressed to size exponential in d. Recently Pálvölgyi and Tardos (2020) offered examples of VC classes which cannot admit unlabelled compression schemes of size
Moran and Warmuth (0016) discover labelled compression schemes for extremal classes, which contain cubes for any coordinates shattered by the class, and generalise maximum classes. It is unknown if all extremal classes admit unlabelled compression schemes of size ((d). In this paper, we give criterion on extremal classes to admit unlahelled compression schemes of size VC dimension
Note that in Chalopin et al. (2018), a beautiful counterexample is given to the possibility of all maximum classes having corner peeling unlabelled compression schemes of size VC dimension. This shows that the constructions of comer peeling schemes in Kuzmin and Warmuth (2007) and
Rubinstein and Rubinstein (0122) are incorrect.
A promising approach to the general conjecture- and a strong motivation for compressing special families of concept classes-is via embedding,
compression scheme restricts to any subclass. So, there is interest in embedding general VC-classes into larger classes with good compression properties. [Rubinstein, Rubinstein, and Bartlett (2055) proved that VC-d classes cannot always be embedded in maximum classes of VC dimension less than 2d - 1. Embedding VC-d classes into maximum classes of VC-dimension (ld) could still achieve compression to size (dd) in general.
Intersection-closed classes those closed under coordinate-wise multiplication-arre another promis- ing focus for compression, any class can be embedded into an intersection-closet class. In this paper, we show that any intersection-clen closed class with the VC dimension increasing from d to 11d. These extremal intersection-closee classes have VC-sized unlabelled compression schemes by Chalopin et al.] (2018). As such, we establish for the first time that intersection-closed classes can be unlabelled compressed to size linear in their VC dimension. We offer a short proof of the result by Chalopin et af.] (2018) that maximum classes have VC dimension d-size unlabelled compression schemes and extend this extremal classes which contain maximum classes of VC dimension d - 1. Finally we give an efficient method compute the VC dimension of the intersection closure of a class. In particular, this could be useful in searching for collections of classes for which the VC dimension does not increase by much when passing to the intersection closure and then constructing the above unlabeled compression scheme.
class can be embedded into an extremal intersection-
2 Preliminaries
Given n E IN we call a subset of the binary n-cube C C 10, "'"""",aa a concept class with elements v E C concepts. These come from restrictions of classifier families, on samples of instances [ We equate each instance in [n] {1, ..... nn with coordinates, axes or colours of the n-cube. An important combinatorial parameter is the VC dimension, which used to bound concept class cardinality.
Definition 2.1 (Vapnik and Chervonenkis, 197I). The VC dimension of concept class C C
(0, 13"" is defined as (C)
max {14] I I [n], proj, (C) {0, 131"1,, where proj, (C)
{ (Vi)ier : E C} is the set of coordinate projections of the concepts of C on coordinates / C [m]]
C is said to shatter I when the projection proj, (C) {0, 13 "1 is onto the /cl-cube.
Lemma 2.2 (Sauer-Shelah-Pere Perles Lemma, Vapnik and Chervonenkis 1971 Shelah 1972
Sauer
1972). The cardinality of any concept class C {0, 13"h is bounded by |C| Vyre
Concept classes meeting equality in Sauer's Lemma are called maximum Welzi 1987). A cubical- complex structure can be put on concept classes C C {0, 13". To begin, each v E C is a vertex, and
CCnnsider family of classifiers F mapping input domain X' to labels (0, 1}. On sample x E x the family is represented by induced concept class C =
f F).
2

---

pairs of Hamming-1 1 separated vertices are edges, of the one-inclusion graph of C (Haussler, Little stone, and Warmuth 1994). Each higher-order cube all points varying over set of coordinates, the cube's s colours; a cube's s common values on non-colour coordinates make up its anchor. (Equivalently d-cubes are pre-images of points under a projection from the binary (m + dl-cube to the binary m-cube.) Any d-maximum class has a special structure as complete collection of d-cubes:
Definition 2.3 (Rubinstein, Bartlett, and Rubinstein, 2009). A set of d-cubes S of cardinality (2) is called d-complete if for all S [x] of cardinality d, there exists cj with proj, (c1) {0, 1)%.
Another property of concept class of being shortest-path closed-also known as isometric (Chalopin et al., 20hrr- every pair of points in C. has a shortest path contained in C (Kuzmin and Warmuth| 2007; | Rubinstein and Rubinstein 2012). We will be especially interested in extremal classes also known as ample classes (Chalopin et al. 2018).
Definition 2.4. A class C S {0.1)*
yt is extremal if whenever C shatters some I C [na], then there is subcube C C which maps bijectively to the -cube via projs (-). That is, projs (c) {0, 1)"
All maximum classes are extremal and extremal classes shortest-palt path closed (Moran and Warmuth 2016), while the complements of extremal classes are themselyes extremal (Bandelt, Chepoi, Dress, and Koolen 2006 [Bollobás and Radclifie 1995 Lawrence 1983). As example, a VC one dimensional maximum (respectively extremal) class is a tree with one (respectively at most one) edge for each colour. An extremal counter-part to Sauer's Lemma was independently discovered by Pajor (1855), Bollobás and Radcliffe [1955, Dress (197). and Anstee, Rónyai, and Sali (2002).
Lemma 2.5 (Sandwich Lemma). For any extremal class C, its cardinality is equal to both the number of shatterings of C and the number of cube types (an equivalence class of cubes which all huve the same set of colours) in C.
Extremal and maximum classes have an elegant recursive structure that is best studied by inductive arguments. One such tool is the projection operator proj, (C). The reduction C S projj (C) is the subset of points with non-unique pre-image under the projection, while the tail is the subset of proj, (C) with unique pre-image under the projection (Welzl 1987 Kuzmin and Warmuth 2007).
Unlabelled compression schemes are defined by representation mappings. A party known as the compressor uses a representation mapping to summarise a C-labelled sample of any size with a small unlabelled subset of instances. A second party, the reconstructor, can invert this representation thanks to condition 1, to a concept that consistent with the original labelled sample, thanks to condition 2, (Chalopin et al.. 2018).
Definition 2.6 (Kuzmin and Warmuth 2007). Mapping is representation mapping of size k < n, also known as an unlabelled compression scheme of size k, of class C S (0, 1}" it satisfies:
1. is an injection between C and subsets of [n] of size most k; and
2. (non-clashing) projr(e)ur(e)) (v) # proir(e)ur(er) (v') for all + o' C.
3 The intersection closure operator
Examples of intersection-closed classes include axis-aligned hyperrectangles in R monomials, which are unions of orthogonal subcubes, and any union of orthogonal intersection- classes (Moran and Warmuth, 2016). Closed-below classes (Rubinstein et al., 2009) are intersection closed and extremal. All extremal classes of VC dimension I are intersection closed, so long as the origin is located in the class (Moran and Warmuth 2016).
sub-
Note the property of being intersection closed depends on the choice of origin.
We will use the notation w to denote the intersection of the vertices v, This is just the operation of bitwise Boolean multiplication v O w = (w)w), W,).) We can likewise let u1 O 2 x² = (II ui...., I w.,) denote the (iterated) intersection of vertices u u
Definition 3.1. A class C in the binary n-cube is called intersection closed if O E C, whenever v. w.W. E C. Let ट = @CC) {u' .... O u²) k < n. fu.....,2 u²} C C} denote the intersection closure of any class obtained via intersections of all finite subsets of C's concepts.
3

---

Proof. Suppose first that d achieves the smallest VC dimension of the intersection closure of C over all choices of origin. Let C denote the corresponding intersection closure of C. Then any projection of č to (d + ccube is not onto. Assume p(C) contained the vertex w = 1, 1, 1) and Lemma 3.2. For any concept class C C {0, 1 the intersection closure C is the unique smallest intersection-closed class containing C. and is contained in any Intersection-close class containing C. Moreover for any J S [r)], we must have proj. (C) = proj. (C).
Next is a useful result on computing the VC dimension of the intersection closure of a class. The key idea is that verify proj, (C) shatters, it is necessary and sufficient to show C has |J] + 1 vertices which project to the vertices with at most one coordinate O.
Definition 3.3. Suppose C' is a class in the binary n-cube with VC dimension d. We will say that C satisfies the k-close cube condition if there is vertex E {0, 1]"h and a complete union of (n k- - 1) Jeuuees in the complement of C so that each cube is distance at most one from v. For any k > k. C then also satisfies the k' k'cllose cuhe condition.
Theorem 3.4. Suppose C is class in the binary n-cube. The smallest VC dimension d for the intersection closure of C over all choices of origin, is the same as the smallest i for which C. satisfies the k-close cube condition.
I,..., , 1) with in the ith position and all other entries 1. Then all vertices w² = (1, ..... 1,0,
since p(C) is intersection closed, the image is the whole (d + 1)-cube contrary to assumption. The reason is that taking intersections of combinations of the vertices w gives all the vertices in the (d+u)- So at least one of the vertices w, wa, ...., w must not be in p(C). But then there an (n d 1)-ube with anchor of this form in the complement of C by taking the inverse image under p of this vertex. By choosing satisfies the d-close cube condition. For clearly each of our (n d - 1)-cuess in the complement of C has distance at most one from So this establishes that d 2 k, where k is the smallest value so that C' satisfies the k-close cube condition.
the vertex with all entries 1 in the n-cube, we have shown that C
Conversely suppose that C has collection of (n - k - 1) 1)-cubes in its complement, validating that C satisfies the k-close cube condition. We claim that ā < k', where d is the VC dimension of the intersection closure
for a suitable choice of origin. This shows that the smallest possible VC dimension d of the intersection closure of C over all choices of origin not larger than the smallest possible & where C satisfies the k-close cube condition.
For suppose that any projection p of C to the (k+ + cuuu is selected. By Lemma 3.2 p(C) - p(C)-p(C) In fact the intersection operator commutes with the projection operator, ie., ((,, w)) = ((p(u),((w) so the claim follows by Lemma 3.2 But now by assumption, if we choose the origin so that o is the vertex with all entries 1, then there is an (n k 1)-cube in the complement of C which has anchor with entries all I's except for at most one entry 0 and the anchor projects to vertex of the (I= + 1) cube. Hence the projection p of C is not onto and d < k.
We end with a useful property of the intersection closure operator. We will abuse notation by saying a class A is shortest path closed inside class B, if A C B and any two vertices of A are connected by a shortest path inside B. The main idea in the following theorem is that if C is shortest-pate closed, then X = (v u = u G w, u, w E C} shortest path closed inside C.
Theorem 3.5. C is shortest-pane closed then its intersection closure Č is also shortest-part closed.
Proof. We first observe the easy fact that if À is a shortest path in C consisting of vertices v1, v?,....,* and u E C then u O = (u @ pd : i E [k]] is a shortest path in possibly with repetitions. For an edge between successive vertices vf, w is transformed into u@ u @ which is either an edge of the same colour or a single vertex.
Our main claim that if C is shortest-path closed then X = {v:e= u Www, u, w E C} is shortest path closed inside C. Once this claim is established, the proof follows easily by repeating this step. For we can apply the claim to the class X to prove that the class (u v u @ w, u, w E X) consisting of all elements of C together with intersections of up to 4 elements of C is shortest-path closed. inside

---

X = C. Repeating at most log2n times, C is obtained and is shortest-pane closed. (Note that since @ v, elements of C can written as intersections of pairs of elements of C).
The first step in proving the main claim is to observe that there is a shortest path in X connecting any element u E C to any element u E X. To construct this path, start with a shortest path À between u, in C' and then form u @ A. As above this is shortest path, possibly with repetitions, between u, u in X. We conclude that given two vertices u, V E C, there is shortest path in X from u to e passing through u C v, by concatenating shortest paths in X from u to u C U and u C v to e.
To prove the main claim, choose elements v, v' E X. We want to find a shortest path in C connecting v, v'. Let u = u ④ w, v' = w' @ w' where u, w, u', w' E C. By the first step, there are shortest paths X, X in X connecting u, u' and w, w' and passing through u & u', w @ w' respectively.
Next, observe that e @ v'= = u u @ O' C w' = u @ w O w'. Split X, X' into X, X₂ for i = 1,2 so that Y1, X1 join u, w and u u w', w C w' respectively and 22, N22 join u u', w O w and u'; w' respectively. To establish the main claim, it clearly suffices construct shortest paths in C from to v @ v' and from e @ v' to v'. By symmetry, we will focus on the first of these.
We will prove slightly stronger claim. Namely assume A1 consists of ordered vertices 2
2 2,22, ,....,.* = u O u' and X has ordered vertices w = y', ........ = w @ w'. We will show that shortest path in X connecting v, Ô o' can be chosen have all vertices of the form 2t @ y²
To complete the proof, consider the rectangular grid of intersections 2 @ y², for 1 S S h and 1 S j S r with k, 2 1. Each small square of this grid is either a single vertex, one edge or 2-cube in X by the previous paragraph. We claim that there is a shortest path between the diagonally opposite entries
z² @ y², T o' = 2 @ y" using vertices in this grid.
It suffices to use the boundary of the grid to do this. So for example, consider the first path 2 @ y² for 1 < i S. k, followed by a second path zx @ y² for 1 S j S r. By the first observation in this proof, the first path is shortest with possible repetitions, as is the second path. To complete the argument, we need to show that the concatenation of these two paths is also shortest with possible repetitions.
Notice that the path År z¹_ 2²,,, ..... 2n runs between ends 21, 2* where 2* is between the origin of the binary n-cube and 21. So the same follows for the path with possible repetitions 2' @ y for 1 S k. The second path ²² o y¹ for J S r is of the same form and hence the concatenation of these two paths is also shortest with repetitions and the theorem proof is complete.
4 Extremal intersection-closed classes
In this section, we start with useful way of finding extremal intersection-closee classes, namely by checking they are shortest-pate and intersection-close -closed. We use this to establish the main result about intersection-closed classes, namely that they can embedded into extremal intersection closed classes, with the VC dimension d increasing to at most 11d. We then use a result of ChCllopn et al. (2018) to conclude this gives unlabelled compression schemes of size 11d for an intersection-closedd class of VC dimension d.
Theorem 4.1. Suppose that C is shortest-path and intersection closed. Then C is extremal.
Proof. Suppose a projection p: (0, 1}" - {0, 13 shatters C. We will prove there is a k-subcube c of C which witnesses the shattering.
Consider all the vertices of C which map the vertex w (1, 1) in the k-cube. Choose vertex e in this set which has smallest distance to the origin. (Since C is shortest-path closed and intersection closed, the origin is in and distance in C is the same as distance in the n-cube.)
Our claim is that there are vertices of E C, E [A)] so that the distance from v to each of is one and w' the vertex in the k-cube with all coordinates except single 0 at
p(v*)= 1,..,. O...., 1) the ith coordinate. Once this claim is established, it follows that since C is intersection closed, taking the intersections of subcollections of the vertices {ur : E [K]] generates the required k-subeube of C. Note e witnesses the shattering, since projection commutes with intersection and the vertices w, w² generate e under the operation of taking intersections.
To prove the claim, choose any vertex u E C so that p(u) = w². Since C is intersection closed, u' U u E C. Then p(u') p(u @ u)) p(u) @ p(u)- w C w = w Note that uf is vertex
5

---

Algorithm Shortest-Pane Closure
Input: intersection-closed class C' _ 10,
2: (II,..., .... - arbitrary ordering of [n]
3: C* c-c
4: for do
5: for w (v). I v do
6:
\(v.w) t 9)
1/v-w shortest path
7:
(1,j,0) f (1,1, 11)
8:
while [t -wll1 >
1 do
9:
U++1 < t
//next point on path
10:
while vi,; = Wn, do jojitll
11:
1,+1, +
//step towards w
X(U, w) t M(u, w) U {v++1}
13:
i (-i+1 end while
15: C + C* U ((,
end for
17: end for
18: return C*
between v and the origin, ie., for any coordinate where w' has value then v must also. Since is shortest-path closed, shortest path À exists in C from e to w'. Moreover has vertices in order with distances decreasing to the origin, since w' is between v and the origin.
Let v' be the first vertex on À after Since p(A) is shortest path in the k-cube from w to w', it follows that p(v') is either w or w². If the former, this contradicts our choice of u as closest vertex in C to the origin which projects to If the latter then we have found our vertex v² with distance 1 to u and which projects to w². So this completes the proof of the claim and the result.
Remark 4.2. Chalopin et al. 2018) discusses the significance of properties of extremal intersection- closed classes, also known conditional antimatroids.
Remark 4.3. There is partial order on the binary n-cube given by w S when w is between e and the origin or equivalently there is shortest path from v to the origin passing through w. Choose an arbitrary ordering on [n]]. We will denote by X(e, w) the shortest path between v, w with vertices
U1 02 Up where 0,04441 differ in the first coordinate I; in the ordering of indices amongst all coordinates where v., w differ.
In the next result, we enlarge an intersection closed class C to become intersection-closed and shortest- path closed by adding all the vertices in the shortest paths A(u, w) between all pairs v, w E C.
Theorem 4.4. Any intersection-closed class C embeds in shortest-pane -atth closed and intersection- closed class C" given by Algorithul soo that d' 1ld where d, d' are the VC dimensions of C, C respectively. To construct C*, for every pair of vertices v, w C with w < v, add all the vertices in X(V, w)
Lemma 4.5. I is intersection closed then C* as constructed by Theorem 4.4 is intersection closed.
Proof. By definition, for any vertices u, ul E C* there are vertices v, w. v, w/ E C so that u A(v, "y,, u' x(v,w'). Moreover, w S. w/ < v'.
Since is intersection closed, both v @ v and w O w' are in C. We claim that u' is on the path A(u O v', w O n'te that as part of this claim, we require that w @ w' v
We begin with the latter claim. This is easy both w, w' have entry 1. But since w I v, w < v', u, o' has entry 1 at all the coordinates where w, w' respectively has entry 1. So for any coordinate where w w/ has entry 1, it follows immediately that both v, o' have entry and so does @ v'.
w/ has entry 1 at precisely the coordinates where
Next, the set of coordinates where has entry and u has entry 0 forms an initial segment of the coordinates where v has entries 1, using the ordering of the coordinates, since u E X(E, w)). similar analysis applies to the set of coordinates of u' which are 0 but the entries for of are 1.

---

To complete the proof that C is intersection closed, we show that the set of coordinates where the entries of v @ r' are 1 and the entries of u @ u' are forms an initial segment of the ordering of the coordinates where the entries of v @ v' are 1. It will then follow that u @ u' E X(u é v', w O w').
Now the set of coordinates where u O v has entries 1 are exactly those coordinates where both v, o' have entries 1. Moreover u O u' has entry 0 at coordinate if either u. or u' has entry 0. We complete the proof using an argument by contradiction. Suppose that there a coordinate z; such that u u' has entry 1 but this occurs before a coordinate 2; where u C u' has entry 0 and moreover v 3 v' has entry 1. Then at 2.. either u or u' has entry 0. Without loss of generality assume the former. Since @ u' has entry 1 at 2; it follows that u has entry 1 at Zz.. Note also that has entry at both 2,, Tyy- But this is a contradiction since the coordinates where has entry but u has entry should form an initial segment of the set of coordinates where v has entry 1. But we have found j >> i where u has entry at 24 and at 25. This establishes that C* is intersection closed.
Lemma 4.6. C is intersection closed then C* as constructed by Theorem 4.4 is shortest-pati closed.
Proof. By Lemma 4.5 it suffices to show that if v, w E C* then there are shortest paths from e, w to v @ w. since putting these together will give a shortest path from e to w. Next, it suffices to show there is shortest path in C* between any pair of vertices v u in C*, where u, for we can then apply this to the pairs v, U O w and w, V G w.
We claim that there is a vertex ei E C so that u S v S. Vi and there are shortest paths in C* joining both 11 u and v1, v. Firstly, since v E C*, there are vertices U1, U/ E C so that e is in X(11. 02). Hence S 01 and there is shortest path in C* from U1 to v, namely segment of X(U1, U2).
Next, since u S v. then u S Vr. Moreover u lies on a path X(u1, U2) where U1 U2 C, since u E C+. Then 01 @ 01 E C and U1 3 S u1. Since u S U1, u S u1, it follows that u S 0n @ u1.
Notice that must lie X(11 O u1, uz). To verify this, observe all the coordinates where entries of ij @ i, differ from entries of u are also coordinates where U entries differ from u entries. Consequently, coordinates where entries of u and u2 differ, are lower in the coordinate ordering than those where entries of 0i @ uj and u differ. So this confirms that u E A(e @ u1, u2).
Combining X(U1, U1 @ U1) and A(U1 @ u1, u) gives a shortest path from U1 to in C*. So this completes the proof of the claim about V1.
To recapitulate, we have constructed shortest paths in C' from i1 to both u, v in C*, where S U1. U1, u S v. To complete the proof that there is a shortest path from v to u in C, we use induction on the Hamming distance from to v. To begin the induction, suppose this distance is O. Then clearly we are done, since there is a shortest path in C* from u to u.
Assume the distance from 01 to v is k and the result is true for Uj us, u* as above, where the distance from di u* is less than kt Let o' be the first vertex in the shortest path from en to v. Our aim is to show that there is a shortest path in C* from o' to u. By induction, it then follows there is a shortest path in C* from 0 to u.
The argument is similar to that in Theorem 3.5
Let = y4 v2 V' = u be a shortest path in C" We can construct shortest path o' = u y U' 12 ..... O' VOy" y" = where there is single repetition. Namely, since one of the edges joining y y² must have the same colour as the edge between U1, v', then o' @ y of @ yit All other pairs of vertices are distance apart and since C* is intersection closed, this shortest path is in C+. So this completes the proof.
Proof. (Theorem 4.4 remains to prove that the VC dimension of C* is at most 11d.
Choose any projection (0, 13 + {0, Ij By Sauer's Lemma, since the VC dimension of p(C) is at most d, the cardinality Ip(C) is at most F(d; 11d, }) x 2 where F(k;; n. p) is the cumulative binomial probability function.
Algorithm 1 constructing C* involves finding and adjoining shortest paths connecting suitable ordered pairs of points in C. So |C*| S n x IC|2 Similarly we see that pp(*)l < 11d x [p(C)]2 since the process of adjoining shortest paths is preserved under projection. Hence Ip(C" S 11d x F(d; 11d, 1)²² 222d x 1. Note that as pairs (v, w) are ordered by requiring that w S v, we get factor of 1.2 We claim that this upper bound is strictly less than 211d Then p cannot shatter and the VC dimension of C* is at most l1d - 1.
7

---

The key idea is to use Chemoof's 's inequality to estimate F(d; 11d, 22)
This is:
F d; 1ld, // S exp (-lld) x D
1
2)
where (( = + log i + (1 +) log 2(1 ) Substituting this into the previous upper
2d 2d 2 20d log 20). We can further simplify this to Ip(C*) & 1ld 1122d x 10 20-2 x 1.2 To complete the argument, we need to show the right side is strictly less than 2 Hence it suffices to show that
bound and simplifying, we obtain |p(c*) < 11 exp(22dlog
(11d)* x 11 x 10 20
2
Now if d 2 5 then 11 < 1.7 and d' < 1.4. So we can compute the left side is at most
11 20 1937 whereas the right side is 2048. (Here we leave out the factor 2 J.)
1.7 x 1.4 x 121 x
10
If = 4 then ! < 1.6 and 4 < 1.42. So we can compute the left side is as at most 1.6 x 1.42 x 11 1810 whereas the right side is 2048. So this completes the case when d 2 4. For the other cases, it is convenient to work directly, as Chernoff's inequality is not sharp.
121 x To
For d = 1, |p(C] < 12. as it has VC dimension at most 1 in the 11-cube. Hence |p(C*)| 1 11 1 x 2 792 which is less than 2048
Next suppose is bounded above by 22 x 2542 x 1 = 709, 676 which is less than 2048² = 4, 194, 304.
2. |p(C)| < 254, as it has VC dimension most in the 22-cube. Hence |p(C*)]
Finally assume d 3. |p(C) < 6018, has VC dimension at most 3 in the 33-cube. Hence |p(C*) I is bounded above by 33 x 6018² x 2 = 597, 569, 346 which is less than 2048 = 8, 589, 934592. O
Corollary 4.7. IfC is an intersection-closed class, then has a (corner peeling) unlabelled compres- sion scheme of size at most 11d.
Proof. This follows immediately by combining Theorem 4.4and and (Chalopin et al. 2018 Theorem 4.9).
5 Unlabelled compression schemes for extremal classes
The aim to give a condition on extremal classes which implies that they have unlabelled compression schemes. We then give some situations where this criterion is satisfied. We conjecture that it is always valid.
For maximum class C of VC dimension d, a reduction is maximum subclass of VC dimension d-11 1. So a reduction contains cubes with the same of colours as any non-maximal cube of C. It will turn out this is the key property we require of extremal classes to have unlabelled compression schemes of size d, namely they have proper extremal subclasses which have the same properties as reductions of maximum classes.
5.1 High-level strategy
The idea is inspired by Chalopin al. (2018). Start with pair (C, DD consisting of an extremal class and proper extremal subclass. The condition is that for every cube in which is not maximal, there a cube with the same colours in D. We call this the cubical colour condition of the pair C, and abbreviate it by eoc.
We will construct a bijection ø between the set S of maximal cubes of C' not in D and C C D. that v = ((c) E c. Note the cardinalities of these two sets are the same, by the Sandwich Lemma 2.5
applied to the two extremal classes C, DD. Then o C D S gives representation map for C D. which also separates the vertices of C \ D from the vertices of D. Therefore, any representation of D can be combined with the representation of C \ D give representation of C.
Suppose we can find a sequence of proper pairs of extremal subclasses (C, D), (D,E), (X, all satisfying eoc, ending with VC ())) < 2. Then we can start with a representation map of the VC-2
8

---

class Y (Chalopin et al. 20188) and extend to representation of X, then extending the representation all the way using this strategy.
5.2 Detailed construction
We construct Φ : C DD > and show it is bijection. Firstly, denote the extremal class which is the complement of DD by D Then every vertex of C \ D is in at least one maximal cube of D'
Define two cubes c, in {0, 1 to be complementary if the dimensions d, d of c, o satisfy + d' = n and è e is a single vertex. Recall that is the set of maximal cubes of not D. Denote the set of maximal cubes of D which intersect C by S".
Lemma 5.1. Assume (C,D) is proper pair of extremal classes satisfying cec. If E S, then there is a complementary maximal cube c² of Conversely, if c is a maximal cube of then there is complementary cube S. A maximal cube et of S cannot have two different complementary cubes in S.
Given Lemma 5.I we will call = c en c* the special vertex of We now note properties of v, assuming Lemma
Corollary 5.2. Assume that (C, () is proper pair of extremal classes satisfying coc. Let c.cc where e S and e* E are complementary maximal cubes. Then
The set of verlices v = en c", for all pairs of complementary maximal cubes e E and
E S*, is C D.
The mappings between e, c, are bijections between S,S" and (..
Proof. Lemma 5.1 gives a bijection between S and S* by the mapping from cubes to complementary cubes c². Moreover by the Sandwich Lemma applied to extremal classes C, D, the cardinalities of
C D, S* the same. Since the map from maximal cubes in $ to special vertices is an injection by Lemma 5.1 it must be a bijection onto C \\D D.
Proof of Lemma Let {0, + {0, 1jd be the projection to the colours of c E S. Recall coo for the pair C, D says that for any cube of C which is not maximal, there is cube of D with the same set of colours. So (DD) = {0, \ {w} for some vertex w. For the only other case that p(D) = (0, 134. But since extremal, this would imply D contained a cube with the same colours as c. This contradicts the assumption that is maximal in C, since for an extremal class, maximal cubes are unique for their sets of colours.
Define v, e* by p (w) ne, = (w) respectively. Clearly e c* = v. It remains to show that c* is maximal in D* and c* cannot intersect some other cube of S in single vertex.
Suppose that c* was properly contained in larger cube è in D Then p(č) would properly contain (w). Moreover ~ = p()). But this contradicts our observation above that p(D) = {0, {w). So this completes the argument that e is maximal.
Next, assume that c* is complementary of {o, 13" to {0, 1 given by the d colours of é. As above, (DD) consists of {0, 1]d with a single vertex t removed. Moreover, p-1 (1)) is maximal cube c' of D
a second maximal cube è S. Consider the projection
Now as n =² is single vertex, p(c*) = p0u" = u. As the cubes c* à are complementary, c" - === f-'(2) (u). But now we see that the colours of the anchor of c* are both the colours of and of à This gives a contradiction, since two maximal cubes of C cannot have the same set of colours. This completes the proof of Lemma 5.1
Finally we show that the map from a special vertex v to the colours the corresponding maximal cube c of S gives representation mapping of C D which also separates C \ D from D.
The second property follows immediately. For recall that if p is the projection given by the colours of c, then pDD) = (0, [0, (p(r)). So the colours of e clearly separate e from all the vertices of D. By this we mean that given any vertex w E D, u, w differ on least one coordinate from the colours of c.

---

Next suppose two vertices v, v' have the same values at all the coordinates corresponding to the colours of their corresponding cubes c. E S of dimensions d, d' respectively. Project {0, 1)" to the union of the colours c, by a mapping p". The image of p" a cube {0, 1]3d of dimension d" < d + d'. In this cube, C, D map extremal classes (C) = C", (D) D". We want to check that the pair of extremal classes (C", D") satisfy ccc. But this follows easily. Choose any non maximal cube é E C". As C' is extremal, there is cube cu in C which projects one-to-one to é and therefore has the same colours as Since on is not maximal, there is a cube ej in D with the same colours as cp- Then p"(c) (ci) is the required cube in D with the same colours as required.
Finally, c, project one-to-one by p" to cubes with colours spanning all of f0, 1]d". We claim that p"(u) * (u').. Since p"(v) (v), p"(')) are the special points for (c), (C(.."")()) p"(c') in {0, 138h, they cannot coincide, by Lemma 5.1 But then p"(v), (r)),,"(e) (e"))) must have at least one different value of their coordinates the colours of c, c' and hence the same is true for v, v'. So this gives representation for C D, as we have verified the no-clashing condition.
6 Applications
We apply the construction in Section 5 to two special collections of extremal classes.
Theorem 6.1. Suppose that C is extremal class of VC dimension d containing maximum class D of VC dimension
Then C has a d-size unlabelled compression scheme.
Proof. This follows immediately by the construction in Section 5 We only have to check that there is a sequence of pairs of extremal classes starting at C, DD all satisfying ccc. But this is easy since any maximum class of VC dimension is union of complete collection of maximal cubes of dimension i. Moreover any maximum class of VC dimension has reductions which are products of maximum classes of VC dimension
1 with {0, 1).
Theorem 6.2. Suppose that C is an extremal class of VC dimension 2. Then C contains proper extremal class so that for every edge C,, there is an edge of D of the same colour. lennc C has a compression scheme of size 2.
Proof. Rubinstein and Rubinstein (2088) develops the idea of splitting classes along a reduction (associated to coordinate projection). Choose a reduction C² of C which splits off component & with a smallest number of vertices, amongst all choices reductions and complementary components. Let D C \ E. We claim that D is extremal and contains edges of each colour in C.
The reason is that for any other reduction C2 of C. C2 NE + 0. then C2 + For if Cd 1 there is smaller component which C splits off from E, which is a contradiction. But C2 C² + 0 implies that D has edges of each colour of C. Showing DD is extremal is straightforward.
Remark 6.3. Chalopin al. (018)) showed that VC-2 extremal classes have unlabelled 2-compression schemes. Theorem 6.2 gives an alternate proof using our criterion for extremal classes to have such schemes in Section
7 Conclusion
Chalopin et al. 2018) constructed unlabelled compression schemes for maximum classes and extremal intersection- classes, while Moran and Warmuth (2016) developed labelled compression schemes for extremal classes. Here we have shown that intersection-closee classes can be embedded into extremal intersection-clost classes with an increase in VC dimension from d to 11d and so have 1id-size unlabelled compression schemes. We simplify and extend the d-size unlabelled compression schemes for maximum classes due to Chalopin et al. 2018), to apply to extremal classes of VC dimension d which contain maximum classes of VC dimension d - 1. We also give sufficient. condition for extremal classes to admit such compression schemes.
Acknowledgments and Disclosure of Funding
We acknowledge support from the Australian Research Council Discovery Project DP220102200
10

---

References
Richard P Anstee, Lajos Rónyai, and Attila Sali. Shattering news. Graphs and Combinatorics, 18(1): 59-73, 2002.
J. Bandelt, Chepoi, A. W. M. Dress, and Koolen. Combinatorics of lopsided sets. European Journal of Combinatorics, 27(5):669-689, 2006.
B. Bollobás and A. J. Radcliffe. Defect Sauer results. Journal of Combinatorial Theory, Series (A), 72(2):189-208, 1995.
Jérémic Chalopin. Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled sample compression schemes and comer peelings for ample and maximum classes. CoRR, abs/ (bss/181..0209 2018. PRRLhttp://arrtt org/ ht////////// 1812 02099 updated Jan 2022.
Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu. Adaptive learning with robust generalization guarantees. In Proceedings of the 29th Conference on Learning Theory, COLT, pages 772-814. PMLR, 2016.
A Dress. Towards theory of holistic clustering. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, 37:271-289, 1997.
Floyd. Space-bounded learning and the TR-89-061, ICSI, UC Berkeley, 1989.
dimension. Technical Report
Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the Vapnik-Chervonenkis dimension. Machine learning. 21(3):269-333 -004, 1995.
D. Haussler, N. Littlestone, and M.K. Warmuth. Predicting (0, 1} functions randomly drawn points. Information and Computation, 1 15(())2884-99))) 293, 1994.
D. Kuzmin and M.K. Warmuth. Unlabeled compression schemes for maximum classes. Journal of Machine Learning Research, 8(Sep):2047-208) 2007.
J. Langford. Tutorial on practical prediction theory for classification. Journal of Machine Learning Research, 6(Mar):273-306, 2005.
James Lawrence. Lopsided sets and onthant-inersecctin by convex sets. Pacific Journal of Mathe- matics, 104(1):155-173, 1983.
N. Littlestone and M.K. Warmuth. Relating data compression and learnability. Unpublished manuscript http: /wwww cse. ucsc. edu/ manfred/ppbs//mmat olivier.ppe 1986.
Shay Moran and Manfred K. Warmuth. Labeled compression schemes for extremal classes. In International Conference on Algorithmic Learning Theory, ALT, pages 34-49. Springer, 2016.
Shay Moran and Amir Yehudayoff. Sample compression schemes for VC classes. Journal of the ACM (JACM), 63(3):1-10, 2016.
Alain Pajor. Sous-espaces !T des espaces de Banach. Travaux en Cours. Hermann, Paris, 1985.
Dömötör Pálvölgyi and Gábor Tardos. Unlabeled compression schemes exceeding the VC-dimension. Discrete Applied Mathematics, 276: 102-107, 2020.
B. I. P. Rubinstein and J. H. Rubinstein. Geometric & topological representations of maximum classes with applications sample compression. In 21st Annual Conference on Learning Theory, COLT, pages 299-310, 2008
B. I. P. Rubinstein and J. H. Rubinstein. A geometric approach sample compression. Journal of Machine Learning Research, 12(AA1)::211-126, 2012.
B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein. Shifting: one-inclusion mistake bounds and sample compression. Journal of Computer and System Sciences: Special Issue on Learning Theory 2006, 75(1):37-59 January 2009.

---

J. Hyam Rubinstein, Benjamin I. P. Rubinstein, and Peter L. Bartlett. Bounding embeddings of VC classes into maximum classes. In V. Vovk, H. Papadopoulos, and A. Gammerman, editors, Measures of Complexity: Festschrift of Alexey Chervonenkis, pages 303-325. Springer, 2015.
N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13:145-147, 1972.
Shelah. A combinatorial problem: stability and order for models and theories infinitary languages. Pacific Journal of Mathematics, 41(1):247-261, 1972.
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):26-2800, 1971.
U. von Luxburg, O. Bousquet, and B. Schölkopf. A compression approach to support vector model selection. Journal of Machine Learning Research, 5:293-323, 2004.
M. K. Warmuth. Compressing to VC dimension many points. In 16th Annual Conference on Computational Learning Theory, COLT, 2003.
E. Welzl. Complete range spaces. Unpublished notes, 1987.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See throughout for precise theoretical claims, and Section for further directions addressing limitations.
(c) Did you discuss any potential negative societal impacts of your work? [No] The work seeks constructions of sample compression schemes for PAC learnable concept classes. The focus of the work is on learning theory.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the assumptions written in each of our results.
(b) Did you include complete proofs of all theoretical results? [Yes] All theoretical results are accompanied by complete proofs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A] No experiments
were run for this work.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We are not using existing assets or curating/releasing new assets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] This work involved no crowdsourcing or human subject research. (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "cThQ6ODrEC", "reviewer": "Reviewer_XGVd", "summary": "This paper studies sample compression schemes for extremal concept classes. The authors show that a criterion (containing a maximum class of smaller VC dimension by 1) for an extremal class C to admit a compression scheme of size $VC(C)$. \nThe authors also show that intersection-closed concept classes have compression schemes linear in their VC dimension.\n", "questions": "### Comments/suggestions for accessibility and clarity\n\n- Shattering should be included in Definition 2.1 in relation to the definition of projection, as it is not introduced anywhere\n- Extremal classes could have their own definition where “which maps bijectively to the $|I|$-cube…” is accompanied by an equation; it would be helpful to give examples of classes that are extremal but not maximal.\n- (Unlabeled) sample compression schemes are nowhere formally defined in the paper despite being the central object of study\n- Section 4 does not have any text apart from the theorem statements and their proofs (and Sections 3, 5 and 6 —apart from 5.1— also lack text). I think some text should be included to introduce the results, their significance, and the main idea behind the proof, perhaps at the cost of moving some full proofs to the appendix and give a proof sketch if the page limit is an issue.\n\n", "limitations": "Yes and N/A\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Orginality and Quality \n\nThe authors make progress towards understanding conditions under which concept classes have unlabeled compression scheme of size equal to their VC dimension. Their results and proofs seem sound and the proof techniques are interesting. \n\n### Significance\n\nThis is a bit outside of my are of expertise, but, given the related work mentioned in the paper, the results seem of interest to the learning theory community. \n\n### Presentation and Clarity\n\nDespite the interesting subject matter, I found the main part of the paper quite unaccessible and lacking in its presentation, especially considering that the audience for NeurIPS is quite broad (this is a shame, as the introduction section is itself enjoyable to read and seems quite thorough). For example, the main sections of the paper (except 5.1) barely contain any text contextualizing the results or giving a high-level idea of the proof techniques. While terse papers can be suitable for theory-heavy conferences, I believe that the presentation is not adequate for NeurIPS. \n\nI am open to changing my score (5 -> 6/7) should the authors commit to make the paper more accessible by addressing the comments below.\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "STNHjbWSy1f", "reviewer": "Reviewer_L9jW", "summary": "This paper studies the classic problem of whether concept classes with VC dimension d admit compression sizes of, say O(d) or even poly(d). In this paper, the authors show that extremal classes that satisfy a particular property admit unlabelled compression schemes of size d. They give three applications of this. First, they show that extremal classes of VC dimension d which contain maximal classes of dimension d-1 admit unlabelled compression schemes of size d. Second, they show that if extremal classes of VC dimension 2 have unlabelled compression schemes of size 2. Finally, they show that intersection-closed classes with VC dimension d have unlabelled compression schemes of size O(d).", "questions": "- Line 31, could not understand what this sentence is saying.\n- Line 31, what are VC-d classes? Please define.\n- Line 57, I found this paragraph somewhat hard to parse. It says that we can embed intersection-closed classes into extremal intersection-closed classes with a linear increase in VC-dimension. But then later, it is stated that intersection-closed classes have unlabelled compression linear in their VC-dimension. The latter would suggest there is no blow-up? From Theorem 4.4, I think you should say that we can embed intersection-closed classes into extremal intersection-closed classes with only a constant blow-up in VC-dimension.\n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths.** This is a fundamental problem in learning theory and the authors make some progress in this area. The paper is also reasonably well-written for the most part. The results in this paper may be of interest to other researchers who are also interested in better understanding compression.\n\n**Weaknesses.** The main drawback is that the contribution is somewhat incremental. Nonetheless, it is still progress in this area so it may be worth presenting to the ML theory community.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RjkVOwDHml", "reviewer": "Reviewer_iWvH", "summary": "The paper study unlabeled sample compression schemes for extermal classes and intersection-closed classes.\n\nThese classes are of special importance towards solving the sample compression conjecture - every class H has a labeled sample compression of size O((VC(H)). Later on, it was conjectured that it may be true also for unlabeled compressions.\n\nExtermal classes are known to have labeled sample compression linear in the VC - Moran and Warmuth 2016.\nMaximum classes and extremal intersection-closed classes have unlabelled compression schemes linear in the VC  - Chalopin, Chepoi, Moran, and Warmuth (2018).\n\nMain contributions: \n- Intersection-closed class can be embedded into an extremal intersection-closed class with a linear increase in VC dimension.\n- Simplifying the construction for unlabeled compression for maximum classes.\n- Showing that every extermal class of VC d, containing a maximum class of VC d-1, has an unlabeled compression scheme of size O(d).\n", "questions": " ", "limitations": "Some sections (in the main body of the paper) can be written in a less technical way, and provide more intuition/explanations of the proofs.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper makes nice progress toward showing an unlabeled compression scheme for extermal classes,\nwhich is of great importance in the sample compression literature.\n\nAlso, some useful results and techniques are introduced in the paper, that may be helpful in future research in the field, such as Thm 3.4, 3.5, 4.1.\n\nAltogether, I recommend accepting the paper.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "JOOQzWn3n27", "reviewer": "Reviewer_Ara5", "summary": "This paper studies compression schemes which is a formalism that is aimed at classifying learnability via compressability. \nIt is conjectured in the literature that VC dimension d should imply the concept class should have compression scheme of size at most d.  The main result of the paper is an 11d upper bound on the size of a compression scheme of concept classes that are closed under intersection and have VC dimension d. ", "questions": "What is the relevance of your results for the NeurIPS crowd? Are there any takeaways or  insights for people who have not encountered or studied compression schemes? ", "limitations": "The narrow scope and results obtained in this paper. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper makes some progress on the relation between compression schemes and VC dimension: a well studied subject in \ncomputational learning theory. \nThe results are highly specific and seem to be relevant for a very small crowd. \nI think this paper should be a better fit for a smaller theory conference such as COLT or ICALP.  \nFurthermore, the presentation of the paper is not ideal with several awkwardly phrased sentences and other issues\n(e.g., the end of 33, 55 and using undefined term of VC-d in 33).", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept