論文の概要: Differentially Private Multi-Sampling from Distributions
- arxiv url: http://arxiv.org/abs/2412.10512v1
- Date: Fri, 13 Dec 2024 19:14:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-17 14:02:25.516321
- Title: Differentially Private Multi-Sampling from Distributions
- Title（参考訳）: 分布からの微分プライベートマルチサンプリング
- Authors: Albert Cheu, Debanuj Nayak,
- Abstract要約: 本研究は,DPエフェッスルサンプリングのサンプル複雑性,すなわち,このタスクの実行に必要なサンプルの最小数について検討する。
エンフルティサンプリングの2つの変種を定義し、そこでは、プライベートに$m>1$サンプルを近似することを目的としている。
- 参考スコア（独自算出の注目度）: 4.292685318253575
- License:
- Abstract: Many algorithms have been developed to estimate probability distributions subject to differential privacy (DP): such an algorithm takes as input independent samples from a distribution and estimates the density function in a way that is insensitive to any one sample. A recent line of work, initiated by Raskhodnikova et al. (Neurips '21), explores a weaker objective: a differentially private algorithm that approximates a single sample from the distribution. Raskhodnikova et al. studied the sample complexity of DP \emph{single-sampling} i.e., the minimum number of samples needed to perform this task. They showed that the sample complexity of DP single-sampling is less than the sample complexity of DP learning for certain distribution classes. We define two variants of \emph{multi-sampling}, where the goal is to privately approximate $m>1$ samples. This better models the realistic scenario where synthetic data is needed for exploratory data analysis. A baseline solution to \emph{multi-sampling} is to invoke a single-sampling algorithm $m$ times on independently drawn datasets of samples. When the data comes from a finite domain, we improve over the baseline by a factor of $m$ in the sample complexity. When the data comes from a Gaussian, Ghazi et al. (Neurips '23) show that \emph{single-sampling} can be performed under approximate differential privacy; we show it is possible to \emph{single- and multi-sample Gaussians with known covariance subject to pure DP}. Our solution uses a variant of the Laplace mechanism that is of independent interest. We also give sample complexity lower bounds, one for strong multi-sampling of finite distributions and another for weak multi-sampling of bounded-covariance Gaussians.
- Abstract（参考訳）: 多くのアルゴリズムは、差分プライバシー(DP)の対象となる確率分布を推定するために開発された。
Raskhodnikova et al (Neurips '21)によって始められた最近の研究は、より弱い目的を探求している。
Raskhodnikovaらは、DP \emph{single-sampling} のサンプルの複雑さ、すなわち、このタスクを実行するのに必要な最小のサンプル数について研究した。
その結果、DP単サンプリングのサンプル複雑性は、特定の分布クラスにおけるDP学習のサンプル複雑性よりも小さいことがわかった。
emph{multi-sampling} の2つの変種を定義する。
これは、探索データ分析に合成データが必要とされる現実的なシナリオをモデル化する。
emph{multi-sampling}のベースラインソリューションは、独立に描画されたサンプルのデータセットで$m$倍の単サンプリングアルゴリズムを呼び出すことである。
データが有限領域から来ると、サンプルの複雑さにおいて$m$の係数でベースラインよりも改善する。
ガウスから得られたデータから、Ghazi et al (Neurips '23) は、近似微分プライバシーの下で \emph{single-sampling} を実行できることを示した。
我々の解は、独立した利害関係を持つラプラス機構の変種を用いる。
また、有限分布の強い多重サンプリングに対して、また有界共分散ガウスの弱い多重サンプリングのために、サンプル複雑性の低い境界を与える。
関連論文リスト
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。
また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
論文 参考訳（メタデータ） (2024-06-03T01:34:34Z) - Weighted Sparse Partial Least Squares for Joint Sample and Feature
Selection [7.219077740523681]
本稿では, 共同サンプルと特徴選択のために, $ell_infty/ell_0$-norm制約付きスパースPSS(ell_infty/ell_$-wsPLS)法を提案する。
我々は,各マルチビューwsPLSモデルに対して効率的な反復アルゴリズムを開発し,その収束性を示す。
論文 参考訳（メタデータ） (2023-08-13T10:09:25Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Bias Mimicking: A Simple Sampling Approach for Bias Mitigation [57.17709477668213]
本稿では,新しいクラス条件サンプリング手法であるBias Mimickingを紹介する。
Bias Mimickingは、4つのベンチマークで3%の精度でサンプリングの精度を向上する。
論文 参考訳（メタデータ） (2022-09-30T17:33:00Z) - Undersampling is a Minimax Optimal Robustness Intervention in
Nonparametric Classification [28.128464387420216]
マイノリティグループサンプルの欠如によって学習が根本的に制約されていることを示す。
特にラベルシフトの場合、最小値のアンダーサンプリングアルゴリズムが常に存在することを示す。
論文 参考訳（メタデータ） (2022-05-26T00:35:11Z) - Covariance-Aware Private Mean Estimation Without Private Covariance Estimation [10.036088581191592]
2つのサンプル係数差分プライベート平均推定器を$d$-dimensional(sub)Gaussian分布に対して提案する。
我々の推定子は、$| tildemu - mu |_Sigma leq alpha$, where $| cdot |_Sigma$がマハラノビス距離であるような$tildemu$を出力します。
論文 参考訳（メタデータ） (2021-06-24T21:40:07Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。