論文の概要: Majority-of-Three: The Simplest Optimal Learner?

• arxiv url: http://arxiv.org/abs/2403.08831v1
• Date: Tue, 12 Mar 2024 18:01:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-16 00:51:27.945073
• Title: Majority-of-Three: The Simplest Optimal Learner?
• Title（参考訳）: Majority-of-Three: The Simplest Optimal Learner?
• Authors: Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy,
• Abstract要約: ハンネケのアルゴリズムは、多くのERM分類器の多数票を返すため、非常に複雑である。 このアルゴリズムは,その誤差に縛られた最適逆予測を実現する。 我々は、このアルゴリズムが実際に高い確率構造において最適であると推測する。
• 参考スコア（独自算出の注目度）: 17.87433808079955
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Developing an optimal PAC learning algorithm in the realizable setting, where empirical risk minimization (ERM) is suboptimal, was a major open problem in learning theory for decades. The problem was finally resolved by Hanneke a few years ago. Unfortunately, Hanneke's algorithm is quite complex as it returns the majority vote of many ERM classifiers that are trained on carefully selected subsets of the data. It is thus a natural goal to determine the simplest algorithm that is optimal. In this work we study the arguably simplest algorithm that could be optimal: returning the majority vote of three ERM classifiers. We show that this algorithm achieves the optimal in-expectation bound on its error which is provably unattainable by a single ERM classifier. Furthermore, we prove a near-optimal high-probability bound on this algorithm's error. We conjecture that a better analysis will prove that this algorithm is in fact optimal in the high-probability regime.
• Abstract（参考訳）: 経験的リスク最小化(ERM)が最適であるような、実現可能な環境で最適なPAC学習アルゴリズムを開発することは、数十年にわたって学習理論において大きなオープンな問題であった。 この問題は、数年前にHannekeによってようやく解決された。 残念なことに、Hannekeのアルゴリズムは非常に複雑であり、データは慎重に選択されたサブセットでトレーニングされた多くのERM分類器の多数投票を返却する。 したがって、最適である最も単純なアルゴリズムを決定することは自然な目標である。 本研究では、3つのEMM分類器の過半数を返却する最も単純なアルゴリズムについて検討する。 本アルゴリズムは,1つのERM分類器で確実に達成不可能な誤差に縛られる最適逆探索を実現する。 さらに,このアルゴリズムの誤差に係わるほぼ最適確率を証明した。 より優れた解析により、このアルゴリズムが実際は高確率状態において最適であることを証明できると推測する。

関連論文リスト

• Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
  モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。 我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。 このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-14T11:12:32Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• First Steps Towards a Runtime Analysis When Starting With a Good Solution [8.34061303235504]
  現実的な応用では、ランダムな解よりも優れた解を推測することができる。 我々は、異なるアルゴリズムがより良い初期解と全く異なる程度に利益を得ることを示す。 このことは、進化的アルゴリズムが良い初期解をうまく活用していることがまだ見つからないことを示唆している。
  論文  参考訳（メタデータ） (2020-06-22T11:46:42Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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