論文の概要: Strict Optimality of Frequency Estimation Under Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2603.11523v1
• Date: Thu, 12 Mar 2026 04:16:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-13 14:46:25.861069
• Title: Strict Optimality of Frequency Estimation Under Local Differential Privacy
• Title（参考訳）: 局所微分プライバシー下における周波数推定の厳密な最適性
• Authors: Mingen Pan,
• Abstract要約: 本稿では、局所的な差分プライバシー下での周波数推定精度の厳密な最適性を確立する。 周波数推定器は, 対称かつ極端な構成であり, 最適化された値に等しい一定のサポートサイズで, 最大精度を実現するのに十分であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper establishes the strict optimality in precision for frequency estimation under local differential privacy (LDP). We prove that a frequency estimator with a symmetric and extremal configuration, and a constant support size equal to an optimized value, is sufficient to achieve maximum precision. Furthermore, we derive that the communication cost of such an optimal estimator can be as low as $\log_2(\frac{d(d-1)}{2}+1)$, where $d$ denotes the dictionary size, and propose an algorithm to generate this optimal estimator. In addition, we introduce a modified Count-Mean Sketch and demonstrate that it is practically indistinguishable from theoretical optimality with a sufficiently large dictionary size (e.g., $d=100$ for a privacy factor of $ε= 1$). We compare existing methods with our proposed optimal estimator to provide selection guidelines for practical deployment. Finally, the performance of these estimators is evaluated experimentally, showing that the empirical results are consistent with our theoretical derivations.
• Abstract（参考訳）: 本稿では、局所微分プライバシー(LDP)の下での周波数推定精度の厳密な最適性を確立する。 周波数推定器は, 対称かつ極端な構成であり, 最適化された値に等しい一定のサポートサイズで, 最大精度を実現するのに十分であることを示す。 さらに、このような最適推定器の通信コストは$\log_2(\frac{d(d-1)}{2}+1)$と低くなり、$d$は辞書のサイズを表し、この最適推定器を生成するアルゴリズムを提案する。 さらに、修正されたCount-Mean Sketchを導入し、十分な辞書サイズ(ε=1$のプライバシ係数に対して$d=100$など)で理論的最適性とは事実上区別できないことを示した。 本稿では,既存手法と最適推定器を比較し,実用的展開のための選択ガイドラインを提供する。 最後に、これらの推定器の性能を実験的に評価し、実験結果が我々の理論的導出と一致していることを示す。

関連論文リスト

• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization [57.179679246370114]
  既存の手法の潜在的な制限は、ステップサイズが提案されない限り、ほとんどの摂動推定器に固有のバイアスである。 本稿では, 良好な構成を維持しつつ, バイアスを排除した非バイアス勾配スケーリング推定器のファミリーを提案する。
  論文  参考訳（メタデータ） (2025-10-22T18:25:43Z)
• Minimax Optimal Kernel Two-Sample Tests with Random Features [6.747832388017275]
  本研究では、ランダムフーリエ特徴量(RFF)近似に基づくスペクトル規則化2サンプル試験を提案する。 RFFの近似順序が十分に大きい場合、提案した試験が最小限最適であることを示す。 そこで本研究では,正規化パラメータを選択するためのデータ適応型戦略を用いて,提案手法の実用的実装可能な置換型バージョンを開発する。
  論文  参考訳（メタデータ） (2025-02-28T06:12:00Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood [33.051282474765955]
  我々の推定器はPML(Pop Profile-maximum-likelihood)に基づいており、様々な対称特性を推定するのに最適なサンプルである。 この結果は、達成可能な時間で$epsilon gg n-1/4$の前の最高精度閾値を改善する。
  論文  参考訳（メタデータ） (2022-10-13T04:52:15Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
  論文  参考訳（メタデータ） (2022-05-05T06:43:46Z)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  非最適化近似問題を考える。 本稿では,最優先計算を保証するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-04-11T09:37:04Z)
• Entropic estimation of optimal transport maps [15.685006881635209]
  厳密な有限サンプル保証付き$mathbbRd$上の2つの分布間の最適写像を推定する手法を開発する。 我々は,Sinkhornのアルゴリズムを用いて,推定器の計算が容易であることを示す。
  論文  参考訳（メタデータ） (2021-09-24T14:57:26Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。 本手法は既存の不一致対策よりも高いロバスト性を実現する。
  論文  参考訳（メタデータ） (2020-06-13T06:09:27Z)
• Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
  プロジェクション・ソリッドスタイン(PRW)は、ワッサーシュタイン・プロジェクション(WPP)のロバストな変種であることを示す。 本稿では,PRW距離の計算への第一歩として,その理論と実データに関する実験の関連について述べる。
  論文  参考訳（メタデータ） (2020-06-12T20:40:22Z)

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

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