論文の概要: Hypothesis Selection via Weighted Medians
- arxiv url: http://arxiv.org/abs/2610.20375v1
- Date: Wed, 14 Oct 2026 15:45:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-15 21:06:16.240768
- Title: Hypothesis Selection via Weighted Medians
- Title（参考訳）: 重み付けメディアを用いた仮説選択
- Abstract要約: 我々は、$O(varepsilon-2log(n/))$ターゲットサンプルを使用して、$O(nvarepsilon-2log(n/))$timeを少なくとも1-$の確率で実行し、$H_hat i$を満足する$d_mathrmTV(P,H_hat i)leq 3min_iin[n]d_mathrmTV(P,H_i)+varepsilon.$
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given $n$ distributions (hypotheses) $\mathcal H=\{H_1,\ldots,H_n\}$ and samples from an unknown target distribution $P$, proper hypothesis selection seeks a distribution whose total variation distance to $P$ is close to the best achievable within the known distributions. We give an algorithm that, using $O(\varepsilon^{-2}\log(n/δ))$ target samples, running in $O(n\varepsilon^{-2}\log(n/δ))$ time, with probability at least $1-δ$, returns $H_{\hat i}$ satisfying $d_\mathrm{TV}(P,H_{\hat i})\leq 3\min_{i\in[n]}d_\mathrm{TV}(P,H_i)+\varepsilon.$ The algorithm achieves the optimal approximation factor and sample complexity. The running time improves the dependence on the failure probability from polynomial to logarithmic in the state-of-the-art bound $\tilde{O}(n\varepsilon^{-2}δ^{-1})$ of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.
- Abstract（参考訳）: n$分布(仮説)$\mathcal H=\{H_1,\ldots,H_n\}$と未知のターゲット分布$P$からのサンプルが与えられたとき、適切な仮説選択は、P$への全変動距離が既知の分布の中で最も達成可能な分布に近くなる分布を求める。
我々は、$O(\varepsilon^{-2}\log(n/δ))$ターゲットサンプルを使用し、$O(n\varepsilon^{-2}\log(n/δ))$timeを少なくとも1-δ$の確率で実行し、$H_{\hat i}$を満足する$d_\mathrm{TV}(P,H_{\hat i})\leq 3\min_{i\in[n]}d_\mathrm{TV}(P,H_i)+\varepsilonを返します。
アルゴリズムは最適な近似係数とサンプルの複雑さを達成する。
ランニングタイムは Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026)$ の最先端境界 $\tilde{O}(n\varepsilon^{-2}δ^{-1}) における多項式から対数への失敗確率への依存を改善し、その結果質問に答える。
関連論文リスト
- High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。
我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
論文 参考訳（メタデータ） (2026-02-01T17:05:31Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Hypothesis Selection: A High Probability Conundrum [18.424488719261984]
P$ への全変動距離が $mathcalH$ の最も近い仮説に匹敵する仮説を求めるアルゴリズムを提案する。
また、仮説選択を3つの代替設定で研究し、事前の作業からいくつかのオープンな質問を解決または進行させる。
論文 参考訳（メタデータ） (2025-09-03T21:44:48Z) - Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions [2.959331374750817]
これは$d$と$frac1epsilon$である。 $L=mathcalO(1)$と$M=mathrmpoly(d)$である。
論文 参考訳（メタデータ） (2025-07-15T12:06:11Z) - Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳（メタデータ） (2023-12-09T19:22:10Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳（メタデータ） (2023-03-30T02:50:49Z) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。