Solve for the Hyperparameter, Skip the Search: Kolmogorov-Optimal Scaling Laws for Spline Regression

2026-06-22 · 16:41 UTC ·Yong Yi Bay, Kathleen A. Yearick ·1 min read

Brief

Spline-regression hyperparameter tuning can be solved rather than searched: using classical approximation theory (Kolmogorov n-width), an explicit polynomial basis dimension in resolution G, and the PRESS leave-one-out identity, the authors derive a closed-form optimal resolution and a scaling law in interaction order. Their algorithm KORE estimates bias/noise from two pilot fits and computes the plug-in resolution with ~a dozen fits, matching exhaustive 3-fold CV and standard criteria while reducing compute (~8× fewer fits) and ranking best on 36 tabular datasets.

Why it matters

Derives a closed-form minimizer for spline regression resolution by balancing squared bias (given by the Kolmogorov n-width, a known power of resolution G) and variance (via leave-one-out/PRESS); basis dimension is an explicit polynomial in G and the result yields a Kolmogorov-optimal scaling law where optimal resolution and error are power functions of effective density (sample size per active component).

Key details

Introduces KORE (Kolmogorov-optimal Order-aware Resolution Estimation): fit two pilot resolutions, solve a leverage-calibrated 2×2 system for bias/noise scales, evaluate the closed-form plug-in resolution and a small leave-one-out certificate (about a dozen fits). Empirically matches exhaustive 3-fold CV and classical criteria while fitting ≈8× fewer models (additive and sparse pairwise targets up to 80 dims); ranks first in accuracy-per-compute across 36 real tabular datasets versus 20 other methods.

Abstract

Hyperparameter tuning almost always means search: fit the model at every value on a grid, score each by cross-validation, and keep the winner. For spline regression that search is unnecessary. The optimal resolution can be solved for in closed form, to the accuracy an exhaustive search reaches, at a fraction of the compute. Three ingredients make this possible: classical approximation theory pins the squared bias to a known power of the resolution G, exactly the Kolmogorov n-width of the smoothness class; the basis dimension is an explicit polynomial in G; and leave-one-out error follows from a single fit via the PRESS identity. Balancing the two known curves gives the minimizer analytically. We extend this calculus to many coordinates by replacing ambient input dimension with interaction order, the number of active low-order components in an ANOVA decomposition, yielding a scaling law in which the optimal resolution and error are power functions of the effective density (sample size per active component), with input dimension absent from the exponent. The law becomes an algorithm. KORE (Kolmogorov-optimal Order-aware Resolution Estimation) fits two pilot resolutions, solves a leverage-calibrated 2x2 system for the bias and noise scales, and evaluates the closed-form plug-in resolution with a tiny leave-one-out certificate: about a dozen fits instead of a full grid sweep, with a consistency guarantee as the sample grows. Across additive and sparse pairwise targets up to 80 input dimensions, KORE matches exhaustive 3-fold cross-validation and the full classical ladder (GCV, Mallows' Cp, AIC, BIC) while fitting roughly 8x fewer models; on 36 real tabular datasets it ranks first among 21 methods in accuracy per unit of compute, ahead of tuned boosters and kernel machines. When complexity lives in low interaction order, solving for the resolution beats searching for it.

Comment: 49 pages, 26 figures, 12 tables. Code: https://github.com/bay-yearick-lab/kore