log n / n 収束レートが一般に最適であることを裏付ける下界を提示する。評価されるグループが、学習目的を緩和することで、サンプルに対して無作為（obliviously）に選ばれるようにすると、我々のアルゴリズムは、グループ実現可能性のもとで最適な 1/n$ 収束レートを達成する。
多グループ学習のための1包含グラフ（One-Inclusion Graph）アプローチ
arXiv cs.LG / 2026/3/25
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、多グループ学習におけるサンプル複雑度の新しく、かつ厳密な上界を提示し、グループ全体で信頼できる性能を得るために必要なデータ量を特徴づけることを目指している。
- 1包含グラフによる予測戦略を拡張し、一般化された二部bマッチングを用いるアルゴリズムを導入する。
- グループが実現可能（group-realizable）な設定では、提案手法の
- \(\log n / n\) 収束レートが一般の場合に最適であることを裏付けるマッチングの下界を示す。
- サンプルに対してターゲットグループが無作為（obliviously）に選ばれる、緩和された評価設定のもとで、アルゴリズムは改良された最適な \(1/n\) 収束レートを達成することが示される。
- 本研究は、多グループ設定において、評価仮定が異なる場合の既知の学習率保証を洗練させる理論的分析として位置づけられている。
