論文の概要: Hypothesis Selection: A High Probability Conundrum

• arxiv url: http://arxiv.org/abs/2509.03734v1
• Date: Wed, 03 Sep 2025 21:44:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-05 20:21:09.979738
• Title: Hypothesis Selection: A High Probability Conundrum
• Title（参考訳）: 仮説選択: 高い確率の良し悪し
• Authors: Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Sandeep Silwal,
• Abstract要約: P$ への全変動距離が $mathcalH$ の最も近い仮説に匹敵する仮説を求めるアルゴリズムを提案する。 また、仮説選択を3つの代替設定で研究し、事前の作業からいくつかのオープンな質問を解決または進行させる。
• 参考スコア（独自算出の注目度）: 18.424488719261984
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the hypothesis selection problem, we are given a finite set of candidate distributions (hypotheses), $\mathcal{H} = \{H_1, \ldots, H_n\}$, and samples from an unknown distribution $P$. Our goal is to find a hypothesis $H_i$ whose total variation distance to $P$ is comparable to that of the nearest hypothesis in $\mathcal{H}$. If the minimum distance is $\mathsf{OPT}$, we aim to output an $H_i$ such that, with probability at least $1-\delta$, its total variation distance to $P$ is at most $C \cdot \mathsf{OPT} + \varepsilon$. Despite decades of work, key aspects of this problem remain unresolved, including the optimal running time for algorithms that achieve the optimal sample complexity and best possible approximation factor of $C=3$. The previous state-of-the-art result [Aliakbarpour, Bun, Smith, NeurIPS 2024] provided a nearly linear in $n$ time algorithm but with a sub-optimal dependence on the other parameters, running in $\tilde{O}(n/(\delta^3\varepsilon^3))$ time. We improve this time complexity to $\tilde{O}(n/(\delta \varepsilon^2))$, significantly reducing the dependence on the confidence and error parameters. Furthermore, we study hypothesis selection in three alternative settings, resolving or making progress on several open questions from prior works. (1) We settle the optimal approximation factor when bounding the \textit{expected distance} of the output hypothesis, rather than its high-probability performance. (2) Assuming the numerical value of \textit{$\mathsf{OPT}$ is known} in advance, we present an algorithm obtaining $C=3$ and runtime $\tilde{O}(n/\varepsilon^2)$ with the optimal sample complexity and succeeding with high probability in $n$. (3) Allowing polynomial \textit{preprocessing} step on the hypothesis class $\mathcal{H}$ before observing samples, we present an algorithm with $C=3$ and subquadratic runtime which succeeds with high probability in $n$.
• Abstract（参考訳）: 仮説選択問題では、候補分布の有限集合(仮説)、$\mathcal{H} = \{H_1, \ldots, H_n\}$、未知分布のサンプルを与えられる。 我々のゴールは、$H_i$ の合計変動距離が$P$ の仮説を$\mathcal{H}$ の仮説に匹敵する仮説を見つけることである。 最小距離が$\mathsf{OPT}$であれば、少なくとも1-\delta$の確率で$P$への総変分距離が少なくとも$C \cdot \mathsf{OPT} + \varepsilon$となるような$H_i$を出力することを目指している。 数十年にわたる作業にもかかわらず、この問題の重要な側面は未解決のままであり、最適なサンプル複雑性を達成するアルゴリズムの最適実行時間と、可能な近似係数が$C=3$である。 以前の最先端の結果(Aliakbarpour, Bun, Smith, NeurIPS 2024)は、ほぼ線形な$n$タイムアルゴリズムを提供するが、他のパラメータへの準最適依存性を持ち、$\tilde{O}(n/(\delta^3\varepsilon^3)$タイムで動作する。 我々はこの時間の複雑さを$\tilde{O}(n/(\delta \varepsilon^2))$に改善し、信頼性とエラーパラメータへの依存を著しく減らした。 さらに, 仮説選択を3つの代替条件で検討し, 先行研究からいくつかのオープンな質問を解いたり, 進行させたりした。 1) 高確率性能ではなく,出力仮説の「textit{expected distance}」をバウンドする場合に最適近似係数を導出する。 2) 先行して \textit{$\mathsf{OPT}$ is known} の数値を仮定すると, 最適なサンプル複雑性を持つ$C=3$および実行時 $\tilde{O}(n/\varepsilon^2)$ を得るアルゴリズムが提案される。 (3) 多項式 {\displaystyle \textit{preprocessing} をサンプルを観察する前に、仮説クラス $\mathcal{H}$ にステップを与えると、$C=3$ と $n$ の確率で成功するサブクアクラティックランタイムを持つアルゴリズムを提示する。

関連論文リスト

• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• 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)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• 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)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
  仮説選択問題に対する最適2ドルの近似学習戦略を導出する。 これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2021-08-17T21:11:20Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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