Fugu-MT 論文翻訳(概要): Differentially Private Kernel Density Estimation

論文の概要: Differentially Private Kernel Density Estimation

arxiv url: http://arxiv.org/abs/2409.01688v1
Date: Tue, 3 Sep 2024 08:01:19 GMT
ステータス: 処理完了
システム内更新日: 2024-09-06 02:30:20.809358
Title: Differentially Private Kernel Density Estimation
Title（参考訳）: 微分プライベートカーネル密度推定
Authors: Erzhi Liu, Jerry Yao-Chieh Hu, Alex Reneau, Zhao Song, Han Liu,
Abstract要約: 我々は、カーネル密度推定(KDE)のための洗練された微分プライベート(DP)データ構造を導入する。類似関数 $f$ とプライベートデータセット $X サブセット mathbbRd$ が与えられた場合、我々のゴールは、任意のクエリ $yinmathbbRd$ に対して、X f(x, y)$ の $sum_x を微分プライベートな方法で近似するように$X$ を前処理することである。
参考スコア（独自算出の注目度）: 11.526850085349155
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: We introduce a refined differentially private (DP) data structure for kernel density estimation (KDE), offering not only improved privacy-utility tradeoff but also better efficiency over prior results. Specifically, we study the mathematical problem: given a similarity function $f$ (or DP KDE) and a private dataset $X \subset \mathbb{R}^d$, our goal is to preprocess $X$ so that for any query $y\in\mathbb{R}^d$, we approximate $\sum_{x \in X} f(x, y)$ in a differentially private fashion. The best previous algorithm for $f(x,y) =\| x - y \|_1$ is the node-contaminated balanced binary tree by [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. Their algorithm requires $O(nd)$ space and time for preprocessing with $n=|X|$. For any query point, the query time is $d \log n$, with an error guarantee of $(1+\alpha)$-approximation and $\epsilon^{-1} \alpha^{-0.5} d^{1.5} R \log^{1.5} n$. In this paper, we improve the best previous result [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024] in three aspects: - We reduce query time by a factor of $\alpha^{-1} \log n$. - We improve the approximation ratio from $\alpha$ to 1. - We reduce the error dependence by a factor of $\alpha^{-0.5}$. From a technical perspective, our method of constructing the search tree differs from previous work [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. In prior work, for each query, the answer is split into $\alpha^{-1} \log n$ numbers, each derived from the summation of $\log n$ values in interval tree countings. In contrast, we construct the tree differently, splitting the answer into $\log n$ numbers, where each is a smart combination of two distance values, two counting values, and $y$ itself. We believe our tree structure may be of independent interest.
Abstract（参考訳）: カーネル密度推定(KDE)のための改良された差分法(DP)データ構造を導入し,プライバシ・ユーティリティ・トレードオフの改善だけでなく,事前結果よりも効率が向上した。具体的には, 類似関数 $f$ (あるいは DP KDE) とプライベートデータセット $X \subset \mathbb{R}^d$ が与えられたとき, 我々の目標は,任意のクエリ $y\in\mathbb{R}^d$ に対して $\sum_{x \in X} f(x, y)$ を微分プライベートな方法で前処理することである。 f(x,y) =\| x - y \|_1$ に対する最も古いアルゴリズムは[Backurs, Lin, Mahabadi, Silwal, Tarnawski, ICLR 2024] によるノード汚染二分木である。それらのアルゴリズムは、$O(nd)$スペースと$n=|X|$で前処理する時間を必要とする。任意のクエリポイントに対して、クエリ時間は$d \log n$で、エラー保証は$(1+\alpha)$-approximationと$\epsilon^{-1} \alpha^{-0.5} d^{1.5} R \log^{1.5} n$である。本稿では,過去最高の結果(Backurs, Lin, Mahabadi, Silwal, Tarnawski, ICLR 2024)を3つの面で改善する。 -近似比を$\alpha$から1に改善する。 -$\alpha^{-0.5}$でエラー依存を減らす。技術的観点から, 探索木構築法は, 以前の研究(Backurs, Lin, Mahabadi, Silwal, Tarnawski, ICLR 2024)とは異なる。以前の作業では、各クエリに対して、答えは$\alpha^{-1} \log n$ numberに分割され、それぞれがインターバルツリーカウントにおける$\log n$値の和から導かれる。対照的に、我々は木を別々に構築し、答えを$\log n$数に分割し、それぞれが2つの距離値、2つのカウント値、および$y$自身からなるスマートな組み合わせである。私たちは、木の構造が独立した関心を持つかもしれないと信じています。

関連論文リスト

Profile Reconstruction from Private Sketches [13.929335175122265]
$mathcalD$から$n$のアイテムの多重集合が与えられたとき、強調される再構成問題は、$t = 0, 1, dots, n$ に対して、$mathcalD$ のアイテムの分数 $vecf[t]$ を正確に $tfty 倍と見積もることである。分散空間制約付き環境での個人プロファイル推定について検討し,マルチセットの更新可能なプライベートスケッチを維持したいと考える。 LPベースの手法の高速化方法を示します
論文参考訳（メタデータ） (2024-06-03T09:51:28Z)
Differentially Private Approximate Pattern Matching [0.0]
我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。 1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
論文参考訳（メタデータ） (2023-11-13T15:53:45Z)
A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文参考訳（メタデータ） (2022-09-06T23:37:31Z)
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。我々はこの$d$への依存が対数的要因まで最適であることを示す。また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文参考訳（メタデータ） (2021-11-09T00:20:01Z)
Coresets for Decision Trees of Signals [19.537354146654845]
仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
論文参考訳（メタデータ） (2021-10-07T05:49:55Z)
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)
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文参考訳（メタデータ） (2020-12-16T17:58:45Z)
Universal guarantees for decision tree induction via a higher-order splitting criterion [16.832966312395126]
本アルゴリズムは,全対象関数に対して,一様分布に対して, -1,1n から -1,1$ の証明可能な保証を実現する。我々の拡張の要点は、その属性の$f$と小さなサブセットの相関を考慮に入れた、新しい分割基準である。我々のアルゴリズムは以下の保証を満たす: すべての対象関数 $f : -1,1n to -1,1$, sizes $sin mathbbN$, error parameters $epsilon$ に対して、決定を構成する。
論文参考訳（メタデータ） (2020-10-16T21:20:45Z)
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)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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