Resumo Técnico: Leis de Escalonamento de Optimalidade de Kolmogorov para Regressão por Splines

Declaração do Problema

O ajuste de hiperparâmetros em aprendizado de máquina é tradicionalmente um processo de busca, baseando-se em buscas exaustivas em grade ou validação cruzada (CV) para selecionar configurações ideais. Esta abordagem é computacionalmente dispendiosa, pouco informativa em relação à mecânica estatística subjacente e escala mal com a complexidade do modelo. Especificamente para a regressão por splines, a resolução ótima (o número de intervalos de nós por coordenada, denotado por $G$) é tipicamente selecionada via busca, apesar da existência da teoria clássica da aproximação que sugere que uma solução em forma fechada pode ser possível.

O desafio central abordado é se a resolução ótima $G^\star$ para regressão por splines estruturada pode ser resolvida analiticamente em vez de buscada, substituindo uma varredura de grade por um número constante de ajustes de modelos. Isso requer uma classe de modelos onde o erro de predição tenha uma dependência analiticamente tratável em relação ao hiperparâmetro, especificamente um caso onde o compromisso entre viés e variância possa ser determinado a partir de um número mínimo de ajustes.

Metodologia: KORE (Estimativa de Resolução de Ordem Otimizada por Kolmogorov)

O artigo propõe o KORE, um algoritmo livre de busca que deriva uma lei de escalonamento em forma fechada para a resolução ótima. A metodologia baseia-se em três pilares teóricos:

1. Aproximação de Optimalidade de Kolmogorov: O viés da regressão por splines é vinculado a $G^{-2\beta}$, onde $\beta$ é o expoente de suavidade. Esta taxa corresponde exatamente à $n$-largura de Kolmogorov da classe de suavidade, o que significa que os splines são de aproximação ótima entre métodos lineares de seu tamanho.
2. Dimensão de Base Explícita: O número de funções de base $p(G)$ é um polinômio explícito na resolução $G$, determinado pela ordem de interação da função alvo (por exemplo, aditiva vs. par de interações esparsas) em vez da dimensão de entrada ambiente.
3. Estimativa de Risco em Forma Fechada: Como os splines são suavizadores lineares, o erro exato de Leave-One-Out (LOO) pode ser computado via da identidade PRESS sem reajustar o modelo.

A Lei de Escalonamento

O erro excessivo de teste esperado (MSE menos o ruído irredutível $\sigma^2$) decompõe-se em viés e variância:
$$\text{Err}(G) - \sigma^2 \approx A G^{-2\beta} + \tau \frac{p(G)}{n}$$
Onde:

• $A$ é a constante de escala do viés.
• $\tau$ é a constante de escala de ruído/variância.
• $p(G)$ é a dimensão da base, escalonando com a densidade efetiva $n/s_r$ (onde $s_r$ é a contagem de componentes de interação de ordem superior ativas), não com a dimensão bruta de entrada $d$.

A resolução ótima $G^\star$ é o minimizador desta curva. Para um alvo com ordem de interação $r$ e suavidade $\beta$, a lei de escalonamento é:
$$G^\star \propto \left( \frac{n}{s_r} \right)^{\frac{1}{2\beta + r}}$$
Crucialmente, a dimensão de entrada $d$ não aparece no expoente; apenas a contagem de componentes ativos $s_r$ importa.

O Algoritmo KORE

Em vez de buscar uma grade, o KORE estima as constantes desconhecidas $A$ e $\tau$ e resolve para $G^\star$:

1. Ajustes Piloto: Ajusta o modelo de spline em duas resoluções piloto distintas ($G_a$ e $G_b$).
2. Estimativa Calibrada por Alavancagem: Computa erros LOO exatos usando a identidade PRESS. Resolve um sistema linear $2 \times 2$ para estimar a escala de viés ($\hat{A}$) e a escala de ruído/variância ($\hat{\tau}$), corrigindo para a inflação de alavancagem na identidade PRESS.
3. Solução em Forma Fechada: Insere $\hat{A}$ e $\hat{\tau}$ na derivada da curva de risco para resolver para a resolução ótima contínua $\hat{G}^\dagger$.
4. Certificação: Arredonda $\hat{G}^\dagger$ para o inteiro mais próximo e verifica contra uma pequena vizinhança simétrica (ex: $\pm 3$) usando pontuações LOO. Isso atua como um certificado contra o erro de discretização de amostra finita, não como uma busca de grade completa.

Principais Contribuições

1. Lei de Erro de Teste de Ordem Intrínseca: O artigo estabelece que a resolução ótima escala com a contagem de interações de ordem superior ativas ($s_r$), não exponencialmente com a dimensão de entrada. O termo de viés é identificado como a $n$-largura de Kolmogorov, garantindo que a família de splines é aproximativamente ótima.
2. Algoritmo Livre de Busca (KORE): Um algoritmo prático que substitui a busca exaustiva em grade por dois ajustes piloto e uma solução de inserção em forma fechada, certificada por uma vizinhança minúscula de LOO.
3. Teorema de Consistência: O artigo prova que as constantes estimadas e a resolução de inserção convergem para seus contrapartes populacionais conforme o tamanho da amostra $n \to \infty$. O seletor de inteiros coincide com o minimizador de risco exaustivo com probabilidade tendendo a um assim que a margem do oráculo excede o erro de inserção.
4. Validação Empírica: Experimentos extensos demonstram que o KORE iguala a precisão da CV exaustiva de 3 dobras e dos critérios clássicos (GCV, AIC, BIC) enquanto realiza aproximadamente 8$\times$ menos ajustes de modelos.

Resultados

Experimentos Sintéticos

• Colapso da Densidade Efetiva: Através das dimensões $d \in \{10, 20, 40, 80\}$, o erro de teste e a resolução ótima colapsam em uma única curva quando plotados contra a densidade efetiva $\rho = n/s_r$, confirmando a lei de escalonamento teórica.
• Consistência: À medida que $n$ aumenta, as escalas de viés e ruído estimadas convergem para 1 (em relação aos valores populacionais) e a resolução selecionada converge para o ótimo populacional.
• Fronteira de Precisão-Computação: Em tarefas controladas de aditividade e pares esparsos, o KORE atinge razões de RMSE de teste $\le 1.0$ em comparação com a CV exaustiva (frequentemente melhor devido à otimização contínua vs. grade discreta) enquanto reduz os ajustes de modelos de ~91 (para CV) para ~9–14.

Benchmarks do Mundo Real

• Dados Tabulares: Em 36 conjuntos de dados tabulares do mundo real (OpenML-CTR23 + Combined Cycle), o KORE foi comparado com 21 baselines, incluindo boosters de gradiente ajustados (XGBoost, LightGBM), máquinas de kernel e outros seletores de spline.
• Levantamento de Ganho Normalizado por Computação (CNL): Usando uma métrica que recompensa a precisão por unidade de tempo de computação, o KORE classificou-se em primeiro lugar entre todos os 21 métodos. Superou boosters de gradiente ajustados e máquinas de kernel, que exigiram ordens de magnitude mais de computação para alcançar uma precisão bruta comparável (mas não superior).
• Robustez: O KORE igualou ou superou a CV exaustiva em alvos suaves e de baixa ordem. Falhou apenas em alvos com altas interações de ordem, divisões categóricas profundas ou heterogeneidade espacial extrema (ex: os benchmarks "Oscillator" ou "Franke"), onde a suposição de resolução global única é estruturalmente violada.

Significância e Alegações

O artigo alega uma mudança fundamental na forma como os hiperparâmetros são tratados para classes de modelos específicas:

• De Busca para Cálculo: Para a regressão por splines, a resolução ótima não é um botão opaco a ser ajustado por tentativa e erro, mas um estimando estatístico que pode ser computado diretamente da distribuição dos dados e da família do modelo.
• Optimalidade de Kolmogorov: O método é "otimizado por Kolmogorov" porque opera dentro da família de subespaços que realizam a melhor taxa de aproximação linear possível (a $n$-largura de Kolmogorov) e simplesmente ajusta o ponto nessa curva onde o equilíbrio viés-variância é ideal.
• Escalabilidade: Ao substituir a dimensão de entrada pela ordem de interação na lei de escalonamento, o método evita a maldição da dimensionalidade para problemas estruturados (aditivos ou pares esparsos), permitindo que escale para altas dimensões ($d=80$) sem o custo exponencial de grades de produto tensorial.
• Eficiência Prática: O algoritmo oferece um "almoço grátis" em termos de computação: ele entrega a precisão de uma busca completa em grade (e muitas vezes melhor, devido à otimização contínua) a uma fração do custo computacional, tornando-o uma escolha superior para tarefas de regressão de baixa ordem e suaves em análise de dados tabulares.

O artigo conclui que, embora a busca continue necessária para modelos complexos, não convexos ou de alta interação (como redes neurais profundas ou conjuntos de árvores), a regressão por splines é uma classe madura onde "resolver" é tratável e superior a "buscar".