高维统计中的可复制性
我们提供了学习大间隔半空间问题的高效可复制算法,改进了 Impagliazzo 等人提供的算法。我们首次设计了这个任务的无维度依赖的可复制算法,其在多项式时间内运行,是合适的,并且在所有相关参数方面与 Impagliazzo 等人取得的结果相比,样本复杂度有明显提高。此外,我们的第一个算法在精度参数 ε 上具有最优的样本复杂度。我们还设计了一种基于 SGD 的可复制算法,在某些参数区间内,比我们第一个算法具有更好的样本和时间复杂度。最后,我们设计了一种改进的算法,其在样本复杂度上优于我们以前的三种算法,并且运行时间呈指数关系于 1/τ^2。
Feb, 2024
我们研究算法可复现性的计算方面,这是由 Impagliazzo、Lei、Pitassi 和 Sorrell [2022] 引入的稳定性概念。通过一系列与可学习性的统计联系的最新研究,如在线学习、私有学习和 SQ 学习,我们旨在更好地理解可复现性与这些学习范式之间的计算联系。我们的第一个结果表明,存在一个概念类,其 PAC 学习可复现且高效,但在标准的密码学假设下,不存在这个类的高效在线学习者。随后,我们设计了一个高效的可复现学习算法,用于在边际分布与均匀分布之间差异很大的情况下 PAC 学习奇偶函数,进展了 Impagliazzo 等人 [2022] 提出的问题。为了获得这个结果,我们设计了一个可复现的提升框架,受 Blanc、Lange、Malik 和 Tan [2023] 的启发,以黑盒方式将均匀边际分布上的高效可复现 PAC 学习器转化为任意边际分布上的可复现 PAC 学习器,其样本和时间复杂度依赖于分布复杂度的某个度量。最后,我们证明任何纯 DP 学习器都可以在准确性、置信度参数的多项式时间内转化为一个可复现学习器,并且与底层假设类的表示维度成指数关系。
May, 2024
探讨强化学习领域中复制性的数学研究,提出了基于生成模型下的可复制性 RL 算法,其中包括一个有效的 $ ho$-replicable 算法和一个可计算的近似可复制的算法。
May, 2023
该论文介绍了一种通过使用分布模型以及多项式时间算法在高维数据中实现鲁棒性估计的方法,并且提出了优化方法,以使算法能够适应更多的数据异常值,实现更高效的鲁棒性估计。
Mar, 2017
该研究提出了一种新的方法来度量高通量实验中的结果再现性,其中使用可重复性鉴定推断,通过一个量化的非标量的可重复性曲线基于一个混合模型,计算可重复性得分(IDR),并证明了其在 ChIP-seq 实验中的有效性。
Oct, 2011
该研究旨在解决高维分布学习中的拜占庭敌人问题,提出了面向单高斯、超立方体上的乘积分布及其混合分布和球形高斯的分布学习的算法,并为高维数据的拜占庭敌人问题提供了一种通用的检测与纠正方案。
Apr, 2016
本研究探讨了可复制的学习算法,在考虑可行的可复制性观念和证明可复制性的基础上,设计了一些用于特定学习问题的算法,其列表和证明的复杂度是最优的,并提出了相应的不可能性结果。
Apr, 2023