オンライン学習からマルチキャリブレーションへの効率的なブラックボックス還元と、Φ-レグレット最小化への新しい道
arXiv cs.LG / 2026/4/22
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- この論文は、Gordon-Greenwald-Marks（GGM）型のブラックボックス還元を提示し、関数クラスH上の任意のno-regret学習器を、期待変分不等式（EVI）ソルバと組み合わせることでオンライン・マルチキャリブレーション達成へ変換することを示します。
- 逆方向として、効率的なオンライン・マルチキャリブレーションが効率的なEVI解法を含意することを証明し、Φ-レグレットに関するGGMでの固定点の役割との対応関係を明確化します。
- これらの結果は、Garg, Jung, Reingold, Roth（SODA ’24）の主要な未解決問題を解決し、一般性のもとでオラクル効率的なオンライン・マルチキャリブレーションが√T型の保証付きで実現可能であることを示します。
- さらに、当事者らは高次元のオンライン・マルチキャリブレーションから文脈付きΦ-レグレット最小化への細粒度の還元も示し、従来の手法より固定点や半分離のような高度な道具を回避して結果を簡素化しつつレートを改善する新しい経路を与え、RKHS（再生核ヒルベルト空間）などのより豊かな逸脱クラスに頑健な新アルゴリズムも可能にします。
