論文の概要: The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

• arxiv url: http://arxiv.org/abs/2607.00876v1
• Date: Wed, 01 Jul 2026 12:38:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-02 19:56:07.892905
• Title: The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting
• Title（参考訳）: 二分木機構は近似微分的連続数に最適である
• Abstract要約: 連続的数え上げのための微分プライベートなメカニズムはすべて、予想される$ell_infty$ error $(log3/2 n)$を発生しなければならないことを示す。 また、線形クエリに対して、遺伝的不一致とprivate $ell_infty$エラーを最大で分離する。
• 参考スコア（独自算出の注目度）: 18.604881105488513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Private continual counting is a fundamental problem in differential privacy: given a binary stream of length $n$, where each $1$ corresponds to the contribution of one individual, the goal is to release all running counts while protecting the privacy of each individual. The standard algorithm is the binary tree mechanism, whose Gaussian-noise variant achieves expected $\ell_\infty$ error proportional to $\log^{3/2} n$ for approximate differential privacy. Whether this dependence on the stream length is necessary has remained a central open problem. In this work, we resolve the dependence on $n$ by proving that every differentially private mechanism for continual counting must incur expected $\ell_\infty$ error $Ω(\log^{3/2} n)$. This shows that the binary tree mechanism is asymptotically optimal in the approximate-DP setting. As a consequence, we also obtain a largest-possible separation between hereditary discrepancy and private $\ell_\infty$ error for linear queries, showing that the known general upper bound in terms of hereditary discrepancy has the optimal dependence on the number of queries.
• Abstract（参考訳）: プライベートな連続カウントは、差分プライバシの基本的な問題である: 長さ$n$のバイナリストリームが与えられた場合、1ドルが1人の個人の貢献に対応する場合、その目標は、各個人のプライバシを保護しながら、実行中のカウントをすべてリリースすることである。 標準的なアルゴリズムは二分木機構であり、ガウスノイズの変種は予想される$\ell_\infty$エラーを近似微分プライバシーのために$\log^{3/2} n$に比例する。 このストリーム長への依存が必要とされるかどうかは、依然として中心的なオープンな問題である。 この研究では、連続的な数え上げのための微分プライベートなメカニズムはすべて、期待される$\ell_\infty$ error $Ω(\log^{3/2} n)$を発生しなければならないことを証明して、$n$への依存を解消する。 このことは、二分木機構が近似DP設定において漸近的に最適であることを示している。 その結果、線形クエリに対して、遺伝的不一致とプライベート$\ell_\infty$エラーを最大に分離し、遺伝的不一致という観点で既知の一般境界がクエリ数に最適に依存することを示す。

関連論文リスト

• Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy [1.8549313085249317]
  本稿では,二元仮説テストのための局所微分プライベートなメカニズムとして,$varepsilon$-locally differentially private mechanism の最適設計について検討する。 われわれの結果は、プライバシー体制を超えて、完全なプライバシー範囲の正確な最適化を効率的に計算し、特徴づけることを可能にする。
  論文  参考訳（メタデータ） (2026-06-05T16:41:31Z)
• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。 本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。 このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
  論文  参考訳（メタデータ） (2026-02-12T17:49:07Z)
• Tight Differentially Private PCA via Matrix Coherence [12.864472925970242]
  特異値分解と標準摂動機構に基づく単純で効率的なアルゴリズムが、プライベートランク-r$近似を返すことを示す。 私たちの推定器は、いくつかの体制において、芸術の状態を著しく上回ります。 我々は、同様の挙動がグラフの植込み問題を含む他の構造化モデルに対して成り立つと推測する。
  論文  参考訳（メタデータ） (2025-10-30T16:47:26Z)
• Optimal Best Arm Identification under Differential Privacy [8.321992395325912]
  BAI(Best Arm Identification)アルゴリズムは、適応的な臨床試験やユーザリサーチなど、データに敏感なアプリケーションにデプロイされる。 本研究では,ベルヌーイ分布に対するグローバル微分プライバシー(DP)の下での固定信頼度BAIの問題について検討する。 提案アルゴリズムは,既存の$delta$correctおよび$epsilon$-global DP BAIアルゴリズムより,$epsilon$の異なる値に対して優れている。
  論文  参考訳（メタデータ） (2025-10-20T09:46:09Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  一般化ガウス機構(英語版)を考察し、ある$beta geq 1$に対して$e-frac| x |sigmabeta $ に比例した付加雑音項 $x$ をサンプリングする。 GGメカニズムとその変種に対するプライバシ会計は独立であり、プライバシ会計の計算コストを大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2025-06-14T15:49:25Z)
• Approximate Differential Privacy of the $\ell_2$ Mechanism [52.61055173572399]
  我々は、近似微分プライバシーの下で、$d$次元統計量と有界$ell$感度を計算するための$ell$メカニズムについて研究する。 プライバシパラメータの範囲で、$ell$メカニズムはLaplaceやGaussianのメカニズムよりも低いエラーを得る。
  論文  参考訳（メタデータ） (2025-02-21T20:56:34Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• Near-Universally-Optimal Differentially Private Minimum Spanning Trees [0.0]
  我々は、最小スパンニングツリーを概解する単純な微分プライベートなメカニズムが、$ell_infty$ 近傍関係に対する普遍的最適性という意味では、ほぼ最適であることを示す。 我々は MST の指数的機構を時間内に実装し、これは $ell_infty$ と $ell_infty$ の近傍関係の両方に対して普遍的な準最適性をもたらすことを示した。
  論文  参考訳（メタデータ） (2024-04-23T13:39:25Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)

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

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