我们研究了函数 $f \colon \{0,1\}^d \to \{0,1\}$ 的单调性测试，使用样本基础算法，仅允许观察从均匀分布独立抽取的点上的值。Bshouty-Tamon 的经典结果证明，单调函数的学习样本复杂度为 $\exp(\widetilde{O}(\min\{\frac{1}{\varepsilon}\sqrt{d},d\}))$，且这一界限同样适用于测试。
在我们之前的研究中，唯一的下界为 $\Omega(\sqrt{\exp(d)/\varepsilon})$，适用于小的 $\varepsilon$ 参数范围，即当 $\varepsilon = O(d^{-3/2})$ 时，由 Goldreich 等人提出（Combinatorica 2000）。因此，当 $\varepsilon \gg d^{-3/2}$ 时，单调性测试的样本复杂度仍未解决。
我们对此问题进行了研究，得到了一个近乎紧的下界：对于所有 $\varepsilon$ 至多为一个足够小的常数，样本复杂度为 $\exp(\Omega(\min\{\frac{1}{\varepsilon}\sqrt{d},d\}))$。实际上，我们证明了一个更一般的结果，显示对于函数 $f \colon \{0,1\}^d \to [r]$ 的 $k$-单调性测试与学习，样本复杂度为 $\exp(\Omega(\min\{\frac{rk}{\varepsilon}\sqrt{d},d\}))$。
对于单侧错误的测试，我们显示样本复杂度为 $\exp(\Theta(d))$。在超立方体之外，我们证明了 $\exp(\widetilde{\Theta}(\min\{\frac{rk}{\varepsilon}\sqrt{d},d\}))$ 的近乎紧界限（在 $d,k,r,1/\varepsilon$ 的多对数因子上）用于测试和学习可测的 $k$-单调函数 $f \colon \mathbb{R}^d \to [r]$，在乘积分布下。我们的上界改善了 Harms-Yoshida（ICALP 2022）为布尔函数（$r=2$）提供的 $\exp(\widetilde{O}(\min\{\frac{k}{\varepsilon^2}\sqrt{d},d\}))$ 的先前界限。
博主点评： 本文为单调性测试的样本复杂度提供了新的近似最优界限，特别是在 $k$-单调函数的上下文中，展示了在样本复杂度的研究中如何通过更精细的分析来改进现有理论，具有重要的理论意义和实际应用潜力。尤其是对于大维度情况下的有效性，具有广泛的应用前景。