提出首个针对采样器的实例相关测试方法，可高效验证自然数域上的采样器。
Instance Dependent Testing of Samplers using Interval Conditioning
- 基于区间条件框架设计距离估计算法，实现对未知分布的高效检验。
- 在自然数域上实现最高1000倍的速度提升，显著优于现有方法。
- 适用于天体物理、金融等需无限域采样的场景，实用价值高。
采样算法在概率人工智能中至关重要，但验证采样程序是否真正从目标分布采样仍是一个难题。近年来虽有Barbarik、Teq、Flash、CubeProbe等可证明正确的测试方法被提出，但均侧重最坏情况效率，无法支持无限域上的采样器验证——这在天体物理、金融、网络安全等领域频繁出现。本文首次设计了具有实例依赖效率的采样器测试方法，可对自然数域上的采样器进行验证。测试基于新颖的区间条件框架下的分布距离估计算法，核心技术在于建立连续分布质量估计的新联系。实验表明，该方法相比当前最优测试工具最高提速达1000倍，具有显著实际优势。
原文摘要 · Abstract (English)
Sampling algorithms play a pivotal role in probabilistic AI. However, verifying if a sampler program indeed samples from the claimed distribution is a notoriously hard problem. Provably correct testers like Barbarik, Teq, Flash, CubeProbe for testing of different kinds of samplers were proposed only in the last few years. All these testers focus on the worst-case efficiency, and do not support verification of samplers over infinite domains, a case occurring frequently in Astronomy, Finance, Network Security, etc. In this work, we design the first tester of samplers with instance-dependent efficiency, allowing us to test samplers over natural numbers. Our tests are developed via a novel distance estimation algorithm between an unknown and a known probability distribution using an interval conditioning framework. The core technical contribution is a new connection with probability mass estimation of a continuous distribution. The practical gains are also substantial: our experiments establish up to 1000x speedup over state-of-the-art testers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。