論文の概要: Fine-Grained Distribution-Dependent Learning Curves
- arxiv url: http://arxiv.org/abs/2208.14615v1
- Date: Wed, 31 Aug 2022 03:29:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-01 13:16:40.383379
- Title: Fine-Grained Distribution-Dependent Learning Curves
- Title(参考訳): 細粒度分布依存学習曲線
- Authors: Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, Ilya
Tolstikhin
- Abstract要約: 学習曲線はラベル付き入力サンプル数の関数として学習アルゴリズムの予測誤差をプロットする。
本稿では,Bousquet et alの最近の成果を改良し,改良する,粒状PACと呼ばれる新しい次元特性について紹介する。
我々の特徴は、きめ細かい境界を提供することによって学習曲線の構造に新たな光を当てることである。
- 参考スコア(独自算出の注目度): 27.09513298165498
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Learning curves plot the expected error of a learning algorithm as a function
of the number of labeled input samples. They are widely used by machine
learning practitioners as a measure of an algorithm's performance, but classic
PAC learning theory cannot explain their behavior. In this paper we introduce a
new combinatorial characterization called the VCL dimension that improves and
refines the recent results of Bousquet et al. (2021). Our characterization
sheds new light on the structure of learning curves by providing fine-grained
bounds, and showing that for classes with finite VCL, the rate of decay can be
decomposed into a linear component that depends only on the hypothesis class
and an exponential component that depends also on the target distribution. In
particular, the finer nuance of the VCL dimension implies lower bounds that are
quantitatively stronger than the bounds of Bousquet et al. (2021) and
qualitatively stronger than classic 'no free lunch' lower bounds. The VCL
characterization solves an open problem studied by Antos and Lugosi (1998), who
asked in what cases such lower bounds exist. As a corollary, we recover their
lower bound for half-spaces in $\mathbb{R}^d$, and we do so in a principled way
that should be applicable to other cases as well. Finally, to provide another
viewpoint on our work and how it compares to traditional PAC learning bounds,
we also present an alternative formulation of our results in a language that is
closer to the PAC setting.
- Abstract(参考訳): 学習曲線はラベル付き入力サンプル数の関数として学習アルゴリズムの期待誤差をプロットする。
機械学習の実践者がアルゴリズムのパフォーマンスの尺度として広く使われているが、古典的なPAC学習理論ではそれらの振る舞いを説明できない。
本稿では, Bousquet et al. (2021) の最近の結果を改善し, 改良する VCL 次元と呼ばれる新しい組合せ的特徴について述べる。
細粒度境界を提供することで学習曲線の構造に新たな光を当て、有限のvclを持つクラスでは、減衰率を仮説クラスのみに依存する線形成分と、対象分布に依存する指数成分に分解できることを示した。
特に、VCL次元のより細かいニュアンスは、Bousquet et al. (2021) の境界よりも定量的に強く、古典的な「無料ランチ」の下限よりも質的に強い下限を意味する。
VCL の特徴付けは、アントスとルゴシ (1998) によって研究された開問題を解く。
corollary として、$\mathbb{R}^d$ の半空間に対する下界を回復し、他のケースにも適用できるような原則化された方法でそれを行う。
最後に,我々の研究に対する別の視点と,従来のpac学習境界との比較について述べるために,pac設定に近い言語で結果の代替的な定式化も提示する。
関連論文リスト
- Imitation Learning in Discounted Linear MDPs without exploration assumptions [58.81226849657474]
ILARLと呼ばれる無限水平線形MDPにおける模倣学習のための新しいアルゴリズムを提案する。
特に、所望の精度$epsilon$から$mathcalObrepsilon-5$から$mathcalObrepsilon-4$への依存を改善します。
線形関数近似による数値実験により、ILARLは他のよく使われるアルゴリズムよりも優れていることが示された。
論文 参考訳(メタデータ) (2024-05-03T15:28:44Z) - Collaborative Learning with Different Labeling Functions [7.228285747845779]
我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。
データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
論文 参考訳(メタデータ) (2024-02-16T04:32:22Z) - Few-Shot Class-Incremental Learning with Prior Knowledge [94.95569068211195]
本稿では,事前学習モデルの一般化能力を高めるために,先行知識を用いた学習(LwPK)を提案する。
実験結果から,LwPKは破滅的忘れ込みに対するモデルレジリエンスを効果的に向上させることが示された。
論文 参考訳(メタデータ) (2024-02-02T08:05:35Z) - Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement
Learning with General Function Approximation [26.277745106128197]
一般関数近似を用いた強化学習における長期計画地平線問題に対処するアルゴリズムを提案する。
導出残差は、線形混合MDPを対数因子まで特殊化する場合のミニマックス下限と一致するため、エンフシャープと見なされる。
このような地平線に依存しない、インスタンスに依存しない、鋭い後悔に満ちたヒンジの達成は、(i)新しいアルゴリズム設計と(ii)きめ細かい解析に基づいている。
論文 参考訳(メタデータ) (2023-12-07T17:35:34Z) - Fine-grained analysis of non-parametric estimation for pairwise learning [9.676007573960383]
ペアワイズ学習における非パラメトリック推定の一般化性能について検討する。
我々の結果は、ランキング、AUC、ペアワイズ回帰、メートル法、類似性学習など、幅広いペアワイズ学習問題に対処するために利用できる。
論文 参考訳(メタデータ) (2023-05-31T08:13:14Z) - Tight Guarantees for Interactive Decision Making with the
Decision-Estimation Coefficient [51.37720227675476]
我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。
我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。
この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
論文 参考訳(メタデータ) (2023-01-19T18:24:08Z) - Chaos is a Ladder: A New Theoretical Understanding of Contrastive
Learning via Augmentation Overlap [64.60460828425502]
コントラスト学習の下流性能に関する新たな保証を提案する。
我々の新しい理論は、攻撃的なデータ強化の下で、異なるクラス内サンプルのサポートがより重なり合うという知見に基づいている。
本稿では、下流の精度とよく一致した教師なしモデル選択距離ARCを提案する。
論文 参考訳(メタデータ) (2022-03-25T05:36:26Z) - On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。
分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
論文 参考訳(メタデータ) (2022-02-28T13:01:04Z) - Sample-efficient L0-L2 constrained structure learning of sparse Ising
models [3.056751497358646]
スパースイジングモデルの基盤となるグラフを$n$ i.i.d.サンプルから$p$ノードで学習する問題を考察する。
濃度制約 L0 ノルムを有効に利用し、このノルムを L2 ノルムと組み合わせて非零係数をモデル化する。
論文 参考訳(メタデータ) (2020-12-03T07:52:20Z) - Provably Efficient Reward-Agnostic Navigation with Linear Value
Iteration [143.43658264904863]
我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。
そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
論文 参考訳(メタデータ) (2020-08-18T04:34:21Z) - Batch Value-function Approximation with Only Realizability [17.692408242465763]
バッチ強化学習(RL):探索データセットからQstar$を学習する。
我々のアルゴリズムであるBVFTは、トーナメントの手順を通じて硬さ予想(探索データというより強い概念の下では)を破る。
また、BVFTが他の拡張と開問題の間のモデル選択にどのように適用できるかについても論じる。
論文 参考訳(メタデータ) (2020-08-11T20:09:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。