Technical Summary: Kolmogorov-Optimal Scaling Laws for Spline Regression

Problem Statement

Hyperparameter tuning in machine learning is traditionally a search-based process, relying on exhaustive grid searches or cross-validation (CV) to select optimal settings. This approach is computationally expensive, uninformative regarding the underlying statistical mechanics, and scales poorly with model complexity. Specifically for spline regression, the optimal resolution (the number of knot intervals per coordinate, denoted $G$) is typically selected via search despite the existence of classical approximation theory that suggests a closed-form solution might be possible.

The core challenge addressed is whether the optimal resolution $G^\star$ for structured spline regression can be solved for analytically rather than searched for, thereby replacing a grid sweep with a constant number of model fits. This requires a model class where the prediction error has an analytically tractable dependence on the hyperparameter, specifically one where the bias-variance tradeoff can be pinned down from a minimal number of fits.

Methodology: KORE (Kolmogorov-Optimal Order-aware Resolution Estimation)

The paper proposes KORE, a search-free algorithm that derives a closed-form scaling law for the optimal resolution. The methodology rests on three theoretical pillars:

1. Kolmogorov-Optimal Approximation: The bias of spline regression is pinned to $G^{-2\beta}$, where $\beta$ is the smoothness exponent. This rate corresponds exactly to the Kolmogorov $n$-width of the smoothness class, meaning splines are approximation-optimal among linear methods of their size.
2. Explicit Basis Dimension: The number of basis functions $p(G)$ is an explicit polynomial in the resolution $G$, determined by the interaction order of the target function (e.g., additive vs. sparse pairwise) rather than the ambient input dimension.
3. Closed-Form Risk Estimation: As splines are linear smoothers, the exact Leave-One-Out (LOO) error can be computed via the PRESS identity without refitting the model.

The Scaling Law

The expected excess test error (MSE minus irreducible noise $\sigma^2$) decomposes into bias and variance:
$$\text{Err}(G) - \sigma^2 \approx A G^{-2\beta} + \tau \frac{p(G)}{n}$$
Where:

• $A$ is the bias scale constant.
• $\tau$ is the noise/variance scale constant.
• $p(G)$ is the basis dimension, scaling with the effective density $n/s_r$ (where $s_r$ is the count of active highest-order interaction components), not the raw input dimension $d$.

The optimal resolution $G^\star$ is the minimizer of this curve. For a target with interaction order $r$ and smoothness $\beta$, the scaling law is:
$$G^\star \propto \left( \frac{n}{s_r} \right)^{\frac{1}{2\beta + r}}$$
Crucially, the input dimension $d$ does not appear in the exponent; only the count of active components $s_r$ matters.

The KORE Algorithm

Instead of searching a grid, KORE estimates the unknown constants $A$ and $\tau$ and solves for $G^\star$:

1. Pilot Fits: Fit the spline model at two distinct pilot resolutions ($G_a$ and $G_b$).
2. Leverage-Calibrated Estimation: Compute exact LOO errors using the PRESS identity. Solve a $2 \times 2$ linear system to estimate the bias scale ($\hat{A}$) and noise/variance scale ($\hat{\tau}$), correcting for the leverage inflation in the PRESS identity.
3. Closed-Form Solution: Plug $\hat{A}$ and $\hat{\tau}$ into the derivative of the risk curve to solve for the continuous optimal resolution $\hat{G}^\dagger$.
4. Certification: Round $\hat{G}^\dagger$ to the nearest integer and verify it against a small symmetric neighborhood (e.g., $\pm 3$) using LOO scores. This acts as a certificate against finite-sample discretization error, not a full grid search.

Key Contributions

1. Intrinsic-Order Test-Error Law: The paper establishes that the optimal resolution scales with the count of active highest-order interactions ($s_r$), not exponentially with input dimension. The bias term is identified as the Kolmogorov $n$-width, ensuring the spline family is approximation-theoretically optimal.
2. Search-Free Algorithm (KORE): A practical algorithm that replaces exhaustive grid search with two pilot fits and a closed-form plug-in solution, certified by a tiny LOO neighborhood.
3. Consistency Theorem: The paper proves that the estimated constants and the plug-in resolution converge to their population counterparts as sample size $n \to \infty$. The integer selector matches the exhaustive risk minimizer with probability approaching one once the oracle margin exceeds the plug-in error.
4. Empirical Validation: Extensive experiments demonstrate that KORE matches the accuracy of exhaustive 3-fold CV and classical criteria (GCV, AIC, BIC) while fitting roughly 8$\times$ fewer models.

Results

Synthetic Experiments

• Effective Density Collapse: Across dimensions $d \in \{10, 20, 40, 80\}$, the test error and optimal resolution collapse onto a single curve when plotted against effective density $\rho = n/s_r$, confirming the theoretical scaling law.
• Consistency: As $n$ increases, the estimated bias and noise scales converge to 1 (relative to population values), and the selected resolution converges to the population optimum.
• Accuracy-Compute Frontier: On controlled additive and sparse pairwise tasks, KORE achieves test RMSE ratios $\le 1.0$ compared to exhaustive CV (often slightly better due to continuous optimization vs. discrete grid) while reducing model fits from ~91 (for CV) to ~9–14.

Real-World Benchmarks

• Tabular Data: On 36 real-world tabular datasets (OpenML-CTR23 + Combined Cycle), KORE was compared against 21 baselines, including tuned gradient boosters (XGBoost, LightGBM), kernel machines, and other spline selectors.
• Compute-Normalized Lift (CNL): Using a metric that rewards accuracy per unit of compute time, KORE ranked first among all 21 methods. It outperformed tuned gradient boosters and kernel machines, which required orders of magnitude more compute to achieve comparable (but not superior) raw accuracy.
• Robustness: KORE matched or beat exhaustive CV on smooth, low-order targets. It failed only on targets with high-order interactions, deep categorical splits, or extreme spatial heterogeneity (e.g., the "Oscillator" or "Franke" benchmarks), where the single global resolution assumption is structurally violated.

Significance and Claims

The paper claims a fundamental shift in how hyperparameters are treated for specific model classes:

• From Search to Calculation: For spline regression, the optimal resolution is not an opaque knob to be tuned by trial and error but a statistical estimand that can be computed directly from the data distribution and model family.
• Kolmogorov Optimality: The method is "Kolmogorov-optimal" because it operates within the family of subspaces that realize the best possible linear approximation rate (the Kolmogorov $n$-width) and simply tunes the point on that curve where the bias-variance balance is optimal.
• Scalability: By replacing the input dimension with interaction order in the scaling law, the method avoids the curse of dimensionality for structured problems (additive or sparse pairwise), allowing it to scale to high dimensions ($d=80$) without the exponential cost of tensor-product grids.
• Practical Efficiency: The algorithm offers a "free lunch" in terms of compute: it delivers the accuracy of a full grid search (and often better, due to continuous optimization) at a fraction of the computational cost, making it a superior choice for smooth, low-order regression tasks in tabular data analysis.

The paper concludes that while search remains necessary for complex, non-convex, or high-interaction models (like deep neural networks or tree ensembles), spline regression is a mature class where "solving" is tractable and superior to "searching."