概要 - 計算統計の難解性から生じるトレードオフ

タイトル

計算統計の難解性から生じるトレードオフ

時間

2025-07-17 15:35:36

著者

{"Guy Blanc","Caleb Koch","Carmen Strassle","Li-Yang Tan"}

カテゴリ

{cs.CC,cs.DS,cs.LG}

リンク
http://arxiv.org/abs/2507.13222v1

PDF リンク
http://arxiv.org/pdf/2507.13222v1

概要

この論文は、学習アルゴリズムにおける実行時間とサンプル複雑度の関係を探求しています。特に、NP-hardnessの文脈で具体的に研究しています。この論文は、これらの二つのリソース間にトレードオフがあることを示しており、一つを改善することで他のものが犠牲になるという意味です。著者たちは、サンプル数が少ないことで概念クラスを学ぶことを目指すPAC学習モデルに焦点を当てています。彼らは、すべての多項式時間複雑度関数p(n)に対して、VC次元が1の概念クラスCが効率的に学習されるためにΘ(p(n))のサンプルが必要であることを示しました。論文はまた、学習の難しさとNPの難しさの間に結びつきを築いています。具体的には、RP = NP（つまり、NP内のすべての言語がランダム化アルゴリズムで多項式時間で決定できる場合）のとき、すべてのNP可計数クラスは多項式時間でO(VCdim(C))のサンプルで学習できることを証明しています。逆に、RP ≠ NPのときは、どのような関数Φであれ、Φ(VCdim(C))のサンプルで多項式時間で学習できないNP可計数クラスがあることを示しています。著者たちは、SAT問題に基づいた学習問題を定義し、その時間とサンプル複雑度のトレードオフがSATのそれを継承することを示し、これらの技術が統一分布学習やオンライン学習などの他の設定にも拡張できることを証明しました。この論文は以下のいくつかの重要な貢献をしています： 1. これまでの障壁を回避して、学習に対する最初のNP-hardnessに基づく下界を提供しています。 2. 学習の難しさとNPの難しさの間に結びつきを築いています。 3. 計算統計的なトレードオフの概念を他の学習設定に拡張しています。全体的に、この論文は学習アルゴリズムの限界と実行時間とサンプル複雑度の相互作用に関する理解に大きく寄与しています。

推奨論文

マッチングの単調回路複雑度

DENSE: 病院訪問を横断する多様な臨床記録の時系列モデリングを用いた長期的な進捗ノート生成

TrajLens: 複数サンプル探索における細胞発達経路構築のための視覚解析

TyDi QA-WANA: 西アと北アフリカの言語における情報探索型質問応答のための基準

重複なし、停止なし：リアルタイムレンダリングのための軽量ストリーミング3Dガウススプラッティング

2025年インタースピーチ音声アクセスプロジェクトチャレンジ

非正規化ユークリッド距離のための$k$-PCA: 多項式時間近似

不確実性下での堅牢最適化を通じてのパーソナライズド薬剤の計算的デザイン

5Gにおけるアクティブ攻撃耐性：認証とキー合意の新しいアプローチ

グラフベースの複製システムにおける対称的プライベート情報検索（SPIR）