統計学輪講 第15回

劣モジュラ関数最小化は、離散最適化における基本問題の一つであり、Lovász 拡張を通じて凸最適化とも密接に関係する。本発表では、ある劣モジュラ関数に一様に近いものの、それ自身は劣モジュラとは限らない関数を、値の問い合わせだけを用いて最小化する問題を考える。厳密な劣モジュラ性が小さな摂動によって失われたとき、通常の劣モジュラ最小化の計算可能性がどこまで残るか、という問題である。

Lovász 拡張上での近似劣勾配を用いることで、多項式回の問い合わせによる最小化誤差の上界を与える。特に、反復点の量子化と座標順序のランダム化を組み合わせると、観測誤差によるバイアスが Shapley 値として現れることを利用する。Shapley 値の次元に依存しないノルム評価により、単純な手法より良い誤差保証が得られる。一方で、基礎となる関数がモジュラ (線形) である場合にも成立する情報理論的な下界を示し、上界との間に依然としてギャップが残ることを明らかにする。最後に、凸最適化における類似の問題との関係と未解決問題について述べる。