技術要約：二乗和（Sum of Squares）による劣モジュラ性の判定

問題設定

劣モジュラ性（Submodularity）は、集合関数の基本的な構造的特性であり、「収穫逓減」の概念をコード化したものである。これは最適化理論において中心的な役割を果たし、経済学、機械学習、オペレーションズ・リサーチに現れるものであり、「離散的な凸性」とも呼ばれる。制約なしの劣モジュダル関数の最小化は多項式時間で解けるが、基数制約下での最大化は、貪欲アルゴリズムによって $(1 - 1/e)$ 近似が可能である。一方で、一般的な集合関数が劣モジュラであるかどうかを判定する問題は、計算量的に困難である。具体的には、次数 $d \ge 4$ の集合関数に対して、決定問題は co-NP 完全である (Crama 1989; Gallo and Simeone 1989)。

この困難さは、劣モジュラ性を証明するための扱いやすい十分条件の必要性を動機づけている。既存のアプローチは、多くの場合、問題固有のヒューリスティックに依存しているか、あるいは広範な手動チューニングを必要とする。本論文は、劣モジュラ性の基礎的な離散構造と、実代数幾何学のツール、特に二乗和（Sum of Squares; SOS）階層との間のギャップに対処し、体系的な代数的フレームワークを提供することを目指している。

手法

著者らは、$t$ という整数によってインデックス付けされた階層である $t$-sos 劣モジュラ性を導入する。この手法は、集合関数とその**多重線形拡張（Multilinear Extension; MLE）**の間の対応関係に基づいている。MLEは多重線形多項式である。

核となる定義

1. 多重線形拡張 (MLE): 集合関数 $f: 2^\Omega \to \mathbb{R}$ は、一意に多重線形多項式 $F \in \mathbb{R}[x_1, \dots, x_n]$ によって表現される。ここで $F(\mathbf{1}_S) = f(S)$ がすべての $S \subseteq \Omega$ に対して成立する。
2. 代数的特徴付け: 劣モジュラ性は、MLE の二次の混合部分微分がブール超立方体 $\{0, 1\}^n$ 上で非正であること（すなわち $\frac{\partial^2 F}{\partial x_i \partial x_j} \le 0$）によって特徴付けられる。
3. $t$-sos 劣モジュラ性: 集合関数 $f$ が $t$-sos 劣モジュラであるとは、すべての $i \neq j$ について、多項式 $-\frac{\partial^2 F}{\partial x_i \partial x_j}$ が、イデアル $I_2[x_{-i,j}] = \langle x_k^2 - x_k \mid k \neq i, j \rangle$ を法として、次数が最大 $t$ の多項式の二乗和であることである。このイデアルは、ブール制約 $x_k \in \{0, 1\}$ を強制する。

計算フレームワーク

$t$-sos 劣モジュラ性のチェックは、半正定値計画問題 (Semidefinite Program; SDP) に帰着される。固定された $t$ および基底集合のサイズ $n$ に対して、検証には $n(n-1)/2$ 個の制約を含む SDP の解決が必要であり、各制約行列のサイズは $n$ に関して多項式である（具体的には $\sum_{k=0}^t \binom{n-2}{k}$）。

本論文は、劣モジュラ性の7つの標準的な定義（例：収穫逓減、格子不等式）に対応する、いくつかの等価な代数的特徴付けを確立している。これらの特徴付けは代数的に等価であるが、著者らは二次の形式（混合部分微分に基づくもの）が最小の SDP 表現をもたらし、最も計算効率が高いことを示している。

主な貢献

1. 理論的基礎

• 階層の構築: 本論文は、$t$-sos 劣モジュラ関数は必ず劣モジュラルであるという性質を持つ階層として、$t$-sos 劣モジュラ性を定義する。逆に、次数 $d$ の任意の劣モジュダル関数は、十分大きな $t$（具体的には $t = \lceil \frac{n+d-5}{2} \rceil$）に対して $t$-sos 劣モジュラとなる。
• 複雑性のギャップ分析:
  • 次数 $d < 4$ の場合、劣モジュラ性と $t$-sos 劣モジュラ性は小さな $t$（例：$d=2$ では $t=0$、$d=3$ では $t=1$）において一致する。これは、劣モジュラ性判定が $d \le 3$ で多項式時間である事実と一致する。
  • $d=4$ の場合、本論文は、$t$-sos 劣モジュラとして証明するために $t \approx n/2$ を必要とする劣モジュダル関数を構成しており、これは問題固有の困難さを反映している。
• 保存特性: 著者らは、$t$-sos 劣モジュラ性を保存する操作（非負の重み付き和、補集合、制限、縮約）と、保存しない操作（部分最小化、畳み込み、単調化）を特定している。後者は、必要な $t$ を劇的に増大させる可能性がある。

2. 応用

本論文は、$t$-sos 劣モジュラ性の有用性を以下の3つの領域で示している。

• 劣モジュダル回帰 (Submodular Regression): 著者らは、SDP を通じてデータに $t$-sos 劣モジュダル多項式を適合させる手法を提案する。既存の手法（ニューラルネットワークベースのアプローチやヒューリスティックなシェル混合など）とは異なり、このアプローチは最小限の手動チューニング（多項式の次数 $k$ と SOS の次数 $t$ のみ）を必要とし、劣モジュダルな出力を保証する。実験結果では、制約なしの多項式回帰や最先端のニューラル手法と比較して、ノイズを含むデータに対して優れた汎化誤差を示した。
• 近似劣モジュダル最大化: 近似的に劣モジュダルな関数の最大化において、貪欲アルゴリズムの性能は劣モジュラリティ比 $\gamma^*$ に依存する。$\gamma^*$ の計算は NP 困難である。本論文は、$t$-sos 劣モジュラ性を用いた、$\gamma^*$ の下界を導出するための体系的な SDP ベースの手順を提供し、数値実験においてスペクトル境界を改善した。
• 差分劣モジュダル (Difference-of-Submodular; DS) 最適化: DS 最適化問題（$\min g - h$）は、劣モジュダル・スーパモジュダル・プロシージャ (SSP) を通じて解かれる。解の質は、特定の DS 分解に依存する。著者らは、より良い局所最適解を得るために、劣モジュダル成分 $h$ の曲率を最大化する既約分解を見つけるための SDP を提案している。これは、自明な分解と比較して計算時間は増えるものの、大幅に優れた結果をもたらす。

結果

• 理論面: 本論文は、集合関数の次数に基づいて、劣モジュラ性と $t$-sos 劣モジュラ性が一致する場合の完全な分類を提供している。$d \ge 4$ の場合、両概念の間のギャップは大きくなり、高いレベルの階層が必要になることを証明している。
• 実証面:
  • 回帰タスクにおいて、$t$-sos アプローチは、合成的な劣モジュダルデータに対するテスト RMSE において、制約なしの多項式回帰および FlexSubNet ニューラルネットワーク手法の両方を上回った。
  • DS 最適化において、SOS 由来の既約分解を使用することで、様々な問題サイズ（$n=10, 15, 20$）にわたって、自明な分解と比較して平均相対最適度ギャップを約 10～15 パーセントポイント減少させた。
  • SDP ベースの下界は、既存のスペクトル境界よりもタイトであった。

意義と主張

本論文は、離散最適化と実代数幾何学の間に新しい架け橋を築くことを主張している。SOS ベースの代数的証明を劣モジュラ性に結びつけることで、従来の組合せ論的なチェックが失敗する場面において、劣モジュダルな構造を証明し活用するための、扱いやすく体系的なフレームワークを提供している。

その意義は以下の点にある：

1. 扱いやすさ（Tractability）: co-NP 完全な検証問題を、固定された $t$ に対して多項式時間の SDP チェックへと変換したこと。
2. 体系的なアプローチ: 境界の導出や分解のために、場当たり的で問題固有の洞察に頼るのではなく、統一された代数的フレームワークを提供したこと。
3. 実用的な有用性: 代数的な劣モジュラ制約を課すことが、非凸なニューラルネットワーク訓練の不安定さを回避しつつ、回帰や最適化タスクの性能を向上させることを示したこと。

著者らは、階層自体は完全である（任意の劣モジュダル関数は最終的に $t$-sos 劣モジュラとなる）ものの、計算コストは $t$ と $n$ とともに増大するため、本手法は現在、低次数の関数や、適度な $t$ で十分な場合に最も効果的であることを認め、限界についても謙虚に述べている。今後の展望として、ラッセア・ヒエラルキー（Lasserre hierarchy）を通じた制約なし最小化への拡張や、回帰手法に対する形式的な統計的保証の確立が挙げられている。