We provide a new algorithmic framework for differentially private estimation
of general functions that adapts to the hardness of the underlying dataset. We
build upon previous work that gives a paradigm for selecting an output through
the exponential mechanism based upon closeness of the inverse to the underlying
dataset, termed the inverse sensitivity mechanism. Our framework will slightly
modify the closeness metric and instead give a simple and efficient application
of the sparse vector technique. While the inverse sensitivity mechanism was
shown to be instance optimal, it was only with respect to a class of unbiased
mechanisms such that the most likely outcome matches the underlying data. We
break this assumption in order to more naturally navigate the bias-variance
tradeoff, which will also critically allow for extending our method to
unbounded data. In consideration of this tradeoff, we provide strong intuition
and empirical validation that our technique will be particularly effective when
the distances to the underlying dataset are asymmetric. This asymmetry is
inherent to a range of important problems including fundamental statistics such
as variance, as well as commonly used machine learning performance metrics for
both classification and regression tasks. We efficiently instantiate our method
in $O(n)$ time for these problems and empirically show that our techniques will
give substantially improved differentially private estimations.

我们提供了一个新的算法框架，用于差分隐私估计一般函数，该框架根据底层数据集的难度进行动态调整。我们构建在先前的工作基础上，通过接近逆过程的数据集，即称为逆敏感性机制的指数机制选择一个输出的范例。我们的框架稍微修改了接近度度量，并提供了稀疏向量技术的简单有效应用。我们打破这个假设，以更自然地处理偏差 - 方差平衡，这也关键地允许我们将方法扩展到无界数据。考虑到这种平衡，我们提供了强有力的直觉和实证验证，表明我们的技术在与底层数据集的距离是非对称的情况下尤为有效。我们以 $O (n)$ 的时间高效实现了这些问题，并通过实验证明我们的技术能够显著改进差分隐私估计。

差分隐私中的实例特定异质敏感度

Instance-Specific Asymmetric Sensitivity in Differential Privacy

The Alternating Direction Method of Multipliers (ADMM) and its distributed
version have been widely used in machine learning. In the iterations of ADMM,
model updates using local private data and model exchanges among agents impose
critical privacy concerns. Despite some pioneering works to relieve such
concerns, differentially private ADMM still confronts many research challenges.
For example, the guarantee of differential privacy (DP) relies on the premise
that the optimality of each local problem can be perfectly attained in each
ADMM iteration, which may never happen in practice. The model trained by DP
ADMM may have low prediction accuracy. In this paper, we address these concerns
by proposing a novel (Improved) Plausible differentially Private ADMM
algorithm, called PP-ADMM and IPP-ADMM. In PP-ADMM, each agent approximately
solves a perturbed optimization problem that is formulated from its local
private data in an iteration, and then perturbs the approximate solution with
Gaussian noise to provide the DP guarantee. To further improve the model
accuracy and convergence, an improved version IPP-ADMM adopts sparse vector
technique (SVT) to determine if an agent should update its neighbors with the
current perturbed solution. The agent calculates the difference of the current
solution from that in the last iteration, and if the difference is larger than
a threshold, it passes the solution to neighbors; or otherwise the solution
will be discarded. Moreover, we propose to track the total privacy loss under
the zero-concentrated DP (zCDP) and provide a generalization performance
analysis. Experiments on real-world datasets demonstrate that under the same
privacy guarantee, the proposed algorithms are superior to the state of the art
in terms of model accuracy and convergence rate.

本文提出了 PP-ADMM 和 IPP-ADMM，采用扰动优化和稀疏向量技术，在保护本地数据隐私的同时，提高了模型的准确性和收敛速度，并跟踪零集中的差分隐私度量，实验证明在相同的隐私保证下，该算法优于现有算法。

基于 ADMM 的可信差分隐私分布式机器学习

Towards Plausible Differentially Private ADMM Based Distributed Machine  Learning

A pervasive task in the differential privacy literature is to select the $k$
items of "highest quality" out of a set of $d$ items, where the quality of each
item depends on a sensitive dataset that must be protected. Variants of this
task arise naturally in fundamental problems like feature selection and
hypothesis testing, and also as subroutines for many sophisticated
differentially private algorithms.
The standard approaches to these tasks---repeated use of the exponential
mechanism or the sparse vector technique---approximately solve this problem
given a dataset of $n = O(\sqrt{k}\log d)$ samples. We provide a tight lower
bound for some very simple variants of the private selection problem. Our lower
bound shows that a sample of size $n = \Omega(\sqrt{k} \log d)$ is required
even to achieve a very minimal accuracy guarantee.
Our results are based on an extension of the fingerprinting method to sparse
selection problems. Previously, the fingerprinting method has been used to
provide tight lower bounds for answering an entire set of $d$ queries, but
often only some much smaller set of $k$ queries are relevant. Our extension
allows us to prove lower bounds that depend on both the number of relevant
queries and the total number of queries.

该研究提出了一个基于 “指纹” 方法的新的隐私保护选择问题下限界估算，并通过分析实际排除了一些标准假设。

差分隐私选择的严格下界

Tight Lower Bounds for Differentially Private Selection

The Sparse Vector Technique (SVT) is a fundamental technique for satisfying
differential privacy and has the unique quality that one can output some query
answers without apparently paying any privacy cost. SVT has been used in both
the interactive setting, where one tries to answer a sequence of queries that
are not known ahead of the time, and in the non-interactive setting, where all
queries are known. Because of the potential savings on privacy budget, many
variants for SVT have been proposed and employed in privacy-preserving data
mining and publishing. However, most variants of SVT are actually not private.
In this paper, we analyze these errors and identify the misunderstandings that
likely contribute to them. We also propose a new version of SVT that provides
better utility, and introduce an effective technique to improve the performance
of SVT. These enhancements can be applied to improve utility in the interactive
setting. Through both analytical and experimental comparisons, we show that, in
the non-interactive setting (but not the interactive setting), the SVT
technique is unnecessary, as it can be replaced by the Exponential Mechanism
(EM) with better accuracy.

本文提出了关于 Sparse Vector Technique 的一些改进和性能优化，揭示了现有变种存在的隐私不足问题，证明了在非交互式设置下，可以用 Exponential Mechanism 取代 SVT 来提供更好的准确性。