Fugu-MT 論文翻訳(概要): Decidability of Sample Complexity of PAC Learning in finite setting

論文の概要: Decidability of Sample Complexity of PAC Learning in finite setting

arxiv url: http://arxiv.org/abs/2002.11519v1
Date: Wed, 26 Feb 2020 14:27:36 GMT
ステータス: 処理完了
システム内更新日: 2022-12-28 14:42:55.367383
Title: Decidability of Sample Complexity of PAC Learning in finite setting
Title（参考訳）: 有限設定におけるpac学習のサンプル複雑性の決定可能性
Authors: Alberto Gandolfi
Abstract要約: 様々な概念のPAC機械学習は、モデルとして考慮された確率測度の支持がa-プリオリ境界を満たすとき、正確に決定できる。この結果は、最近発見された有限支持確率に対するZFC内のEMXの不決定性とは対照的である。
参考スコア（独自算出の注目度）: 1.8130068086063333
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this short note we observe that the sample complexity of PAC machine learning of various concepts, including learning the maximum (EMX), can be exactly determined when the support of the probability measures considered as models satisfies an a-priori bound. This result contrasts with the recently discovered undecidability of EMX within ZFC for finitely supported probabilities (with no a priori bound). Unfortunately, the decision procedure is at present, at least doubly exponential in the number of points times the uniform bound on the support size.
Abstract（参考訳）: この短い注記では、モデルとして見なされる確率測度のサポートがa-priori境界を満たすときに、最大値(emx)を含む様々な概念のpac機械学習のサンプル複雑性を正確に決定できることを観察する。この結果は、有限支持確率に対するZFC内でのEMXの非決定性(事前境界を持たない)とは対照的である。残念なことに、決定手続きは現在、少なくとも支持サイズに一様束縛された点数の2倍の指数関数である。

関連論文リスト

Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
論文参考訳（メタデータ） (2024-06-12T06:41:47Z)
Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming [0.6906005491572401]
本稿では,凸問題や強凸プログラミング(SP)問題におけるサンプル平均近似(SAA)について検討する。 SAAのサンプルの複雑さは、計量エントロピーの定量化から完全に解放されることを示している。
論文参考訳（メタデータ） (2024-01-01T04:35:53Z)
Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-12-08T16:06:29Z)
Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
論文参考訳（メタデータ） (2023-10-31T19:26:36Z)
Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。簡便な解と理論的に最適な解との決定論的関係を導出する。
論文参考訳（メタデータ） (2023-10-03T04:40:38Z)
Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文参考訳（メタデータ） (2023-07-01T18:35:21Z)
Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文参考訳（メタデータ） (2022-10-08T08:26:22Z)
Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
本稿では,一般的な逐次決定のための簡単な学習アルゴリズムを提案する。我々は,OMLEが極めて豊富な逐次的意思決定問題のクラスにおいて,ほぼ最適ポリシーを学習していることを証明する。
論文参考訳（メタデータ） (2022-09-29T17:56:25Z)
Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文参考訳（メタデータ） (2020-06-22T17:58:54Z)

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