用数学公式直接算出样条回归最优分辨率,省去耗时调参。
Solve for the Hyperparameter, Skip the Search: Kolmogorov-Optimal Scaling Laws for Spline Regression
- 基于逼近论和PRESS公式,闭式求解最优分辨率
- 在80维数据上性能媲美全网格搜索,仅需约1/8模型训练量
- 适合低阶交互复杂度的表格数据,尤其高效于高维稀疏场景
传统样条回归超参数调优依赖网格搜索,而本文提出无需搜索:最优分辨率可通过闭式公式精确求解,计算量仅为完整搜索的几分之一。核心在于:平方偏差与分辨率G的幂律关系由Kolmogorov n-宽度决定;基函数维度为G的显式多项式;留一法误差仅需一次拟合即可由PRESS恒等式得出。通过平衡两者曲线可解析求得最小化点。该方法拓展至多维情形,以交互阶数替代输入维度,构建出最优分辨率与误差对有效密度(每活跃成分样本数)的幂律关系,且输入维度不参与指数项。由此发展出算法KORE(Kolmogorov-最优阶感知分辨率估计):仅需两次预拟合,解一个校准杠杆的2×2系统获得偏差与噪声尺度,再以极小留一法验证得到闭式插值分辨率。整个过程仅约十余次拟合,相比完整网格搜索节省近8倍计算量,并在36个真实表格数据集上以单位算力精度领先21种方法,超越调优后的提升器与核机器。当复杂性集中于低阶交互时,求解优于搜索。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。