Tight L_∞ Sample Complexity for Low-Degree and Sparse Boolean Polynomials

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 the surrogate yields good solutions for the underlying objective, we require uniform L_∞-error guarantees rather than the usual L2-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most d on n variables, the sample complexity scales as nd+1. Second, for s-sparse Fourier-Walsh polynomials with s ≤ n, it scales as ns2. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as nd and ns, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the L2-norm do not naturally extend to the L_∞-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the L_∞-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.