論文の概要: Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
- arxiv url: http://arxiv.org/abs/2610.19335v1
- Date: Wed, 14 Oct 2026 00:21:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-15 21:06:15.860205
- Title: Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
- Title（参考訳）: Markov Chainsの異なるプライベート学習: アイテムとユーザレベルのプライバシのためのほぼ最適なサンプル複雑さ
- Abstract要約: 離散エルゴード型マルコフ鎖の遷移行列を長さ T の N 個の独立軌道からプライベートに推定する。
アイテムレベルのプライバシの下では、サンプリング、州の占有と混合、プライバシーのコストを分離する、上下限のバウンダリを与えます。
個別分布の積を推定するために最適なユーザレベルのプライベートバウンダリを確立する。
- 参考スコア（独自算出の注目度）: 8.77927725146269
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sequential data such as documents, conversations, and trajectories are naturally partitioned across users, motivating privacy guarantees that protect each user's entire trajectory. We initiate the study of privately estimating the transition matrix of a discrete ergodic Markov chain from N independent trajectories of length T, with arbitrary initial distributions, under maximum row-wise ell 1 error. Besides N, T, and the number of states, our bounds depend on the minimum stationary probability and the pseudo-spectral gap, which govern state coverage and mixing. Under item-level privacy, we give upper and lower bounds that separate the costs of sampling, state occupancy and mixing, and privacy. Under user-level privacy, we reduce the problem for sufficiently long trajectories to private product distribution estimation. Along the way, we establish optimal user-level private bounds for estimating products of discrete distributions, which may be of independent interest. In the user level setting, our bounds are nearly tight in the large T regime, whereas in the item-level setting, our bounds as tight up-to a non-private term.
- Abstract（参考訳）: 文書、会話、トラジェクトリなどのシーケンシャルデータは、ユーザー間で自然に分割され、各ユーザのトラジェクトリ全体を保護するプライバシー保証を動機付けている。
任意の初期分布を持つ長さ T の N 個の独立トラジェクトリから離散エルゴード型マルコフ鎖の遷移行列を最大行幅のEL 1 誤差でプライベートに推定する研究を開始する。
N、T、および状態の数に加えて、我々の境界は、状態カバレッジと混合を管理する最小の定常確率と擬スペクトルギャップに依存する。
アイテムレベルのプライバシの下では、サンプリング、州の占有と混合、プライバシーのコストを分離する、上下限のバウンダリを与えます。
ユーザレベルのプライバシの下では,個人の製品分布推定に十分な長いトラジェクトリの問題を低減します。
その過程で、個別分布の積を推定するための最適なユーザレベルのプライベート境界を確立する。
ユーザレベルの設定では、我々の境界は大きなT体制でほぼ緊密であるのに対して、アイテムレベルの設定では、私たちの境界は非プライベートな用語にタイトである。
関連論文リスト
- A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants [0.8021197489470758]
本稿では,確率 1 あるいは指数関数的に 1 に近いアグリゲーション不変量を維持する高エントロピー差分プライバシー実装を提案する。
この手法は、線形等式制約下での通常の混合モデルからのサンプリングの文脈で一般的に用いられる。
論文 参考訳（メタデータ） (2026-07-24T16:13:07Z) - Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。
本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。
このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
論文 参考訳（メタデータ） (2026-02-12T17:49:07Z) - Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。
微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。
これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
論文 参考訳（メタデータ） (2025-02-13T02:05:45Z) - Enhancing Feature-Specific Data Protection via Bayesian Coordinate Differential Privacy [55.357715095623554]
ローカル微分プライバシー(LDP)は、ユーザーが外部の関係者を信頼することなく、強力なプライバシー保証を提供する。
本稿では,ベイジアン・フレームワークであるベイジアン・コーディネート・ディファレンシャル・プライバシ(BCDP)を提案する。
論文 参考訳（メタデータ） (2024-10-24T03:39:55Z) - Optimal Private Discrete Distribution Estimation with One-bit Communication [63.413106413939836]
1ビット通信制約を伴う個別分布推定問題を考える。
1ビット通信制約下での最悪のトレードオフの1次を特徴付ける。
これらの結果は,1ビット通信制約下でのプライバシユーティリティトレードオフの最適依存性を示す。
論文 参考訳（メタデータ） (2023-10-17T05:21:19Z) - On the Statistical Complexity of Estimation and Testing under Privacy Constraints [17.04261371990489]
差分プライバシー下での統計的テストのパワーをプラグアンドプレイ方式で特徴付ける方法を示す。
プライバシ保護のレベルが非常に高い場合にのみ、プライバシの維持が顕著なパフォーマンス低下をもたらすことを示す。
最後に,プライベート凸解法であるDP-SGLDアルゴリズムを高信頼度で最大推定できることを示した。
論文 参考訳（メタデータ） (2022-10-05T12:55:53Z) - Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。
ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。
これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
論文 参考訳（メタデータ） (2022-06-06T13:49:37Z) - Don't Generate Me: Training Differentially Private Generative Models
with Sinkhorn Divergence [73.14373832423156]
そこで我々はDP-Sinkhornを提案する。DP-Sinkhornは個人データからデータ分布を差分プライバシで学習するための新しいトランスポートベース生成手法である。
差分的にプライベートな生成モデルを訓練するための既存のアプローチとは異なり、我々は敵の目的に頼らない。
論文 参考訳（メタデータ） (2021-11-01T18:10:21Z) - Successive Refinement of Privacy [38.20887036580742]
本研究は、局所微分プライバシー(LDP)を実現するために、どの程度ランダム性が必要かを検討する。
モチベーションシナリオは、複数のアナリストに複数のレベルのプライバシを提供することである。
各ユーザのプライバシーを維持しながら、ランダムなキーを時間の経過とともに再利用できないことを示す。
論文 参考訳（メタデータ） (2020-05-24T04:16:01Z) - Bounding, Concentrating, and Truncating: Unifying Privacy Loss
Composition for Data Analytics [2.614355818010333]
アナリストが純粋なDP、境界範囲(指数的なメカニズムなど)、集中的なDPメカニズムを任意の順序で選択できる場合、強いプライバシー損失バウンダリを提供する。
また、アナリストが純粋なDPと境界範囲のメカニズムをバッチで選択できる場合に適用される最適なプライバシー損失境界を提供する。
論文 参考訳（メタデータ） (2020-04-15T17:33:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。