Quanto può essere lungo il percorso di un flusso gradiente su una funzione convessa, dato il vincolo che rimanga all'interno della palla euclidea unitaria in dimensione n?
^ questa è la domanda che uso da 2 anni per testare il progresso dell'IA. È terribilmente semplice da enunciare, eppure diavolosamente difficile da risolvere. In 168 minuti di riflessione, GPT-5.6 è riuscito a battere in modo molto significativo lo stato dell'arte pubblicato su questa domanda, in un modo che nessun altro modello era finora riuscito a fare. Ma mi sto facendo prendere la mano, ragioniamo prima un po' sulla domanda, rivediamo la letteratura, e poi discutiamo come è stato il progresso da o3 a gpt-5.6.
1. STATO DELL'ARTE
Ingenuamente si potrebbe dire: "beh, la discesa del gradiente ha un tasso di convergenza che è indipendente dalla dimensione — motivo per cui è entusiasmante usarla per problemi con molti parametri! — quindi probabilmente la lunghezza di un tale flusso dovrebbe essere anch'essa indipendente dalla dimensione?". Beh, a volte le impressioni ingenue possono essere totalmente sbagliate. Per cominciare: tali curve sono anche solo rettificabili (cioè di lunghezza finita, senza considerare la dipendenza dalla dimensione)??? Anche questo non è facile da dimostrare, e in realtà è FALSO per la discesa del gradiente accelerata di Nesterov (vedi questo articolo di @ErnestRyu, tutto fatto con gpt-5.5).
Okay, quindi cosa si sa esattamente su questa domanda? Beh, c'è un bellissimo articolo del 1991 di Manselli e Pucci che mostra che tali curve sono effettivamente rettificabili, e inoltre la loro lunghezza è al massimo n^O(n). Sì, avete letto bene, persino peggio che esponenziale nella dimensione, questo è il miglior limite di 35 anni fa!! A proposito, questo articolo sottolinea anche che tali curve sono ciò che viene chiamato "auto-contratte", cioè si avvicinano sempre al loro futuro (prendete un punto qualsiasi sulla curva al tempo t, allora dist(x(s), x(t)) è non crescente per s<t; vedi illustrazione sotto).
Ora, per quanto riguarda i limiti inferiori, cioè costruire una curva auto-contratta effettivamente lunga? Un esempio standard dalla letteratura sull'ottimizzazione convessa sarebbe una quadratica mal condizionata, qualcosa come x_1^2 + cost_grande\x_2^2 + cost_ancora_più_grande\x_3^2 + ... Il punto è che la discesa del gradiente andrà prima quasi diritta lungo la direzione con la costante più grande, poi nella direzione con la seconda costante più grande, e così via (vedi illustrazione sotto). Quindi la lunghezza totale del percorso sarà all'incirca n, e il percorso è contenuto nell'ipercubo che è contenuto in una palla di raggio sqrt(n), quindi riscalando otteniamo una curva auto-contratta di lunghezza sqrt(n).
Questo è tutto. Questo è lo stato dell'arte pubblicato: limite superiore di n^O(n) e limite inferiore di sqrt(n). Un bel divario per una domanda così semplice e naturale!!!
Definizione di una curva auto-contratta
Una curva auto-contratta di lunghezza sqrt(n)
2. Lavoro non pubblicato da esseri umani
Ho pensato a questa domanda 8 anni fa con fantastici collaboratori Omer Angel, Tomas Merchan Rodriguez e Fedja Nazarov. Siamo riusciti a fare progressi considerevoli e abbiamo stabilito che la risposta è effettivamente esponenziale nella dimensione!! Nello specifico, avevamo un limite inferiore di sqrt(2)^n e un limite superiore di 4^n. L'articolo con queste stime è scritto in modo ordinato e giace nella mia cartella Dropbox da quasi un decennio, in parte perché sapevamo che questi limiti potevano essere ulteriormente migliorati. E infatti Tomas e Fedja hanno fatto ulteriori progressi, prima portando il limite inferiore a 2^n e poi migliorando anche il limite superiore a 2.29...^n. Nota che la mia personale comprensione del problema è rimasta al limite inferiore leggermente-migliore-di-sqrt(2)^n e al limite superiore 4^n (infatti, avevo dimenticato il 2^n e il 2.29^n finché l'IA non ha iniziato a fare progressi su questo... più sotto).
3. Progresso dell'IA
o3 è stato il primo modello di IA a comprendere anche solo la domanda. Sì, avete letto bene quella frase. Forse ve ne siete dimenticati, ma due anni fa non era nemmeno chiaro che un'IA potesse CAPIRE domande così ingannevolmente semplici, figuriamoci risolverle. In particolare, o3 riusciva a vedere che la domanda riguardava in realtà le curve auto-contratte, e sapeva qual era lo stato dell'arte su questa domanda. Rimasi davvero molto molto colpito all'epoca.
Ma poi le cose si sono complicate, e con l'arrivo della serie di modelli GPT-5 ho usato questa domanda come monito: fino a febbraio di quest'anno, nei miei interventi sui progressi delle LLM in matematica, portavo questa domanda come esempio di una domanda che NON dovreste fare alle LLM. Il motivo è che GPT-5 o anche GPT-5.2/5.4 PROVAVANO a dare risposte complicate, ma erano invariabilmente errate da qualche parte, e si perdeva un sacco di tempo a verificarle. Quindi era un buon esempio del fatto che, per non perdere tempo con le LLM in matematica, bisogna sapere quale sia il giusto livello di domanda da porre.
Questo è cambiato con GPT-5.5, e improvvisamente, con molti scambi e un prompting esperto, Mark Sellke è riuscito a riscoprire la costruzione del limite inferiore 2^n (cosa che mi ha SBAORDITO, in parte perché avevo dimenticato che Tomer e Fedja già la conoscevano 😅). D'altra parte, nessun successo per quanto riguarda il limite superiore.
E ora arriva GPT-5.6, e il progresso dell'IA diventa pienamente visibile:
- GPT-5.6-pro RISOLVE AL PRIMO TENTATIVO il limite inferiore 2^n. Potete vedere il tentativo unico qui (80 minuti di riflessione): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
- GPT-5.6-pro RISOLVE AL PRIMO TENTATIVO il limite superiore 4^n, e in realtà lo fa molto rapidamente nella sua catena di pensiero, e alla fine della sua riflessione produce un limite superiore di 2.31...^n. Non raggiunge esattamente il 2.29...^n di Fedja (e in realtà la strategia del 2.31...^n non può essere migliorata ulteriormente senza nuove idee — infatti lo stesso Fedja lo notò in un post su MathOverflow nel 2018: "[per 2.31..] l'argomento diventa un po' complesso ed è chiaro che questa strada non porterà alla stima ottimale"). Ma comunque è piuttosto dannatamente impressionante e va oltre ciò che io stesso avevo personalmente capito del problema quando ci lavoravo seriamente. Potete vedere il tentativo unico qui, fatto in 88 minuti di riflessione: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64
3. Una sfida per il futuro
Questa storia vede ancora gli umani come vincitori. 2.29 per gli umani contro 2.31 per le macchine. Naturalmente, la congettura è che le curve auto-contratte non possano essere più lunghe di 2^n (che sarebbe quindi la risposta ottimale dato il limite inferiore di 2^n). Questo sembra molto difficile da dimostrare e al di là delle capacità di GPT-5.6. Per quanto tempo potrò ancora usare questa domanda per tracciare il progresso dell'IA? Sospetto che possa essere meno di 6 mesi...
P.S.: Ho copiato e incollato il post qui sopra in ChatGPT lavoro e gli ho chiesto di produrre illustrazioni a corredo. La raccolta di immagini qui è stata ottenuta al primo tentativo da quella richiesta.
