論文の概要: Optimal PAC Bounds Without Uniform Convergence
- arxiv url: http://arxiv.org/abs/2304.09167v1
- Date: Tue, 18 Apr 2023 17:57:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-19 13:46:04.438173
- Title: Optimal PAC Bounds Without Uniform Convergence
- Title（参考訳）: 一様収束のない最適PAC境界
- Authors: Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita
Zhivotovskiy
- Abstract要約: 我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。
我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。
具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
- 参考スコア（独自算出の注目度）: 11.125968799758436
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In statistical learning theory, determining the sample complexity of
realizable binary classification for VC classes was a long-standing open
problem. The results of Simon and Hanneke established sharp upper bounds in
this setting. However, the reliance of their argument on the uniform
convergence principle limits its applicability to more general learning
settings such as multiclass classification. In this paper, we address this
issue by providing optimal high probability risk bounds through a framework
that surpasses the limitations of uniform convergence arguments.
Our framework converts the leave-one-out error of permutation invariant
predictors into high probability risk bounds. As an application, by adapting
the one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth, we
propose an algorithm that achieves an optimal PAC bound for binary
classification. Specifically, our result shows that certain aggregations of
one-inclusion graph algorithms are optimal, addressing a variant of a classic
question posed by Warmuth.
We further instantiate our framework in three settings where uniform
convergence is provably suboptimal. For multiclass classification, we prove an
optimal risk bound that scales with the one-inclusion hypergraph density of the
class, addressing the suboptimality of the analysis of Daniely and
Shalev-Shwartz. For partial hypothesis classification, we determine the optimal
sample complexity bound, resolving a question posed by Alon, Hanneke, Holzman,
and Moran. For realizable bounded regression with absolute loss, we derive an
optimal risk bound that relies on a modified version of the scale-sensitive
dimension, refining the results of Bartlett and Long. Our rates surpass
standard uniform convergence-based results due to the smaller complexity
measure in our risk bound.
- Abstract（参考訳）: 統計的学習理論では、vcクラスで実現可能なバイナリ分類のサンプル複雑性を決定することは長年のオープン問題であった。
Simon と Hanneke の結果は、この設定で鋭い上界を確立した。
しかし、一様収束原理へのそれらの議論の依存は、多クラス分類のようなより一般的な学習環境に適用性を制限する。
本稿では,一様収束論の限界を超えるフレームワークを通じて,最適な高確率リスク境界を提供することによってこの問題に対処する。
本フレームワークは置換不変量予測器の残欠誤差を高い確率リスク境界に変換する。
本研究では,haussler,littlestone,warmuth の 1-inclusion graph アルゴリズムを適用し,二分分類に最適なpacバウンドを実現するアルゴリズムを提案する。
具体的には,Warmuthによる古典的問題に対処するため,一括グラフアルゴリズムのある種の集約が最適であることを示す。
さらに、一様収束が確実に最適である3つの設定でフレームワークをインスタンス化する。
多クラス分類では、クラスの一介在超グラフ密度でスケールする最適リスク境界を証明し、ダニーとシャレフ=シュワルツの分析の準最適性に対処する。
部分的仮説分類では, alon, hanneke, holzman, moranによって提起された質問を解き, 最適なサンプル複雑性を決定づける。
絶対損失のある実現可能な有界回帰に対しては、スケール感性次元の修正版に依存する最適リスク境界を導出し、バートレットとロングの結果を精査する。
リスクバウンドの複雑さの指標が小さいため、標準の均一収束に基づく結果を上回っます。
関連論文リスト
- Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - The One-Inclusion Graph Algorithm is not Always Optimal [11.125968799758436]
本稿では,Vapnik-Chervonenkisクラスに対する探索的一括グラフアルゴリズムを提案する。
我々は,近年の予測手法により,同じ低い高確率性能が継承されていることを示す。
論文 参考訳（メタデータ） (2022-12-19T06:49:39Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Sharp global convergence guarantees for iterative nonconvex
optimization: A Gaussian process perspective [30.524043513721168]
回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。
決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。
我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
論文 参考訳（メタデータ） (2021-09-20T21:48:19Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。
我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
論文 参考訳（メタデータ） (2021-05-13T18:24:30Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。