Il passo di Polyak: perché funziona così bene su ogni tipo di funzione?

Il passo di Polyak è una strategia di apprendimento per il gradiente discendente che risale al 1969. A differenza dei passi fissi, qui la dimensione del passo si adatta in base alla differenza tra il valore corrente della funzione e il valore ottimale stimato. Recenti risultati dimostrano che questa semplice idea è incredibilmente potente.

Gli autori hanno costruito esempi di funzioni “peggiori” per mostrare che i tassi di convergenza noti sono esatti: per funzioni fortemente convesse lisce, il gradiente scende con un fattore \(1-1/\kappa\) ad ogni iterazione, mentre per le convesse lisce il miglioramento è dell'ordine \(1/K\). Non c'è margine di miglioramento in generale.

Ma c'è una sorpresa: gli errori di arrotondamento dei calcolatori, di solito considerati fastidi, vengono sfruttati dal passo di Polyak per “sfuggire” a questi scenari peggiori. In pratica, il rumore numerico aiuta l'algoritmo a trovare percorsi più rapidi.

Inoltre, il nuovo studio amplia la teoria includendo condizioni di lisciità e crescita di tipo Hölder. Questo significa che il passo di Polyak si adatta automaticamente a funzioni non solo lisce o fortemente convesse, ma anche a quelle con curvature più morbide, senza conoscere in anticipo parametri come la costante di condizione. In sintesi, il passo di Polyak è universale: si regola da solo, garantendo convergenza rapida in una vasta gamma di problemi di ottimizzazione.

Il passo di Polyak, formalmente definito come \(\alpha_k = \frac{f(x_k)-f^*}{\|\nabla f(x_k)\|^2}\), richiede una stima del valore ottimale \(f^*\). In pratica, si usa una lower bound o una stima iterativa. La dimostrazione di tightness parte dalla costruzione di funzioni quadratriche con matrice di Hessiana \(Q\) avente autovalori \(\lambda_{\min}=\mu\) e \(\lambda_{\max}=L\), dove \(\kappa=L/\mu\). Si mostra che, per tali funzioni, l'iterato \(x_{k+1}=x_k-\alpha_k\nabla f(x_k)\) produce esattamente il fattore di contrazione \(1-1/\kappa\). Per le convesse lisce, si utilizza una famiglia di funzioni \(f_t(x)=\frac{1}{t}\|x\|^t\) con \(t\in(1,2]\) per dimostrare il limite \(O(1/K)\).

L'analisi degli errori di floating‑point si basa sul modello di arrotondamento di IEEE‑754: \(fl(a\cdot b)=a\cdot b(1+\delta)\) con \(|\delta|\leq\epsilon_{mach}\). Inserendo questi termini nella ricorsione del passo di Polyak, si ottiene un termine di rumore che, in media, aggiunge una componente positiva al decremento della funzione, rompendo la sequenza peggiore.

Le condizioni Hölder introducono esponenti \(\nu\in(0,1]\) per la lisciità (\(\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|^{\nu}\)) e \(\theta\in(0,1]\) per la crescita (\(f(x)-f^*\ge c\|x-x^*\|^{\theta}\)). Con queste ipotesi, la scelta di \(\alpha_k\) resta invariata, ma la dimostrazione della convergenza utilizza disuguaglianze di Young e la proprietà di autovalutazione per ottenere tassi \(O(k^{-\nu/\theta})\). Questo mostra che il passo di Polyak è intrinsecamente adattivo, senza richiedere la conoscenza preventiva di \(L,\mu,\nu,\theta\).