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

• URL: http://arxiv.org/abs/2606.23575v1
• Date: Mon, 22 Jun 2026 16:41:10 GMT
• Title: Solve for the Hyperparameter, Skip the Search: Kolmogorov-Optimal Scaling Laws for Spline Regression
• Abstract summary: Optimal resolution can be solved for in closed form, to the accuracy an exhaustive search reaches, at a fraction of the compute.<n>KORE 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Scaling-Score Conformal Prediction for Multi-Target Regression [0.42970700836450476]
  Multi-target regression requires a model to simultaneously predict several related outputs.<n>We propose the scaling-score conformal method, which is model-agnostic (requires only component-wise absolute residuals)
  arXiv  Detail & Related papers  (2026-09-15T12:23:57Z)
• Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation [0.0]
  This paper studies the problem for the integral R2 indicator in three objectives.<n>We show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function.<n>We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision.
  arXiv  Detail & Related papers  (2026-06-25T04:25:20Z)
• Preference-Shaped Expected Hypervolume and R2 Improvement: Exact Computation and Monotonicity [0.0]
  We consider two indicator families which are often used for similar algorithmic purposes, but which are geometrically different.<n>The hypervolume indicator is based on a dystopian reference point and measures dominated volume in objective space.<n>The R2 indicator is based on a utopian point and evaluates approximation sets through weighted Tchebycheff scalarization envelopes.
  arXiv  Detail & Related papers  (2026-05-27T17:02:28Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Optimal Transportation and Alignment Between Gaussian Measures [80.4634530260329]
  Optimal transport (OT) and Gromov-Wasserstein (GW) alignment provide interpretable geometric frameworks for datasets.<n>Because these frameworks are computationally expensive, large-scale applications often rely on closed-form solutions for Gaussian distributions under quadratic cost.<n>This work provides a comprehensive treatment of Gaussian, quadratic cost OT and inner product GW (IGW) alignment, closing several gaps in the literature to broaden applicability.
  arXiv  Detail & Related papers  (2025-12-03T09:01:48Z)
• $\ell_0$-Regularized Quadratic Surface Support Vector Machines [0.0]
  Kernel-free quadratic surface support vector machines have recently gained traction due to their flexibility in modeling nonlinear decision boundaries without relying on kernel functions.<n>We propose a sparse variant of the QSVM by enforcing a cardinality constraint on the model parameters.<n>We validate our approach on several real-world datasets, demonstrating its ability to reduce overfitting while maintaining strong classification performance.
  arXiv  Detail & Related papers  (2025-01-20T04:26:34Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Sliced gradient-enhanced Kriging for high-dimensional function approximation [2.8228516010000617]
  Gradient-enhanced Kriging (GE-Kriging) is a well-established surrogate modelling technique for approximating expensive computational models. It tends to get impractical for high-dimensional problems due to the size of the inherent correlation matrix. A new method, called sliced GE-Kriging (SGE-Kriging), is developed in this paper for reducing the size of the correlation matrix. The results show that the SGE-Kriging model features an accuracy and robustness that is comparable to the standard one but comes at much less training costs.
  arXiv  Detail & Related papers  (2022-04-05T07:27:14Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  We propose a new formulation for the bundle adjustment problem which relies on nullspace marginalization of landmark variables by QR decomposition. Our approach, which we call square root bundle adjustment, is algebraically equivalent to the commonly used Schur complement trick. We show in real-world experiments with the BAL datasets that even in single precision the proposed solver achieves on average equally accurate solutions.
  arXiv  Detail & Related papers  (2021-03-02T16:26:20Z)
• Canny-VO: Visual Odometry with RGB-D Cameras based on Geometric 3D-2D Edge Alignment [85.32080531133799]
  This paper reviews the classical problem of free-form curve registration and applies it to an efficient RGBD visual odometry system called Canny-VO. Two replacements for the distance transformation commonly used in edge registration are proposed: Approximate Nearest Neighbour Fields and Oriented Nearest Neighbour Fields. 3D2D edge alignment benefits from these alternative formulations in terms of both efficiency and accuracy.
  arXiv  Detail & Related papers  (2020-12-15T11:42:17Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.