隱私計算在私密重複與元選擇中的權衡

私密重複演算法

私密重複演算法是一種特殊的演算法，它可以把一個成功機率固定的私密演算法，提升到一個成功機率很高的演算法。這些演算法和私密元選擇演算法有很大的關係，後者是用來與許多私密演算法中最好的進行競爭的；還有私密超參數調整演算法，這些演算法則是與私密學習演算法中最好的超參數設定進行競爭。

隱私成本與計算成本

目前已經有的演算法在這些任務中，通常會付出很大的隱私成本或計算成本。我們的研究顯示，對於這類問題有很強的下限，特別是對於任何能保持隱私成本在固定範圍內的演算法，它的失敗機率只能隨著計算成本的增加而多項式下降。這與非私密的情況形成了鮮明的對比，因為在非私密的情況下，失敗機率會隨著計算成本的增加而指數下降。

計算與隱私的平衡

透過仔細結合現有的元選擇演算法，我們證明了計算和隱私之間的權衡，這些權衡幾乎達到了我們的下限。