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

We study monotonicity testing of functions f colon 0,1d → 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(widetildeO(minfrac1varepsilon√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(√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(minfrac1varepsilon√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,1d → [r] is exp(Omega(minfracrkvarepsilon√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(widetildeTheta(minfracrkvarepsilon√d,d)) on the sample complexity of testing and learning measurable k-monotone functions f colon ℝd → [r] under product distributions. Our upper bound improves upon the previous bound of exp(widetildeO(minfrackvarepsilon2√d,d)) by Harms-Yoshida (ICALP 2022) for Boolean functions (r=2).