Stochastic Adaptive Gradient Descent Without Descent

Enunciato del Problema
Il documento affronta il problema dell'ottimizzazione convessa stocastica:
$$\min_{x \in \mathbb{R}^d} f(x) = \min_{x \in \mathbb{R}^d} \mathbb{E}[f_\xi(x)]$$
dove $f$ è una funzione convessa, differenziabile e limitata inferiormente. L'obiettivo è trovare un minimizzatore $x^\star$ utilizzando un oracolo del gradiente stocastico $\nabla f_{\xi_k}$ senza richiedere la calibrazione accurata degli iper-parametri, specificamente del passo iniziale $\lambda_0$. Mentre lo Stochastic Gradient Descent (SGD) standard richiede la calibrazione di $\lambda_0$ per bilanciare velocità di convergenza e stabilità, e i metodi adattivi esistenti (come quelli di Malitsky e Mishchenko [2020]) spesso mantengono una dipendenza da un parametro $\alpha$ calibrabile nell'ambito stocastico, questo lavoro cerca un approccio "tuning-free" (senza calibrazione) che si adatti alla geometria locale della funzione obiettivo utilizzando solo chiamate all'oracolo del primo ordine.

Metodologia
Gli autori propongono AdaSGD, un adattamento stocastico del metodo "Adaptive Gradient Descent Without Descent" (AdaGD). L'innovazione principale risiede nella regola di aggiornamento del passo, che evita il parametro $\alpha$ richiesto dalle precedenti adattazioni stocastiche.

L'algoritmo segue la ricorsione stocastica standard $x_{k+1} = x_k - \lambda_k \nabla f_{\xi_k}(x_k)$. Il passo $\lambda_k$ viene aggiornato sulla base della geometria locale della funzione. Una distinzione chiave rispetto all'AdaGD deterministico e ai precedenti tentativi stocastici è l'evaluazione della differenza del gradiente. Invece di utilizzare l'attuale batch $\xi_k$ per entrambi i punti (il che introdurrebbe un bias o richiederebbe un secondo batch indipendente $\zeta_k$), il metodo valuta la differenza del gradiente utilizzando la variabile casuale precedente $\xi_{k-1}$:
$$\hat{L}_{k-1} = \frac{\|\nabla f_{\xi_{k-1}}(x_k) - \nabla f_{\xi_{k-1}}(x_{k-1})\|}{\|x_k - x_{k-1}\|}$$
Ciò consente che il passo sia definito senza un parametro di scala esterno. Il documento propone tre varianti (V-I, V-II, V-III) per $k \ge 2$:
$$\lambda_k = \min \left( \frac{c_k}{2\sqrt{2}\hat{L}_{k-1}}, \frac{\lambda_{k-1}}{\sqrt{1 + \theta_{k-1}}} \right)$$
dove $\theta_{k-1} = \lambda_{k-1}/\lambda_{k-2}$ e $c_k$ è un fattore di decadimento (specificamente $c_k = 1$ per V-I, e $c_k = k^{1/2+\delta}$ per V-II e V-III con $0 < \delta < 1/2$). La variante V-III è raccomandata in quanto fornisce le più forti garanzie teoriche.

Analisi Teorica
L'analisi della convergenza si basa sulla costruzione di una sequenza di Lyapunov $(T_k)$, ispirata a Malitsky e Mishchenko [2020] ma adattata per l'ambito stocastico. La sequenza è definita come:
$$T_k = \|x_{k+1} - x^\star\|^2 + 2(\lambda_k(1+\theta_k))(f(x_k) - f^\star) + \frac{\|x_{k+1} - x_k\|^2}{2}$$
Gli autori dimostrano che, sotto specifiche assunzioni (struttura finite-sum con gradienti Lipschitziani, o iterati limitati), la sequenza $(T_k)$ converge quasi certamente.

• Convergenza Quasi Sicura (Almost Sure Convergence): Il Teorema 3.2 stabilisce che se i passi sono sommabili al quadrato ($\sum \lambda_k^2 < \infty$), la sequenza di Lyapunov converge. Questa condizione è dimostrata essere valida in casi di forte convessità, regressione lineare e somme di funzioni ridge.
• Tassi di Convergenza: Per funzioni fortemente convesse (Caso-1), il Teorema 3.4 deriva un tasso di convergenza di $O(1/k^{1/2+\delta})$ per l'errore atteso. Fondamentalmente, i fattori esponenziali che governano il comportamento transitorio dipendono dal rapporto $L^2/\mu^2$ (dove $L$ è la costante di smoothness e $\mu$ è il parametro di forte convessità) piuttosto che dal passo iniziale $\lambda_0$. Ciò contrasta con il vanilla SGD, dove il passo iniziale può causare una crescita esponenziale del limite dell'errore prima della convergenza.

Contributi Chiave

1. Adattamento Stocastico Tuning-Free: Il documento introduce una strategia del passo stocastico che elimina la necessità di calibrare il parametro $\alpha$ (o $\lambda_0$) richiesto nella versione stocastica di AdaGD di Malitsky e Mishchenko [2020].
2. Garanzie Teoriche: Gli autori forniscono dimostrazioni rigorose di convergenza e tassi sotto assunzioni standard (forte convessità, gradienti Lipschitziani) senza richiedere la conoscenza globale di $L$ o $\mu$.
3. Robustezza all'Inizializzazione: Il metodo è progettato in modo che la scelta di un passo iniziale piccolo sia sempre sicura, evitando i problemi di sensibilità comuni in altri metodi adattivi.

Risultati Sperimentali
Esperimenti numerici sono stati condotti su sei problemi di ottimizzazione convessa stocastica (regressione lineare/ridge/logistica/Poisson) utilizzando dati sintetici e reali (Diabetes, 2moons, w8a).

• Sensibilità a $\lambda_0$: I risultati dimostrano che AdaSGD è significativamente meno sensibile alla scelta del passo iniziale $\lambda_0$ rispetto a vanilla SGD, decaying SGD, Adagrad e lo stochastic AdaGD-MM. Mentre altri metodi richiedono una ricerca densa su griglia per trovare un $\lambda_0$ ottimale, AdaSGD performa costantemente bene con un valore iniziale fisso e piccolo (ad esempio, $\lambda_0 = 10^{-3}$).
• Performance: In termini di performance di minimizzazione (gap di ottimalità), AdaSGD (specificamente le varianti V-II e V-III) raggiunge risultati comparabili a quelli dei baseline ottimamente calibrati. Gli autori osservano che, mentre V-I a volte fatica con oscillazioni dovute al rumore, il decadimento introdotto in V-II e V-III stabilizza il metodo.
• Costo: Il metodo richiede una valutazione aggiuntiva del gradiente stocastico per iterazione (per calcolare $\nabla f_{\xi_{k-1}}(x_k)$), ma gli autori sostengono che questo costo sia compensato dall'eliminazione della ricerca su griglia necessaria per la calibrazione degli iper-parametri.

Significatività e Rivendicazioni
Il documento sostiene che AdaSGD trasferisce con successo i benefici dell' "Adaptive Gradient Descent Without Descent" deterministico all'ambito stocastico, una transizione che tentativi precedenti non sono riusciti a compiere senza reintrodurre la calibrazione degli iper-parametri. Il contributo primario è un metodo che è "tuning-free" nella pratica: permette ai professionisti di utilizzare un passo iniziale fisso e piccolo senza sacrificare i tassi di convergenza o la stabilità. Gli autori sottolineano che, sebbene il metodo non sia strettamente "parameter-free" (poiché dipende dal valore iniziale $\lambda_0$ per il valore iniziale della funzione di Lyapunov), la dipendenza è sufficientemente debole da rendere l'uso di piccoli valori universalmente efficace, rendendo il metodo robusto e pratico per l'ottimizzazione stocastica senza la necessità di un'estesa ricerca di iper-parametri. Il lavoro rimane focalizzato sui contesti convessi, con estensioni non convesse segnalate come una sfida significativa futura a causa della dipendenza dalle disuguaglianze di convessità nella derivazione.