提出高效检测数据偏见的新方法，降低计算开销。
Sample Complexity of Bias Detection with Subsampled Point-to-Subspace Distances
- 将偏见检测转化为测度空间的点到子空间距离问题
- 在上确界范数下实现可高效子采样，理论保证正确性
- 适用于有调查数据不确定性的实际场景，适合监管合规应用
偏见估计的样本复杂度是任何偏见检测方法运行时间的下限。许多监管框架要求对所有子群体进行偏见测试，而子群体数量随受保护属性数量呈指数增长。除非接受双指数级运行时间，否则需确保单个子群体的偏见检测具有多项式复杂度。同时，参考数据可能来自调查，因此存在非平凡的不确定性。本文将偏见检测重新形式化为测度空间中的点到子空间问题，并证明在上确界范数下可高效子采样。特别地，我们的概率近似正确（PAC）结果已在知名实例上得到验证。
原文摘要 · Abstract (English)
Sample complexity of bias estimation is a lower bound on the runtime of any bias detection method. Many regulatory frameworks require the bias to be tested for all subgroups, whose number grows exponentially with the number of protected attributes. Unless one wishes to run a bias detection with a doubly-exponential run-time, one should like to have polynomial complexity of bias detection for a single subgroup. At the same time, the reference data may be based on surveys, and thus come with non-trivial uncertainty. Here, we reformulate bias detection as a point-to-subspace problem on the space of measures and show that, for supremum norm, it can be subsampled efficiently. In particular, our probabilistically approximately correct (PAC) results are corroborated by tests on well-known instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。