論文の概要: Optimal Lower Bounds for Online Multicalibration
- arxiv url: http://arxiv.org/abs/2601.05245v1
- Date: Thu, 08 Jan 2026 18:59:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-09 17:01:53.355067
- Title: Optimal Lower Bounds for Online Multicalibration
- Title（参考訳）: オンライン多重校正のための最適下界
- Authors: Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth,
- Abstract要約: 期待される多重校正誤差に対して$(T2/3)$低い境界を3つの非結合二元群を用いて証明する。
次に、文脈に依存するが学習者の予測には依存しない群関数のより難しい場合の下位境界に目を向ける。
- 参考スコア（独自算出の注目度）: 9.852468478532652
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove tight lower bounds for online multicalibration, establishing an information-theoretic separation from marginal calibration. In the general setting where group functions can depend on both context and the learner's predictions, we prove an $Ω(T^{2/3})$ lower bound on expected multicalibration error using just three disjoint binary groups. This matches the upper bounds of Noarov et al. (2025) up to logarithmic factors and exceeds the $O(T^{2/3-\varepsilon})$ upper bound for marginal calibration (Dagan et al., 2025), thereby separating the two problems. We then turn to lower bounds for the more difficult case of group functions that may depend on context but not on the learner's predictions. In this case, we establish an $\widetildeΩ(T^{2/3})$ lower bound for online multicalibration via a $Θ(T)$-sized group family constructed using orthogonal function systems, again matching upper bounds up to logarithmic factors.
- Abstract（参考訳）: オンラインマルチキャリブレーションの限界を厳格に低くし,限界校正から情報理論的分離を確立する。
群関数が文脈と学習者の予測の両方に依存できる一般的な設定では、たった3つの非結合なバイナリ群を用いて、期待される多重校正誤差に対して$Ω(T^{2/3})$低い境界を証明している。
これは、Noarov et al (2025) の上界を対数的因子に当てはめ、境界校正の$O(T^{2/3-\varepsilon})$上界(Dagan et al , 2025)を超え、2つの問題を分離する。
次に、文脈に依存するが学習者の予測には依存しない群関数のより難しい場合の下位境界に目を向ける。
この場合、直交関数系を用いて構築された$(T)$サイズの群族を経由し、オンライン多重校正のための$\widetildeΩ(T^{2/3})$ローバウンドを確立する。
関連論文リスト
- Efficient Swap Multicalibration of Elicitable Properties [41.64272548564929]
[NR23] は任意のプロパティのマルチキャリブレーションとプロパティのエリケーションとの間に驚くべき関係を確立しました。
本稿では,グループメンバシップ関数から任意の有界仮説クラスへの帰納的プロパティに対する多重校正を一般化する。
論文 参考訳（メタデータ） (2025-11-07T01:14:39Z) - Minimax learning rates for estimating binary classifiers under margin conditions [0.0]
水平関数によって決定境界を記述する二分推定器を用いた分類問題について検討する。
我々は、ルベーグノルムの有界コルモゴロフエントロピーを持つ広関数クラスに対するミニマックス学習率の上限と下限を確立する。
論文 参考訳（メタデータ） (2025-05-15T18:05:10Z) - On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
平面トーラスから構築したグラフ上での最大独立集合(MIS)問題として問題を再構成することにより、$m_1(mathbbR2)$を推定する新しいアプローチを導入する。
提案手法の理論的正当性によって支持された実験結果から, 十分に広い範囲のパラメータに対して, この手法が既知の下界を改善できないことを示す。
論文 参考訳（メタデータ） (2024-11-20T12:07:19Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Neural-network quantum state study of the long-range antiferromagnetic Ising chain [0.771303749110121]
横磁場イジング鎖の反強磁性相互作用を代数的に減衰させた反強磁性相互作用における量子相転移について検討する。
SR極限の普遍比が$alpha_mathrmLR 2$で成り立たないことが、臨界度の偏りを示唆している。
論文 参考訳（メタデータ） (2023-08-18T17:58:36Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
本稿では,ガウス分布下での中間空間の学習に関するよく研究された問題について,難易度学習モデルを用いて考察する。
下界の2つの変種を証明し、それぞれがダイアコニコラスら (2021) の成分と、Boolean の設定に対する SQ 下界に対する異なる以前のアプローチ(拡張)を組み合わせた。
論文 参考訳（メタデータ） (2022-02-10T15:34:10Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。