論文の概要: Privacy Amplification Without Independence: How Far Negative Dependence Carries the Guarantees of Poisson Subsampling
- arxiv url: http://arxiv.org/abs/2609.01944v1
- Date: Tue, 01 Sep 2026 23:20:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-03 17:53:18.009518
- Title: Privacy Amplification Without Independence: How Far Negative Dependence Carries the Guarantees of Poisson Subsampling
- Title（参考訳）: 独立性のないプライバシの増幅:ポアソン・サブサンプリングの保証に負の依存がいかに影響するか
- Abstract要約: 我々は、$k=1$のランダムアロケーションに対して、レニ・ディファレンス基準に対する線形法則を証明した。
Poissonベースの計算が構造化された参加に相応しいままで、どこで失敗し、デプロイに何の代償がかかるか、というように、プライバシ会計の代用マップを提供します。
- 参考スコア（独自算出の注目度）: 3.6238624372073254
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Poisson subsampling is the default sampler in differentially private optimization because its independence makes privacy amplification tractable. Practical systems, however, are moving toward structured participation: random allocation (balls-in-bins), per-epoch allocation, random check-ins, schemes widely believed to be at least as private as Poisson subsampling at the matched rate. We isolate the probabilistic mechanism behind this belief and delimit it exactly, for Gaussian mechanisms up to correlated-noise matrix mechanisms. (1) If the participation indicator vector is negatively associated (NA), then at every integer Rényi order $α\ge2$, exactly at all finite parameters, its remove-direction Rényi divergence is dominated by that of the marginal-matched independent scheme. For fixed gradient sequences, this extends to the mechanism level whenever the noise strategy's Gram matrix is sign-balanced, an $O(t^2)$-checkable condition. (2) The integer-order restriction is essential. For random allocation with $k=1$, we prove a linear law for the Rényi-difference criterion: at large $t$, dominance reverses for every $α<3/2$, including KL divergence, while the crossing order tends to $3/2$ independently of $σ$. (3) We also localize the known failure of rate-matched Poisson domination exactly: below $(1-q)^t$, the hockey-stick ordering reverses, so substituting the Poisson pair into composition machinery is unsound. An upper-tail argument yields a finite crossover $γ_\star$, connecting this threshold picture to the Rényi boundary at $3/2$. Together, these results give a substitution map for privacy accounting: when Poisson-based computations remain sound for structured participation, where they fail, and what sound alternatives cost in deployment.
- Abstract（参考訳）: Poissonサブサンプリングは、独立性によってプライバシーの増幅が困難になるため、差分的にプライベートな最適化においてデフォルトのサンプリングである。
しかし、実際のシステムでは、ランダムアロケーション(ボール・イン・ビン)、エポックアロケーション毎のアロケーション、ランダム・チェックイン、一致したレートでポアソン・サブサンプリングする少なくともプライベートであると広く信じられているスキームなど、構造化された参加に向かっている。
我々は、この信念の背後にある確率的メカニズムを分離し、それを正確に、ガウス的メカニズムから相関ノイズ行列機構まで、分離する。
1) 参加指示ベクトルが負に関連している場合(NA)、任意の整数 Rényi 位数 $α\ge2$ において、正確にはすべての有限パラメータにおいて、その除去方向 Rényi の発散は、境界整合独立スキームによって支配される。
固定勾配列の場合、これはノイズストラテジーのグラム行列が符号平衡であるときに、$O(t^2)$-checkable条件で、メカニズムレベルまで拡張される。
2) 整数階数制限は必須である。
k=1$ のランダムな割当については、Rényi-difference criterion に対する線型法則を証明します:大まかに $t$ では、KL の発散を含むすべての$α<3/2$ に対して支配逆であり、交差順序は$σ$ とは独立に$/2$ となる傾向があります。
(3) 速度整合ポアソン支配の既知失敗は, 1-q)^t$以下で, ホッケースティックの順序が逆転するので, ポアソン対を合成機械に置換することは正しくない。
上尾の引数は有限のクロスオーバー$γ_\star$となり、このしきい値をレニー境界に3/2$で接続する。
これらの結果は、Poissonベースの計算が構造化された参加に対して健全なままで、どこで失敗し、デプロイにどのサウンドがかかるかというように、プライバシ会計の代用マップを提供する。
関連論文リスト
- A Finite Sample Analysis for Quantile Temporal Difference Learning in Distributional Reinforcement Learning [18.875039998204848]
分散強化学習における同期量子時間差分学習(QTD)のグローバル有限サンプル保証を確立する。
大域的な比較論は、報酬累積分布関数の順序単調性と分布ベルマン作用素の$W_infty$収縮に基づいて、局所近傍に任意に安定性をもたらす。
論文 参考訳（メタデータ） (2026-08-27T16:16:09Z) - The Variance of Thought: Policy Variance, Critical Forks, and Local Credit Assignment [2.6994604905555004]
政策分散はリターン分散の唯一の源であり、臨界フォークと呼ばれる状態において離散パルスに注入される。
ブートストラッピングは、生存確率の積を和に変換することによってモンテカルロの利点推定を除去する。
論文 参考訳（メタデータ） (2026-08-23T15:46:56Z) - Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。
本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。
結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
論文 参考訳（メタデータ） (2026-08-12T14:54:15Z) - Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
論文 参考訳（メタデータ） (2026-08-04T23:38:54Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Anisotropic local law for non-separable sample covariance matrices [10.181748307494608]
サンプル共分散行列の局所法則を$K = N-1sum_i=1N g_ig_ig_i*$ とすると、Rn$ の確率ベクトル $g_1, ldots, g_N は共通共分散$$と独立である。
我々は,条件付き平均ゼロ分布,ランダム特徴モデル$g = (Xw)$,ガウス測度など,我々の仮定を満たす非分離例のクラスについて論じる。
論文 参考訳（メタデータ） (2026-02-20T03:28:51Z) - Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。
任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。
本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
論文 参考訳（メタデータ） (2026-02-19T17:21:15Z) - Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
有限状態マルコフ鎖を$n$状態と遷移行列$P$で研究する。
すべての非退化モードが実周辺不変部分空間 $mathcalK(P)$ によってキャプチャされ、商空間 $mathbbRn/mathcalK(P) 上の誘導作用素が厳密に収縮し、ユニークな商解が得られることを示す。
論文 参考訳（メタデータ） (2026-01-31T02:57:01Z) - Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
我々は、各期間に複数の武器で再生可能資源の1単位を割り当てる意思決定者について検討する。
アームは未知でランダムな報酬であり、その手段は割り当てられたリソースに比例し、分散は割り当てられたリソースのオーダー$b$に比例する。
論文 参考訳（メタデータ） (2023-06-28T21:59:11Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。