論文の概要: Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension

• arxiv url: http://arxiv.org/abs/2302.13849v3
• Date: Thu, 17 Aug 2023 18:35:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-22 00:47:08.718504
• Title: Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
• Title（参考訳）: エキスパートアドバイザとランダム化リトルストーン次元を用いた最適予測
• Authors: Yuval Filmus, Steve Hanneke, Idan Mehalel and Shay Moran
• Abstract要約: 古典的な結果は、リトルストーン次元を用いた決定論的学習者によって達成可能な最適誤りを特徴づける。 クラス $mathcalH$ の学習における最適予測誤差は、そのランダム化されたリトルストーン次元と等しいことを示す。
• 参考スコア（独自算出の注目度）: 32.29254118429081
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an analogous result for randomized learners: we show that the optimal expected mistake bound in learning a class $\mathcal{H}$ equals its randomized Littlestone dimension, which is the largest $d$ for which there exists a tree shattered by $\mathcal{H}$ whose average depth is $2d$. We further study optimal mistake bounds in the agnostic case, as a function of the number of mistakes made by the best function in $\mathcal{H}$, denoted by $k$. We show that the optimal randomized mistake bound for learning a class with Littlestone dimension $d$ is $k + \Theta (\sqrt{k d} + d )$. This also implies an optimal deterministic mistake bound of $2k + \Theta(d) + O(\sqrt{k d})$, thus resolving an open question which was studied by Auer and Long ['99]. As an application of our theory, we revisit the classical problem of prediction using expert advice: about 30 years ago Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire and Warmuth studied prediction using expert advice, provided that the best among the $n$ experts makes at most $k$ mistakes, and asked what are the optimal mistake bounds. Cesa-Bianchi, Freund, Helmbold, and Warmuth ['93, '96] provided a nearly optimal bound for deterministic learners, and left the randomized case as an open problem. We resolve this question by providing an optimal learning rule in the randomized case, and showing that its expected mistake bound equals half of the deterministic bound of Cesa-Bianchi et al. ['93,'96], up to negligible additive terms. In contrast with previous works by Abernethy, Langford, and Warmuth ['06], and by Br\^anzei and Peres ['19], our result applies to all pairs $n,k$.
• Abstract（参考訳）: オンライン学習における古典的な結果は、リトルストーン次元を用いて決定論的学習者によって達成可能な最適誤り境界を特徴づける(littlestone '88)。 クラス $\mathcal{h}$ を学習する際の最適な期待誤差は、そのランダム化されたリトルストーン次元に等しいことを示し、これは$\mathcal{h}$ の平均深さが 2d$ であるような$\mathcal{h}$ で砕かれた木が存在する最大の$d$である。 我々はさらに、独立な場合における最適な誤り境界を、$k$ で表される$\mathcal{h}$ における最善の関数によってなされる誤り数の関数として研究する。 リトルストーン次元$d$を持つクラスを学ぶための最適ランダム化ミスは、$k + \Theta (\sqrt{k d} + d )$であることを示す。 これはまた、2k + \theta(d) + o(\sqrt{k d})$ の最適決定論的誤りであり、auer と long ['99] によって研究されたオープン問題を解くことを意味する。 約30年前、cesa-bianchi, freund, haussler, helmbold, schapire, warmuth は、専門家のアドバイスを使って予測を研究し、n$の専門家のベストが最大$k$の間違いを犯し、最適な誤り境界は何であるかを尋ねた。 Cesa-Bianchi, Freund, Helmbold, Warmuth ['93, '96] は、決定論的学習者にほぼ最適な境界を与え、ランダム化されたケースをオープンな問題として残した。 ランダム化の場合、最適学習規則を提供することでこの問題を解決し、その予測誤りがチェサ・ビアンキらの決定論的境界の半分に等しいことを示す。 ['93,'96]、無視可能な加法項まで。 Abernethy, Langford, Warmuth['06] と Br\^anzei と Peres ['19] の以前の研究とは対照的に、我々の結果はすべての対 $n,k$ に適用できる。

関連論文リスト

• Deterministic Apple Tasting [2.4554686192257424]
  我々は、初めて広く適用可能な決定論的リンゴテイスティング学習者を提供する。 すべてのクラス $mathcalH$ は簡単、困難、あるいは学習不能でなければならない、という三分法を証明します。 我々の上限は、リンゴの味付けフィードバックに関する専門家のアドバイスから学ぶための決定論的アルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2024-10-14T11:54:46Z)
• Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs [32.29254118429081]
  我々は,帯域幅フィードバックの下での最適誤りが,全情報ケースの最適誤りよりも少なくとも$O(k)$倍高いことを示す。 また、ランダム化学習者と決定論的学習者の間のギャップに対して、$tildeTheta(k)$のほぼ最適な境界を示す。
  論文  参考訳（メタデータ） (2024-02-12T07:20:05Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios [69.2027612631023]
  学習曲線指数$beta$を決定する上で,局所性が重要であることを示す。 我々は、自然の仮定を用いて、トレーニングセットのサイズに応じて減少するリッジでカーネルレグレッションを実行すると、リッジレスの場合と同じような学習曲線指数が得られることを証明して結論付けた。
  論文  参考訳（メタデータ） (2021-06-16T08:27:31Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games [38.15628332832227]
  我々は、常に「単純な」予測器を用いて、ほぼ最適なミス/リグレット境界を達成する方法を示す。 この証明の技術的要素は、二元ゼロサムゲームに対する有名なミニマックス定理の一般化である。
  論文  参考訳（メタデータ） (2021-02-02T18:02:01Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。