論文の概要: Differentially Private Language Generation and Identification in the Limit
- arxiv url: http://arxiv.org/abs/2604.08504v1
- Date: Thu, 09 Apr 2026 17:48:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-10 18:34:06.055945
- Title: Differentially Private Language Generation and Identification in the Limit
- Title（参考訳）: 限界における微分プライベート言語の生成と識別
- Authors: Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou,
- Abstract要約: 我々は,Kleinberg と Mullainathan [KM24] が最近導入した言語生成の限界について,差分プライバシーの制約の下で検討した。
我々は任意の可算コレクションから極限を生成する$varepsilon$-differentially-privateアルゴリズムを提供する。
我々は、$varepsilon$-DPアルゴリズムが無限交叉と有限集合差を持つ2つの言語を含む集合を識別できないことを証明した。
- 参考スコア（独自算出の注目度）: 17.31852533022177
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consider the continual release model, where a generator must eventually output a stream of valid strings while protecting the privacy of the entire input sequence. Our first main result is that for countable collections of languages, privacy comes at no qualitative cost: we provide an $\varepsilon$-differentially-private algorithm that generates in the limit from any countable collection. This stands in contrast to many learning settings where privacy renders learnability impossible. However, privacy does impose a quantitative cost: there are finite collections of size $k$ for which uniform private generation requires $Ω(k/\varepsilon)$ samples, whereas just one sample suffices non-privately. We then turn to the harder problem of language identification in the limit. Here, we show that privacy creates fundamental barriers. We prove that no $\varepsilon$-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference, a condition far stronger than the classical non-private characterization of identification. Next, we turn to the stochastic setting where the sample strings are sampled i.i.d. from a distribution (instead of being generated by an adversary). Here, we show that private identification is possible if and only if the collection is identifiable in the adversarial model. Together, our results establish new dimensions along which generation and identification differ and, for identification, a separation between adversarial and stochastic settings induced by privacy constraints.
- Abstract（参考訳）: Kleinberg と Mullainathan [KM24] が最近導入したモデルである。
連続的なリリースモデルを考えると、ジェネレータは最終的に有効な文字列のストリームを出力し、入力シーケンス全体のプライバシを保護する必要がある。
最初の主な成果は、可算言語のコレクションの場合、プライバシは定性的なコストを伴わず、任意の可算コレクションから制限で生成される$\varepsilon$-differentially-privateアルゴリズムを提供することです。
これは、プライバシーが学習を不可能にする多くの学習環境とは対照的である。
しかし、プライバシーは定量的なコストを課す:$k$の有限サイズのコレクションがあり、一様プライベート世代は$Ω(k/\varepsilon)$サンプルを必要とする。
そして、その限界における言語識別の難しい問題に目を向けます。
ここでは、プライバシーが基本的な障壁を生み出すことを示す。
我々は、$\varepsilon$-DPアルゴリズムが無限交叉と有限集合差を持つ2つの言語を含むコレクションを識別できないことを証明した。
次に、サンプル文字列が分布から(相手によって生成される代わりに)サンプリングされる確率的な設定に目を向ける。
ここでは,個人識別が可能であることと,そのコレクションが敵モデルで識別可能であることとを示す。
その結果, 生成と識別の異なる新たな次元が確立され, プライバシー制約によって引き起こされる対角的・確率的設定の分離が確認された。
関連論文リスト
- Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。
本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。
このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
論文 参考訳（メタデータ） (2026-02-12T17:49:07Z) - High-Dimensional Asymptotics of Differentially Private PCA [4.168157981135696]
差分プライバシーでは、機密データセットの統計はランダムノイズを導入することで民営化される。
このような高い騒音レベルが本当に必要か、あるいは証明技術に限界があるのかは、まだ不明である。
本稿では,ターゲットのプライバシレベルを達成するために必要な最小のノイズレベルを識別する,シャープなプライバシ特性を得ることができるかを検討する。
論文 参考訳（メタデータ） (2025-11-10T16:17:16Z) - DP-Fusion: Token-Level Differentially Private Inference for Large Language Models [51.71591819896191]
大規模言語モデル(LLM)は、推論時にプライバシを保存しない。
DP-Fusion は LLM の出力にコンテキスト内のトークンの集合が持つ影響を証明的に束縛する。
提案手法は, 理論的および実証的プライバシを大幅に改善した, 証明可能な民営化文書を作成する。
論文 参考訳（メタデータ） (2025-07-06T20:49:39Z) - InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy [7.006059299522521]
InvisibleInkは、厳格な差分プライバシー保証を満たすスケーラブルな長文生成フレームワークである。
モデルログ内の機密情報のみを分離・切断することで、プライバシコストを削減する。
我々は、トップ$kのプライベートトークンの小さなスーパーセットからサンプリングすることで、テキストの品質を向上させる。
論文 参考訳（メタデータ） (2025-06-30T18:00:41Z) - On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。
差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。
アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
論文 参考訳（メタデータ） (2023-02-11T14:45:31Z) - 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) - Quantifying identifiability to choose and audit $\epsilon$ in
differentially private deep learning [15.294433619347082]
機械学習で差分プライバシーを使用するには、データサイエンティストがプライバシパラメータを$(epsilon,delta)$を選択する必要がある。
私たちは$(epsilon,delta)$を、トレーニングデータセット内のレコードの存在に関する差分プライバシーによって想定される相手のベイジアン後方信念にバインドに変換します。
我々は、データサイエンティストがモデルのトレーニングを監査し、経験的識別可能性スコアと経験的$(epsilon,delta)$を計算することを可能にするこの差分プライバシーの敵対の実装を策定します。
論文 参考訳（メタデータ） (2021-03-04T09:35:58Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - Successive Refinement of Privacy [38.20887036580742]
本研究は、局所微分プライバシー(LDP)を実現するために、どの程度ランダム性が必要かを検討する。
モチベーションシナリオは、複数のアナリストに複数のレベルのプライバシを提供することである。
各ユーザのプライバシーを維持しながら、ランダムなキーを時間の経過とともに再利用できないことを示す。
論文 参考訳（メタデータ） (2020-05-24T04:16:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。