論文の概要: Breaking the $T^{2/3}$ Barrier for Sequential Calibration

• arxiv url: http://arxiv.org/abs/2406.13668v3
• Date: Fri, 15 Nov 2024 20:32:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-19 14:30:23.516669
• Title: Breaking the $T^{2/3}$ Barrier for Sequential Calibration
• Title（参考訳）: シークエンシャルキャリブレーションのための$T^{2/3}$バリアを壊す
• Authors: Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, Princewill Okoroafor,
• Abstract要約: バイナリシーケンスのオンライン校正予測の問題について検討する。 Foster & Vohra (1998) は、$O(T2/3)$キャリブレーション誤差を$T$タイムステップ後に引き起こし、$Omega(T1/2)$の低い境界を示した。 Qiao & Valiant (2021) は、符号保存と呼ばれるゲームを導入して下限を$Omega(T0.528)$に改善した。
• 参考スコア（独自算出の注目度）: 26.563792462828726
• License:
• Abstract: A set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of timesteps where that prediction was made. We study the fundamental problem of online calibrated forecasting of binary sequences, which was initially studied by Foster & Vohra (1998). They derived an algorithm with $O(T^{2/3})$ calibration error after $T$ time steps, and showed a lower bound of $\Omega(T^{1/2})$. These bounds remained stagnant for two decades, until Qiao & Valiant (2021) improved the lower bound to $\Omega(T^{0.528})$ by introducing a combinatorial game called sign preservation and showing that lower bounds for this game imply lower bounds for calibration. In this paper, we give the first improvement to the $O(T^{2/3})$ upper bound on calibration error of Foster & Vohra. We do this by introducing a variant of Qiao & Valiant's game that we call sign preservation with reuse (SPR). We prove that the relationship between SPR and calibrated forecasting is bidirectional: not only do lower bounds for SPR translate into lower bounds for calibration, but algorithms for SPR also translate into new algorithms for calibrated forecasting. We then give an improved \emph{upper bound} for the SPR game, which implies, via our equivalence, a forecasting algorithm with calibration error $O(T^{2/3 - \varepsilon})$ for some $\varepsilon > 0$, improving Foster & Vohra's upper bound for the first time. Using similar ideas, we then prove a slightly stronger lower bound than that of Qiao & Valiant, namely $\Omega(T^{0.54389})$. Our lower bound is obtained by an oblivious adversary, marking the first $\omega(T^{1/2})$ calibration lower bound for oblivious adversaries.
• Abstract（参考訳）: 予測器の各予測が、その予測がなされた時間ステップのサブセットにおける結果の経験的分布を近似すると、確率予測のセットを校正する。 本稿では、Foster & Vohra (1998) が最初に研究した2進数列のオンライン校正予測の基本的な問題について考察する。 彼らは、$O(T^{2/3})$キャリブレーション誤差を、$T$タイムステップ後に引き起こし、$\Omega(T^{1/2})$の低い境界を示した。 これらの境界は2021年にQiao & Valiant(英語版)が$\Omega(T^{0.528})$に下限を改良するまで20年間停滞し続けた。 本稿では,Foster & Vohraのキャリブレーション誤差の上限値である$O(T^{2/3})$を初めて改善する。 我々はQiao & Valiantのゲームを再利用による手形保存(SPR)と呼ぶ変種を導入することでこれを実現している。 我々は、SPRとキャリブレーション予測の関係が双方向であることを証明する。SPRの下位境界はキャリブレーションの下位境界に変換されるだけでなく、SPRのアルゴリズムはキャリブレーション予測の新しいアルゴリズムにも変換される。 次に、SPRゲームに対して改良された 'emph{upper bound} を与える。これは、我々の同値性を通して、キャリブレーション誤差$O(T^{2/3 - \varepsilon})$を、ある$\varepsilon > 0$ に対して、フォスター・アンド・ボーラの上界を初めて改善する予測アルゴリズムである。 類似のアイデアを用いることで、カイオ・アンド・ヴァリアントのそれよりもわずかに強い下界、すなわち$\Omega(T^{0.54389})$を証明できる。 我々の下限は難解な敵によって得られ、最初の$\omega(T^{1/2})$ calibration lower bound for oblivious adversariesである。

関連論文リスト

• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。 TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。 我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
  論文  参考訳（メタデータ） (2024-11-19T01:08:13Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• An Elementary Predictor Obtaining $2\sqrt{T}+1$ Distance to Calibration [4.628072661683411]
  オンライン予測器は, 対向的な設定でキャリブレーションまでの距離が$O(sqrtT)$であることを示す。 キャリブレーション誤差を最大2sqrtT+1$で求める,極めて単純,効率的,決定論的アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-18T00:53:05Z)
• On the Distance from Calibration in Sequential Prediction [4.14360329494344]
  キャリブレーション距離から予測器を評価可能な逐次二分予測条件について検討する。 キャリブレーション距離は、完全キャリブレーションから逸脱する自然で直感的な尺度である。 我々は,逆選択された$T$バイナリ結果の列に対して,予測において$O(sqrtT)$キャリブレーション距離を達成できる予測アルゴリズムが存在することを証明した。
  論文  参考訳（メタデータ） (2024-02-12T07:37:19Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。 また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
  論文  参考訳（メタデータ） (2022-06-26T06:51:31Z)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。 上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
  論文  参考訳（メタデータ） (2021-02-06T15:05:14Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Stronger Calibration Lower Bounds via Sidestepping [18.383889039268222]
  予測器が1ビットあたり$T$のシーケンスを1つずつ観測するオンラインバイナリ予測設定について検討する。 予測器は、[0, 1]$の各$pに対して、予測器が確率$p$を予測する$n_p$ビットのうち、$p cdot n_p$に対して実際に$p cdot n_p$と等しい場合、よく校正される。 キャリブレーション誤差は$sum_p |m_p - p n_p|$と定義され、予測器が適切に校正されない範囲を定量化する。
  論文  参考訳（メタデータ） (2020-12-07T05:29:28Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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