技術要約：スプライン回帰におけるコルモゴロフ最適スケーリング則

問題提起

機械学習におけるハイパーパラメータチューニングは、伝統的にグリッドサーチや交差検証（CV）に依存した探索プロセスである。このアプローチは計算コストが高く、基礎となる統計的メカニズムに関する情報を提供せず、モデルの複雑さに伴ってスケーラビリティが低下する。特にスプライン回帰において、最適な解像度（各座標あたりのノット間隔の数、$G$と表記）は、古典的な近似理論によって閉形式の解が存在することを示唆されているにもかかわらず、通常は探索によって選択される。

本研究が取り組む核心的な課題は、構造化されたスプライン回帰のための最適解像度 $G^\star$ が、グリッドスイープの代わりに定数個のモデル適合で済むような、解析的に解けるものであるかどうかである。これには、バイアス・バリアンスのトレードオフを最小限の適合回数から特定できる、予測誤差がハイパーパラメータに対して解析的に扱いやすいモデルクラスが必要となる。

手法：KORE (Kolmogorov-Optimal Order-aware Resolution Estimation)

本論文は、最適解像度のための閉形式のスケーリング則を導出する、探索フリーのアルゴリズムであるKOREを提案している。この手法は、以下の3つの理論的柱に基づいている。

1. コルモゴロフ最適近似: スプライン回帰のバイアスは $G^{-2\beta}$ に結び付けられる。ここで $\beta$ は滑らかさの指数である。このレートは、滑らかさのクラスの**コルモゴロフ $n$ 幅（Kolmogorov $n$-width）**と正確に一致しており、これはスプラインがそのサイズにおける線形手法の中で近似的に最適であることを意味する。
2. 明示的な基底次元: 基底関数の数 $p(G)$ は、入力の次元数ではなく、ターゲット関数の相互作用次数（例：加法的なものか、疎なペアワイズか）によって決定される、解像度 $G$ の明示的な多項式である。
3. 閉形式のリスク推定: スプラインは線形スムーザーであるため、モデルを再適合することなく、PRESS恒等式を介して正確なLeave-One-Out (LOO) 誤差を計算できる。

スケーリング則

期待される超過テスト誤差（MSEから既約ノイズ $\sigma^2$ を引いたもの）は、バイアスとバリアンスに分解される：
$$\text{Err}(G) - \sigma^2 \approx A G^{-2\beta} + \tau \frac{p(G)}{n}$$
ここで：

• $A$ はバイアスのスケール定数である。
• $\tau$ はノイズ／バリアンスのスケール定数である。
• $p(G)$ は基底次元であり、生の入力次元 $d$ ではなく、有効密度 $n/s_r$ （ここで $s_r$ は活性な最高次相互作用成分の数）に伴ってスケールする。

最適解像度 $G^\star$ は、この曲線の最小値である。相互作用次数 $r$ と滑らかさ $\beta$ を持つターゲットに対し、スケーリング則は以下の通りとなる：
$$G^\star \propto \left( \frac{n}{s_r} \right)^{\frac{1}{2\beta + r}}$$
極めて重要な点は、入力次元 $d$ は指数の項に現れず、活性な成分の数 $s_r$ のみが影響を与えることである。

KORE アルゴリズム

KOREは、未知の定数 $A$ と $\tau$ を推定し、$G^\star$ を解くことで、グリッド探索の代わりに機能する。

1. パイロット適合: 2つの異なるパイロット解像度（$G_a$ および $G_b$）でスプラインモデルを適合させる。
2. レバレッジ校正推定: PRESS恒等式を用いて正確なLOO誤差を計算する。PRESS恒等式におけるレバレッジによる膨張を補正しながら、2×2の線形系を解いて、バイアスのスケール（$\hat{A}$）とノイズ／バリアンスのスケール（$\hat{\tau}$）を推定する。
3. 閉形式の解: リスク曲線の微分に $\hat{A}$ と $\hat{\tau}$ を代入し、連続的な最適解 $\hat{G}^\dagger$ を求める。
4. 認証: $\hat{G}^\dagger$ を最も近い整数に丸め、小さな対称近傍（例：$\pm 3$）に対してLOOスコアを用いて検証する。これは、完全なグリッド探索ではなく、有限サンプルにおける離散化誤差に対する認証として機能する。

主な貢献

1. 内在的次数テスト誤差則: 本論文は、最適解像度が入力次元に対して指数関数的に増大するのではなく、活性な最高次相互作用の数（$s_r$）に対してスケールすることを確立した。バイアス項はコルモゴロフ $n$ 幅として特定されており、これによりスプラインファミリーが近似理論的に最適であることが保証される。
2. 探索フリー・アルゴリズム (KORE): 網羅的なグリッド探索を、2回のパイロット適合と閉形式のプラグイン解への置き換えを実現する実用的なアルゴリズムである。
3. 一貫性定理: 推定された定数およびプラグイン解が、サンプルサイズ $n \to \infty$ において母集団の対応値に収束することを証明している。整数セレクターは、オラクル・マージンがプラグイン誤差を上回る場合、完全なリスク最小値と確率的に一致する。
4. 実証的検証: 広範な実験により、KOREが網羅的な3分割交差検証（3-fold CV）および古典的な基準（GCV, AIC, BIC）と同等の精度を実現しつつ、モデル適合回数を約8分の1に削減できることを示した。

結果

合成実験

• 有効密度の崩壊: 次元 $d \in \{10, 20, 40, 80\}$ 全体において、テスト誤差と最適解像度は、有効密度 $\rho = n/s_r$ に対してプロットした際に単一の曲線へと収束（collapse）し、理論的なスケーリング則を裏付けた。
• 一貫性: $n$ が増加するにつれ、推定されたバイアスおよびノイズのスケールは1（母集団の値に対する相対値）に収束し、選択された解像度は母集団の最適値に収束する。
• 精度・計算量フロンティア: 制御された加法的および疎なペアワイズ・タスクにおいて、KOREは網羅的なCVと比較してテストRMSE比 $\le 1.0$ を達成し（連続最適化によるものにより、しばしばCVより優れた結果となる）、モデル適合回数を約91回から9〜14回へと削減した。

実世界のベンチマーク

• テーブルデータ: 36の現実世界のテーブルデータセット（OpenML-CTR23 + Combined Cycle）において、KOREを調整済みの勾配ブースター（XGBoost, LightGBM）、カーネルマシン、その他のスプラインセレクターを含む21のベースラインと比較した。
• 計算量正規化リフト (CNL): 精度を計算時間で評価する指標において、KOREはすべての21の手法の中で第1位となった。KOREは、同等の（あるいはそれ以上の）生精度を得るために数桁多くの計算量を必要とした調整済み勾配ブースターやカーネルマシンを上回った。
• 堅牢性: KOREは、滑らかな低次ターゲットに対しては網羅的なCVと同等またはそれを上回る性能を示した。ただし、高次の相互作用、深いカテゴリカルな分岐、または極端な空間的不均一性（例：「Oscillator」や「Franke」のベンチマーク）を持つターゲットでは、単一のグローバルな解像度の仮定が構造的に破綻するため、失敗した。

意義と主張

本論文は、特定のモデルクラスにおけるハイパーパラメータの扱いに関する根本的な転換を主張している：

• 探索から計算へ: スプライン回帰にとって、最適解像度は試行錯誤によって調整される不透明なつまみではなく、データ分布とモデルファミリーから直接計算可能な**統計的推定対象（estimand）**である。
• コルモゴロフ最適性: 本手法が「コルモゴロフ最適」とされるのは、それが最高の線形近似率（コルモゴロフ $n$ 幅）を実現する部分空間のファミリー内で動作し、バイアスとバリアンスのバランスが最適となる点を単にチューニングしているためである。
• スケーラビリティ: 入力次元を相互作用次数に置き換えることで、本手法は構造化された問題（加法的または疎なペアワイズ）における次元の呪いを回避し、テンソル積グリッドの指数関数的なコストなしに高次元（$d=80$）へのスケーリングを可能にしている。
• 実用的な効率性: アルゴリズムは計算量における「フリーランチ」を提供する。すなわち、網羅的なグリッドサーチと同等（あるいは連続最適化によりしばしばそれ以上）の精度を、ごくわずかな計算コストで提供し、テーブルデータの分析における滑らかな低次回帰タスクにおいて優れた選択肢となる。

結論として、複雑、非凸、または高次相互作用を持つモデル（深層ニューラルネットワークや決定木アンサンブルなど）には依然として探索が必要であるが、スプライン回帰は「探索」よりも「解決」が可能である、成熟したモデルクラスである。