論文の概要: Improved bounds for calibration via stronger sign preservation games
- arxiv url: http://arxiv.org/abs/2406.13668v1
- Date: Wed, 19 Jun 2024 16:19:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-21 19:04:39.327021
- Title: Improved bounds for calibration via stronger sign preservation games
- Title（参考訳）: 強手保存ゲームによる校正限界の改善
- 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: http://creativecommons.org/licenses/by/4.0/
- 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. We introduce a strengthening 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. In particular, any strategy that improves the trivial upper bound for the value of the SPR game would imply a forecasting algorithm with calibration error exponent less than 2/3, 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年間停滞し続けた。
そこで我々はQiao & ValiantのゲームをSPR(Sign Reserve with reuse)と呼んでいる。
我々は、SPRとキャリブレーション予測の関係が双方向であることを証明する。SPRの下位境界はキャリブレーションの下位境界に変換されるだけでなく、SPRのアルゴリズムはキャリブレーション予測の新しいアルゴリズムにも変換される。
特に、SPRゲームの値に対する自明な上限を改善する戦略は、キャリブレーション誤差指数が2/3未満の予測アルゴリズムを暗示し、フォスター・アンド・ボーラの上限を初めて改善する。
類似のアイデアを用いることで、カイオ・アンド・ヴァリアントのそれよりもわずかに強い下界、すなわち$\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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。