論文の概要: Effective Littlestone Dimension
- arxiv url: http://arxiv.org/abs/2411.15109v1
- Date: Fri, 22 Nov 2024 18:11:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-25 15:02:37.895990
- Title: Effective Littlestone Dimension
- Title（参考訳）: 有効リトルストーン次元
- Authors: Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer,
- Abstract要約: 有限効用Littlestone次元は計算可能なオンライン学習に必要な条件であることを示す。
実効的なリトルストーン次元は、2つの特別な場合における計算可能学習者の最適誤りと等しい。
興味深いことに、有限実効的なリトルストーン次元もまた、クラスが計算可能な函数のみからなることを保証している。
- 参考スコア（独自算出の注目度）: 45.14832807541816
- License:
- Abstract: Delle Rose et al.~(COLT'23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learners. In this paper, we introduce and study a similar effectivization of the notion of Littlestone dimension. Finite effective Littlestone dimension is a necessary condition for computable online learning but is not a sufficient one -- which we already establish for classes of the effective Littlestone dimension 2. However, the effective Littlestone dimension equals the optimal mistake bound for computable learners in two special cases: a) for classes of Littlestone dimension 1 and b) when the learner receives as additional information an upper bound on the numbers to be guessed. Interestingly, finite effective Littlestone dimension also guarantees that the class consists only of computable functions.
- Abstract（参考訳）: Delle Rose et al ~(COLT'23)は、Vapnik-Chervonenkis次元の効果的なバージョンを導入し、計算可能な全学習者による不適切なPAC学習を特徴付けることを示した。
本稿では,リトルストーン次元の概念の同様の効果について紹介し,考察する。
有限効用リトルストーン次元は計算可能なオンライン学習に必要な条件であるが、十分ではない。
しかし、実効的なリトルストーン次元は、2つの特別な場合において計算可能学習者の最適誤りと等しい。
a) リトルストーン次元1のクラスと
b) 学習者が推測すべき数字の上限を追加情報として受け取るとき。
興味深いことに、有限実効的なリトルストーン次元もまた、クラスが計算可能な函数のみからなることを保証している。
関連論文リスト
- Golden Ratio-Based Sufficient Dimension Reduction [6.184279198087624]
本稿では,ニューラルネットワークを用いた十分次元削減手法を提案する。
構造次元を効果的に特定し、中心空間をうまく推定する。
これは、バロンクラスの関数に対するニューラルネットワークの近似能力の利点を生かし、計算コストの削減につながる。
論文 参考訳（メタデータ） (2024-10-25T04:15:15Z) - Applications of Littlestone dimension to query learning and to
compression [1.9336815376402723]
我々は、ランダムな反例を持つ同値クエリによる学習のために、2017年のシアングルインのモデルを拡張した。
第二に、このモデルを無作為性のある無限の概念クラスに拡張する。
第三に、Littlestone次元と拡張$d$-compressionスキームを持つクラスとの関係に関する改善された結果を与える。
論文 参考訳（メタデータ） (2023-10-07T14:04:18Z) - Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。
まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。
オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
論文 参考訳（メタデータ） (2023-07-07T21:39:25Z) - Ticketed Learning-Unlearning Schemes [57.89421552780526]
そこで我々は,学習のためのチケット付きモデルを提案する。
広義のコンセプトクラスに対して,空間効率のよいチケット付き学習スキームを提供する。
論文 参考訳（メタデータ） (2023-06-27T18:54:40Z) - Multiclass Online Learning and Uniform Convergence [34.21248304961989]
対戦型オンライン学習環境におけるマルチクラス分類について検討する。
任意のマルチクラスの概念クラスが、そのリトルストーン次元が有限である場合に限り、不可知的に学習可能であることを証明する。
論文 参考訳（メタデータ） (2023-03-30T21:35:48Z) - A Survey of Learning on Small Data: Generalization, Optimization, and
Challenge [101.27154181792567]
ビッグデータの一般化能力を近似した小さなデータについて学ぶことは、AIの究極の目的の1つである。
この調査はPACフレームワークの下でのアクティブサンプリング理論に従い、小さなデータにおける学習の一般化誤差とラベルの複雑さを分析した。
効率的な小さなデータ表現の恩恵を受けるかもしれない複数のデータアプリケーションについて調査する。
論文 参考訳（メタデータ） (2022-07-29T02:34:19Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z) - Near-tight closure bounds for Littlestone and threshold dimensions [59.245101116396555]
二つの仮説クラスのリトルストーンおよびしきい値次元の閉包特性について検討する。
我々の上界は、アロンらによって示される類似境界に対して指数的($k$で)改善を与える。
論文 参考訳（メタデータ） (2020-07-07T17:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。