論文の概要: Instance-Optimal Private Density Estimation in the Wasserstein Distance
- arxiv url: http://arxiv.org/abs/2406.19566v1
- Date: Thu, 27 Jun 2024 22:51:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-01 18:10:10.224679
- Title: Instance-Optimal Private Density Estimation in the Wasserstein Distance
- Title（参考訳）: ワッサーシュタイン距離におけるインスタンス・最適プライベート密度推定
- Authors: Vitaly Feldman, Audra McMillan, Satchit Sivakumar, Kunal Talwar,
- Abstract要約: サンプルから分布の密度を推定することは統計学の基本的な問題である。
ワッサーシュタイン距離における個人密度の差分推定について検討する。
- 参考スコア（独自算出の注目度）: 37.58527481568219
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical settings, the Wasserstein distance is an appropriate error metric for density estimation. For example, when estimating population densities in a geographic region, a small Wasserstein distance means that the estimate is able to capture roughly where the population mass is. In this work we study differentially private density estimation in the Wasserstein distance. We design and analyze instance-optimal algorithms for this problem that can adapt to easy instances. For distributions $P$ over $\mathbb{R}$, we consider a strong notion of instance-optimality: an algorithm that uniformly achieves the instance-optimal estimation rate is competitive with an algorithm that is told that the distribution is either $P$ or $Q_P$ for some distribution $Q_P$ whose probability density function (pdf) is within a factor of 2 of the pdf of $P$. For distributions over $\mathbb{R}^2$, we use a different notion of instance optimality. We say that an algorithm is instance-optimal if it is competitive with an algorithm that is given a constant-factor multiplicative approximation of the density of the distribution. We characterize the instance-optimal estimation rates in both these settings and show that they are uniformly achievable (up to polylogarithmic factors). Our approach for $\mathbb{R}^2$ extends to arbitrary metric spaces as it goes via hierarchically separated trees. As a special case our results lead to instance-optimal private learning in TV distance for discrete distributions.
- Abstract（参考訳）: サンプルから分布の密度を推定することは統計学の基本的な問題である。
多くの実践的な設定において、ワッサーシュタイン距離は密度推定の適切な誤差計量である。
例えば、地理的領域における人口密度を推定する場合、小さなワッサーシュタイン距離は、推定値が人口質量のほぼどこにあるかを把握することができることを意味する。
本研究ではワッサーシュタイン距離における個人密度の差分推定について検討する。
この問題に対して、簡単なインスタンスに適応可能なインスタンス最適化アルゴリズムを設計し、分析する。
P$ over $\mathbb{R}$ に対して、インスタンス最適化率を均一に達成するアルゴリズムは、ある分布に対して、確率密度関数 (pdf) が $P$ の pdf の 2 倍の範囲内であるような$P$ または $Q_P$ であることを示すアルゴリズムと競合する。
$\mathbb{R}^2$ 上の分布に対しては、インスタンス最適性という別の概念を用いる。
分布密度の定数乗算近似が与えられるアルゴリズムと競合する場合、アルゴリズムはインスタンス最適化であると述べる。
これら2つの設定のインスタンス-最適推定速度を特徴付けるとともに、それらが一様達成可能であることを示す(多言語的要因まで)。
我々の $\mathbb{R}^2$ に対するアプローチは、階層的に分離された木を通る任意の距離空間に拡張する。
特別の場合として,本研究の結果は,個別分布におけるテレビ距離のインスタンス最適プライベートラーニングに繋がる。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。
我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
論文 参考訳（メタデータ） (2024-09-04T03:41:44Z) - Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳（メタデータ） (2023-11-21T18:50:38Z) - Estimating the Density Ratio between Distributions with High Discrepancy
using Multinomial Logistic Regression [21.758330613138778]
その結果, 最先端密度比推定器は, 十分に分離されたケースでは性能が良くないことがわかった。
密度比推定に多クラス分類を利用する方法を提案する。
論文 参考訳（メタデータ） (2023-05-01T15:10:56Z) - Energy-Based Sliced Wasserstein Distance [47.18652387199418]
スライスされたワッサーシュタイン(SW)距離の鍵成分はスライス分布である。
本研究では,スライシング分布をパラメータフリーなエネルギーベース分布として設計する。
次に、新しいスライスされたワッセルシュタイン計量、エネルギーベースのスライスされたワッセルシュタイン距離(EBSW)を導出する。
論文 参考訳（メタデータ） (2023-04-26T14:28:45Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳（メタデータ） (2023-01-09T18:36:49Z) - Linear Optimal Transport Embedding: Provable Wasserstein classification
for certain rigid transformations and perturbations [79.23797234241471]
分布の区別は多くの科学分野において重要な問題である。
線形最適輸送(LOT)は分布の空間を$L2$-スペースに埋め込む。
複数の分布分類問題に対するLOTの利点を実証する。
論文 参考訳（メタデータ） (2020-08-20T19:09:33Z) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。
我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。
AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
論文 参考訳（メタデータ） (2020-02-05T03:09:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。