Resolvable Fourier Degree and Minimax Estimation on theBoolean Hypercube
Abstract
We study high-dimensional nonparametric regression on the Boolean hypercube {0,1}d, from a sample of size n, under a Fourier--Sobolev budget, i.e., a bound B on the total quadratic influence of the regression function. The central object is the resolvable Fourier degree D*(d,n), defined as the largest interaction order D such that the dimension of the degree-D Fourier--Walsh space does not exceed n. We prove that the minimax risk over Fourier--Sobolev ellipsoids is of order B/D*(d,n): estimation is possible up to the statistically visible interaction order, and the budget controls the residual mass carried by higher-order interactions. We then study monotone regression under the same budget. For monotone functions supported on a known set of s coordinates, with s of order log n, we obtain a matching minimax rate of order B/s. Finally, we consider an unknown-support model in which the function is monotone and depends on at most s coordinates; its minimax risk is governed by the intrinsic dimension s together with the logarithmic cost of selecting the active support.
Related
- When Is a Relevance Threshold Statistically Resolvable? Minimax Limits for Effect Classification
- Nonparametric hazard rate estimation with associated kernels and minimax bandwidth choice
- Minimax Rates for the Estimation of Eigenpairs of Weighted Laplace–Beltrami Operators on Manifolds
- Minimax rates for pointwise CATE estimation: the role of design smoothness
- A statistical theory for blind denoising: minimax estimation of the noise level from a single sample
BibTeX
@misc{biau2026resolvable,
title = {{Resolvable Fourier Degree and Minimax Estimation on theBoolean Hypercube}},
author = {Gérard Biau},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15595},
eprint = {2609.15595},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15595},
}
RIS
TY - UNPB
TI - Resolvable Fourier Degree and Minimax Estimation on theBoolean Hypercube
AU - G{é}rard Biau
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15595
UR - https://arxiv.org/abs/2609.15595
AB - We study high-dimensional nonparametric regression on the Boolean hypercube {0,1}^d, from a sample of size n, under a Fourier--Sobolev budget, i.e., a bound B on the total quadratic influence of the regression function. The central object is the resolvable Fourier degree D^*(d,n), defined as the largest interaction order D such that the dimension of the degree-D Fourier--Walsh space does not exceed n. We prove that the minimax risk over Fourier--Sobolev ellipsoids is of order B/D^*(d,n): estimation is possible up to the statistically visible interaction order, and the budget controls the residual mass carried by higher-order interactions. We then study monotone regression under the same budget. For monotone functions supported on a known set of s coordinates, with s of order log n, we obtain a matching minimax rate of order B/s. Finally, we consider an unknown-support model in which the function is monotone and depends on at most s coordinates; its minimax risk is governed by the intrinsic dimension s together with the logarithmic cost of selecting the active support.
ER -