Implicit Bias of Per-sample Adam on Separable Data: Departure from the Full-batch Regime

Este trabalho demonstra que o viés implícito do Adam com amostras individuais (incremental) em dados linearmente separáveis pode divergir do regime de lote completo, convergindo para classificadores de margem máxima em normas diferentes (como $\ell_2$ em vez de $\ell_\infty$) dependendo do conjunto de dados, ao contrário do Signum, que mantém invariância no viés para qualquer tamanho de lote.

O essencial

Imagine que você está tentando ensinar um robô a separar duas turmas de alunos (os "dados") em uma sala de aula. O robô usa uma régua invisível (o "modelo") para desenhar uma linha no chão e separar as duas turmas. O objetivo é fazer essa linha ficar o mais justa possível, deixando o máximo de espaço (margem) entre a linha e os alunos mais próximos.

Existem várias maneiras de ajustar essa régua. A mais famosa e comum é o Adam, que é como um guia muito esperto que olha para o chão, sente a textura e decide se deve dar um passo grande ou pequeno, e em qual direção.

Aqui está o que os autores descobriram, explicado de forma simples:

1. O Segredo do "Chefe" vs. O "Estagiário"

Antes deste estudo, sabíamos que quando o robô olha para todos os alunos de uma vez (o modo "Full-Batch", ou "Chefe"), o guia Adam age de uma maneira muito específica: ele tende a desenhar uma linha que se parece com um cubo. Ele prioriza o espaço em todas as direções de forma igual, como se estivesse tentando caber dentro de uma caixa quadrada. Isso é chamado de viés $\ell_\infty$.

Mas, na vida real, os robôs não olham para todos os alunos de uma vez. Eles olham para um aluno de cada vez (ou pequenos grupos), o que chamamos de "Mini-batch" ou "Estagiário".

A grande descoberta: Os autores provaram que, quando o Adam trabalha sozinho, olhando um aluno por vez (modo "Incremental"), ele esquece de ser aquele guia "cúbico". Ele muda de personalidade! Em vez de desenhar um cubo, ele começa a desenhar uma linha que se parece mais com uma bola (o viés $\ell_2$), ou seja, ele tenta ser o mais "redondo" e equilibrado possível.

2. A Analogia da Montanha e do Mapa

Pense no treinamento do robô como uma descida de montanha:

• O Adam "Chefe" (Full-Batch): Ele tem um mapa perfeito de toda a montanha. Ele sabe exatamente onde estão os picos e vales. Por isso, ele segue um caminho muito rígido e previsível (o caminho do cubo).
• O Adam "Estagiário" (Mini-batch): Ele só vê o pedaço de chão onde está pisando no momento. Ele tropeça um pouco, ajusta a direção com base no que vê agora. O estudo mostra que essa "visão limitada" faz com que ele termine em um lugar diferente do "Chefe". Ele acaba seguindo um caminho que depende muito de como os alunos estão distribuídos na sala. Se os alunos estiverem em um formato estranho, o robô se adapta a esse formato, em vez de seguir uma regra fixa.

3. O "Proxy" (O Tradutor)

Como é difícil prever exatamente onde o "Estagiário" vai parar (porque ele depende dos dados), os autores criaram um "tradutor" matemático. Eles inventaram um algoritmo fictício chamado AdamProxy.

• Imagine que o AdamProxy é um tradutor que pega o comportamento bagunçado do Adam "Estagiário" e diz: "Ok, ele vai parar aqui, porque os dados têm esta forma específica".
• Eles mostraram que, para certos tipos de dados, esse tradutor confirma que o robô vai parar no centro da "bola" (margem máxima $\ell_2$), e para outros dados, ele pode voltar a ser um "cubo". O importante é que não é mais uma regra fixa; depende do cenário.

4. O "Signum": O Robô Teimoso

Para contrastar, os autores olharam para outro algoritmo chamado Signum.

• Se o Adam é um guia que muda de ideia dependendo de quem ele vê, o Signum é um teimoso.
• Não importa se ele olha para um aluno ou para a turma toda, o Signum sempre insiste em desenhar aquele "cubo" (o viés $\ell_\infty$). Ele não muda de personalidade. Isso é interessante porque mostra que a mudança de comportamento do Adam não é uma lei universal de todos os otimizadores, mas sim uma característica específica do Adam quando ele trabalha em pequenos passos.

Resumo da Ópera

• O que pensávamos: O Adam sempre age como um "cubo" (prioriza certas direções), não importa como ele é usado.
• O que descobrimos: Se você usar o Adam olhando um dado de cada vez (como na maioria dos treinamentos reais), ele muda! Ele se torna mais flexível e depende da forma dos dados, muitas vezes agindo como uma "bola".
• Por que importa: Isso explica por que o Adam funciona tão bem em redes neurais complexas (como as que geram texto ou imagens). Ele não é "cego" e rígido; ele se adapta à geometria dos dados quando trabalha em pequenos passos, o que pode ser a chave para sua eficiência.

Em suma, o Adam é como um motorista: se ele tem o GPS completo (Full-Batch), ele segue a rota mais direta e rígida. Se ele está dirigindo olhando apenas pela janela (Mini-batch), ele ajusta a rota constantemente, e o destino final depende muito do trânsito e das ruas que ele encontra.

Resumo técnico

Resumo Técnico: Viés Implícito do Adam por Amostra em Dados Separáveis

1. Problema e Contexto

O otimizador Adam é o padrão de facto no treinamento de redes neurais profundas, mas sua compreensão teórica, especialmente em relação ao seu viés implícito (a tendência de convergir para soluções específicas sem regularização explícita), permanece limitada.

• Estado da Arte (Full-Batch): Trabalhos anteriores (ex: Zhang et al., 2024a) demonstraram que o Adam em full-batch (processando todo o conjunto de dados a cada passo) converge direcionalmente para a solução de margem máxima $\ell_\infty$ em problemas de classificação linear com dados separáveis. Isso é atribuído à sua similaridade com o Sign Gradient Descent (SignGD).
• A Lacuna: A prática moderna utiliza mini-batches (ou até mesmo per-sample, batch size = 1). A questão central deste trabalho é: O viés $\ell_\infty$ do Adam persiste no regime de mini-batch?
• Hipótese Inicial: Resultados anteriores sobre o SGD indicam que o uso de mini-batches não altera o viés implícito (mantendo o viés $\ell_2$ do Gradiente Descendente). Esperava-se que o Adam se comportasse de forma similar, mas os autores investigam se a adaptividade coordenada do Adam interage de forma diferente com o ruído do mini-batch.

2. Metodologia e Abordagem

Os autores focam em Classificação Linear com Perda Logística (ou Exponencial) em dados linearmente separáveis. Eles analisam o Inc-Adam (Incremental Adam), que processa os dados em ordem cíclica (um amostra por vez), servindo como um proxy teórico para o Adam com batch size 1.

Principais Ferramentas Analíticas:

1. Aproximação de Atualizações por Época:
   • Eles derivam que, sob condições de taxa de aprendizado decrescente e momentum, a atualização do Adam em full-batch (Det-Adam) pode ser aproximada por um SignGD.
   • Em contraste, a atualização do Inc-Adam é aproximada por um Gradiente Descendente Ponderado e Pré-condicionado, onde os pesos dependem da história dos gradientes e da estrutura dos dados.
2. Análise de Dados Estruturados (Scaled Rademacher - SR):
   • Para isolar o efeito da adaptividade, eles constroem um conjunto de dados onde a adaptividade coordenada é eliminada.
   • Resultado Chave: Neste cenário, provam que o Inc-Adam converge para a solução de margem máxima $\ell_2$, enquanto o Adam full-batch converge para a margem máxima $\ell_\infty$. Isso demonstra uma divergência fundamental baseada apenas no esquema de batching.
3. Proxy Uniforme e Limites de $\beta_2 \to 1$:
   • Para dados gerais, a análise direta é complexa devido à dependência da história completa dos gradientes.
   • Os autores introduzem um algoritmo proxy (AdamProxy) válido no limite onde o parâmetro de segunda ordem do momentum ($\beta_2$) tende a 1.
   • Eles caracterizam a direção de convergência como a solução de um problema de maximização de margem adaptativa, definida por uma norma de Mahalanobis. A matriz de covariância dessa norma é determinada por uma equação de ponto fixo dual dependente dos dados.
4. Análise do Signum:
   • Para contraste, analisam o algoritmo Signum (SignSGD com momentum), provando que ele mantém o viés $\ell_\infty$ independentemente do tamanho do batch, desde que o momentum seja suficientemente próximo de 1.

3. Contribuições Principais

1. Descoberta de uma Divergência Crítica:
   • Demonstram que, ao contrário do SGD, o viés implícito do Adam não é invariante ao tamanho do batch. O Adam full-batch favorece a geometria $\ell_\infty$, enquanto o Adam com batch size 1 (incremental) pode convergir para direções diferentes, incluindo a margem máxima $\ell_2$ em certos cenários.
2. Caracterização Teórica para Dados Gerais:
   • Introduzem uma formulação baseada em ponto fixo para descrever o limite do Adam incremental. A direção de convergência é dada por:
     $$\hat{w} \propto \frac{\sum c_i x_i}{\sqrt{\sum c_i^2 x_i^2}}$$
     onde os coeficientes $c_i$ são soluções de um problema de otimização paramétrica acoplado a uma equação de ponto fixo dual. Isso revela que o viés é dependente dos dados de forma complexa, não sendo puramente $\ell_2$ ou $\ell_\infty$.
3. Prova de Invariância do Signum:
   • Provam que o Signum (com momentum alto) preserva o viés $\ell_\infty$ para qualquer tamanho de batch, destacando que a perda do viés $\ell_\infty$ no Adam é específica à sua estrutura de adaptação de taxa de aprendizado por coordenada, e não apenas ao uso de momentum.
4. Evidência Empírica:
   • Experimentos em dados Gaussianos e dados estruturados (SR) confirmam que o Adam incremental converge para a solução predita pelo modelo de ponto fixo, que difere tanto da solução $\ell_2$ (GD) quanto da $\ell_\infty$ (Full-batch Adam).

4. Resultados Chave

• Dados Scaled Rademacher (SR): O Inc-Adam converge para a solução de margem máxima $\ell_2$. O Adam full-batch converge para $\ell_\infty$.
• Dados Gaussianos: O Inc-Adam converge para uma direção intermediária, descrita pelo ponto fixo da equação dual, que não coincide nem com $\ell_2$ nem com $\ell_\infty$.
• Dados Diagonais Deslocados: Em certos casos estruturados, o Inc-Adam pode ainda convergir para $\ell_\infty$, mostrando que o viés é uma função contínua da estrutura dos dados.
• Dependência de $\beta_2$: A aproximação via AdamProxy e a caracterização de ponto fixo são válidas estritamente quando $\beta_2 \to 1$. Para $\beta_2$ menores, a dinâmica é mais complexa e o viés pode variar.
• Signum vs. Adam: O Signum mantém robustez no viés $\ell_\infty$ mesmo com mini-batches, sugerindo que a "perda" da geometria $\ell_\infty$ no Adam é um efeito da interação entre a adaptação de taxa de aprendizado e o ruído do batch.

5. Significado e Impacto

• Revisão do Entendimento do Adam: O trabalho desafia a visão de que o Adam é simplesmente um otimizador que busca a margem $\ell_\infty$. Mostra que essa propriedade é frágil e depende criticamente do regime de batching.
• Explicação para o Desempenho em LLMs: A literatura recente sugere que a vantagem do Adam em Grandes Modelos de Linguagem (LLMs) vem de sua exploração da geometria $\ell_\infty$. Este artigo sugere que, em cenários de batch pequeno (comum no treinamento de LLMs), essa vantagem teórica pode se dissipar ou transformar-se em um viés dependente dos dados, o que pode explicar por que o Adam ainda funciona bem (devido a outros fatores) ou por que o gap entre Adam e SGD diminui em batches menores.
• Novas Direções de Pesquisa: Abre caminho para o desenvolvimento de otimizadores que possam manter a estabilidade do Adam com full-batch enquanto preservam a convergência desejada em mini-batches, ou para a compreensão de como a escolha de hiperparâmetros ($\beta_1, \beta_2$) e o tamanho do batch devem ser ajustados para controlar o viés implícito.

Em resumo, o paper estabelece que o viés implícito do Adam é altamente sensível ao esquema de batching, desconectando-o da simples convergência para a margem $\ell_\infty$ observada no regime full-batch, e fornece uma ferramenta teórica robusta (ponto fixo dual) para prever esse comportamento em cenários práticos de treinamento incremental.