スケーラブルなサブモジュラ最適化のための適応的閾値駆動型連続グリーディ法

概要: マトロイド制約の下でのサブモジュラ最大化は、感知、データ要約、能動学習、資源配分への応用を持つ組合せ最適化における基本的な問題である。逐次貪欲（Sequential Greedy, SG）アルゴリズムは、取り返しのつかない選択によって rac{1}{2} の近似しか達成できない一方で、連続貪欲（Continuous Greedy, CG）は、多重線形緩和（multilinear relaxation）により最適な igl(1-rac{1}{e}igr) の近似を達成する。しかしその代償として、徐々に密な決定ベクトルが生じ、ほぼすべての基底集合要素に対してエージェントが特徴埋め込みを交換することを強いられる。われわれは extit{ATCG}（\underline{A}daptive \underline{T}hresholded \underline{C}ontinuous \underline{G}reedy；適応的しきい値付き連続貪欲）を提案する。これは、勾配評価を各パーティションごとの進捗比 eta_i の背後で制御し、現在の候補が十分な限界利得を捉えられない場合にのみ各エージェントのアクティブ集合を拡張することで、そもそも送信される特徴埋め込みがどれであるかを直接的に制限する。理論解析により、曲率を考慮した近似保証が確立され、有効因子 au_{mathrm{eff}}=max aw r ight m{ au,1-c ight m} が得られ、しきい値に基づく保証と、低曲率の領域との間を補間する。そこでは extit{ATCG} が CG の性能を回復する。CIFAR-10 動物データセットの一部分上で行った、クラスバランスのとれたプロトタイプ選択問題に関する実験では、 extit{ATCG} はフルの CG 手法と同等の目的関数値を達成しつつ、適応的なアクティブ集合の拡張により通信オーバーヘッドを大幅に削減することが示された。