論文の概要: Optimal Pure Differentially Private Sparse Histograms in Near-Linear Deterministic Time

• arxiv url: http://arxiv.org/abs/2507.17017v1
• Date: Tue, 22 Jul 2025 21:17:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-24 22:33:14.77426
• Title: Optimal Pure Differentially Private Sparse Histograms in Near-Linear Deterministic Time
• Title（参考訳）: 近距離決定論的時間における最適純分別スパースヒストグラム
• Authors: Florian Kerschbaum, Steven Lee, Hao Wu,
• Abstract要約: そこで本研究では,純微分プライベートなスパースヒストグラムを,サイズ$d gg n$の領域から引き出された参加者に対してリリースするアルゴリズムを提案する。 我々の手法は最適な$ell_infty$-estimation誤差を達成し、ワードRAMモデルで厳密に$O(n ln ln d)$時間で実行します。
• 参考スコア（独自算出の注目度）: 27.86810658667445
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We introduce an algorithm that releases a pure differentially private sparse histogram over $n$ participants drawn from a domain of size $d \gg n$. Our method attains the optimal $\ell_\infty$-estimation error and runs in strictly $O(n \ln \ln d)$ time in the word-RAM model, thereby improving upon the previous best known deterministic-time bound of $\tilde{O}(n^2)$ and resolving the open problem of breaking this quadratic barrier (Balcer and Vadhan, 2019). Central to our algorithm is a novel private item blanket technique with target-length padding, which transforms the approximate differentially private stability-based histogram algorithm into a pure differentially private one.
• Abstract（参考訳）: そこで本研究では,純微分プライベートなスパースヒストグラムを,サイズ$d \gg n$の領域から引き出された参加者に対してリリースするアルゴリズムを提案する。 我々の手法は最適な$\ell_\infty$-estimation誤差を達成し、ワードRAMモデルにおいて厳密な$O(n \ln \ln d)$時間で動作し、これにより以前の最もよく知られた決定論的時間境界である$\tilde{O}(n^2)$を改良し、この二次障壁を破る開放的な問題を解消する(Balcer and Vadhan, 2019)。 我々のアルゴリズムの中心は、ターゲット長のパディングを持つ新しいプライベートアイテム毛布技術であり、近似的にプライベートな安定性に基づくヒストグラムアルゴリズムを純粋にプライベートなものに変換する。

関連論文リスト

• Private Continual Counting of Unbounded Streams [11.941250828872189]
  入力サイズ$n$が予め分かっていないような非有界な環境では、差分プライベートな連続数え上げの問題について検討する。 一般的な2倍のトリックを使用すると、$n$の知識は避けられるが、最適でないエラーと非滑らかなエラーにつながる。 先行研究で研究された関数 $frac1sqrt1-z$ の対数摂動に基づく新しい行列分解を導入する。
  論文  参考訳（メタデータ） (2025-06-17T23:09:53Z)
• 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)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More [5.893651469750359]
  マルチウェイカットと最小$k$cutのためのエッジ微分プライベートアルゴリズムを導入する。 最小$k$-cut問題に対して、指数的メカニズムと近似$k$-cutの数の有界性を組み合わせた別のアプローチを用いる。
  論文  参考訳（メタデータ） (2024-07-09T14:46:33Z)
• Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
  重み付き勾配を持つ差分プライベート凸最適化(DP-SCO)の問題を考察し、一様境界ではなく、サンプル関数のリプシッツ定数上の$ktextth$-momentを仮定する。 Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon) 1 の誤差を達成し、重み付け設定における第1次最適率(対数係数まで)を得るための新しい還元ベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2024-06-04T21:26:29Z)
• Almost linear time differentially private release of synthetic graphs [6.076406622352115]
  本稿では,指数関数的メカニズムから,ほぼ線形時間と空間のアルゴリズムをサンプリングする。 直接的な結果として、差分入力を指数関数的に大きな$G$mエッジとして定義する。 これらは合成グラフを公開するためのプライベートファーストのプライベートアルゴリズムである。
  論文  参考訳（メタデータ） (2024-06-04T09:44:24Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。 我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
  論文  参考訳（メタデータ） (2022-10-27T05:11:00Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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