揭示高维大间隔半空间的可复制性极限，解决多个开放问题。
Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
- 基于局部Borsuk-Ulam定理证明下界，拓扑方法突破传统分析。
- 在d维空间中，最大可复制列表长度为d，与维度线性相关。
- 适用于学习理论、通信复杂性研究者，尤其关注随机与伪确定性差异。
我们证明了d维γ-边缘半空间的列表可复制性数满足 $ \frac{d}{2}+1 \le \mathrm{LR}(H^d_γ) \le d $，且随维度增长。该结果解决了多个开放问题： • 任意将无限维大边缘半空间消歧为全概念类时，其Littlestone维数无界，回应Alon等（FOCS '21）之问； • 大间隙情形下Gap Hamming距离问题的公共随机通信复杂度无界，回答Fang等（STOC '25）之问； • 随机与伪确定性通信复杂度存在O(1)与ω(1)的分离； • 任意有限点集与齐次半空间在d维欧氏空间中的最大列表可复制性为d，解决Chase、Moran、Yehudayoff（FOCS '23）之题； • 存在Littlestone维数为1的偏概念类，其所有消歧均具无穷Littlestone维数，回应Cheung等（ICALP '23）之问。下界由局部Borsuk-Ulam定理导出，上界通过SVM泛化性质构造可复制学习规则。
原文摘要 · Abstract (English)
We prove that the list replicability number of $d$-dimensional $γ$-margin half-spaces satisfies \[ \frac{d}{2}+1 \le \mathrm{LR}(H^d_γ) \le d, \] which grows with dimension. This resolves 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$ 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öös, Harms, and Hatami (STOC '25). $\bullet$ There is a separation of $O(1)$ vs $ω(1)$ between randomized and pseudo-deterministic communication complexity. $\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$ There exists a partial concept class with Littlestone dimension $1$ such that all its disambiguations have infinite Littlestone dimension. This resolves a problem of Cheung, H. Hatami, P. Hatami, and Hosseini (ICALP '23). Our lower bound follows from a topological argument based on a local Borsuk-Ulam theorem. For the upper bound, we construct a list-replicable learning rule using the generalization properties of SVMs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。