Fugu-MT 論文翻訳(概要): Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms

論文の概要: Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms

arxiv url: http://arxiv.org/abs/2610.33333v1
Date: Fri, 23 Oct 2026 22:10:12 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-27 22:27:13.303118
Title: Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms
Title（参考訳）: 微分プライベートアルゴリズムの構成とサブサンプリングのためのガウス近似
Abstract要約: このペアのプライバシロスは、各ステップが小さな確率を除いて小さなプライバシロスを持つ限り、ほぼガウス的であることを示す。特に、この構成はガウスの差分プライバシーを$varepsilon$の下位シフトと加法誤差$$$で満たしている。また、単一ステップの2ドルの発散に依存するサブサンプル機構に対して、結果として生じる分散ベースの境界を簡易に解析する方法を提供する。
参考スコア（独自算出の注目度）: 13.186391867041394
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: The privacy analysis of differentially private stochastic gradient descent (DP-SGD) relies on bounds for the composition of subsampled mechanisms. The privacy of such a composition is bounded by that of a pair of product distributions, whose privacy loss is a sum of independent terms and has been analyzed via a variety of notions and concentration results. Yet, existing closed-form bounds either lose a logarithmic factor or require restrictive conditions on the noise scale and delicate analysis of subsampling. Further, while it is well known that sums of independent random variables are approximately Gaussian, existing CLT-based techniques give an approximation with a large error in $δ$. We show that the privacy loss of this pair is approximately Gaussian as long as each step has a small privacy loss except with small probability. Specifically, its privacy loss distribution is close to a Gaussian with the same mean and variance, after truncating the rare large privacy losses. The closeness in both directions is up to a shift of $\varepsilon$ that grows only as $\ln(1/β)$ for an additive error $β$ in $δ$ and is a lower-order term in typical applications. In particular, the composition satisfies Gaussian differential privacy up to a lower-order shift of $\varepsilon$ and the additive error $β$. We also give a simple way to analyze the resulting variance-based bounds for subsampled mechanisms which relies on the $χ^2$ divergence of a single step. For the Gaussian mechanism at sampling rate $1/t$ and $t>\ln^{3}(1/δ)$, this gives the predicted rate for $σ\gtrsim\max\{1,\sqrt{\ln(1/δ)}/\ln(t)\}$, whereas the standard Rényi-divergence analyses need $σ\gtrsim\sqrt{t\ln(1/δ)}/\ln(t)$. We extend these results to random allocation (balls-and-bins sampling), and show that it explains the high accuracy of the connect-the-dots method.
Abstract（参考訳）: 個人確率勾配勾配(DP-SGD)のプライバシー分析は, サブサンプリング機構の構成の限界に依存する。このような構成のプライバシは、プライバシの損失は独立した用語の総和であり、さまざまな概念と集中結果を通じて分析された、一対の製品分布によって制限される。しかし、既存の閉形式境界は対数係数を失うか、ノイズスケールの制限条件とサブサンプリングの微妙な解析を必要とする。さらに、独立確率変数の和がほぼガウス的であることはよく知られているが、既存の CLT ベースの手法は大きな誤差を$δ$で近似する。このペアのプライバシロスは、各ステップが小さな確率を除いて小さなプライバシロスを持つ限り、ほぼガウス的であることを示す。具体的には、そのプライバシー損失の分布は、稀な大きなプライバシー損失を減らした後、同じ平均とばらつきを持つガウシアンに近い。両方の方向の近さは$\varepsilon$のシフトであり、このシフトは$\ln(1/β)$として、加法誤差$β$ in $δ$に対してのみ成長し、典型的なアプリケーションでは下位の項である。特に、この構成はガウス微分プライバシーを$\varepsilon$と加法誤差$β$の下位シフトに満足する。また, 単一ステップの $ ^2$ の発散に依存する部分サンプリング機構に対して, 結果の分散に基づく境界を簡易に解析する方法も提示する。サンプリングレート 1/t$ と $t>\ln^{3}(1/δ)$ のガウス機構では、$σ\gtrsim\max\{1,\sqrt{\ln(1/δ)}/\ln(t)\}$ が予想されるが、標準のレニー・ディバージェンス解析では$σ\gtrsim\sqrt{t\ln(1/δ)}/\ln(t)$ が必要とされる。本研究では,これらの結果をランダムなアロケーション(ボール・アンド・ビンサンプリング)に拡張し,コネクテッド・ザ・ドット法の高精度性を示す。

論文の概要: Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms

関連論文リスト