論文の概要: Private Query Release Assisted by Public Data

• arxiv url: http://arxiv.org/abs/2004.10941v1
• Date: Thu, 23 Apr 2020 02:46:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-10 09:01:52.401985
• Title: Private Query Release Assisted by Public Data
• Title（参考訳）: 公開データによるプライベートクエリリリース
• Authors: Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, Zhiwei Steven Wu
• Abstract要約: 本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。 我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
• 参考スコア（独自算出の注目度）: 96.6174729958211
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of differentially private query release assisted by access to public data. In this problem, the goal is to answer a large class $\mathcal{H}$ of statistical queries with error no more than $\alpha$ using a combination of public and private samples. The algorithm is required to satisfy differential privacy only with respect to the private samples. We study the limits of this task in terms of the private and public sample complexities. First, we show that we can solve the problem for any query class $\mathcal{H}$ of finite VC-dimension using only $d/\alpha$ public samples and $\sqrt{p}d^{3/2}/\alpha^2$ private samples, where $d$ and $p$ are the VC-dimension and dual VC-dimension of $\mathcal{H}$, respectively. In comparison, with only private samples, this problem cannot be solved even for simple query classes with VC-dimension one, and without any private samples, a larger public sample of size $d/\alpha^2$ is needed. Next, we give sample complexity lower bounds that exhibit tight dependence on $p$ and $\alpha$. For the class of decision stumps, we give a lower bound of $\sqrt{p}/\alpha$ on the private sample complexity whenever the public sample size is less than $1/\alpha^2$. Given our upper bounds, this shows that the dependence on $\sqrt{p}$ is necessary in the private sample complexity. We also give a lower bound of $1/\alpha$ on the public sample complexity for a broad family of query classes, which by our upper bound, is tight in $\alpha$.
• Abstract（参考訳）: 本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。 この問題において、目標は、パブリックとプライベートのサンプルの組み合わせを使って、統計クエリの大規模なクラス$\mathcal{h}$に$\alpha$以上のエラーで答えることである。 このアルゴリズムは、プライベートサンプルに関してのみ差分プライバシーを満たす必要がある。 我々は,この課題の限界を,私的および公的なサンプルの複雑さの観点から検討する。 まず、任意のクエリクラス$\mathcal{H}$に対して、$d/\alpha$公開サンプルと$\sqrt{p}d^{3/2}/\alpha^2$プライベートサンプルのみを用いて有限VC次元の問題を解くことができ、$d$と$p$はそれぞれ$\mathcal{H}$のVC次元と双対VC次元であることを示す。 対照的に、プライベートサンプルのみの場合、VC次元の単純なクエリクラスであってもこの問題は解決できず、プライベートサンプルがなければ、より大規模な公開サンプルである$d/\alpha^2$が必要である。 次に、サンプルの複雑さを、$p$と$\alpha$に強く依存する境界を低くする。 決定スランプのクラスでは、パブリックなサンプルサイズが1/\alpha^2$未満であれば、プライベートなサンプル複雑性に対して$\sqrt{p}/\alpha$が下限となる。 上界を考えると、$\sqrt{p}$への依存はプライベートサンプルの複雑さに必要であることを示す。 また、より広い種類のクエリクラスに対して、公開サンプルの複雑さに対して1/\alpha$の低いバウンダリを与えます。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Public-data Assisted Private Stochastic Optimization: Power and Limitations [30.298342283075172]
  本稿では,PA-DPアルゴリズムの限界と限界について検討する。 完全な/ラベル付き公開データについては、$tildeOmegabig(minbigfrac1sqrtn+fracsqrtdnepsilon big big)$が過剰なリスクを持つことを示す。 また,PA-DPによる教師あり学習について,テキスト非ラベル公開サンプルを用いて検討した。
  論文  参考訳（メタデータ） (2024-03-06T17:06:11Z)
• Private Distribution Learning with Public Data: The View from Sample Compression [15.626115475759713]
  公共データへのアクセスによる個人分布学習の課題について検討する。 我々は,クラス$mathcal Q$のパブリックな学習性は,サンプル圧縮スキームの存在に関係していることを示す。
  論文  参考訳（メタデータ） (2023-08-11T17:15:12Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Robust Estimation of Discrete Distributions under Local Differential Privacy [1.52292571922932]
  局所的な差分プライバシー制約の下で,n$の汚染データバッチから離散分布を推定する問題を考察する。 2つの制約を組み合わせることで、$epsilonsqrtd/alpha2 k+sqrtd2/alpha2 kn$を$sqrtlog (1/epsilon)$ factorに設定できる。
  論文  参考訳（メタデータ） (2022-02-14T15:59:02Z)
• User-Level Private Learning via Correlated Sampling [49.453751858361265]
  我々は、各ユーザが$m$のサンプルを持ち、プライバシ保護が各ユーザのデータレベルで実施される設定について検討する。 この設定では、より少ない数のユーザーで学習できることが示されます。
  論文  参考訳（メタデータ） (2021-10-21T15:33:53Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
  差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。 $n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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