arXiv:2607.21761math.COcs.LG2026-07被引 1

通过函数理论方法,改进了从树结构中提取阈值的边界,解决两个开放问题。

Encoding orders and trees in real-valued functions

  • 用实值函数重构树结构中的弱阈值,突破原有限制
  • 得到比之前更优的界,实现至少双指数级上界控制
  • 适用于稳定函数的量化正则性分析,适合学习理论研究者

我们证明了霍奇斯关于从二叉树中提取序性质的定量结果在函数理论中的类比。此前,达斯卡拉基斯与戈洛维奇、安德森与贝内迪克特已获得类似结论。这些成果源于统计学习理论,其中二叉树由顺序肥散维数刻画,序性质则由各类“阈值”概念控制。本文第一个主要结果(定理1.11)聚焦于从树中提取较弱的阈值形式,相比早期更严格版本,给出了显著更优的界。该结果的动机来自一篇配套论文,用于推导“稳定函数”量化正则性引理中的高效界。本文利用定理1.11以更强形式重证安德森与贝内迪克特的结果并改进界。此外,还用其证明了对偶顺序肥散维数的至多双指数界,解决了开放问题。第二个主要结果(定理1.14)为达斯卡拉基斯与戈洛维奇关于从大顺序肥散维数中提取“紧阈值”的结果提供了新证明,并进一步优化界,同时解决了与容·金与特瓦里所声称结果相关的一个证明修正问题。

原文摘要 · Abstract (English)

We prove function-theoretic analogues of a quantitative result of Hodges on extracting the order property from a sufficiently large 2-tree coded in a binary relation. Similar analogues for functions were previously obtained by Daskalakis and Golowich and by Anderson and Benedikt. These results are from statistical learning theory, where 2-trees are captured by sequential fat-shattering dimension, and the order property is controlled by various notions of "thresholds". Our first main result (Theorem 1.11) focuses on extracting a less restrictive kind of threshold from a tree, and yields significantly better bounds compared to what can be obtained from earlier results focusing on more restrictive versions. Part of the motivation for Theorem 1.11 lies in a companion paper, where this theorem is used to obtain efficient bounds in quantitative regularity lemmas for "stable functions". Here will use Theorem 1.11 to reprove a result of Anderson and Benedikt in a stronger form and with improved bounds. We also use Theorem 1.11 to prove an at most double-exponential bound on dual sequential fat-shattering, which resolves an open problem. In our second main result (Theorem 1.14), we give a new proof of a result of Daskalakis and Golowich on extracting "tight thresholds" from large sequential fat-shattering dimension, with improved bounds. This resolves another open problem related to correcting the proof of a result claimed by Jung, Kim, and Tewari.

函数理论学习理论阈值提取双指数界

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。