Tight $L_{\infty }$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials

Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1

Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing th…