Riepilogo Tecnico: Leggi di Scaling Kolmogorov-Ottimali per la Regressione Spline

Definizione del Problema

La sintonizzazione degli iperparametri nel machine learning è tradizionalmente un processo basato sulla ricerca, che si affida a una ricerca esaustiva su griglia (grid search) o alla validazione incrociata (CV) per selezionare le impostazioni ottimali. Questo approccio è computazionalmente costoso, poco informativo riguardo alla sottostante meccanica statistica e scala male con la complessità del modello. Specificamente per la regressione spline, la risoluzione ottimale (il numero di intervalli di nodi per coordinata, denotato con $G$) viene tipicamente selezionata tramite ricerca, nonostante l'esistenza della classica teoria dell'approssimazione suggerisca che una soluzione in forma chiusa sia possibile.

La sfida centrale affrontata è se la risoluzione ottimale $G^\star$ per la regressione spline strutturata possa essere risolta analiticamente invece di essere cercata, sostituendo una scansione di griglia con un numero costante di adattamenti del modello. Ciò richiede una classe di modelli in cui l'errore di predizione abbia una dipendenza analiticamente trattabile dall'iperparametro, specificamente in un caso in cui il compromesso bias-varianza possa essere determinato da un numero minimo di adattamenti.

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

Il paper propone KORE, un algoritmo privo di ricerca che deriva una legge di scaling in forma chiusa per la risoluzione ottimale. La metodologia si basa su tre pilastri teorici:

1. Approssimazione Kolmogorov-Ottimale: Il bias della regressione spline è vincolato a $G^{-2\beta}$, dove $\beta$ è l'esponente di regolarità (smoothness). Questo tasso corrisponde esattamente alla $n$-larghezza di Kolmogorov della classe di regolarità, il che significa che le spline sono di approssimazione-ottimali tra i metodi lineari della loro dimensione.
2. Dimensione Esplicita della Base: Il numero di funzioni di base $p(G)$ è un polinomio esplicito nella risoluzione $G$, determinato dall'ordine di interazione della funzione target (ad esempio, additiva vs. pairwise sparsa) piuttosto che dalla dimensione dello spazio di input.
3. Stima del Rischio in Forma Chiusa: Poiché le spline sono smoothers lineari, l'errore esatto Leave-One-Out (LOO) può essere calcolato tramite l'identità PRESS senza dover riadattare il modello.

La Legge di Scaling

L'errore eccessivo atteso del test (MSE meno il rumore irriducibile $\sigma^2$) si decompone in bias e varianza:
$$\text{Err}(G) - \sigma^2 \approx A G^{-2\beta} + \tau \frac{p(G)}{n}$$
Dove:

• $A$ è la costante di scala del bias.
• $\tau$ è la costante di scala del rumore/varianza.
• $p(G)$ è la dimensione della base, che scala con la densità effettiva $n/s_r$ (dove $s_r$ è il conteggio dei componenti di interazione di ordine massimo attivi), non con la dimensione grezza dell'input $d$.

La risoluzione ottimale $G^\star$ è il minimizzatore di questa curva. Per un target con ordine di interazione $r$ e regolarità $\beta$, la legge di scaling è:
$$G^\star \propto \left( \frac{n}{s_r} \right)^{\frac{1}{2\beta + r}}$$
Fondamentalmente, la dimensione dell'input $d$ non compare nell'esponente; conta solo il numero di componenti attive $s_r$.

L'Algoritmo KORE

Invece di cercare su una griglia, KORE stima le costanti ignote $A$ e $\tau$ e risolve per $G^\star$:

1. Pilot Fits: Adatta il modello spline a due diverse risoluzioni pilota ($G_a$ e $G_b$).
2. Stima Calibrata sulla Leverage: Calcola gli errori LOO esatti utilizzando l'identità PRESS. Risolve un sistema lineare $2 \times 2$ per stimare la scala del bias ($\hat{A}$) e la scala del rumore/varianza ($\hat{\tau}$), correggendo per l'inflazione della leverage nella identità PRESS.
3. Soluzione in Forma Chiusa: Inserisce $\hat{A}$ e $\hat{\tau}$ nella derivata della curva di rischio per risolvere la risoluzione ottimale continua $\hat{G}^\dagger$.
4. Certificazione: Arrotonda $\hat{G}^\dagger$ all'intero più vicino e lo verifica rispetto a un piccolo vicinato simmetrico (ad esempio, $\pm 3$) utilizzando i punteggi LOO. Questo funge da certificato contro l'errore di discretizzazione del campione finito, non da una ricerca completa su griglia.

Contributi Chiave

1. Legge dell'Errore di Test con Ordine Intrinseco: Il paper stabilisce che la risoluzione ottimale scala con il conteggio delle interazioni di ordine massimo attive ($s_r$), non esponenzialmente con la dimensione dell'input. Il termine di bias è identificato come la $n$-larghezza di Kolmogorov, garantendo che la famiglia delle spline sia teoricamente ottimale per l'approssimazione.
2. Algoritmo Senza Ricerca (KORE): Un algoritmo pratico che sostituisce la ricerca esaustiva su griglia con due adattamenti pilota e una soluzione plug-in in forma chiusa, certificata da un minuscolo vicinato LOO.
3. Teorema di Consistenza: Il paper dimostra che le costanti stimate e la risoluzione plug-in convergono ai rispettivi valori di popolazione all'aumentare della dimensione del campione $n \to \infty$. Il selettore intero coincide con il minimizzatore del rischio esaustivo con probabilità che tende a uno una volta che il margine oracle supera l'errore plug-in.
4. Validazione Empirica: Esperimenti estesi dimostrano che KORE eguaglia l'accuratezza della CV esaustiva a 3-fold e dei classici criteri (GCV, AIC, BIC), pur effettuando circa 8 volte meno adattamenti di modelli.

Risultati

Esperimenti Sintetici

• Collasso della Densità Effettiva: Attraverso dimensioni $d \in \{10, 20, 40, 80\}$, l'errore di test e la risoluzione ottimale collassano su un'unica curva quando tracciati rispetto alla densità effettiva $\rho = n/s_r$, confermando la legge di scaling teorica.
• Consistenza: All'aumentare di $n$, le scale stimate del bias e del rumore convergono a 1 (rispetto ai valori di popolazione) e la risoluzione selezionata converge all'ottimo di popolazione.
• Frontiera Accuratezza-Calcolo: Su compiti controllati additivi e di sparse pairwise, KORE raggiunge rapporti RMSE di test $\le 1.0$ rispetto alla CV esaustiva (spesso leggermente migliore grazie all'ottimizzazione continua rispetto alla griglia discreta) riducendo gli adattamenti del modello da ~91 (per la CV) a ~9–14.

Benchmark del Mondo Reale

• Dati Tabulari: Su 36 dataset tabulari reali (OpenML-CTR23 + Combined Cycle), KORE è stato confrontato con 21 baseline, inclusi gradient booster sintonizzati (XGBoost, LightGBM), kernel machines e altri selettori di spline.
• Compute-Normalized Lift (CNL): Utilizzando una metrica che premia l'accuratezza per unità di tempo di calcolo, KORE si è classificato primo tra tutti i 21 metodi. Ha superato i gradient booster sintonizzati e le kernel machines, che richiedevano ordini di grandezza di calcolo in più per raggiungere un'accuratezza comparabile (ma non superiore).
• Robustezza: KORE ha eguagliato o battuto la CV esaustiva su target smooth e a basso ordine. È fallito solo su target con alte interazioni, split categorici profondi o estrema eterogeneità spaziale (ad esempio, i benchmark "Oscillator" o "Franke"), dove l'assunzione di una singola risoluzione globale è strutturalmente violata.

Significato e Rivendicazioni

Il paper rivendica un cambiamento fondamentale nel modo in cui gli iperparametri vengono trattati per specifiche classi di modelli:

• Dalla Ricerca al Calcolo: Per la regressione spline, la risoluzione ottimale non è un pomello opaco da sintonizzare per tentativi ed errori, ma un estimando statistico che può essere calcolato direttamente dalla distribuzione dei dati e dalla famiglia del modello.
• Ottimalità di Kolmogorov: Il metodo è "Kolmogorov-ottimale" perché opera all'interno della famiglia di sottospazi che realizzano il miglior tasso di approssimazione lineare possibile ($n$-larghezza di Kolmogorov) e semplicemente sintonizza il punto su tale curva dove il bilanciamento bias-varianza è ottimale.
• Scalabilità: Sostituendo la dimensione dell'input con l'ordine di interazione nella legge di scaling, il metodo evita la maledizione della dimensionalità per problemi strutturati (additivi o sparse pairwise), permettendo di scalare ad alte dimensioni ($d=80$) senza il costo esponenziale delle griglie prodotto-tensore.
• Efficienza Pratica: L'algoritmo offre un "pasto gratis" in termini di calcolo: fornisce l'accuratezza di una ricerca completa su griglia (e spesso migliore, grazie all'ottimizzazione continua) a una frazione del costo computazionale, rendendolo una scelta superiore per compiti di regressione smooth e a basso ordine nell'analisi di dati tabulari.

Il paper conclude che, sebbene la ricerca rimanga necessaria per modelli complessi, non convessi o ad alta interazione (come reti neurali profonde o ensemble di alberi), la regressione spline è una classe matura dove il "risolvere" è trattabile e superiore al "cercare".