📊 statistics

How AI settled the complexity of the oldest SGD algorithm

Este artigo relata como modelos modernos de IA foram utilizados para finalmente determinar a complexidade de pior caso do algoritmo de Kaczarz, um método fundamental de gradiente descendente estocástico proposto por Stefan Kaczarz em 1937.

Autores originais: Michał Dereziński, Xiaoyu Dong

Publicado 2026-06-30

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Michał Dereziński, Xiaoyu Dong

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

A História: Como a IA resolveu um enigma matemático de 90 anos

Imagine um problema matemático que está parado em uma prateleira desde 1937, acumulando poeira. É um enigma sobre como resolver um sistema gigante de equações (uma forma de encontrar a resposta perfeita para uma questão complexa). Este método específico, chamado algoritmo de Kaczmarz, é, na verdade, o "bisavô" da tecnologia que alimenta a IA moderna, como o ChatGPT e o Gemini.

Por décadas, os matemáticos sabiam que este algoritmo funcionava, mas não consegiam provar exatamente o quão rápido ele funcionava no pior cenário possível. Era como ter um carro que você sabe que consegue dirigir de Nova York a Los Angeles, mas você não consegue calcular o tempo máximo exato que levaria se pegasse todos os sinais vermelhos e congestionamentos.

Este artigo conta a história de como dois modelos de IA diferentes, Gemini e ChatGPT, se uniram para finalmente resolver este mistério, provando exatamente a velocidade de convergência do algoritmo.

Os Personagens e a Missão

O Algoritmo (O Método de Kaczmarz): Imagine que você está tentando encontrar um tesouro escondido em um mapa. Você não sabe o local exato, mas tem uma lista de pistas (equações). O algoritmo de Kaczmarz é como um caminhante que, a cada passo, escolhe uma pista aleatória, caminha em direção ao ponto que satisfaz essa pista e, então, escolhe outra pista aleatória. Com o tempo, o caminhante chega cada vez mais perto do tesouro.
O Mistério: O caminhante eventualmente encontra o tesouro, mas os matemáticos estavam discutindo sobre a velocidade. O caminhante poderia ficar andando em círculos por muito tempo? Ou existe um limite de velocidade garantido?
Os Pesquisadores Humanos: Dois cientistas (Michał e Xiaoyu) tentaram resolver isso usando a matemática humana tradicional. Eles chegaram perto, mas bateram em um muro. Eles perceberam que precisavam de uma nova perspectiva.
A Equipe de IA: Os pesquisadores recorreram à IA. Eles não apenas pediram para a IA "resolver o problema". Em vez disso, eles atuaram como maestros, deixando os modelos de IA conversarem entre si.

O Momento "Aha!": Uma Corrida de Revezamento de Ideias

A solução não veio de uma IA trabalhando sozinha. Aconteceu como uma corrida de revezamento onde o bastão foi passado entre dois corredores diferentes:

A Percepção do Gemini (O Analista Funcional): Ao ser solicitado para resolver o problema, o Gemini não deu uma prova completa. Em vez disso, ele fez uma conexão estranha e brilhante. Ele olou para o problema matemático e disse: "Isso não é apenas sobre equações; parece um conceito de um ramo da matemática chamado análise funcional (especificamente, algo chamado 'semigrupos de Markov quânticos')".
- Analogia: Imagine um mecânico tentando consertar um motor quebrado. Em vez de olhar para as engrenagens, o Gemini disse: "Este motor está, na verdade, rodando sob os mesmos princípios físicos de um reator nuclear". Foi uma conexão estranha e de alto nível que os pesquisadores humanos não tinham visto antes.
- A Armadilha: O Gemini acertou a conexão, mas não conseguiu prová-la. Ele citou alguns artigos matemáticos que, na verdade, não continham a prova que ele precisava. Era como apontar para um livro de biblioteca e dizer: "A resposta está aí dentro", mas o livro estava, na verdade, vazio.
A Prova do ChatGPT (O Solucionador Elementar): Os pesquisadores humanos pegaram essa "conexão estranha" do Gemini e a entregaram ao ChatGPT. Eles perguntaram: "Ok, se esta conexão for verdadeira, você pode prová-la usando matemática básica?".
- O ChatGPT olhou para o problema e disse: "Eu consigo fazer isso". Ele não usou o jargão complexo e confuso que o Gemini mencionou. Em vez disso, usou um truque inteligente envolvendo números complexos (um tipo de matemática geralmente reservada para física avançada e engenharia) para provar o limite de velocidade.
- Analogia: Se o Gemini foi a pessoa que apontou para uma montanha distante e disse: "O tesouro está sob aquele pico", o ChatGPT foi quem realmente escalou a montanha, cavou o buraco e encontrou o ouro.

O Resultado: O "Último Passo" é Rápido

O artigo prova uma coisa específica: O algoritmo de Kaczmarz é tão rápido quanto esperávamos.

No mundo desses algoritmos, existem duas maneiras de verificar a resposta:

A Média: Você pega todos os passos que o caminhante deu, tira a média deles e isso te dá uma boa resposta. (Já sabíamos que isso era rápido).
O Último Passo: Você apenas olha para onde o caminhante parou ao final de tudo. (Este era o mistério).

O artigo prova que o último passo é tão rápido quanto a média. O caminhante não precisa vagar sem rumo no final para "se estabilizar". A posição final já é uma solução perfeita.

Por Que Isso Importa (De Acordo com o Artigo)

É um Ciclo Completo: A versão mais antiga conhecida do algoritmo que treina a IA moderna (SGD) foi resolvida pela IA moderna.
É uma Nova Forma de Pesquisa: O artigo não é apenas sobre matemática; é um estudo de caso sobre como humanos e IA podem trabalhar juntos. Os humanos não escreveram a prova; a IA escreveu. Os humanos apenas facilitaram a conversa entre duas IAs diferentes.
Resolve um Problema Maior: Ao resolver este enigma específico, eles também resolveram uma questão mais ampla e de longa data sobre a velocidade com que os algoritmos de treinamento de IA funcionam em geral.

A Conclusão

Este artigo é a história de um problema matemático de 90 anos que foi teimoso demais para os humanos resolverem sozinhos. Ao deixar dois modelos de IA colaborarem — um para encontrar uma conexão estranha e de alto nível, e o outro para construir a prova real — o mistério foi finalmente resolvido. O resultado confirma que o "último passo" deste algoritmo clássico é perfeitamente eficiente e nos mostra um vislumbre de como poderá ser a pesquisa científica no futuro: uma parceria onde os humanos guiam a IA, e a IA faz o trabalho pesado.

Resumo Técnico: Resolvendo a Complexidade do Algoritmo SGD Mais Antigo

Enunciado do Problema
O artigo aborda um problema em aberto de longa data referente à complexidade computacional de pior caso do algoritmo de Kaczmarz, proposto por Stefan Kaczmarz em 1937. Este algoritmo é o exemplo mais antigo conhecido de Descida de Gradiente Estocástica (SGD), um paradigma fundamental para o treinamento de Modelos de Linguagem de Grande Escala (LLMs) modernos. O algoritmo de Kaczmarz resolve um sistema de equações lineares $Ax = b$ ao projetar iterativamente a estimativa atual sobre uma equação selecionada aleatoriamente.

Embora a convergência da iteração média do Kaczmarz aleatorizado fosse conhecida como $O(1/\epsilon)$ (independente do número de condição da matriz), a taxa de convergência da última iteração (o resultado padrão na prática) permanecia não resolvida. Tentativas anteriores, tanto de matemáticos aplicados quanto de cientistas da computação, produziram apenas resultados parciais ou limites subótimos (por exemplo, $O(1/\epsilon^{1/\alpha})$ com $\alpha < 1$ ). A questão central é se a última iteração do algoritmo de Kaczmarz aleatorizado atinge a taxa de convergência ótima de $O(1/\epsilon)$ , igualando o desempenho da iteração média e os limites teóricos para regressão de mínimos quadrados sem ruído.

Metodologia: Pesquisa Liderada por IA
O artigo apresenta um estudo de caso inovador de "pesquisa liderada por IA", onde pesquisadores humanos facilitam uma colaboração entre dois modelos de IA, Gemini Deep Think e ChatGPT Pro, para derivar uma prova matemática. A metodologia seguiu uma trajetória específica:

Interação Inicial Humano-IA: Os autores primeiro utilizaram o raciocínio humano para reduzir o problema a uma desigualdade discreta, que então incumbiram o ChatGPT de resolver. Isso resultou em um limite subótimo ( $\alpha = 3/4$ ).
Tentativas Autônomas: Os autores instigaram ambos os modelos a resolver o problema autonomamente. O ChatGPT identificou corretamente o problema como uma questão em aberto, enquanto o Gemini afirmou possuir uma solução afirmativa, mas falhou em fornecer uma prova rigorosa, citando teoremas inexistentes e referências incorretas.
Síntese e Verificação: Apesar das falhas na prova do Gemini, ele identificou uma conexão crucial com a análise funcional, especificamente a teoria de semigrupos de Markov quânticos simétricos e operadores de Ritt. Os autores sintetizaram os insights do Gemini em uma conjectura formal relativa a um limite de operador.
Derivação Final: Esta conjectura foi apresentada ao ChatGPT, que derivou com sucesso uma prova elementar usando técnicas de análise complexa (especificamente a estimativa de Cauchy para derivadas de funções analíticas) e teoria de operadores, resolvendo assim a questão em aberto.

Principais Contribuições e Resultados
A principal contribuição é a prova de que a última iteração do algoritmo de Kaczmarz atinge a taxa de convergência ótima.

Teorema Principal (Teorema 3.1): Os autores estabelecem um limite geral para um operador linear $\Phi(X) = \mathbb{E}[BXB]$ , onde $B$ é uma contração positiva aleatória. Eles provam que a norma do operador da diferença entre as composições $T$ e $T+1$ satisfaz:
$\|\Phi^T - \Phi^{T+1}\|_{op \to op} \leq \frac{3}{T+1}$
Aplicação a Kaczarp (Corolário 3.2): Ao mapear a atualização de Kaczarp para este arcabouço de operador, o artigo prova que, para uma matriz $A$ e um vetor $b$ , o erro quadrático esperado da última iteração $x^{(T)}$ satisfaz:
$\mathbb{E} \|A(x^{(T)} - x^*)\|^2 \leq \frac{C}{T} \|A\|_F^2 \|x^*\|^2$
Isso confirma a taxa de convergência $O(1/\epsilon)$ para a última iteração, resolvendo a questão colocada na literatura anterior [39, 6].
Implicações Mais Amplas (Corolário 3.3): O resultado estende-se à análise da última iteração de SGD para regressão de mínimos quadrados sem ruído, resolvendo uma questão de longa data sobre a dinâmica de convergência de SGD em contextos de treinamento de LLMs [8, 41].

Significância e Alegações
O artigo reivindica significância em duas frentes:

Resolução Matemática: Ele encerra um problema fundamental em otimização estocástica que resistiu à solução por décadas, preenchendo uma lacuna entre a análise teórica (que frequentemente depende de média) e a aplicação prática (que utiliza a última iteração). A prova utiliza uma abordagem distinta envolvendo análise funcional e análise complexa, diferenciando-se de provas anteriores de convergência de SGD.
Estudo de Caso Metodológico: O artigo serve como uma documentação de uma forma específica de colaboração Humano-IA. Os autores enfatizam que, embora a prova matemática tenha sido gerada por IA, o processo de pesquisa exigiu facilitação humana para transferir insights entre modelos e verificar a validade do output. Eles argumentam que isso representa um "meio termo" de pesquisa liderada por IA, onde a IA atua como o motor primário de análise, mas permanece sob supervisão humana, destacando tanto as capacidades atuais quanto as limitações da IA autônoma na descoberta matemática.

Os autores mantêm-se modestos quanto à novidade do resultado em si, observando que, dada a natureza elementar do argumento, pesquisadores humanos poderiam eventualmente ter resolvido o problema com tempo e esforço suficientes. No entanto, eles afirmam que o caminho específico tomado — aproveitando a IA para unir campos distintos da matemática (SGD e análise funcional) — demonstra um novo potencial para a descoberta científica.