Fugu-MT 論文翻訳(概要): On the Information Complexity of Proper Learners for VC Classes in the Realizable Case

論文の概要: On the Information Complexity of Proper Learners for VC Classes in the Realizable Case

arxiv url: http://arxiv.org/abs/2011.02970v1
Date: Thu, 5 Nov 2020 16:55:33 GMT
ステータス: 処理完了
システム内更新日: 2022-09-29 12:59:07.741830
Title: On the Information Complexity of Proper Learners for VC Classes in the Realizable Case
Title（参考訳）: vcクラスにおける適切な学習者の情報複雑性について
Authors: Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, Daniel M. Roy
Abstract要約: Vapnik-Chervonenkis (VC) クラスの固有学習者の条件付き相互情報(CMI)は$d log n + 2$ から$O(d)$ に改善できないことを示す。
参考スコア（独自算出の注目度）: 37.49575289458763
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We provide a negative resolution to a conjecture of Steinke and Zakynthinou (2020a), by showing that their bound on the conditional mutual information (CMI) of proper learners of Vapnik--Chervonenkis (VC) classes cannot be improved from $d \log n +2$ to $O(d)$, where $n$ is the number of i.i.d. training examples. In fact, we exhibit VC classes for which the CMI of any proper learner cannot be bounded by any real-valued function of the VC dimension only.
Abstract（参考訳）: スタインケとザキンチヌー (2020a) の予想に対する負の解決として、vapnik--chervonenkis (vc) クラスの適切な学習者の条件付き相互情報 (cmi) の束縛が $d \log n +2$ から $o(d)$ に改善されないことを示し、ここで $n$ は i.i.d. のトレーニング例の数である。実際、我々は任意の適切な学習者のcmiがvc次元の任意の実数値関数に制限されないvcクラスを示す。

関連論文リスト

Toward Automatic Relevance Judgment using Vision--Language Models for Image--Text Retrieval Evaluation [56.49084589053732]
VLM(Vision-Language Models)は、様々なアプリケーションで成功を収めてきたが、関連性判断を支援する可能性はまだ不明である。本稿では,CLIP,LLaVA,GPT-4Vを含むVLMの関連性評価機能について,ゼロショット方式でマルチメディアコンテンツ作成に適した大規模テキスト分割ホック検索タスクで評価する。
論文参考訳（メタデータ） (2024-08-02T16:15:25Z)
Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization [36.28082578445787]
我々は,円錐曲線最適化(SCO)の文脈における記憶と学習の相互作用について検討する。我々は,Steinke と Zakynthinou が提唱した条件付き相互情報(CMI)の枠組みを用いた記憶の定量化(2020年) L2$ Lipschitz-bounded set and under strong convexity, every learner with a excess error have CMI bounded by $Omega (1/varepsilon2)$ and $Omega (1/varepsilon)$。
論文参考訳（メタデータ） (2024-02-14T17:17:30Z)
The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。 PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
論文参考訳（メタデータ） (2023-07-22T18:02:53Z)
Class-Incremental Learning: A Survey [84.30083092434938]
CIL(Class-Incremental Learning)は、学習者が新しいクラスの知識を段階的に取り入れることを可能にする。 CILは、前者の特徴を壊滅的に忘れる傾向にあり、その性能は劇的に低下する。ベンチマーク画像分類タスクにおける17の手法の厳密で統一的な評価を行い、異なるアルゴリズムの特徴を明らかにする。
論文参考訳（メタデータ） (2023-02-07T17:59:05Z)
Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-30T17:26:39Z)
A Characterization of List Learnability [15.368858716555888]
我々は、$k$の予測リストを出力することを目標とするPAC学習について検討する。最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。
論文参考訳（メタデータ） (2022-11-07T21:28:05Z)
Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
論文参考訳（メタデータ） (2022-10-11T13:54:41Z)
Conditional Prompt Learning for Vision-Language Models [107.06776396086471]
近ごろ提案されたContext Optimization (CoOp) は、文脈単語をプロンプトで学習可能なベクトルの集合に変換する。 CoOpは、CoOpよりもはるかに優れたクラスを非表示に一般化し、単一のデータセットを超える有望な転送可能性を示している。我々の実験によると、CoCoOpはCoOpよりもはるかに優れたクラスに一般化しており、単一のデータセットを超える有望な転送可能性を示している。
論文参考訳（メタデータ） (2022-03-10T18:59:41Z)
Towards a Unified Information-Theoretic Framework for Generalization [43.23033319683591]
まず、このフレームワークを用いて、任意の学習アルゴリズムに対して非自明な(しかし、準最適)境界を表現できることを実証する。我々は、CMIフレームワークが、ハーフスペースを学習するためのSVM(Support Vector Machines)の予測されるリスクに最適な境界をもたらすことを証明した。
論文参考訳（メタデータ） (2021-11-09T17:09:40Z)
A Theory of Usable Information Under Computational Constraints [103.5901638681034]
本稿では,複雑なシステムにおける情報推論のための新しいフレームワークを提案する。我々の基礎はシャノンの情報理論の変分拡張に基づいている。計算制約を組み込むことで,データから$mathcalV$-informationを確実に推定できることを示す。
論文参考訳（メタデータ） (2020-02-25T06:09:30Z)

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