We propose the \emph{Target Charging Technique} (TCT), a unified privacy analysis framework for interactive settings where a sensitive dataset is accessed multiple times using differentially private algorithms. Unlike traditional composition, where privacy guarantees deteriorate quickly with the number of accesses, TCT allows computations that don't hit a specified \emph{target}, often the vast majority, to be essentially free (while incurring instead a small overhead on those that do hit their targets). TCT generalizes tools such as the sparse vector technique and top-$k$ selection from private candidates and extends their remarkable privacy enhancement benefits from noisy Lipschitz functions to general private algorithms.
翻译:我们提出了“目标充电技术”(TCT),这是一种统一的隐私分析框架,用于交互式设置中多次访问敏感数据集的差分隐私算法。与传统组合不同,其中隐私保证随访问次数迅速恶化,TCT允许不命中指定的“目标”(通常是绝大部分)的计算基本上是免费的(而在命中其目标的计算中则需要承担小的额外成本)。 TCT泛化了从私有候选人选择稀疏向量技术和top-k选择等工具,并将它们显着的隐私增强优势从有噪Lipschitz功能扩展到了一般的私有算法。