論文の概要: Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning

• arxiv url: http://arxiv.org/abs/2608.26516v1
• Date: Thu, 27 Aug 2026 01:39:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-28 16:30:58.212242
• Title: Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning
• Title（参考訳）: アルゴリズムによるマルチクラス学習の原則:正規化の限界と適切な学習
• Abstract要約: 統計的学習理論における最も基本的な2つの疑問は、どの予測問題が学習可能か、どのように学習すべきかである。 適切な学習を行うにはトレーニングエラーが必要であり,この現象を正確に特徴づける必要がある。 我々は,構造リスク最小化学習者が学習できない適切な学習可能なクラスと,局所正規化学習者が学習できない学習可能なクラスを提示する。
• 参考スコア（独自算出の注目度）: 17.483318390877916
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Two of the most fundamental questions in statistical learning theory are the following: which prediction problems are learnable, and how should they be learned? For the former, elegant answers often take the form of combinatorial dimensions. The latter question, however, has proved considerably more elusive: all known general-purpose multiclass learners rely on intricate orientations of exponentially large one-inclusion structures, and familiar algorithmic principles such as proper learning and regularization remain poorly understood. Motivated by prior work, we ask whether learning reduces to proper learning---possibly over a larger hypothesis class---and whether proper or improper multiclass learning can ultimately be captured by suitable regularizers. Our primary results answer both questions negatively, resolving three open problems from prior work. First, we exhibit a learnable multiclass problem that cannot be embedded in any properly learnable class, meaning learning cannot be reduced to proper learning by enlarging the hypothesis class. Second, we demonstrate that proper learning can require training error and characterize this phenomenon precisely: every properly learnable class admits a proper learner making $o(m)$ errors on samples of size $m$, but every prescribed sublinear scale $a_m=o(m)$ is necessary for some properly learnable problem. Third, regularization is not a general learner: we exhibit a properly learnable class that cannot be learned by any Structural Risk Minimization (SRM) learner, and a learnable class that cannot be learned by any local regularizer. We complement these impossibility results with a positive theory that gives two sufficient conditions for SRM learnability and characterizes SRM representability through integrability of revealed preferences.
• Abstract（参考訳）: 統計的学習理論における最も基本的な2つの疑問は、どの予測問題が学習可能か、どのように学習すべきか、である。 前者にとってエレガントな答えは、しばしば組合せ次元の形を取る。 一般的な多クラス学習者は、指数関数的に大きな一介在物構造の複雑な配向に依存しており、適切な学習や正規化のような慣れ親しんだアルゴリズム原理はいまだに理解されていない。 先行研究によって動機づけられた学習が、より大規模な仮説クラスよりも適切な学習に還元されるか否か、そして、適切な正規化によって、適切な学習と不適切なマルチクラス学習が最終的に取得できるかどうかを問う。 私たちの主な結果は、両方の質問に否定的に答え、前の作業から3つのオープンな問題を解決します。 まず、適切な学習可能なクラスに組み込むことができない学習可能なマルチクラス問題を示す。 第二に、適切な学習にはトレーニングエラーが必要であり、この現象を正確に特徴づけることが示される: 適切な学習可能なクラスは、$m$のサンプルに対して$o(m)$エラーを生成できるが、適切な学習可能な問題に対して、所定のサブ線形スケール$a_m=o(m)$が必須である。 第三に、正規化は一般的な学習者ではなく、構造的リスク最小化(SRM)学習者が学べない適切な学習可能なクラスと、局所正規化者が学べない学習可能なクラスを示す。 本研究では、これらの不合理性の結果を、SRM学習可能性に十分な2つの条件を与える肯定的な理論で補完し、明らかな選好の可積分性を通じてSRM表現性を特徴付ける。

関連論文リスト

• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。 この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。 この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
  論文  参考訳（メタデータ） (2026-05-10T14:28:05Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。 一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。 一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
  論文  参考訳（メタデータ） (2026-02-24T06:15:59Z)
• Computable universal online learning [1.7961752949636303]
  普遍的なオンライン学習は、計算可能な普遍的なオンライン学習を含まないことを示す。 また、適切なユニバーサルオンライン学習のバリエーションを検討し、それがいつ可能かを正確に示す。
  論文  参考訳（メタデータ） (2025-10-21T07:21:32Z)
• Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
  適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを示す。 そこで本研究では,PACモデルにおいて,適切な学習可能性の特性を損なう不確実性に関するすべての結果を示す。
  論文  参考訳（メタデータ） (2025-02-14T18:41:53Z)
• Ticketed Learning-Unlearning Schemes [57.89421552780526]
  そこで我々は,学習のためのチケット付きモデルを提案する。 広義のコンセプトクラスに対して,空間効率のよいチケット付き学習スキームを提供する。
  論文  参考訳（メタデータ） (2023-06-27T18:54:40Z)
• Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization [39.51923275855131]
  本研究では,テスト時間における逆例に頑健な予測器の学習問題に対して,最小限の最適学習器を提案する。 特に、強い否定的な意味で、モンタッサー、ハネケ、スレブロによって提案された頑健な学習者の亜最適性を示す。
  論文  参考訳（メタデータ） (2022-09-15T15:32:42Z)
• Realizable Learning is All You Need [21.34668631009594]
  実現可能かつ不可知的な学習可能性の同値性は、学習理論における基本的な現象である。 実現可能かつ不可知な学習可能性の同値性を説明する最初のモデルに依存しないフレームワークを提示する。
  論文  参考訳（メタデータ） (2021-11-08T19:00:00Z)
• Exploring Bayesian Deep Learning for Urgent Instructor Intervention Need in MOOC Forums [58.221459787471254]
  大規模なオープンオンラインコース(MOOC)は、その柔軟性のおかげで、eラーニングの一般的な選択肢となっている。 多くの学習者とその多様な背景から、リアルタイムサポートの提供は課税されている。 MOOCインストラクターの大量の投稿と高い作業負荷により、インストラクターが介入を必要とするすべての学習者を識別できる可能性は低いです。 本稿では,モンテカルロドロップアウトと変分推論という2つの手法を用いて,学習者によるテキスト投稿のベイジアン深層学習を初めて検討する。
  論文  参考訳（メタデータ） (2021-04-26T15:12:13Z)
• Constrained Learning with Non-Convex Losses [119.8736858597118]
  学習は現代の情報処理の中核技術になっているが、バイアス、安全でない、偏見のあるソリューションにつながるという証拠はたくさんある。
  論文  参考訳（メタデータ） (2021-03-08T23:10:33Z)
• Probably Approximately Correct Constrained Learning [135.48447120228658]
  我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。 PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。 このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
  論文  参考訳（メタデータ） (2020-06-09T19:59:29Z)

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

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