详细内容或原文请订阅后点击阅览
私人重复和元选择中的隐私计算权衡
私有重复算法将成功概率为恒定的差分私有算法作为输入，并将其提升为成功概率较高的算法。这些算法与与众多私有算法中的最佳算法竞争的私有元选择算法以及与私有学习算法的最佳超参数设置竞争的私有超参数调整算法密切相关。这些任务的现有算法要么在隐私成本上付出了巨大的开销，要么在计算成本上付出了巨大的开销。在这项工作中，我们展示了强下限......
来源:Apple机器学习研究隐私重复算法将成功概率为常数的差分隐私算法作为输入，并将其提升为成功概率较高的算法。这些算法与隐私元选择算法密切相关，这些算法与众多隐私算法中的最佳算法竞争，而隐私超参数调整算法与隐私学习算法的最佳超参数设置竞争。现有的用于这些任务的算法要么付出巨大的隐私成本，要么付出巨大的计算成本。在这项工作中，我们展示了此类问题的强下限，特别是表明，对于任何将隐私成本保持在常数因子的算法，失败概率只能在计算开销中呈多项式下降。这与非隐私设置形成鲜明对比，在非隐私设置中，失败概率在计算开销中呈指数下降。通过仔细结合现有的元选择算法，我们证明了计算隐私权衡几乎与我们的下限相匹配。