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

arXiv: https://arxiv.org/abs/2606.17319 · HTML: https://mlsanity.com/paper/2606.17319/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 15 Jun 2026.

## Builds on (most cited first, 8 of 8)

- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Combinatorial Black-Box Optimization with Expert Advice](https://mlsanity.com/paper/2006.03963/) (2020)
- [Learning low-degree functions from a logarithmic number of random queries](https://mlsanity.com/paper/2109.10162/) (2021)
- [The Restricted Isometry Property of Subsampled Fourier Matrices](https://mlsanity.com/paper/1507.01768/) (2015)
- [Fourier Representations for Black-Box Optimization over Categorical Variables](https://mlsanity.com/paper/2202.03712/) (2022)
- [Low-degree learning and the metric entropy of polynomials](https://mlsanity.com/paper/2203.09659/) (2022)

## Abstract (arXiv)

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.