論文の概要: Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis

• arxiv url: http://arxiv.org/abs/2412.14396v1
• Date: Wed, 18 Dec 2024 23:11:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-20 13:31:46.289437
• Title: Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
• Title（参考訳）: Fingerprinting Codes with Geometry: プライベートクエリリリースとアダプティブデータ分析のための低境界の改善
• Authors: Xin Lyu, Kunal Talwar,
• Abstract要約: 本稿では,フィンガープリント方式の下位境界の証明のための一般的なフレームワークを提案する。 宇宙上の任意の適応的数え上げクエリにQ$$$mathcalX$ to accuracy $alpha$ needs $Omega(fracsqrt log|mathcalX| log (1/delta) log Qvarepsilonalpha2)$ sample, matching known upper bounds to constants。
• 参考スコア（独自算出の注目度）: 25.476062424924713
• License:
• Abstract: Fingerprinting codes are a crucial tool for proving lower bounds in differential privacy. They have been used to prove tight lower bounds for several fundamental questions, especially in the ``low accuracy'' regime. Unlike reconstruction/discrepancy approaches however, they are more suited for query sets that arise naturally from the fingerprinting codes construction. In this work, we propose a general framework for proving fingerprinting type lower bounds, that allows us to tailor the technique to the geometry of the query set. Our approach allows us to prove several new results, including the following. First, we show that any (sample- and population-)accurate algorithm for answering $Q$ arbitrary adaptive counting queries over a universe $\mathcal{X}$ to accuracy $\alpha$ needs $\Omega(\frac{\sqrt{\log |\mathcal{X}|}\cdot \log Q}{\alpha^3})$ samples, matching known upper bounds. This shows that the approaches based on differential privacy are optimal for this question, and improves significantly on the previously known lower bounds of $\frac{\log Q}{\alpha^2}$ and $\min(\sqrt{Q}, \sqrt{\log |\mathcal{X}|})/\alpha^2$. Second, we show that any $(\varepsilon,\delta)$-DP algorithm for answering $Q$ counting queries to accuracy $\alpha$ needs $\Omega(\frac{\sqrt{ \log|\mathcal{X}| \log(1/\delta)} \log Q}{\varepsilon\alpha^2})$ samples, matching known upper bounds up to constants. Our framework allows for proving this bound via a direct correlation analysis and improves the prior bound of [BUV'14] by $\sqrt{\log(1/\delta)}$. Third, we characterize the sample complexity of answering a set of random $0$-$1$ queries under approximate differential privacy. We give new upper and lower bounds in different regimes. By combining them with known results, we can complete the whole picture.
• Abstract（参考訳）: フィンガープリントコードは、差分プライバシーの低い境界を証明するための重要なツールである。 これらはいくつかの基本的な問題、特に『低い精度』の体制において、厳密な下限を証明するために使われてきた。 しかし、再構築/離散化アプローチとは異なり、指紋コードの構築から自然に生じるクエリセットにはより適している。 本研究では,フィンガープリント方式の下位境界を証明するための一般的なフレームワークを提案する。 このアプローチによって、以下のものを含む、いくつかの新しい結果が証明できます。 まず、ある宇宙上の任意のアダプティブカウンティングクエリにQ$$$\mathcal{X}$から精度$\alpha$が$\Omega(\frac{\sqrt{\log |\mathcal{X}|}\cdot \log Q}{\alpha^3})$サンプルに一致することを示す。 このことは、微分プライバシーに基づくアプローチがこの問題に最適であることを示し、以前に知られていた$\frac{\log Q}{\alpha^2}$と$\min(\sqrt{Q}, \sqrt{\log |\mathcal{X}|})/\alpha^2$の下位境界で大幅に改善されることを示している。 次に、$Q$を精度にカウントする$(\varepsilon,\delta)$-DPアルゴリズムには$\Omega(\frac{\sqrt{ \log|\mathcal{X}| \log(1/\delta)} \log Q}{\varepsilon\alpha^2})$サンプルが必要である。 我々のフレームワークは、直接相関解析によってこの境界を証明することができ、[BUV'14]の事前境界を$\sqrt{\log(1/\delta)}$で改善することができる。 第3に、近似微分プライバシーの下でランダムな$0$-$1$のクエリに答えることの複雑さを特徴付ける。 我々は異なる体制で新しい上と下の境界を与える。 それらを既知の結果と組み合わせることで、全体像を完結させることができる。

関連論文リスト

• Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity [8.100854060749212]
  本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。 我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
  論文  参考訳（メタデータ） (2023-12-09T19:22:10Z)
• Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
  精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。 また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
  論文  参考訳（メタデータ） (2023-05-08T17:46:01Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• Private High-Dimensional Hypothesis Testing [4.133655523622441]
  我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。 具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
  論文  参考訳（メタデータ） (2022-03-03T06:25:48Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Differentially Private Release and Learning of Threshold Functions [27.612916837481485]
  我々は、$(epsilon, delta)$微分プライベートアルゴリズムのサンプル複雑性に対して、新しい上界と下界を証明した。 完全に順序付けられたドメイン上のしきい値関数$c_x$は$c_x(y) = 1$ if $y le x$と評価され、$0$と評価される。
  論文  参考訳（メタデータ） (2015-04-28T16:15:01Z)

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

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