Otimização convexa online: em 20 anos, da teoria ao Adam e aos LLMs

Há vinte anos, a online convex optimization (OCO) ainda era uma área jovem, na interseção entre ciência da computação teórica, aprendizado de máquina e otimização. Hoje, sua linguagem (regret, atualizações adaptativas, decisões sequenciais sem conhecimento do futuro) está embutida na forma como os modelos modernos são treinados. A publicação chinesa Jiqizhixin dedicou uma longa reportagem a essa trajetória, com um título irônico: o homem que passou a vida estudando o «arrependimento» diz que não se arrepende de nada.

No trecho a que tivemos acesso, o texto é interrompido em uma lista de métodos (Online Newton Step e os seguintes), e o nome do protagonista não aparece. Por isso, a seguir nos baseamos na história pública da área, e não nos detalhes da entrevista em si.

O que o regret mede

Na formulação usual de um problema de otimização, a função de perda inteira é conhecida de antemão. Na OCO, é diferente. A cada passo, o algoritmo escolhe um ponto e só depois o ambiente revela uma função de perda convexa. A qualidade é medida pelo regret: a soma das perdas do algoritmo menos a soma das perdas da melhor solução fixa, que só pode ser escolhida em retrospecto.

A principal conquista da área é conseguir tornar o regret sublinear. Nesse caso, a perda média do algoritmo converge para a perda da melhor escolha constante, e isso sem nenhuma hipótese estatística sobre os dados. O trabalho clássico de Martin Zinkevich, de 2003, mostrou que o gradiente descendente online entrega regret da ordem de √T em funções convexas e Lipschitz. Esse foi o ponto de partida.

Do Online Newton Step aos otimizadores adaptativos

Por volta de 2006, Elad Hazan, Amit Agarwal e Satyen Kale propuseram o algoritmo Online Newton Step. Para as chamadas funções exp-concave, ele entrega regret da ordem de log T, ou seja, nitidamente melhor que √T. A ideia é usar informação de segunda ordem: o passo se ajusta à geometria dos gradientes acumulados.

Dali, essa linha levou a métodos que qualquer pessoa que já rodou um treinamento conhece:

• AdaGrad (Duchi, Hazan, Singer, 2011): uma escala de passo própria para cada parâmetro. Funciona bem com features esparsas.
• RMSProp e Adam (2014): descendentes práticos da mesma ideia, com média móvel exponencial dos gradientes.
• Análise de regret como padrão de prova: a justificativa original de convergência do Adam foi construída justamente no arcabouço da OCO.

Há também um episódio revelador. Em 2018, o artigo «On the Convergence of Adam and Beyond» (Reddi et al., ICLR) mostrou que a prova original do Adam contém um erro e que o método pode não convergir em alguns problemas convexos. A correção, o AMSGrad, também foi formulada na linguagem do regret. A teoria não só descrevia a prática: ela apontou os erros dela.

Por que isso importa agora

Os grandes modelos de linguagem costumam ser treinados com variantes do Adam, na maioria das vezes o AdamW. O problema, nesse caso, é não convexo, e as garantias da OCO não se transferem diretamente. Mas a intuição se transfere: passos adaptativos, precondicionamento, consideração da curvatura. Pesquisas recentes sobre otimizadores com precondicionadores matriciais seguem essa mesma linha, em que a adaptação diagonal do AdaGrad cede lugar a estruturas mais ricas.

Um ramo à parte está ligado ao aprendizado online em sua forma pura. A minimização de regret está na base de algoritmos para jogos, sistemas de recomendação, precificação dinâmica e alocação de recursos. Nesses problemas, o futuro é de fato desconhecido, e os dados não precisam ser independentes.

O que levar disso para a prática

Se você treina ou faz fine-tuning de modelos, vale lembrar de onde vieram os hiperparâmetros do otimizador. Epsilon, coeficientes beta e o cronograma do passo não são arbitrários: têm um significado teórico. Isso ajuda a depurar treinamentos instáveis, já que a divergência muitas vezes vem de a média adaptativa «esquecer» gradientes raros, porém grandes, exatamente no espírito do contraexemplo ao Adam.

Para quem constrói sistemas de decisões sequenciais (recomendações, lances em leilões de anúncios, roteamento de requisições entre modelos), a OCO oferece um arcabouço pronto. Ele permite comparar algoritmos com uma referência justa e obter garantias sem hipóteses sobre a distribuição dos dados. Para uma introdução ao tema, o livro de Hazan, «Introduction to Online Convex Optimization», é uma boa escolha. Vale ler a entrevista completa no site da Jiqizhixin no original: por trás do título sobre «zero arrependimentos», a julgar pelo anúncio, há a história pessoal de vinte anos de desenvolvimento do método.