論文の概要: Prediction, Learning, Uniform Convergence, and Scale-sensitive
Dimensions
- arxiv url: http://arxiv.org/abs/2304.11059v2
- Date: Mon, 24 Apr 2023 17:06:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-25 11:12:18.591592
- Title: Prediction, Learning, Uniform Convergence, and Scale-sensitive
Dimensions
- Title（参考訳）: 予測・学習・一様収束・スケール感応次元
- Authors: Peter L. Bartlett and Philip M. Long
- Abstract要約: 本稿では,$[0,1]$-valued関数のクラスを学習するための新しい汎用アルゴリズムを提案する。
このアルゴリズムの絶対誤差の一般上界を証明した。
本研究は, 学習の複雑さに関する一般化された一般境界を得るために, 両方のパッキングバウンドをどう適用するかを示す。
- 参考スコア（独自算出の注目度）: 39.97534972432276
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We present a new general-purpose algorithm for learning classes of
$[0,1]$-valued functions in a generalization of the prediction model, and prove
a general upper bound on the expected absolute error of this algorithm in terms
of a scale-sensitive generalization of the Vapnik dimension proposed by Alon,
Ben-David, Cesa-Bianchi and Haussler. We give lower bounds implying that our
upper bounds cannot be improved by more than a constant factor in general. We
apply this result, together with techniques due to Haussler and to Benedek and
Itai, to obtain new upper bounds on packing numbers in terms of this
scale-sensitive notion of dimension. Using a different technique, we obtain new
bounds on packing numbers in terms of Kearns and Schapire's fat-shattering
function. We show how to apply both packing bounds to obtain improved general
bounds on the sample complexity of agnostic learning. For each $\epsilon > 0$,
we establish weaker sufficient and stronger necessary conditions for a class of
$[0,1]$-valued functions to be agnostically learnable to within $\epsilon$, and
to be an $\epsilon$-uniform Glivenko-Cantelli class.
This is a manuscript that was accepted by JCSS, together with a correction.
- Abstract（参考訳）: 予測モデルの一般化における$[0,1]$値関数のクラスを学習するための新しい汎用アルゴリズムを提案し、Alon, Ben-David, Cesa-Bianchi, Hausslerによって提案されたVapnik次元のスケール敏感な一般化の観点から、このアルゴリズムの予測絶対誤差の一般上限を証明した。
下限を与えるということは、上限は一般に定数因子以上では改善できないことを意味する。
この結果とハウスラーとベネデックとイタイによる手法を併用して、このスケールに敏感な次元の概念を用いて、荷造り数上の新たな上限を求める。
異なる手法を用いて、カーンズとシャファイアの脂肪散乱関数の観点から、パッキング数に関する新しい境界を求める。
そこで本研究では,パッキン境界とパッキング境界の両方を適用し,無知学習のサンプル複雑性に対する一般境界の改善について述べる。
それぞれの $\epsilon > 0$ に対して、$[0,1]$-valued 関数が $\epsilon$ 内で不可知的に学習され、$\epsilon$-uniform Glivenko-Cantelli クラスとなるために、より弱くより強い必要条件を確立する。
これはjcssが修正とともに受け入れた写本である。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Local Borsuk-Ulam, Stability, and Replicability [16.6959756920423]
また,PAC設定では,リストリプリケータとグローバルな安定学習の両方が不可能であることを示す。
具体的には、有限類におけるリストの複製性と大域的安定性数に対する最適境界を確立する。
論文 参考訳（メタデータ） (2023-11-02T21:10:16Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Learning Algorithm Generalization Error Bounds via Auxiliary Distributions [16.44492672878356]
一般化エラー境界は、機械学習モデルがどのように機能するかを理解するのに不可欠である。
そこで本研究では,Auxiliary Distribution Methodという新たな手法を提案する。
論文 参考訳（メタデータ） (2022-10-02T10:37:04Z) - Localization, Convexity, and Star Aggregation [0.0]
オフセットラデマッハ複体は、正方形損失に対する鋭く線形依存的な上界を示すことが示されている。
統計的設定では、オフセット境界は一定の均一な凸性を満たす任意の損失に一般化可能であることを示す。
論文 参考訳（メタデータ） (2021-05-19T00:47:59Z) - On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and
Fourier-based Algorithms [10.66048003460524]
構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。
0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
論文 参考訳（メタデータ） (2021-02-11T21:28:55Z) - Q-learning with Uniformly Bounded Variance: Large Discounting is Not a
Barrier to Fast Learning [7.6146285961466]
我々は、すべての$gamma 1$に対して一様に束縛されたサンプル複雑性を持つ新しいアルゴリズムのクラスを導入する。
最適化されたステップサイズシーケンスとQ-ラーニングアルゴリズムの共分散は、1/(1-ガンマ)$の二次関数であることを示す。
論文 参考訳（メタデータ） (2020-02-24T15:12:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。