在隐私保护计算中，提升成功率需权衡计算开销与隐私成本。
Privacy-Computation trade-offs in Private Repetition and Metaselection
- 通过组合现有元选择算法，实现计算与隐私的最优平衡。
- 隐私成本不变时，失败概率仅随计算开销多项式下降。
- 适用于需要严格隐私保障的超参数调优场景。
私有重复算法将一个成功概率为常数的差分隐私算法，提升为高成功率算法。这类算法与私有元选择、私有超参数调优密切相关。现有方法在隐私或计算成本上存在巨大开销。本文证明了强下界：若隐私开销保持常数倍，则失败概率仅随计算开销多项式级下降。这与非私有场景中指数下降形成鲜明对比。通过巧妙组合已有元选择算法，我们构建的方案近乎逼近该理论下界。
原文摘要 · Abstract (English)
A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. These algorithms are closely related to private metaselection algorithms that compete with the best of many private algorithms, and private hyperparameter tuning algorithms that compete with the best hyperparameter settings for a private learning algorithm. Existing algorithms for these tasks pay either a large overhead in privacy cost, or a large overhead in computational cost. In this work, we show strong lower bounds for problems of this kind, showing in particular that for any algorithm that preserves the privacy cost up to a constant factor, the failure probability can only fall polynomially in the computational overhead. This is in stark contrast with the non-private setting, where the failure probability falls exponentially in the computational overhead. By carefully combining existing algorithms for metaselection, we prove computation-privacy tradeoffs that nearly match our lower bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。