用拓扑方法给出学习理论中列表可复现性的精确边界。
Tight list replicability bounds via a novel sphere covering theorem
- 基于Borsuk-Ulam定理推出球面覆盖新定理，指导列表大小设计。
- VC类的列表大小与精度关系达到理论最优，依赖维度和复杂度。
- 大间距超平面场景下，最优列表大小为⌈d/2⌉+1，适合高维学习研究者。
近年来，列表可复现性成为学习理论中形式化可重复性的框架。核心问题在于列表大小如何随精度参数和假设类的自然复杂度变化。为获得列表可复现性的紧致界，本文基于Borsuk-Ulam定理推导出一个新颖的拓扑球面覆盖定理：若d-球面被若干位于开半球内的开集覆盖，则至少有d+1个集合存在公共交集。利用该结果，我们得到了VC类中列表大小与精度关系的紧致界。对于大间距半空间，在间距不过大的情况下，最优列表大小等于环境维度；当间距极大时，我们构造了一个可复现算法，实现最小列表大小⌈d/2⌉+1。
原文摘要 · Abstract (English)
In recent years, list replicability has emerged as a framework for formalizing reproducibility in learning theory. A central question is how the required list size relates to the accuracy parameter and natural complexity measures of the hypothesis class. To achieve sharp bounds on list replicability, we prove a novel topological sphere covering theorem, derived from the Borsuk-Ulam theorem. Specifically, if the $d$-sphere is covered by open sets, each of which lies in an open hemisphere, then $d+1$ of these sets must have a common intersection. Using this result, we obtain a sharp bound on the relationship between list size and accuracy for VC classes. We also show that for large-margin half-spaces, provided the margin is not too large, the optimal list size equals the ambient dimension. However, when the margin is taken to be very large, we devise a replicable algorithm achieving the minimal list size of $\lceil d/2 \rceil + 1$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。