Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
复制标题
稳定就是稳定：可复制性、隐私性和自适应泛化之间的联系
DOI：
10.1145/3564246.3585246
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Sorrell, Jessica
中科院分区：
文献类型：
--
作者：
Bun, Mark;Gaboardi, Marco;Hopkins, Max;Impagliazzo, Russell;Lei, Rex;Pitassi, Toniann;Sivakumar, Satchit;Sorrell, Jessica
可复制算法的概念是由Imagliazzo、Lei、Pitassi和Sorrell(STOC‘22)引入的，用于描述在其输入重采样下稳定的随机算法。更准确地说，当可复制算法的随机性固定并且在新的身份识别上运行时，它以很高的概率给出相同的输出。从相同的分配中抽取样本。使用可复制算法进行数据分析，可以确保分析结果大概率相同，即使分析是在新的数据集上执行的，从而有助于验证已发表的结果。在这项工作中，我们在可复制性和算法稳定性的标准概念之间建立了新的联系和分离。特别地，对于一大类统计问题，我们给出了完全泛化、近似差分隐私和可复制性之间的样本高效算法约简。相反，我们证明了任何这样的等价性都必须在计算上被打破：存在统计问题，这些问题在差异隐私下很容易，但如果不破解公钥密码学，这些问题就不能被复制地解决。此外，这些结果是紧凑的：我们的约简是统计最优的，并且我们证明了DP和可复制性之间的任何计算分离必然意味着单向函数的存在。我们的统计约简为稳定性概念之间的转换提供了一个新的算法框架，我们通过实例化来回答几个关于可复制性和隐私的公开问题。这包括针对各种PAC学习、分布估计和分布测试问题给出样本高效的可复制算法，在近似DP中对δ的算法放大，从项级到用户级隐私的转换，以及结构化分布下私人不可知性到可实现学习约简的存在。
The notion of replicable algorithms was introduced by Impagliazzo, Lei, Pitassi, and Sorrell (STOC’22) to describe randomized algorithms that are stable under the resampling of their inputs. More precisely, a replicable algorithm gives the same output with high probability when its randomness is fixed and it is run on a new i.i.d. sample drawn from the same distribution. Using replicable algorithms for data analysis can facilitate the verification of published results by ensuring that the results of an analysis will be the same with high probability, even when that analysis is performed on a new data set.In this work, we establish new connections and separations between replicability and standard notions of algorithmic stability. In particular, we give sample-efficient algorithmic reductions between perfect generalization, approximate differential privacy, and replicability for a broad class of statistical problems. Conversely, we show any such equivalence must break down computationally: there exist statistical problems that are easy under differential privacy, but that cannot be solved replicably without breaking public-key cryptography. Furthermore, these results are tight: our reductions are statistically optimal, and we show that any computational separation between DP and replicability must imply the existence of one-way functions.Our statistical reductions give a new algorithmic framework for translating between notions of stability, which we instantiate to answer several open questions in replicability and privacy. This includes giving sample-efficient replicable algorithms for various PAC learning, distribution estimation, and distribution testing problems, algorithmic amplification of δ in approximate DP, conversions from item-level to user-level privacy, and the existence of private agnostic-to-realizable learning reductions under structured distributions.
登录
查看更多内容
影响因子：
3.7
作者：
Fuhrer R;Hofmann S;Hild N;Vetsch JR;Herrmann IK;Grass RN;Stark WJ
通讯作者：
Stark WJ
自适应数据分析中的自然分析师
DOI：
--
发表时间：
2019
期刊：
Proceedings of ICML 2019
影响因子：
--
作者：
Zrnic, Tijana;Hardt, Moritz
通讯作者：
Hardt, Moritz
DOI：
--
发表时间：
2018-06
期刊：
ArXiv
影响因子：
--
作者：
Kobbi Nissim;Adam D. Smith;T. Steinke;Uri Stemmer;Jonathan Ullman
通讯作者：
Kobbi Nissim;Adam D. Smith;T. Steinke;Uri Stemmer;Jonathan Ullman
学习的可重复性
DOI：
--
发表时间：
2022
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
R. Impagliazzo;Rex Lei;T. Pitassi;Jessica Sorrell
通讯作者：
Jessica Sorrell
用于私人分类和在线预测的闭包属性
DOI：
--
发表时间：
2020
期刊：
Proceedings of Thirty Third Conference on Learning Theory
影响因子：
--
作者：
Alon, Noga;Beimel, Amos;Moran, Shay;and Stemmer, Uri
通讯作者：
and Stemmer, Uri