論文の概要: Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm

• arxiv url: http://arxiv.org/abs/2205.03728v1
• Date: Sat, 7 May 2022 22:03:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-15 06:45:12.664067
• Title: Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm
• Title（参考訳）: 縮合ベイズアルゴリズムによるログロスの高精度レグレト境界
• Authors: Changlong Wu, Mohsen Heidari, Ananth Grama, Wojciech Szpankowski
• Abstract要約: 対数損失下での逐次的オンライン回帰(シーケンシャル確率代入)について検討する。 我々は、専門家のクラスで発生する過剰な損失として定義される連続したミニマックスの後悔に対して、厳密で、しばしば一致し、下限と上限を得ることに重点を置いている。
• 参考スコア（独自算出の注目度）: 14.834625066344582
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the sequential general online regression, known also as the sequential probability assignments, under logarithmic loss when compared against a broad class of experts. We focus on obtaining tight, often matching, lower and upper bounds for the sequential minimax regret that are defined as the excess loss it incurs over a class of experts. After proving a general upper bound, we consider some specific classes of experts from Lipschitz class to bounded Hessian class and derive matching lower and upper bounds with provably optimal constants. Our bounds work for a wide range of values of the data dimension and the number of rounds. To derive lower bounds, we use tools from information theory (e.g., Shtarkov sum) and for upper bounds, we resort to new "smooth truncated covering" of the class of experts. This allows us to find constructive proofs by applying a simple and novel truncated Bayesian algorithm. Our proofs are substantially simpler than the existing ones and yet provide tighter (and often optimal) bounds.
• Abstract（参考訳）: 一般オンライン回帰(sequential general online regression, シーケンシャル確率割当とも呼ばれる)を、幅広い専門家と比較した場合の対数損失下で検討した。 専門家のクラスで発生する過大な損失として定義される、逐次的ミニマックスの後悔に対して、厳密で、しばしば一致し、下界と上界を得ることに集中します。 一般上界を証明した後、リプシッツ類から有界ヘッセン類への専門家の特定のクラスを考え、証明可能な最適定数を持つ下界と上界のマッチングを導出する。 私たちの境界は、データ次元とラウンド数という幅広い値に対して機能します。 下限を導出するために、情報理論(例えばシュタルコフ和)のツールを使い、上限については専門家の階級の新しい「スムース・トランケーテッド・カバー」に頼る。 これにより、単純かつ斬新なベイズアルゴリズムを適用することで、構成的証明を見つけることができる。 我々の証明は既存の証明よりもかなり単純であり、より厳密な(そしてしばしば最適な)境界を提供する。

関連論文リスト

• Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
  本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。 本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
  論文  参考訳（メタデータ） (2023-10-02T19:59:39Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Generalization Analysis for Contrastive Representation Learning [80.89690821916653]
  既存の一般化誤差境界は負の例の数$k$に線形に依存する。 対数項まで$k$に依存しないコントラスト学習のための新しい一般化境界を確立する。
  論文  参考訳（メタデータ） (2023-02-24T01:03:56Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers [31.102181563065844]
  量子的(そしてより一般的には、KL)後悔は、最高の個人専門家と競争する目標を緩和し、敵対的なデータに関して、ほとんどの専門家と競争するだけである。 最近では、半対人パラダイム(Bilodeau、Negrea、Roy 2020)は、完全に対人的でも対人的でもないデータを考えることによって、対人的オンライン学習の代替緩和を提供する。 我々は、FTRLと別個のルート対数正規化器を併用したFTRLを用いて、両方のパラダイムにおいて最小限の後悔を達成し、どちらも正規Hedgeの変種と解釈できる。
  論文  参考訳（メタデータ） (2021-10-27T22:38:52Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Best-Case Lower Bounds in Online Learning [9.01310450044549]
  オンライン学習における研究の多くは、後悔に対する下線上界の研究に焦点を当てている。 本研究では,オンライン凸最適化における最良ケース下界の研究を開始する。 我々はFTRLの線形化バージョンが負の線形後悔を達成できることを示した。
  論文  参考訳（メタデータ） (2021-06-23T23:24:38Z)
• A Simple yet Universal Strategy for Online Convex Optimization [97.64589722655612]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 鍵となるアイデアは、元のオンライン機能を処理する専門家のセットを構築し、emphlinearized lossの上にメタアゴリタムを配置することだ。 我々の戦略は、強い凸関数と指数関数のために設計された専門家の理論的保証を継承する。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• Comparator-adaptive Convex Bandits [77.43350984086119]
  我々は,コンパレータのノルムが小さい場合,残差が小さい凸バンディットアルゴリズムを開発した。 アイデアを拡張して、リプシッツや滑らかな損失関数で包帯を凸する。
  論文  参考訳（メタデータ） (2020-07-16T16:33:35Z)
• Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance [37.0414602993676]
  連続)計量エントロピー $mathcalO(gamma-p)$ at scale $gamma$ を持つ任意の専門家クラスに対して、ミニマックス後悔は $mathcalO(np/(p+1))$ であることを示す。 我々の手法の応用として、専門家の非パラメトリックリプシッツ類に対するミニマックス後悔を解消する。
  論文  参考訳（メタデータ） (2020-07-02T14:47:33Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-01-23T16:47:52Z)

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

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