[Deep Learning] Nozioni di base sui modelli grafici (7): Metodo di riduzione della varianza nell'ottimizzazione del machine learning (1)

2024-07-12

Riepilogo

L’ottimizzazione stocastica è una componente vitale dell’apprendimento automatico e al suo centro c’è l’algoritmo di discesa del gradiente stocastico (SGD), un metodo ampiamente utilizzato da quando è stato proposto per la prima volta più di 60 anni fa. Negli ultimi otto anni abbiamo assistito a un nuovo entusiasmante sviluppo: tecniche di riduzione della varianza per metodi di ottimizzazione stocastica. Questi metodi di riduzione della varianza (metodi VR) funzionano bene in scenari che consentono più iterazioni dei dati di addestramento, mostrando una convergenza più rapida rispetto all'SGD, sia in teoria che in pratica. Questo aumento di velocità evidenzia il crescente interesse per i metodi VR e il rapido accumulo di risultati della ricerca in questo settore. Questo articolo esamina i principi chiave e i principali progressi nei metodi VR per l'ottimizzazione di set di dati limitati, con l'obiettivo di informare i lettori non esperti. Ci concentriamo principalmente sugli ambienti di ottimizzazione convessi e forniamo un riferimento per i lettori interessati alle estensioni alla minimizzazione delle funzioni non convesse.

Parole chiave |.Apprendimento automatico;riduzione della varianza

1. Introduzione

Nel campo della ricerca sull’apprendimento automatico, una questione fondamentale e importante è come adattare i modelli a enormi set di dati. Ad esempio, possiamo considerare il caso tipico di un modello lineare dei minimi quadrati:

$x^* in argmin_{x in mathbb{R}^d} frac{1}{n} sum_{i=1}^{n} (a_i^T x - b_i)^2$

In questo modello abbiamo $D$ parametri, rappresentati da vettori $bb{R}^d$ dato.Nel frattempo, abbiamo a portata di mano $N$ punti dati, inclusi i vettori delle caratteristiche $a_i in mathbb{R}^d$ e valore obiettivo $b_i in mathbb{R}$ .Il processo di adattamento del modello consiste nel regolare questi parametri in modo che l'output previsto del modello $a_i^T x$ in media il più vicino possibile al valore target $B_{iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo}$ 。

Più in generale, potremmo utilizzare una funzione di perdita $F_{iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo} (X)$ Per misurare le previsioni del modello e il $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo$ Quanto sono vicini i punti dati:

$x^* in argmin_{x in mathbb{R}^d} f(x) := frac{1}{n} sum_{i=1}^{n} f_i(x)$

funzione di perdita $F_{iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo} (X)$ Se è maggiore, indica che le previsioni del modello si discostano notevolmente dai dati; $F_{iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo} (X)$ Uguale a zero, il modello si adatta perfettamente ai punti dati.funzione $F (X)$ Riflette la perdita media del modello sull'intero set di dati.

Problemi come la forma (2) di cui sopra si applicano non solo ai problemi dei minimi quadrati lineari, ma anche a molti altri modelli studiati nell'apprendimento automatico. Ad esempio, in un modello di regressione logistica risolviamo per:

$x^* in argmin_{x in mathbb{R}^d} frac{1}{n} sum_{i=1}^{n} log(1 + e^{-b_i a_i^T x}) + frac{lambda}{2} |x|_2^2$

Qui abbiamo a che fare $b_i in {-1, +1}$ Per un problema di classificazione binaria, la previsione si basa su $a_i^T x$ simboli.Nella formula è introdotto anche un termine di regolarizzazione $|x|_2^2$ per evitare di adattare eccessivamente i dati, dove $x|_2^2$ esprimere $X$ Il quadrato della norma euclidea di .

Nella maggior parte dei modelli di apprendimento supervisionato, il processo di addestramento può essere espresso come forma (2), inclusi i minimi quadrati regolarizzati L1, la Support Vector Machine (SVM), l'analisi delle componenti principali, i campi casuali condizionali e le reti neurali profonde, ecc.

Una sfida chiave nei casi di problemi moderni è il numero di punti dati $N$ Probabilmente estremamente grande. Spesso abbiamo a che fare con set di dati che vanno ben oltre la portata dei terabyte e possono provenire da fonti diverse come Internet, satelliti, sensori remoti, mercati finanziari ed esperimenti scientifici. Per gestire insiemi di dati così grandi, un approccio comune consiste nell'utilizzare l'algoritmo SGD (stochastic gradient descend), che utilizza solo un piccolo numero di punti dati selezionati casualmente in ciascuna iterazione. Inoltre, recentemente si è verificato un forte aumento dell’interesse per i metodi del gradiente stocastico di riduzione della varianza (VR), che hanno tassi di convergenza più rapidi rispetto ai tradizionali metodi del gradiente stocastico.
Inserisci qui la descrizione dell'immagine
Figura 1. Sul problema della regressione logistica basato sul set di dati dei funghi [7], la discesa del gradiente (GD), la discesa del gradiente accelerata (AGD, GD accelerato in [50]), la discesa del gradiente stocastico (SGD) e il metodo ADAM [30] sono stati rispetto ai metodi di riduzione della varianza (VR) SAG e SVRG, dove n = 8124, d = 112.

1.1. Metodi del gradiente e della discesa stocastica del gradiente

La discesa del gradiente (GD) è un algoritmo classico utilizzato per risolvere il problema di cui sopra (2) e la sua formula di aggiornamento iterativo è la seguente:
$x_{k+1} = x_k - gamma frac{1}{n} sum_{i=1}^{n} nabla f_i(x_k)$

Qui, $γ$ è un valore di passo fisso maggiore di zero.Durante ogni iterazione dell'algoritmo GD, ciascun punto dati deve essere $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo$ Calcola il gradiente $f_i(x_k)$ , il che significa che GD richiede tutto $N$ eseguire un attraversamento completo dei punti dati.Quando la dimensione del set di dati $N$ Quando diventa molto grande, il costo di ogni iterazione dell’algoritmo GD diventa molto alto, limitandone così l’applicazione.

In alternativa, possiamo considerare il metodo della discesa del gradiente stocastico (SGD), proposto per la prima volta da Robbins e Monro, e la sua formula di aggiornamento iterativo è la seguente:
$x_{k+1} = x_k - gamma nabla f_{i_k}(x_k)$

L'algoritmo SGD funziona utilizzando solo il gradiente di un punto dati selezionato casualmente in ciascuna iterazione. $f_{i_k}(x_k)$ per ridurre il costo di ogni iterazione. Nella Figura 1, possiamo vedere che SGD ottiene progressi più significativi rispetto a GD (compresi i metodi GD accelerati) nelle prime fasi del processo di ottimizzazione.Il grafico mostra l'avanzamento dell'ottimizzazione in termini di epoche, definite come il calcolo di tutti $N$ Il numero di gradienti per l'addestramento dei campioni. L'algoritmo GD esegue un'iterazione in ogni round, mentre l'algoritmo SGD esegue un'iterazione in ogni round $N$ iterazioni.Usiamo i round come base per confrontare SGD e GD, perché presupponiamo $N$ In casi molto ampi, il costo principale di entrambi i metodi è concentrato nel gradiente $f_i(x_k)$ calcolo.

1.2. Problema della varianza

Consideriamo l'indicizzazione casuale $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo_{K}$ dalla raccolta ${1, \dots, N}$ Nel caso della selezione casuale uniforme, ciò significa che per tutti $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo$ ,scegliere $i_k = io$ La probabilità $P[i_k = i]$ pari $\frac{1}{N}$ . in questo caso, $f_{i_k}(x_k)$ COME $f(x_k)$ Lo stimatore di è imparziale perché, per la definizione di aspettativa, abbiamo:
$f_{i_k}(x_k) | x_k] = frazione {1} {n} somma_{i=1}^{n} nabla f_i(x_k) = nabla f(x_k) quad (6)$

Sebbene il metodo SGD (Stochastic Gradient Descent) non garantisca il funzionamento in ogni iterazione $F$ Il valore di diminuirà, ma in media si sposta verso il gradiente pieno negativo, che rappresenta la direzione verso il basso.

Tuttavia, disporre di uno stimatore del gradiente imparziale non è sufficiente per garantire la convergenza delle iterazioni SGD. Per illustrare questo punto, la Figura 2 (a sinistra) mostra la traiettoria iterativa di SGD quando si applica una funzione di regressione logistica utilizzando una dimensione del passo costante sul set di dati a quattro categorie fornito da LIBSVM [7].Le ellissi concentriche nella figura rappresentano i contorni della funzione, cioè il valore della funzione $F (X) = C$ punto corrispondente $X$ raccogliere, $C$ è una costante specifica nell'insieme dei numeri reali.valori costanti diversi $C$ Corrisponde a diverse ellissi.

La traiettoria iterativa di SGD non converge alla soluzione ottima (indicata da un asterisco verde in figura), ma forma una nuvola di punti attorno alla soluzione ottima. Al contrario, mostriamo nella Figura 2 la traiettoria iterativa di un metodo di riduzione della varianza (VR), gradiente medio stocastico (SAG), utilizzando la stessa dimensione del passo costante, che introdurremo più avanti. Il motivo per cui SGD non riesce a convergere in questo esempio è che il gradiente stocastico stesso non converge a zero e, pertanto, il metodo SGD a passo costante (5) non si ferma mai.Ciò è in netto contrasto con i metodi di discesa del gradiente (GD), che naturalmente si fermano come $x_k$ Si avvicina $x^*$ ,pendenza $f(x_k)$ tenderà a zero.
Inserisci qui la descrizione dell'immagine
Figura 2. Grafici di set di livelli per la regressione logistica bidimensionale utilizzando metodi iterativi SGD a passo fisso (a sinistra) e SAG (a destra). L'asterisco verde indica xsciogliere.

1.3. Metodo classico di riduzione della varianza

elaborazione dovuta a $f_i(x_k)$ Esistono diverse tecniche classiche per problemi di non convergenza causati dalla varianza dei valori.Ad esempio, Robbins e Monro [64] utilizzano una serie di passi decrescenti $gamma_k$ per risolvere il problema della varianza, garantendo che il prodotto $gamma_k nabla f_{i_k}(x_k)$ può convergere a zero. Tuttavia, regolare questa sequenza di passaggi decrescenti per evitare di fermare l’algoritmo troppo presto o troppo tardi è un problema difficile.

Un'altra tecnica classica per ridurre la varianza è utilizzare multipli $f_i(x_k)$ media per ottenere il gradiente completo $\nabla F (X)$ una stima più accurata. Questo approccio è chiamato minibatch ed è particolarmente utile quando è possibile valutare più gradienti in parallelo. Ciò si traduce in un'iterazione del modulo:
$x_{k+1} = x_k - gamma frac{1}{|B_k|} sum_{i in B_k} nabla f_i(x_k) quad (7)$
In $B_k$ è un insieme di indici casuali, $|B_k|$ esprimere $B_k$ la dimensione di.Se $B_k$ Campionando uniformemente con sostituzione, la varianza di questa stima del gradiente è correlata alla "dimensione del batch" $|B_k|$ è inversamente proporzionale, quindi la varianza può essere ridotta aumentando la dimensione del lotto.

Tuttavia, il costo di tali iterazioni è proporzionale alla dimensione del batch, quindi questa forma di riduzione della varianza comporta un aumento dei costi computazionali.

Un’altra strategia comune per ridurre la varianza e migliorare la performance empirica dell’SGD è aggiungere “slancio”, un termine aggiuntivo basato sulla direzione utilizzata nei passaggi precedenti. In particolare, la forma dell’SGD con momentum è la seguente:
$x_{k+1} = x_k - gamma m_k quad (9)$
dove il parametro della quantità di moto $β$ Situato nell'intervallo (0, 1).Se lo slancio iniziale $m_0 = 0$ , ed espandere in (8) $m_k$ Per gli aggiornamenti, otteniamo $m_k$ è la media ponderata dei gradienti precedenti:
$m_k = sum_{t=0}^{k} beta^{kt} nabla f_{i_t}(x_t) quad (10)$
Perciò, $m_k$ è la somma ponderata dei gradienti stocastici.Perché $somma_{t=0}^{k} beta^{kt} = frazione{1 - beta^{k+1}}{1 - beta}$ , possiamo convertirci $beta^k} m_k$ Considerato come media ponderata dei gradienti stocastici.Se confrontiamo questo con l'espressione per il gradiente completo $f(x_k) = frazione{1}{n} somma_{i=1}^{n} quindi f_i(x_k)$ Per confrontare, possiamo $beta^k} m_k$ (così come $m_k$ ) viene interpretato come una stima del gradiente completo. Sebbene questa somma ponderata riduca la varianza, solleva anche questioni chiave.Poiché la somma ponderata (10) dà più peso ai gradienti recentemente campionati, non convergerà al gradiente completo $f(x_k)$ , quest'ultima è una media semplice. Il primo metodo di riduzione della varianza che vedremo nella Sezione II-A risolve questo problema utilizzando una media semplice invece di una media ponderata.

1.4. Metodi moderni di riduzione della varianza

A differenza dei metodi classici, ne utilizzano direttamente uno o più $f_i(x_k)$ COME $f(x_k)$ In approssimazione, i moderni metodi di riduzione della varianza (VR) utilizzano una strategia diversa.Questi metodi utilizzano $f_i(x_k)$ per aggiornare la stima del gradiente $g_k$ , il cui obiettivo è realizzare $g_k$ approccio $f(x_k)$ .Nello specifico, speriamo $g_k$ in grado di soddisfare $g_k circa nabla f(x_k)$ . Sulla base di tali stime del gradiente, eseguiamo quindi un passaggio approssimativo del gradiente del modulo:
$x_{k+1} = x_k - gamma g_k quad (11)$
Qui $γ > 0$ è il parametro della dimensione del passo.

Per garantire che venga utilizzata una dimensione del passo costante $γ$ Quando l'iterazione (11) può convergere, dobbiamo garantire che la stima del gradiente $g_k$ La varianza tende a zero. Matematicamente, questo può essere espresso come:
$g_k - nabla f(x_k) |^2 destra] rightarrow 0 quad text{as } k rightarrow infty quad (12)$
aspettative qui $E$ si basa sull'algoritmo fino al $K$ Tutte le variabili casuali vengono calcolate per le iterazioni. La proprietà (12) garantisce che il metodo VR possa essere interrotto quando viene raggiunta la soluzione ottima. Consideriamo questa proprietà come una caratteristica distintiva dell'approccio VR e quindi la chiamiamo proprietà VR. È bene notare che l'espressione varianza “ridotta” può essere fuorviante, perché in realtà la varianza tende a zero. La proprietà (12) è un fattore chiave che consente ai metodi VR di raggiungere una convergenza più rapida in teoria (sotto i presupposti appropriati) e in pratica (come mostrato nella Figura 1).

1.5 Primo esempio di metodo di riduzione della varianza: SGD²

Un semplice metodo di miglioramento può far sì che la formula ricorsiva SGD (5) raggiunga la convergenza senza ridurre la dimensione del passo, ovvero traslare ciascun gradiente. Il metodo specifico consiste nel sottrarre $f_i(x^*)$ , questo metodo è definito come segue:
$x_{k+1} = x_k - gamma (nabla f_{i_k}(x_k) - nabla f_{i_k}(x^*)) quad (13)$
Questo metodo è chiamato SGD² [22].Anche se di solito non possiamo saperlo con certezza ogni $f_i(x^*)$ , ma SGD², ad esempio, può ben illustrare le caratteristiche di base del metodo di riduzione della varianza.Inoltre, molti metodi di riduzione della varianza possono essere visti come una forma approssimativa del metodo SGD²; questi metodi non si basano su ciò che è noto; $f_i(x^*)$ , ma utilizza invece un metodo che possa approssimare $f_i(x^*)$ valore stimato.

Vale la pena notare che SGD² utilizza una stima imparziale del gradiente completo.Perché $f(x^*) = 0$ ,F:
$f_{i_k}(x_k) - nabla f_{i_k}(x^*)] = nabla f(x_k) - nabla f(x^*) = nabla f(x_k)$
Inoltre, quando SGD² raggiunge la soluzione ottimale, si fermerà naturalmente per qualsiasi motivo $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo$ ,Avere:
$f_i(x) - nabla f_i(x^*)) bigg|_{x=x^*} = 0$

Dopo ulteriore osservazione, con $x_k$ vicino $x^*$ (per consecutivi $f_i$ ), SGD² soddisfa la proprietà di riduzione della varianza (12) perché:
$g_k - nabla f(x_k) |^2 destra] = \Esinistra[ | nabla f_{i_k}(x_k) - nabla f_{i_k}(x^*) - nabla f(x_k) |^2 destra] leq Eleft[ | nabla f_{i_k}(x_k) - nabla f_{i_k}(x^*) |^2 a destra]$
Qui usiamo il Lemma 2, let $f_{i_k}(x_k) - nabla f_{i_k}(x^*)$ , e ne ho approfittato $f_{i_k}(x_k) - nabla f_{i_k}(x^*)] = nabla f(x_k)$ natura. Questa proprietà indica che SGD² ha una velocità di convergenza più rapida rispetto ai tradizionali metodi SGD, che abbiamo dettagliato nell'Appendice B.

1.6. Convergenza rapida del metodo di riduzione della varianza

In questa sezione introdurremo due ipotesi standard utilizzate per analizzare il metodo di riduzione della varianza (VR) e discuteremo l'effetto di accelerazione che può essere ottenuto con queste ipotesi rispetto al tradizionale metodo SGD. Innanzitutto, assumiamo che il gradiente abbia continuità Lipschitz, il che significa che la velocità di variazione del gradiente è finita.

Presupposto 1 (continuità di Lipschitz)

Assumiamo che la funzione $F$ è differenziabile ed è $L$ - liscio, per tutti $X$ E $e$ e qualcuno $0 < L < \infty$ ,Le seguenti condizioni:
$∥\nabla F (X) - \nabla F (e) ∥ \leq L ∥ X - e ∥ (14)$
Ciò significa che ogni $mathbb{R}^d freccia a destra mathbb{R}$ è differenziabile, $L_i$ - liscio, definiamo $L_{testo{max}}$ per $max{L_1, . . . , L_n}$ 。

Sebbene questo sia generalmente considerato un presupposto debole, nei capitoli successivi discuteremo dei metodi VR adatti a problemi non lisci. Per una funzione univariata due volte differenziabile, $L$ -La levigatezza può essere intuitivamente intesa come: equivale ad assumere che la derivata seconda lo sia $L$ limite superiore, cioè $∣ F^{''} (X) ∣ \leq L$ per tutti $bb{R}^d$ .Per funzioni due volte differenziabili di più variabili, equivale ad assumere una matrice Hessiana $nabla^2 f(x)$ Il valore singolare di $L$ limite superiore.

Ipotesi 2 (forte convessità)

La seconda ipotesi che consideriamo è che la funzione (f) sia $μ$ -Fortemente convesso, il che significa che per certo $μ > 0$ ,funzione $frac{mu}{2}|x|^2$ È convesso.Inoltre, per ciascuno $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo = 1, ..., N$ ， $mathbb{R}^d freccia a destra mathbb{R}$ È convesso.

Questo è un presupposto forte.Nel problema dei minimi quadrati, ciascuno (fi$ è convesso, ma la funzione complessiva (f) è solo nella matrice di progetto $a_1 , . . . , un_n]$ È fortemente convesso solo se ha rango di riga perfetto. Il problema della regressione logistica regolarizzata L2 soddisfa questo presupposto a causa dell'esistenza del termine di regolarizzazione, dove $μ \geq λ$ 。

Un'importante classe di problemi che soddisfano queste ipotesi sono i problemi di ottimizzazione della forma:
$x^* in argmin_{x in mathbb{R}^d} f(x) = frac{1}{n} sum_{i=1}^{n} ell_i(a_i^Tx) + frac{lambda}{2}|x|^2 quad (15)$
dove ogni funzione di "perdita". $ell_i: mathbb{R} freccia a destra mathbb{R}$ è due volte differenziabile e la sua derivata seconda $ell_i''$ è limitato a 0 e ad un limite superiore $M$ fra. Ciò include una varietà di funzioni di perdita con regolarizzazione L2 nell'apprendimento automatico, come i minimi quadrati, la regressione logistica, la regressione probit, la regressione robusta di Huber, ecc.In questo caso, per tutti $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo$ ,Abbiamo $L_i leq M|a_i|^2 + lambda$ E $μ \geq λ$ 。

Con questi presupposti, il tasso di convergenza del metodo della discesa del gradiente (GD) è determinato dal numero della condizione $κ := L / μ$ Decidere. Il numero di condizione è sempre maggiore o uguale a 1 e quando è significativamente maggiore di 1, i contorni della funzione diventano molto ellittici, facendo oscillare le iterazioni del metodo GD.Al contrario, quando $κ$ Quando è vicino a 1, il metodo GD converge più velocemente.

Sotto le ipotesi 1 e 2, il metodo VR converge a una velocità lineare.Diciamo che il valore della funzione di un metodo casuale ({f(x_k)}) è dato da $0 < ρ \leq 1$ Il tasso di convergenza lineare (sotto le aspettative), se esiste una costante $C > 0$ Fa:
$E[f(x_k)] - f(x^*) leq (1 - rho)^k C = O(exp(-krho)) quad per tutti i k quad (16)$
Ciò è in contrasto con i metodi SGD classici che si basano solo su stime imparziali del gradiente ad ogni iterazione, che ottengono tassi sublineari solo con queste ipotesi:
$E[f(x_k)] - f(x^*) leq O(1/k)$
Il minimo che soddisfa questa disuguaglianza $K$ Si chiama complessità iterativa dell'algoritmo. Di seguito sono riportati la complessità iterativa e il costo di un'iterazione per le varianti di base dei metodi GD, SGD e VR:

algoritmo	Numero di iterazioni	costo di un'iterazione
D.O.	$Lo (κ Io G (1/ ϵ))$	$Lo (N)$
Dollaro di Singapore	$O(kappa_{testo{max}} max(1/epsilon))$	$Lo (1)$
Realtà virtuale	$O((kappa_{text{max}} + n) log(1/epsilon))$	$Lo (1)$

Il tempo di esecuzione totale di un algoritmo è determinato dal prodotto della complessità dell'iterazione e del tempo di esecuzione dell'iterazione.usato qui $kappa_{testo{max}} := max_i L_i/mu$ .Avviso $kappa_{testo{max}} geq kappa$ Pertanto, la complessità dell'iterazione del GD è inferiore a quella del metodo VR.

Tuttavia, poiché il costo per iterazione di GD è quello del metodo VR $N$ volte, il metodo VR è superiore in termini di tempo di esecuzione totale.

Il vantaggio dei metodi SGD classici è che il loro tempo di esecuzione e il tasso di convergenza non dipendono da $N$ , ma ha una tolleranza $ϵ$ La dipendenza è molto peggiore, il che spiega la scarsa performance dell’SGD quando la tolleranza è piccola.

Nell'Appendice B, forniamo una semplice dimostrazione che mostra che il metodo SGD² ha la stessa complessità iterativa del metodo VR.

2. Metodo base di riduzione della varianza

Lo sviluppo dei metodi di riduzione della varianza (VR) ha attraversato diverse fasi e il lotto iniziale di metodi ha prodotto tassi di convergenza significativamente migliorati. L'inizio di questa serie di metodi è l'algoritmo SAG. Successivamente, l'algoritmo stocastico di salita a doppia coordinata (SDCA), l'algoritmo MISO, l'algoritmo stocastico di riduzione della varianza del gradiente (SVRG/S2GD) e l'algoritmo SAGA (che significa SAG "migliorato") sono usciti uno dopo l'altro.

In questo capitolo descriveremo in dettaglio questi metodi pionieristici della realtà virtuale. Nel Capitolo 4 esploreremo alcuni metodi più recenti che mostrano caratteristiche superiori rispetto a questi metodi di base in scenari applicativi specifici.

2.1. Metodo del gradiente medio stocastico (SAG)

La nostra esplorazione del primo metodo di riduzione della varianza (VR) inizia con l'imitazione dell'intera struttura del gradiente.Dal momento che il gradiente completo $\nabla F (X)$ è tutto $f_i(x)$ Una media semplice dei gradienti, quindi la nostra stima del gradiente completo $g_k$ Dovrebbe anche essere la media di queste stime del gradiente. Questa idea ha dato origine al nostro primo metodo VR: il metodo del gradiente medio stocastico (SAG).

Il metodo SAG [37], [65] è una versione randomizzata del metodo IAG (Incremental Aggreged Gradient) precoce [4]. L'idea centrale di SAG è quella per ciascun punto dati $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo$ mantenere una stima $v_{ik} circa nabla f_i(x_k)$ .Quindi, usa questi $la_{io lo so}$ Come stima del gradiente completo viene utilizzata la media dei valori, ovvero:
$bar{g}_k = frac{1}{n} somma_{j=1}^{n} v_{jk} circa frac{1}{n} somma_{j=1}^{n} nabla f_j(x_k) = nabla f(x_k) quad (18)$

In ogni iterazione di SAG, dal set ${1, \dots, N}$ Estrai un indice da $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo_{K}$ , e poi aggiornato secondo le seguenti regole $v_{v_} (giusto)$ ：
$begin{cases} nabla f_{i_k}(x_k), & text{if } j = i_k \ v_{jk}^k, & text{if } j neq i_k end{cases}$
Tra loro, ciascuno $v_{0i}$ Può essere inizializzato a zero o $f_i(x_0)$ valore approssimativo.Con la soluzione $x^*$ approssimazione, ciascuno $la_{io lo so}$ convergerà gradualmente a $f_i(x^*)$ , soddisfacendo così la proprietà VR (12).

Per implementare il SAG in modo efficiente, dobbiamo prestare attenzione al calcolo $bar{g}_k$ per evitare di ricominciare ogni volta la somma da zero $N$ vettore, perché questo è $N$ Il costo è alto quando è grande.Fortunatamente, poiché ogni iterazione ne ha solo una $la_{io lo so}$ I termini cambieranno e non dovremo ricalcolare ogni volta l'intera somma.Nello specifico, supponiamo che durante l'iterazione $K$ Indice estratto da $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo_{K}$ , allora c'è:
$bar{g}_k = frac{1}{n} somma_{sottopila{j=1 \ j neq i_k}}^{n} v_{jk} + frac{1}{n} v_{i_k}^k = bar{g}_{k-1} - frac{1}{n} v_{i_k}^{k-1} + frac{1}{n} v_{i_k}^k quad (20)$

Poiché oltre a $vi_{io_k}$ tutto tranne $v_{v_} (giusto)$ I valori rimangono tutti gli stessi, li memorizziamo e basta $J$ Un vettore corrispondente a $v_j$ . L'algoritmo 1 mostra l'implementazione specifica del metodo SAG.

SAG è il primo metodo stocastico per ottenere la convergenza lineare e la sua complessità di iterazione lo è $O((kappa_{text{max}} + n) log(1/epsilon))$ , utilizzando la dimensione del passo $O(1/L_{testo{max}})$ . Questa convergenza lineare può essere osservata nella Figura 1.Vale la pena notare che a causa di $L_{testo{max}}$ -Funzione fluida per qualsiasi $L_{testo{max}}$ Pure $L^{'}$ - I metodi SAG uniformi raggiungono tassi di convergenza lineare per dimensioni di passo sufficientemente piccole, in contrasto con i metodi SGD classici, che raggiungono solo velocità sublineari con sequenze di dimensioni di passo decrescenti che sono difficili da regolare nella pratica.

A quel tempo, la convergenza lineare del SAG rappresentava un progresso significativo perché calcolava solo un gradiente stocastico (elaborando un singolo punto dati) in ciascuna iterazione. Tuttavia, la prova di convergenza fornita da Schmidt et al [65] è molto complessa e si basa su passaggi verificati dal computer. Uno dei motivi principali per cui il SAG è difficile da analizzare è questo $g_k$ è una stima distorta del gradiente.

Successivamente, introduciamo il metodo SAGA, una variante del SAG che sfrutta il concetto di covariate per creare una variante imparziale del metodo SAG che ha prestazioni simili ma è più facile da analizzare.

Algoritmo 1: metodo SAG

Parametri: dimensione del passo $γ > 0$
inizializzazione: $x_0$ ， $v_i = 0 in mathbb{R}^d$ per $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo = 1, \dots, N$
Giusto $K = 1, \dots, T - 1$ strumento:
a. Selezione casuale $i_k in {1, ldots, n}$
b $bar{g}_k = bar{g}_{k-1} - frac{1}{n} v_{i_k}^{k-1}$
aggiornamento $v_{i_k}^k = nabla f_{i_k}(x_k)$
d. Aggiornare la stima del gradiente $bar{g}_k = bar{g}_k + frac{1}{n} v_{i_k}^k$
e $x_{k+1} = x_k - gamma bar{g}_k$
Produzione: $x_T$

2.2.Metodo SAGA

Una stima del gradiente imparziale di base ridotta $f_{i_k}(x_k)$ L’approccio della varianza avviene attraverso l’uso delle cosiddette covariate, o variabili di controllo.per $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo = 1, \dots, N$ ,impostare $v_i in mathbb{R}^d$ è un vettore.Usando questi vettori, possiamo convertire l'intero gradiente $\nabla F (X)$ Riscritto come:
$somma_{i=1}^{n}(nabla f_i(x) - v_i + v_i) = frac{1}{n} somma_{i=1}^{n} nabla f_i(x) - v_i + frac{1}{n} somma_{j=1}^{n} v_j$
$somma_{i=1}^{n} nabla f_i(x, v) quad (21)$
che definisce $f_i(x, v) := nabla f_i(x) - v_i + frac{1}{n} somma_{j=1}^{n} v_j$ .Ora possiamo campionare casualmente a $f_i(x, v)$ per costruire il gradiente completo $\nabla F (X)$ Una stima imparziale di $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo \in {1, \dots, N}$ , puoi applicare il metodo SGD e utilizzare la stima del gradiente:
$g_k = nabla f_{i_k}(x_k, v) = nabla f_{i_k}(x_k) - v_{i_k} + frac{1}{n} somma_{j=1}^{n} v_j quad (22)$

per l'osservazione $vi_io$ La differenza della coppia di selezione $g_k$ influenza, possiamo $g_k = nabla f_{i_k}( x_k, v)$ Sostituisci e usa $E_i sim frac{1}{n}[v_i] = frac{1}{n} somma_{j=1}^{n} v_j$ Per calcolare l'aspettativa, otteniamo:
$f_i(x_k) - v_i + E_i sim frac{1}{n}[v_i - nabla f_i(x_k)]|^2 destra] leq E sinistra[ |nabla f_i(x_k) - v_i|^2 destra] quad (23)$
Il Lemma 2 è usato qui, dove $f_i(x_k) - v_i$ .Questo limite (23) mostra che se $vi_io$ insieme a $K$ L'aumento è vicino a $f_i(x_k)$ , possiamo ottenere attributi VR (12).Ecco perché chiamiamo $vi_io$ sono covariate e possiamo selezionarle per ridurre la varianza.

Ad esempio, questo approccio è implementato anche dal metodo SGD² (13), dove $v_i = nabla f_i(x^*)$ .Tuttavia, questo non è comunemente usato nella pratica perché di solito non lo sappiamo $f_i(x^*)$ .Un'opzione più pratica è $vi_io$ come sappiamo $bar{x}_i in mathbb{R}^d$ gradiente vicino $f_i(bar{x}_i)$ . SAGA per ogni funzione $f_i$ utilizzare un punto di riferimento $bar{x}_i in mathbb{R}^d$ e utilizzare le covariate $v_i = nabla f_i(bar{x}_i)$ , ognuno dei quali $bar{x}_i$ sarà la nostra ultima valutazione $f_i$ punto. Usando queste covariate, possiamo costruire una stima del gradiente, seguendo la (22), dando:
$g_k = nabla f_{i_k}(x_k) - nabla f_{i_k}(bar{x}_{i_k}) + frac{1}{n} somma_{j=1}^{n} nabla f_j(bar{x}_j) quad (24)$

Per implementare SAGA possiamo memorizzare i gradienti $f_i(bar{x}_i)$ invece di $N$ Punto di riferimento $bar{x}_i$ .Vale a dire, supponiamo $v_j = nabla f_j(bar{x}_j)$ per $J \in {1, \dots, N}$ , in ogni iterazione, aggiorniamo un gradiente stocastico come SAG $v_j$ 。

Algoritmo 2 SAGA

Parametri: dimensione del passo $γ > 0$
inizializzazione: $x_0$ ， $v_i = 0 in mathbb{R}^d$ per $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo = 1, \dots, N$
condotta $K = 1, \dots, T - 1$ iterazioni:
a. Selezione casuale $i_k in {1, ldots, n}$
b. Salvare il vecchio valore $v_{testo{vecchio}} = v_{i_k}$
aggiornamento $v_{i_k} = nabla f_{i_k}(x_k)$
Aggiornamento $x_{k+1} = x_k - gamma (v_{i_k} - v_{text{old}} + bar{g}_k)$
e. Aggiornare la stima del gradiente $bar{g}_k = bar{g}_{k-1} + frac{1}{n} (v_{i_k} - v_{testo{vecchio}})$
Produzione: $x_T$

Il metodo SAGA ha la stessa complessità di iterazione di SAG $O((kappa_{text{max}} + n) log(1/epsilon))$ , utilizzando la dimensione del passo $O(1/L_{testo{max}})$ , ma la dimostrazione è molto più semplice.Tuttavia, come SAG, il metodo SAGA richiede l'archiviazione $N$ vettori ausiliari $v_i in mathbb{R}^d$ per $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo = 1, \dots, N$ , il che significa la necessità $Lo (N D)$ di spazio di archiviazione.Quando $D$ E $N$ Quando entrambi sono grandi, ciò potrebbe non essere fattibile. Nella sezione successiva verrà descritto in dettaglio come ridurre questo requisito di memoria per modelli comuni come i modelli lineari regolarizzati.

quando è possibile $N$ Quando due vettori ausiliari vengono archiviati in memoria, SAG e SAGA tendono a comportarsi in modo simile. Se questo requisito di memoria è troppo elevato, il metodo SVRG, che esamineremo nella sezione successiva, è una buona alternativa. Il metodo SVRG raggiunge lo stesso tasso di convergenza ed è spesso quasi altrettanto veloce nella pratica, ma richiede solo $Lo (D)$ della memoria, per questioni generali.

2.3.Metodo SVRG

Prima dell'avvento del metodo SAGA, alcuni dei primi lavori introdussero per la prima volta le covariate per risolvere il problema dell'elevata memoria richiesto dal metodo SAG.Questi studi si basano su un punto di riferimento fisso $mathbb{R}^d$ covariate, a quel punto abbiamo calcolato l’intero gradiente $\nabla F (\overset{X}{ˉ})$ .memorizzando punti di riferimento $\overset{X}{ˉ}$ e il corrispondente gradiente completo $\nabla F (\overset{X}{ˉ})$ , possiamo farlo senza memorizzarli ciascuno $f_j(bar{x})$ Nel caso, utilizzare $xˉbar{x}_j = bar{x}$ a tutti $J$ per implementare l'aggiornamento(24).Nello specifico, invece di memorizzare questi vettori, utilizziamo i punti di riferimento memorizzati in ogni iterazione $\overset{X}{ˉ}$ calcolare $f_{i_k}(bar{x})$ . Questo metodo è stato originariamente proposto da diversi autori con nomi diversi, ma è stato successivamente unificato come metodo SVRG, seguendo la nomenclatura di [28] e [84].

Formalizziamo il metodo SVRG nell'algoritmo 3.

Utilizzando la (23), possiamo ricavare la stima del gradiente $g_k$ La varianza di è limitata:
$g_k - nabla f(x_k) |^2 destra] leq Eleft[ | nabla f_i(x_k) - nabla f_i(bar{x}) |^2 destra] leq L_{text{max}}^2 | x_k - bar{x} |^2$
dove la seconda disuguaglianza utilizza ciascuno $f_i$ Di $L_i$ -Levigatezza.

Vale la pena notare che il punto di riferimento $\overset{X}{ˉ}$ Più ci avviciniamo al punto attuale $x_k$ , minore è la varianza della stima del gradiente.

Affinché il metodo SVRG sia efficace, è necessario aggiornare frequentemente i punti di riferimento $\overset{X}{ˉ}$ (richiedendo quindi il calcolo del gradiente completo) viene ponderato rispetto al beneficio della varianza ridotta.Per questo motivo, ciascuno di noi $T$ Aggiorna il punto di riferimento una volta ad ogni iterazione per avvicinarlo $x_k$ (Vedi riga 11 dell'Algoritmo II-C).Cioè, il metodo SVRG contiene due cicli: un ciclo esterno $S$ , dove viene calcolato il gradiente di riferimento $f(bar{x}_{s-1})$ (Linea 4) e un ciclo interno in cui il punto di riferimento è fisso e l'iterazione interna viene aggiornata in base al passo del gradiente stocastico (22) $x_k$ (Riga 10).

A differenza di SAG e SAGA, SVRG richiede solo $Lo (D)$ di memoria. Gli svantaggi di SVRG includono: 1) Abbiamo un parametro aggiuntivo $T$ , ovvero la lunghezza del ciclo interno, deve essere regolata 2) È necessario calcolare due gradienti per ogni iterazione e il gradiente completo deve essere calcolato ogni volta che si cambia il punto di riferimento;

Johnson e Zhang [28] hanno dimostrato che SVRG ha complessità iterativa $O((kappa_{text{max}} + n) log(1/epsilon))$ , simile a SAG e SAGA.Questo è il numero di cicli all'interno dell'ipotesi $T$ dalla raccolta ${1, \dots, M}$ Ottenuto in condizioni di campionamento uniforme, dove $L_{testo{max}}$ ， $μ$ , dimensione del passo $γ$ E $T$ Tra di loro devono essere soddisfatte alcune dipendenze.In pratica, utilizzando $O(1/L_{testo{max}})$ e la lunghezza del circuito interno $T = N$ , SVRG tende a funzionare bene, che è esattamente l'impostazione utilizzata nella Figura 1.

Ora, ci sono molte varianti del metodo SVRG originale.Ad esempio, alcune varianti utilizzano $T$ distribuzione alternativa [32], alcune varianti consentono la forma $O(1/L_{testo{max}})$ La dimensione del passo [27], [33], [35].Ci sono anche alcune varianti che utilizzano $\nabla F (\overset{X}{ˉ})$ approssimazione mini-batch per ridurre il costo di queste valutazioni complete del gradiente e aumentare la dimensione del mini-batch per preservare le proprietà VR.Esistono anche alcune varianti in cui gli aggiornamenti vengono ripetuti nel ciclo interno secondo [54] $g_k$ ：
[ g_k = nabla f_{i_k}(x_k) - nabla f_{i_k}(x_{k-1}) + g_{k-1} quad (25) ]
Ciò fornisce un'approssimazione più locale. L'uso di questa variante di aggiornamento continuo (25) mostra vantaggi unici nel minimizzare le funzioni non convesse, come discusso brevemente nella Sezione IV.Infine, ricordiamo che SVRG può trarne vantaggio $f(bar{x}_s)$ valore per aiutare a decidere quando terminare l'algoritmo.

Algoritmo 3 Metodo SVRG

Parametri: dimensione del passo $γ > 0$
Inizializza il punto di riferimento $bar{x}_0 = x_0 in mathbb{R}^d$
Effettuare la circolazione esterna $S = 1, 2, \dots$ ：
a. Calcolare e memorizzare $f(bar{x}_{s-1})$
b $x_0 = bar{x}_{s-1}$
c. Selezionare il numero di iterazioni del ciclo interno $T$
d. Effettuare la circolazione interna $K = 0, 1, \dots, T - 1$ ：
Selezione casuale $i_k in {1, ldots, n}$
ii.Calcolo $g_k = nabla f_{i_k}(x_k) - nabla f_{i_k}(bar{x}_{s-1}) + nabla f(bar{x}_{s-1})$
iii.Aggiornamento $x_{k+1} = x_k - gamma g_k$
e. Aggiornare il punto di riferimento $bar{x}_s = x_t$

2.4.SDCA e sue varianti

Uno svantaggio dei metodi SAG e SVRG è che la loro dimensione del passo si basa su valori sconosciuti che potrebbero essere sconosciuti in alcuni problemi. $L_{testo{max}}$ . Prima di SVRG, il metodo SDCA [70], come uno dei primi metodi VR, estendeva la ricerca sui metodi di discesa delle coordinate ai problemi a somma finita. L'idea alla base dell'SDCA e delle sue varianti è che le coordinate del gradiente forniscono una stima del gradiente che riduce la varianza naturale.Nello specifico, supponiamo $J \in {1, \dots, D}$ e definire $nabla_j f(x) := sinistra( frac{f(x) parziale}{x_j parziale} destra) e_j$ è l'esimo di (f(x)) $J$ derivate nelle direzioni delle coordinate, dove $e_j in mathbb{R}^d$ E' il primo $J$ vettore unitario.Una proprietà chiave delle derivate delle coordinate è questa $nabla_j f(x^*) = 0$ , perché lo sappiamo $f(x^*) = 0$ .La derivata di questo con ciascun punto dati $f_j$ diverso, quest'ultimo lo è $x^*$ potrebbe non essere zero. Pertanto abbiamo:
$nabla_j f(x) |^2 rightarrow 0 quad text{当} quad x rightarrow x^* quad (26)$
Ciò significa che la derivata delle coordinate soddisfa la proprietà di riduzione della varianza (12).Inoltre, possiamo usare $nabla_j f(x)$ costruire $\nabla F (X)$ una stima imparziale di.Ad esempio, supponiamo $J$ proviene dalla collezione ${1, \dots, D}$ Un indice selezionato in modo uniforme e casuale in formato .Pertanto, per qualsiasi $iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo \in {1, \dots, D}$ ,Abbiamo $P [J = iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo] = \frac{1}{D}$ . Perciò, $nabla_j f(x)$ SÌ $\nabla F (X)$ Una stima imparziale del perché:
$nabla_j f(x) right] = d sum_{i=1}^{d} P[j = i] frac{parziale f(x)}{parziale x_i} e_i = sum_{i=1}^{d} frac{parziale f(x)}{parziale x_i} e_i = nabla f(x)$

Perciò, $nabla_j f(x)$ Ha tutte le proprietà ideali che ci aspetteremmo per la stima VR dei gradienti completi, senza la necessità di utilizzare covariate. Uno svantaggio dell'utilizzo di questo gradiente di coordinate è che è computazionalmente costoso per il nostro problema di somma (2).Questo perché il calcolo $nabla_j f(x)$ È necessario attraversare l'intero set di dati perché $nabla_j f(x) = frac{1}{n} somma_{i=1}^{n} nabla_j f_i(x)$ . Pertanto, l'uso delle derivate coordinate sembra incompatibile con la struttura del nostro problema di somma. Tuttavia, possiamo spesso riscrivere il problema originale (2) in una cosiddetta formulazione duale, dove le derivate coordinate possono sfruttare la struttura intrinseca.

Ad esempio, la doppia formula del modello lineare regolarizzato L2 (15) è:
$v^* in argmax_{v in mathbb{R}^n} frac{1}{n} somma_{i=1}^{n} -ell_i^*(-v_i) - frac{lambda}{2} sinistra| frac{1}{lambda} somma_{i=1}^{n} v_i a_i destra|^2 quad (27)$
In $ell_i^*(v)$ SÌ $ell_i$ coniugato convesso.Possiamo usare la mappatura $somma_{i=1}^{n} v_i a_i$ per ripristinare il problema originale (15) $X$ variabile.risolverà $v^*$ Sostituendo nella parte destra della mappatura precedente, possiamo ottenere la soluzione di (15) $x^*$ 。

Si noti che questo duplice problema ha $N$ variabili reali $v_i in mathbb{R}$ , corrispondente ad uno per ciascun campione di addestramento.Inoltre, ciascuna funzione di doppia perdita $ell_i^*$ soltanto $vi_io$ La funzione. Cioè, il primo termine della funzione di perdita è coordinabilmente separabile. Questa separabilità in coordinate, unita alla forma semplice del secondo termine, ci consente di implementare in modo efficiente il metodo di risalita delle coordinate.In effetti, Shalev-Shwartz e Zhang hanno dimostrato che l'ascesa coordinata su questo problema ha una complessità iterativa simile a SAG, SAGA e SVRG $O((kappa_{text{max}} + n) log(1/epsilon))$ 。

Anche il costo dell'iterazione e la struttura dell'algoritmo sono molto simili: somma tramite tracciamento $somma_{i=1}^{n} v_i a_i$ Per gestire il secondo termine in (27), ciascuna iterazione di risalita a doppia coordinata deve considerare solo un campione di addestramento e il costo di ciascuna iterazione è lo stesso di $N$ Niente da fare.Inoltre, possiamo utilizzare una ricerca di linea 1D per calcolare in modo efficiente la dimensione del passo da massimizzare come $vi_io$ Duplice obiettivo della funzione.Ciò significa che anche senza $L_{testo{max}}$ O conoscendo le quantità rilevanti, è anche possibile ottenere tempi di esecuzione rapidi nel caso peggiore per i metodi VR.

3. Problemi pratici di riduzione della varianza

Per implementare il metodo di riduzione della varianza (VR) di base e ottenere prestazioni ragionevoli, è necessario affrontare diversi problemi di implementazione. In questa sezione, discutiamo diverse questioni non trattate sopra.

3.1.SAG/SAGA/SVRG impostazione della dimensione del passo

Nel campo degli algoritmi di ottimizzazione, in particolare nei metodi di riduzione della variazione come il gradiente medio stocastico (SAG), l'algoritmo del gradiente medio stocastico (SAGA) e il gradiente stocastico (SVRG), l'impostazione della dimensione del passo è una questione chiave.Sebbene per il metodo stocastico di salita a doppia coordinata (SDCA), possiamo utilizzare il doppio obiettivo per determinare la dimensione del passo, la base teorica per i metodi variabili originali di SAG, SAGA e SVRG è che la dimensione del passo dovrebbe essere $Osinistra(frac{1}{L_{testo{max}}}destra)$ modulo.Tuttavia, nelle applicazioni pratiche, spesso non lo sappiamo $L_{testo{max}}$ valore esatto e l'utilizzo di altre dimensioni di passo può fornire prestazioni migliori.

Una strategia classica per impostare la dimensione del passo nel metodo di discesa del gradiente completo (full-GD) è la ricerca della linea Armijo.dato il punto attuale $x_k$ e la direzione della ricerca $g_k$ , Ricerca linea Armijo in $gamma_k$ viene eseguito sulla linea, che è definita come $gamma_k in {gamma : x_k + gamma g_k}$ , e la funzione deve essere sufficientemente ridotta, ovvero:
$f(x_k + gamma_k g_k) < f(x_k) - c gamma_k |nabla f(x_k)|^2$
Tuttavia, questo approccio richiede più passaggi candidati $gamma_k$ Calcolo $x_k + gamma_k g_k)$ , che valuta $F (X)$ Costo proibitivo quando si tratta di attraversare l'intero set di dati.

Per risolvere questo problema, è possibile utilizzare un metodo di variazione casuale per trovare quelli che soddisfano le seguenti condizioni $gamma_k$ ：
$f_{ik}(x_k + gamma_k g_k) < f_{ik}(x_k) - c gamma_k |nabla f_{ik}(x_k)|^2$
Questo approccio di solito funziona bene nella pratica, soprattutto quando $f_{ik}(x_k)|$ non vicino allo zero, anche se attualmente non esiste alcuna teoria a sostegno di questo approccio.

Inoltre Mairal ha proposto una "tecnica Bottou" per impostare nella pratica la dimensione del passo. Questo metodo esegue una ricerca binaria prendendo una piccola porzione del set di dati (ad esempio il 5%) per cercare di trovare la dimensione del passo ottimale in un singolo passaggio attraverso questo campione. Simile alla ricerca della linea Armijo, questo metodo spesso funziona bene nella pratica, ma ancora una volta manca di un fondamento teorico.

Tieni presente che il contenuto di cui sopra è una riaffermazione del testo originale, utilizzando il formato Markdown per rappresentare formule e variabili matematiche.

Tuttavia, il metodo SDCA presenta anche alcuni svantaggi.Innanzitutto è necessario calcolare il coniugato convesso $ell_i^*$ piuttosto che un semplice gradiente. Non disponiamo di un equivalente differenziale automatico per i coniugati convessi, quindi ciò potrebbe aumentare lo sforzo di implementazione. Un lavoro recente ha proposto metodi SDCA "dual-free" che non richiedono la coniugazione e utilizzano invece direttamente i gradienti. Tuttavia, in questi metodi non è più possibile tracciare il doppio target per impostare la dimensione del passo.In secondo luogo, sebbene la SDCA richieda solo $Lo (N + D)$ memoria per risolvere il problema (15), ma per questa categoria di problemi è necessario solo SAG/SAGA $Lo (N + D)$ di memoria (vedere Sezione 3).Una variante di SDCA adatta a problemi più generali con SAG/SAGA $Lo (N D)$ memoria perché $vi_io$ diventare avere $D$ vettore di elementi. Un ultimo sottile inconveniente dell’SDCA è che assume implicitamente una forte costante di convessità $μ$ pari $λ$ .per $μ$ più del $λ$ problema, il metodo VR originale di solito supera significativamente l’SDCA.

3.2 Determinazione delle condizioni di risoluzione

Nel campo dell'ottimizzazione degli algoritmi, spesso ci basiamo su risultati teorici di complessità iterativa per prevedere il numero di iterazioni nel caso peggiore necessarie affinché un algoritmo raggiunga una precisione specifica. Tuttavia, questi limiti teorici spesso si basano su alcune costanti che non possiamo prevedere e, nelle applicazioni pratiche, l’algoritmo può spesso raggiungere la precisione prevista in un minor numero di iterazioni. Pertanto, dobbiamo impostare alcuni criteri di test per determinare quando terminare l'algoritmo.

Nel tradizionale metodo di discesa a gradiente completo (full-GD), solitamente utilizziamo la norma del gradiente $f(x_k) |$ O qualche altra quantità correlata a questa per decidere quando interrompere l'iterazione.Per il metodo SVRG possiamo adottare lo stesso criterio ma utilizzare $f(bar{x}_s) |$ come base per il giudizio.Per il metodo SAG/SAGA, anche se non calcoliamo esplicitamente il gradiente completo, la quantità $ g_{bar{k}} $ si avvicinerà gradualmente a $f(x_k)$ , quindi, utilizzare $∥ G_{\overset{ˉ}{K}} ∥$ come condizione di arresto è un'euristica ragionevole.

Nel metodo SDCA, con qualche lavoro di registrazione aggiuntivo, possiamo tracciare il gradiente del doppio obiettivo senza aggiungere ulteriori costi asintotici.Inoltre, un approccio più sistematico sarebbe quello di monitorare il doppio divario, anche se ciò aumenterebbe il gap $Lo (N)$ costo, ma è in grado di fornire condizioni di terminazione con prove di dual gap. Inoltre, basandosi sulla condizione di ottimalità di target fortemente convessi, il metodo MISO adotta un metodo basato su principi basati sul limite inferiore quadratico [41].

Di seguito sono riportate formule e variabili matematiche espresse in formato Markdown:

Norma del gradiente: $f(x_k) |$
Norma del gradiente nel metodo SVRG: $f(bar{x}_s) |$
La quantità di gradiente di approssimazione nel metodo SAG/SAGA: $ g_{bar{k}} $
Aumento del costo per iterazione: $Lo (N)$
Metodo MISO
limite inferiore quadratico

Tieni presente che il contenuto di cui sopra è una riaffermazione del testo originale, utilizzando il formato Markdown per rappresentare formule e variabili matematiche.

3.3 Ridurre i requisiti di memoria

Sebbene l'algoritmo Stochastic Variational Reduction of Gradient (SVRG) elimini i requisiti di memoria dei precedenti metodi di riduzione delle variazioni, nelle applicazioni pratiche gli algoritmi SAG (Stochastic Average Gradient Descent) e SAGA (Stochastic Average Gradient Descent with Gradient Accumulation) vengono utilizzati in molti problemi tendono a richiedere meno iterazioni rispetto all'algoritmo SVRG.Ciò ha innescato un pensiero: ci sono alcuni problemi che consentono a SAG/SAGA di farlo $Lo (N D)$ I requisiti di memoria sono implementati di seguito. Questa sezione esplora una classe di modelli lineari per i quali i requisiti di memoria possono essere significativamente ridotti.

Considera un modello lineare in cui ciascuna funzione $F_{iooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo} (X)$ Può essere espresso come $xi_i(mathbf{a}_i^top x)$ .Giusto $X$ La derivata dà la forma del gradiente:
$f_i(x) = xi'(mathbf{a}_i^top x) mathbf{a}_i$
Qui, $ξ^{'}$ esprimere $ξ$ la derivata di.Supponendo di avere accesso diretto agli autovettori $matematicabf{a}_i$ , quindi per implementare il metodo SAG/SAGA, dobbiamo solo memorizzare lo scalare $xi(mathbf{a}_i^top x)$ .In questo modo, i requisiti di memoria variano da $Lo (N D)$ ridotto a $Lo (N)$ . Anche l'algoritmo SVRG può trarre vantaggio da questa struttura di gradienti: memorizzandola $N$ scalare, possiamo ridurre il numero di valutazioni del gradiente richieste per l'iterazione "interna" SVRG a 1 per questa classe di problemi.

Esistono altri tipi di problemi, come i modelli grafici probabilistici, che offrono anche la possibilità di ridurre i requisiti di memoria [66]. Attraverso la specifica struttura dei dati e l'ottimizzazione dell'algoritmo, le risorse di memoria richieste dall'algoritmo in fase di esecuzione possono essere ulteriormente ridotte.

Di seguito sono riportate formule e variabili matematiche espresse in formato Markdown:

Funzione del modello lineare: $f_i(x) = xi_i(mathbf{a}_i^top x)$
Espressione gradiente: $f_i(x) = xi'(mathbf{a}_i^top x) mathbf{a}_i$
Vettore delle caratteristiche: $matematicabf{a}_i$
I requisiti di memoria vanno da $Lo (N D)$ Ridurre a $Lo (N)$ 。

3.4. Elaborazione di gradienti sparsi

In alcuni problemi, il gradiente $f_i(x)$ Può contenere un gran numero di valori zero, come un modello lineare con caratteristiche sparse.In questo caso, il tradizionale algoritmo stocastico di discesa del gradiente (SGD) può essere implementato in modo efficiente, con complessità computazionale lineare nel numero di elementi diversi da zero nel gradiente, che di solito è molto più piccolo della dimensione del problema $D$ . Tuttavia, nei metodi standard di riduzione variazionale (VR), questo vantaggio non viene sfruttato. Fortunatamente, ci sono due modi noti per migliorare questo aspetto.

Il primo miglioramento è stato proposto da Schmidt et al., che sfrutta la semplicità del processo di aggiornamento e implementa una variante del calcolo "al volo" in modo tale che il costo di ciascuna iterazione sia proporzionale al numero di valori diversi da zero elementi.Prendendo SAG come esempio (ma questo approccio funziona per tutte le varianti), questo viene fatto non memorizzando il vettore completo dopo ogni iterazione $la_{io lo so}$ , ma calcola solo quelli corrispondenti a elementi diversi da zero $v_{ik_j}$ , aggiornando ciascuna variabile dall'ultima volta che l'elemento era diverso da zero $v_{ik_j}$ 。

Il secondo metodo di miglioramento è stato proposto da Leblond et al per SAGA, che aggiorna la formula $x_{k+1} = x_k - gamma(nabla f_{ik}(x_k) - nabla f_{ik}(bar{x}_{ik}) + bar{g}_k)$ Viene introdotta ulteriore casualità. Qui, $f_{ik}(x_k)$ E $f_{ik}(bar{x}_{ik})$ è scarso e $bar{g}_k$ è denso.In questo metodo, il termine denso $(bar{g}_k)_j$ Ogni componente di è sostituito da $w_j (bar{g}_k)_j$ ,In $mathbb{R}^d$ è un vettore sparso casuale il cui insieme di supporto è contenuto $f_{ik}(x_k)$ , e dovrebbe essere un vettore costante con tutti gli elementi uguali a 1. In questo modo, il processo di aggiornamento rimane imparziale (anche se ora scarso) e l’aumento della varianza non influisce sul tasso di convergenza dell’algoritmo. Maggiori dettagli sono forniti da Leblond et al.

Di seguito sono riportate formule e variabili matematiche espresse in formato Markdown:

pendenza: $f_i(x)$
Aggiornamento SGD: $x_{k+1} = x_k - gamma(nabla f_{ik}(x_k) - nabla f_{ik}(bar{x}_{ik}) + bar{g}_k)$
Gradiente sparso: $f_{ik}(x_k)$ E $f_{ik}(bar{x}_{ik})$
Gradiente denso: $bar{g}_k$
Vettori sparsi casuali: $io$
Si aspetta un vettore costante: un vettore con tutti gli elementi uguali a 1.

Condivisione della tecnologia