Sample Compression Scheme Reductions

We present novel reductions from sample compression schemes in multiclass classification, regression, and adversarially robust learning settings to binary sample compression schemes. Assuming we have a compression scheme for binary classes of size f(dVC), where dVC is the VC dimension, then we have the following results: (1) If the binary compression scheme is a majority-vote or a stable compression scheme, then there exists a multiclass compression scheme of size O(f(dG)), where dG is the graph dimension. Moreover, for general binary compression schemes, we obtain a compression of size O(f(dG)log|Y|), where Y is the label space. (2) If the binary compression scheme is a majority-vote or a stable compression scheme, then there exists an ε-approximate compression scheme for regression over [0,1]-valued functions of size O(f(dP)), where dP is the pseudo-dimension. For general binary compression schemes, we obtain a compression of size O(f(dP)log(1/ε)). These results would have significant implications if the sample compression conjecture, which posits that any binary concept class with a finite VC dimension admits a binary compression scheme of size O(dVC), is resolved (Littlestone and Warmuth, 1986; Floyd and Warmuth, 1995; Warmuth, 2003). Our results would then extend the proof of the conjecture immediately to other settings. We establish similar results for adversarially robust learning and also provide an example of a concept class that is robustly learnable but has no bounded-size compression scheme, demonstrating that learnability is not equivalent to having a compression scheme independent of the sample size, unlike in binary classification, where compression of size 2O(dVC) is attainable (Moran and Yehudayoff, 2016).