論文の概要: Edit-Neighboring Data Streams and Privacy under Continual Observation
- arxiv url: http://arxiv.org/abs/2607.20727v1
- Date: Wed, 22 Jul 2026 20:54:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-24 18:26:25.220655
- Title: Edit-Neighboring Data Streams and Privacy under Continual Observation
- Title（参考訳）: 連続観察による編集関連データストリームとプライバシ
- Abstract要約: 連続観測(CO)下での差分プライバシーは、センシティブな入力データストリームを使用して生成された出力がオンライン設定で発行されたときに発生するプライバシーの損失を定量化する。
我々は、個人の参加がストリーム全体をタイムステップでシフトする、以前の作業と比べて、より厳密なプライバシの概念を考えます。
我々は、任意の入力ストリームとスパースストリームの両方に対して、より悪い定数係数で、プライバシという標準概念と同じ加算誤差を回復できることを示します。
- 参考スコア（独自算出の注目度）: 12.49920379845039
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting. In this paper, we consider a more stringent notion of privacy compared to prior work wherein an individual's participation may shift the entire stream by a time-step. We define a new notion of edit-neighboring streams that captures this scenario. Our findings are as follows. First, we prove that on a stream of length $T$, every additive-noise mechanism incurs error $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ when required to be $\varepsilon$-DP under CO for edit-neighboring streams. This includes state-of-the-art continual counters constructed via the factorization mechanism that in the standard neighboring setting incur only polylogarithmic additive error. Second, we construct the first mechanisms with polylogarithmic additive error for our more stringent notion of privacy. We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams. Third, we show that the notion of edit-neighboring streams inhabits a `sweet-spot' in terms of generality and additive error incurred. More precisely, we show that the even more general notion of prefix-sum neighboring streams---which arises naturally in reductions for problems under CO---must incur additive error scaling as $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ for any mechanism that is $\varepsilon$-DP under continual observation. Finally, we show empirically on synthetic data that when compared with prior work, our mechanism achieves a superior trade-off between the success probability of a simple distinguishing attack, and the additive error incurred by the respective mechanisms.
- Abstract（参考訳）: 連続観測(CO)下での差分プライバシーは、センシティブな入力データストリームを使用して生成された出力がオンライン設定で発行されたときに発生するプライバシーの損失を定量化する。
本稿では、個人の参加がストリーム全体をタイムステップでシフトする前よりも、より厳密なプライバシの概念を考察する。
我々は、このシナリオをキャプチャする編集関連ストリームという新しい概念を定義します。
私たちの発見は以下の通りである。
まず、長さ$T$のストリームでは、任意の加法ノイズ機構がエラー$\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$を発生させる。
これには、標準的な隣り合う設定において、多対数加法誤差のみを発生させる因子化機構によって構築された最先端の連続カウンタが含まれる。
第二に、より厳密なプライバシー概念のための多対数付加誤差を用いた最初のメカニズムを構築する。
我々は、任意の入力ストリームとスパースストリームの両方に対して、より悪い定数係数で、プライバシという標準概念と同じ加算誤差を回復できることを示します。
第三に、編集近傍のストリームの概念は、一般化と加法誤差の点で「スイートスポット」に生息していることを示す。
より正確には、プレフィックス-sum 隣り合うストリームのより一般的な概念が-------------帰納的帰納的誤りスケーリングの問題を、連続観察の下で$\varepsilon$-DPとなる任意のメカニズムに対して$\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$として自然に減少することを示します。
最後に, 先行研究と比較した場合, 単純な判別攻撃の成功確率と, それぞれの機構によって生じる付加誤差との間には, 優れたトレードオフが達成されることを示す。
関連論文リスト
- RAPTOR: Role-Aware Private Training for Mixture-of-Experts [68.5626338219096]
RAPTORはRole-Aware Private Trainingフレームワークである。
RAPTORは共有と専門家の最適化を交互に行い、各障害を直接ターゲットする。
GLUEタスク間でのSwitch TransformerとOLMoEの微調整およびDeepSeek-VL2-Tinyの実験では、標準のDPベースラインよりも一貫した利得を示している。
論文 参考訳（メタデータ） (2026-09-04T23:16:12Z) - Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe [22.282174850598953]
一つの挿入/削除がすべての更新を切り替える、隣接した単一編集のユーザストリームについて検討する。
ランダム化されたバッファリングラッパーはサイズ$[U,2U]$のビンを出力し、シングル編集ストリームをハンミングスタイルの更新ストリームに還元する。
適応的でないハミング近傍のDP証明が適応的な入力に対して連続的なプリミティブリフトを行うときの証明定理を証明した。
論文 参考訳（メタデータ） (2026-07-08T09:44:27Z) - Computing Maximal Per-Record Leakage and Leakage-Distortion Functions for Privacy Mechanisms under Entropy-Constrained Adversaries [19.239827561129513]
本稿では,最大1レコードリーク,一次リーク・歪みトレードオフ,二重歪み最小化の3つの問題について検討する。
我々は凸性-凸性双対性を利用する効率的な交互最適化アルゴリズムを開発した。
この研究は、プライバシのリスクを監査し、認定されたメカニズムを設計するための計算フレームワークを提供する。
論文 参考訳（メタデータ） (2026-01-31T12:23:24Z) - Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency [53.98433419539793]
エッジ差分プライバシー(DP)下におけるスペクトルグラフクラスタリングの問題点について検討する。
具体的には, (i) エッジフリップによるグラフ摂動と, エッジプライバシを強制する隣接行列シャッフルを併用したグラフ摂動, (ii) 次元と複雑性の複雑さを低減するために低次元空間における加法的ガウス雑音を伴うプライベートグラフプロジェクション, (iii) 収束性を維持しながらエッジDPを確保するために反復的にガウス雑音を分散するノイズの多いパワーイテレーション手法である。
論文 参考訳（メタデータ） (2025-10-08T15:30:27Z) - Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
プライバシー制約の下では、プライベート線形回帰の複雑さは通常の共分散行列によって捉えられる。
最適率を達成するための情報重み付け回帰手法を提案する。
特に、我々の結果は、共同プライバシーは追加費用がほとんどないことを示している。
論文 参考訳（メタデータ） (2025-02-18T18:35:24Z) - Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation [3.9476868147424162]
挿入や削除を処理するすべての異なるプライベートなメカニズムは、比較的弱いイベントレベルのプライバシ定義の下でも、最低でもT1/4$の付加エラーがあることを示す。
最大フリップパンシー$w$を持つすべてのターンタイルストリームに対して、$O(sqrtw cdot polylog T)$加法誤差で異なる要素の数を連続的に出力するアイテムレベル微分プライベート機構を提案する。
論文 参考訳（メタデータ） (2023-06-11T16:54:39Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳（メタデータ） (2023-01-31T18:47:42Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
本研究は,局所的差分プライバシー(LDP)の制約の下で,集団平均の非パラメトリック,非漸近的統計的推測を行う手法を導出する。
民営化データへのアクセスのみを与えられた場合、$mustar$に対して信頼区間(CI)と時間一様信頼シーケンス(CS)を提示する。
論文 参考訳（メタデータ） (2022-02-17T16:04:49Z) - Differentially Private Community Detection for Stochastic Block Models [22.526853379896252]
本研究では,個々の接続のプライバシを保ちながら,コミュニティ検出問題について検討する。
本稿では,3つの異なる地域社会回復機構の幅広いクラスについて,関連する情報トレードオフを提示し,分析する。
論文 参考訳（メタデータ） (2022-01-31T18:59:19Z) - Frequency Estimation Under Multiparty Differential Privacy: One-shot and
Streaming [10.952006057356714]
プライバシと通信の制約下での周波数推定の基本的問題について検討し,そのデータを$k$のパーティ間で分散する。
私たちは、ローカルディファレンシャルプライバシ(LDP)と(分散)ディファレンシャルプライバシよりも一般的なマルチパーティディファレンシャルプライバシ(MDP)のモデルを採用しています。
我々のプロトコルは、より厳密な2つの制約によって許容可能な最適性(対数因子まで)を達成する。
論文 参考訳（メタデータ） (2021-04-05T08:15:20Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。