論文の概要: Simultaneous Swap Regret Minimization via KL-Calibration

• arxiv url: http://arxiv.org/abs/2502.16387v1
• Date: Sun, 23 Feb 2025 00:23:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:51:44.136327
• Title: Simultaneous Swap Regret Minimization via KL-Calibration
• Title（参考訳）: KLキャリブレーションによる同時スワップレグレスト最小化
• Authors: Haipeng Luo, Spandan Senapati, Vatsal Sharan,
• Abstract要約: 我々は,(擬似)KL-キャリブレーション(擬似)と呼ばれる新たな校正の概念を導入する。 我々の研究の技術的貢献は、新しいランダム化されたラウンドリング手順と、ログ損失のスワップ後悔を最小限に抑える不均一な離散化スキームである。
• 参考スコア（独自算出の注目度）: 31.959887895880765
• License:
• Abstract: Calibration is a fundamental concept that aims at ensuring the reliability of probabilistic predictions by aligning them with real-world outcomes. There is a surge of studies on new calibration measures that are easier to optimize compared to the classical $\ell_1$-Calibration while still having strong implications for downstream applications. One recent such example is the work by Fishelson et al. (2025) who show that it is possible to achieve $O(T^{1/3})$ pseudo $\ell_2$-Calibration error via minimizing pseudo swap regret of the squared loss, which in fact implies the same bound for all bounded proper losses with a smooth univariate form. In this work, we significantly generalize their result in the following ways: (a) in addition to smooth univariate forms, our algorithm also simultaneously achieves $O(T^{1/3})$ swap regret for any proper loss with a twice continuously differentiable univariate form (such as Tsallis entropy); (b) our bounds hold not only for pseudo swap regret that measures losses using the forecaster's distributions on predictions, but also hold for the actual swap regret that measures losses using the forecaster's actual realized predictions. We achieve so by introducing a new stronger notion of calibration called (pseudo) KL-Calibration, which we show is equivalent to the (pseudo) swap regret for log loss. We prove that there exists an algorithm that achieves $O(T^{1/3})$ KL-Calibration error and provide an explicit algorithm that achieves $O(T^{1/3})$ pseudo KL-Calibration error. Moreover, we show that the same algorithm achieves $O(T^{1/3}(\log T)^{-1/3}\log(T/\delta))$ swap regret w.p. $\ge 1-\delta$ for any proper loss with a smooth univariate form, which implies $O(T^{1/3})$ $\ell_2$-Calibration error. A technical contribution of our work is a new randomized rounding procedure and a non-uniform discretization scheme to minimize the swap regret for log loss.
• Abstract（参考訳）: キャリブレーション(Calibration)は、確率的予測の信頼性を確保するための基本的な概念である。 従来の$\ell_1$-Calibrationと比較して最適化が容易な新しいキャリブレーション対策の研究が急増しているが、下流のアプリケーションに強く影響している。 フィッシュソンら (2025) による最近の研究は、正方形損失の擬スワップ後悔を最小化することで、$O(T^{1/3})$ pseudo $\ell_2$-Calibration 誤差を達成できることを示した。 本研究では,これらの結果を以下の方法で大幅に一般化する。 (a) 滑らかな単変数形式に加えて、我々のアルゴリズムは、連続的に微分可能な2つの単変数形式(例えば、ツァリスエントロピー)で任意の適切な損失に対して、同時に$O(T^{1/3})$スワップ後悔を達成する。 (b)予測者の分布を用いて損失を計測する擬似スワップ後悔だけでなく、予測者の実際に実現した予測を用いて損失を計測する実際のスワップ後悔も有する。 我々は、(擬似)KL-キャリブレーションと呼ばれる、より強力な校正の概念を導入し、ログ損失に対する後悔を(擬似)スワップする(擬似)スワップと等価であることを示す。 我々は,$O(T^{1/3})$KL-Calibrationエラーを実現するアルゴリズムが存在することを証明し,$O(T^{1/3})$擬似KL-Calibrationエラーを実現する明示的なアルゴリズムを提供する。 さらに、同じアルゴリズムが、滑らかな単変量形式を持つ任意の適切な損失に対して、$O(T^{1/3})$$O(T^{1/3})$$$\ell_2$-Calibrationエラーをもたらすことを示す。 我々の研究の技術的貢献は、新しいランダム化されたラウンドリング手順と、ログ損失のスワップ後悔を最小限に抑える不均一な離散化スキームである。

関連論文リスト

• Full Swap Regret and Discretized Calibration [18.944031222413294]
  構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。 我々は、Emphfullスワップリ後悔の最小化という新しいオンライン学習問題を導入する また、これらのツールをオンライン予測問題に適用し、校正誤差を補正する。
  論文  参考訳（メタデータ） (2025-02-13T13:49:52Z)
• Any-stepsize Gradient Descent for Separable Data under Fenchel--Young Losses [17.835960292396255]
  emphFenchel-Young損失の枠組みに基づく一般損失関数に対して任意のステップの勾配収束を示す。 我々は、自己有界性の代わりに損失関数の分岐マージンによって、これらのより良いレートが可能であると論じる。
  論文  参考訳（メタデータ） (2025-02-07T12:52:12Z)
• Revisiting Projection-Free Online Learning with Time-Varying Constraints [35.573654458435854]
  我々は制約付きオンライン凸最適化について検討し、そこでは決定は固定的で典型的には複雑な領域に属する必要がある。 いくつかのプロジェクションフリーな手法が$mathcalO(T3/4 sqrtlog T)$ regret boundと$mathcalO(T3/4 sqrtlog T)$ cumulative constraint violation (CCV) bound for general convex lossで提案されている。 本稿では,損失関数が強凸である場合に,この結果を改善し,さらにテクスチノーベルの後悔とCCV境界を確立する。
  論文  参考訳（メタデータ） (2025-01-27T13:38:51Z)
• Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
  Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。 一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
  論文  参考訳（メタデータ） (2024-06-10T23:23:52Z)
• Orthogonal Causal Calibration [55.28164682911196]
  我々は、任意の損失$ell$に対して、任意の因果パラメータのキャリブレーション誤差$theta$の一般的な上限を証明した。 我々は、因果校正のための2つのサンプル分割アルゴリズムの収束解析に境界を用いる。
  論文  参考訳（メタデータ） (2024-06-04T03:35:25Z)
• Optimal Multiclass U-Calibration Error and Beyond [31.959887895880765]
  オンラインマルチクラス境界U-キャリブレーションの問題は、予測器がU-キャリブレーション誤差の低いクラスをK$で逐次分布予測することを目的としている。 最適U校正誤差は$Theta(sqrtKT)$である。
  論文  参考訳（メタデータ） (2024-05-28T20:33:18Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Scale-free Unconstrained Online Learning for Curved Losses [1.5147172044848798]
  コンパレータのノルム$U$と勾配の最大ノルム$G$に同時に適応する可能性を検討する。 意外なことに、最近の研究では1ドル=Lipschitz損失の特定のケースにおいて、適応性に対するそのような価格が不要であることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T14:10:35Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)

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

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