論文の概要: Skirting Additive Error Barriers for Private Turnstile Streams

• arxiv url: http://arxiv.org/abs/2602.10360v1
• Date: Tue, 10 Feb 2026 23:10:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-12 21:44:01.334033
• Title: Skirting Additive Error Barriers for Private Turnstile Streams
• Title（参考訳）: 自家用旋回流用加振型エラーバリア
• Authors: Anders Aamand, Justin Y. Chen, Sandeep Silwal,
• Abstract要約: 本研究では,ターンタイルストリームにおける各項目数の個人的連続的解放について検討した。 長さ'23のストリームの場合、空間制限がなくても$(T1/4)$の加算誤差が必要である。 加法的インプハンド乗算誤差の両方で推定値の出力が許された場合、この誤差の下限を回避できることが示される。
• 参考スコア（独自算出の注目度）: 15.938776246823275
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study differentially private continual release of the number of distinct items in a turnstile stream, where items may be both inserted and deleted. A recent work of Jain, Kalemaj, Raskhodnikova, Sivakumar, and Smith (NeurIPS '23) shows that for streams of length $T$, polynomial additive error of $Ω(T^{1/4})$ is necessary, even without any space restrictions. We show that this additive error lower bound can be circumvented if the algorithm is allowed to output estimates with both additive \emph{and multiplicative} error. We give an algorithm for the continual release of the number of distinct elements with $\text{polylog} (T)$ multiplicative and $\text{polylog}(T)$ additive error. We also show a qualitatively similar phenomenon for estimating the $F_2$ moment of a turnstile stream, where we can obtain $1+o(1)$ multiplicative and $\text{polylog} (T)$ additive error. Both results can be achieved using polylogarithmic space whereas prior approaches use polynomial space. In the sublinear space regime, some multiplicative error is necessary even if privacy is not a consideration. We raise several open questions aimed at better understanding trade-offs between multiplicative and additive error in private continual release.
• Abstract（参考訳）: 本研究では,各項目を挿入・削除できるターンタイルストリームにおいて,各項目の個数の個人的連続的リリースについて検討する。 Jain, Kalemaj, Raskhodnikova, Sivakumar, Smith (NeurIPS '23) の最近の研究は、長さ$T$のストリームに対して、$Ω(T^{1/4})$の多項式加法誤差が空間制限なしで必要であることを示している。 この加算誤差の下限は、加法的 \emph{and multiplicative} 誤差の両方で推定値を出力することが許された場合、回避可能であることを示す。 我々は、$\text{polylog} (T)$ multiplicative と $\text{polylog}(T)$ additive error で異なる要素の数を連続的に解放するアルゴリズムを提供する。 ここでは1+o(1)$乗算と$\text{polylog} (T)$加法誤差を得ることができる。 どちらの結果も多対数空間を用いて達成できるが、事前のアプローチでは多項式空間を用いる。 サブ線形空間では、プライバシーが考慮されない場合でも、乗法誤差が必要になる。 プライベートな継続的リリースにおいて、乗法的エラーと加法的エラーの間のトレードオフをよりよく理解することを目的とした、いくつかのオープンな質問を提起する。

関連論文リスト

• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。 本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。 ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
  論文  参考訳（メタデータ） (2025-05-29T17:21:20Z)
• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  我々は、$k$-core分解のための$eps$-edge差分秘密アルゴリズムが乗算誤差なしでコア数を出力し、$O(textlog(n)/eps)$加法誤差を示す。 これは乗法誤差における2の因子による以前の作業を改善すると同時に、ほぼ最適加法誤差を与える。
  論文  参考訳（メタデータ） (2023-12-12T20:09:07Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。 当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• 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)
• List-Decodable Covariance Estimation [1.9290392443571387]
  共分散推定アルゴリズムを初めて提案する。 この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
  論文  参考訳（メタデータ） (2022-06-22T09:38:06Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。 局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
  論文  参考訳（メタデータ） (2021-05-31T14:41:40Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)

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

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