論文の概要: Transductive Learning Is Compact

• arxiv url: http://arxiv.org/abs/2402.10360v3
• Date: Wed, 30 Oct 2024 06:33:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-31 14:23:44.411681
• Title: Transductive Learning Is Compact
• Title（参考訳）: トランスダクティブ学習はコンパクトである
• Authors: Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng,
• Abstract要約: 一般の損失関数を用いた教師あり学習において, 広範に保持されるコンパクト性結果を示す。 不適切な計量損失を伴う実現可能な学習のために、サンプルの複雑さの正確なコンパクトさは失敗する可能性があることを示す。 我々は、無知の場合においてより大きなギャップが可能であると推測する。
• 参考スコア（独自算出の注目度）: 10.168670899305232
• License:
• Abstract: We demonstrate a compactness result holding broadly across supervised learning with a general class of loss functions: Any hypothesis class $H$ is learnable with transductive sample complexity $m$ precisely when all of its finite projections are learnable with sample complexity $m$. We prove that this exact form of compactness holds for realizable and agnostic learning with respect to any proper metric loss function (e.g., any norm on $\mathbb{R}^d$) and any continuous loss on a compact space (e.g., cross-entropy, squared loss). For realizable learning with improper metric losses, we show that exact compactness of sample complexity can fail, and provide matching upper and lower bounds of a factor of 2 on the extent to which such sample complexities can differ. We conjecture that larger gaps are possible for the agnostic case. Furthermore, invoking the equivalence between sample complexities in the PAC and transductive models (up to lower order factors, in the realizable case) permits us to directly port our results to the PAC model, revealing an almost-exact form of compactness holding broadly in PAC learning.
• Abstract（参考訳）: すべての仮説クラス$H$は、すべての有限射影が標本複雑性$m$で学習可能であれば、正確には、半帰納的標本複雑性$m$で学習可能である。 この厳密なコンパクト性は、任意の適切な計量損失函数(例えば、$\mathbb{R}^d$のノルム)およびコンパクト空間上の任意の連続損失(例えば、クロスエントロピー、正方形損失)に関して、実現可能かつ非依存的な学習に成り立つことを証明している。 不適切な計量損失を伴う実現可能な学習のために、サンプルの複雑さの正確なコンパクト性は失敗しうることを示し、そのようなサンプルの複雑さが相違する程度で2の係数の上と下の境界が一致することを示す。 我々は、無知の場合においてより大きなギャップが可能であると推測する。 さらに、PACのサンプル複雑度とトランスダクティブモデル(実現可能な場合、低次因子まで)の等価性を呼び出すことで、結果を直接PACモデルに移植することが可能となり、PAC学習において広く保持されるほぼ正確なコンパクト性の形式が明らかになる。

関連論文リスト

• Is Transductive Learning Equivalent to PAC Learning? [0.9012198585960443]
  PACモデルとトランスダクティブモデルは、本質的には非依存のバイナリ分類に等価であることを示す。 我々は,2番目の結果が2進分類を超えて拡張可能かどうかという興味深い疑問を残して,トランスダクティブモデルとPACモデルがより広範に等価であることを示す。
  論文  参考訳（メタデータ） (2024-05-08T16:26:49Z)
• On Representation Complexity of Model-based and Model-free Reinforcement Learning [11.843778337443824]
  回路複雑性の文脈におけるモデルベースおよびモデルフリー強化学習(RL)の表現複雑性について検討した。 理論的には、その基底となる遷移関数と報酬関数が、大きさの一定深さの回路で表現できるような、幅広い種類のMDPが存在することを証明している。 近似誤差に注意を向け、複雑性理論への接続を構築することによって、モデルベースのアルゴリズムが、新しい表現複雑性の観点からモデルフリーアルゴリズムよりも、なぜサンプルの複雑さを楽しむのかというユニークな洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-03T00:01:58Z)
• On Learning Latent Models with Multi-Instance Weak Supervision [57.18649648182171]
  本稿では,複数の入力インスタンスに関連付けられた遷移関数$sigma$ラベルによって,教師信号が生成される弱い教師付き学習シナリオについて考察する。 我々の問題は、潜在的な構造学習やニューロシンボリックな統合など、さまざまな分野で満たされている。
  論文  参考訳（メタデータ） (2023-06-23T22:05:08Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency [105.17746223041954]
  部分的に観察されたマルコフ決定過程(POMDP)における強化学習は2つの課題に直面している。 しばしば、未来を予測するのに完全な歴史を要し、地平線と指数関数的にスケールするサンプルの複雑さを誘導する。 本稿では,2段階の表現を最適化しながら学習するETC(Embed to Control)という強化学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-26T16:34:46Z)
• Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability [7.727052811126007]
  結果の不一致性において、目標は、ターゲット予測子と区別できない予測子を出力することである。 結果の不一致性のサンプル複雑性は、$P$ w.r.tの計量エントロピーによって特徴づけられる。 この同値性は凸幾何学における長年の計量エントロピー双対性予想と興味深い関係を持つ。
  論文  参考訳（メタデータ） (2022-03-09T06:02:31Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)
• The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model [11.821892196198457]
  我々は$d$-bitパリティ関数の学習のサンプル複雑さが$Omega (2d/2)$であることを示した。 また、単純なシャッフルモデルプロトコルをスケッチし、その結果が$poly(d)$ factorにきついことを示す。
  論文  参考訳（メタデータ） (2021-03-29T15:26:02Z)
• Enhanced Principal Component Analysis under A Collaborative-Robust Framework [89.28334359066258]
  重み学習とロバストな損失を非自明な方法で組み合わせる,一般的な協調ロバスト重み学習フレームワークを提案する。 提案されたフレームワークでは、トレーニング中の重要度を示す適切なサンプルの一部のみがアクティブになり、エラーが大きい他のサンプルは無視されません。 特に、不活性化試料の負の効果はロバスト損失関数によって軽減される。
  論文  参考訳（メタデータ） (2021-03-22T15:17:37Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)

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

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