Fugu-MT 論文翻訳(概要): The optimal information complexity of VC learning

論文の概要: The optimal information complexity of VC learning

arxiv url: http://arxiv.org/abs/2610.10600v1
Date: Tue, 06 Oct 2026 22:58:21 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-10 02:36:53.560918
Title: The optimal information complexity of VC learning
Title（参考訳）: VC学習における最適情報複雑性
Abstract要約: Steinke と Zakynthinou (2020) は、学習アルゴリズムの情報複雑さを解析する Conditional Mutual Information (CMI) フレームワークを導入した。本稿では,eCMI が順 O(d) である学習アルゴリズムを構築することにより,VC クラスに対する最適 PAC 保証を回復可能であることを示す。
参考スコア（独自算出の注目度）: 29.919066635725923
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Steinke and Zakynthinou(2020) introduces the Conditional Mutual Information (CMI) framework of analyzing the information complexity of learning algorithms based on algorithm-dependent information-theoretic quantities. We study one of these quantities, the evaluated Conditional Mutual Information (eCMI). It has been an interesting question whether the optimal PAC guarantee for VC classes can be recovered from the algorithm-dependent analyses via CMI. And we show that it is possible to recover this guarantee by constructing a learning algorithm whose eCMI is of order O(d) in the realizable case, where d is the VC-dimension of the concept class. Specially, our algorithm is a randomized Majority-of-5 base learners with optimal in-expectation generalization guarantee.
Abstract（参考訳）: Steinke と Zakynthinou (2020) は、アルゴリズム依存の情報理論量に基づいて学習アルゴリズムの情報複雑性を分析するための条件付き相互情報(CMI)フレームワークを導入した。評価された条件相互情報(eCMI)について検討する。 CMIによるアルゴリズム依存分析から,VCクラスに対する最適PAC保証を回収できるかどうか,興味深い問題となっている。また,eCMI が O(d) の次数である学習アルゴリズムを,d が概念クラスのVC次元であるような実現可能なケースで構築することで,この保証を回復可能であることを示す。特に,本アルゴリズムは,探索内一般化を最適に保証するランダム化された5進学習者である。

関連論文リスト

Indexed Bellman Information Complexity [5.082462420126421]
本稿では,情報指標と参照履歴に着目した対話的意思決定の表現レベル理論を開発する。我々は、DECは、普遍的に厳密な変換機構ではなく、インデックス付きベルマン情報複雑性の一段階緩和とみなすのが最適であることを示す。
論文参考訳（メタデータ） (2026-06-09T17:49:09Z)
Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
論文参考訳（メタデータ） (2023-06-21T16:04:03Z)
Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文参考訳（メタデータ） (2023-04-12T14:51:47Z)
Information Theoretic Lower Bounds for Information Theoretic Upper Bounds [14.268363583731848]
コンベックス最適化の文脈における出力モデルと経験的一般化の関係について検討する。本研究は,真のリスク最小化には相互情報が必要であることを明らかにする。既存の情報理論の一般化境界は、SGDや正規化などのアルゴリズムの能力を捉えるのに不足している。
論文参考訳（メタデータ） (2023-02-09T20:42:36Z)
Multivariate Systemic Risk Measures and Computation by Deep Learning Algorithms [63.03966552670014]
本稿では,主観的最適度と関連するリスク割り当ての公平性に着目し,重要な理論的側面について論じる。私たちが提供しているアルゴリズムは、予備項の学習、二重表現の最適化、およびそれに対応する公正なリスク割り当てを可能にします。
論文参考訳（メタデータ） (2023-02-02T22:16:49Z)
On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
残余条件付き相互情報(loo-CMI)の新しい尺度に基づく教師付き学習アルゴリズムのための情報理論の一般化境界を導出する。他のCMI境界とは対照的に、我々のloo-CMI境界は容易に計算でき、古典的なout-out-out-cross-validationのような他の概念と関連して解釈できる。ディープラーニングのシナリオにおいて予測された一般化ギャップを評価することにより,境界の質を実証的に検証する。
論文参考訳（メタデータ） (2022-07-01T17:58:29Z)
An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文参考訳（メタデータ） (2021-11-30T17:08:53Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)
Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文参考訳（メタデータ） (2020-07-06T15:20:17Z)
Reasoning About Generalization via Conditional Mutual Information [26.011933885798506]
我々は、Mutual Information (CMI) を用いて、入力がどの程度の精度で認識できるかを定量化する。 CMIのバウンダリは,VC次元,圧縮スキーム,差分プライバシー,その他の手法から得られることを示す。次に、有界な CMI は様々な種類の一般化を意味することを示す。
論文参考訳（メタデータ） (2020-01-24T18:13:04Z)

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