論文の概要: Tractable Importance Sampling for Monte Carlo Privacy Accounting
- arxiv url: http://arxiv.org/abs/2611.17596v1
- Date: Thu, 12 Nov 2026 23:33:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-16 18:43:16.277326
- Title: Tractable Importance Sampling for Monte Carlo Privacy Accounting
- Title(参考訳): モンテカルロのプライバシ会計におけるトラクタブルな重要度測定
- Abstract要約: 重要サンプリングによりモンテカルロをより効率的にすることができることを示す。
我々は、同じ有界な値を持つ重要サンプリング方向のサポートに対して、閉形式の$B() 1$を証明した。
- 参考スコア(独自算出の注目度): 8.992130705989604
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Evaluating tight Differential Privacy (DP) parameters for DP matrix factorization with privacy amplification by sampling requires analyzing high-dimensional, correlated Gaussian mixtures. Because integrating these mixture distributions to find the exact privacy failure probability ($δ$) is analytically intractable, these mechanisms are typically analyzed using Monte Carlo accounting. However, standard sampling suffers from prohibitive variance when estimating small $δ$ associated with strict privacy guarantees, which in turn requires a large sample complexity, making Monte Carlo accounting inefficient. We demonstrate that Monte Carlo accounting can be made much more efficient via importance sampling. We give a shifted importance sampling proposal distribution parameterized by a stretch factor $α> 1$. We prove a closed-form bound $B(α) < 1$ on the support of the importance-weighted estimator that holds identically for both directions of the hockey-stick divergence, show that $B$ is log-convex so that the optimal $α$ is a one-dimensional root-finding problem, and show that the resulting estimator seamlessly plugs into the KL-Hoeffding verification protocol used by past work, with a sample complexity reduced by exactly a factor of $1/B(α^*)$.
- Abstract(参考訳): DP行列分解のための厳密な微分プライバシ(DP)パラメータとサンプリングによるプライバシ増幅の評価には,高次元の相関したガウス混合の解析が必要である。
これらの混合分布を統合することで、正確なプライバシ障害確率(δ$)が分析可能であるため、これらのメカニズムは通常モンテカルロ会計を用いて分析される。
しかし、標準サンプリングは、厳格なプライバシー保証と関連する小さな$δ$を推定する際には、禁止的なばらつきに悩まされるため、モンテカルロの会計は非効率である。
重要サンプリングによりモンテカルロ会計をより効率的にすることができることを示す。
ストレッチ係数$α> 1$でパラメータ化された重要サンプリング提案分布をシフトする。
ホッケースティックの分岐の両方向を同一に保持する重要重み付き推定器の支持について、B(α) < 1$ の閉形式有界な $B(α) < 1$ を証明し、最適な $B$ が 1 次元のルートフィンディング問題であるように、対数凸であることを示すとともに、得られた推定器が過去の作業で使用される KL-Hoeffding の検証プロトコルにシームレスに接続し、サンプルの複雑さを1/B(α^*)$ の係数で正確に減らしたことを示す。
関連論文リスト
- Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。
我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文 参考訳(メタデータ) (2026-08-06T19:49:48Z) - High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
サブエクスフォデンシャルテールの繰り返し勾配を用いて,ログコンケーブサンプリングの精度保証が達成可能であることを示す。
また、このフレームワークは、0番目の順序(値)クエリの下でも、同様の高精度な保証を提供する。
論文 参考訳(メタデータ) (2026-02-15T23:19:07Z) - Demystifying SGD with Doubly Stochastic Gradients [13.033133586372612]
一般条件下では、独立なミニバッチとランダムリシャッフルを併用した2重SGDの収束特性を確立する。
ランダムリシャッフルによりサブサンプリングノイズの複雑性依存性が向上することが証明された。
論文 参考訳(メタデータ) (2024-06-03T01:13:19Z) - Convergence for score-based generative modeling with polynomial
complexity [9.953088581242845]
我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。
以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。
予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
論文 参考訳(メタデータ) (2022-06-13T14:57:35Z) - Covariance-Aware Private Mean Estimation Without Private Covariance Estimation [10.036088581191592]
2つのサンプル係数差分プライベート平均推定器を$d$-dimensional(sub)Gaussian分布に対して提案する。
我々の推定子は、$| tildemu - mu |_Sigma leq alpha$, where $| cdot |_Sigma$がマハラノビス距離であるような$tildemu$を出力します。
論文 参考訳(メタデータ) (2021-06-24T21:40:07Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳(メタデータ) (2020-12-31T18:24:41Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳(メタデータ) (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。