¿Qué longitud puede tener la trayectoria de un flujo gradiente sobre una función convexa, dada la restricción de que permanezca dentro de la bola euclidiana unitaria en dimensión n?
^ Esta es la pregunta que he estado usando durante 2 años para probar el progreso de la IA. Es engañosamente simple de enunciar y, sin embargo, diabólicamente difícil de resolver. En 168 minutos de pensamiento, GPT-5.6 logró superar significativamente el estado del arte publicado sobre esta cuestión, de una manera que ningún otro modelo había logrado hasta ahora. Pero me estoy adelantando; primero pensemos un poco en la pregunta, revisemos la literatura y luego discutamos cómo ha sido el progreso de o3 a GPT-5.6.
1. Estado del arte
Ingenuamente, uno podría decir: "bueno, el descenso por gradiente tiene una tasa de convergencia que es independiente de la dimensión —¡por eso 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 esas curvas (es decir, de longitud finita, sin importar la dependencia de la dimensión)? ¡Incluso eso no es fácil de demostrar! De hecho, es FALSO para el descenso por gradiente acelerado de Nesterov (véase este artículo de @ErnestRyu, todo hecho con GPT-5.5).
Bien, ¿qué se sabe exactamente sobre esta cuestión? Pues 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 como máximo n^O(n). Sí, leíste bien: ¡incluso peor que exponencial en la dimensión! Ese es el mejor límite de hace 35 años. Por cierto, este artículo también señala que esas curvas son lo que se llama "autocontraídas", es decir, siempre se acercan a su futuro (toma cualquier punto de la curva en el tiempo t, entonces dist(x(s), x(t)) es no creciente para s < t; ver ilustración más abajo).
Ahora, ¿qué hay de las cotas inferiores, es decir, construir una curva autocontraída realmente larga? Un ejemplo estándar de la literatura de optimización convexa sería una cuadrática mal condicionada, algo como x_1^2 + cst_grande\x_2^2 + cst_aún_más_grande\x_3^2 + ... La cuestión es que el descenso por gradiente primero irá casi en línea recta a lo largo de la dirección con la constante más grande, luego irá en la dirección de la segunda constante más grande, y así sucesivamente (ver ilustración más abajo). Por lo tanto, la longitud total del camino será aproximadamente n, y el camino está contenido en el hipercubo, que a su vez está contenido en una bola de radio sqrt(n), así que reescalando 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 grande 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 colaboradores increíbles: 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 guardado en mi carpeta de Dropbox durante casi una década, en parte porque sabíamos que estos límites podían mejorarse aún más. Y de hecho, Tomas y Fedja avanzaron más, primero elevando la cota inferior a 2^n y también mejorando la cota superior a 2.29...^n. Nota que mi propia comprensión del problema se quedó en la cota inferior ligeramente mejor que sqrt(2)^n y la cota superior de 4^n (de hecho, había olvidado los 2^n y 2.29^n hasta que la IA empezó 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 bien esa frase. Quizás lo olvidaste, pero hace dos años ni siquiera estaba claro que una IA pudiera COMPRENDER 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 sabía cuál era el estado del arte en esta cuestión. En ese entonces, quedé muy, muy impresionado.
Pero luego las cosas se complicaron, y con la llegada de la serie GPT-5 de modelos, usé esta pregunta como una historia de advertencia: incluso en febrero de este año, en charlas sobre el progreso de los LLMs en matemáticas, ponía esta pregunta como un ejemplo de lo que NO se debería preguntar a los LLMs. La razón es que GPT-5 o incluso GPT-5.2/5.4 INTENTABAN dar respuestas complicadas, pero siempre estaban equivocadas en algún punto, y uno perdía mucho tiempo verificándolas. Así que era un buen ejemplo de que, para no perder tiempo con los LLMs en matemáticas, hay que saber el nivel adecuado de pregunta que hacer.
Esto cambió con GPT-5.5, y de repente, con mucho ida y vuelta y un 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 alguna con la cota superior.
Y ahora llega GPT-5.6, y el progreso de la IA se vuelve completamente visible:
- GPT-5.6-pro RESUELVE DE UN SOLO INTENTO la cota inferior de 2^n. Puedes ver el resultado aquí (80 minutos de pensamiento): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro RESUELVE DE UN SOLO INTENTO 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 los 2.29...^n de Fedja (y de hecho, la estrategia de 2.31...^n no se puede mejorar sin nuevas ideas —de hecho, el propio Fedja lo señaló en un post de MathOverflow en 2018: "[para 2.31...] el argumento se vuelve algo enredado y está claro que este camino no llevará a la estimación óptima"). Pero sigue siendo bastante impresionante y más allá de lo que yo mismo había entendido sobre el problema cuando trabajaba seriamente en él. Puedes ver el resultado aquí, hecho 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 los humanos frente a 2.31 para las máquinas. Naturalmente, la conjetura es que las curvas autocontraídas no pueden tener una longitud mayor 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. ¿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é el texto anterior en ChatGPT y le pedí que generara ilustraciones. La colección de imágenes aquí se obtuvo de un solo intento a partir de esa consulta.
