論文の概要: Sharp Integrality Gaps in Calibration Distance
- arxiv url: http://arxiv.org/abs/2610.05679v1
- Date: Mon, 05 Oct 2026 01:44:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-10 12:06:39.187141
- Title: Sharp Integrality Gaps in Calibration Distance
- Title（参考訳）: キャリブレーション距離におけるシャープ積分ギャップ
- Abstract要約: 二元単位重み列に対する決定論的校正距離Cとその分数緩和Lのオフラインギャップについて検討する。
m 個の異なる予測を持つ全ての入力に対して、C = L + m であり、制限されないサンプルの最悪のスパース順序は Theta(m) である。
- 参考スコア（独自算出の注目度）: 2.2209978758723476
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the offline gap between deterministic calibration distance C and its fractional relaxation L for binary unit-weight sequences under total absolute-change cost. We sharpen the offline comparison C <= L + O(sqrt(T)) (Qiao and Zheng, 2024, Theorem 2) to the sharp worst-case order Theta(T^(1/3)). If Delta_T is the supremum of C - L over length-T inputs, then T^(1/3)/1000 <= Delta_T <= 41T^(1/3) for T >= 216. The upper bound holds for every input, while each T >= 216 has a rational lower-bound input. For every input with m distinct forecasts, C <= L + m, and the unrestricted-sample worst-case sparse order is Theta(m). For rational forecasts and accuracy, with binary-encoded multiplicities of separately assignable unit identities, a grid-free polynomial-bit-time procedure returns B <= L <= U, U - B < eta, and an exactly calibrated compact repair of cost at most U + m <= L + m + eta.
- Abstract（参考訳）: 決定論的キャリブレーション距離Cと二元単位重み列の分数緩和Lとの完全絶対変化コストによるオフラインギャップについて検討した。
オフライン比較 C <= L + O(sqrt(T)) (Qiao and Zheng, 2024, Theorem
2) 鋭い最悪のケースオーダー Theta(T^(1/3))。
Delta_T が長さ-T入力上の C - L の上限であれば、T >= 216 に対して T^(1/3)/1000 <= Delta_T <= 41T^(1/3) となる。
上界は各入力に対して保持し、T >= 216 は合理的な下界入力を持つ。
m 個の異なる予測を持つ全ての入力に対して、C <= L + m であり、制限されないサンプルの最悪のスパース順序は Theta(m) である。
有理予測と正確性については、分割可能な単位単位のバイナリ符号化多重度で、グリッドフリー多項式ビット時間プロシージャは B <= L <= U, U - B < eta を返却し、U + m <= L + m + eta でコストの正確な調整を行う。
関連論文リスト
- Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation [51.56484100374058]
我々は、ハードレイヤーワイドリプシッツ予算の下で近似を研究する。
構成条件下では、対応するレイヤエラーをキャンセルする必要はないことを示す。
クラスのすべての作用素に対して、安定した深さ-$L$タワーが存在し、累積誤差の定数分を実現できる。
論文 参考訳（メタデータ） (2026-09-14T20:17:04Z) - Semidefinite extension complexity of the separable set, with applications to approximate disentanglers [0.6117371161379209]
分離可能な状態における測定値の最大受容確率を近似する半定値プログラムを考える。
我々の証明は、Lee, Raghavendra, Steurer の量的擬似密度定理と明示的なブロック陽性作用素とチェビシェフ増幅を組み合わせたものである。
論文 参考訳（メタデータ） (2026-09-08T17:00:11Z) - Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$を符号、空間性、正方性制限なしで証明する。
純粋な$varepsilon$-DP行列力学クラスでは、最適化された最大誤差と平均二乗誤差の両方が$(varepsilon-2log3(n+1))$である。
論文 参考訳（メタデータ） (2026-07-30T14:41:34Z) - Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs [56.28491566735463]
既存のマルコフ決定過程のアルゴリズムは、$smashtildeO(dH2sqrtT)$を後悔する。
本稿では,最悪の場合において既存の境界を復元し,構造化されたMDPに対して改善する,$smashtildeO(dH2bar_TsqrtT)$の後悔を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-05-19T12:39:32Z) - Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
本稿では,FSCLB(Federated Sketch Contextual Linear Bandits)を提案する。
合成と実世界の両方のデータセットの実験では、FSCLBは計算と通信のコストを90%以上削減している。
論文 参考訳（メタデータ） (2026-05-01T08:22:06Z) - Optimal Lower Bounds for Online Multicalibration [9.852468478532652]
期待される多重校正誤差に対して$(T2/3)$低い境界を3つの非結合二元群を用いて証明する。
次に、文脈に依存するが学習者の予測には依存しない群関数のより難しい場合の下位境界に目を向ける。
論文 参考訳（メタデータ） (2026-01-08T18:59:32Z) - Unitary synthesis with fewer T gates [1.3512504563343783]
我々は,Tカウント$O(24n/3 n2/3)$のクリフォード+T回路を用いて任意の$n$-qubitユニタリ演算子を実装する単純なアルゴリズムを提案する。
これは以前の最もよく知られた上限である$O(23n/2 n)$を改善するが、最もよく知られた下限は$Omega (2n)$のままである。
論文 参考訳（メタデータ） (2025-09-30T03:01:34Z) - Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case [22.29614516455028]
入力を実質的に拡張するマルチ出力の定数深度回路の場合、その出力は十分な独立性を持つ分布からサンプリングされた文字列から非常に遠い可能性が示されている。
これにより、$mathsfNC0$回路のセル-プローブローバウンドとレンジ回避アルゴリズムへの応用が可能になる。
論文 参考訳（メタデータ） (2025-07-29T22:33:09Z) - Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。