論文の概要: Tight Lower Bounds for Differentially Private Continual Counting

• arxiv url: http://arxiv.org/abs/2609.17650v2
• Date: Thu, 17 Sep 2026 18:31:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-21 18:40:16.689881
• Title: Tight Lower Bounds for Differentially Private Continual Counting
• Title（参考訳）: 個人別連続計数のためのタイトな下界
• Abstract要約: 固定された$0 varepsilon le 1$ に対して、最悪のケースでは$(log2 n)$、平均と最大で$(log3 n)$の2乗誤差では$(log2 n)$ が成立する。 我々の下位境界はラプラスノイズでインスタンス化されたバイナリツリー機構と一致し、純粋微分プライバシーと近似微分プライバシーの両方の下でその最適性を確立する。
• 参考スコア（独自算出の注目度）: 0.9208007322096535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has remained unresolved since its introduction. We resolve this question. For fixed $0 < \varepsilon \le 1$, we prove asymptotically tight lower bounds of $Ω(\log^2 n)$ for worst-case expected $\ell_\infty$ error and $Ω(\log^3 n)$ for mean and maximum per-coordinate expected squared error. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. The same lower bounds hold under approximate differential privacy whenever $δ\le n^{-c}$, for any fixed $c>0$. Our lower bounds match the Binary Tree Mechanism instantiated with Laplace noise, establishing its asymptotic optimality under both pure differential privacy and approximate differential privacy in the standard regime of $δ\ll1/n$. Our proof uses a single hard distribution with a bounded exponential score on a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.
• Abstract（参考訳）: バイナリツリーメカニズムは、微分的にプライベートな連続的なカウントのための標準的なアルゴリズムであるが、純粋な微分プライバシーの下での漸近的最適性は、導入以来未解決のままである。 私たちはこの問題を解決します。 固定された$0 < \varepsilon \le 1$ に対して、最悪の場合の$\ell_\infty$ と$Ω(\log^3 n) の平均と最大の2乗誤差に対する $Ω(\log^2 n) の漸近的に厳しい下界を証明する。 これらの境界は、ストリーム全体が事前に利用可能である場合でも、任意のメカニズムを保持する。 同じ下界は、任意の固定された$c>0$に対して$δ\le n^{-c}$のとき、近似微分プライバシーの下で保持される。 我々の下限は、Laplaceノイズでインスタンス化されたBinary Treeメカニズムと一致し、その漸近的最適性は、純粋な差分プライバシーと、標準のδ\ll1/n$の差分プライバシーの両方の下で確立される。 我々の証明は、木上の有界指数スコアを持つ単一の硬分布を用いる。 スコアの簡単な変更により、同じフレームワークが3つのエラー測度すべてに対して厳密な下限を確立することができる。

関連論文リスト

• Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures [0.40611352512781873]
  我々は、$[0,1]d$の$n$ポイントに対して、$varepsilon$-微分的にプライベートな合成測度を研究する。 サンプリングや人口分布の仮定なしに最悪のデータモデルを考える。
  論文  参考訳（メタデータ） (2026-09-15T05:27:33Z)
• The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting [18.604881105488513]
  連続的数え上げのための微分プライベートなメカニズムはすべて、予想される$ell_infty$ error $(log3/2 n)$を発生しなければならないことを示す。 また、線形クエリに対して、遺伝的不一致とprivate $ell_infty$エラーを最大で分離する。
  論文  参考訳（メタデータ） (2026-07-01T12:38:33Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Approximate Differential Privacy of the $\ell_2$ Mechanism [52.61055173572399]
  我々は、近似微分プライバシーの下で、$d$次元統計量と有界$ell$感度を計算するための$ell$メカニズムについて研究する。 プライバシパラメータの範囲で、$ell$メカニズムはLaplaceやGaussianのメカニズムよりも低いエラーを得る。
  論文  参考訳（メタデータ） (2025-02-21T20:56:34Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。 誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
  論文  参考訳（メタデータ） (2024-01-17T09:23:25Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma [10.176795938619417]
  統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。 フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
  論文  参考訳（メタデータ） (2022-05-17T17:55:10Z)
• 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)
• A bounded-noise mechanism for differential privacy [3.9596068699962323]
  ベクトル $vecx(i) の平均 $frac1nsum_i=1n vecx(i)$ を [0,1]k$ で出力し、任意の $vecx(i)$ に対してプライバシーを保持します。 我々は、ほとんどの値$delta$に対して最適な$ell_infty$エラーを持つ$(epsilon,delta)$-privateメカニズムを示す。
  論文  参考訳（メタデータ） (2020-12-07T16:03:21Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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