論文の概要: 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である。
関連論文リスト
- Orthogonal Causal Calibration [55.28164682911196]
我々は、任意の損失$ell$に対して、任意の因果パラメータのキャリブレーション誤差$theta$の一般的な上限を証明した。
我々は、因果校正のための2つのサンプル分割アルゴリズムの収束解析に境界を用いる。
論文 参考訳（メタデータ） (2024-06-04T03:35:25Z) - Predict to Minimize Swap Regret for All Payoff-Bounded Tasks [15.793486463552144]
バイナリイベントの予測の最大スワップレグレット(MSR)について検討する。
我々は、$O(sqrtTlogT)$ expected MSRを保証する効率的なランダム化予測アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-21T01:53:20Z) - On the Distance from Calibration in Sequential Prediction [4.14360329494344]
キャリブレーション距離から予測器を評価可能な逐次二分予測条件について検討する。
キャリブレーション距離は、完全キャリブレーションから逸脱する自然で直感的な尺度である。
我々は,逆選択された$T$バイナリ結果の列に対して,予測において$O(sqrtT)$キャリブレーション距離を達成できる予測アルゴリズムが存在することを証明した。
論文 参考訳（メタデータ） (2024-02-12T07:37:19Z) - Closing the Gap Between the Upper Bound and the Lower Bound of Adam's
Iteration Complexity [51.96093077151991]
我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。
本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
論文 参考訳（メタデータ） (2023-10-27T09:16:58Z) - 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) - New Lower Bounds for Private Estimation and a Generalized Fingerprinting
Lemma [10.176795938619417]
統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。
フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
論文 参考訳（メタデータ） (2022-05-17T17:55:10Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。