Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
Nov 28, 2022
Speakers
Joachim Rubinstein
Speaker · 0 followers
Benjamin Rubinstein
Speaker · 0 followers
About
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.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 f…
Organizer
NeurIPS 2022
Account · 952 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Reflection of Thought: Inversely Eliciting Numerical Reasoning in Language Models via Solving Linear Systems
Watch later
Fan Zhou, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Reinforcement Learning Approaches for Traffic Signal Control under Missing Data
Watch later
Hao Mei, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Actor Prioritized Experience Replay
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Wearable-based Human Activity Recognition with Spatio-Temporal Spiking Neural Networks
Watch later
Yuhang Li, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
C-Mixup: Improving Generalization in Regression
Watch later
Huaxiu Yao, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Calibration of Large Neural Weather Models
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%