Yang Cai氏ら9名の研究者は2026年11月19日(現地時間)、学習理論における長年の課題であったサンプル圧縮予想の進展に関する研究成果を発表した。arXiv cs.LGで公開された論文「Near-Quadratic Sample Compression for All VC Classes」によると、VC次元 $d$ を持つすべての二値概念クラスに対し、サイズ $O(d^2 \log^2 d)$ のサンプル圧縮スキームを構築し、その存在を証明した。
学習理論の分野では、予測器が訓練サンプルの一部のみを用いて定義される場合、それが良好な一般化能力を持つという考えが、1980年代のLittlestoneとWarmuthによる研究に端を発し、サンプル圧縮スキームとして定式化されてきた。この概念は、多くの自然な学習アルゴリズムの解析において利用されている。
FloydとWarmuthは1995年に、VC次元 $d$ を持つすべての二値概念クラスがサイズ $O(d)$ のサンプル圧縮スキームを許容するという予想を提唱した。また、より弱い予想として、サイズが $d$ の多項式であるスキームの存在も問われていた。これらの予想は長年未解決のままであった。
これまでの研究では、MoranとYehudayoffが2016年に $d$ のみに依存する最初のバウンドを示したが、その規模は $d$ に対して指数関数的であった。今回の論文では、これまで未解決であったより弱い方の予想に対し、サイズ $O(d^2 \log^2 d)$ のサンプル圧縮スキームを構築することで、その証明に至った。
参考: arXiv cs.LG (アーカイブ) — 2026年11月20日 14:00 (JST)
この記事をシェア