単調劣モジュラ最大化に関する最近の動向

[注意] このブログ記事の筆者は劣モジュラ最適化の専門家ではない．

[Chen+] Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel, NeurIPS21
[Liu+] Cardinality constrained submodular maximization for random streams, NeurIPS21

NeurIPS2021のposter sessionに，Chenらの「Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel」と題する論文が採択されている．この論文では，単調劣モジュラ最大化問題に対する新たな探索手法「LS+PGB」を提案している．この手法は，これまでのSOTAと同じ近似比をより高速に達成できるらしい．

確認ではあるが，この最大化問題は，目的関数（集合に対して実数の評価値を与える関数）が単調劣モジュラ関数であり，n個の候補の中からk個を選択した時の評価値の最大化を目的とする．（cardinality constraint k on a ground set of size n）

単調劣モジュラ最大化問題に対しては，Nemhausarらが1978年に，貪欲法による探索が1-1/e（およそ0.63）の近似比を与えることを示している．つまり，貪欲法という非常にシンプルな方法が，任意の単調劣モジュラ最大化問題について，最悪でも最適解の0.63倍の目的関数値を与える解を出力することを意味する．

Chenらの論文のTable1を見る限り，これまでのSOTA手法たちもこの近似比を上回ってはいない．詳しいことは確認できなかったが，多項式時間アルゴリズムによる近似比として1-1/eはoptimalらしい，つまりこれを上回るのは多項式時間では無理，ということもNemhausarらが示しているらしい．

さて，これまでと同じ近似比を与える新しいアルゴリズムについて，競われているのは速さである．詳しくいうと，「adaptive complexity (adaptivity)」と「query complexity (queries)」である．高速化のために並列化されるのが一般的で，前者は並列化の下でのアルゴリズムのラウンド数，後者は目的関数値の計算回数である．並列アルゴリズムのもとで各ラウンド内でクエリは独立に実行できると仮定されるので，adaptive complexityが低いほど，並列化が効いているアルゴリズムであるといえるらしい．

それぞれ，log n / log log n と nが下界であることが示されている．つまり，これより高速化はできない．

提案手法であるLS+PGBは，queriesに関してほぼ理論的に最適のオーダーである O(n/(epsilon²)) を達成している．また，adaptivityに関しても，ほぼ最適のO(1/(epsilon²) log(n/epsilon))を達成している．

同じくNeurIPS21において，Liuらの「Cardinality constrained submodular maximization for random streams」も提案されている．こちらは，streaming settingと呼ばれ，ground setの元がランダムな順序で一度だけアルゴリズムに与えられるような設定での劣モジュラ最大化手法を提案している．メモリが無限なら全て集めてから普通に最大化をすれば良さそうだが，流石にそういった方向とは対立していて，メモリ消費量のオーダーの削減に注力した手法となっている． cardinality constraint kに対して，O(k/\epsilon)らしい．選択する個数に対して線形と定数倍ってすごいのでは．

アルゴリズムの詳細は理解する前に力尽きたので，また今度．