論文の概要: Locally differentially private estimation of nonlinear functionals of
discrete distributions
- arxiv url: http://arxiv.org/abs/2107.03940v1
- Date: Thu, 8 Jul 2021 16:11:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-09 13:39:48.397851
- Title: Locally differentially private estimation of nonlinear functionals of
discrete distributions
- Title(参考訳): 離散分布の非線形汎関数の局所微分プライベート推定
- Authors: Cristina Butucea and Yann Issartel
- Abstract要約: 離散分布の非線形関数を局所的差分プライバシーの文脈で推定する問題について検討する。
alpha$-locally differentially private (LDP) サンプルのみが公開されているが、'local' という用語は、各$z_i$が1つの個々の$x_i$を使って生成されることを意味する。
パワー和関数 $F_gamma = sum_k=1K p_kgamma$, $gamma > 0$ を $K, n の関数として推定する二次リスクの挙動を記述する。
- 参考スコア(独自算出の注目度): 3.8073142980733
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of estimating non-linear functionals of discrete
distributions in the context of local differential privacy. The initial data
$x_1,\ldots,x_n \in [K]$ are supposed i.i.d. and distributed according to an
unknown discrete distribution $p = (p_1,\ldots,p_K)$. Only $\alpha$-locally
differentially private (LDP) samples $z_1,...,z_n$ are publicly available,
where the term 'local' means that each $z_i$ is produced using one individual
attribute $x_i$. We exhibit privacy mechanisms (PM) that are interactive (i.e.
they are allowed to use already published confidential data) or
non-interactive. We describe the behavior of the quadratic risk for estimating
the power sum functional $F_{\gamma} = \sum_{k=1}^K p_k^{\gamma}$, $\gamma >0$
as a function of $K, \, n$ and $\alpha$. In the non-interactive case, we study
two plug-in type estimators of $F_{\gamma}$, for all $\gamma >0$, that are
similar to the MLE analyzed by Jiao et al. (2017) in the multinomial model.
However, due to the privacy constraint the rates we attain are slower and
similar to those obtained in the Gaussian model by Collier et al. (2020). In
the interactive case, we introduce for all $\gamma >1$ a two-step procedure
which attains the faster parametric rate $(n \alpha^2)^{-1/2}$ when $\gamma
\geq 2$. We give lower bounds results over all $\alpha$-LDP mechanisms and all
estimators using the private samples.
- Abstract(参考訳): 離散分布の非線形関数を局所的差分プライバシーの文脈で推定する問題について検討する。
初期データ $x_1,\ldots,x_n \in [K]$ は i.i.d である。
そして、未知の離散分布$p = (p_1,\ldots,p_K)$に従って分布する。
唯一の$\alpha$-locally differentially private (ldp) サンプル $z_1,...,z_n$ が公開されているが、ここでは 'local' という用語は、各$z_i$ が1つの個別属性 $x_i$ を使って生成されることを意味する。
我々は、対話的(すなわち)プライバシメカニズム(pm)を示す。
それらは、既に公開された機密データまたは非対話的の使用が許可されている。
パワー和関数 $F_{\gamma} = \sum_{k=1}^K p_k^{\gamma}$, $\gamma >0$ を $K, \, n$ および $\alpha$ の関数として推定する二次リスクの振る舞いを記述する。
非対話的なケースでは、jiaoらによって分析されたmleに類似したすべての$\gamma >0$に対して、$f_{\gamma}$の2つのプラグインタイプの推定器を調査した。
(2017年) 多項モデル。
しかし、プライバシーの制約のため、私たちが達成したレートは遅く、Collierらによって得られたガウスモデルと似ている。
(2020).
インタラクティブな場合には、$\gamma \geq 2$の場合により速いパラメトリックレート$(n \alpha^2)^{-1/2}$となる2ステップの手順をすべて$\gamma >1$に導入する。
我々は,すべての$\alpha$-LDP機構とプライベートサンプルを用いたすべての推定器に対して,より低い境界値を与える。
関連論文リスト
- On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。
この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
論文 参考訳(メタデータ) (2024-06-24T04:06:09Z) - Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。
我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
論文 参考訳(メタデータ) (2024-05-30T18:20:35Z) - Debiasing and a local analysis for population clustering using
semidefinite programming [1.9761774213809036]
サブガウス分布の混合から引き出された小さいデータサンプルを$n$で分割する問題を考察する。
この研究は、起源の個体数に応じた集団化の応用によって動機付けられている。
論文 参考訳(メタデータ) (2024-01-16T03:14:24Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳(メタデータ) (2023-09-29T14:14:53Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Private Convex Optimization via Exponential Mechanism [16.867534746193833]
我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。
また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
論文 参考訳(メタデータ) (2022-03-01T06:51:03Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳(メタデータ) (2022-02-15T03:49:28Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。