Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper study unlabeled sample compression schemes for extermal classes and intersection-closed classes.

These 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.

Extermal classes are known to have labeled sample compression linear in the VC - Moran and Warmuth 2016.
Maximum classes and extremal intersection-closed classes have unlabelled compression schemes linear in the VC  - Chalopin, Chepoi, Moran, and Warmuth (2018).

Main contributions: 
- Intersection-closed class can be embedded into an extremal intersection-closed class with a linear increase in VC dimension.
- Simplifying the construction for unlabeled compression for maximum classes.
- 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).

strengths_and_weaknesses: The paper makes nice progress toward showing an unlabeled compression scheme for extermal classes,
which is of great importance in the sample compression literature.

Also, 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.

Altogether, I recommend accepting the paper.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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)$. 
The authors also show that intersection-closed concept classes have compression schemes linear in their VC dimension.

strengths_and_weaknesses: ### Orginality and Quality 

The 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. 

### Significance

This 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. 

### Presentation and Clarity

Despite 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. 

I am open to changing my score (5 -> 6/7) should the authors commit to make the paper more accessible by addressing the comments below.


questions: ### Comments/suggestions for accessibility and clarity

- Shattering should be included in Definition 2.1 in relation to the definition of projection, as it is not introduced anywhere
- 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.
- (Unlabeled) sample compression schemes are nowhere formally defined in the paper despite being the central object of study
- 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.


limitations: Yes and N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies compression schemes which is a formalism that is aimed at classifying learnability via compressability. 
It 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. 
strengths_and_weaknesses: The paper makes some progress on the relation between compression schemes and VC dimension: a well studied subject in 
computational learning theory. 
The results are highly specific and seem to be relevant for a very small crowd. 
I think this paper should be a better fit for a smaller theory conference such as COLT or ICALP.  
Furthermore, the presentation of the paper is not ideal with several awkwardly phrased sentences and other issues
(e.g., the end of 33, 55 and using undefined term of VC-d in 33).
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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).
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.

**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.
questions: - Line 31, could not understand what this sentence is saying.
- Line 31, what are VC-d classes? Please define.
- 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.

limitations: Yes
review_title: null

Meta-review: metareview: The reviewers agree that this is a solid contribution. Please do revise the paper according to the reviewers comments and the discussion. In particular, the reviewers point out that the presentation can and should be improved: this is important because NeurIPS is a broad conference and the theoretical paper is init should be accessible to the general learning theory community.
confidence: Certain
Decision: Accept