The Zero Pattern of a Design Matrix Drives Multiple Descent in Over-parameterized Regression

Resumo Técnico: O Padrão de Zeros de uma Matriz de Design Impulsiona a Descida Múltipla em Regressão Sobreparametrizada

Enunciado do Problema
A regressão linear sobreparametrizada tem sido extensamente estudada, mas os quadros teóricos existentes baseiam-se amplamente em duas suposições restritivas: que as covariáveis são independentes e que suas matrizes de covariância são não degeneradas (positivas definidas). Sob essas condições, o risco de predição exibe tipicamente uma curva de "descida dupla" com um único pico no limiar de interpolação ($\gamma = p/n = 1$), impulsionada por um único evento espectral onde a matriz de design perde o posto (rank).

Este artigo aborda a lacuna na compreensão de quando e por que a descida múltipla — o surgimento de múltiplos picos de risco — pode ocorrer unicamente através da estrutura dos dados, sem depender de ajustes arquiteturais, blocos de características distintos ou escalas de kernel distintas. Os autores investigam a regressão de mínimos quadrados com regularização ridge evanescente ($\lambda_n \downarrow 0$) no regime proporcional ($p/n \to \gamma \in (0, \infty)$) sob duas relaxações específicas:

1. Heterogeneidade: As observações são independentes, mas possuem matrizes de covariância distintas e potencialmente de posto deficiente.
2. Dependência: As observações são correlacionadas através de componentes separáveis de posto finito (ex: aumento de dados/data augmentation).

Metodologia
A inovação metodológica central é a redução de designs heterogêneos e dependentes para um modelo de perfil de variância. Ao rotacionar os dados em uma base de autovetores compartilhada (onde as covariâncias são simultaneamente diagonalizáveis), os autores transformam o problema na análise de uma matriz Gaussiana com entradas independentes, mas variâncias desiguais, definida por uma matriz de perfil de variância $S \in \mathbb{R}^{n \times p}$.

1. Redução ao Perfil de Variância:

   • Para o Modelo 1 (Heterogêneo), onde $X_i = \Sigma_i^{1/2} Z_i$, o perfil $S$ é construído a partir dos autovalores das covariâncias individuais $\Sigma_i$.
   • Para o Modelo 2 (Dependente), onde $X = \sum (\tilde{\Sigma}^{(m)})^{1/2} Z^{(m)} (\Sigma^{(m)})^{1/2}$, o perfil $S$ é derivado do produto dos autovalores dos componentes de covariância de amostra e de coordenadas.
   • Crucialmente, o padrão de zeros de $S$ (onde $S_{ij} = 0$) codifica quais observações não conseguem "enxergar" quais direções de coordenadas, representando degenerações estruturais.

2. Equivalentes Determinísticos via Leis Locais:
   Os autores derivam equivalentes determinísticos para o risco de predição (viés e variância) em um regime de ridge evanescente. Isso requer a extensão da lei local da teoria de matrizes aleatórias (especificamente a partir de [4]) para rastrear o parâmetro espectral explicitamente à medida que ele se aproxima de zero ($\lambda_n \downarrow 0$). Isso permite a análise da "aresta dura" (hard edge) do espectro, onde pequenos autovalores se acumulam.

3. Caracterização Combinatória:
   O comportamento do risco está ligado à decomposição de Dulmage–Mendelsohn (DM) do grafo bipartido associado ao suporte de $S$ (o "grafo de variância").

   • Suporte do Viés: Determinado pelo conjunto de colunas ($J_S$) que podem ser deixadas não correspondidas por um emparelhamento máximo no grafo de variância. Estas correspondem às direções onde o estimador retém viés.
   • Picos de Variância: Determinados por uma "condição de alternância" (switching condition) no grafo residual (após a remoção de colunas degeneradas e seus vizinhos). Um pico ocorre quando o grafo residual perde a "propriedade de Hall forte do lado da coluna", forçando os menores autovalores não nulos para a aresta dura.

Principais Contribuições e Resultados

1. Mecanismo para Descida Múltipla:
   O artigo demonstra que um único design de matriz e um único estimador podem produzir múltiplos picos de risco. Esses picos não são artefatos de arquiteturas específicas, mas são intrínsecos à degeneração espectral causada pelo padrão de zeros da estrutura de covariância.

   • Viés: Persiste em coordenadas que são estruturalmente inobserváveis (não correspondidas na decomposição DM).
   • Variância: Diverge em razões de aspecto específicas onde o design residual torna-se "quadrado" (a condição de alternância), causando um pico no risco.

2. Regras Exatas para Localização de Picos:
   Os autores fornecem uma regra combinatória exata para prever o número e a localização dos pros:

   • O suporte do viés é fixado pelo conjunto de colunas degeneradas $J_S$.
   • Os picos de variância ocorrem nos valores de $\gamma$ onde o sub-design residual (após a remoção de $J_S$) transita de possuir folga de Hall forte do lado da coluna para falhar nela.
   • Isso é ilustrado em exemplos como aumento de dados (Modelo 2) e subespaços heterogêneos (Modelo 1), onde múltiplos limiares emergem conforme diferentes blocos do design tornam-se quadrados em relação ao tamanho da amostra.

3. Contraste com Designs Positivos Definidos:
   O artigo distingue entre covariâncias de posto deficiente e positivas definidas.

   • Se as covariâncias forem positivas definidas (mesmo que heterogêneas e não comutativas), o padrão de zeros é vazio. Os autores conjecturam, apoiados por simulações, que tais designs retêm apenas o pico clássico único em $\gamma = 1$.
   • A descida múltipla é impulsionada especificamente pelos zeros (deficiência de posto) na covariância, não meramente pela heterogeneidade ou rotação.

4. Robustez e Universalidade:

   • Os resultados teóricos sustentam-se para designs com entradas independentes e perfis de variância correspondentes, não apenas para os gaussianos (Observação 1). Simulações com entradas Student-$t_3$ (momento terceiro infinito) confirmam que a estrutura de picos persiste.
   • O mecanismo aplica-se a designs degenerados do mundo real, como embeddings de texto de modelos pré-treinados (transformers) aumentados com ruído Gaussiano, que exibem descida múltipla em testes empíricos.

Significância
O artigo afirma que o fenômeno da descida múltipla não se limita a modelos complexos de múltiplos componentes, mas pode surgir da estrutura de padrão de zeros de um único design heterogêneo ou dependente. Ao caracterizar os picos de risco através da decomposição de Dulmage–Mendelsohn do suporte do perfil de variância, os autores fornecem uma regra determinística para prever onde ocorrem os picos de risco. Isso altera a compreensão da regressão sobreparametrizada de uma perspectiva puramente espectral (baseada em razões de aspecto) para uma estrutural (baseada na observabilidade de coordenadas), destacando que a degeneração no design da covariância é o principal motor da descida múltipla.

O trabalho também introduz uma extensão técnica de leis locais para o regime de ridge evanescente, permitindo a análise da aresta dura do espectro na presença de zeros estruturais, uma ferramenta de interesse independente para a teoria de matrizes aleatórias.