📊 statistics

How AI settled the complexity of the oldest SGD algorithm

Este artículo relata cómo se utilizaron modelos de IA modernos para determinar finalmente la complejidad del peor caso del algoritmo de Kaczmarz, un método fundamental de descenso de gradiente estocástico propuesto por Stefan Kaczmarz en 1937.

Autores originales: Michał Dereziński, Xiaoyu Dong

Publicado 2026-06-30

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Michał Dereziński, Xiaoyu Dong

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

La historia: Cómo la IA resolvió un enigma matemático de 90 años

Imagina un problema matemático que ha estado sentado en un estante desde 1937, acumulando polvo. Es un rompecabezas sobre cómo resolver un sistema gigante de ecuaciones (una forma de encontrar la respuesta perfecta a una pregunta compleja). Este método específico, llamado algoritmo de Kaczmarz, es en realidad el "bisabuelo" de la tecnología que impulsa la IA moderna como ChatGPT y Gemini.

Durante décadas, los matemáticos sabían que este algoritmo funcionaba, pero no podían demostrar exactamente qué tan rápido funcionaba en el peor de los casos. Era como tener un coche que sabías que podía conducir de Nueva York a Los Ángeles, pero no podías calcular el tiempo máximo exacto que tardaría si se encontraba con cada semáforo en rojo y cada atasco de tráfico.

Este artículo cuenta la historia de cómo dos modelos de IA diferentes, Gemini y ChatGPT, se unieron para finalmente resolver este misterio, demostrando exactamente qué tan rápido converge el algoritmo.

Los personajes y la misión

El Algoritmo (El método de Kaczmarz): Imagina que estás intentando encontrar un tesoro oculto en un mapa. No conoces el lugar exacto, pero tienes una lista de pistas (ecuaciones). El algoritmo de Kaczmarz es como un excursionista que, en cada paso, elige una pista al azar, camina hacia el lugar que satisface esa pista, y luego elige otra pista al azar. Con el tiempo, el excursionista se acerca cada vez más al tesoro.
El Misterio: El excursionista eventualmente encuentra el tesoro, pero los matemáticos discutían sobre la velocidad. ¿Podría el excursionista quedarse dando vueltas en círculos durante mucho tiempo? ¿O existe un límite de velocidad garantizado?
Los Investigadores Humanos: Dos científicos (Michał y Xiaoyu) intentaron resolver esto usando la matemática tradicional humana. Se acercaron mucho, pero chocaron contra un muro. Se dieron cuenta de que necesitaban una nueva perspectiva.
El Equipo de IA: Los investigadores recurrieron a la IA. No se limitaron a pedirle a la IA que "lo resolviera". En su lugar, actuaron como directores de orquesta, permitiendo que los modelos de IA hablaran entre sí.

El momento "¡Ajá!": Una carrera de relevos de ideas

La solución no vino de una sola IA trabajando sola. Ocurrió como una carrera de relevos donde el testigo era pasado entre dos corredores diferentes:

La visión de Gemini (El analista funcional): Al pedirle que resolviera el problema, Gemini no dio una prueba completa. En su lugar, hizo una conexión extraña y brillante. Miró el problema matemático y dijo: "Esto no es solo sobre ecuaciones; parece un concepto de una rama de las matemáticas llamada análisis funcional (específicamente, algo llamado 'semigrupos de Markov cuánticos')".
- Analogía: Imagina a un mecánico intentando arreglar un motor averiado. En lugar de mirar los engranajes, Gemini dijo: "Este motor en realidad funciona bajo los mismos principios físicos que un reactor nuclear". Fue una conexión extraña y de alto nivel que los investigadores humanos no habían visto antes.
- El problema: Gemini acertó la conexión, pero no pudo demostrarla. Citó algunos artículos matemáticos que en realidad no contenían la prueba que necesitaba. Era como señalar un libro de una biblioteca y decir: "La respuesta está ahí", pero el libro estaba en realidad vacío.
La prueba de ChatGPT (El resolvedor elemental): Los investigadores humanos tomaron la "conexión extraña" de Gemini y se la entregaron a ChatGPT. Le preguntaron: "Bien, si esta conexión es cierta, ¿puedes demostrarlo usando matemáticas básicas?".
- ChatGPT miró el problema y dijo: "Puedo hacer esto". No utilizó la jerga compleja y confusa que mencionó Gemini. En su lugar, utilizó un truco ingenioso y elemental que involucra números complejos (un tipo de matemática que suele reservarse para la física avanzada y la ingeniería) para demostrar el límite de velocidad.
- Analogía: Si Gemini fue la persona que señaló una montaña distante y dijo: "El tesoro está bajo ese pico", ChatGPT fue quien realmente escaló la montaña, cavó el agujero y encontró el oro.

El resultado: El "último paso" es rápido

El artículo demuestra una cosa específica: El algoritmo de Kaczmarz es tan rápido como esperábamos.

En el mundo de estos algoritmos, hay dos formas de verificar la respuesta:

El Promedio: Tomas todos los pasos que dio el excursionista, los promedias y eso te da una buena respuesta. (Ya sabíamos que esto era rápido).
El Último Paso: Simplemente miras dónde se detuvo el excursionista al final. (Este era el misterio).

El artículo demuestra que el último paso es tan rápido como el promedio. El excursionista no necesita andar dando vueltas al final para "estabilizarse". La posición final ya es una solución perfecta.

Por qué esto es importante (según el artículo)

Es un círculo completo: La versión más antigua conocida del algoritmo que entrena a la IA moderna (SGD) fue resuelta por la IA moderna.
Es una nueva forma de investigar: El artículo no es solo sobre matemáticas; es un estudio de caso sobre cómo los humanos y la IA pueden trabajar juntos. Los humanos no escribieron la prueba; la IA lo hizo. Los humanos solo facilitaron la conversación entre dos IAs diferentes.
Resuelve un problema mayor: Al resolver este rompecabezas específico, también resolvieron una pregunta más amplia y de larga data sobre qué tan rápido funcionan los algoritmos de entrenamiento de IA en general.

La conclusión

Este artículo es la historia de un problema matemático de 90 años que fue demasiado obstinado para que los humanos lo resolvieran solos. Al permitir que dos modelos de IA colaboraran —uno para encontrar una conexión extraña y de alto nivel, y el otro para construir la prueba real— el misterio fue finalmente resuelto. El resultado confirma que el "último paso" de este algoritmo clásico es perfectamente eficiente, y nos muestra un vistazo de cómo podría ser la investigación científica del futuro: una asociación donde los humanos guían a la IA, y la IA realiza el trabajo pesado.

Resumen Técnico: Resolviendo la Complejidad del Algoritmo SGD más Antiguo

Planteamiento del Problema
El artículo aborda un problema abierto de larga data sobre la complejidad computacional en el peor de los casos del algoritmo de Kaczmarz, propuesto por Stefan Kaczarwicz en 1937. Este algoritmo es la instancia más antigua conocida de el Descenso de Gradiente Estocástico (SGD), un paradigma fundamental para el entrenamiento de los modelos de lenguaje de gran tamaño (LLM) modernos. El algoritmo de Kaczmarz resuelve un sistema de ecuaciones lineales $Ax = b$ proyectando iterativamente la estimación actual sobre una ecuación seleccionada aleatoriamente.

Si bien la convergencia del iterado promediado de Kaczmarz aleatorizado era conocida como $O(1/\epsilon)$ (independiente del número de condición de la matriz), la tasa de convergencia del último iterado (el resultado estándar en la práctica) permanecía sin resolver. Intentos previos, tanto de matemáticos aplicados como de científicos de la computación, arrojaron solo resultados parciales o cotas subóptimas (por ejemplo, $O(1/\epsilon^{1/\alpha})$ con $\alpha < 1$ ). La cuestión central es si el último iterado del algoritmo de Kaczmarz aleatorizado alcanza la tasa de convergencia óptima de $O(1/\epsilon)$ , igualando el rendimiento del iterado promediado y los límites teóricos para la regresión de mínimos cuadrados sin ruido.

Metodología: Investigación Liderada por IA
El artículo presenta un caso de estudio novedoso de "investigación liderada por IA", donde investigadores humanos facilitan una colaboración entre dos modelos de IA, Gemini Deep Think y ChatGPT Pro, para derivar una prueba matemática. La metodología siguió una trayectoria específica:

Interacción Inicial Humano-IA: Los autores primero utilizaron el razonamiento humano para reducir el problema a una desigualdad discreta, la cual encargaron a ChatGPT para resolverla. Esto produjo una cota subóptima ( $\alpha = 3/4$ ).
Intentos Autónomos: Los autores instaron a ambos modelos a resolver el problema de forma autónoma. ChatGPT identificó correctamente el problema como una cuestión abierta, mientras que Gemini afirmó tener una solución afirmativa pero no logró proporcionar una prueba rigurosa, citando teoremas inexistentes y referencias incorrectas.
Síntesis y Verificación: A pesar de las fallas en la prueba de Gemini, este identificó una conexión crucial con el análisis funcional, específicamente la teoría de semigrupos de Markov cuánticos simétricos y operadores Ritt. Los autores sintetizaron las ideas de Gemini en una conjetura formal sobre una cota de operador.
Derivación Final: Esta conjetura fue presentada a ChatGPT, que derivó con éxito una prueba elemental utilizando técnicas de análisis complejo (específicamente la estimación de Cauchy para derivadas de funciones analíticas) y teoría de operadores, resolviendo así la cuestión abierta.

Contribuciones Clave y Resultados
La contribución principal es la prueba de que el último iterado del algoritmo de Kaczmarz alcanza la tasa de convergencia óptima.

Teorema Principal (Teorema 3.1): Los autores establecen una cota general para un operador $\Phi(X) = \mathbb{E}[BXB]$ , donde $B$ es una contracción positiva aleatoria. Demuestran que la norma del operador de la diferencia entre las composiciones $T$ y $T+1$ satisface:
$\|\Phi^T - \Phi^{T+1}\|_{op \to op} \leq \frac{3}{T+1}$
Aplicación a Kaczmarz (Corolario 3.2): Al mapear la actualización de Kaczmarz a este marco de operadores, el artículo demuestra que, para una matriz $A$ y un vector $b$ , el error cuadrático esperado del último iterado $x^{(T)}$ satisface:
$\mathbb{E} \|A(x^{(T)} - x^*)\|^2 \leq \frac{C}{T} \|A\|_F^2 \|x^*\|^2$
Esto confirma la tasa de convergencia $O(1/\epsilon)$ para el último iterado, resolviendo la cuestión planteada en la literatura previa [39, 6].
Implicaciones Más Amplias (Corolario 3.3): El resultado se extiende al análisis del último iterado de SGD para la regresión de mínimos cuadrados sin ruido, resolviendo una pregunta abierta de larga data sobre la dinámica de convergencia de SGD en contextos de entrenamiento de LLM [8, 41].

Significancia y Reivindicaciones
El artículo reclama significancia en dos frentes:

Resolución Matemática: Resuelve un problema abierto fundamental en la optimización estocástica que ha resistido su solución durante décadas, cerrando la brecha entre el análisis teórico (que a menudo depende del promedio) y la aplicación práctica (que utiliza el último iterado). La prueba utiliza un enfoque distinto que involucra análisis funcional y análisis complejo, diferenciándose de las pruebas previas de convergencia de SGD.
Caso de Estudio Metodológico: El artículo sirve como documentación de una forma específica de colaboración humano-IA. Los autores enfatizan que, si bien la prueba matemática fue generada por una IA, el proceso de investigación requirió la facilitación humana para transferir conocimientos entre modelos y verificar la validez del resultado. Argumentan que esto representa un "punto medio" de la investigación liderada por IA donde la IA actúa como el motor principal del análisis pero permanece bajo supervisión humana, destacando tanto las capacidades actuales como las limitaciones de la IA autónoma en el descubrimiento matemático.

Los autores mantienen la modestia respecto a la novedad del resultado en sí, señalando que, dada la naturaleza elemental del argumento, los investigadores humanos podrían haberlo resuelto eventualmente con suficiente tiempo y esfuerzo. Sin embargo, afirman que el camino específico tomado —aprovechar la IA para conectar campos dispares de las matemáticas (SGD y análisis funcional)— demuestra un nuevo potencial para el descubrimiento científico.