Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

技術的サマリー：深層セットとヤノッシ・プーリングの普遍性に対する埋め込み次元の下限

問題定義
本論文は、置換不変なニューラルネットワークアーキテクチャ、具体的には深層セット（Deep Sets）とその一般化であるヤノッシ・プーリング（Janossy pooling）における普遍性（universality）の理論的問いに取り組む。これらのアーキテクチャが任意の連続な置換不変関数を近似できることは確立されているが、この普遍性を保証するために必要な最小の埋め込み次元 $M$（潜在次元）を決定するという重要な未解決問題が残されている。

先行研究は、上限（例：$d>1$ の場合の深層セットに対して $M \le 2nd + 1$）と自明な下限（例：$d=1$ の場合 $M \ge n$）を提供してきた。しかし、$d > 1$ の深層セットおよび $k > 1$ の $k$ 項ヤノッシ・プーリングに対して、環境次元 $d$ に応じてスケーリングする非自明な下限は知られていなかった。本論文は、定義域 $K = [0, 1]^d$ 上のスカラー出力ケース（$p=1$）に焦点を当て、普遍性に必要な最小埋め込み次元を $M_{univ}(d, n, k)$ と定義する。

手法
著者は、埋め込み次元の下限を確立するために、ボルスク＝ウラムの定理に基づく新規手法を導入する。手法は以下の主要なステップを経て進行する。

1. インデックス付きヤノッシ・プーリングへの還元：著者はまず、標準的な $k$ 項ヤノッシ・アーキテクチャが普遍性を持つならば、より大規模で不変ではない「インデックス付きヤノッシ・プーリング」と呼ばれるクラスの普遍性も意味することを示す。このインデックス付き変種では、エンコーダ関数 $\phi_{i_1, \dots, i_k}$ は、すべての置換にわたって共有されるのではなく、入力タプルの特定のインデックスに依存することを許容する。この還元により、著者はインデックス付きクラスに対する下限を証明でき、それは自動的に元の対称クラスにも適用される。
2. 有限差分の剛性：重要な補題として、インデックス付きヤノッシ・潜在マップが特定の「有限差分の剛性」を満たすことを示す。もしマップがグリッドの「軸」部分集合（少なくとも一つの座標がゼロである部分）で一致するなら、それはグリッド全体で一致しなければならない。この性質は、スパースな入力集合におけるエンコーダの振る舞いと、密なグリッドにおけるその振る舞いを結びつける。
3. ボルスク＝ウラムの構成：下限を証明するために、著者は入力空間内に 2 つの互いに素なコンパクト集合 $E_+$ と $E_-$ を構成する。ボルスク＝ウラムの定理を用いて、埋め込み次元 $M$ が小さすぎる場合（具体的には、導出された閾値より小さい場合）、$\mathbb{R}^M$ へ写像する任意の連続エンコーダ $\Phi$ は、対蹠点のペア（$E_+$ からの 1 点と $E_-$ からの 1 点）を同じ潜在ベクトルに写さなければならないことを示す。
4. 衝突の議論：$E_-$ と $E_+$ でそれぞれ異なる値（0 と 1）をとる連続な目標関数 $g$ を構成することで、エンコーダがこれらの集合からの点を同じ潜在ベクトルに写す場合、いかなるデコーダ $\rho$ も $1/2$ 未満の誤差で $g$ を近似できないことを著者は示す。この矛盾により、仮定された次元 $M$ が普遍性には不十分であることが証明される。

主要な貢献と結果

• 深層セット（$k=1$）に対する新たな下限：本論文は、$\mathbb{R}^d$ 内の $n$ 点の集合に対して作用する深層セットにおいて、最小埋め込み次元が以下の式を満たすことを証明する。
  $$M_{univ}(d, n, 1) \ge d(n - 1)$$
  これは、$d > 1$ に対して環境次元 $d$ に応じて増加する最初の下限である。既存の上限 $2nd + 1$（Dym–Gortler による）と組み合わせることで、必要な次元が定数倍を除いて $\Theta(nd)$ としてスケーリングすることが確立される。$d=1$ の場合、この限界は $n-1$ を与え、加法定数まで $n$ に対する既知の線形依存性を回復する。

• $k$ 項ヤノッシ・プーリング（$k > 1$）に対する最初の非自明な下限：一般的な $k$ 項ヤノッシ・プーリングに対して、著者は $d$ に依存する最初の非自明な下限を導出する。その結果は以下の通りである。
  $$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$$
  この結果は、有限次数の相互作用（$k > 1$）があっても、必要な潜在次元は環境次元 $d$ と集合サイズ $n$ の両方とともに増加しなければならないことを示している。

• 技術的枠組み：本論文は、対称アーキテクチャをインデックス付きのものに還元し、トポロジカルな障害（ボルスク＝ウラム）を潜在空間写像に適用することで普遍性を分析する厳密な枠組みを提供する。

意義と限界
本論文は、これらの結果が先行文献で指摘されていた置換不変ネットワークの次元要件に関する重要な未解決問題を解決すると主張している。具体的には、深層セットにおいて埋め込み次元は $n$ と $d$ の両方に線形にスケーリングしなければならないことを確認し、$d>1$ に対して $n$ 依存の限界のみが知られていた以前のギャップを修正した。$k$ 項プーリングについては、相互作用が $d$ に対する次元増加の必要性を排除しないことを確立している。

著者は、現在の構成における特定の限界を指摘している。

• 深層セット（$k=1$）の場合、限界は $dn$ではなく$d(n-1)$ である。この「1 点の損失」は、証明戦略がボルスク＝ウラムの議論で使用される 2 つの互いに素なコンパクト集合を分離するために、変数の 1 つのブロックを必要とすることに起因する。
• $k > 1$ の場合、下限における指数 $1/k$ は、球面上の領域をラベル付けするために $k$ つの基底変数を使用する現在の構成の限界である。これは、導出された下限と深層セットから継承された $O(nd)$ の上限との間に大きなギャップを残している。

本論文は、$d$、$n$、および $k$ に対する正確な依存関係を決定し、有限次数のヤノッシ・プーリングに対して一致する上限と下限を証明することは、依然として未解決の問題であると結論付けている。