How abundant are good interpolators?

Resumo Técnico: "Quão abundantes são os bons interpoladores?"

Problema
O artigo investiga as propriedades de generalização do conjunto de classificadores lineares interpoladores em regimes sobreparametrizados. Especificamente, considera um conjunto de dados rotulados $(X_i, y_i)_{i=1}^n$ em $\mathbb{R}^d$ onde $n/d \to \alpha$ com $\alpha$ pequeno (alta sobreparametrização). Os autores definem o conjunto $S$ de classificadores lineares de norma unitária $\theta$ que classificam corretamente todos os pontos de treinamento com uma margem fixa $\kappa$. A questão central é: Qual é o desempenho de generalização típico de um classificador escolhido uniformemente ao acaso de $S$?

Esta investigação aborda o fenômeno do "overfitting benigno", onde modelos com erro de treinamento zero generalizam bem. Embora a regularização implícita (ex: via gradiente descendente) seja conhecida por selecionar interpoladores específicos com bom desempenho, o artigo questiona se a maioria dos interpoladores compartilha essa propriedade ou se "bons" interpoladores são exceções raras dentro do espaço de soluções.

Metodologia
Os autores empregam ferramentas da física estatística, especificamente a teoria de grandes desvios e o método da réplica (adaptado para provas probabilísticas rigorosas), para analisar a geometria do espaço de soluções $S$.

1. Modelos de Dados: A análise é conduzida sob duas distribuições distintas de geração de dados com uma razão sinal-ruído (SNR) constante $\lambda$:
   • Um Modelo de Mistura Gaussiana (GMM).
   • Um modelo Logístico com características Gaussianas.
2. Princípio de Grandes Desvios (LDP): A abordagem técnica central envolve estabelecer um princípio de grandes desvios "quenched" para o overlap $\langle \theta, \theta^* \rangle / d$ entre um interpolador aleatório $\theta$ e a verdadeira direção do sinal $\theta^*$. O objetivo é caracterizar a taxa exponencial do volume do conjunto de interpoladores com um determinado overlap $x$.
3. Formulação Variacional: Os autores derivam uma função de taxa $\Phi(x, q)$ definida sobre o overlap $x$ e um parâmetro $q$ (representando o overlap entre dois interpoladores aleatórios independentes). O volume do espaço de solução é caracterizado por um problema de ponto de sela envolvendo $\sup_x \inf_q \Phi(x, q)$.
4. Técnicas de Prova:
   • Medida de Referência Gaussiana: As provas relaxam a restrição esférica para uma medida Gaussiana completa para utilizar a concentração de medida e técnicas de interpolação Gaussiana (seguindo a abordagem de Talagrand para o perceptron esférico).
   • Método da Cavidade: Os autores utilizam um argumento de "cavidade" para adicionar restrições (pontos de dados) um a um, relacionando a energia livre de $n$ pontos com a de $n-1$ pontos.
   • Restrições Rígidas (Hard Constraints): Um passo crítico envolve converter as funções de suavização (mollification) usadas na análise Gaussiana de volta para as restrições de função degrau rígidas que definem os interpoladores ($y_i \langle X_i, \theta \rangle \ge \kappa$). Isso requer lidar com componentes de sinal não Gaussianos e estabelecer limites de concentração para medidas de Gibbs com restrições rígidas.
   • Comparação Bayesiana: O artigo também analisa a distribuição posterior (estimador Bayes-ótimo) para derivar uma linha de base para o desempenho ótimo, observando que a posterior satisfaz uma relação específica (linha de Nishimori) entre overlaps que a medida uniforme sobre os interpoladores não satisfaz.

Contribuições Principais e Resultados

1. Concentração do Desempenho Típico: O artigo estabelece que, com alta probabilidade sobre os dados, o erro de generalização de um interpolador uniformemente aleatório concentra-se exponencialmente em torno de um valor "típico" único $x^*$. Isso confirma uma conjectura de Theisen, Klusowski e Mahoney [TKM21] sobre a existência de um erro típico, embora o artigo refine as condições sob as quais isso ocorre.
2. Raridade de Bons Interpoladores: A principal descoberta é que, no regime sobreparametrizado com SNR constante, o desempenho típico $x^*$ é significamente pior do que o desempenho alcançado por algoritmos eficientes.
   • Os autores comparam $x^*$ com o desempenho de um estimador de Programação Linear (LP) e do Gradiente Descendente (GD) na perda logística.
   • Simulações numéricas e limites teóricos mostram que $x^* < x_{LP}$ e $x^* < x_{GD}$ para uma ampla gama de parâmetros.
   • Consequentemente, "bons" interpoladores (aqueles que performam tão bem quanto LP ou GD) constituem uma fração exponencialmente pequena do conjunto total de interpoladores.
3. Dependência da SNR: O artigo esclarece que a abundância de bons interpoladores é altamente dependente da SNR. Enquanto análises heurísticas anteriores sugeriam que bons classificadores são abundantes, essas análises assumiam implicitamente uma alta SNR (onde a separação de classes cresce com a dimensão). No regime de SNR constante analisado aqui, bons interpoladores são extremamente raros, tornando o sucesso da regularização implícita um fenômeno não trivial.
4. Caracterização Bayes-Ótima: Os autores fornecem uma caracterização assintótica do desempenho Bayes-ótimo ($x_{Bayes}$) sob ambos os modelos de dados, mostrando que algoritmos eficientes (LP e GD) superam significativamente o interpolador típico e aproximam-se mais do limite Bayes-ótimo do que um sorteio aleatório do conjunto de soluções.

Significância e Alegações
O artigo afirma resolver a questão da "abundância de bons interpoladores" no regime de SNR constante e sobreparametrizado. Sua significância reside em demonstrar que:

• A Regularização Implícita é Essencial: O fato de algoritmos eficientes (GD, LP) superarem vastamente um interpolador aleatório sugere que o sucesso de generalização de modelos sobreparametrizados não é uma propriedade inerente do conjunto de soluções $S$, mas sim uma consequência do caminho específico tomado pelos algoritmos de otimização (regularização implícita).
• Refutação da Abundância Heurística: Os resultados contradizem as heurísticas que sugerem que "bons classificadores são abundantes" no regime de interpolação, mostrando que tal abundância só ocorre nos limites de alta SNR.
• LDP Rigoroso para Interpoladores: O trabalho fornece um princípio de grandes desvios (LDP) rigoroso para o erro de generalização de interpoladores uniformes, um resultado que anteriormente era heurístico ou limitado a pressupostos específicos de alta SNR.

Os autores afirmam explicitamente que suas descobertas destacam a natureza não trivial do overfitting benigno neste cenário, onde a vasta maioria das soluções para o problema de interpolação são de baixo desempenho, e apenas um subconjunto minúsculo, selecionado algoritmicamente, performa bem.