論文の概要: Stronger Calibration Lower Bounds via Sidestepping

• arxiv url: http://arxiv.org/abs/2012.03454v3
• Date: Fri, 6 Oct 2023 04:05:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-13 17:43:06.320599
• Title: Stronger Calibration Lower Bounds via Sidestepping
• Title（参考訳）: サイドステッピングによるより強いキャリブレーション下限
• Authors: Mingda Qiao, Gregory Valiant
• Abstract要約: 予測器が1ビットあたり$T$のシーケンスを1つずつ観測するオンラインバイナリ予測設定について検討する。 予測器は、[0, 1]$の各$pに対して、予測器が確率$p$を予測する$n_p$ビットのうち、$p cdot n_p$に対して実際に$p cdot n_p$と等しい場合、よく校正される。 キャリブレーション誤差は$sum_p |m_p - p n_p|$と定義され、予測器が適切に校正されない範囲を定量化する。
• 参考スコア（独自算出の注目度）: 18.383889039268222
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider an online binary prediction setting where a forecaster observes a sequence of $T$ bits one by one. Before each bit is revealed, the forecaster predicts the probability that the bit is $1$. The forecaster is called well-calibrated if for each $p \in [0, 1]$, among the $n_p$ bits for which the forecaster predicts probability $p$, the actual number of ones, $m_p$, is indeed equal to $p \cdot n_p$. The calibration error, defined as $\sum_p |m_p - p n_p|$, quantifies the extent to which the forecaster deviates from being well-calibrated. It has long been known that an $O(T^{2/3})$ calibration error is achievable even when the bits are chosen adversarially, and possibly based on the previous predictions. However, little is known on the lower bound side, except an $\Omega(\sqrt{T})$ bound that follows from the trivial example of independent fair coin flips. In this paper, we prove an $\Omega(T^{0.528})$ bound on the calibration error, which is the first super-$\sqrt{T}$ lower bound for this setting to the best of our knowledge. The technical contributions of our work include two lower bound techniques, early stopping and sidestepping, which circumvent the obstacles that have previously hindered strong calibration lower bounds. We also propose an abstraction of the prediction setting, termed the Sign-Preservation game, which may be of independent interest. This game has a much smaller state space than the full prediction setting and allows simpler analyses. The $\Omega(T^{0.528})$ lower bound follows from a general reduction theorem that translates lower bounds on the game value of Sign-Preservation into lower bounds on the calibration error.
• Abstract（参考訳）: 我々は、予測者が1つずつ$t$ビットのシーケンスを観察するオンラインバイナリ予測設定を考える。 各ビットが明かされる前に、予測器はビットが1ドルである確率を予測する。 予測器が well-calibrated と呼ばれるのは、各$p \in [0, 1]$ に対して、予測者が確率 $p$ を予測する$n_p$ のうち、実際の数 $m_p$ が$p \cdot n_p$ に等しい場合である。 キャリブレーション誤差は$\sum_p |m_pp n_p|$と定義され、予測器が適切に校正されない範囲を定量化する。 O(T^{2/3})$キャリブレーション誤差は、ビットが逆選択された場合でも達成可能であり、おそらくは以前の予測に基づいている。 しかし、独立フェアコインフリップの自明な例から従う$\Omega(\sqrt{T})$boundを除いて、下界側ではほとんど知られていない。 本稿では,キャリブレーション誤差に対する$\Omega(T^{0.528})$バウンドを証明し,この設定を私たちの知識の最高のものにするための最初のスーパー=$\sqrt{T}$ローバウンドである。 我々の研究の技術的貢献には、早期停止とサイドステッピングの2つの下限技術が含まれており、これは以前に強いキャリブレーションの下限を妨げていた障害を回避するものである。 また, 予測設定の抽象化として, 独立興味を持った手話保存ゲームを提案する。 このゲームは完全な予測設定よりもずっと小さな状態空間を持ち、より単純な分析を可能にする。 $\Omega(T^{0.528})$ lower bound は Sign-Preservation のゲーム値の下位境界をキャリブレーション誤差の下位境界に変換する一般還元定理から従う。

関連論文リスト

• Breaking the $T^{2/3}$ Barrier for Sequential Calibration [26.563792462828726]
  バイナリシーケンスのオンライン校正予測の問題について検討する。 Foster & Vohra (1998) は、$O(T2/3)$キャリブレーション誤差を$T$タイムステップ後に引き起こし、$Omega(T1/2)$の低い境界を示した。 Qiao & Valiant (2021) は、符号保存と呼ばれるゲームを導入して下限を$Omega(T0.528)$に改善した。
  論文  参考訳（メタデータ） (2024-06-19T16:19:39Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。 適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
  論文  参考訳（メタデータ） (2024-05-24T11:22:19Z)
• On the Distance from Calibration in Sequential Prediction [4.14360329494344]
  キャリブレーション距離から予測器を評価可能な逐次二分予測条件について検討する。 キャリブレーション距離は、完全キャリブレーションから逸脱する自然で直感的な尺度である。 我々は,逆選択された$T$バイナリ結果の列に対して,予測において$O(sqrtT)$キャリブレーション距離を達成できる予測アルゴリズムが存在することを証明した。
  論文  参考訳（メタデータ） (2024-02-12T07:37:19Z)
• Better and Simpler Lower Bounds for Differentially Private Statistical Estimation [7.693388437377614]
  任意の$alpha le O(1)$に対して、ガウスの共分散をスペクトル誤差まで推定するには$tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$サンプルが必要である。 次に、有界な$k$thモーメントで重み付き分布の平均を推定するには$tildeOmegaleft(fracdalphak/(k-1) varepsilon +
  論文  参考訳（メタデータ） (2023-10-10T04:02:43Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Evaluating Probabilistic Inference in Deep Learning: Beyond Marginal Predictions [37.92747047688873]
  一般的に使われる$tau=1$は、多くの関心のある設定で良い決定を下すには不十分であることを示す。 さらに、$tau$が成長するにつれて、$mathbfd_mathrmKLtau$は任意の決定に対する普遍的な保証を回復する。
  論文  参考訳（メタデータ） (2021-07-20T01:55:01Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)
• On the robustness of the minimum $\ell_2$ interpolator [2.918940961856197]
  一般高次元線形回帰フレームワークにおいて最小$ell$-norm$hatbeta$で補間を解析する。 高い確率で、この推定器の予測損失は、上から$(|beta*|2r_cn(Sigma)vee |xi|2)/n$で有界であることを証明する。
  論文  参考訳（メタデータ） (2020-03-12T15:12:28Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
  本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
  論文  参考訳（メタデータ） (2020-01-25T14:44:53Z)

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

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