論文の概要: 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のベストエキスパートとベストエキスパートの損失の平均差であることを示す。
さらに,損失関数が正方形損失である場合,アルゴリズムは過去の結果よりも改善された後悔境界も保証する。
関連論文リスト
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback [6.390468088226495]
曲面損失と遅延フィードバックを用いたオンライン凸最適化問題について検討する。
次数$minsigma_maxln T, sqrtd_mathrmtot$を後悔する規則化リーダの変種を提案する。
次に、exp-concave損失を検討し、適応的な学習率チューニングで遅延を処理するためにOnline Newton Stepアルゴリズムを拡張した。
論文 参考訳（メタデータ） (2025-06-09T09:49:54Z) - Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
論文 参考訳（メタデータ） (2025-02-06T12:03:24Z) - 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) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。