May, 2024
可复现学习的计算景观
On the Computational Landscape of Replicable Learning
Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas, Felix Zhou
TL;DR我们研究算法可复现性的计算方面，这是由 Impagliazzo、Lei、Pitassi 和 Sorrell [2022] 引入的稳定性概念。通过一系列与可学习性的统计联系的最新研究，如在线学习、私有学习和 SQ 学习，我们旨在更好地理解可复现性与这些学习范式之间的计算联系。我们的第一个结果表明，存在一个概念类，其 PAC 学习可复现且高效，但在标准的密码学假设下，不存在这个类的高效在线学习者。随后，我们设计了一个高效的可复现学习算法，用于在边际分布与均匀分布之间差异很大的情况下 PAC 学习奇偶函数，进展了 Impagliazzo 等人 [2022] 提出的问题。为了获得这个结果，我们设计了一个可复现的提升框架，受 Blanc、Lange、Malik 和 Tan [2023] 的启发，以黑盒方式将均匀边际分布上的高效可复现 PAC 学习器转化为任意边际分布上的可复现 PAC 学习器，其样本和时间复杂度依赖于分布复杂度的某个度量。最后，我们证明任何纯 DP 学习器都可以在准确性、置信度参数的多项式时间内转化为一个可复现学习器，并且与底层假设类的表示维度成指数关系。