Sparsity in real-world functions. Even in the noiseless setting, in order to perfectly learn a general pseudo-Boolean function \(f (\cdot )\) , its evaluations on all input binary vectors \(x \in \lbrace  \pm 1 \rbrace ^{d}\)  are required, which may be very expensive. In the presence of additional structures, this significant statistical and computational cost can be mitigated. One such structure that has been observed in real-world biological and physical functions is sparsity in WHT [1]}, [2]}, [3]}. In particular, in the theoretical analysis of this paper, we assume that the ground-truth function \(f_{*}\)  has a sparse polynomial representation composed of at most \(k\)  monomials. Namely, \(\Vert  \mathbf {H}f_{*} (\mathbf {X}) \Vert _0 \le k\) , where \(k \ll 2^d\)  is typically unknown.
