Rischiosi passi da gigante possono risolvere i problemi di ottimizzazione più velocemente | Rivista Quanta

I problemi di ottimizzazione possono essere complicati, ma fanno funzionare meglio il mondo. Questo tipo di domande, che mirano al modo migliore di fare qualcosa, sono assolutamente ovunque. Il GPS del telefono calcola il percorso più breve per raggiungere la destinazione. I siti web di viaggi cercano la combinazione di voli più economica che corrisponde al tuo itinerario. E le applicazioni di apprendimento automatico, che apprendono analizzando i modelli nei dati, cercano di presentare le risposte più accurate e simili a quelle umane a qualsiasi domanda.

Per semplici problemi di ottimizzazione, trovare la soluzione migliore è solo una questione di aritmetica. Ma le domande del mondo reale che interessano matematici e scienziati sono raramente semplici. Nel 1847, il matematico francese Augustin-Louis Cauchy stava lavorando a un esempio adeguatamente complicato - calcoli astronomici - quando fu il pioniere di un metodo comune di ottimizzazione ora noto come discesa del gradiente. La maggior parte dei programmi di apprendimento automatico oggi fa molto affidamento sulla tecnica e anche altri campi la utilizzano per analizzare i dati e risolvere problemi di ingegneria.

I matematici perfezionano la discesa del gradiente da oltre 150 anni, ma il mese scorso, uno studio dimostrato che un presupposto di base sulla tecnica potrebbe essere sbagliato. "Ci sono state solo diverse volte in cui sono rimasto sorpreso, [come] la mia intuizione è rotta", ha detto Ben Grimmer, matematico applicato alla Johns Hopkins University e unico autore dello studio. I suoi risultati controintuitivi hanno mostrato che la discesa del gradiente può funzionare quasi tre volte più velocemente se infrange una regola accettata da tempo su come trovare la risposta migliore per una determinata domanda. Sebbene il progresso teorico probabilmente non si applichi ai problemi più nodosi affrontati dall'apprendimento automatico, ha indotto i ricercatori a riconsiderare ciò che sanno sulla tecnica.

"Si scopre che non avevamo una piena comprensione" della teoria alla base della discesa del gradiente, ha detto Shuvomoy Das Gupta, un ricercatore di ottimizzazione presso il Massachusetts Institute of Technology. Ora, ha detto, siamo "più vicini a capire cosa sta facendo la discesa del gradiente".

La tecnica stessa è ingannevolmente semplice. Usa qualcosa chiamato funzione di costo, che sembra una linea liscia e curva che serpeggia su e giù attraverso un grafico. Per qualsiasi punto su quella linea, l'altezza rappresenta in qualche modo il costo: quanto tempo, energia o errore incorrerà nell'operazione se sintonizzata su un'impostazione specifica. Più alto è il punto, più lontano dall'ideale è il sistema. Naturalmente, vuoi trovare il punto più basso su questa linea, dove il costo è minimo.

Gli algoritmi di discesa del gradiente si fanno strada verso il basso selezionando un punto e calcolando la pendenza (o il gradiente) della curva attorno ad esso, quindi spostandosi nella direzione in cui la pendenza è più ripida. Immagina di sentirti giù da una montagna nell'oscurità. Potresti non sapere esattamente dove spostarti, per quanto tempo dovrai camminare o quanto vicino al livello del mare ti avvicinerai alla fine, ma se percorri la discesa più ripida, alla fine dovresti arrivare al punto più basso della zona.

A differenza del metaforico alpinista, i ricercatori di ottimizzazione possono programmare i loro algoritmi di discesa del gradiente per eseguire passi di qualsiasi dimensione. I passi da gigante sono allettanti ma anche rischiosi, in quanto potrebbero superare la risposta. Invece, la saggezza convenzionale del settore per decenni è stata quella di fare piccoli passi. Nelle equazioni di discesa del gradiente, ciò significa una dimensione del passo non maggiore di 2, sebbene nessuno possa dimostrare che le dimensioni del passo più piccole siano sempre migliori.

Con i progressi nelle tecniche di dimostrazione assistita da computer, i teorici dell'ottimizzazione hanno iniziato a testare tecniche più estreme. In uno studio, prima postato in 2022 e recentemente pubblicato in Programmazione matematica, Das Gupta e altri hanno incaricato un computer di trovare le migliori lunghezze di passo per un algoritmo limitato all'esecuzione di soli 50 passi, una sorta di problema di meta-ottimizzazione, poiché stava cercando di ottimizzare l'ottimizzazione. Hanno scoperto che i 50 passi ottimali variavano significativamente in lunghezza, con un passo nel mezzo della sequenza che raggiungeva quasi la lunghezza 37, molto al di sopra del limite tipico di lunghezza 2.

I risultati hanno suggerito che i ricercatori di ottimizzazione si erano persi qualcosa. Incuriosito, Grimmer cercò di trasformare i risultati numerici di Das Gupta in un teorema più generale. Per superare un limite arbitrario di 50 passi, Grimmer ha esplorato quali sarebbero le lunghezze di passo ottimali per una sequenza che potrebbe ripetersi, avvicinandosi alla risposta ottimale a ogni ripetizione. Fece scorrere il computer attraverso milioni di permutazioni di sequenze di lunghezza del passo, aiutando a trovare quelle che convergevano più velocemente sulla risposta.

Grimmer ha scoperto che le sequenze più veloci avevano sempre una cosa in comune: il passo intermedio era sempre importante. La sua dimensione dipendeva dal numero di passaggi nella sequenza ripetuta. Per una sequenza di tre passi, il grande passo aveva una lunghezza di 4.9. Per una sequenza di 15 passaggi, l'algoritmo consigliava un passaggio di lunghezza 29.7. E per una sequenza di 127 passi, la più lunga testata, il grande salto centrale è stato un enorme 370. All'inizio sembra un numero assurdamente grande, ha detto Grimmer, ma c'erano abbastanza passi totali per compensare quel salto gigante, quindi anche se hai superato il fondo, potresti comunque tornare indietro velocemente. Il suo articolo ha mostrato che questa sequenza può arrivare al punto ottimale quasi tre volte più velocemente di quanto farebbe facendo piccoli passi costanti. "A volte, dovresti davvero impegnarti troppo", ha detto.

Questo approccio ciclico rappresenta un modo diverso di pensare alla discesa del gradiente, ha detto Aymeric Dieuleveut, ricercatore di ottimizzazione presso l'École Polytechnique di Palaiseau, in Francia. "Questa intuizione, che dovrei pensare non passo dopo passo, ma come una serie di passaggi consecutivamente, penso che questo sia qualcosa che molte persone ignorano", ha detto. "Non è il modo in cui viene insegnato." (Grimmer osserva che anche questa ristrutturazione è stata proposto per una classe di problemi simile in una tesi di master del 2018 di Jason Altschuler, un ricercatore di ottimizzazione ora all'Università della Pennsylvania.)

Tuttavia, sebbene queste intuizioni possano cambiare il modo in cui i ricercatori pensano alla discesa del gradiente, probabilmente non cambieranno il modo in cui la tecnica è attualmente utilizzata. L'articolo di Grimmer si è concentrato solo sulle funzioni lisce, che non hanno nodi taglienti, e sulle funzioni convesse, che hanno la forma di una ciotola e hanno un solo valore ottimale nella parte inferiore. Questi tipi di funzioni sono fondamentali per la teoria ma meno rilevanti nella pratica; i programmi di ottimizzazione utilizzati dai ricercatori di machine learning sono solitamente molto più complicati. Questi richiedono versioni di discesa del gradiente che hanno "così tante campane e fischietti e così tante sfumature", ha detto Grimmer.

Alcune di queste tecniche truccate possono andare più veloci dell'approccio a grandi passi di Grimmer, ha detto Gauthier Gidel, un ricercatore di ottimizzazione e apprendimento automatico presso l'Università di Montreal. Ma queste tecniche hanno un costo operativo aggiuntivo, quindi la speranza era che la regolare discesa del gradiente potesse avere la meglio con la giusta combinazione di dimensioni dei gradini. Sfortunatamente, la triplice accelerazione del nuovo studio non è sufficiente.

"Mostra un miglioramento marginale", ha detto Gidel. "Ma immagino che la vera domanda sia: possiamo davvero colmare questo divario?"

I risultati sollevano anche un ulteriore mistero teorico che ha tenuto sveglio la notte Grimmer. Perché i modelli ideali delle dimensioni dei gradini avevano tutti una forma così simmetrica? Non solo il gradino più grande è sempre al centro, ma lo stesso schema appare su entrambi i lati: continua a ingrandire e suddividere la sequenza, ha detto, e ottieni uno "schema quasi frattale" di gradini più grandi circondati da gradini più piccoli . La ripetizione suggerisce una struttura di fondo che governa le migliori soluzioni che nessuno è ancora riuscito a spiegare. Ma Grimmer, almeno, è fiducioso.

"Se non posso decifrarlo, lo farà qualcun altro", ha detto.