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\_{i=1}^d(\E[f(X)\mid X\_i=1]-\E[f(X)\mid X\_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)\leqslant K$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.19648
curl -X POST /api/v1/records/arxiv/2605.19648/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.19648/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'