Fugu-MT 論文翻訳(概要): Differentially Private Release and Learning of Threshold Functions

論文の概要: Differentially Private Release and Learning of Threshold Functions

arxiv url: http://arxiv.org/abs/1504.07553v2
Date: Thu, 19 Dec 2024 23:22:37 GMT
ステータス: 翻訳完了
システム内更新日: 2025-01-12 15:57:51.987442
Title: Differentially Private Release and Learning of Threshold Functions
Title（参考訳）: 閾値関数の微分プライベートリリースと学習
Authors: Mark Bun, Kobbi Nissim, Uri Stemmer, Salil Vadhan,
Abstract要約: 我々は、$(epsilon, delta)$微分プライベートアルゴリズムのサンプル複雑性に対して、新しい上界と下界を証明した。完全に順序付けられたドメイン上のしきい値関数$c_x$は$c_x(y) = 1$ if $y le x$と評価され、$0$と評価される。
参考スコア（独自算出の注目度）: 27.612916837481485
License:
Abstract: We prove new upper and lower bounds on the sample complexity of $(\epsilon, \delta)$ differentially private algorithms for releasing approximate answers to threshold functions. A threshold function $c_x$ over a totally ordered domain $X$ evaluates to $c_x(y) = 1$ if $y \le x$, and evaluates to $0$ otherwise. We give the first nontrivial lower bound for releasing thresholds with $(\epsilon,\delta)$ differential privacy, showing that the task is impossible over an infinite domain $X$, and moreover requires sample complexity $n \ge \Omega(\log^*|X|)$, which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with $n \le 2^{(1+ o(1))\log^*|X|}$ samples. This improves the previous best upper bound of $8^{(1 + o(1))\log^*|X|}$ (Beimel et al., RANDOM '13). Our sample complexity upper and lower bounds also apply to the tasks of learning distributions with respect to Kolmogorov distance and of properly PAC learning thresholds with differential privacy. The lower bound gives the first separation between the sample complexity of properly learning a concept class with $(\epsilon,\delta)$ differential privacy and learning without privacy. For properly learning thresholds in $\ell$ dimensions, this lower bound extends to $n \ge \Omega(\ell \cdot \log^*|X|)$. To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database $D$ of elements from $X$, the interior point problem asks for an element between the smallest and largest elements in $D$. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential privacy.
Abstract（参考訳）: 閾値関数に近似した解を出すために,$(\epsilon, \delta)$差分プライベートアルゴリズムのサンプル複雑性に対して,新しい上界と下界を証明した。完全に順序付けられたドメイン上のしきい値関数$c_x$は$c_x(y) = 1$ if $y \le x$と評価され、$0$と評価される。差分プライバシーが$(\epsilon,\delta)$で閾値を解放する最初の非自明な下界を与えると、そのタスクは無限のドメインで$X$で不可能であり、さらに、ドメインのサイズで成長するサンプルの複雑さ$n \ge \Omega(\log^*|X|)$を必要とする。この下界を証明するために用いられる手法に着想を得て、$n \le 2^{(1+ o(1))\log^*|X|}$サンプルで閾値を解放するアルゴリズムを与える。これにより、以前の最高上限である 8^{(1 + o(1))\log^*|X|}$ (Beimel et al , RANDOM '13) が改善される。また,本サンプルの複雑性は,コルモゴロフ距離に対する分布の学習や,差分プライバシーによるPAC学習閾値の適正化にも適用できる。下限は、$(\epsilon,\delta)$差分プライバシーとプライバシのない学習という概念クラスを適切に学習する、サンプルの複雑さを初めて分離するものである。 $\ell$次元の閾値を適切に学習するために、この下界は$n \ge \Omega(\ell \cdot \log^*|X|)$に拡張される。この結果を得るため,両方向の学習しきい値の解放と適切な学習から,より単純な内部点問題まで,両方向の削減を図った。データベースが$X$から$D$の要素を与えられたとき、内点問題は$D$の最小要素と最大の要素の間の要素を求める。本稿では、内部点問題におけるサンプルの複雑さを束縛する新たな再帰的構造を導入するとともに、差分プライバシーにおける他の基本的な問題に対する可逆性を証明するためのさらなる削減と技術を導入する。

論文の概要: Differentially Private Release and Learning of Threshold Functions

関連論文リスト