Technische Samenvatting: Kolmogorov-Optimale Schalingswetten voor Spline-regressie

Probleemstelling

Hyperparameter-tuning in machine learning is traditioneel een zoekproces, dat vertrouwt op exhaustieve grid searches of cross-validatie (CV) om optimale instellingen te selecteren. Deze aanpak is computationeel duur, oninformatief over de onderliggende statistische mechanica en schaalt slecht met de complexiteit van het model. Specifiek voor spline-regressie wordt de optimale resolutie (het aantal knoopintervallen per coördinaat, aangeduid als $G$) doorgaans via een zoekproces gekozen, ondanks het feit dat de klassieke benaderingstheorie suggereert dat een gesloten vorm oplossing mogelijk is.

De kern van de uitdaging die hier wordt aangepakt, is of de optimale resolutie $G^\star$ voor gestructureerde spline-regressie analytisch kan worden opgelost in plaats van gezocht, waardoor een grid sweep wordt vervangen door een constant aantal model-fits. Dit vereist een modelklasse waarbij de voorspellingsfout een analytisch hanteerbare afhankelijkheid heeft van de hyperparameter, specifiek één waar de bias-variantie trade-off bepaald kan worden vanuit een minimaal aantal fits.

Methodologie: KORE (Kolmogorov-Optimale Order-bewuste Resolutie Estimatie)

Het artikel stelt KORE voor, een zoekvrij algoritme dat een gesloten vorm schalingswet afleidt voor de optimale resolutie. De methodologie rust op drie theoretische pijlers:

1. Kolmogorov-Optimale Benadering: De bias van spline-regressie is gekoppeld aan $G^{-2\beta}$, waarbij $\beta$ de gladheidsexponent (smoothness exponent) is. Dit tempo komt exact overeen met de Kolmogorov $n$-breedte van de gladheidsklasse, wat betekent dat splines benaderings-optimaal zijn onder lineaire methoden van hun omvang.
2. Expliciete Basisdimensie: Het aantal basisfuncties $p(G)$ is een expliciet polynoom in de resolutie $G$, bepaald door de interactieorde van de doelfunctie (bijv. additief versus ijle pairwise interacties) in plaats van de omgeving-inputdimensie.
3. Gesloten Vorm Risico-estimatie: Omdat splines lineaire smoothers zijn, kan de exacte Leave-One-Out (LOO) fout worden berekend via de PRESS-identiteit zonder het model opnieuw te fitten.

De Schalingswet

De verwachte excessieve testfout (MSE minus irreducibele ruis $\sigma^2$) ontbindt in bias en variantie:
$$\text{Err}(G) - \sigma^2 \approx A G^{-2\beta} + \tau \frac{p(G)}{n}$$
Waar:

• $A$ de bias-schaalconstante is.
• $\tau$ de ruis/variantie-schaalconstante is.
• $p(G)$ de basisdimensie is, die schaalt met de effectieve dichtheid $n/s_r$ (waarbij $s_r$ het aantal actieve componenten van de hoogste orde is), niet met de ruwe inputdimensie $d$.

De optimale resolutie $G^\star$ is de minimizer van deze curve. Voor een doel met interactieorde $r$ en gladheid $\beta$ is de schalingswet:
$$G^\star \propto \left( \frac{n}{s_r} \right)^{\frac{1}{2\beta + r}}$$
Cruciaal is dat de inputdimensie $d$ niet in de exponent verschijnt; alleen het aantal actieve componenten $s_r$ doet er toe.

Het KORE Algoritme

In plaats van een grid te doorzoeken, schat KORE de onbekende constanten $A$ en $\tau$ in en lost het $G^\star$ op:

1. Pilot Fits: Fit het spline-model bij twee verschillende pilot-resoluties ($G_a$ en $G_b$).
2. Leverage-gekalibreerde Estimatie: Bereken exacte LOO-fouten met behulp van de PRESS-identiteit. Los een $2 \times 2$ lineair systeem op om de bias-schaal ($\hat{A}$) en de ruis/variantie-schaal ($\hat{\tau}$) te schatten, waarbij gecorrigeerd wordt voor de leverage-inflatie in de PRESS-identiteit.
3. Gesloten Vorm Oplossing: Gebruik $\hat{A}$ en $\hat{\tau}$ in de afgeleide van de risicocurve om de continue optimale resolutie $\hat{G}^\dagger$ te berekenen.
4. Certificering: Rond $\hat{G}^\dagger$ af naar de dichtstbijzijnde integer en verifieer dit tegen een kleine symmetrische buurt (bijv. $\pm 3$) met behulp van LOO-scores. Dit fungeert als een certificaat tegen eindige-steekproef discretisatiefouten, en niet als een volledige grid search.

Belangrijkste Bijdragen

1. Intrinsic-Order Test-Error Wet: Het artikel stelt vast dat de optimale resolutie schaalt met het aantal actieve hoogste-orde interacties ($s_r$), en niet exponentieel met de inputdimensie. De bias-term wordt geïdentificeerd als de Kolmogorov $n$-breedte, wat garandeert dat de spline-familie benaderingstheoretisch optimaal is.
2. Zoekvrij Algoritme (KORE): Een praktisch algoritme dat de exhaustieve grid search vervangt door twee pilot fits en een gesloten vorm plug-in oplossing, gecertificeerd door een zeer kleine LOO-buurt.
3. Consistentie-stelling: Het artikel bewijst dat de geschatte constanten en de plug-in resolutie convergeren naar hun populatie-tegenhangers naarmate de steekproefomvang $n \to \infty$. De integer-selector komt met een waarschijnlijkheid die naar één nadert overeen met de exhaustieve risicominimizer zodra de oracle-marge de plug-in fout overstijgt.
4. Empirische Validatie: Uitgebreide experimenten tonen aan dat KORE de nauwkeurigheid van exhaustieve 3-voudige CV en klassieke criteria (GCV, AIC, BIC) evenaart (terwijl het ongeveer 8$\times$ minder modellen fit).

Resultaten

Synthetische Experimenten

• Effectieve Dichtheid Collaps: Over dimensies $d \in \{10, 20, 40, 80\}$ klappen de testfout en de optimale resolutie samen op één curve wanneer ze worden uitgezet tegen de effectieve dichtheid $\rho = n/s_r$, wat de theoretische schalingswet bevestigt.
• Consistentie: Naarmate $n$ toeneemt, convergeren de geschatte bias- en ruisschalen naar 1 (relatief ten opzien van de populatiewaarden), en convergeert de geselecteerde resolutie naar het populatieoptimum.
• Accuracy-Compute Frontier: Op gecontroleerde additieve en ijle pairwise taken bereikt KORE test RMSE-ratio's $\le 1.0$ vergeleken met exhaustieve CV (vaak zelfs beter door continue optimalisatie versus discrete grids), terwijl het het aantal model-fits vermindert van ~91 (voor CV) naar ~9–14.

Real-World Benchmarks

• Tabulaire Data: Op 36 real-world tabulaire datasets (OpenML-CTR23 + Combined Cycle) werd KORE vergeleken met 21 baselines, inclusief getunede gradient boosters (XGBoost, LightGBM), kernel machines en andere spline-selectors.
• Compute-Normalized Lift (CNL): Gebruikmakend van een metriek die nauwkeurigheid beloont per eenheid rekentijd, rangschikte KORE eerste onder alle 21 methoden. Het presteerde beter dan getunede gradient boosters en kernel machines, die orders van grootte meer rekenkracht nodig hadden om een vergelijkbare (maar niet superieure) ruwe nauwkeurigheid te bereiken.
• Robuustheid: KORE evenaarde of versloeg exhaustieve CV op gladde, laag-orde targets. Het faalde alleen op targets met hoge-orde interacties, diepe categorische splits of extreme ruimtelijke heterogeniteit (zoals de "Oscillator" of "Franke" benchmarks), waar de aanname van een enkele globale resolutie structureel wordt geschonden.

Betekenis en Claims

Het artikel claimt een fundamentele verschuiving in hoe hyperparameters worden behandeld voor specifieke modelklassen:

• Van Zoeken naar Berekenen: Voor spline-regressie is de optimale resolutie geen opaak wiel dat via trial-and-error getuned moet worden, maar een statistisch estimand dat direct berekend kan worden uit de datadistributie en de modelfamilie.
• Kolmogorov-Optimaliteit: De methode is "Kolmogorov-optimaal" omdat deze opereert binnen de familie van subspaces die de beste mogelijke lineaire benaderingssnelheid (de Kolmogorov $n$-breedte) realiseren, en simpelweg het punt op die curve afstemt waar de bias-variantie balans optimaal is.
• Schaalbaarheid: Door de inputdimensie te vervangen door de interactieorde in de schalingswet, vermijdt de methode de vloek van de dimensionaliteit voor gestructureerde problemen (additief of ijle pairwise), waardoor het kan schalen naar hoge dimensies ($d=80$) zonder de exponentiële kosten van tensor-product grids.
• Praktische Efficiëntie: Het algoritme biedt een "gratis lunch" in termen van rekenkracht: het levert de nauwkeurigheid van een volledige grid search (en vaak zelfs beter, door continue optimalisatie) tegen een fractie van de computationele kosten, wat het een superieure keuze maakt voor gladde, laag-orde regressietaken in tabulaire data-analyse.

Het artikel concludeert dat hoewel zoeken noodzakelijk blijft voor complexe, niet-convexe of hoog-interactieve modellen (zoals diepe neurale netwerken of boom-ensembles), spline-regressie een volwassen klasse is waar "oplossen" tractabel is en superieur is aan "zoeken".