The problem of learning pseudo-Boolean functions with sparse polynomial representations has a rich history from both theoretical and empirical viewpoints. In particular, since the pseudo-Boolean functions being learned in their polynomial representations are linear functions in their coefficients, one may think about this problem as a special instance of sparse linear regression in dimension \(2^d\) . There are a number of algorithms for sparse linear regression such as LASSO [1]}, OMP [2]}, AMP [3]}, and FISTA [4]}. In particular, one may apply LASSO to get statistical guarantees for this problem which only scale linearly in the sparsity of the underlying ground truth polynomial \(k\)  and logarithmicaly in the problem dimension \(\log (2^d)\)  [5]}. Likewise, from another perspective, one may view the polynomial instead as a vector of \(2^d\)  outcomes \({f}({\bf X})\) ; the objective of the learner is to approximate \(f (\mathbf {X})\) , when the learner can observe any chosen set of a few entries of this vector (corrupted by noise), under the assumption that \(f ({\bf X})\)  itself has a sparse WHT. In the literature, this problem has been referred to by a number of names, and we refer to it as the sparse WHT problem. There are yet again a number of computationally and statistically efficient algorithms for solving this problem, such as SPRIGHT [6]} and Sparse-FFT [7]}, among others.
