# 可解性複雑性指標(Solvability Complexity Index, SCI) Navigation: [[index]] | [[overview]] ## 定義 可解性複雑性指標(Solvability Complexity Index, SCI)は、ある計算問題をデータから解くために何回の逐次的な極限操作(successive limits)が本質的に必要かを形式化した指標である(Hansen 2011、Ben-Artzi・Colbrook・Hansen・Nevanlinna・Seidel 2020)。「極限」とは、データ量($M \to \infty$)・モデル複雑性($N \to \infty$、次元や辞書サイズ)・正則化パラメータ($\varepsilon \downarrow 0$)など、アルゴリズムが収束のために踏む段階的な精緻化のことを指す。 [[@2026__NatCommun__Adversarial dynamical systems characterize when data-driven learning succeeds or fails]]では、Koopman作用素のスペクトル学習問題にSCIを適用し、上界(収束するアルゴリズムの構成)と下界(敵対的力学系による不可能性証明)を同時に与えることで、問題の複雑性を完全に分類した。具体的には、測度保存性・連続性の法(modulus of continuity)という2条件が両方揃うクラス $\Omega_X^{\alpha,m}$ では単一極限($n \to \infty$)で解けるが、条件が一つ欠けるクラス($\Omega_X^\alpha$ または $\Omega_X^m$)では2つの逐次極限が必要になり、いずれの仮定もない一般クラス $\Omega_X$ では3つの逐次極限(データ数・部分空間次元・正則化パラメータ)が必要になる。この階層は $\Delta_m$(SCI≤$m$のクラス)・$\Sigma_m$・$\Pi_m$(最終極限での検証方向:内側からの収束/上からの収束)という記法で整理される。上界と下界が一致する箇所では、アルゴリズムが証明可能に最適(optimal)であることが示される(Source: [[@2026__NatCommun__Adversarial dynamical systems characterize when data-driven learning succeeds or fails]])。 ## 横断的知見 - (本 wiki では現時点でこの論文が唯一のSCI関連ソースであるため、複数ソース間の横断的知見はまだ蓄積されていない。次にSCIまたは計算可能性理論に関するソースが入った時点で追記する。) ## 未解決の問い - スペクトル計算に依存しない(non-spectral)データ駆動学習問題に対して、SCIの下界をどう確立するか。著者らは敵対的力学系の枠組みがこれらにも拡張できると予想しているが、具体的な構成は今後の課題としている。(Source: [[@2026__NatCommun__Adversarial dynamical systems characterize when data-driven learning succeeds or fails]]) - Table 1に整理された既存アルゴリズム(EDMD・Residual DMD・Hankel DMDなど)のSCI上界の多くは「シャープでない」(必要以上の極限を要求している)と指摘されている。どのアルゴリズムがどこまでシャープ化できるかは未整理。(Source: [[@2026__NatCommun__Adversarial dynamical systems characterize when data-driven learning succeeds or fails]]) ## 関連 - [[@2026__NatCommun__Adversarial dynamical systems characterize when data-driven learning succeeds or fails]] — SCIをKoopman作用素学習に適用し、上界・下界を統一的に分類 - [[Koopman作用素]] ## 出典 - [[@2026__NatCommun__Adversarial dynamical systems characterize when data-driven learning succeeds or fails]]