English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 classicresult by Bshouty-Tamon (J. ACM 1996) proved that monotone functions can belearned with $\exp(O(\min\{\frac{1}{\varepsilon}\sqrt{d},d\}))$ samples and itis not hard to show that this bound extends to testing. Prior to our work theonly lower bound for this problem was $\Omega(\sqrt{\exp(d)/\varepsilon})$ inthe small $\varepsilon$ parameter regime, when $\varepsilon = O(d^{-3/2})$, dueto 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 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 generalresult, showing that the sample complexity of $k$-monotonicity testing andlearning for functions $f \colon \{0,1\}^d \to [r]$ is$\exp(\Theta(\min\{\frac{rk}{\varepsilon}\sqrt{d},d\}))$. For testing withone-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 thesample complexity of testing and learning measurable $k$-monotone functions $f\colon \mathbb{R}^d \to [r]$ under product distributions. Our upper boundimproves upon the previous bound of$\exp(\widetilde{O}(\min\{\frac{k}{\varepsilon^2}\sqrt{d},d\}))$ byHarms-Yoshida (ICALP 2022) for Boolean functions ($r=2$).

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