We study 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 (J. ACM 1996) proved that monotone functions can be learned with $\exp(\widetilde{ O}(\min\{ \frac{ 1}{ \varepsilon}\sqrt{ d},d\}))$ samples and it is not hard to show that 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$ parameter regime, when $\varepsilon = O(d^{ -3/2})$, due to Goldreich-Goldwasser-Lehman-Ron-Samorodnitsky (Combinatorica 2000). Thus, the sample complexity of monotonicity testing was wide 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 much 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 (ICALP 2022) for Boolean functions ($r=2$).

Categories: cs.DS

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions