将多分类等复杂学习任务的压缩方案，归约为二分类压缩方案，推动压缩猜想的证明。
Sample Compression Scheme Reductions
- 将多分类、回归等任务的压缩问题转化为二分类压缩问题处理。
- 多分类压缩大小为 $O(f(d_G)\log|Y|)$，回归压缩大小为 $O(f(d_P)\log(1/ε))$。
- 揭示鲁棒学习中可学习但无有界压缩的反例，挑战压缩与可学习的等价性。
我们提出了从多分类、回归以及对抗鲁棒学习中的样本压缩方案到二分类压缩方案的新规约。假设存在大小为 $f(d_ ext{VC})$ 的二分类压缩方案，其中 $d_ ext{VC}$ 是 VC 维：（1）若该二分类方案为多数投票或稳定压缩方案，则存在大小为 $O(f(d_ ext{G}))$ 的多分类压缩方案，其中 $d_ ext{G}$ 为图维数；对一般情况，压缩大小为 $O(f(d_ ext{G})\log|Y|)$，$Y$ 为标签空间。 （2）对取值于 $[0,1]$ 的函数回归，若二分类方案为多数投票或稳定方案，则存在大小为 $O(f(d_ ext{P}))$ 的 $\varepsilon$-近似压缩方案，$d_ ext{P}$ 为伪维数；一般情况压缩大小为 $O(f(d_ ext{P})\log(1/\varepsilon))$。若样本压缩猜想（即任何有限 VC 维的二分类概念类存在大小为 $O(d_ ext{VC})$ 的压缩方案）成立，这些结果将直接推广至其他学习设置。我们还得到了对抗鲁棒学习的类似结果，并构造了一个鲁棒可学习但无有界压缩方案的概念类，表明鲁棒学习中可学习性不蕴含压缩性，不同于二分类中可达 $2^{O(d_ ext{VC})}$ 大小的压缩。
原文摘要 · Abstract (English)
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(d_\mathrm{VC})$, where $d_\mathrm{VC}$ 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(d_\mathrm{G}))$, where $d_\mathrm{G}$ is the graph dimension. Moreover, for general binary compression schemes, we obtain a compression of size $O(f(d_\mathrm{G})\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(d_\mathrm{P}))$, where $d_\mathrm{P}$ is the pseudo-dimension. For general binary compression schemes, we obtain a compression of size $O(f(d_\mathrm{P})\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(d_\mathrm{VC})$, 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 $2^{O(d_\mathrm{VC})}$ is attainable (Moran and Yehudayoff, 2016).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。