Optimistic Rates for Multiclass PAC Learning

技術要約：マルチクラスPAC学習における楽観的レート

問題設定
本論文は、PAC学習フレームワークにおけるマルチクラス分類の統計的な困難さに取り組んでいる。既存の最悪ケースのマルチクラス学習の境界は、2つの容量パラメータ、すなわちナタラジャン次元（$d_N$）とダニエリ・シャレヴ＝シャヴァッツ（DS）次元（$d_{DS}$）に依存している。既知の最適レートは、実現可能学習（$L^\star = 0$）と完全なアグノスティック学習（$L^\star$ が定数）の両極端においては判明しているが、その中間領域の挙動は未解決のままであった。具体的には、現在の最悪ケースのアグノスティック境界は $\sqrt{d_N/n} + d_{DS}/n$ とスケールしており、「もし最良の分類器がほぼ正しければ（小さなオラクル・リスク $L^\star$）、学習問題はより容易になるはずである」という事実を反映できていない。本研究の目的は、実現可能レートとアグノスティック・レートの間を補間する「楽観的レート」を確立することである。

手法
著者らは、$L^\star$ や信頼レベル $\delta$ の事前知識なしにこの補間を実現する学習器 RMC（Relative Menu Compression）を提案する。証明のアーキテクチャは、[CEH+26] の「カバー–メニュー–圧縮（cover–menu–compression）」による簡約を適応させつつ、新しい統計的インターフェースを導入した3ブロックのサンプル分割戦略に基づいている。

1. ブロック1（カバー）: 決定論的な圧縮器が、無限の仮説集合を、サイズがおよそ $d_{DS} \log^2 n$ の有限な家族 $\hat{\mathcal{F}}$ に縮小する。このステップにより、任意の比較対象 $h$ に対して、その $h$ が正しい領域において $h$ と一致する「標準的な証拠（canonical witness）」が $\hat{\mathcal{F}}$ 内に存在することが保証される。
2. ブロック2（メニュー）: マルチプライカティブ・ウェイト法を用いて、オラクルの正しい領域における標準的な証拠のラベルをカバーする「メニュー」$\mu$（各入力に対する候補ラベルの集合）を学習する。このステップは、正しいラベルがメニューから欠落している確率を制御するが、この失敗モードは $d_{DS}$ によって支配される。
3. ブロック3（圧縮）: メニューが固定されると、問題はメニュー内での二値分類へと還元される。学習器は、ある固定された比較対象を経験的に支配する圧縮ルールを適用する。

核心となる技術的革新は、比較対象指向の相対圧縮定理（Theorem 3.3）である。標準的な圧縮境界が、学習器の母集団リスクをその経験的リスクと比較する（これにより $\sqrt{k/n}$ の変動が生じる）のに対し、この定理は、学習器の母集団リスクを直接、固定された比較対象の母集団リスク $L(h)$ と比較する。これは、もしサイズ $k$ の圧縮ルールが $h$ よりも大きな経験的損失を持たないならば、以下を満たすことを確立している：
$$L(A(S)) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
決定的なのは、係数 $L(h)$ が正確に1であり、変動が $\sqrt{L(h)}$ でスケールすることである。これは、安定性の仮定を必要とせず、重複インデックスを用いた順序付き記述と片側ベルンシュタイン不等式を用いることで達成される。

主な貢献

1. 最適なマルチクラス楽観的レート: 本論文は、ナタジャン次元 $d_N$ と DS 次元 $d_{DS}$ を持つクラスに対して、最適な超過リスクが次であることを証明している：
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   この結果は、アルファベットのサイズに関して一様に成り立つ。$d_N$ 項は $L^\star$ に局在化し、$d_{DS}$ 項は実現可能オーダーの残差として残る。
2. 一致する下界: 著者らは、任意の固定された $L^\star$ に対して、両方の項を同時に強制する単一の仮説集合と単一の分布を構成している。これにより、ラベルの被覆（$d_{DS}$ が制御）とメニュー内の変動（$d_N$ が制御）という役割の分離が、分析の副産物ではなく、問題の本質的な性質であることを確認している。
3. リスト学習への拡張: このアーキテクチャはリスト学習（$r$ 個のラベルを出力する）へと拡張されている。著者らは、最良の $r$-タプルに対する楽観的レートを導出し、変動をオラクル・リスト・リスクに局在化させている。これは、$r$ 次のナタジャン変動項が必要であるという [Pab26] の予想を解消し、因子 $r$ を除去することで既知の実現可能リスト下界を改善するものである。
4. 形式的検証: 主要な定理とその証明は Lean 4 によって機械検証されており、定数や論理的依存関係の正確性が保証されている。

結果

• 上界 (Theorem 3.1): RMC 学習器は、確率 $1-\delta$ でレート $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$ を達成する。この学習器はパラメータフリーである（$L^\star$ および $\delta$ に依存しない）。
• 下界 (Theorem 4.1): $1 \leq d_N \leq d_{DS}$ である任意のとき、期待超過リスクが少なくとも $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$ となるクラスと分布が存在する。この構成は、ノイズを含むナタジャン・キューブと擬似キューブ（[BCD+22] に由来）の積を用い、これら2つの次元を分離している。
• リスト学習 (Theorems 5.1 & 5.2): 楽観的レートは、最良の $r$-タプルに対するリスト学習器にも拡張され、変動項の必要性を裏付ける下界が示されている。さらに、実現可能リスト学習における新しい下界は、[HMZ24] に存在する因子 $r$ を除去している。

意義と主張
本論文は、マルチクラス学習における実現可能レートとアグノスティック・レートの間のギャップを埋め、初の分布フリーかつパラメータフリーなマルチクラス学習の楽観的レートを提供することを主張している。

• 理論的統一: かつてブール・キューブの幾何学 [MQZ26] を通じて二値分類において確立された「係数1」の比較原理が、ラベルの幾何学（メニュー/カバーによって処理）と確率的変動（相対圧縮によって処理）を切り離すことにより、マルチクラスの設定にも持ち上げられることを示している。
• 本質的な分離: 下界は、2つの容量パラメータ（$d_N$ と $d_{DS}$）が、互換性のない明確に異なる役割を果たしていることを証明している。すなわち、$d_{DS}$ は正しいラベルが見えているかどうか（被覆）を決定し、$d_N$ は見えているラベルの中から選択する難易度（変動）を決定する。
• 限界: 著者らは、上界における対数因子が最適化されていないこと、および学習器が情報理論的であること（必ずしも計算効率的ではないこと）を指摘している。また、結果は有限のラベルアルファベットを想定しているが、その大きさに関して一様である。

本研究は、マルチクラスPAC学習における補間問題の解決策として提示されており、統計的な困難さがまさに実現可能性のレベルに依存していること、そしてその困難さがどの程度の速さで劣化するかを精密に示している。