Theory of Computing
-------------------
Title     : Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
Authors   : Hadley Black
Volume    : 22
Number    : 8
Pages     : 1-33
URL       : https://theoryofcomputing.org/articles/v022a008

Abstract
--------

We study monotonicity testing of functions  f:{0,1}^d --> {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 error at most \eps \in (0,1) using
\exp(\widetilde{O}(\min\{\frac{1}{\eps}\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)/\eps})  in the small $\eps$ parameter regime,
when  \eps = O(d^{-3/2}), due to Goldreich--Goldwasser--Lehman--Ron--
Samorodnitsky (Combinatorica 2000). Thus, the sample complexity of 
monotonicity testing was wide open when  \eps  is much greater than
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
 \eps  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:{0,1}^d --> [r]
is  \exp(\Omega(\min\{\frac{rk}{\eps}\sqrt{d},d})). For testing with
one-sided error we show that the sample complexity is \exp(\Omega(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}{\eps}\sqrt{d},d\}))$
on the sample complexity of testing and learning measurable
k-monotone functions  f:\mathbb{R}^d --> [r]  under product
distributions. Our upper bound improves upon the previous bound of
\exp(\widetilde{O}(\min\{\frac{k}{\eps^2}\sqrt{d},d\}))$ by
Harms--Yoshida (ICALP'22) for Boolean functions (r=2).

-----------------

A conference version of this paper appeared in the Proceedings of the
28th Internat. Conference on Randomization and Computation (RANDOM'24).