在经典的点位置问题中，给定一个任意数据集 $X \subset \mathbb{R}^d$，包含 $n$ 个点，并可以查询一个未知的半空间 $f : \mathbb{R}^d \to \{0,1\}$，目标是学习 $X$ 中每个点的标签。该问题的研究非常深入，Hopkins-Kane-Lovett-Mahajan 提出的几乎最优查询算法为 $\widetilde{O}(d \log n)$，但其算法允许查询 $X$ 之外的任意点（点合成）。实际上，若没有这种能力，Dasgupta 在 NeurIPS 2004 中证明了存在一个 $\Omega(n)$ 的查询下界。
本研究的目标是设计高效算法，在没有点合成的情况下学习半空间。为规避 $\Omega(n)$ 下界，我们考虑从大小为 $D$ 的集合中获取法向量的半空间，并展示了 $\Theta(D + \log n)$ 的紧界限。作为推论，我们获得了一个最佳的 $O(d + \log n)$ 查询确定性学习器，用于轴对齐半空间，填补了之前 $O(d \log n)$ 与 $\Omega(d + \log n)$ 之间的差距。
实际上，我们的算法解决了一个更一般的问题：学习一个在至少 $D$ 个给定顺序下单调的布尔函数 $f$，该函数的元素数量为 $n$。我们的技术洞见在于利用这些顺序中的结构，进行并行二分搜索，而不是逐个顺序处理。
此外，我们使用精确学习算法来获得几乎最优的 PAC 学习算法。我们证明，$O(\min(D + \log(1/\varepsilon), 1/\varepsilon) \cdot \log D)$ 次查询足以在误差 $\varepsilon$ 的情况下学习 $f$，即使在 $f$ 可以在 $c\varepsilon$ 的点上遭到对抗性破坏的情况下，$c$ 为足够小的常数。这一界限在 $\log D$ 因子上是最优的，包括在可实现的设置中。
博主点评： 本文提出的算法在没有合成数据的情况下，实现了对半空间的高效学习，填补了理论与实践之间的差距。通过并行化的二分搜索方法，作者克服了传统方法的局限，展现了强大的适应性与广泛的应用潜力。