論文の概要: Differentially Private Continual Release of Histograms and Related Queries

• arxiv url: http://arxiv.org/abs/2302.11341v2
• Date: Mon, 10 Mar 2025 12:40:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:38:36.561574
• Title: Differentially Private Continual Release of Histograms and Related Queries
• Title（参考訳）: ヒストグラムと関連クエリの個人的リリース
• Authors: Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner,
• Abstract要約: 我々は、$T$行の更新を行う宇宙からのエントリを持つ$d$次元テーブルの列和をプライベートにリリースすることを研究する。 我々のメカニズムは、大量のクエリと入力ストリームに対する既存のメカニズムよりも、より優れた付加的な$ell_infty$-errorを提供する。
• 参考スコア（独自算出の注目度）: 2.5200018924833327
• License:
• Abstract: We study privately releasing column sums of a $d$-dimensional table with entries from a universe $\chi$ undergoing $T$ row updates, called histogram under continual release. Our mechanisms give better additive $\ell_\infty$-error than existing mechanisms for a large class of queries and input streams. Our first contribution is an output-sensitive mechanism in the insertions-only model ($\chi = \{0,1\}$) for maintaining (i) the histogram or (ii) queries that do not require maintaining the entire histogram, such as the maximum or minimum column sum, the median, or any quantiles. The mechanism has an additive error of $O(d\log^2 (dq^*)+\log T)$ whp, where $q^*$ is the maximum output value over all time steps on this dataset. The mechanism does not require $q^*$ as input. This breaks the $\Omega(d \log T)$ bound of prior work when $q^* \ll T$. Our second contribution is a mechanism for the turnstile model that admits negative entry updates ($\chi = \{-1, 0,1\}$). This mechanism has an additive error of $O(d \log^2 (dK) + \log T)$ whp, where $K$ is the number of times two consecutive data rows differ, and the mechanism does not require $K$ as input. This is useful when monitoring inputs that only vary under unusual circumstances. For $d=1$ this gives the first private mechanism with error $O(\log^2 K + \log T)$ for continual counting in the turnstile model, improving on the $O(\log^2 n + \log T)$ error bound by Dwork et al. [ASIACRYPT 2015], where $n$ is the number of ones in the stream, as well as allowing negative entries, while Dwork et al. [ASIACRYPT 2015] can only handle nonnegative entries ($\chi=\{0,1\}$).
• Abstract（参考訳）: 我々は、宇宙からのエントリを持つ$d$次元テーブルの列和をプライベートにリリースすることを研究する。 我々のメカニズムは、大量のクエリと入力ストリームに対する既存のメカニズムよりも、より優れた付加的な$\ell_\infty$-errorを提供する。 私たちの最初の貢献は、挿入専用モデル(\chi = \{0,1\}$)における出力に敏感なメカニズムである。 ヒストグラム; ヒストグラム; ヒストグラム (ii)最大または最小列和、中央値、または任意の量子化など、ヒストグラム全体の維持を必要としないクエリ。 このメカニズムは、$O(d\log^2 (dq^*)+\log T)$wpという加算誤差を持つ。 このメカニズムは入力として$q^*$を必要としない。 これは$q^* \ll T$のときの$\Omega(d \log T)$境界を破る。 第二の貢献は、負のエントリ更新(\chi = \{-1, 0,1\}$)を受け入れるターンタイルモデルのメカニズムである。 このメカニズムは、$O(d \log^2 (dK) + \log T)$wpという加算誤差を持ち、$K$は2つの連続するデータ行の回数が異なり、そのメカニズムは入力として$K$を必要としない。 これは、異常な状況下でのみ異なる入力を監視する場合に有用である。 これは$d=1$に対して、エラー$O(\log^2 K + \log T)$をターンタイルモデルで連続カウントするための最初のプライベートメカニズムを与える。$O(\log^2 n + \log T)$ error bound by Dwork et al [ASIACRYPT 2015], where $n$ is the number of the stream, and allowing negative entry, while Dwork et al [ASIACRYPT 2015] can handle non negative entry(\chi=\{0,1\}$)。

関連論文リスト

• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。 我々はアルゴリズムをほぼ一致する下界で補完する。
  論文  参考訳（メタデータ） (2025-02-20T18:32:02Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
  正確な平衡は$O(fracln Kepsilon)$クエリの代わりに$O(fracln Kepsilon)$から効率的に計算できることを示す。 我々は下界に対する新しい手法を導入し、任意の$epsilon leq 1 / (cK4)$に対して$tildeOmega(frac1Kepsilon)$の下位境界を得ることができる。
  論文  参考訳（メタデータ） (2023-04-25T12:42:59Z)
• Fast Attention Requires Bounded Entries [19.17278873525312]
  内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。 行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。 このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
  論文  参考訳（メタデータ） (2023-02-26T02:42:39Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Chi-square and normal inference in high-dimensional multi-task regression [7.310043452300736]
  本稿では,Multi-Task(MT)線形モデルにおける未知の係数行列$B*$サイズ$ptimes T$に対するカイ二乗法および正規手法を提案する。
  論文  参考訳（メタデータ） (2021-07-16T11:19:49Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
  最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。 最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。 これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
  論文  参考訳（メタデータ） (2020-04-16T22:57:06Z)

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

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