¿Qué tan largo puede ser el camino de un flujo de gradiente en una función convexa, bajo la restricción de que permanezca dentro de la bola euclidiana unitaria en dimensión n?
^ esa es la pregunta que he estado usando durante 2 años para probar el progreso de la IA. Es increíblemente simple de plantear, pero endiabladamente difícil de resolver. En 168 minutos de pensamiento, GPT-5.6 logró superar significativamente el estado del arte publicado sobre esta pregunta, de una manera que ningún otro modelo había logrado hasta ahora. Pero me estoy adelantando, primero reflexionemos un poco sobre la pregunta, revisemos la literatura y luego discutamos cómo ha sido el progreso de o3 a GPT-5.6.
1. SOTA
Ingenuamente uno podría decir: "bueno, el descenso de gradiente tiene una tasa de convergencia que es independiente de la dimensión —por lo que es emocionante usarlo para problemas con muchos parámetros—, así que probablemente la longitud de dicho flujo también debería ser independiente de la dimensión". Bueno, a veces las ideas ingenuas pueden estar completamente equivocadas. Para empezar: ¿siquiera son rectificables dichas curvas (es decir, de longitud finita, sin mencionar la dependencia de la dimensión)? Incluso eso no es fácil de demostrar, y de hecho es FALSO para el descenso de gradiente acelerado de Nesterov (ver este artículo de @ErnestRyu, todo hecho con GPT-5.5).
Bien, entonces, ¿qué se sabe exactamente sobre esta pregunta? Bueno, hay un hermoso artículo de 1991 de Manselli y Pucci que muestra que dichas curvas son efectivamente rectificables, y además su longitud es a lo sumo n^O(n). Sí, leíste bien, incluso peor que exponencial en la dimensión, ¡esa es la mejor cota de hace 35 años! Por cierto, este artículo también señala que dichas curvas son lo que se llama "autocontraídas", es decir, siempre se acercan a su futuro (toma cualquier punto en la curva en el tiempo t, entonces dist(x(s), x(t)) es no creciente para s<t; ver ilustración a continuación).
Ahora, ¿qué hay de las cotas inferiores, es decir, construir una curva autocontraída realmente larga? Algo estándar de la literatura de optimización convexa sería una cuadrática mal condicionada, algo como x_1^2 + cte_grandex_2^2 + cte_aún_más_grandex_3^2 + ... El punto es que el descenso de gradiente primero irá casi en línea recta a lo largo de la dirección con la cte más grande, luego irá en la dirección de la segunda cte más grande, y así sucesivamente (ver ilustración a continuación). Por lo tanto, la longitud total del camino será aproximadamente n, y el camino está contenido en el hipercubo que está contenido en una bola de radio sqrt(n), por lo que al reescalar obtenemos una curva autocontraída de longitud sqrt(n).
Eso es todo. Ese es el estado del arte publicado: cota superior de n^O(n) y cota inferior de sqrt(n). ¡Qué brecha tan enorme para una pregunta tan simple y natural!!!
Definición de una curva autocontraída
Una curva autocontraída de longitud sqrt(n)
2. Trabajo no publicado por humanos
Pensé en esta pregunta hace 8 años con increíbles colaboradores Omer Angel, Tomas Merchan Rodriguez y Fedja Nazarov. Logramos avanzar bastante y establecimos que la respuesta es efectivamente exponencial en la dimensión. Específicamente, teníamos una cota inferior de sqrt(2)^n y una cota superior de 4^n. El artículo con estas estimaciones está bien escrito y ha estado en mi carpeta de Dropbox durante casi una década, en parte porque sabíamos que estas cotas podían mejorarse aún más. Y de hecho, Tomas y Fedja hicieron más progresos, primero elevando la cota inferior a 2^n y también mejorando la cota superior a 2.29...^n. Nota: mi propia comprensión del problema se quedó en una cota inferior ligeramente mejor que sqrt(2)^n y una cota superior de 4^n (de hecho, había olvidado los 2^n y 2.29^n hasta que la IA comenzó a progresar en esto... más abajo).
3. Progreso de la IA
o3 fue el primer modelo de IA en siquiera entender la pregunta. Sí, leíste esa frase correctamente. Quizás hayas olvidado, pero hace dos años ni siquiera estaba claro que una IA pudiera ENTENDER preguntas tan engañosamente simples, y mucho menos resolverlas. En particular, o3 podía ver que la pregunta trataba en realidad sobre curvas autocontraídas, y conocía el estado del arte sobre esta pregunta. En ese momento, quedé muy, muy impresionado.
Pero luego las cosas se complicaron, y con la llegada de la serie de modelos GPT-5, usé esta pregunta como una advertencia: hasta febrero de este año, daba esta pregunta en charlas sobre el progreso de los LLM en matemáticas como un ejemplo de una pregunta que NO se debería hacer a los LLM. La razón es que GPT-5 o incluso GPT-5.2/5.4 INTENTABAN dar respuestas complicadas, pero invariablemente estaban equivocadas en algún punto, y uno perdía mucho tiempo revisándolas. Así que era un buen ejemplo de que para no perder tiempo con los LLM en matemáticas, uno debe saber el nivel adecuado de pregunta que hacer.
Esto cambió con GPT-5.5, y de repente, con mucho ir y venir y prompting experto, Mark Sellke logró redescubrir la construcción de la cota inferior de 2^n (¡lo cual me IMPACTÓ, en parte porque había olvidado que Tomer y Fedja ya la conocían 😅). Por otro lado, no hubo suerte en absoluto con la cota superior.
Y ahora llega GPT-5.6, y el progreso de la IA se ve completamente:
- GPT-5.6-pro RESUELVE DE UNA SOLA VEZ la cota inferior de 2^n. Puedes ver la solución aquí (80 minutos de pensamiento): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro RESUELVE DE UNA SOLA VEZ la cota superior de 4^n, y de hecho lo hace muy rápidamente en su cadena de pensamiento, y al final de su razonamiento produce una cota superior de 2.31...^n. No alcanza exactamente el 2.29...^n de Fedja (y de hecho, la estrategia de 2.31...^n no se puede mejorar sin nuevas ideas, como el propio Fedja señaló en una publicación de MathOverflow en 2018: '[para 2.31..] el argumento se vuelve algo complicado y está claro que este camino no llevará a la estimación óptima'). Pero aún así es bastante impresionante y supera lo que yo había entendido personalmente sobre el problema cuando trabajaba seriamente en él. Puedes ver la solución aquí, realizada en 88 minutos de pensamiento: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. Un desafío para el futuro
Esta historia todavía tiene a los humanos como ganadores. 2.29 para humanos contra 2.31 para máquinas. Naturalmente, la conjetura es que las curvas autocontraídas no pueden ser más largas que 2^n (lo que sería la respuesta óptima dada la cota inferior de 2^n). Esto parece muy difícil de demostrar y está más allá de las capacidades de GPT-5.6. ¿Por cuánto tiempo podré usar esta pregunta para seguir el progreso de la IA? Sospecho que podría ser menos de 6 meses...
PD: Copié y pegué la publicación anterior en ChatGPT work y le pedí que generara ilustraciones para ella. La colección de imágenes aquí se obtuvo de una sola vez a partir de esa consulta.
