論文の概要: A Fast Gaussian Mechanism under Continual Observation, with Applications

• arxiv url: http://arxiv.org/abs/2606.11760v1
• Date: Wed, 10 Jun 2026 07:36:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-18 14:37:43.08514
• Title: A Fast Gaussian Mechanism under Continual Observation, with Applications
• Title（参考訳）: 連続観測における高速ガウス機構とその応用
• Authors: Rasmus Pagh, Sia Sejer,
• Abstract要約: 更新時に$k$次元ベクトルをプライベートにリリースする問題について検討する。 我々は$A(1),dots,A(T)$の近似を、等級$textpolylog(T)$の付加雑音でリリースする。 本稿では,2つのデータ管理アプリケーションについて述べる。
• 参考スコア（独自算出の注目度）: 10.345196226375455
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of privately releasing a $k$-dimensional vector under updates: Starting with a zero vector, at times $t_1, t_2,\dots$ the vector is updated by adding $x^{(1)}, x^{(2)},\dots$, respectively. For positive integers $T$, $k$ we model the updates as a data set $\{(t_i, x^{(i)})\}_i$, where $t_i \in [T]$ and $x^{(i)} \in B_k$ (the $k$-dimensional unit ball). Two such data sets are said to be neighboring if their symmetric difference has size at most $1$. The continual release consists of the sum $A^{(t)} = \sum_{i \; : \; t_i \leq t} x^{(i)}$ for each time step $t=1,\dots,T$. Classical continual release techniques allow us to release an approximation of $A^{(1)},\dots,A^{(T)}$ with additive noise of magnitude $\text{polylog}(T)$, computed in time $O(kT)$, even in the on-line, adaptive case where data is continually revealed for the current time step. Motivated by private sketching techniques, we consider the setting where only a \emph{subset} of entries in $A^{(t)}$ need to be released at time step $t$. Our new result is that it is possible to sample any desired entry in a given noise vector in \emph{constant time} while reproducing exactly the distribution of the binary tree mechanism with Gaussian noise. The improvement on the known time bound of $O(\log T)$ comes from a new data structure that allows us to sample a new noise value with the correct correlations in constant time using Brownian bridges. We present two data management applications, of independent interest, that use our technique in conjunction with differentially private CountSketches: 1) A dynamic data structure for orthogonal range counting queries with a better privacy/accuracy/space trade-off than previous data structures, and 2) Join size estimation, where in addition we show improved high-probability bounds.
• Abstract（参考訳）: ゼロベクトルから開始すると、それぞれ$x^{(1)}, x^{(2)},\dots$, $x^{(1)}, x^{(2)},\dots$が更新される。 正の整数に対して$T$, $k$ は、更新をデータセット $\{(t_i, x^{(i)})\}_i$ としてモデル化するが、$t_i \in [T]$ と $x^{(i)} \in B_k$ ($k$次元単位球)である。 そのような2つのデータセットは、それらの対称差が少なくとも1ドルという大きさを持つ場合、隣り合うと言われる。 A^{(t)} = \sum_{i \; : \; t_i \leq t} x^{(i)}$ は各時間ステップ $t=1,\dots,T$ である。 A^{(1)},\dots,A^{(T)}$, $\text{polylog}(T)$, computed in time $O(kT)$, in the on-line, Adaptive case, where data is continuously revealed for the current time step。 プライベートなスケッチ技術によって動機付けられ、$A^{(t)}$のエントリの \emph{subset} のみを時間ステップ$t$でリリースする必要がある設定を考える。 我々の新しい結果は、ガウス雑音による二分木機構の分布を正確に再現しながら、所与のノイズベクトルの任意の入力を \emph{constant Time} でサンプリングすることが可能である。 既知時間境界の$O(\log T)$の改善は、ブラウン橋を用いて一定の時間内に正しい相関関係を持つ新しいノイズ値のサンプリングを可能にする新しいデータ構造から得られる。 我々は、独立性のある2つのデータ管理アプリケーションを提示し、我々の技術と微分プライベートなCountSketchesを併用する。 1) 従来のデータ構造よりも優れたプライバシー/精度/空間トレードオフを有するクエリを直交範囲でカウントする動的データ構造 2) 結合サイズ推定では, 高確率境界が改良された。

関連論文リスト

• Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
  ヘビーテール付きバンディットには、ヘビーテール付きノイズ、トランケーション、中央値の2つの基本戦略が導入されている。 本稿では,オンラインミラー降下フレームワークに基づくEmphone-passアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-03-01T09:41:45Z)
• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• Profile Reconstruction from Private Sketches [13.929335175122265]
  $mathcalD$から$n$のアイテムの多重集合が与えられたとき、強調される再構成問題は、$t = 0, 1, dots, n$ に対して、$mathcalD$ のアイテムの分数 $vecf[t]$ を正確に $tfty 倍と見積もることである。 分散空間制約付き環境での個人プロファイル推定について検討し,マルチセットの更新可能なプライベートスケッチを維持したいと考える。 LPベースの手法の高速化方法を示します
  論文  参考訳（メタデータ） (2024-06-03T09:51:28Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Dynamic Ranking and Translation Synchronization [3.946250592943285]
  本研究では, エン翻訳同期問題の動的設定への拡張について検討する。 そこで我々は,2つの推定器を提案し,その1つはスムーズネスの最小二乗法に基づくものであり,もう1つは適切な滑らかさ演算子の低周波固有空間への射影に基づくものである。
  論文  参考訳（メタデータ） (2022-07-04T14:45:12Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed Data [22.233705161499273]
  我々は$epsilon$-DPモデルにおける$ell_1$-norm線形回帰に注目した。 我々は高い確率で$tildeO(sqrtfracdnepsilon)$の上限を達成することができることを示す。 我々のアルゴリズムは、データの各座標が有界なモーメントを持つような、よりリラックスしたケースにも拡張できる。
  論文  参考訳（メタデータ） (2022-01-10T08:17:05Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)

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

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