技術要約：スカラー倍ゲートを持つトロピカル回路

問題設定

本論文は、正の実数による定数倍の演算を可能にするゲートによって標準的なトロピカル（max-plus）回路を拡張したモデルである、**スカラー・トロピカル回路（STC）**の計算能力を調査している。標準的なトロピカル回路はmaxと+ゲートのみを使用し、純粋な動的計画法をモデルすることが知られている。ニューラルネットワーク（具体的にはReLUおよびmaxoutネットワーク）は、負の重みを通じて減算を実装できる能力があるため、トロピカル回路よりも厳密に強力であることが確立されているが、スカラー倍（減算なし）が計算能力に与える具体的な寄与については未解決の問題であった。

中心となる問題は、正の定数によるスカラー倍を許容することで、特定の多面体（特にマルチリニアなトロピカル多項式である0-1係数を持つもの）のサポート関数を計算するために必要な回路サイズが大幅に削減されるかどうかである。具体的には、著者らは次のように問いかけている：多項式的な拡張複雑性（extension complexity）を持つ多面体の中で、STCにおいて指数サイズのサイズを必要とするものは存在するのか？

手法

1. モデルの定義

著者らは、以下の3種類のゲートを持つ有向非巡回グラフとしてSTCを定義している：

• Maxゲート: $\max(u, w)$ を計算する。
• Plusゲート: $u + w$ を計算する。
• スカラーゲート: 定数 $\lambda \in \mathbb{R}_{>0}$ に対して $\lambda u$ を計算する。
  STCのサイズは、スカラーゲートを除いたmaxおよび+ゲートの数として定義される。

2. 幾何学的双対性

この解析は、サポート関数と多面体の間の双対性に依拠している。関数 $f$ を計算するSTCは、関数 $f$ が多面体 $P$ のサポート関数となるような多面体 $P$（ニュートン多面体）を構成することに対応する。

• maxゲートは、多面体の和の凸包に対応する：$P_{max} = \text{conv}(P_u \cup P_w)$。
• +ゲートは、ミンコフスキー和に対応する：$P_{+} = P_u + P_w$。
• スラーゲートは、膨張（dilation）に対応する：$P_{\lambda} = \lambda P_u$。

3. 分解補題（一般的な下界戦略）

核心となる技術的貢献は、STC用に適応された一般化された分解補題（Lemma 3.5）である。標準的なトロピカル回路ではニュートン多面体の頂点が整数のみであるのに対し、STCは非整数の頂点を持つ多面体を生成し得る。
この補題は、もし多面体 $Q$ がサイズ $t$ のSTCによって計算されるならば、$Q$ は以下のように分解できることを述べている：
$$Q = \text{conv}\left(A_0 \cup \bigcup_{i=1}^k (A_i + B_i)\right)$$
ここで $k \le t$ であり、各多面体 $A_i$ は選択された測度 $\mu$ に関して「単純」である。測度 $\mu$ は、ミンコフスキー和および凸包の下での劣加法性を満たさなければならない。

4. 測度の選択

下界を証明するために、著者らはターゲットとなる多面体に特化した特定の測度 $\mu$ を構築している。戦略としては、上述の形式の分解（$A_i$ が「単純」な $A_i + B_i$）は、ターゲットとなる多面体の頂点のわずかな割合しか含むことができないため、多数の項（$k$）を必要とすることを示すというものである。

主要な貢献と結果

1. STCに対する指数的下界

本論文は、スカラー倍が以下の2つの基本的な組合せ最適化問題に対して、回路サイズを大幅に減少させないことを証明している：

• バーコフ多面体 ($P_{PERM}$): 完全二部グラフ $K_{n,n}$ における完全マッチングの凸包。

  • 結果: $P_{PERM}$ のサポート関数を計算する任意のSTCは、$\Omega(2^n)$ 個のプラスゲートを必要とする（Theorem 1.1）。
  • 文脈: $P_{PERM}$ の拡張複雑性は多項式的（$O(n^2)$）であるが、STCのサイズは指数的である。これは、拡張複雑性に基づく下界が指数関数的に緩くなり得ることを示している。

• 有向全域木多面体 ($P_{DST}$): 完全有向グラフにおけるノード $n$ を根とするアルボレセンス（根付き木）の凸包。

  • 結果: 任意のSTCは、$P_{DST}$ のサポート関数を計算するために $\Omega(2^n)$ 個のプラスゲートを必要とする（Theorem 1.2）。
  • 文脈: これは、標準的なトロピカル回路に関するJerrumおよびSnir [JS82] の古典的な結果をスカラーの場合へと拡張したものである。

2. モノトーンおよび非モノトーン・ニューラルネットワークの分離

著者らは、ニューラルネットワークに関する系を導出している：

• 定義:
  • $nnc(P)$:$f_P$ を計算するランク2のmaxoutネットワークの最小サイズ。
  • $mnnc(P)$:$f_P$ を計算するランク2のmaxout 入力凸ニューラルネットワーク（ICNN）（入力エッジに対してのみモノトーンな重みが許可される）の最小サイズ。
• 系 1.3: $mnnc(P_{PERM}) \in 2^{\Omega(n)}$。
• 系 1.4: 有向全域木多面体については、$nnc(P_{DST}) \in O(n^3)$ （多項式）である一方で、$mnnc(P_{DST}) \in 2^{\Omega(n)}$ （指数的）である。
• 意義: これは、モノトーン（ICNN）と非モノトーンなニューラルネットワークの間の指数的なサイズの分離を確立している。これは、凸性の制約（ICNNにおけるような）を課すことで、同じ関数を表現するために、制限のないネットワークと比較して指数関数的に大きなネットワークが必要になる可能性があることを証明している。

3. STCによるモノトーン・ネットワークのシミュレーション

証明の重要なステップは、サイズ $s$ のバイアスなしモノトーン・ランク $k$ maxoutネットワークが、サイズ $O(s^2)$ のSTCによってシミュレート可能であることを示すLemma 3.3である。これにより、STCに対して導出された下界を、モノトーン・maxoutネットワークに直接転用することが可能となる。

意義と主張

本論文は以下の意義を主張している：

1. スカラー倍の限界: 0-1係数を持つ関数（0-1多面体のサポート関数）に対して、任意の正のスカラー倍を行う能力が、標準的なトロピカル回路と比較して、回路サイズにおいて有意な利点を提供しないことを示している。
2. 動的計画法の限界: これらの結果は、「純粋な」動的計画法に正のスカラー倍を加えても、最大重み有向全域木問題や二部完全マッチング問題を解くために、依然として指数関数的な反復を必要とすることを意味している。
3. ニューラルネットワーク理論: 本研究は、入力凸ニューラルネットワーク（ICNN）が、制限のないモデルよりも性能が低かったり、より多くのリソースを必要としたりすることが多いという観察に対して、厳密な理論的根拠を与えるものである。これは、有向全域木のような特定のクラスの関数に対して、モノトーン/凸アーキテクチャへの制限がネットワークサイズの指数関数的な増大を強いることを証明している。
4. 下界手法の洗練: 著者らは、非整数の頂点を扱う多面体分解手法を導入し、算術およびトロピカル回路で使用されてきた従来の手法を一般化した。

限界と未解決問題

著者らは、指数的な下界を証明してはいるものの、指数における定数が標準的なトロピカル回路（例：バーコフ多面体に対して $2^n$）よりも弱い（例：$2^{0.918n}$）ことを謙虚に認めている。また、スカラー倍を用いても、無向全域木多面体に対して多項式サイズのSTCが存在するかどうかは、有向ケースで使用された手法がスカラー倍を保持する可能性のある組合せ構造に依存しているため、未解決の問いとして残っていることも指摘している。さらに、パーマネント（およびしたがって $nnc(P_{PERM})$ が多項式であるか）に対して、多項式サイズの (max, +, -) 回路が存在するかどうかという問題も未解決のままである。