{"id":"arxiv/2606.17319","url":"https://arxiv.org/abs/2606.17319","tags":["stat.ML","cs.LG","math.CO","math.ST"],"score":0,"title":"Tight $L_\\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials","domain":"stat.ML","source":"arxiv","authors":["Jasper van Doornmalen","Mathieu Molina","Victor Verdugo","José Verschae"],"reviews":0,"subject":"stat.ML","summary":"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_\\infty$-error guarantees rather than the usual $L_2$-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 $n^{d+1}$. Second, for $s$-sparse…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-06-15","reactions":{}}