論文の概要: Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
- arxiv url: http://arxiv.org/abs/2602.17577v1
- Date: Thu, 19 Feb 2026 18:02:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-20 15:21:29.241332
- Title: Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
- Title（参考訳）: 同時ブラックウェルアプローチ可能性とマルチクラスOmnipredictionへの応用
- Authors: Lunjia Hu, Kevin Tian, Chutong Yang,
- Abstract要約: コンパレータファミリ $mathcalC$ が無限となるようなマルチクラス設定で全方位法を研究する。
我々の主な成果は、[OKK25] の最近の二進検定アルゴリズムをマルチクラス設定に拡張したことである。
- 参考スコア（独自算出の注目度）: 17.79426749489757
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses $\mathcal{L}$ against a family of comparator predictors $\mathcal{C}$. We initiate the study of omniprediction in a multiclass setting, where the comparator family $\mathcal{C}$ may be infinite. Our main result is an extension of the recent binary omniprediction algorithm of [OKK25] to the multiclass setting, with sample complexity (in statistical settings) or regret horizon (in online settings) $\approx \varepsilon^{-(k+1)}$, for $\varepsilon$-omniprediction in a $k$-class prediction problem. En route to proving this result, we design a framework of potential broader interest for solving Blackwell approachability problems where multiple sets must simultaneously be approached via coupled actions.
- Abstract（参考訳）: オムニプレディクション(Omniprediction)は、損失の族である$\mathcal{L}$と、コンパレータ予測子の族である$\mathcal{C}$のそれぞれに最適な境界を必要とする学習問題である。
多クラス設定において、コンパレータ族 $\mathcal{C}$ が無限であるような全方位の研究を開始する。
我々の主な成果は、最近の[OKK25]のバイナリ・オムニプレディションアルゴリズムをマルチクラス・セッティングに拡張し、サンプルの複雑さ(統計的設定)や後悔の地平線(オンライン設定)を$\approx \varepsilon^{-(k+1)}$, for $\varepsilon$-omniprediction in a $k$-class prediction problem。
この結果の証明に向け、複数の集合を結合作用により同時にアプローチしなければならないブラックウェルのアプローチ可能性問題を解決するための、潜在的に広範な関心の枠組みを設計する。
関連論文リスト
- Rate optimal learning of equilibria from data [63.14746189846806]
マルチエージェント・イミテーション・ラーニング(MAIL)における理論的ギャップは,非対話的MAILの限界を特徴づけ,ほぼ最適なサンプル複雑性を持つ最初の対話的アルゴリズムを提示することによって解決する。
インタラクティブな設定では、報酬のない強化学習と対話型MAILを組み合わせたフレームワークを導入し、それをMAIL-WARMというアルゴリズムでインスタンス化する。
我々は,我々の理論を裏付ける数値的な結果を提供し,グリッドワールドのような環境において,行動クローンが学習に失敗する状況を示す。
論文 参考訳（メタデータ） (2025-10-10T12:28:35Z) - Towards Fundamental Limits for Active Multi-distribution Learning [16.639855803241524]
我々は,多分布学習のための新しいアルゴリズムを開発し,ラベルの複雑さを向上する。
実現可能な設定のバウンダリは情報理論的に最適であり、設定の$knu/varepsilon2$項は適切な学習者にとって基本的なものであることを示す。
論文 参考訳（メタデータ） (2025-06-21T06:08:58Z) - Improved Bounds for Swap Multicalibration and Swap Omniprediction [31.959887895880765]
我々は,有界線型関数に対する$O(sqrtT)$ $ell_2$-swap多重校正誤差を効率よく実現できることを示す。
また、凸関数とリプシッツ関数のクラスに対して、$varepsilon$-swap omnipredictorを効率的に学習する、$O(varepsilon -3)$サンプル複雑性も確立する。
論文 参考訳（メタデータ） (2025-05-27T08:29:35Z) - Omnipredicting Single-Index Models with Multi-Index Models [9.794426212144453]
単調なリプシッツリンク関数によって引き起こされる任意の損失に対して、$varepsilon$-competitive であるオムニプレクタを出力する学習者を与える。
我々のアルゴリズムでは,$approx varepsilon-4$サンプルをほぼ線形時間で実行し,リンク関数がbi-Lipschitzであれば$approx varepsilon-2$に改善する。
論文 参考訳（メタデータ） (2024-11-20T07:20:49Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - 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) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。