論文の概要: Instance-Adaptive Online Multiclass Multicalibration
- arxiv url: http://arxiv.org/abs/2610.15954v1
- Date: Sun, 11 Oct 2026 22:21:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-19 08:23:37.615377
- Title: Instance-Adaptive Online Multiclass Multicalibration
- Title（参考訳）: インスタンス適応型オンラインマルチクラス多重校正
- Abstract要約: 我々は、T$ラウンド以上のオンラインマルチクラス多重校正について研究し、余計な保証付きアルゴリズムを提供する。
逆選択された結果の列が次元$s$のアフィン部分空間にある場合、高い確率でエラー$widetilde O(n1/(s+2)T(s+1)/(s+2))$を得る。
- 参考スコア（独自算出の注目度）: 11.377412007104363
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study online multiclass multicalibration over $T$ rounds, and give an algorithm with beyond-worst-case guarantees. With $n$ possible outcomes, forecasts lie in a simplex of dimension $d=n-1$. In the worst case, cumulative $\ell_1$ multicalibration error scales with $\widetildeΘ(T^{(d+1)/(d+2)})$, which becomes untenable once $d$ exceeds a small constant. Our algorithm adapts to the geometry of the realized sequence: if the sequence of adversarially selected outcome means lies in an affine subspace of dimension $s$, it obtains error $\widetilde O(n^{1/(s+2)}T^{(s+1)/(s+2)})$ with high probability. The algorithm adapts to this structure without knowing the subspace or its dimension. For $T\ge n\ge2$, this rate is minimax optimal up to polylogarithmic factors. For a stochastic instance with a fixed conditional mean, the bound specializes to $\widetilde O(\sqrt{nT})$, giving a square-root dependence on the horizon.
- Abstract（参考訳）: 我々は、T$ラウンド以上のオンラインマルチクラス多重校正について研究し、余計な保証付きアルゴリズムを提供する。
可能な結果が$n$の場合、予測は次元$d=n-1$の単純集合に置かれる。
最悪の場合、累積$\ell_1$multicalibration error scales with $\widetildez(T^{(d+1)/(d+2)})$は、$d$が小さな定数を超えると停止不能になる。
逆選択された結果の列が次元$s$のアフィン部分空間にある場合、高い確率でエラー$\widetilde O(n^{1/(s+2)}T^{(s+1)/(s+2)})$を得る。
このアルゴリズムは部分空間やその次元を知ることなく、この構造に適応する。
T\ge n\ge2$ の場合、この値は多対数因子まで最小値である。
固定条件平均を持つ確率的な場合、境界は$\widetilde O(\sqrt{nT})$に特殊化され、地平線への平方根依存を与える。
関連論文リスト
- High-dimensional online calibration from harmonic weights [26.94938196315732]
任意の凸集合$YsubseteqmathbbRd$上での多次元予測のオンライン校正について検討する。
我々のアルゴリズムは単純で、各ラウンドで調和的に滑らかな過去の結果に対して調和的に重み付けされた分布を出力する。
論文 参考訳（メタデータ） (2026-10-06T04:36:12Z) - Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization [55.29259818039367]
支持領域がより均一な選択を許すにつれて、認証された近似係数がどのように改善されるかを示す。
明示的なパラメータの選択は、非遅延認証プロファイルに$underline_k()$を与える。
値保持丸めは、これらの保証をマトロイドとクナプサックの制約に転送する。
論文 参考訳（メタデータ） (2026-10-02T20:52:38Z) - Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps [28.438129186461598]
コンパクト凸集合の一般ノルム $|cdot|$ と自己写像 $T$ に対して、小さな固定点残差 $|T(x)-x| leq $ を持つ点を計算するオラクル複雑性について検討する。
弱ラデマッハ型$q > 1$の任意のノルムに対して、高い確率でそのような問題を解くアルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-09-08T23:09:39Z) - Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry [20.068722738606287]
我々は、$(epsilon,delta)$-differential privacy(DP)の制約の下で、サドル点問題(SSP)と変分不等式(SVI)を研究する。
強いSPギャップ上の$tildeObig(frac1sqrtn + fracsqrtdnepsilonbig)$のバウンドを得る。
我々は、$の強いVI-ギャップ上の有界値を得る最初の解析を提供する。
論文 参考訳（メタデータ） (2024-11-07T21:45:05Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Beyond Moments: Robustly Learning Affine Transformations with
Asymptotically Optimal Error [8.615625517708324]
サンプルから標準ハイパーキューブの未知アフィン変換を学習するためのリアルタイムアルゴリズムを提案する。
本アルゴリズムは,証明書の要求が満たされない場合に,未知アフィン変換の推定を反復的に改善する手法に基づいている。
論文 参考訳（メタデータ） (2023-02-23T19:13:30Z) - List-Decodable Covariance Estimation [1.9290392443571387]
共分散推定アルゴリズムを初めて提案する。
この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
論文 参考訳（メタデータ） (2022-06-22T09:38:06Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。