研究人员和从业人员如何处理隐私 - 实用性权衡之间存在脱节。研究人员主要是从隐私的第一角度运作，设定严格的隐私要求并最大程度地限制受这些约束的风险。从业者通常希望获得准确的第一视角，可能会对他们可能获得足够小的错误的最大隐私感到满意。 Ligett等。已经引入了一种“降噪”算法来解决后一种观点。作者表明，通过添加相关的拉普拉斯噪声并逐步减少其需求，可以产生一系列越来越准确的私人参数估计值，而仅以最低噪声介绍的方式支付隐私成本。在这项工作中，我们将降噪概括为高斯噪声的设置，并引入了布朗机制。布朗机制首先添加与模拟布朗运动的最后点相对应的高方差的高斯噪声。然后，根据从业人员的酌情决定权，通过沿着布朗的路径追溯到较早的时间来逐渐降低噪音。我们的机制更自然地适用于有限的$ \ ell_2 $ - 敏感性的共同设置，从经验上优于公共统计任务上的现有工作，并在与从业者的整个交互中提供了对隐私损失的可自定义控制。我们通过简化的Brownian机制来补充我们的布朗机制，这是对提供自适应隐私保证的经典座位算法的概括。总体而言，我们的结果表明，人们可以达到公用事业的限制，同时仍保持强大的隐私水平。

我们考虑如何私下分享客观扰动，使用每个实例差异隐私（PDP）所产生的个性化隐私损失。标准差异隐私（DP）为我们提供了一个最坏的绑定，可能是相对于固定数据集的特定个人的隐私丢失的数量级。PDP框架对目标个人的隐私保障提供了更细粒度的分析，但每个实例隐私损失本身可能是敏感数据的函数。在本文中，我们分析了通过客观扰动释放私人经验风险最小化器的每案隐私丧失，并提出一组私下和准确地公布PDP损失的方法，没有额外的隐私费用。

我们提出并分析了算法，以解决用户级差分隐私约束下的一系列学习任务。用户级DP仅保证只保证个人样本的隐私，而是保护用户的整个贡献（$ M \ GE 1 $ Samples），而不是对信息泄漏提供更严格但更现实的保护。我们表明，对于高维平均估计，具有平稳损失，随机凸优化和学习假设类别的经验风险最小化，具有有限度量熵，隐私成本随着用户提供的$ O（1 / \ SQRT {M}）$减少更多样本。相比之下，在增加用户数量$ N $时，隐私成本以较快的价格降低（1 / n）$率。我们将这些结果与下界相提并论，显示了我们算法的最低限度估计和随机凸优化的算法。我们的算法依赖于私有平均估计的新颖技术，其任意维度与误差缩放为浓度半径$ \ tai $的分布而不是整个范围。

在数据库查询结果中添加随机噪声是实现隐私的重要工具。一个挑战是最大程度地减少这种噪音，同时仍然满足隐私要求。最近，出版了$（\ epsilon，\ delta）$的足够和必要的条件 - 高斯噪声的差异隐私。这种情况允许计算此分布的最小隐私量表。我们扩展了这项工作，并为$（\ epsilon，\ delta）$ - 差分隐私提供了足够和必要的条件，用于所有对称和对象concove噪声密度。我们的结果允许将噪声分布的细粒度调整为查询结果的维度。我们证明，与当前使用的Laplace和Gaussian机制相同的$ \ epsilon $和$ \ delta $发生的Laplace和Gaussian机制所产生的均方误差明显低得多。

The ''Propose-Test-Release'' (PTR) framework is a classic recipe for designing differentially private (DP) algorithms that are data-adaptive, i.e. those that add less noise when the input dataset is nice. We extend PTR to a more general setting by privately testing data-dependent privacy losses rather than local sensitivity, hence making it applicable beyond the standard noise-adding mechanisms, e.g. to queries with unbounded or undefined sensitivity. We demonstrate the versatility of generalized PTR using private linear regression as a case study. Additionally, we apply our algorithm to solve an open problem from ''Private Aggregation of Teacher Ensembles (PATE)'' -- privately releasing the entire model with a delicate data-dependent analysis.

我们考虑一个顺序设置，其中使用单个数据集用于执行自适应选择的分析，同时确保每个参与者的差别隐私丢失不超过预先指定的隐私预算。此问题的标准方法依赖于限制所有个人对所有个人的隐私损失的最坏情况估计，以及每个单一分析的所有可能的数据值。然而，在许多情况下，这种方法过于保守，特别是对于“典型”数据点，通过参与大部分分析产生很少的隐私损失。在这项工作中，我们基于每个分析中每个人的个性化隐私损失估计的价值，给出了更严格的隐私损失会计的方法。实现我们设计R \'enyi差异隐私的过滤器。过滤器是一种工具，可确保具有自适应选择的隐私参数的组合算法序列的隐私参数不超过预先预算。我们的过滤器比以往的$（\ epsilon，\ delta）$ - rogers等人的差别隐私更简单且更紧密。我们将结果应用于对嘈杂渐变下降的分析，并显示个性化会计可以实用，易于实施，并且只能使隐私式权衡更紧密。

Concentrated differential privacy" was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Rényi divergence between the distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and raise a few new questions. We also unify this approach with approximate differential privacy by giving an appropriate definition of "approximate concentrated differential privacy."

我们提出了一种基于优化的基于优化的框架，用于计算差异私有M估算器以及构建差分私立置信区的新方法。首先，我们表明稳健的统计数据可以与嘈杂的梯度下降或嘈杂的牛顿方法结合使用，以便分别获得具有全局线性或二次收敛的最佳私人估算。我们在局部强大的凸起和自我协调下建立当地和全球融合保障，表明我们的私人估算变为对非私人M估计的几乎最佳附近的高概率。其次，我们通过构建我们私有M估计的渐近方差的差异私有估算来解决参数化推断的问题。这自然导致近​​似枢轴统计，用于构建置信区并进行假设检测。我们展示了偏置校正的有效性，以提高模拟中的小样本实证性能。我们说明了我们在若干数值例子中的方法的好处。

Privacy-preserving machine learning algorithms are crucial for the increasingly common setting in which personal data, such as medical or financial records, are analyzed. We provide general techniques to produce privacy-preserving approximations of classifiers learned via (regularized) empirical risk minimization (ERM). These algorithms are private under the ǫ-differential privacy definition due to Dwork et al. (2006). First we apply the output perturbation ideas of Dwork et al. (2006), to ERM classification. Then we propose a new method, objective perturbation, for privacy-preserving machine learning algorithm design. This method entails perturbing the objective function before optimizing over classifiers. If the loss and regularizer satisfy certain convexity and differentiability criteria, we prove theoretical results showing that our algorithms preserve privacy, and provide generalization bounds for linear and nonlinear kernels. We further present a privacy-preserving technique for tuning the parameters in general machine learning algorithms, thereby providing end-to-end privacy guarantees for the training process. We apply these results to produce privacy-preserving analogues of regularized logistic regression and support vector machines. We obtain encouraging results from evaluating their performance on real demographic and benchmark data sets. Our results show that both theoretically and empirically, objective perturbation is superior to the previous state-of-the-art, output perturbation, in managing the inherent tradeoff between privacy and learning performance.

我们呈现渐近最优的$（\ epsilon，\ delta）$差异私有机制，用于回答多个，自适应的$ \ delta $ -sursitive查询，解决Steinke和Ullman的猜想[2020]。我们的算法具有显着的优点，即它向每个查询增加独立的有界噪声，从而提供绝对误差。此外，我们在自适应数据分析中应用了我们的算法，获得了使用有限样本对某些基础分布的多个查询的改进保证。数值计算表明，界限噪声机制在许多标准设置中优于高斯机制。

最大信息系数（MIC）是一个强大的统计量，可以识别变量之间的依赖性。但是，它可以应用于敏感数据，并且发布可能会泄漏私人信息。作为解决方案，我们提出算法以提供差异隐私的方式近似麦克风。我们表明，经典拉普拉斯机制的自然应用产生的精度不足。因此，我们介绍了MICT统计量，这是一种新的MIC近似值，与差异隐私更加兼容。我们证明MICS是麦克风的一致估计器，我们提供了两个差异性私有版本。我们对各种真实和合成数据集进行实验。结果表明，私人微统计数据极大地超过了拉普拉斯机制的直接应用。此外，对现实世界数据集的实验显示出准确性，当样本量至少适中时可用。

在共享数据的统计学习和分析中，在联合学习和元学习等平台上越来越广泛地采用，有两个主要问题：隐私和鲁棒性。每个参与的个人都应该能够贡献，而不会担心泄露一个人的敏感信息。与此同时，系统应该在恶意参与者的存在中插入损坏的数据。最近的算法在学习中，学习共享数据专注于这些威胁中的一个，使系统容易受到另一个威胁。我们弥合了这个差距，以获得估计意思的规范问题。样品。我们介绍了素数，这是第一算法，实现了各种分布的隐私和鲁棒性。我们通过新颖的指数时间算法进一步补充了这一结果，提高了素数的样本复杂性，实现了近最优保证并匹配（非鲁棒）私有平均估计的已知下限。这证明没有额外的统计成本同时保证隐私和稳健性。

特征在于构图的隐私劣化，即隐私会计，是差异隐私（DP）的基本话题，许多应用于差异私有机器学习和联合学习。我们提出了近期进步（Renyi DP，Privacy Compiles，$-D $ -dp和Pld形式主义）的统一，通过\ emph {phi $ \ phi $ -function）{占主导地位}隐私损失随机变量。我们展示了我们的方法允许\ emph {natural}自适应组成等renyi dp，提供\ emph {完全紧张}隐私会计，如pld，并且可以（通常是\ memph {docklyly}）转换为隐私权概况和$ f $ -dp ，从而提供$（\ epsilon，\ delta）$ - DP保证和可解释的权衡职能。算法，我们提出了一个\ xper {分析傅里叶会计师}，它象征性地表示$ \ phi $ -functions的\ icph {complex}对数，并使用高斯正交进行数值计算。在几个受欢迎的DP机制及其撤销的对应物上，我们展示了我们在理论和实验中的方法的灵活性和紧张性。

在本文中，我们重新审视了私人经验风险最小化（DP-erm）和差异私有随机凸优化（DP-SCO）的问题。我们表明，来自统计物理学（Langevin Exfusion（LD））的经过良好研究的连续时间算法同时为DP-SCO和DP-SCO提供了最佳的隐私/实用性权衡，$ \ epsilon $ -DP和$ $ \ epsilon $ -DP和$ （\ epsilon，\ delta）$ - dp均用于凸和强烈凸损失函数。我们为LD提供新的时间和尺寸独立统一稳定性，并使用我们为$ \ epsilon $ -DP提供相应的最佳超额人口风险保证。 $ \ epsilon $ -DP的DP-SCO保证的一个重要属性是，它们将非私人最佳界限匹配为$ \ epsilon \与\ infty $。在此过程中，我们提供了各种技术工具，这些工具可能引起独立的关注：i）在两个相邻数据集上运行损失功能时，一个新的r \'enyi Divergence绑定了LD，ii）最后一个过多的经验风险范围迭代LD，类似于Shamir和Zhang的嘈杂随机梯度下降（SGD）和iii）的LD，对LD进行了两期多余的风险分析，其中第一阶段是当扩散在任何合理意义上都没有在任何合理意义上融合到固定分布时，在第二阶段扩散已收敛到吉布斯分布的变体。我们的普遍性结果至关重要地依赖于LD的动力学。当它融合到固定分布时，我们获得了$ \ epsilon $ -DP的最佳界限。当它仅在很短的时间内运行$ \ propto 1/p $时，我们在$（\ epsilon，\ delta）$ -DP下获得最佳界限。在这里，$ p $是模型空间的维度。

我们给出了第一个多项式算法来估计$ d $ -variate概率分布的平均值，从$ \ tilde {o}（d）$独立的样本受到纯粹的差异隐私的界限。此问题的现有算法无论是呈指数运行时间，需要$ \ OMEGA（D ^ {1.5}）$样本，或仅满足较弱的集中或近似差分隐私条件。特别地，所有先前的多项式算法都需要$ d ^ {1+ \ omega（1）} $ samples，以保证“加密”高概率，1-2 ^ { - d ^ {\ omega（1） $，虽然我们的算法保留$ \ tilde {o}（d）$ SAMPS复杂性即使在此严格设置中也是如此。我们的主要技术是使用强大的方块方法（SOS）来设计差异私有算法的新方法。算法的证据是在高维算法统计数据中的许多近期作品中的一个关键主题 - 显然需要指数运行时间，但可以通过低度方块证明可以捕获其分析可以自动变成多项式 - 时间算法具有相同的可证明担保。我们展示了私有算法的类似证据现象：工作型指数机制的实例显然需要指数时间，但可以用低度SOS样张分析的指数时间，可以自动转换为多项式差异私有算法。我们证明了捕获这种现象的元定理，我们希望在私人算法设计中广泛使用。我们的技术还在高维度之间绘制了差异私有和强大统计数据之间的新连接。特别是通过我们的校验算法镜头来看，几次研究的SOS证明在近期作品中的算法稳健统计中直接产生了我们差异私有平均估计算法的关键组成部分。

在这项工作中，我们在用户级差异隐私下研究高维平均值估计，并设计$（\ varepsilon，\ delta）$ - 使用尽可能少的用户差异化私人机制。特别是，即使用户数量低至$ o（\ frac {1} {\ varepsilon } \ log \ frac {1} {\ delta}）$。有趣的是，这对\ emph {users}的数量绑定到独立于维度（尽管\ emph {samples aper users}的数量被允许以多项式依赖于尺寸），这与先前需要用户数量的工作数量不同。在多项式上依赖于维度。这解决了Amin等人首先提出的问题。此外，我们的机制可抵抗高达$ 49 \％用户的损坏。最后，我们的结果还适用于与少数用户私下学习离散分布的最佳算法，回答Liu等人的问题，以及更广泛的问题，例如随机凸优化和通过差异化的随机梯度优化和随机梯度下降的变体私人平均估计。

我们给出了第一个多项式时间和样本$（\ epsilon，\ delta）$ - 差异私有（DP）算法，以估计存在恒定的对抗性异常分数的平均值，协方差和更高的时刻。我们的算法成功用于分布的分布系列，以便在经济估计上满足两个学习的良好性质：定向时刻的可证明的子销售，以及2度多项式的可证式超分子。我们的恢复保证持有“右仿射效率规范”：Mahalanobis距离的平均值，乘法谱和相对Frobenius距离保证，适用于更高时刻的协方差和注射规范。先前的作品获得了私有稳健算法，用于界限协方差的子静脉分布的平均估计。对于协方差估算，我们的是第一算法（即使在没有异常值的情况下也是在没有任何条件号的假设的情况下成功的。我们的算法从一个新的框架出现，该框架提供了一种用于修改凸面放宽的一般蓝图，以便在算法在其运行中产生正确的正确性的证人，以满足适当的参数规范中的强烈最坏情况稳定性。我们验证了用于修改标准的平方（SOS）SEMIDEFINITE编程放松的担保，以实现鲁棒估算。我们的隐私保障是通过将稳定性保证与新的“估计依赖性”噪声注入机制相结合来获得，其中噪声比例与估计的协方差的特征值。我们认为，此框架更加有用，以获得强大的估算器的DP对应者。独立于我们的工作，Ashtiani和Liaw [Al21]还获得了高斯分布的多项式时间和样本私有鲁棒估计算法。

许多现代的机器学习算法由简单的私人算法组成；因此，一个越来越重要的问题是有效计算组成下的整体隐私损失。在这项研究中，我们介绍了Edgeworth会计师，这是一种分析方法，用于构成私人算法的差异隐私保证。 Edgeworth会计师首先使用$ f $ - 不同的隐私框架来无误地跟踪构图下的隐私损失，该框架使我们能够使用隐私损失log-logikelihoodhiehood（pllrs）表达隐私保证。顾名思义，该会计师接下来使用Edgeworth扩展到上下界限PLLR的总和的概率分布。此外，通过依靠一种使用简单的技术近似复杂分布的技术，我们证明了Edgeworth会计师可以应用于任何噪声加成机制的组成。由于Edgeworth扩展的某些吸引人的功能，该会计师提供的$（\ epsilon，\ delta）$ - 差异隐私范围是非反应的，基本上没有额外的计算成本，而不是先前的方法运行时间随成分的数量而增加。最后，我们证明了我们的上和下部$（\ epsilon，\ delta）$ - 差异隐私范围在联合分析和培训私人深度学习模型的某些制度中紧密。

We introduce a new tool for stochastic convex optimization (SCO): a Reweighted Stochastic Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. Combining ReSQue with recent advances in ball oracle acceleration [CJJJLST20, ACJJS21], we develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings. For a SCO objective constrained to the unit ball in $\mathbb{R}^d$, we obtain the following results (up to polylogarithmic factors). We give a parallel algorithm obtaining optimization error $\epsilon_{\text{opt}}$ with $d^{1/3}\epsilon_{\text{opt}}^{-2/3}$ gradient oracle query depth and $d^{1/3}\epsilon_{\text{opt}}^{-2/3} + \epsilon_{\text{opt}}^{-2}$ gradient queries in total, assuming access to a bounded-variance stochastic gradient estimator. For $\epsilon_{\text{opt}} \in [d^{-1}, d^{-1/4}]$, our algorithm matches the state-of-the-art oracle depth of [BJLLS19] while maintaining the optimal total work of stochastic gradient descent. We give an $(\epsilon_{\text{dp}}, \delta)$-differentially private algorithm which, given $n$ samples of Lipschitz loss functions, obtains near-optimal optimization error and makes $\min(n, n^2\epsilon_{\text{dp}}^2 d^{-1}) + \min(n^{4/3}\epsilon_{\text{dp}}^{1/3}, (nd)^{2/3}\epsilon_{\text{dp}}^{-1})$ queries to the gradients of these functions. In the regime $d \le n \epsilon_{\text{dp}}^{2}$, where privacy comes at no cost in terms of the optimal loss up to constants, our algorithm uses $n + (nd)^{2/3}\epsilon_{\text{dp}}^{-1}$ queries and improves recent advancements of [KLL21, AFKT21]. In the moderately low-dimensional setting $d \le \sqrt n \epsilon_{\text{dp}}^{3/2}$, our query complexity is near-linear.

本文研究了Markov决策过程（MDP）的隐私保留探索，线性表示。我们首先考虑线性混合MDP（Ayoub等，2020）（A.K.A.基于模型的设置）的设置，并提供统一的框架，用于分析关节和局部差异私有（DP）探索。通过这个框架，我们证明了一个$ \ widetilde {o}（k ^ {3/4} / \ sqrt {\ epsilon}）$遗憾绑定$（\ epsilon，\ delta）$ - 本地DP探索和$ \widetilde {o}（\ sqrt {k / \ epsilon}）$后悔绑定$（\ epsilon，\ delta）$ - 联合dp。我们进一步研究了Linear MDP中的隐私保留探索（Jin等，2020）（AKA \ Forws-Free Setting），我们提供$ \ widetilde {o}（\ sqrt {k / \ epsilon}）$后悔绑定$（\ epsilon，\ delta）$ - 关节dp，具有基于低切换的新型算法。最后，我们提供了在这种无模型设置中设计本地DP算法的问题的见解。