論文の概要: Efficient derandomization of differentially private counting queries

• arxiv url: http://arxiv.org/abs/2510.16959v2
• Date: Tue, 21 Oct 2025 08:25:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:11.926907
• Title: Efficient derandomization of differentially private counting queries
• Title（参考訳）: 微分プライベートカウントクエリの効率的なデランドマイズ
• Authors: Surendra Ghentiyala,
• Abstract要約: 2020年国勢調査の異なるプライバシーは90テラバイトのランダムネス[GL20]を必要とした。 これは、$mathcalP, dots, MathcalP_d$の述語を満たすデータセットにエントリの数を出力するタスクである。 彼らはかなり驚くべき事実を示し、$varepsilon-differentially private mechanism for one counting query requires $O(log d)$ bits of in expectation。 ここでは、時間的メカニズムを示します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Differential privacy for the 2020 census required an estimated 90 terabytes of randomness [GL20], an amount which may be prohibitively expensive or entirely infeasible to generate. Motivated by these practical concerns, [CSV25] initiated the study of the randomness complexity of differential privacy, and in particular, the randomness complexity of $d$ counting queries. This is the task of outputting the number of entries in a dataset that satisfy predicates $\mathcal{P}_1, \dots, \mathcal{P}_d$ respectively. They showed the rather surprising fact that though any reasonably accurate, $\varepsilon$-differentially private mechanism for one counting query requires $1-O(\varepsilon)$ bits of randomness in expectation, there exists a fairly accurate mechanism for $d$ counting queries which requires only $O(\log d)$ bits of randomness in expectation. The mechanism of [CSV25] is inefficient (not polynomial time) and relies on a combinatorial object known as rounding schemes. Here, we give a polynomial time mechanism which achieves nearly the same randomness complexity versus accuracy tradeoff as that of [CSV25]. Our construction is based on the following simple observation: after a randomized shift of the answer to each counting query, the answer to many counting queries remains the same regardless of whether we add noise to that coordinate or not. This allows us to forgo the step of adding noise to the result of many counting queries. Our mechanism does not make use of rounding schemes. Therefore, it provides a different -- and, in our opinion, clearer -- insight into the origins of the randomness savings that can be obtained by batching $d$ counting queries.
• Abstract（参考訳）: 2020年国勢調査の異なるプライバシーは90テラバイトのランダムネス[GL20]を必要とした。 これらの実践的懸念に動機づけられた[CSV25]は、差分プライバシーのランダム性複雑性、特に$d$のクエリのランダム性複雑性の研究を開始した。 これは、それぞれ$\mathcal{P}_1, \dots, \mathcal{P}_d$を満たすデータセットにエントリの数を出力するタスクである。 彼らは、$\varepsilon$-differentially private mechanism for one counting query requires $1-O(\varepsilon)$ bits of randomness in expectationという驚くべき事実を示した。 CSV25] のメカニズムは非効率(多項式時間ではない)であり、丸めスキームとして知られる組合せ対象に依存している。 ここでは[CSV25]とほぼ同じランダム性複雑性と精度トレードオフを実現する多項式時間機構を提案する。 我々の構成は以下の単純な観察に基づいており、各カウントクエリに対する解のランダムなシフトの後、その座標にノイズを加えるかどうかに関わらず、多くのカウントクエリに対する解は同じままである。 これにより、多くのカウントクエリの結果にノイズを追加するステップを回避できます。 私たちのメカニズムは丸めのスキームを使わない。 したがって、クエリを$d$のバッチで取得することで得られるランダムな保存の起源に関する洞察を、別の - そして私たちの意見では -- より明確にします。

関連論文リスト

• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph [45.975805184376036]
  局所的な差分プライバシーを満足するアルゴリズムを記述し、個人に対して$tildeO(k3/2)$非適応クエリを実行する。 また、Scheff'eグラフをダブする新しいオブジェクトを導入し、$Q$の分散間の差の構造をキャプチャする。
  論文  参考訳（メタデータ） (2025-09-19T17:41:15Z)
• The Role of Randomness in Stability [20.718747268949112]
  学習における安定性という2つの重要な概念,すなわち複製可能性と差分プライバシーのランダム性複雑性について検討する。 安定に対する弱強強化定理(英語版)を証明し、タスクのランダム性複雑性は最適な複製確率によって厳しく制御される。
  論文  参考訳（メタデータ） (2025-02-11T23:06:43Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• On the Fine-Grained Query Complexity of Symmetric Functions [4.956977275061968]
  本稿では、Watrous予想のきめ細かいバージョンについて考察する。 確率が任意に1/2ドルに近いランダム化および量子化アルゴリズムを含む。
  論文  参考訳（メタデータ） (2023-09-20T13:04:45Z)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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