論文の概要: When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses

• arxiv url: http://arxiv.org/abs/2506.01722v1
• Date: Mon, 02 Jun 2025 14:29:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:34.488026
• Title: When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses
• Title（参考訳）: 低次の項が支配する時:重機損失に対する適応的エキスパートアルゴリズム
• Authors: Antoine Moulin, Emmanuel Esposito, Dirk van der Hoeven,
• Abstract要約: 我々は、損失の範囲や第2モーメントに関する事前知識を必要としない適応アルゴリズムを開発する。 既存の適応アルゴリズムは、通常、彼らの後悔の保証において下位項と見なされるものを持っている。
• 参考スコア（独自算出の注目度）: 12.39860047886679
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem setting of prediction with expert advice with possibly heavy-tailed losses, i.e.\ the only assumption on the losses is an upper bound on their second moments, denoted by $\theta$. We develop adaptive algorithms that do not require any prior knowledge about the range or the second moment of the losses. Existing adaptive algorithms have what is typically considered a lower-order term in their regret guarantees. We show that this lower-order term, which is often the maximum of the losses, can actually dominate the regret bound in our setting. Specifically, we show that even with small constant $\theta$, this lower-order term can scale as $\sqrt{KT}$, where $K$ is the number of experts and $T$ is the time horizon. We propose adaptive algorithms with improved regret bounds that avoid the dependence on such a lower-order term and guarantee $\mathcal{O}(\sqrt{\theta T\log(K)})$ regret in the worst case, and $\mathcal{O}(\theta \log(KT)/\Delta_{\min})$ regret when the losses are sampled i.i.d.\ from some fixed distribution, where $\Delta_{\min}$ is the difference between the mean losses of the second best expert and the best expert. Additionally, when the loss function is the squared loss, our algorithm also guarantees improved regret bounds over prior results.
• Abstract（参考訳）: 我々は、専門家の助言による予測に関する問題設定、すなわち、損失に関する唯一の仮定は、その第2モーメントの上限であり、$\theta$で表される。 我々は、損失の範囲や第2モーメントに関する事前の知識を必要としない適応アルゴリズムを開発する。 既存の適応アルゴリズムは、通常、彼らの後悔の保証において下位項と見なされるものを持っている。 我々は、しばしば損失の最大値であるこの下位項が、我々の設定における後悔の束縛を実際に支配していることを示します。 具体的には、小さな定数$\theta$であっても、この下位項は$\sqrt{KT}$とスケールできる。 このような下位項への依存を回避し、最悪の場合において$\mathcal{O}(\sqrt{\theta T\log(K)})$ regret と $\mathcal{O}(\theta \log(KT)/\Delta_{\min})$ regret を保証し、損失がサンプリングされたとき、すなわち、ある固定分布から$\Delta_{\min}$が第2のベストエキスパートとベストエキスパートの損失の平均差であることを示す。 さらに,損失関数が正方形損失である場合,アルゴリズムは過去の結果よりも改善された後悔境界も保証する。

関連論文リスト

• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
  論文  参考訳（メタデータ） (2024-12-11T03:06:42Z)
• Optimal Multiclass U-Calibration Error and Beyond [31.959887895880765]
  オンラインマルチクラス境界U-キャリブレーションの問題は、予測器がU-キャリブレーション誤差の低いクラスをK$で逐次分布予測することを目的としている。 最適U校正誤差は$Theta(sqrtKT)$である。
  論文  参考訳（メタデータ） (2024-05-28T20:33:18Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  遅延フィードバックを伴うバンド凸最適化(BCO)。 我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。 提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
  論文  参考訳（メタデータ） (2024-02-14T13:08:26Z)
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
  論文  参考訳（メタデータ） (2023-05-01T14:00:15Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• Constant regret for sequence prediction with limited advice [0.0]
  予測とm$ge$2の専門家の損失を観測するために,p = 2の専門家のみを1ラウンド毎に組み合わせた戦略を提供する。 学習者が1ラウンドにつき1人の専門家のフィードバックのみを観察することを制約されている場合、最悪の場合の後悔は"スローレート"$Omega$($sqrt$KT)である。
  論文  参考訳（メタデータ） (2022-10-05T13:32:49Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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