Another issue is specific to algorithms for solving the sparse WHT problem: some of these approaches require observing \(f(\cdot )\)  at any chosen input [1]}, [2]}. In many practical applications, where data is prohibitively expensive to collect, one is often forced to work with a handful of random samples. For example, in the case of proteins, a common approach to measure biological functions is through a procedure called random mutagenesis which allows only a random sampling of the combinatorial sequence space [3]}. This constraint renders several algorithms for the sparse WHT problem ill-suited for learning, even though they admit near-optimal computational and sample complexity guarantees.
