We study the monotonicity testing of functions $f \colon \{0,1\}^d \to \{0,1\}$ using sample-based algorithms, which are only allowed to observe the value of $f$ on points drawn independently from the uniform distribution. A classic result by Bshouty-Tamon shows that monotone functions can be learned with $\exp(\widetilde{O}(\min\{\frac{1}{\varepsilon}\sqrt{d},d\}))$ samples, and this bound extends to testing.
Prior to our work, the only lower bound for this problem was $\Omega(\sqrt{\exp(d)/\varepsilon})$ in the small $\varepsilon$ regime, when $\varepsilon = O(d^{-3/2})$, due to Goldreich et al. Thus, the sample complexity of monotonicity testing was open for $\varepsilon \gg d^{-3/2}$.
We resolve this question, obtaining a nearly tight lower bound of $\exp(\Omega(\min\{\frac{1}{\varepsilon}\sqrt{d},d\}))$ for all $\varepsilon$ at most a sufficiently small constant. In fact, we prove a more general result, showing that the sample complexity of $k$-monotonicity testing and learning for functions $f \colon \{0,1\}^d \to [r]$ is $\exp(\Omega(\min\{\frac{rk}{\varepsilon}\sqrt{d},d\}))$.
For testing with one-sided error, we show that the sample complexity is $\exp(\Theta(d))$. Beyond the hypercube, we prove nearly tight bounds (up to polylog factors of $d,k,r,1/\varepsilon$ in the exponent) of $\exp(\widetilde{\Theta}(\min\{\frac{rk}{\varepsilon}\sqrt{d},d\}))$ on the sample complexity of testing and learning measurable $k$-monotone functions $f \colon \mathbb{R}^d \to [r]$ under product distributions. Our upper bound improves upon the previous bound of $\exp(\widetilde{O}(\min\{\frac{k}{\varepsilon^2}\sqrt{d},d\}))$ by Harms-Yoshida for Boolean functions ($r=2$).
Blogger's Review: This paper provides new nearly optimal bounds for the sample complexity of monotonicity testing, particularly in the context of $k$-monotone functions. It demonstrates how finer analysis can improve existing theories in sample complexity research, bearing significant theoretical implications and practical applications. The effectiveness in high-dimensional cases presents broad prospects for application.