論文の概要: Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
- arxiv url: http://arxiv.org/abs/2506.01162v1
- Date: Sun, 01 Jun 2025 20:46:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-04 21:47:33.959
- Title: Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
- Title（参考訳）: 最適近似係数を用いた近距離時間プライベート仮説の選択
- Authors: Maryam Aliakbarpour, Zhan Shi, Ria Stevens, Vincent X. Wang,
- Abstract要約: 分布の密度をサンプルから推定することは統計学の基本的な問題である。
仮説選択は、サンプルセットに加えて、$n$の候補分布が与えられる設定に対処する。
本稿では,仮説の数に関して,ほぼ直線時間で実行される中央モデルに差分プライベートなアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 7.069470347531414
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Estimating the density of a distribution from its samples is a fundamental problem in statistics. Hypothesis selection addresses the setting where, in addition to a sample set, we are given $n$ candidate distributions -- referred to as hypotheses -- and the goal is to determine which one best describes the underlying data distribution. This problem is known to be solvable very efficiently, requiring roughly $O(\log n)$ samples and running in $\tilde{O}(n)$ time. The quality of the output is measured via the total variation distance to the unknown distribution, and the approximation factor of the algorithm determines how large this distance is compared to the optimal distance achieved by the best candidate hypothesis. It is known that $\alpha = 3$ is the optimal approximation factor for this problem. We study hypothesis selection under the constraint of differential privacy. We propose a differentially private algorithm in the central model that runs in nearly-linear time with respect to the number of hypotheses, achieves the optimal approximation factor, and incurs only a modest increase in sample complexity, which remains polylogarithmic in $n$. This resolves an open question posed by [Bun, Kamath, Steinke, Wu, NeurIPS 2019]. Prior to our work, existing upper bounds required quadratic time.
- Abstract（参考訳）: 分布の密度をサンプルから推定することは統計学の基本的な問題である。
仮説の選択は、サンプルセットに加えて、$n$の候補分布(仮説と呼ばれる)が与えられます。
この問題は、およそ$O(\log n)$サンプルを必要とし、$\tilde{O}(n)$時間で実行されるため、非常に効率的に解けることが知られている。
出力の質は、未知分布に対する全変動距離によって測定され、アルゴリズムの近似係数は、この距離が最適な仮説によって達成される最適距離と比較されるかを決定する。
この問題の最適近似因子は$\alpha = 3$であることが知られている。
差分プライバシーの制約下での仮説選択について検討する。
仮説の数に関してほぼ直線的な時間で実行され、最適近似係数を達成し、サンプルの複雑さをわずかに増加させるだけであり、これは$n$でポリ対数的のままである。
これは[Bun, Kamath, Steinke, Wu, NeurIPS 2019]が提起したオープンな質問を解決します。
我々の研究に先立ち、既存の上限は2次時間を必要とした。
関連論文リスト
- Instance-Optimality for Private KL Distribution Estimation [41.35506763248454]
未知の離散分布 $p$ over $d$ symbols, given $n$ i.i.d. sample from the distribution。
本稿では,差分プライバシー制約を伴わずに,一定要素までのインスタンス最適化を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-05-29T16:27:57Z) - Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Instance-Optimal Private Density Estimation in the Wasserstein Distance [37.58527481568219]
サンプルから分布の密度を推定することは統計学の基本的な問題である。
ワッサーシュタイン距離における個人密度の差分推定について検討する。
論文 参考訳（メタデータ） (2024-06-27T22:51:06Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳（メタデータ） (2022-12-15T18:27:39Z) - Distributionally Robust Optimization with Markovian Data [8.126833795693699]
本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。
本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
論文 参考訳（メタデータ） (2021-06-12T10:59:02Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。