证明双曲空间在层次数据学习上比欧氏空间更高效，样本需求可指数级降低。
Minimax Rates for Hyperbolic Hierarchical Learning
- 用双曲嵌入克服欧氏空间的体积坍塌问题，实现常数级光滑性
- 在深度为R、分支因子m的树结构上，仅需O(mR log m)样本即可学习
- 适用于层次化数据建模，如生物分类、语义网络等场景
我们证明了在标准Lipschitz正则化下，对于深度为R、分支因子为m的层次数据，欧氏表示与双曲表示之间存在指数级的样本复杂度差异。首先建立欧氏空间的几何障碍：任何有界半径嵌入都会导致体积坍塌，将指数级远的点映射到邻近位置，迫使Lipschitz常数至少为exp(Ω(R))，从而在容量控制下导致指数级样本复杂度。而在双曲空间中，该障碍消失：常数失真嵌入可实现O(1)-Lipschitz可实现性，使得学习仅需n = O(mR log m)样本。通过Fano不等式证明Ω(mR log m)下界，表明双曲表示达到信息论最优。此外，还揭示了与几何无关的瓶颈：任意秩k预测空间仅能捕捉O(k)个标准层次对比。
原文摘要 · Abstract (English)
We prove an exponential separation in sample complexity between Euclidean and hyperbolic representations for learning on hierarchical data under standard Lipschitz regularization. For depth-$R$ hierarchies with branching factor $m$, we first establish a geometric obstruction for Euclidean space: any bounded-radius embedding forces volumetric collapse, mapping exponentially many tree-distant points to nearby locations. This necessitates Lipschitz constants scaling as $\exp(Ω(R))$ to realize even simple hierarchical targets, yielding exponential sample complexity under capacity control. We then show this obstruction vanishes in hyperbolic space: constant-distortion hyperbolic embeddings admit $O(1)$-Lipschitz realizability, enabling learning with $n = O(mR \log m)$ samples. A matching $Ω(mR \log m)$ lower bound via Fano's inequality establishes that hyperbolic representations achieve the information-theoretic optimum. We also show a geometry-independent bottleneck: any rank-$k$ prediction space captures only $O(k)$ canonical hierarchical contrasts.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。