We show how to obtain improved active learning methods in the agnostic (adversarial noise) setting by combining marginal leverage score sampling with non-independent sampling strategies that promote spatial coverage. In particular, we propose an easily implemented method based on the pivotal sampling algorithm, which we test on problems motivated by learning-based methods for parametric PDEs and uncertainty quantification. In comparison to independent sampling, our method reduces the number of samples needed to reach a given target accuracy by up to $50\%$. We support our findings with two theoretical results. First, we show that any non-independent leverage score sampling method that obeys a weak one-sided $\ell_{\infty}$ independence condition (which includes pivotal sampling) can actively learn $d$ dimensional linear functions with $O(d\log d)$ samples, matching independent sampling. This result extends recent work on matrix Chernoff bounds under $\ell_{\infty}$ independence, and may be of interest for analyzing other sampling strategies beyond pivotal sampling. Second, we show that, for the important case of polynomial regression, our pivotal method obtains an improved bound of $O(d)$ samples.

我们展示了如何通过将边际杠杆得分抽样与促进空间覆盖的非独立抽样策略相结合，从而在不知情（对抗性噪声）设置中获得改进的主动学习方法。我们提出了一个简单实现的基于关键抽样算法的方法，并在基于学习的参数化PDEs和不确定性量化的问题上进行了测试。与独立抽样相比，我们的方法将达到给定目标精度所需的样本数量减少了最多50％。我们用两个理论结果支持了我们的发现。首先，我们证明了任何满足弱单向的离散l∞独立条件（其中包括关键抽样）的非独立杠杆得分抽样方法可以以O(dlogd)的样本主动学习d维线性函数，与独立抽样相匹配。这个结果扩展了最近关于l∞独立性下矩阵Chernoff界的工作，并可能对分析关键抽样之外的其他抽样策略感兴趣。其次，我们证明了对于多项式回归的重要案例，我们的关键方法获得了O(d)的改进界。

通过相关杠杆得分抽样改进主动学习