Problem statement. We consider the problem of learning structured pseudo-Boolean functions on the binary hypercube \(\lbrace  \pm 1 \rbrace ^d\) . In the finite sample setting, we assume that the learner has access to a dataset \(D_n\)  comprised of \(n\)  labeled data points \((x^i,y^i)_{i=1}^n\)  where \(x^i \in \lbrace  \pm 1 \rbrace ^d\)  are drawn from an input distribution \(\mathcal {D}\)  and the real-valued output \(y_i \in \mathbb {R}\)  is a noisy realization of an unknown pseudo-Boolean function of the input We use the subscript \(x_i\)  to refer to the \(i^\text{th}\)  digit in the binary string \(x=(x_1,x_2,\cdots ,x_d)\) .. Namely we assume that there is a rich nonlinear function class \(\mathcal {F} = \lbrace  f_{ : \mathbb {R}^m \rbrace  parameterized by , where f_{ : \lbrace  \pm 1 \rbrace ^d \rightarrow \mathbb {R}. The labels are generated as y^i = f_{*}(x^i) + Z^i where Z^i is the noise in the measurement for input x^i, assumed to be independent and normally distributed \sim \mathcal {N} (0,\sigma ^2) \footnote {In fact, our results only require the noise to be independent subgaussian random variables with variance parameter \sigma ^2, but for ease of exposition, we impose the Gaussian noise condition.}. The objective of the learner is to learn *.}}\)Multi-linear polynomial representation. Any pseudo-Boolean function \(f(\cdot )\)  can be uniquely represented as a multi-linear polynomial, \(f(x) = \sum _{z \in \lbrace  \pm 1 \rbrace ^d}\alpha _{z} \prod _{i : z_i = +1} x_i \) , where the scalar \(\alpha _{z} \in \mathbb {R}\)  is the coefficient corresponding to the monomial \(\prod _{i : z_i = +1} x_i\) , with order \(\sum _{i=1}^d \mathbb {1} (z_i = +1)\)  [1]}.
The problem of learning a pseudo-Boolean function \(f (\cdot )\)  is equivalent to finding the \(2^d\)  unknown coefficients \(\alpha _z\) .
In particular, the evaluations of \(f\)  on all vertices of the binary hypercube \(\lbrace  \pm 1 \rbrace ^{2^d}\)  results in a linear system of equations over the \(\alpha _{z}\)  variables,
\(\begin{bmatrix} f(x) : x \in \lbrace  \pm 1 \rbrace ^d \end{bmatrix}^T = \mathbf {H}\begin{bmatrix} \alpha _z : z \in \lbrace  \pm 1 \rbrace ^d \end{bmatrix}^T,\) 
