論文の概要: Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT

• arxiv url: http://arxiv.org/abs/2610.42117v1
• Date: Fri, 30 Oct 2026 17:51:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.861816
• Title: Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT
• Title（参考訳）: マルチスケールFFTを用いたランダムアロケーションのための高速プライバシ損失会計
• Abstract要約: 各ダイアディック区間に一様である格子上の確率比を表すアルゴリズムを与える。 各ペアの和の正確な丸めを各インターバル内で FFT を用いて計算する。 実験では,高精度に数桁の高速化を実現する。
• 参考スコア（独自算出の注目度）: 13.186391867041394
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the random allocation sampling scheme each user's data is used in $k$ steps chosen randomly and uniformly from a sequence of $t$ steps. This scheme is known to improve on Poisson sampling in private optimization and in communication-efficient aggregation. The existing privacy loss distribution (PLD) accountant for this scheme runs in time quadratic in the inverse of the accuracy parameter $α$ (Feldman and Shenfeld, 2026). We give an algorithm, \emph{multiscale FFT}, that represents likelihood ratios on a grid that is uniform within each dyadic interval and computes the exact rounding of every pairwise sum using FFTs within each interval. It keeps the guarantees of the accountant and improves the dependence of its running time on $α$ from $O(α^{-2})$ to $O(α^{-1}\log(1/α))$. In addition, we demonstrate that rounding can be performed via the mean-preserving connect-the-dots projection of (Doroshenko et al., 2026). This reduces the errors that rounding introduces in the mean of the privacy loss and in the $χ^2$ divergence of the computed pair from the order of $α$ to $O(α^2/\log(t))$. In our experiments, our algorithm achieves speedups of several orders of magnitude at high accuracy and gives improved privacy bounds for DP-SGD with PREAMBLE.
• Abstract（参考訳）: ランダム・アロケーション・サンプリング・スキームでは、各ユーザのデータは$k$のステップでランダムに選択され、$t$のステップのシーケンスから均一に選択される。 このスキームは、プライベート最適化や通信効率のよいアグリゲーションにおいて、Poissonサンプリングを改善することが知られている。 このスキームの既存のプライバシ損失分布(PLD)は、精度パラメータ$α$(フェルドマンとシェンフェルト、2026年)の逆の時間2次的に実行される。 本稿では,各次元間隔で均一な格子上の確率比を表すアルゴリズム「emph{multiscale FFT}」を提案し,各間隔でFFTを用いて各対の和の正確な丸めを計算する。 会計士の保証を維持し、実行時の依存を$O(α^{-2})$から$O(α^{-1}\log(1/α))$に改善する。 さらに,ドロッシェンコらによる平均保存接続ドット投影(2026年,2026年)によりラウンド化が可能であることを示す。 これにより、プライバシ損失や計算されたペアの$α$から$O(α^2/\log(t))$への分岐によって、ラウンドリングが引き起こすエラーが減少する。 実験では, DP-SGDの精度向上のために, DP-SGDの高速化を実現し, DP-SGDのプライバシバウンドをPreAMBLEで実現した。

関連論文リスト

• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
  オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。 長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
  論文  参考訳（メタデータ） (2026-09-30T21:03:03Z)
• Near-optimal Swap Regret Minimization for Convex Losses [21.006993033547708]
  我々は、ほぼ最適の$widetilde O(sqrt T)$期待スワップリミスを保証するランダム化されたオンラインアルゴリズムを、単位区間において適応的に選択されたLipschitz凸損失の任意の列に対して与える。
  論文  参考訳（メタデータ） (2026-02-09T16:26:34Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
  純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。 純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。 平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
  論文  参考訳（メタデータ） (2022-12-15T18:27:39Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
  整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。 大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
  論文  参考訳（メタデータ） (2022-05-16T02:24:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。