論文の概要: Two Dimensions Govern Agnostic Multiclass Transductive Learning

• arxiv url: http://arxiv.org/abs/2608.25326v1
• Date: Wed, 26 Aug 2026 03:15:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-27 14:15:15.547081
• Title: Two Dimensions Govern Agnostic Multiclass Transductive Learning
• Title（参考訳）: 2次元の非依存型多クラストランスダクティブ学習
• Abstract要約: 帰納的分類では、敵はラベル付き人口を固定し、1つのラベルは均一に隠され、学習者は残りの全てのラベルを見る。 バイナリクラスでは、トランスダクティブとPAC学習は同じミニマックスレートを持つ。 我々は、この有限人口分割における実現可能な圧縮、ラベル空間の縮小、および内部メニュー圧縮を組み合わせる。
• 参考スコア（独自算出の注目度）: 1.14219428942199
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In transductive classification, an adversary fixes a labeled population, one label is hidden uniformly, and the learner sees all remaining labels. For binary classes, agnostic transductive and PAC learning have the same minimax rate. Whether this extends to multiclass learning was open, especially for unbounded label spaces where uniform convergence can fail. We resolve the question up to logarithmic factors. For every multiclass class $\mathcal H$ with DS dimension $d_{DS}$ and Natarajan dimension $d_{\mathrm N}$, the optimal agnostic transductive excess error satisfies $\widetildeΘ\left(\frac{d_{DS}}{n}+\sqrt{\frac{d_{\mathrm N}}{n}}\right).$ The result holds for arbitrary label spaces. The two terms are both necessary. A DS pseudo-cube gives the realizable $d_{DS}/n$ obstruction, while a Natarajan cube with repeated points and fair labels gives the agnostic $\sqrt{d_{\mathrm N}/n}$ obstruction. The upper bound uses a random-reservation principle. The learner deliberately ignores a constant fraction of the visible labels, which makes the true test point uniform in a large unseen block. We combine realizable compression, a label-space reduction, and inside-menu agnostic compression across this finite-population split. A new without-replacement multiplicative-weights lemma preserves the fast $d_{DS}/n$ term. Consequently, agnostic multiclass PAC and transductive learning obey the same two-dimension law up to logarithmic factors.
• Abstract（参考訳）: 帰納的分類では、敵はラベル付き人口を固定し、1つのラベルは均一に隠され、学習者は残りの全てのラベルを見る。 バイナリクラスでは、非依存的トランスダクティブとPAC学習は同じミニマックスレートを持つ。 これがマルチクラス学習に拡張されるかどうかは、特に一様収束が失敗する可能性のある非有界ラベル空間において明らかである。 私たちはその問題を対数的要因まで解決する。 DS 次元 $d_{DS}$ とNatarajan 次元 $d_{\mathrm N}$ を持つ任意の多クラスクラス $\mathcal H$ に対して、最適アグノスティックな帰納的過剰誤差は $\widetilde\left(\frac{d_{DS}}{n}+\sqrt {\frac{d_{\mathrm N}}{n}}\right) を満たす。 結果は任意のラベル空間に対して保持される。 どちらの条件も必要である。 DS擬キューブは実現可能な$d_{DS}/n$障害物を与えるが、繰り返し点とフェアラベルを持つナタラジャン立方体は agnostic $\sqrt{d_{\mathrm N}/n}$障害物を与える。 上界はランダム保存原理を用いる。 学習者は、目に見えるラベルの一定部分を無視して、真のテストポイントを大きな目に見えないブロックで均一にする。 我々は、この有限集団分割による実現可能な圧縮、ラベル空間の縮小、および内部メニューに依存しない圧縮を組み合わせる。 新しい非置換乗法的重み付け補題は、高速な$d_{DS}/n$項を保存する。 その結果、非依存的多クラスPACとトランスダクティブラーニングは対数的要因まで同じ2次元法則に従う。

関連論文リスト

• Optimistic Rates for Multiclass PAC Learning [39.91890433860882]
  最悪のマルチクラス境界は、最高の分類器が既にほぼ正しいときに小さくならない。 ナタラジャン次元のクラス $d_N$ と Daniely-Shalev-Shwartz 次元 $d_DS$ に対して、最適余剰リスクは2つのエンドポイントで知られている。 固定オラクルリスクが$Lstar$であれば、最適な過剰リスクは$widetilde(sqrtLstar d_N/n+d_DS/n)$で、アルファベットサイズは一様である。
  論文  参考訳（メタデータ） (2026-08-11T12:46:03Z)
• The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought [8.076068840853512]
  完全自己回帰的チェイン・オブ・サートトレースに対する完全トレース学習のサンプルの複雑さは、局所的な次トーケンクラスの標準マルチクラスレートによって上限づけられていることを証明する。 しかし、停止ルールの$mathtthalt$とすべてのポイントワイズ$mathtthalt$-haltingローカルクラスに対して。 $operatornameDSdim(mathrmH)$への依存は最悪のケース最適である。
  論文  参考訳（メタデータ） (2026-07-08T13:49:54Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds [16.636823007179082]
  我々は, [Goel et al. 2017] が導入した対戦型インジェクションモデルを用いてオンライン学習を研究する。 一致する$(sqrtT)$ down bound for VC dimension $1$を証明し、2つの情報体制の鮮明な分離を確立します。 敵の汚染に対する耐性が保たれていることを予測するためのラベル付きサンプルの小さなサブセットである、インプロバストな目撃者によって駆動される潜在的基盤フレームワークを導入する。
  論文  参考訳（メタデータ） (2026-02-23T18:30:48Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• Towards Fundamental Limits for Active Multi-distribution Learning [16.639855803241524]
  我々は,多分布学習のための新しいアルゴリズムを開発し,ラベルの複雑さを向上する。 実現可能な設定のバウンダリは情報理論的に最適であり、設定の$knu/varepsilon2$項は適切な学習者にとって基本的なものであることを示す。
  論文  参考訳（メタデータ） (2025-06-21T06:08:58Z)
• Multiclass Transductive Online Learning [14.093228102168872]
  本稿では,ラベルの数が無制限である場合のオンライン学習の帰納的課題について考察する。 レベル制約されたリトルストーン次元と呼ばれる新しい次元は、この設定におけるオンライン学習可能性の特徴である。 ラベル空間が非有界である場合でも、期待されるミス回数の最小値の3分法が保たれることを示す。
  論文  参考訳（メタデータ） (2024-11-03T16:57:13Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Agnostic Multi-Group Active Learning [24.97598179536084]
  能動的学習の観点から,この問題の変種を考察し,学習者がコレクションの各分布からどの例をラベル付けするかを判断する権限を付与する。 我々の主な課題は、不一致に基づくアクティブラーニングのような標準的なアクティブラーニング技術が、マルチグループラーニングの目的に直接適用されないことである。 既存のアルゴリズムを改良し、多群学習の非依存的な定式化のための一貫した能動的学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-06-02T21:24:13Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)

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

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