Two-Point Deterministic Equivalence for Stochastic Gradient Dynamics in Linear Models

Resumo Técnico: Equivalência determinística de dois pontos para dinâmicas de gradiente estocástico em modelos lineares

Enunciado do Problema
A aprendizagem profunda moderna exibe leis de escalonamento previsíveis, onde o desempenho melhora com aumentos nos dados, no tamanho do modelo e na capacidade de computação. Embora trabalhos recentes tenham analisado o comportamento de escalonamento de métodos de kernel e modelos de características aleatórias treinados com Descida de Gradiente Estocástico (SGD), os quadros teóricos existentes frequentemente tratam efeitos específicos — como tamanho finito do conjunto de dados, largura finita do modelo e ruído do SGD — de forma isolada ou dependem de abordagens complexas de teoria de campo médio dinâmica (DMFT). Um quadro analítico unificado capaz de capturar a inter-relação entre dados limitados, características limitadas e ruído do SGD em modelos lineares de alta dimensão, particularmente para dinâmicas dependentes do tempo e cenários fora da distribuição (OOD), permanece um desafio. Especificamente, técnicas padrão de matrizes aleatórias frequentemente dependem de "resolventes de um ponto", que são insuficientes quando as matrizes que governam as dinâmicas (por exemplo, covariância empírica, covariância populacional e matrizes de características) não comutam.

Metodologia
Os autores desenvolvem um quadro analítico novel baseado em equivalências determinísticas de dois pontos para resolventes de matrizes aleatórias. O núcleo da metodologia envolve:

1. Configuração do Modelo: O artigo considera regressão linear e modelos de características aleatórias lineares ($f(x) = x^\top F v$) treinados via SGD com tamanho de lote $B$ em um conjunto de dados de tamanho $P$. A análise opera no limite de alta dimensão onde a dimensão de entrada $D$, a largura de características $N$ e o tamanho do conjunto de dados $P$ crescem conjuntamente até o infinito com razões fixas.
2. Dinâmicas Reduzidas: Seguindo trabalhos anteriores, os autores derivam um modelo reduzido para a evolução dos erros de treinamento e generalização. Isso envolve rastrear a covariância da discrepância dos pesos ($\Delta w_t \Delta w_t^\top$) e expressar as dinâmicas de risco como uma equação integral de Volterra. Esta equação consiste em um "termo de forçamento" (componente de fluxo de gradiente) e um "termo de kernel" (componente de ruído do SGD).
3. Análise no Espaço de Fourier: Os autores transformam as dinâmicas no domínio do tempo para o espaço de Fourier. Isso revela que os termos de forçamento envolvem produtos de dois resolventes avaliados em argumentos diferentes (frequências), ou seja, $(\lambda + AB)^{-1} M (\lambda' + BA)^{-1}$.
4. Equivalência Determinística de Dois Pontos: A inovação técnica primária é a derivação de um equivalente determinístico para esses produtos de resolventes de dois pontos. Usando a teoria da probabilidade livre, especificamente as propriedades da Transformada-S e uma expansão diagramática planar, os autores avaliam o comportamento assintótico desses produtos. Eles distinguem entre contribuições "desconectadas" (fatorando em equivalentes de um ponto) e contribuições "conectadas" envolvendo cumulantes mistos, levando a uma equação autoconsistente para a função de dois pontos.
5. Aplicação ao Risco: Essas equivalências são aplicadas para derivar expressões assintóticas precisas tanto para os riscos de treinamento quanto de teste (generalização), incluindo cenários com deslocamento de covariável (onde os dados de teste seguem uma distribuição diferente da de treinamento).

Principais Contribuições

• Nova Equivalência Determinística: O artigo deriva uma nova classe de "equivalências determinísticas de dois pontos" para resolventes de matrizes aleatórias avaliados em pares arbitrários de argumentos. Isso estende resultados anteriores de "um ponto" para lidar com matrizes não comutativas, o que é essencial para dinâmicas de tempo finito e tamanhos de conjuntos de dados finitos.
• Derivação Unificada: O quadro fornece uma derivação unificada do desempenho para regressão linear de alta dimensão, regressão de kernel e modelos de características aleatórias lineares. Ele recupera assíntotas previamente conhecidas (por exemplo, de abordagens DMFT em [16] e técnicas de equivalência de um ponto em [17]) enquanto fornece resultados novel para dinâmicas dependentes do tempo.
• Caracterização do Ruído do SGD: Os autores modelam explicitamente a interação entre dados limitados, características limitadas e ruído do SGD. Eles derivam assíntotas precisas para o "termo de kernel do SGD", mostrando como o ruído contribui para as dinâmicas de risco ao longo do tempo.
• Análise de Deslocamento de Covariável: A metodologia é estendida para cenários fora da distribuição, fornecendo fórmulas assintóticas exatas para o erro de generalização quando as covariáveis de teste seguem uma distribuição Gaussiana diferente da do conjunto de treinamento.
• Conexão com DMFT: O artigo estabelece um link direto entre as quantidades de matrizes aleatórias derivadas e a Teoria de Campo Médio Dinâmica. Ele interpreta a Transformada-S da probabilidade livre como uma função de resposta e identifica as equivalências determinísticas de dois pontos com as funções de correlação usadas na DMFT.

Resultados
Os autores obtêm fórmulas assintóticas explícitas e precisas para:

• Perda de Treinamento e Teste: Expressões para a evolução temporal do erro de treinamento e generalização em modelos de características aleatórias lineares, decompostas em contribuições de fluxo de gradiente (forçamento) e ruído do SGD (kernel).
• Termos de Fluxo de Gradiente: Novas equivalências de dois pontos para os termos de forçamento, que capturam a natureza não comutativa das covariâncias empírica e populacional em tempo finito.
• Termos de Kernel do SGD: Expressões assintóticas para os kernels que governam o acúmulo de ruído do SGD, incluindo correções para tamanhos de lote finitos e dimensões de características.
• Limites Estáticos: Os resultados recuperam os limites estáticos conhecidos (tempo infinito), como o desempenho de regressão sem regularização (ridgeless), validando a abordagem dinâmica.
• Desempenho OOD: Assíntotas de forma fechada para o erro de generalização sob deslocamento de covariável, recuperando e estendendo resultados estáticos anteriores para o cenário dinâmico.

Significado
O artigo reivindica significado ao fornecer uma ferramenta analítica unificada e rigorosa para entender as leis de escalonamento e as dinâmicas de aprendizagem de modelos lineares de alta dimensão. Ao introduzir equivalências determinísticas de dois pontos, os autores fecham a lacuna entre a teoria de matrizes aleatórias estática e a natureza dinâmica e não comutativa do treinamento por SGD. Isso permite a caracterização precisa de como dados finitos, largura finita do modelo e ruído estocástico interagem para determinar o desempenho. O trabalho sugere que a Transformada-S e os métodos diagramáticos planares oferecem uma alternativa poderosa à DMFT para derivar esses resultados, potencialmente simplificando a análise de dinâmicas de aprendizagem complexas enquanto mantêm o rigor matemático no limite de alta dimensão. Os autores observam que, embora não provem limites quantitativos de erro para dimensões finitas, espera-se que as fórmulas assintóticas forneçam boas aproximações com base em resultados conhecidos em cenários estáticos e evidências numéricas da literatura anterior.