Adaptive Monotonicity Testing in Sublinear Time

Housen Li

doi:10.1109/TIT.2025.3646887

2026-02-01

PRE

Housen Li *

Liu Zhi

Axel Munk

DOI：10.1109/TIT.2025.3646887

原文链接

原文求助

摘要

En 中文

现代大规模数据分析日益面临实现计算效率与统计精度双重挑战，因为经典的统计高效方法往往在计算效率方面表现不足。在回归函数单调性检验的背景下，我们提出FOMT（快速最优单调性检验），一种旨在满足这两方面需求的新型方法。FOMT采用一组稀疏的局部检验，通过随机生成来检测回归函数定义域内散布的单调性违反情况。这种稀疏性实现了显著的计算效率，在大多数情况下达到次线性运行时间，最坏情况下为拟线性运行时间（即最多乘以对数因子）。相比之下，现有的统计最优检验通常需要至少二次方运行时间。FOMT的统计精度通过精确校准这些局部检验及其有效组合来实现，确保对违反情况的敏感度并控制假阳性。更具体地说，我们证明了FOMT在Hölder光滑度阶数在(0,2]的函数类上以最小最大最优速率区分零假设与备择假设。此外，当光滑度未知时，我们引入基于改进Lepskii原理的FOMT自适应版本，该版本达到统计最优性，同时保持与已知内在光滑度时相同的计算复杂度。大量模拟证实了FOMT及其自适应变体的竞争力和有效性。

Keyword:

Testing

Runtime

Computational efficiency

Adaptation models

Computational complexity

Computational modeling

Splines (mathematics)

Estimation

Bandwidth

Stress

Fast computation