Adaptive Sparse Möbius Transforms for Learning Polynomials

Yigit Efe Erginbas, Justin Singh Kang, Elizabeth Polito +1

We consider the problem of exactly learning an $s$-sparse real-valued Boolean polynomial of degree $d$ of the form $f:\{0,1{\}}^n\to \mathbb{R}$. This problem corresponds t…