論文の概要: High dimensional online calibration in polynomial time

• arxiv url: http://arxiv.org/abs/2504.09096v1
• Date: Sat, 12 Apr 2025 06:28:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:53:58.088916
• Title: High dimensional online calibration in polynomial time
• Title（参考訳）: 多項式時間における高次元オンライン校正
• Authors: Binghui Peng,
• Abstract要約: オンライン(シークエンシャル)キャリブレーションでは、予測器は有限結果空間上の確率分布を予測し、T$dayのシーケンス上で$[d]$を予測する。 最もよく知られたアルゴリズムは、非自明なキャリブレーションを達成するのに$exp(d)$dayが必要である。 本稿では,複数のラウンドの後に,非自明なアルゴリズムキャリブレーションを保証する第1のキャリブレーション戦略を提案する。
• 参考スコア（独自算出の注目度）: 17.45683822446751
• License:
• Abstract: In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space $[d]$ over a sequence of $T$ days, with the goal of being calibrated. While asymptotically calibrated strategies are known to exist, they suffer from the curse of dimensionality: the best known algorithms require $\exp(d)$ days to achieve non-trivial calibration. In this work, we present the first asymptotically calibrated strategy that guarantees non-trivial calibration after a polynomial number of rounds. Specifically, for any desired accuracy $\epsilon > 0$, our forecaster becomes $\epsilon$-calibrated after $T = d^{O(1/\epsilon^2)}$ days. We complement this result with a lower bound, proving that at least $T = d^{\Omega(\log(1/\epsilon))}$ rounds are necessary to achieve $\epsilon$-calibration. Our results resolve the open questions posed by [Abernethy-Mannor'11, Hazan-Kakade'12]. Our algorithm is inspired by recent breakthroughs in swap regret minimization [Peng-Rubinstein'24, Dagan et al.'24]. Despite its strong theoretical guarantees, the approach is remarkably simple and intuitive: it randomly selects among a set of sub-forecasters, each of which predicts the empirical outcome frequency over recent time windows.
• Abstract（参考訳）: オンライン(シークエンシャル)キャリブレーションでは、予測者は有限結果空間上の確率分布を[d]$で予測し、キャリブレーションを目標とする。 漸近的に校正された戦略は存在することが知られているが、それらは次元の呪いに悩まされている。 本研究は,数個のラウンドの後に非自明なキャリブレーションを保証するための,最初の漸近的キャリブレーション戦略を示す。 具体的には、任意の精度が$\epsilon > 0$の場合、予測器は$T = d^{O(1/\epsilon^2)} の後に$\epsilon$-calibratedとなる。 我々はこの結果を下界で補い、少なくとも$T = d^{\Omega(\log(1/\epsilon))} のラウンドが$\epsilon$-calibrationを達成するために必要であることを示す。 我々の結果は[Abernethy-Mannor'11, Hazan-Kakade'12]によるオープンな疑問を解決します。 我々のアルゴリズムは、後悔の最小化(Peng-Rubinstein'24, Dagan et al '24]をスワップする最近のブレークスルーにインスパイアされている。 非常に理論的な保証があるにもかかわらず、このアプローチは驚くほど単純で直感的であり、一連のサブフォカスターの中からランダムに選択し、それぞれが最近のタイムウインドウ上で経験的な結果の頻度を予測する。

関連論文リスト

• Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
  2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。 2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
  論文  参考訳（メタデータ） (2024-10-31T13:51:59Z)
• Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
  本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。 我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
  論文  参考訳（メタデータ） (2024-10-02T15:21:07Z)
• Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression [44.13655983242414]
  最適誤差保証付きニア・ニア・ニア・リニア時間アルゴリズムの最初のサンプルを設計する。 堅牢な線形回帰のために、サンプル複雑性$n = tildeO(d/epsilon2)$と、ターゲット回帰器を$ell$-$O(epsilon)$で近似するほぼ線形ランタイムを持つ最初のアルゴリズムを与える。 これは、文献のオープンな疑問に答え、最適なエラー保証を達成するための最初のサンプルとタイムアルゴリズムである。
  論文  参考訳（メタデータ） (2023-12-04T00:31:16Z)
• Quantum speedups for linear programming via interior point methods [1.8434042562191815]
  本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。 我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
  論文  参考訳（メタデータ） (2023-11-06T16:00:07Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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