Abstract
二値分類におけるVC次元に関する最適なサンプル複雑度はよく確立されている一方で、多クラス分類における最適なサンプル複雑度の決定は未解決のままであった。多クラス分類に適切な複雑度パラメータはDS次元であり、さまざまな努力にもかかわらず、サンプル複雑度の上界と下界の間にはsqrt{\text{DS}}のギャップが残り続けてきた。
Hannekeら（2026）による最近の研究は、DS次元に基づく代数的な観点から多クラス仮説クラスを新たに特徴づけることを示している。これを土台として、任意の多クラス仮説クラスの最大の双曲グラフ密度が、そのDS次元によって上から抑えられることを示す。これはDanielyとShalev-Shwartz（2014）による長年の予想を証明する。その結果として、我々は、多クラスに対してもリスト学習に対しても、サンプル複雑度がDS次元にどのように最適に依存するかを決定する。
