論文の概要: Toward Simultaneously Optimal Regret in U-Calibration

• arxiv url: http://arxiv.org/abs/2606.18527v1
• Date: Tue, 16 Jun 2026 22:44:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-18 17:16:50.923161
• Title: Toward Simultaneously Optimal Regret in U-Calibration
• Title（参考訳）: U-キャリブレーションにおける最適レグレットの同時実現に向けて
• Authors: Rafael Frongillo, Haipeng Luo, Nishant A. Mehta, Jon Schneider,
• Abstract要約: 既存のU校正アルゴリズムは、すべての有界固有損失に対して、最悪のケースの最適$O(sqrtT)$後悔を達成する。 正方形損失のような滑らかな損失であっても、最適の$O(log T)$後悔の代わりに$(sqrtT)$後悔を引き起こす。 具体的には,有界固有損失毎に$tilde O(sqrtT)$ regretを同時に達成する単一予測アルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 41.366442572915496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal $O(\sqrt{T})$ regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur $Ω(\sqrt{T})$ regret instead of the optimal $O(\log T)$ regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves $\tilde O(\sqrt{T})$ regret for every bounded proper loss and $O(\log T)$ regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using self-concordant noise. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.
• Abstract（参考訳）: U-calibrationは、未知の下流エージェントによって予測を消費できるオンライン予測アルゴリズムを研究し、すべての適切な損失関数に対して同時にサブ線形後悔を保証する。 既存のU校正アルゴリズムは、すべての有界固有損失に対して最悪の場合の$O(\sqrt{T})$後悔を達成するが、より簡単な損失に適応することができない:私たちが示すように、二乗損失のような滑らかな損失に対しても、最適な$O(\log T)$後悔の代わりに$Ω(\sqrt{T})$後悔を引き起こす。 この研究において、この制限は固有のものではないことを示す。 具体的には,任意の有界な純損失に対して$\tilde O(\sqrt{T})$後悔を同時に達成し,任意の有界な純損失に対して$O(\log T)$後悔を同時に達成する単一予測アルゴリズムを設計する。 より一般的には、このアルゴリズムはログバリアに対してスムーズな損失に対して、いくつかの非Lipschitz例を含む対数的後悔を実現する。 提案手法は,自己協和音を用いた予測空間に摂動を直接適用するFollow-the-Perturbed-Leader (FTPL) の新たな変種に基づく。 結果として得られた分析は、このノイズの複雑な性質のため、以前のFTPL分析から大きく離れており、独立した関心を持つ可能性がある。

関連論文リスト

• When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses [10.329071967218054]
  我々は、損失の範囲や第2モーメントに関する事前知識を必要としない適応アルゴリズムを開発する。 既存の適応アルゴリズムは、通常、彼らの後悔の保証において下位項と見なされるものを持っている。
  論文  参考訳（メタデータ） (2025-06-02T14:29:05Z)
• 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)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)

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

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