Reproducibility in learning
Reproducibility in learning
复制标题
学习的可重复性
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Jessica Sorrell
中科院分区：
文献类型：
--
作者：
R. Impagliazzo;Rex Lei;T. Pitassi;Jessica Sorrell
我们介绍了可再生算法的概念，在学习的上下文中。可重复的学习算法对样本的变化具有弹性-当运行来自相同底层分布的两个样本时，它很有可能返回完全相同的输出。我们开始首先解开定义，澄清随机性如何有助于平衡准确性和可重复性。我们发起了一个理论的可重复算法，再现性意味着理想的属性，如数据重用和有效的可测试性。尽管对可重复性的要求非常高，但对于统计和学习中的几个基本问题，仍然存在有效的可重复算法。首先，我们证明了任何统计查询算法都可以通过适度增加样本复杂性来实现可重复性，并且我们使用此来构建可重复的算法来找到近似的重量级人物和中位数。利用这些思想，我们给出了第一个通过可再生弱学习器和可再生boosting算法学习半空间的可再生算法。有趣的是，我们利用连接泡沫作为一个更高的维度随机舍入方案。最后，我们开始研究可重复算法的下限和固有的权衡，给出了几乎紧样本复杂性的上限和下限可重复与不可重复的SQ算法。
We introduce the notion of a reproducible algorithm in the context of learning. A reproducible learning algorithm is resilient to variations in its samples — with high probability, it returns the exact same output when run on two samples from the same underlying distribution. We begin by unpacking the definition, clarifying how randomness is instrumental in balancing accuracy and reproducibility. We initiate a theory of reproducible algorithms, showing how reproducibility implies desirable properties such as data reuse and efficient testability. Despite the exceedingly strong demand of reproducibility, there are efficient reproducible algorithms for several fundamental problems in statistics and learning. First, we show that any statistical query algorithm can be made reproducible with a modest increase in sample complexity, and we use this to construct reproducible algorithms for finding approximate heavy-hitters and medians. Using these ideas, we give the first reproducible algorithm for learning halfspaces via a reproducible weak learner and a reproducible boosting algorithm. Interestingly, we utilize a connection to foams as a higher-dimension randomized rounding scheme. Finally, we initiate the study of lower bounds and inherent tradeoffs for reproducible algorithms, giving nearly tight sample complexity upper and lower bounds for reproducible versus nonreproducible SQ algorithms.
影响因子：
--
作者：
G. Barthe;Rohit Chadha;Paul Krogmeier;A. Sistla;Mahesh Viswanathan
通讯作者：
G. Barthe;Rohit Chadha;Paul Krogmeier;A. Sistla;Mahesh Viswanathan
影响因子：
1.8
作者：
Albarghouthi, Aws;Hsu, Justin
通讯作者：
Hsu, Justin
通过 Boosting 实现高效、耐噪音和私密学习
DOI：
--
发表时间：
2020
期刊：
Proceedings of Machine Learning Research - COLT
影响因子：
--
作者：
Bun, Mark;Carmosino, Marco;Sorrell, Jessica
通讯作者：
Sorrell, Jessica