Compositional Approximation Can Strictly Outperform Superpositional Approximation

技術要約：構成的近似は重ね合わせ的近似を厳密に凌駕し得る

問題提起
本論文は、近似理論における根本的な問いに取り組んでいる。すなわち、どのような条件下で、構成的（compositional）な手法（ニューラルネットワークなど）が、重ね合わせ的（superpositional）な手法（辞書の要素の線形結合、例えばM項近似など）よりも厳密に優れた近似率を提供できるのかという問いである。経験的な証拠はニューラルネットワークの強力さを示唆しているが、理論的な正当化の多くは、既存の手法を模倣し、同等あるいは同程度の率を達成することに留まっている。さらに、多くの古典的な関数クラスは、最適なM項近似率をもたらす辞書を持つ。著者らは、構成的近似が、いかなる重ね合わせ的近似をも厳密に凌駕できるような関数クラスの構造的特性を特定しようとしている。その際、パラメータのビット列による効率的な符号化を可能にする制約（「力まかせ」な辞書構築を防ぐための制約）の下でも、この優位性が成立するように設計されている。

手法とフレームワーク
著者らは、近似スキームを比較するために、ヒルベルト空間 $H$ 内の厳密な数学的フレームワークを確立している。

1. 近似率: 著者らは、パラメータ予算 $M$ の関数としての一様誤差の多項式減衰次数として、近似率 $\gamma(C, S)$ を定義する。
2. 重ね合わせ的スキーム: これらは、辞書要素 $D = (\phi_i)_{i \in \mathbb{N}}$ の $M$ 項線形結合として定義されるが、「多項式深さ探索」の制約が付随する。この制約は、使用される辞書要素のインデックスおよび係数の大きさを $M$ の多項式に制限するものであり、これにより近似関数が長さ $O(M \log^q M)$ のビット列として符号化できることを保証している。リエッツ近似率 ($\gamma_{\text{Riesz}}$) は、下部リエッツ境界を満たす任意の辞書によって達成可能な近似率の余剰（supremum）である（これは安定性を保証するものである）。
3. 構成的スキーム: これらは、深さ（$M$ の対数多項式）、連結性（$M$ に関して線形）、および重みの大きさ（$M$ に関して多項式）に制約を持つニューラルネットワークを通じてモデル化される。これにより、同様のビット列符号化効率が確保される。
4. 幾何学的視点: 理論的な核心となる洞察は、関数クラスの漸近的幾何学に基づいている。著者らは、ある関数クラスが、限られた数の低次元線形部分空間の和集合によって $\epsilon$-近似可能であるが（これは構成的構造によって活用可能な構造である）、線形近似には高次元の線形部分空間を必要とする場合、近似率にギャップが生じる可能性があると主張している。これは「被覆数（covering numbers）」の概念に関連しており、$\epsilon \to 0$ となるにつれて、非線形な近似集合が、必要な線形空間に対して極めて微小になることを示している。

主要な貢献と結果

1. SPOON構成: 著者らは、SPOON（Superpolynomially growing almost Orthogonal sequeNce：超多項式的に増大する、ほぼ直交する数列）と呼ばれる典型的な集合構造を導入している。SPOONは、以下の性質を持つ一連の集合 $V_m$ で構成される：

   • 濃度が超多項式的に増大する（$|V_m| \ge 2^{m^\alpha}$）。
   • 要素のノルムが $m^{-\mu}$ として減衰する。
   • 要素が互いに $\eta$-ほぼ直交しており、内積の境界が $m^{-\nu}$ として減衰する。

2. 重ね合わせ的近似率の上界（定理 3.4）: 中心となる理論的結果は、関数クラス $C$ が $(\mu, \nu)$-SPOON を含む場合、達成可能な最良のリエッツ近似率は次のように抑えられることを証明している：
   $$\gamma_{\text{Riesz}}(C) \le \frac{1}{2} + \frac{\mu}{\nu}$$
   この証明は、ほぼ直交する集合の幾何学と、リエッツ辞書の性質を用いた背理法を用いている。これは、リエッツ条件を満たすいかなる辞書も、SPOON 内の指数関数的に巨大でほぼ直交する集合を、多項式個の項のみを用いて効率的に被覆することはできないことを示している。

3. 明示的な構成（セクション 4）: 著者らは、「ハット」関数 $f$ の合成を用いて、明示的な関数クラス $V(k, \alpha, \beta, \mu)$ を構築している。これらのクラスは、バイナリベクトルによって定義される関数の反復合成によって形成される。

   • これらのクラスが、大きな、ほぼ直交する関数の集合を含むことを証明している。
   • ReLUニューラルネットワークが、$\gamma_{\rho}^N \ge \frac{\mu}{\alpha}$ という率でこれらのクラスを近似できることを示している。
   • これらを組み合わせることで、特定のパラメータ選択（例：$\mu = \sqrt{k}$）において、構成的近似率とリエッツ近似率の間のギャップが、合成の深さ $k$ が増加するにつれて任意に大きくなることを示している。具体的には、$\lim_{k \to \infty} \gamma_{\rho}^N = \infty$ である一方で、$\lim_{k \to \infty} \gamma_{\text{Riesz}} \le \frac{1}{2}$ となる。

4. 病的な直交性の例（付録 A）: 本論文では、係数が対数的に減衰する正規直交系の、より単純で、かつ病的な例も提示している。この場合、重ね合わせ的近似は $-\infty$ の率（多項式的な減衰なし）をもたらすが、ニューラルネットワークは正の率を達成しており、重ね合わせ的手法が高度に直交した構造に対して直面する困難さを浮き彫りにしている。

意義と主張
本論文は、安定性（リエッツ）および符号化の制約の下で最適な辞書を選択することを許容した場合であっても、構成的近似が重ね合わせ的近似を厳密に凌駕する、最初のエクプリシット（明示的）な例を提供したと主張している。

その意義は、特定の構造的特性――有限次元の部分空間内における、大規模でほぼ直交する集合の存在――を特定した点にある。この特性は、線形結合では効率的に捉えることが極めて困難であるが、単純な構成要素の階層的な合成によって自然に扱えるものである。著者らは、この構造的な不一致が、ニューラルネットワークが不安定性や無制限のパラメータ符号化に頼ることなく、特定のクラスに対してより優れた率を達成できる理由であると論じている。本研究は、ニューラルネットワークの優位性が単なる普遍近似能にあるのではなく、この「ほぼ直交する」構造を持つ関数クラスに対する特定の幾何学的適応能にあることを示唆している。

著者らは、自らの結果の適用範囲について謙虚な姿勢を保っており、これらの結果は特定のSPOON構造を含む関数クラスに適用されること、また現在の重ね合わせ的近似率の境界はリエッツ辞書に限定されていることを注記している。ただし、これらは根本的な制限ではなく、技術的な制限であると考えている。彼らは、これらの結果がすべての関数クラスに適用されることや、ニューラルネットワークが普遍的に優れていることを主張しているのではない。むしろ、この特定の漸近的幾何学的構造を示すクラスに対して、ニューラルネットワークが優位にあることを主張しているのである。