Machine learning (ML) models have become increasingly commonplace in learning pseudo-Boolean functions \(f(\cdot )\) , which map a \(d\) -dimensional binary vector \(x\in \lbrace \pm 1\rbrace ^d\)  to a real number \(f(x)\in \mathbb {R}\) . In biology, ML models are being used to infer the functional properties of macro-molecules (e.g., proteins) from a small set of mutations [1]}, [2]}. In physics, ML models are being used to infer the thermodynamic properties of combinatorial systems defined over a set of binary (Ising) state variables [3]}, [4]}. These highly nonlinear and complex ML models are trained using modern techniques in continuous optimization, yet they inherit the elegant properties of pseudo-Boolean functions over the discrete binary hypercube \(\lbrace \pm 1\rbrace ^d\) . In particular, it is known that the spectral representation of a pseudo-Boolean function is defined as the Walsh-Hadamard transform (WHT) of the resulting vector of combinatorial function evaluations, that is, \(\mathbf {H}f({\bf X})\) , where \(\mathbf {H}\)  is a \(2^d\times 2^d\)  Walsh matrix and the function evaluation vector \({f}({\bf X})=[f(x) : x \in \mathbf {X}]^T\)  is sorted in the lexicographic ordering of all the length-\(d\)  binary strings in \(\mathbf {X}\) . The WHT enables writing the pseudo-Boolean function \(f(x)\)  as a multi-linear polynomial \(f(x) = \sum _{\mathcal {S}\subseteq [d]}\alpha _{\mathcal {S}}\prod _{i\in \mathcal {S}}x_i \) , where \([d]=\lbrace 1,2,\dots ,d\rbrace \)  and \(\alpha _{\mathcal {S}}\in \mathbb {R}\)  is the WHT coefficient corresponding to the monomial \(\prod _{i\in \mathcal {S}}x_i\)  [5]}.We use these terms interchangeably for pseudo-Boolean functions: spectral, Fourier, and Walsh-Hadamard.
