On (not) learning the Möbius function
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning to Understand: Identifying Interactions via the Möbius Transform
One of the key challenges in machine learning is to find interpretable representations of learned functions. The M\"obius transform is essential for this purpose, as its coefficients correspond to unique importance score…
Learning TheoryComputational Aspects of the Mobius Transform
In this paper we associate with every (directed) graph G a transformation called the Mobius transformation of the graph G. The Mobius transformation of the graph (O) is of major significance for Dempster-Shafer theory of…
Studying number theory with deep learning: a case study with the Möbius and squarefree indicator functions
Building on work of Charton, we train small transformer models to calculate the M\"obius function $\mu(n)$ and the squarefree indicator function $\mu^2(n)$. The models attain nontrivial predictive power. We then iterativ…
Beyond Normal: Learning Spatial Density Models of Node Mobility
Learning models of complex spatial density functions, representing the steady-state density of mobile nodes moving on a two-dimensional terrain, can assist in network design and optimization problems, e.g., by accelerati…
Adaptive Sparse Möbius Transforms for Learning Polynomials
We consider the problem of exactly learning an $s$-sparse real-valued Boolean polynomial of degree $d$ of the form $f:\{ 0,1\}^n \rightarrow \mathbb{R}$. This problem corresponds to decomposing functions in the AND basis…