Quão longo pode ser o caminho de um fluxo gradiente em uma função convexa, dada a restrição de que ele permaneça dentro da bola euclidiana unitária na dimensão n?
^ esta é a pergunta que venho usando há 2 anos para testar o progresso da IA. É incrivelmente simples de enunciar, mas extremamente difícil de resolver. Em 168 minutos de raciocínio, o GPT-5.6 conseguiu superar de forma muito significativa o melhor resultado publicado (SOTA) para esta questão, de uma forma que nenhum outro modelo havia conseguido até agora. Mas estou me adiantando; vamos primeiro pensar um pouco sobre a questão, revisar a literatura e, em seguida, discutir como tem sido o progresso do o3 para o GPT-5.6.
1. SOTA (Estado da Arte)
Ingenuamente, alguém poderia dizer: "bem, a descida do gradiente tem uma taxa de convergência que é independente da dimensão — é por isso que é empolgante usar para problemas com muitos parâmetros! — então, provavelmente, o comprimento de tal fluxo também deve ser independente da dimensão?". Bem, às vezes, visões ingênuas podem estar totalmente erradas. Para começar: essas curvas são sequer retificáveis (ou seja, de comprimento finito, sem falar na dependência da dimensão)??? Mesmo isso não é fácil de provar e, na verdade, é FALSO para a descida do gradiente acelerada de Nesterov (veja este artigo de @ErnestRyu, tudo feito com o GPT-5.5).
Ok, então o que exatamente se sabe sobre esta questão? Bem, há um belo artigo de 1991 de Manselli e Pucci que mostra que tais curvas são de fato retificáveis e, além disso, seu comprimento é no máximo n^O(n). Sim, você leu corretamente, ainda pior do que exponencial na dimensão, essa é a melhor estimativa de 35 anos atrás!! A propósito, este artigo também aponta que tais curvas são o que se chama de "autocontraídas", ou seja, elas estão sempre se aproximando de seu futuro (pegue qualquer ponto na curva no tempo t, então dist(x(s), x(t)) é não crescente para s < t; veja a ilustração abaixo).
Agora, e quanto aos limites inferiores, ou seja, construir uma curva autocontraída realmente longa? Uma coisa padrão a se observar na literatura de otimização convexa seria uma quadrática mal condicionada, algo como x_1^2 + cst_grande\x_2^2 + cst_ainda_maior\x_3^2 + ... O ponto é que a descida do gradiente primeiro irá quase em linha reta ao longo da direção com o maior cst, depois irá na direção do segundo maior cst, e assim por diante (veja a ilustração abaixo). Portanto, o comprimento total do caminho será aproximadamente n, e o caminho está contido no hipercubo que está contido em uma bola de raio sqrt(n), então, por reescalonamento, obtemos uma curva autocontraída de comprimento sqrt(n).
É isso. Esse é o SOTA publicado: limite superior de n^O(n) e limite inferior de sqrt(n). Que lacuna enorme para uma questão tão simples e natural!!!
Definição de uma curva autocontraída
Uma curva autocontraída de comprimento sqrt(n)
2. Trabalho não publicado por humanos
Pensei sobre esta questão há 8 anos com colaboradores incríveis: Omer Angel, Tomas Merchan Rodriguez e Fedja Nazarov. Conseguimos fazer um progresso considerável e estabelecemos que a resposta é de fato exponencial na dimensão!! Especificamente, tínhamos um limite inferior de sqrt(2)^n e um limite superior de 4^n. O artigo com essas estimativas está bem escrito e está na minha pasta do Dropbox há quase uma década, em parte porque sabíamos que esses limites poderiam ser melhorados ainda mais. E, de fato, Tomas e Fedja fizeram mais progresso, primeiro elevando o limite inferior para 2^n e também melhorando o limite superior para 2,29...^n. Observe que minha própria compreensão do problema permaneceu no limite inferior ligeiramente melhor que sqrt(2)^n e no limite superior de 4^n (na verdade, eu tinha esquecido os valores 2^n e 2,29^n até a IA começar a progredir nisso... mais abaixo).
3. Progresso da IA
O o3 foi o primeiro modelo de IA a sequer entender a questão. Sim, você leu essa frase corretamente. Talvez você tenha esquecido, mas há dois anos não estava claro se uma IA conseguiria ENTENDER questões tão enganosamente simples, muito menos resolvê-las. Em particular, o o3 conseguia ver que a questão era, na verdade, sobre curvas autocontraídas e sabia qual era o SOTA para esta questão. Fiquei altamente, altamente impressionado na época.
Mas então as coisas ficaram complicadas e, com a chegada da série de modelos GPT-5, usei esta questão como um conto de advertência: até fevereiro deste ano, eu usava esta questão em palestras sobre o progresso dos LLMs em matemática como um exemplo de uma questão que você NÃO deveria perguntar aos LLMs. A razão é que o GPT-5 ou mesmo o GPT-5.2/5.4 TENTAVAM dar respostas complicadas, mas invariavelmente estavam errados em algum lugar, e perderíamos muito tempo verificando-as. Portanto, era um bom exemplo de que, para não perder tempo com LLMs em matemática, é preciso saber o nível certo de pergunta a fazer.
Isso mudou com o GPT-5.5 e, de repente, com muita ida e volta e prompting especializado, Mark Sellke conseguiu redescobrir a construção do limite inferior de 2^n (o que me CHOCOU, em parte porque eu tinha esquecido que Tomer e Fedja já sabiam disso 😅). Por outro lado, nenhuma sorte com o limite superior.
E agora chega o GPT-5.6, e o progresso da IA se torna totalmente visível:
- O GPT-5.6-pro ACERTA DE PRIMEIRA o limite inferior de 2^n. Você pode ver o acerto de primeira aqui (80 minutos de raciocínio): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- O GPT-5.6-pro ACERTA DE PRIMEIRA o limite superior de 4^n e, na verdade, faz isso muito rapidamente em sua Cadeia de Pensamento (CoT) e, no final de seu raciocínio, produz um limite superior de 2,31...^n. Não chega a igualar o 2,29...^n de Fedja (e, na verdade, a estratégia de 2,31...^n não pode ser melhorada sem novas ideias — na verdade, o próprio Fedja observou isso em uma postagem no MathOverflow em 2018: "[para 2,31..] o argumento fica um pouco confuso e está claro que este caminho não levará à estimativa ideal"). Ainda assim, é impressionante e vai além do que eu pessoalmente entendia sobre o problema quando trabalhava seriamente nele. Você pode ver o acerto de primeira aqui, feito em 88 minutos de raciocínio: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. Um desafio para o futuro
Esta história ainda tem os humanos como vencedores. 2,29 para humanos contra 2,31 para máquinas. Naturalmente, a conjectura é que as curvas autocontraídas não podem ser mais longas do que 2^n (o que seria então a resposta ótima, dado o limite inferior de 2^n). Isso parece muito difícil de provar e está além das capacidades do GPT-5.6. Por quanto tempo conseguirei usar esta questão para acompanhar o progresso da IA? Suspeito que talvez menos de 6 meses...
PS: Copiei e colei o post acima no ChatGPT e pedi que ele criasse ilustrações para ele. A coleção de imagens aqui foi obtida de uma única solicitação (one-shot) a partir dessa consulta.
