摘要 Abstract
近年来,学习理论取得了显著进展,表明对于全概念类,列表可复制性、全局稳定性、差分隐私(DP)可学习性和共享随机性可复制性都与Littlestone维数的有限性等价。这一等价性是否可以推广到部分概念类?我们通过证明$d$维$\gamma$-间隔半空间的列表可复制数满足\[\frac{d}{2}+1 \leq \mathrm{LR}(H^d_\gamma) \leq d,\]其中结果随维度增长,回答了这个问题。由此可知,对于部分类,列表可复制性和全局稳定性不一定由有界Littlestone维数、纯DP可学习性或共享随机性可复制性推导得出。应用我们的主要定理,我们解决了几个开放问题:$\bullet$ 无限维大间隔半空间的每个去模糊化为全概念类的操作都有无界的Littlestone维数,回答了Alon、Hanneke、Holzman和Moran(FOCS '21)提出的一个开放问题。$\bullet$ 在$d$维欧几里得空间中的任何有限点集和齐次半空间的最大列表可复制数为$d$,解决了Chase、Moran和Yehudayoff(FOCS '23)提出的问题。$\bullet$ 大间隙条件下Gap Hamming距离问题的每个去模糊化操作都有无界的公共硬币随机通信复杂度。这回答了Fang、Göös、Harms和Hatami(STOC '25)提出的一个开放问题。我们的下界基于Chase、Chornomaz、Moran和Yehudayoff(STOC '24)提出的局部波苏克-乌拉姆定理的拓扑论证。对于上界,我们利用支持向量机(SVM)的泛化性质构建了一个列表可复制的学习规则。
Recent remarkable advances in learning theory have established that, for total concept classes, list replicability, global stability, differentially private (DP) learnability, and shared-randomness replicability all coincide with the finiteness of Littlestone dimension. Does this equivalence extend to partial concept classes? We answer this question by proving that the list replicability number of $d$-dimensional $\gamma$-margin half-spaces satisfies \[ \frac{d}{2}+1 \le \mathrm{LR}(H^d_\gamma) \le d, \] which grows with dimension. Consequently, for partial classes, list replicability and global stability do not necessarily follow from bounded Littlestone dimension, pure DP-learnability, or shared-randomness replicability. Applying our main theorem, we resolve several open problems: $\bullet$ Every disambiguation of infinite-dimensional large-margin half-spaces to a total concept class has unbounded Littlestone dimension, answering an open question of Alon, Hanneke, Holzman, and Moran (FOCS '21). $\bullet$ The maximum list-replicability number of any finite set of points and homogeneous half-spaces in $d$-dimensional Euclidean space is $d$, resolving a problem of Chase, Moran, and Yehudayoff (FOCS '23). $\bullet$ Every disambiguation of the Gap Hamming Distance problem in the large gap regime has unbounded public-coin randomized communication complexity. This answers an open question of Fang, G\"o\"os, Harms, and Hatami (STOC '25). Our lower bound follows from a topological argument based on the local Borsuk-Ulam theorem of Chase, Chornomaz, Moran, and Yehudayoff (STOC '24). For the upper bound, we construct a list-replicable learning rule using the generalization properties of SVMs.