Adaptive Sparse M"obius 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,1n rightarrow ℝ. This problem corresponds to decomposing functions in the AND basis and is known as taking a M"obius transform. While the analogous problem for the parity basis (Fourier transform) f: -1,1 n rightarrow ℝ is well-understood, the AND basis presents a unique challenge: the basis vectors are coherent, precluding standard compressed sensing methods. We overcome this challenge by identifying that we can exploit adaptive group testing to provide a constructive, query-efficient implementation of the M"obius transform (also known as M"obius inversion) for sparse functions. We present two algorithms based on this insight. The Fully-Adaptive Sparse M"obius Transform (FASMT) uses O(sd log(n/d)) adaptive queries in O((sd + n) sd log(n/d)) time, which we show is near-optimal in query complexity. Furthermore, we also present the Partially-Adaptive Sparse M"obius Transform (PASMT), which uses O(sd2log(n/d)) queries, trading a factor of d to reduce the number of adaptive rounds to O(d2log(n/d)), with no dependence on s. When applied to hypergraph reconstruction from edge-count queries, our results improve upon baselines by avoiding the combinatorial explosion in the rank d. We demonstrate the practical utility of our method for hypergraph reconstruction by applying it to learning real hypergraphs in simulations.