Influence as soft sparsity: Estimation of monotone functions on $\{0,1{\}}^d$

We study the problem of estimating a monotone function $f:\{0,1{\}}^d\to [0,1]$ from noisy observations at uniformly random vertices of the Boolean hypercube. As a measure of complexity for the target~$f$, we use the total $L^1$-influence $I(f)=\sum \mathrm{\_}{i=1}^d(\text{E}[f(X)\mid X\mathrm{\_}i=1]-\text{E}[f(X)\mid X\mathrm{\_}i=0])$, a classical quantity in Boolean analysis that is nonnegative for monotone functions and controls the effective dimensionality of the estimation problem: through a spectral concentration result in the spirit of Friedgut’s junta theorem, the Fourier spectrum of any $f$ with $I(f)⩽K$ concentrates on low-degree subsets of the influential coordinates. We establish minimax bounds over the class $\text{cF}\mathrm{\_}K=\{f:\{0,1{\}}^d\to [0,1],f\text{ monotone},I(f)⩽K\}$: $$c\frac{K^2}{(\log n{)}^{3\mathrm{/}2}}⩽\inf \mathrm{\_}\widehat{f}\sup \mathrm{\_}f\in \text{cF}\mathrm{\_}K\text{E}[\mathrm{\parallel }\widehat{f}-f\mathrm{\parallel }\mathrm{\_}{2}^2]⩽C\frac{K}{\sqrt{\log n}},$$ where $n$ is the sample size. The upper bound holds for all $K⩾1$ and is uniform in the ambient dimension~$d$ (under the mild condition $\log d⩽n^{1-\epsilon }$). It is achieved by a Fourier thresholding estimator that adapts to the unknown~$K$. The lower bound relies on a Varshamov–Gilbert packing on the middle layer of the hypercube combined with Fano’s inequality.