证明了用常见方法无法学习莫比乌斯函数
On (not) learning the Möbius function
- 通过数字特征相关性分析，揭示学习障碍
- 在多种输入结构下，莫比乌斯函数相关性极低
- 结果与数字型素数定理密切相关，适合数论研究者
我们证明了使用核方法、含噪声梯度法以及相关统计查询算法学习莫比乌斯函数或刘维尔函数的下界。这些结果源于对莫比乌斯函数与不同有限阿贝尔群的数字特征之间相关性的量化估计，群的类型由算法接收的输入数据决定。对多个素数取模对应循环群，而固定素数的进制展开则对应初等阿贝尔p-群。此外，此类下界与特定类型的数字型素数定理密切相关。
原文摘要 · Abstract (English)
We prove lower bounds on learning the Möbius or Liouville function with a variety of standard learning techniques, including kernel methods, noisy gradient methods, and correlational statistical query algorithms. These results follow from quantitative bounds on the correlation of Möbius with digital characters of various finite abelian groups, where the group is dictated by the type of input data the algorithm is given. Using residues mod $p$ for many different primes corresponds to a cyclic group, and using the base $p$ expansion for a fixed prime corresponds to an elementary abelian $p$-group. We also note that lower bounds of this form are closely related to certain types of digital prime number theorems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。