让机器学习结果可公开验证，提升可信度与鲁棒性
Publicly-Verifiable Certificates for Statistical Algorithms
- 提出非交互式验证证书，实现对学习结果的公开可验证
- 针对自适应统计查询算法，样本复杂度仅随log k增长
- 适合需要高可信度验证的机器学习应用，如医疗或金融
受Goldwasser等人在ITCS'21中提出的交互式学习证明框架启发，我们首次研究非交互式学习证明。本文定义并研究了一种新概念：公开可验证的统计有效性证书（pvCSV），允许在分布鲁棒条件下公开验证学习算法结果的有效性。在pvCSV中，学习者发布假设h及其对应证书π；任何持有特定分布的用户均可高效验证该假设是否在自身分布下有效。我们在自适应统计查询（SQ）算法背景下构建了pvCSV。对于执行k个自适应查询的算法，其证书样本复杂度为O(log k)，而最优学习算法的复杂度为~O(√k)。此外，我们系统研究了SQ模型中的学习证明体系，揭示了该模型的优势与局限。
原文摘要 · Abstract (English)
Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning [ITCS'21], we initiate the study of non-interactive proofs of learning. We define and study a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs), which allow for public, distributionally-robust certification that the result of a learning algorithm is valid. In a pvCSV, a learner publishes a hypothesis $h$ and corresponding certificate $π$; then, any user, who holds a user-specific distribution, can read the pair $(h,π)$ and determine efficiently whether the hypothesis is valid according to the user-specific distribution. We construct pvCSVs in the context of Adaptive Statistical Query (SQ) Algorithms. To certify SQ algorithms that makes $k$ adaptive queries, we construct pvCSVs where the sample complexity scales with $O(\log k)$, whereas the sample complexity of the best learning algorithms scale with $\tilde{O}(\sqrt{k})$. More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。