📊 statistics

How AI settled the complexity of the oldest SGD algorithm

Dit artikel beschrijft hoe moderne AI-modellen werden ingezet om eindelijk de slechtste complexiteit van het Kaczmarz-algoritme te bepalen, een fundamentele methode voor stochastische gradiëntafdaling die in 1937 door Stefan Kaczmarz werd voorgesteld.

Oorspronkelijke auteurs: Michał Dereziński, Xiaoyu Dong

Gepubliceerd 2026-06-30

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Michał Dereziński, Xiaoyu Dong

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Verhaal: Hoe AI een 90 jaar oud wiskundig raadsel oploste

Stel je een wiskundig probleem voor dat sinds 1937 op een plank ligt te verstoffen. Het is een puzzel over hoe je een gigantisch stelsel van vergelijkingen oplost (een manier om het perfecte antwoord te vinden op een complexe vraag). Deze specifieke methode, de Kaczmarz-algoritme, is eigenlijk de "grootvader" van de technologie die moderne AI zoals ChatGPT en Gemini aandrijft.

Decennialang wisten wiskundigen dat dit algoritme werkte, maar ze konden niet precies bewijzen hoe snel het werkte in het absolute slechtst denkbare scenario. Het was als een auto waarvan je wist dat hij van New York naar Los Angeles kon rijden, maar je kon niet de exacte maximale tijd berekenen die het zou kosten als je elke rode stoplicht en elke file tegenkwam.

Dit artikel vertelt het verhaal van hoe twee verschillende AI-modellen, Gemini en ChatGPT, samenwerkten om dit mysterie eindelijk op te lossen, waarbij ze precies bewezen hoe snel het algoritme convergeert.

De Personages en de Missie

Het Algoritme (De Kaczmarz-methode): Stel je voor dat je een verborgen schat op een kaart probeert te vinden. Je weet de exacte plek niet, maar je hebt een lijst met aanwijzingen (vergelijkingen). Het Kaczmarz-algoritme is als een wandelaar die bij elke stap één willekeurige aanwijzing kiest, richting de plek loopt die aan die aanwijzing voldoet, en dan weer een andere willekeurige aanwijzing kiest. Na verloop van tijd komt de wandelaar steeds dichter bij de schat.
Het Mysterie: De wandelaar vindt uiteindelijk de schat, maar wiskundigen discussieerden over de snelheid. Zou de wandelaar heel lang in cirkels kunnen blijven dwalen? Of is er een gegarandeerde snelheidslimiet?
De Menselijke Onderzoekers: Twee wetenschappers (Michał en Xiaoyu) probeerden dit op te lossen met de ouderwetse menselijke wiskunde. Ze kwamen dichtbij, maar liepen tegen een muur op. Ze realiseerden zich dat ze een nieuw perspectief nodig hadden.
Het AI-team: De onderzoekers wenden zich tot AI. Ze vroegen de AI niet simpelweg om "het op te lossen". In plaats daarvan traden ze op als dirigenten, waarbij ze de AI-modellen met elkaar lieten communiceren.

Het "Aha!"-moment: Een estafette van ideeën

De oplossing kwam niet voort uit één AI die alleen werkte. Het gebeurde als een estafette waarbij het stokje werd doorgegeven tussen twee verschillende hardlopers:

Gemini's Inzicht (De Functioneel Analist): Wanneer Gemini werd gevraagd het probleem op te lossen, gaf het niet een volledig bewijs. In plaats daarvan maakte het een vreemde, briljante connectie. Het keek naar het wiskundige probleem en zei: "Dit gaat niet alleen over vergelijkingen; het lijkt op een concept uit een tak van de wiskunde genaamd functionele analyse (specifiek iets als 'kwantum-Markov-semigroepen')."
- Analogie: Stel je een monteur voor die probeert een kapotte motor te repareren. In plaats van naar de tandwielen te kijken, zei Gemini: "Deze motor draait eigenlijk op dezelfde natuurkundige principes als een kernreactor." Het was een vreemde, hoogwaardige connectie die de menselijke onderzoekers niet eerder hadden gezien.
- De Addertjes onder het gras: Gemini kreeg de connectie goed, maar kon het niet bewijzen. Het citeerde enkele wiskundige papers die de bewijsvoering die het nodig had, eigenlijk niet bevatten. Het was alsoast wijzen naar een bibliotheekboek en zeggen: "Het antwoord staat daarin," terwijl het boek eigenlijk leeg was.
ChatGPT's Bewijs (De Elementaire Oplosser): De menselijke onderzoekers namen de "vreemde connectie" van Gemini en gaven deze aan ChatGPT. Ze vroegen: "Oké, als deze connectie waar is, kun je het dan bewijzen met basiswiskunde?"
- ChatGPT bekeek het probleem en zei: "Dat kan ik." Het gebruikte niet de complexe, verwarrende jargon die Gemini noemde. In plaats daarvan gebruikte het een slimme, elementaire truc met behulp van complexe getallen (een type wiskunde dat meestal gereserveerd is voor geavanceerde natuurkunde en techniek) om de snelheidslimiet te bewijzen.
- Analogie: Als Gemini de persoon was die naar een verre berg wees en zei: "De schat ligt onder die top," dan was ChatGPT degene die de berg daadwerkelijk beklom, het gat groef en het goud vond.

Het Resultaat: De "Laatste Stap" is Snel

Het paper bewijst een specifiek ding: Het Kaczmarz-algoritme is zo snel als we hoopten.

In de wereld van deze algoritmen zijn er twee manieren om het antwoord te controleren:

Het Gemiddelde: Je neemt alle stappen die de wandelaar heeft genomen, middelt ze uit, en dat geeft een goed antwoord. (We wisten al dat dit snel was).
De Laatste Stap: Je kijkt gewoon waar de wandelaar aan het einde is gestopt. (Dit was het mysterie).

Het paper bewijst dat de laatste stap net zo snel is als het gemiddelde. De wandelaar hoeft aan het einde niet rond te dwalen om te "landen". De uiteindelijke positie is al een perfecte oplossing.

Waarom dit ertoe doet (volgens het paper)

Het is een Cirkel die Rond is: De oudst bekende versie van het algoritme dat moderne AI traint (SGD), werd opgelost door moderne AI.
Het is een Nieuwe Manier van Onderzoek: Het paper gaat niet alleen over wiskunde; het is een casestudy over hoe mensen en AI samen kunnen werken. De mensen schreven het bewijs niet; de AI deed dat. De mensen faciliteerden slechts het gesprek tussen twee verschillende AI's.
Het Lost een Groter Probleem Op: Door dit specifieke puzzeltje op te lossen, hebben ze ook een bredere, langdurige vraag beantwoord over hoe snel AI-trainingsalgoritmen in het algemeen werken.

De Kernboodschap

Dit paper is het verhaal van een 90 jaar oud wiskundig probleem dat te koppig was voor mensen om alleen te kraken. Door twee verschillende AI-modellen te laten samenwerken — de een om een vreemde, hoogwaardige connectie te vinden, en de ander om het eigenlijke bewijs te bouwen — is het mysterie eindelijk opgelost. Het resultaat bevestigt dat de "laatste stap" van dit klassieke algoritme perfect efficiënt is, en het geeft ons een glimp van hoe toekomstig wetenschappelijk onderzoek eruit kan zien: een partnerschap waarbij mensen de AI sturen, en de AI het zware werk doet.

Technische Samenvatting: Het oplossen van de complexiteit van het oudste SGD-algoritme

Probleemstelling
Het artikel behandelt een langlopend open probleem met betrekking tot de worst-case computationele complexiteit van het Kaczmarz-algoritme, voorgesteld door Stefan Kaczarski in 1937. Dit algoritme is de vroegste bekende instantie van Stochastic Gradient Descent (SGD), een paradigma dat fundamenteel is voor het trainen van moderne Large Language Models (LLM's). Het Kaczmarz-algoritme lost een stelsel van lineaire vergelijkingen $Ax = b$ op door iteratief de huidige schatting te projecteren op een willekeurig geselecteerde vergelijking.

Hoewel de convergentie van de gemiddelde iteratie van de gerandomiseerde Kaczmarz bekend was als $O(1/\epsilon)$ (onafhankelijk van de conditiegetal van de matrix), bleef de convergentiesnelheid van de laatste iteratie (de standaard output in de praktijk) onopgelost. Eerdere pogingen door zowel toegepaste wiskundigen als informatici leverden slechts gedeeltelijke resultaten of suboptimale grenzen op (bijv. $O(1/\epsilon^{1/\alpha})$ met $\alpha < 1$ ). De centrale vraag is of de laatste iteratie van het gerandomiseerde Kaczmarz-algoritme de optimale $O(1/\epsilon)$ convergentiesnelheid bereikt, die overeenkomt met de prestaties van de gemiddelde iteratie en de theoretische ondergrenzen voor ruisloze kleinste kwadraten regressie.

Methodologie: AI-gestuurd onderzoek
Het artikel presenteert een innovatieve casestudy van "AI-gestuurd onderzoek", waarbij menselijke onderzoekers een samenwerking faciliteren tussen twee AI-modellen, Gemini Deep Think en ChatGPT Pro, om een wiskundig bewijs af te leiden. De methodologie volgde een specifiek traject:

Initiële Mens-AI-interactie: De auteurs gebruikten eerst menselijke redenering om het probleem te reduceren tot een discrete ongelijkheid, die zij vervolgens aan ChatGPT toewezen om op te lossen. Dit leverde een suboptimale grens op ( $\alpha = 3/4$ ).
Autonome pogingen: De auteurs promptten beide modellen om het probleem autonoom op te lossen. ChatGPT identificeerde het probleem correct als een open vraag, terwijl Gemini beweerde een bevestigende oplossing te hebben, maar faalde in het leveren van een rigoureus bewijs door te verwijzen naar niet-bestaande stellingen en incorrecte referenties.
Synthese en verificatie: Ondanks de gebreken in het bewijs van Gemini, identificeerde het model een cruciale verbinding met de functionele analyse, specifiek de theorie van symmetrische kwantum Markov-semigroepen en Ritt-operatoren. De auteurs synthetiseerden de inzichten van Gemini tot een formele conjectuur over een operatorbegrens.
Definitieve afleiding: Deze conjectuur werd aan ChatGPT gepresenteerd, dat er vervolgens in slaagde een elementair bewijs af te leiden met behulp van technieken uit de complexe analyse (specifiek de Cauchy-schatting voor afgeleiden van analytische functies) en de operatortheorie, waarmee de openstaande vraag werd opgelost.

Belangrijkste bijdragen en resultaten
De primaire bijdrage is het bewijs dat de laatste iteratie van het gerandomiseerde Kaczmarz-algoritme de optimale convergentiesnelheid bereikt.

Hoofdstelling (Stelling 3.1): De auteurs stellen een algemene grens vast voor een lineaire operator $\Phi(X) = \mathbb{E}[BXB]$ , waarbij $B$ een willekeurige positieve contractie is. Zij bewijzen dat de operatornorm van het verschil tussen de composities $T$ en $T+1$ voldoet aan:
$\|\Phi^T - \Phi^{T+1}\|_{op \to op} \leq \frac{3}{T+1}$
Toepassing op Kaczmarz (Corollary 3.2): Door de Kaczmarz-update naar dit operatorkader te mappen, bewijst het artikel dat voor een matrix $A$ en vector $b$ , de verwachte kwadratische fout van de laatste iteratie $x^{(T)}$ voldoet aan:
$\mathbb{E} \|A(x^{(T)} - x^*)\|^2 \leq \frac{C}{T} \|A\|_F^2 \|x^*\|^2$
Dit bevestigt de $O(1/\epsilon)$ convergentiesnelheid voor de laatste iteratie, waarmee de vraag gesteld in eerdere literatuur [39, 6] wordt beslecht.
Breder bereik (Corollary 3.3): Het resultaat strekt zich uit tot de last-iterate analyse van SGD voor ruisloze kleinste kwadraten regressie, waarmee een langlopende open vraag over de convergentiedynamiek van SGD in contexten van LLM-training wordt opgelost [8, 41].

Betekenis en claims
Het artikel claimt significant te zijn op twee fronten:

Wiskundige resolutie: Het lost een fundamenteel open probleem in de stochastische optimalisatie op dat decennialang onopgelost bleef, waarbij de kloof wordt overbrugd tussen theoretische analyse (die vaak steunt op middeling) en praktische toepassing (die de laatste iteratie gebruikt). Het bewijs maakt gebruik van een afwijkende aanpak die betrokkenheid van functionele analyse en complexe analyse vereist, wat verschilt van eerdere SGD-convergentiebewijzen.
Methodologische casestudy: Het artikel dient als documentatie van een specifieke vorm van mens-AI-samenwerking. De auteurs benadrukken dat hoewel het wiskundige bewijs door AI is gegenereerd, het onderzoeks-proces menselijke facilitatie vereiste om inzichten tussen modellen over te dragen en de geldigheid van de output te verifiëren. Zij stellen dat dit een "middenweg" vertegenwoordigt van AI-gestuurd onderzoek, waarbij AI de primaire drijfveer van de analyse is maar onder menselijk toezicht blijft, wat zowel de huidige capaciteiten als de beperkingen van autonome AI in wiskundige ontdekking belicht.

De auteurs blijven bescheiden over de nieuwheid van het resultaat zelf, waarbij zij opmerken dat, gezien de elementaire aard van het argument, menselijke onderzoekers het probleem waarschijnlijk ook met voldoende tijd en inspanning hadden kunnen oplossen. Zij stellen echter dat het specifieke pad dat is genomen — het inzetten van AI om uiteenlopende wiskundige velden (SGD en functionele analyse) te overbruggen — een nieuw potentieel voor wetenschappelijke ontdekking aantoont.