論文の概要: Full Swap Regret and Discretized Calibration

• arxiv url: http://arxiv.org/abs/2502.09332v1
• Date: Thu, 13 Feb 2025 13:49:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:47:25.133914
• Title: Full Swap Regret and Discretized Calibration
• Title（参考訳）: 完全スワップレグレットと離散校正
• Authors: Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, Yifeng Teng,
• Abstract要約: 構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。 我々は、Emphfullスワップリ後悔の最小化という新しいオンライン学習問題を導入する また、これらのツールをオンライン予測問題に適用し、校正誤差を補正する。
• 参考スコア（独自算出の注目度）: 18.944031222413294
• License:
• Abstract: We study the problem of minimizing swap regret in structured normal-form games. Players have a very large (potentially infinite) number of pure actions, but each action has an embedding into $d$-dimensional space and payoffs are given by bilinear functions of these embeddings. We provide an efficient learning algorithm for this setting that incurs at most $\tilde{O}(T^{(d+1)/(d+3)})$ swap regret after $T$ rounds. To achieve this, we introduce a new online learning problem we call \emph{full swap regret minimization}. In this problem, a learner repeatedly takes a (randomized) action in a bounded convex $d$-dimensional action set $\mathcal{K}$ and then receives a loss from the adversary, with the goal of minimizing their regret with respect to the \emph{worst-case} swap function mapping $\mathcal{K}$ to $\mathcal{K}$. For varied assumptions about the convexity and smoothness of the loss functions, we design algorithms with full swap regret bounds ranging from $O(T^{d/(d+2)})$ to $O(T^{(d+1)/(d+2)})$. Finally, we apply these tools to the problem of online forecasting to minimize calibration error, showing that several notions of calibration can be viewed as specific instances of full swap regret. In particular, we design efficient algorithms for online forecasting that guarantee at most $O(T^{1/3})$ $\ell_2$-calibration error and $O(\max(\sqrt{\epsilon T}, T^{1/3}))$ \emph{discretized-calibration} error (when the forecaster is restricted to predicting multiples of $\epsilon$).
• Abstract（参考訳）: 構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。 プレイヤーは非常に多くの(潜在的に無限の)純粋なアクションを持つが、各アクションは$d$次元空間に埋め込み、これらの埋め込みの双線型関数によってペイオフが与えられる。 我々は,この設定に対する効率的な学習アルゴリズムを提案し,最大$\tilde{O}(T^{(d+1)/(d+3)} を$T$ラウンド後にリセットする。 これを実現するために、我々は「後悔の最小化」を「emph{full swap regret minimization」と呼ぶ新しいオンライン学習問題を導入する。 この問題において、学習者は、有界凸$d$-次元アクションセット$\mathcal{K}$で繰り返し(ランダム化された)アクションを受け取り、次に敵から損失を受け取り、 \emph{worst-case} のスワップ関数 $\mathcal{K}$ から $\mathcal{K}$ への写像に関して後悔を最小限にすることを目的としている。 損失関数の凸性と滑らか性に関する様々な仮定に対して、$O(T^{d/(d+2)})$から$O(T^{(d+1)/(d+2)})$までの完全スワップ後悔境界を持つアルゴリズムを設計する。 最後に、これらのツールをオンライン予測問題に適用し、校正誤差を最小限に抑えるとともに、校正の考え方を完全なスワップ後悔の特定の事例と見なせることを示す。 特に,最大$O(T^{1/3})$\ell_2$-calibrationエラーと$O(\max(\sqrt{\epsilon T}, T^{1/3})$ \emph{discretized-calibration}エラー(予測者が$\epsilon$の多重予測に制限されている場合)を保証できる効率的なオンライン予測アルゴリズムを設計する。

関連論文リスト

• Sparsity-Based Interpolation of External, Internal and Swap Regret [4.753557469026313]
  本稿では,$phi$-regret最小化によるパフォーマンス指標のコンパレータについて検討する。 本稿では,インスタンス適応型$phi$-regretバウンダリを実現する単一アルゴリズムを提案する。 従来の$phi$-regretの最小化から外部後悔の最小化への削減を前提に、我々は後者をさらにオンライン線形回帰に変換することを目的としている。
  論文  参考訳（メタデータ） (2025-02-06T22:47:52Z)
• Near-Optimal Algorithms for Omniprediction [6.874077229518565]
  オンライン設定とオフライン設定の両方で、オムニプレディションのためのほぼ最適学習アルゴリズムを提供します。 オンライン学習アルゴリズムは、様々な尺度でほぼ最適な複雑さを実現する。 オフライン学習アルゴリズムは効率的な$(mathcalL_mathrmBV,mathcalH,varepsilon(m)$)を返す
  論文  参考訳（メタデータ） (2025-01-28T02:58:37Z)
• Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees [36.746745619968024]
  本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。 我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。 本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
  論文  参考訳（メタデータ） (2023-05-19T15:02:10Z)
• Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime [74.52487417350221]
  オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。 そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-27T21:19:24Z)
• Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
  文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。 我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
  論文  参考訳（メタデータ） (2022-11-27T20:38:47Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。 強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
  論文  参考訳（メタデータ） (2021-03-21T11:43:35Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints [94.76881135901753]
  一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。 提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。 まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
  論文  参考訳（メタデータ） (2021-01-06T18:56:07Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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