[Deep Learning] Grundlagen grafischer Modelle (7): Varianzreduktionsmethode bei der Optimierung maschinellen Lernens (1)

[Deep Learning] Grundlagen des grafischen Modells (7): Varianzreduktionsmethode bei der Optimierung des maschinellen Lernens (1)

2024-07-12

Zusammenfassung

Die stochastische Optimierung ist ein wesentlicher Bestandteil des maschinellen Lernens. Ihr Kernstück ist der stochastische Gradientenabstiegsalgorithmus (SGD), eine Methode, die seit ihrer ersten Einführung vor mehr als 60 Jahren weit verbreitet ist. In den letzten acht Jahren haben wir eine aufregende neue Entwicklung erlebt: Varianzreduktionstechniken für stochastische Optimierungsmethoden. Diese Varianzreduktionsmethoden (VR-Methoden) funktionieren gut in Szenarien, die mehrere Iterationen der Trainingsdaten ermöglichen, und zeigen sowohl in der Theorie als auch in der Praxis eine schnellere Konvergenz als SGD. Diese Geschwindigkeitssteigerung verdeutlicht das wachsende Interesse an VR-Methoden und die rasch wachsende Forschungsleistung in diesem Bereich. In diesem Artikel werden die wichtigsten Prinzipien und großen Fortschritte bei VR-Methoden zur Optimierung begrenzter Datensätze besprochen, mit dem Ziel, auch nicht fachkundige Leser zu informieren. Wir konzentrieren uns hauptsächlich auf konvexe Optimierungsumgebungen und bieten eine Referenz für Leser, die an Erweiterungen zur Minimierung nichtkonvexer Funktionen interessiert sind.

Schlüsselwörter |. Maschinelles Lernen; Varianzreduzierung

1. Einleitung

Im Bereich der maschinellen Lernforschung ist eine grundlegende und wichtige Frage die Frage, wie Modelle an große Datenmengen angepasst werden können. Beispielsweise können wir den typischen Fall eines linearen Modells der kleinsten Quadrate betrachten:

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

In diesem Modell haben wir $D$ Parameter, die durch Vektoren dargestellt werden $mathbb{R}^d$ gegeben.In der Zwischenzeit haben wir zur Hand $N$ Datenpunkte, einschließlich Merkmalsvektoren $a_i in mathbb{R}^d$ und Zielwert $b_i in mathbb{R}$ .Der Anpassungsprozess des Modells besteht darin, diese Parameter so anzupassen, dass sie der vorhergesagten Ausgabe des Modells entsprechen $a_i^T x$ im Durchschnitt möglichst nah am Zielwert liegen $b_i$ 。

Im weiteren Sinne könnten wir eine Verlustfunktion verwenden $f_i(x)$ Um die Modellvorhersagen zu messen und die $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch$ Wie nah sind die Datenpunkte:

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

verlustfunktion $f_i(x)$ Wenn es größer ist, bedeutet dies, dass die Vorhersagen des Modells stark von den Daten abweichen $f_i(x)$ Bei einem Wert von Null passt das Modell perfekt zu den Datenpunkten.Funktion $F (X)$ Spiegelt den durchschnittlichen Verlust des Modells über den gesamten Datensatz wider.

Probleme wie Form (2) oben gelten nicht nur für lineare Kleinste-Quadrate-Probleme, sondern auch für viele andere Modelle, die im maschinellen Lernen untersucht werden. In einem logistischen Regressionsmodell lösen wir beispielsweise nach:

$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$

Hier geht es um $b_i in {-1, +1}$ Bei einem binären Klassifizierungsproblem basiert die Vorhersage auf $a_i^T x$ Symbole.In die Formel wird auch ein Regularisierungsterm eingeführt $|x|_2^2$ um eine Überanpassung der Daten zu vermeiden, wo $x|_2^2$ äußern $X$ Das Quadrat der euklidischen Norm von .

In den meisten überwachten Lernmodellen kann der Trainingsprozess als Form (2) ausgedrückt werden, einschließlich L1-regularisierter kleinster Quadrate, Support Vector Machine (SVM), Hauptkomponentenanalyse, bedingter Zufallsfelder und tiefer neuronaler Netze usw.

Eine zentrale Herausforderung bei modernen Problemfällen ist die Anzahl der Datenpunkte $N$ Wahrscheinlich extrem groß. Wir haben es oft mit Datensätzen zu tun, die weit über den Terabyte-Bereich hinausgehen und aus so unterschiedlichen Quellen wie dem Internet, Satelliten, Fernsensoren, Finanzmärkten und wissenschaftlichen Experimenten stammen können. Um solch große Datensätze zu verarbeiten, besteht ein gängiger Ansatz darin, den stochastischen Gradientenabstiegsalgorithmus (SGD) zu verwenden, der in jeder Iteration nur eine kleine Anzahl zufällig ausgewählter Datenpunkte verwendet. Darüber hinaus ist in letzter Zeit das Interesse an stochastischen Gradientenmethoden zur Varianzreduktion (VR) stark gestiegen, die schnellere Konvergenzraten aufweisen als herkömmliche stochastische Gradientenmethoden.
Fügen Sie hier eine Bildbeschreibung ein
Abbildung 1. Das logistische Regressionsproblem basiert auf dem Pilzdatensatz [7], dem Gradientenabstieg (GD), dem beschleunigten Gradientenabstieg (AGD, beschleunigter GD in [50]), dem stochastischen Gradientenabstieg (SGD) und der ADAM-Methode [30]. verglichen mit den Varianzreduktionsmethoden (VR) SAG und SVRG, wobei n = 8124, d = 112.

1.1. Gradienten- und stochastische Gradientenabstiegsmethoden

Der Gradientenabstieg (GD) ist ein klassischer Algorithmus zur Lösung des obigen Problems (2) und seine iterative Aktualisierungsformel lautet wie folgt:
$x_{k+1} = x_k - gamma frac{1}{n} sum_{i=1}^{n} nabla f_i(x_k)$

Hier, $γ$ ist ein fester Schrittwert größer als Null.Während jeder Iteration des GD-Algorithmus muss jeder Datenpunkt vorhanden sein $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch$ Steigung berechnen $f_i(x_k)$ , was bedeutet, dass GD alles erfordert $N$ Führen Sie eine vollständige Durchquerung der Datenpunkte durch.Wenn die Größe des Datensatzes $N$ Wenn es sehr groß wird, werden die Kosten jeder Iteration des GD-Algorithmus sehr hoch, wodurch seine Anwendung eingeschränkt wird.

Als Alternative können wir die Methode des stochastischen Gradientenabstiegs (SGD) in Betracht ziehen, die erstmals von Robbins und Monro vorgeschlagen wurde und deren iterative Aktualisierungsformel wie folgt lautet:
$x_{k+1} = x_k - gamma nabla f_{i_k}(x_k)$

Der SGD-Algorithmus funktioniert, indem er in jeder Iteration nur den Gradienten eines zufällig ausgewählten Datenpunkts verwendet. $f_{i_k}(x_k)$ um die Kosten jeder Iteration zu reduzieren. In Abbildung 1 können wir sehen, dass SGD in den frühen Phasen des Optimierungsprozesses größere Fortschritte erzielt als GD (einschließlich beschleunigter GD-Methoden).Die Grafik zeigt den Fortschritt der Optimierung in Bezug auf Epochen, die als Berechnung aller definiert sind $N$ Die Anzahl der Farbverläufe für Trainingsbeispiele. Der GD-Algorithmus führt in jeder Runde eine Iteration durch, während der SGD-Algorithmus in jeder Runde eine Iteration durchführt $N$ Iterationen.Wir verwenden Runden als Grundlage für den Vergleich von SGD und GD, da davon ausgegangen wird $N$ In sehr großen Fällen konzentrieren sich die Hauptkosten beider Methoden auf den Gradienten $f_i(x_k)$ Berechnung.

1.2. Varianzproblem

Betrachten wir die zufällige Indizierung $ich_k$ aus der Sammlung ${1, \dots, N}$ Im Falle einer einheitlichen Zufallsauswahl bedeutet dies: für alle $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch$ ,wählen $i_k = ich$ Die Wahrscheinlichkeit $P[i_k = i]$ gleich $1 n frac{1}{n}$ . in diesem Fall, $f_{i_k}(x_k)$ als $f(x_k)$ Der Schätzer von ist erwartungstreu, weil wir nach der Definition der Erwartung Folgendes haben:
$f_{i_k}(x_k) | x_k] = frac{1}{n} sum_{i=1}^{n} nabla f_i(x_k) = nabla f(x_k) quad (6)$

Obwohl die SGD-Methode (Stochastic Gradient Descent) nicht die Funktion in jeder Iteration garantiert $F$ Der Wert von wird abnehmen, aber im Durchschnitt bewegt er sich in Richtung des negativen Vollgradienten, der die Abwärtsrichtung darstellt.

Allerdings reicht ein unverzerrter Gradientenschätzer nicht aus, um die Konvergenz der SGD-Iterationen sicherzustellen. Um diesen Punkt zu veranschaulichen, zeigt Abbildung 2 (links) den iterativen Verlauf von SGD bei Anwendung einer logistischen Regressionsfunktion mit einer konstanten Schrittgröße auf den von LIBSVM bereitgestellten Datensatz mit vier Kategorien [7].Die konzentrischen Ellipsen in der Abbildung stellen die Konturen der Funktion dar, also den Funktionswert $F (X) = C$ entsprechenden Punkt $X$ versammeln, $C$ ist eine bestimmte Konstante in der Menge der reellen Zahlen.verschiedene konstante Werte $C$ Entspricht verschiedenen Ellipsen.

Die iterative Trajektorie von SGD konvergiert nicht zur optimalen Lösung (in der Abbildung durch ein grünes Sternchen gekennzeichnet), sondern bildet eine Punktwolke um die optimale Lösung. Im Gegensatz dazu zeigen wir in Abbildung 2 die iterative Trajektorie einer Varianzreduktionsmethode (VR), des stochastischen Durchschnittsgradienten (SAG), unter Verwendung derselben konstanten Schrittgröße, die wir später vorstellen werden. Der Grund dafür, dass SGD in diesem Beispiel nicht konvergiert, liegt darin, dass der stochastische Gradient selbst nicht gegen Null konvergiert und daher die SGD-Methode mit konstantem Schritt (5) niemals stoppt.Dies steht in krassem Gegensatz zu Gradientenabstiegsmethoden (GD), die natürlicherweise aufhören $x_k$ Ansätze $x^*$ ,Gradient $f(x_k)$ wird gegen Null tendieren.
Fügen Sie hier eine Bildbeschreibung ein
Abbildung 2. Level-Set-Diagramme für die zweidimensionale logistische Regression unter Verwendung der iterativen Methoden SGD (links) und SAG (rechts) mit festem Schritt. Ein grüner Stern zeigt x anlösen.

1.3. Klassische Varianzreduktionsmethode

Verarbeitung aufgrund $f_i(x_k)$ Es gibt mehrere klassische Techniken für Nichtkonvergenzprobleme, die durch die Varianz von Werten verursacht werden.Beispielsweise verwenden Robbins und Monro [64] eine Reihe abnehmender Schritte $gamma_k$ Um das Varianzproblem zu lösen, stellen Sie sicher, dass das Produkt $gamma_k nabla f_{i_k}(x_k)$ gegen Null konvergieren kann. Es ist jedoch ein schwieriges Problem, diese Abfolge abnehmender Schritte anzupassen, um zu vermeiden, dass der Algorithmus zu früh oder zu spät gestoppt wird.

Eine weitere klassische Technik zur Reduzierung der Varianz ist die Verwendung mehrerer $f_i(x_k)$ Durchschnitt, um den vollen Gradienten zu erhalten $\nabla F (X)$ eine genauere Schätzung. Dieser Ansatz wird Minibatch genannt und ist besonders nützlich, wenn mehrere Gradienten parallel ausgewertet werden können. Dies führt zu einer Iteration der Form:
$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$ ist ein zufälliger Indexsatz, $B_k|$ äußern $B_k$ die Größe von.Wenn $B_k$ Bei gleichmäßiger Probenahme und Ersetzung hängt die Varianz dieser Gradientenschätzung mit der „Chargengröße“ zusammen. $B_k|$ ist umgekehrt proportional, sodass die Varianz durch Erhöhen der Chargengröße verringert werden kann.

Allerdings sind die Kosten solcher Iterationen proportional zur Stapelgröße, sodass diese Form der Varianzreduzierung mit einem erhöhten Rechenaufwand verbunden ist.

Eine weitere gängige Strategie zur Verringerung der Varianz und zur Verbesserung der empirischen Leistung von SGD besteht darin, „Momentum“ hinzuzufügen, einen zusätzlichen Begriff, der auf der in den vorherigen Schritten verwendeten Richtung basiert. Insbesondere ist die Form von SGD mit Impuls wie folgt:
$x_{k+1} = x_k - gamma m_k quad (9)$
wo der Impulsparameter $β$ Liegt im Bereich (0, 1).Wenn der anfängliche Schwung $m_0 = 0$ , und erweitern Sie in (8) $m_k$ Für Updates erhalten wir $m_k$ ist der gewichtete Durchschnitt vorheriger Farbverläufe:
$m_k = Summe_{t=0}^{k} beta^{kt} nabla f_{i_t}(x_t) quad (10)$
daher, $m_k$ ist die gewichtete Summe stochastischer Gradienten.Weil $Summe_{t=0}^{k} beta^{kt} = frac{1 - beta^{k+1}}{1 - beta}$ , wir können konvertieren $beta^k} m_k$ Wird als gewichteter Durchschnitt stochastischer Gradienten betrachtet.Vergleichen wir dies mit dem Ausdruck für den gesamten Gradienten $f(x_k) = frac{1}{n} sum_{i=1}^{n} nabla f_i(x_k)$ Zum Vergleich können wir $beta^k} m_k$ (sowie $m_k$ ) wird als Schätzung des gesamten Gradienten interpretiert. Während diese gewichtete Summe die Varianz verringert, wirft sie auch wichtige Fragen auf.Da die gewichtete Summe (10) den kürzlich abgetasteten Gradienten mehr Gewicht verleiht, konvergiert sie nicht zum vollständigen Gradienten $f(x_k)$ Letzteres ist ein einfacher Durchschnitt. Die erste Varianzreduktionsmethode, die wir in Abschnitt II-A sehen werden, löst dieses Problem, indem sie einen einfachen Durchschnitt anstelle eines gewichteten Durchschnitts verwendet.

1.4. Moderne Varianzreduktionsmethoden

Im Gegensatz zu klassischen Methoden verwenden sie direkt eine oder mehrere $f_i(x_k)$ als $f(x_k)$ Als Näherungswert verwenden moderne Methoden zur Varianzreduktion (VR) eine andere Strategie.Diese Methoden verwenden $f_i(x_k)$ um die Gradientenschätzung zu aktualisieren $g_k$ , dessen Ziel es ist, zu machen $g_k$ Ansatz $f(x_k)$ .Konkret hoffen wir $g_k$ befriedigen können $g_k ungefähr nabla f(x_k)$ . Basierend auf solchen Gradientenschätzungen führen wir dann einen ungefähren Gradientenschritt der Form durch:
$x_{k+1} = x_k - gamma g_k quad (11)$
Hier $γ > 0$ ist der Schrittgrößenparameter.

Um sicherzustellen, dass eine konstante Schrittgröße verwendet wird $γ$ Wenn Iteration (11) konvergieren kann, müssen wir sicherstellen, dass der Gradient geschätzt wird $g_k$ Die Varianz tendiert gegen Null. Mathematisch lässt sich dies wie folgt ausdrücken:
$g_k - nabla f(x_k) |^2 right] rightarrow 0 quad text{als } k rightarrow infty quad (12)$
Erwartungen hier $E$ basiert auf dem Algorithmus bis zum $k$ Alle Zufallsvariablen werden für Iterationen berechnet. Eigenschaft (12) sorgt dafür, dass die VR-Methode gestoppt werden kann, wenn die optimale Lösung erreicht ist. Wir betrachten diese Immobilie als charakteristisches Merkmal des VR-Ansatzes und bezeichnen sie daher als VR-Immobilie. Es ist erwähnenswert, dass der Ausdruck „reduzierte“ Varianz irreführend sein kann, da die Varianz tatsächlich gegen Null tendiert. Eigenschaft (12) ist ein Schlüsselfaktor, der es VR-Methoden ermöglicht, in der Theorie (unter geeigneten Annahmen) und in der Praxis (wie in Abbildung 1 dargestellt) eine schnellere Konvergenz zu erreichen.

1.5. Erstes Beispiel einer Varianzreduktionsmethode: SGD²

Eine einfache Verbesserungsmethode kann dazu führen, dass die rekursive SGD-Formel (5) Konvergenz erreicht, ohne die Schrittgröße zu verringern, dh jeden Gradienten zu übersetzen. Die spezifische Methode besteht darin, zu subtrahieren $f_i(x^*)$ , diese Methode ist wie folgt definiert:
$x_{k+1} = x_k - gamma (nabla f_{i_k}(x_k) - nabla f_{i_k}(x^*)) quad (13)$
Diese Methode wird SGD² genannt [22].Obwohl wir normalerweise nicht alles genau wissen können $f_i(x^*)$ , aber SGD² kann als Beispiel die grundlegenden Eigenschaften der Varianzreduktionsmethode gut veranschaulichen.Darüber hinaus können viele Varianzreduktionsmethoden als Näherungsform der SGD²-Methode angesehen werden; diese Methoden basieren nicht auf dem Bekannten $f_i(x^*)$ , sondern verwenden Sie stattdessen eine Methode, die näherungsweise möglich ist $f_i(x^*)$ geschätzter Wert.

Es ist erwähnenswert, dass SGD² eine unvoreingenommene Schätzung des gesamten Gradienten verwendet.Weil $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)$
Wenn SGD² außerdem die optimale Lösung erreicht, wird es für jeden natürlich gestoppt $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch$ ,haben:
$f_i(x) - nabla f_i(x^*)) bigg|_{x=x^*} = 0$

Bei weiterer Beobachtung mit $x_k$ nahe $x^*$ (für aufeinanderfolgende $f_i$ ), SGD² erfüllt die Varianzreduktionseigenschaft (12), weil:
$g_k - nabla f(x_k) |^2 rechts] = \Elinks[ | nabla f_{i_k}(x_k) - nabla f_{i_k}(x^*) - nabla f(x_k) |^2 rechts] leq Elinks[ | nabla f_{i_k}(x_k) - nabla f_{i_k}(x^*) |^2 rechts]$
Hier verwenden wir Lemma 2, let $f_{i_k}(x_k) - nabla f_{i_k}(x^*)$ , und ausgenutzt $f_{i_k}(x_k) - nabla f_{i_k}(x^*)] = nabla f(x_k)$ Natur. Diese Eigenschaft weist darauf hin, dass SGD² eine schnellere Konvergenzgeschwindigkeit aufweist als herkömmliche SGD-Methoden, die wir in Anhang B detailliert beschrieben haben.

1.6. Schnelle Konvergenz der Varianzreduktionsmethode

In diesem Abschnitt stellen wir zwei Standardannahmen vor, die zur Analyse der Varianzreduktionsmethode (VR) verwendet werden, und diskutieren den Beschleunigungseffekt, der unter diesen Annahmen im Vergleich zur herkömmlichen SGD-Methode erzielt werden kann. Zunächst gehen wir davon aus, dass der Gradient Lipschitz-Stetigkeit aufweist, was bedeutet, dass die Änderungsrate des Gradienten endlich ist.

Annahme 1 (Lipschitz-Stetigkeit)

Wir gehen davon aus, dass die Funktion $F$ ist differenzierbar und ist $M$ - glatt, für alle $X$ Und $j$ und jemand $0 < M < \infty$ ,Die folgenden Bedingungen:
$∥\nabla F (X) - \nabla F (j) ∥ \leq M ∥ X - j ∥ (14)$
Das bedeutet, dass jeder $mathbb{R}^d rightarrow mathbb{R}$ ist differenzierbar, $L_i$ - glatt, wir definieren $L_{text{max}}$ für $max{L_1, . . . , L_n}$ 。

Obwohl dies im Allgemeinen als schwache Annahme angesehen wird, werden wir in den folgenden Kapiteln VR-Methoden diskutieren, die für nicht glatte Probleme geeignet sind. Für eine zweifach differenzierbare univariate Funktion gilt: $M$ -Glätte kann intuitiv verstanden werden als: Dies entspricht der Annahme, dass die zweite Ableitung vorhanden ist $M$ Obergrenze also $∣ F^{''} (X) ∣ \leq M$ für alle $mathbb{R}^d$ .Für zweimal differenzierbare Funktionen mehrerer Variablen entspricht dies der Annahme einer Hesse-Matrix $nabla^2 f(x)$ Der singuläre Wert von $M$ Höchstgrenze.

Annahme 2 (starke Konvexität)

Die zweite Hypothese, die wir betrachten, ist, dass Funktion (f) ist $μ$ -Stark konvex, was mit Sicherheit bedeutet $μ > 0$ ,Funktion $frac{mu}{2}|x|^2 abgebildet.$ Es ist konvex.Darüber hinaus für jeden $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch = 1, ..., N$ ， $mathbb{R}^d rightarrow mathbb{R}$ Es ist konvex.

Dies ist eine starke Annahme.Beim Problem der kleinsten Quadrate ist jedes (fi$ konvex, aber die Gesamtfunktion (f) ist nur in der Entwurfsmatrix enthalten $A := [a_1, . . . , a_n]$ Es ist nur dann stark konvex, wenn es einen perfekten Zeilenrang hat. Das Problem der regulierten logistischen L2-Regression erfüllt diese Annahme aufgrund der Existenz des Regularisierungsterms wo $μ \geq λ$ 。

Eine wichtige Klasse von Problemen, die diese Annahmen erfüllen, sind Optimierungsprobleme der Form:
$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)$
wo jede „Verlust“-Funktion $ell_i : mathbb{R} rightarrow mathbb{R}$ ist zweimal differenzierbar und seine zweite Ableitung $ell_i''$ ist auf 0 und eine gewisse Obergrenze beschränkt $M$ zwischen. Dazu gehören eine Vielzahl von Verlustfunktionen mit L2-Regularisierung beim maschinellen Lernen, wie z. B. kleinste Quadrate, logistische Regression, Probit-Regression, robuste Huber-Regression usw.In diesem Fall für alle $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch$ ,Wir haben $L_i leq M|a_i|^2 + lambda$ Und $μ \geq λ$ 。

Unter diesen Annahmen wird die Konvergenzrate der Gradientenabstiegsmethode (GD) durch die Bedingungszahl bestimmt $κ := M / μ$ Entscheiden. Die Bedingungszahl ist immer größer oder gleich 1, und wenn sie deutlich größer als 1 ist, werden die Konturen der Funktion sehr elliptisch, was dazu führt, dass die Iterationen der GD-Methode oszillieren.Im Gegenteil, wann $κ$ Wenn es nahe bei 1 liegt, konvergiert die GD-Methode schneller.

Unter den Annahmen 1 und 2 konvergiert die VR-Methode linear.Wir sagen, dass der Funktionswert einer Zufallsmethode ({f(x_k)}) gegeben ist durch $0 < ρ \leq 1$ Die Rate der linearen Konvergenz (unter Erwartung), sofern eine Konstante vorhanden ist $C > 0$ Macht:
$E[f(x_k)] - f(x^*) leq (1 - rho)^k C = O(exp(-krho)) quad für alle k quad (16)$
Dies steht im Gegensatz zu klassischen SGD-Methoden, die nur auf unvoreingenommenen Schätzungen des Gradienten bei jeder Iteration basieren und unter diesen Annahmen nur sublineare Raten erhalten:
$E[f(x_k)]−f(x^*)leqO(1/k)$
Das Minimum, das diese Ungleichung erfüllt $k$ Sie wird als iterative Komplexität des Algorithmus bezeichnet. Im Folgenden sind die iterative Komplexität und die Kosten einer Iteration für Grundvarianten der GD-, SGD- und VR-Methoden aufgeführt:

Algorithmus	Anzahl der Iterationen	Kosten einer Iteration
GD	$Ö (κ siehe G (1/ ϵ))$	$Ö (N)$
SGD	$O(kappa_{text{max}} max(1/epsilon))$	$Ö (1)$
VR	$O((kappa_{text{max}} + n) log(1/epsilon))$	$Ö (1)$

Die Gesamtlaufzeit eines Algorithmus wird durch das Produkt aus Iterationskomplexität und Iterationslaufzeit bestimmt.hier verwendet $kappa_{text{max}} := max_i L_i/mu$ .Beachten $kappa_{text{max}} geq kappa$ ; Daher ist die Iterationskomplexität von GD kleiner als die der VR-Methode.

Da jedoch die Kosten pro Iteration von GD denen der VR-Methode entsprechen $N$ Mal ist die VR-Methode hinsichtlich der Gesamtlaufzeit überlegen.

Der Vorteil klassischer SGD-Methoden besteht darin, dass ihre Laufzeit und Konvergenzrate nicht davon abhängen $N$ , aber es hat eine Toleranz $ϵ$ Die Abhängigkeit von ist viel schlimmer, was die schlechte Leistung von SGD erklärt, wenn die Toleranz gering ist.

In Anhang B liefern wir einen einfachen Beweis, der zeigt, dass die SGD²-Methode die gleiche iterative Komplexität aufweist wie die VR-Methode.

2. Grundlegende Varianzreduktionsmethode

Die Entwicklung von Varianzreduktionsmethoden (VR) hat mehrere Phasen durchlaufen, und die ersten Methoden führten zu deutlich verbesserten Konvergenzraten. Den Anfang dieser Methodenreihe bildet der SAG-Algorithmus. Anschließend kamen nacheinander der stochastische Dual-Koordinaten-Aufstiegsalgorithmus (SDCA), der MISO-Algorithmus, der stochastische Varianzreduktionsgradienten-Algorithmus (SVRG/S2GD) und der SAGA-Algorithmus (was „verbesserter“ SAG) bedeutet.

In diesem Kapitel werden wir diese bahnbrechenden VR-Methoden detailliert beschreiben. In Kapitel 4 werden wir einige neuere Methoden untersuchen, die in bestimmten Anwendungsszenarien überlegene Eigenschaften im Vergleich zu diesen Basismethoden aufweisen.

2.1. Stochastische Durchschnittsgradientenmethode (SAG)

Unsere Untersuchung der ersten Methode zur Varianzreduktion (VR) beginnt mit der Nachahmung der vollständigen Gradientenstruktur.Da das komplette Gefälle $\nabla F (X)$ ist Alles $f_i(x)$ Ein einfacher Durchschnitt der Gradienten, dann unsere Schätzung des gesamten Gradienten $g_k$ Es sollte auch der Durchschnitt dieser Gradientenschätzungen sein. Aus dieser Idee entstand unsere erste VR-Methode: die SAG-Methode (Stochastic Average Gradient).

Die SAG-Methode [37], [65] ist eine randomisierte Version der frühen inkrementellen aggregierten Gradientenmethode (IAG) [4]. Die Kernidee von SAG besteht darin, für jeden Datenpunkt zu sorgen $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch$ einen Kostenvoranschlag beibehalten $v_{ik} ungefähr nabla f_i(x_k)$ .Dann nutzen Sie diese $v_{ik}$ Der Durchschnitt der Werte wird als Schätzung des gesamten Gradienten verwendet, das heißt:
$bar{g}_k = frac{1}{n} sum_{j=1}^{n} v_{jk} approximativ frac{1}{n} sum_{j=1}^{n} nabla f_j(x_k) = nabla f(x_k) quad (18)$

In jeder Iteration von SAG aus dem Satz ${1, \dots, N}$ Extrahieren Sie einen Index aus $ich_k$ , und dann gemäß den folgenden Regeln aktualisiert $v_{jk}$ ：
$begin{cases} nabla f_{i_k}(x_k), & text{if } j = i_k \ v_{jk}^k, & text{if } j neq i_k end{cases}$
Unter ihnen jeder $v_{0i}$ Kann auf Null oder initialisiert werden $f_i(x_0)$ ungefährer Wert.Mit der Lösung $x^*$ Annäherung, jeweils $v_{ik}$ wird sich allmählich annähern $f_i(x^*)$ , wodurch die VR-Eigenschaft (12) erfüllt wird.

Um SAG effizient umzusetzen, müssen wir auf die Berechnung achten $Strich{g}_k$ um zu vermeiden, dass die Summe jedes Mal von vorne beginnt $N$ Vektor, denn das ist $N$ Die Kosten sind hoch, wenn es groß ist.Zum Glück, da jede Iteration nur eine hat $v_{ik}$ Die Bedingungen ändern sich und wir müssen nicht jedes Mal die gesamte Summe neu berechnen.Nehmen Sie insbesondere an, dass dies beim Iterieren der Fall ist $k$ Index extrahiert aus $ich_k$ , dann ist da:
$bar{g}_k = frac{1}{n} sum_{substack{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)$

Da zusätzlich zu $v_{i_k}$ alles außer $v_{jk}$ Die Werte bleiben alle gleich, wir speichern sie einfach $J$ Ein Vektor, der entspricht $v_j$ . Algorithmus 1 zeigt die spezifische Implementierung der SAG-Methode.

SAG ist die erste stochastische Methode, die eine lineare Konvergenz erreicht, und ihre Iterationskomplexität ist hoch $O((kappa_{text{max}} + n) log(1/epsilon))$ , unter Verwendung der Schrittweite $O(1/L_{text{max}})$ . Diese lineare Konvergenz ist in Abbildung 1 zu beobachten.Es ist erwähnenswert, dass aufgrund $L_{text{max}}$ -Smooth-Funktion für alle $L_{text{max}}$ Zu $M^{'}$ - Glatte SAG-Methoden erreichen lineare Konvergenzraten für ausreichend kleine Schrittgrößen, im Gegensatz zu klassischen SGD-Methoden, die nur sublineare Raten mit Sequenzen abnehmender Schrittgrößen erreichen, die in der Praxis schwer anzupassen sind.

Zu dieser Zeit stellte die lineare Konvergenz von SAG einen erheblichen Fortschritt dar, da in jeder Iteration nur ein stochastischer Gradient (Verarbeitung eines einzelnen Datenpunkts) berechnet wurde. Der von Schmidt et al. [65] bereitgestellte Konvergenznachweis ist jedoch sehr komplex und basiert auf computerverifizierten Schritten. Ein wesentlicher Grund, warum SAG schwierig zu analysieren ist, ist dieser $g_k$ ist eine voreingenommene Schätzung des Gradienten.

Als Nächstes stellen wir die SAGA-Methode vor, eine Variante von SAG, die das Konzept der Kovariaten nutzt, um eine unvoreingenommene Variante der SAG-Methode zu erstellen, die eine ähnliche Leistung bietet, aber einfacher zu analysieren ist.

Algorithmus 1: SAG-Methode

Parameter: Schrittgröße $γ > 0$
Initialisierung: $x_0$ ， $v_i = 0 in mathbb{R}^d$ für $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch = 1, \dots, N$
Rechts $k = 1, \dots, T - 1$ implementieren:
a. Zufällige Auswahl $i_k in {1, ldots, n}$
b. Berechnen $bar{g}_k = bar{g}_{k-1} - frac{1}{n} v_{i_k}^{k-1}$
c. Aktualisieren $v_{i_k}^k = nabla f_{i_k}(x_k)$
d. Gradientenschätzung aktualisieren $bar{g}_k = bar{g}_k + frac{1}{n} v_{i_k}^k$
e. Aktualisieren $x_{k+1} = x_k - gamma bar{g}_k$
Ausgabe: $x_T$

2.2.SAGA-Methode

Eine reduzierte grundlegende unvoreingenommene Gradientenschätzung $f_{i_k}(x_k)$ Der Varianzansatz erfolgt durch die Verwendung sogenannter Kovariaten oder Kontrollvariablen.für $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch = 1, \dots, N$ ,aufstellen $v_i in mathbb{R}^d$ ist ein Vektor.Mithilfe dieser Vektoren können wir den gesamten Farbverlauf umwandeln $\nabla F (X)$ Umgeschrieben als:
$sum_{i=1}^{n}(nabla f_i(x) - v_i + v_i) = frac{1}{n} sum_{i=1}^{n} nabla f_i(x) - v_i + frac{1}{n} sum_{j=1}^{n} v_j$
$sum_{i=1}^{n} nabla f_i(x, v) quad (21)$
was definiert $f_i(x, v) := nabla f_i(x) - v_i + frac{1}{n} sum_{j=1}^{n} v_j$ .Jetzt können wir a zufällig auswählen $f_i(x, v)$ um den vollständigen Gradienten zu konstruieren $\nabla F (X)$ Eine unvoreingenommene Schätzung von $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch \in {1, \dots, N}$ , können Sie die SGD-Methode anwenden und die Gradientenschätzung verwenden:
$g_k = nabla f_{i_k}(x_k, v) = nabla f_{i_k}(x_k) - v_{i_k} + frac{1}{n} sum_{j=1}^{n} v_j quad (22)$

zur Beobachtung $v_i$ Der Auswahlpaarunterschied $g_k$ Einfluss nehmen können wir $g_k = nabla f_{i_k}(x_k, v)$ Ersetzen und verwenden $E_i sim frac{1}{n}[v_i] = frac{1}{n} sum_{j=1}^{n} v_j$ Um den Erwartungswert zu berechnen, erhalten wir:
$f_i(x_k) - v_i + E_i sim frac{1}{n}[v_i - nabla f_i(x_k)]|^2 rechts] leq E links[ |nabla f_i(x_k) - v_i|^2 rechts] quad (23)$
Hier wird Lemma 2 verwendet, wo $f_i(x_k) - v_i$ .Diese Schranke (23) zeigt, dass if $v_i$ zusammen mit $k$ Der Anstieg liegt nahe bei $f_i(x_k)$ , können wir VR-Attribute (12) erhalten.Deshalb rufen wir an $v_i$ sind Kovariaten, und wir können sie auswählen, um die Varianz zu reduzieren.

Dieser Ansatz wird beispielsweise auch durch die SGD²-Methode (13) umgesetzt, wobei $v_i = nabla f_i(x^*)$ .Dies wird jedoch in der Praxis nicht häufig verwendet, da wir es normalerweise nicht wissen $f_i(x^*)$ .Eine praktischere Option ist $v_i$ wie wir wissen $bar{x}_i in mathbb{R}^d$ nahegelegenes Gefälle $f_i(bar{x}_i)$ . SAGA für jede Funktion $f_i$ Verwenden Sie einen Referenzpunkt $bar{x}_i in mathbb{R}^d$ und verwenden Sie Kovariaten $v_i = nabla f_i(bar{x}_i)$ , von denen jedes $Strich{x}_i$ wird unsere letzte Einschätzung sein $f_i$ Punkt. Unter Verwendung dieser Kovariaten können wir nach (22) eine Gradientenschätzung erstellen, die Folgendes ergibt:
$g_k = nabla f_{i_k}(x_k) - nabla f_{i_k}(bar{x}_{i_k}) + frac{1}{n} sum_{j=1}^{n} nabla f_j(bar{x}_j) quad (24)$

Um SAGA zu implementieren, können wir Farbverläufe speichern $f_i(bar{x}_i)$ anstatt $N$ Anhaltspunkt $Strich{x}_i$ .Das heißt, nehmen wir an $v_j = nabla f_j(bar{x}_j)$ für $J \in {1, \dots, N}$ In jeder Iteration aktualisieren wir einen stochastischen Gradienten wie SAG $v_j$ 。

Algorithmus 2 SAGA

Parameter: Schrittgröße $γ > 0$
Initialisierung: $x_0$ ， $v_i = 0 in mathbb{R}^d$ für $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch = 1, \dots, N$
Benehmen $k = 1, \dots, T - 1$ Iterationen:
a. Zufällige Auswahl $i_k in {1, ldots, n}$
b. Alten Wert speichern $v_{text{alt}} = v_{i_k}$
c. Aktualisieren $v_{i_k} = nabla f_{i_k}(x_k)$
d. Aktualisieren $x_{k+1} = x_k - gamma (v_{i_k} - v_{text{alt}} + bar{g}_k)$
e. Gradientenschätzung aktualisieren $bar{g}_k = bar{g}_{k-1} + frac{1}{n} (v_{i_k} - v_{text{alt}})$
Ausgabe: $x_T$

Die SAGA-Methode hat die gleiche Iterationskomplexität wie SAG $O((kappa_{text{max}} + n) log(1/epsilon))$ , unter Verwendung der Schrittweite $O(1/L_{text{max}})$ , aber der Beweis ist viel einfacher.Allerdings erfordert die SAGA-Methode wie SAG eine Speicherung $N$ Hilfsvektoren $v_i in mathbb{R}^d$ für $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch = 1, \dots, N$ , was die Notwendigkeit bedeutet $Ö (N D)$ von Stauraum.Wann $D$ Und $N$ Wenn beide groß sind, ist dies möglicherweise nicht möglich. Im nächsten Abschnitt erläutern wir detailliert, wie dieser Speicherbedarf für gängige Modelle wie regulierte lineare Modelle reduziert werden kann.

wenn es möglich ist $N$ Wenn zwei Hilfsvektoren im Speicher gespeichert sind, verhalten sich SAG und SAGA tendenziell ähnlich. Wenn dieser Speicherbedarf zu hoch ist, ist die SVRG-Methode, die wir im nächsten Abschnitt besprechen, eine gute Alternative. Die SVRG-Methode erreicht die gleiche Konvergenzrate und ist in der Praxis oft fast genauso schnell, benötigt aber nur $Ö (D)$ des Gedächtnisses, für allgemeine Fragen.

2.3.SVRG-Methode

Vor dem Aufkommen der SAGA-Methode wurden in einigen frühen Arbeiten erstmals Kovariaten eingeführt, um das für die SAG-Methode erforderliche Problem des hohen Speichers zu lösen.Diese Studien bauen auf einem festen Bezugspunkt auf $mathbb{R}^d$ Kovariaten haben wir den vollständigen Gradienten an diesem Punkt berechnet $\nabla F (\overset{X}{ˉ})$ .durch die Speicherung von Referenzpunkten $\overset{X}{ˉ}$ und der entsprechende vollständige Gradient $\nabla F (\overset{X}{ˉ})$ , wir können dies tun, ohne jedes einzelne zu speichern $f_j(bar{x})$ Für den Fall, verwenden Sie $Strich{x}_j = Strich{x}$ an alle $J$ um update(24) zu implementieren.Anstatt diese Vektoren zu speichern, verwenden wir insbesondere die gespeicherten Referenzpunkte in jeder Iteration $\overset{X}{ˉ}$ berechnen $f_{i_k}(bar{x})$ . Diese Methode wurde ursprünglich von verschiedenen Autoren unter unterschiedlichen Namen vorgeschlagen, später jedoch als SVRG-Methode vereinheitlicht und folgte der Nomenklatur von [28] und [84].

Wir formalisieren die SVRG-Methode in Algorithmus 3.

Mit (23) können wir die Gradientenschätzung ableiten $g_k$ Die Varianz von ist beschränkt:
$g_k - nabla f(x_k) |^2 rechts] leq Elinks[ | nabla f_i(x_k) - nabla f_i(bar{x}) |^2 rechts] leq L_{text{max}}^2 | x_k - bar{x} |^2$
wobei die zweite Ungleichung jeweils verwendet wird $f_i$ von $L_i$ -Glätte.

Es ist erwähnenswert, dass der Referenzpunkt $\overset{X}{ˉ}$ Je näher am aktuellen Punkt $x_k$ , desto kleiner ist die Varianz der Gradientenschätzung.

Damit die SVRG-Methode effektiv ist, müssen wir die Referenzpunkte regelmäßig aktualisieren $\overset{X}{ˉ}$ (was die Berechnung des gesamten Gradienten erfordert) wird gegen den Vorteil einer verringerten Varianz abgewogen.Aus diesem Grund haben wir alle $T$ Aktualisieren Sie den Referenzpunkt einmal bei jeder Iteration, um ihn in die Nähe zu bringen $x_k$ (Siehe Zeile 11 des Algorithmus II-C).Das heißt, die SVRG-Methode enthält zwei Schleifen: eine äußere Schleife $S$ , wobei der Referenzgradient berechnet wird $f(bar{x}_{s-1})$ (Zeile 4) und eine innere Schleife, in der der Referenzpunkt festgelegt ist und die innere Iteration basierend auf dem stochastischen Gradientenschritt (22) aktualisiert wird. $x_k$ (Zeile 10).

Im Gegensatz zu SAG und SAGA erfordert SVRG nur $Ö (D)$ der Erinnerung. Zu den Nachteilen von SVRG gehören: 1) Wir haben einen zusätzlichen Parameter $T$ , dh die Länge der inneren Schleife, muss angepasst werden. 2) Für jede Iteration müssen zwei Gradienten berechnet werden, und der vollständige Gradient muss jedes Mal berechnet werden, wenn der Referenzpunkt geändert wird.

Johnson und Zhang [28] zeigten, dass SVRG eine iterative Komplexität aufweist $O((kappa_{text{max}} + n) log(1/epsilon))$ , ähnlich SAG und SAGA.Dies ist die Anzahl der Schleifen innerhalb der Hypothese $T$ aus der Sammlung ${1, \dots, M}$ Erhalten unter der Bedingung einer einheitlichen Probenahme, wo $L_{text{max}}$ ， $μ$ , Schrittlänge $γ$ Und $T$ Zwischen ihnen müssen bestimmte Abhängigkeiten erfüllt sein.In der Praxis durch die Verwendung $O(1/L_{text{max}})$ und innere Schleifenlänge $T = N$ , SVRG tendiert dazu, eine gute Leistung zu erbringen, was genau der Einstellung entspricht, die wir in Abbildung 1 verwendet haben.

Mittlerweile gibt es viele Variationen der ursprünglichen SVRG-Methode.Beispielsweise verwenden einige Variationen $T$ Alternativverteilung [32], einige Varianten erlauben die Form $O(1/L_{text{max}})$ Die Schrittgröße [27], [33], [35].Es gibt auch einige Variationen bei der Verwendung $\nabla F (\overset{X}{ˉ})$ Mini-Batch-Näherung, um die Kosten dieser vollständigen Gradientenauswertungen zu senken und die Mini-Batch-Größe zu erhöhen, um VR-Eigenschaften beizubehalten.Es gibt auch einige Varianten, bei denen Aktualisierungen gemäß [54] in der inneren Schleife wiederholt werden. $g_k$ ：
[ g_k = nabla f_{i_k}(x_k) - nabla f_{i_k}(x_{k-1}) + g_{k-1} quad (25) ]
Dies liefert eine lokalere Näherung. Die Verwendung dieser kontinuierlichen Aktualisierungsvariante (25) zeigt einzigartige Vorteile bei der Minimierung nichtkonvexer Funktionen, wie wir in Abschnitt IV kurz diskutieren.Beachten Sie abschließend, dass SVRG davon profitieren kann $f(bar{x}_s)$ Wert, der bei der Entscheidung hilft, wann der Algorithmus beendet werden soll.

Algorithmus 3 SVRG-Methode

Parameter: Schrittgröße $γ > 0$
Referenzpunkt initialisieren $bar{x}_0 = x_0 in mathbb{R}^d$
Führen Sie eine externe Zirkulation durch $S = 1, 2, \dots$ ：
a. Berechnen und speichern $f(bar{x}_{s-1})$
b. Annehmen $x_0 = bar{x}_{s-1}$
c. Wählen Sie die Anzahl der Iterationen der inneren Schleife $T$
d. Führen Sie eine interne Zirkulation durch $k = 0, 1, \dots, T - 1$ ：
i. Zufällige Auswahl $i_k in {1, ldots, n}$
ii. Berechnung $g_k = nabla f_{i_k}(x_k) - nabla f_{i_k}(bar{x}_{s-1}) + nabla f(bar{x}_{s-1})$
iii. Aktualisieren $x_{k+1} = x_k - gamma g_k$
e. Referenzpunkt aktualisieren $Strich{x}_s = x_t$

2.4. SDCA und seine Varianten

Ein Nachteil der SAG- und SVRG-Methoden besteht darin, dass ihre Schrittgröße auf unbekannten Werten beruht, die bei einigen Problemen möglicherweise unbekannt sind. $L_{text{max}}$ . Vor SVRG erweiterte die SDCA-Methode [70] als eine der frühesten VR-Methoden die Forschung zu Koordinatenabstiegsmethoden auf Finite-Summen-Probleme. Die Idee hinter SDCA und seinen Varianten besteht darin, dass die Koordinaten des Gradienten eine natürliche varianzreduzierende Gradientenschätzung liefern.Nehmen wir konkret an $J \in {1, \dots, D}$ , und definieren $nabla_j f(x) := left( frac{partiell f(x)}{partiell x_j} rechts) e_j$ ist das te von (f(x)) $J$ Ableitungen in Koordinatenrichtungen, wo $e_j in mathbb{R}^d$ Es ist das erste $J$ Einheitsvektor.Eine Schlüsseleigenschaft von Koordinatenableitungen ist das $nabla_j f(x^*) = 0$ , weil wir es wissen $f(x^*) = 0$ .Die Ableitung davon mit jedem Datenpunkt $f_j$ anders, Letzteres ist $x^*$ darf nicht Null sein. Deshalb haben wir:
$nabla_j f(x) |^2 rightarrow 0 quad text{当} quad x rightarrow x^* quad (26)$
Dies bedeutet, dass die Koordinatenableitung die Varianzreduktionseigenschaft (12) erfüllt.Darüber hinaus können wir verwenden $nabla_j f(x)$ bauen $\nabla F (X)$ eine unvoreingenommene Schätzung von.Nehmen wir zum Beispiel an $J$ ist aus der Sammlung ${1, \dots, D}$ Ein gleichmäßig zufällig ausgewählter Index in .Daher für jeden $ichchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchchch \in {1, \dots, D}$ ,Wir haben $P [ j = i ] = 1 d P[j = i] = frac{1}{d}$ . daher, $nabla_j f(x)$ Ja $\nabla F (X)$ Eine unvoreingenommene Schätzung, weil:
$nabla_j f(x) right] = d sum_{i=1}^{d} P[j = i] frac{partial f(x)}{partial x_i} e_i = sum_{i=1}^{d} frac{partial f(x)}{partial x_i} e_i = nabla f(x)$

daher, $nabla_j f(x)$ Verfügt über alle idealen Eigenschaften, die wir für die VR-Schätzung vollständiger Gradienten erwarten würden, ohne dass Kovariaten verwendet werden müssen. Ein Nachteil der Verwendung dieses Koordinatengradienten besteht darin, dass er für unser Summenproblem (2) rechenintensiv ist.Dies liegt an der Berechnung $nabla_j f(x)$ Der gesamte Datensatz muss durchlaufen werden, weil $nabla_j f(x) = frac{1}{n} sum_{i=1}^{n} nabla_j f_i(x)$ . Daher scheint die Verwendung von Koordinatenableitungen mit der Struktur unseres Summenproblems unvereinbar zu sein. Allerdings können wir das ursprüngliche Problem (2) oft in eine sogenannte duale Formulierung umschreiben, bei der die Koordinatenableitungen die inhärente Struktur ausnutzen können.

Die duale Formel des L2-regularisierten linearen Modells (15) lautet beispielsweise:
$v^* in argmax_{v in mathbb{R}^n} frac{1}{n} sum_{i=1}^{n} -ell_i^*(-v_i) - frac{lambda}{2} links| frac{1}{lambda} sum_{i=1}^{n} v_i a_i rechts|^2 quad (27)$
In $ell_i ^*(v)$ Ja $ell_i$ konvexes Konjugat.Wir können Mapping verwenden $sum_{i=1}^{n} v_i a_i$ um das ursprüngliche Problem zu beheben (15) $X$ Variable.wir klären das $v^*$ Durch Einsetzen in die rechte Seite der obigen Abbildung erhalten wir die Lösung von (15) $x^*$ 。

Beachten Sie, dass dieses Doppelproblem besteht $N$ reelle Variablen $v_i in mathbb{R}$ , was einem für jedes Trainingsbeispiel entspricht.Darüber hinaus hat jede doppelte Verlustfunktion $ell_i^*$ nur $v_i$ Die Funktion. Das heißt, der erste Term in der Verlustfunktion ist koordinativ trennbar. Diese Trennbarkeit in Koordinaten, gepaart mit der einfachen Form des zweiten Termes, ermöglicht uns die effiziente Implementierung der Koordinatenaufstiegsmethode.Tatsächlich zeigten Shalev-Shwartz und Zhang, dass der Koordinatenaufstieg bei diesem Problem eine ähnliche iterative Komplexität aufweist wie SAG, SAGA und SVRG $O((kappa_{text{max}} + n) log(1/epsilon))$ 。

Auch die Iterationskosten und die Algorithmusstruktur sind sehr ähnlich: Summierung durch Tracking $Summe_{i=1}^{n} v_i a_i$ Um den zweiten Term in (27) zu verarbeiten, muss jede Dual-Koordinaten-Aufstiegsiteration nur eine Trainingsprobe berücksichtigen, und die Kosten jeder Iteration sind dieselben wie $N$ Nichts zu tun.Darüber hinaus können wir eine 1D-Liniensuche verwenden, um die zu maximierende Schrittgröße effizient zu berechnen $v_i$ Doppeltes Ziel der Funktion.Das bedeutet auch ohne $L_{text{max}}$ Durch die Kenntnis relevanter Größen können auch schnelle Worst-Case-Laufzeiten für VR-Methoden erreicht werden.

3. Praktische Fragen der Varianzreduktion

Um die grundlegende Varianzreduktionsmethode (VR) zu implementieren und eine angemessene Leistung zu erzielen, müssen mehrere Implementierungsprobleme angegangen werden. In diesem Abschnitt besprechen wir mehrere Themen, die oben nicht behandelt wurden.

3.1. SAG/SAGA/SVRG-Einstellung der Schrittgröße

Im Bereich der Optimierungsalgorithmen, insbesondere bei Variationsreduktionsverfahren wie dem stochastischen Durchschnittsgradienten (SAG), dem stochastischen Durchschnittsgradientenalgorithmus (SAGA) und dem stochastischen Gradienten (SVRG), ist die Einstellung der Schrittweite ein zentrales Thema.Obwohl wir für die SDCA-Methode (Stochastic Dual Coordinate Ascent) das duale Ziel zur Bestimmung der Schrittgröße verwenden können, ist die theoretische Grundlage für die ursprünglichen Variablenmethoden von SAG, SAGA und SVRG, dass die Schrittgröße sein sollte $Olinks(frac{1}{L_{text{max}}}rechts)$ bilden.In praktischen Anwendungen wissen wir es jedoch oft nicht $L_{text{max}}$ Geben Sie den genauen Wert an, und die Verwendung anderer Schrittgrößen kann zu einer besseren Leistung führen.

Eine klassische Strategie zum Festlegen der Schrittgröße in der Methode des vollständigen Gradientenabstiegs (Full-GD) ist die Armijo-Liniensuche.gegebener aktueller Punkt $x_k$ und Suchrichtung $g_k$ , Armijo-Zeilensuche in $gamma_k$ wird auf der Linie ausgeführt, die definiert ist als $gamma_k in {gamma : x_k + gamma g_k}$ , und die Funktion muss ausreichend reduziert werden, das heißt:
$f(x_k + gamma_k g_k) < f(x_k) - c gamma_k |nabla f(x_k)|^2$
Dieser Ansatz erfordert jedoch mehrere Kandidatenschritte $gamma_k$ Berechnung $f(x_k + gamma_k g_k)$ , die auswertet $F (X)$ Die Kosten sind unerschwinglich, wenn es darum geht, den gesamten Datensatz zu durchqueren.

Um dieses Problem zu lösen, kann eine zufällige Variationsmethode verwendet werden, um diejenigen zu finden, die die folgenden Bedingungen erfüllen $gamma_k$ ：
$f_{ik}(x_k + gamma_k g_k) < f_{ik}(x_k) - c gamma_k |nabla f_{ik}(x_k)|^2$
Dieser Ansatz funktioniert in der Praxis normalerweise gut, insbesondere wenn $f_{ik}(x_k)|$ nicht nahe Null, obwohl es derzeit keine Theorie gibt, die diesen Ansatz unterstützt.

Darüber hinaus schlug Mairal eine „Bottou-Technik“ zur Einstellung der Schrittweite in der Praxis vor. Diese Methode führt eine binäre Suche durch, indem sie einen kleinen Teil des Datensatzes (z. B. 5 %) verwendet, um zu versuchen, die optimale Schrittgröße in einem einzigen Durchgang durch diese Stichprobe zu finden. Ähnlich wie die Armijo-Liniensuche schneidet diese Methode in der Praxis oft gut ab, es mangelt ihr aber wiederum an einer theoretischen Grundlage.

Bitte beachten Sie, dass der obige Inhalt eine Neuformulierung des Originaltextes ist und das Markdown-Format zur Darstellung mathematischer Formeln und Variablen verwendet.

Allerdings hat die SDCA-Methode auch einige Nachteile.Zunächst muss das konvexe Konjugat berechnet werden $ell_i^*$ statt eines einfachen Farbverlaufs. Wir haben kein automatisches Differentialäquivalent für konvexe Konjugate, daher kann dies den Implementierungsaufwand erhöhen. In neueren Arbeiten wurden „dualfreie“ SDCA-Methoden vorgeschlagen, die keine Konjugation erfordern und stattdessen direkt Gradienten verwenden. Allerdings ist es bei diesen Methoden nicht mehr möglich, das Doppelziel zur Einstellung der Schrittweite zu verfolgen.Zweitens, obwohl SDCA nur erfordert $Ö (N + D)$ Speicher zur Lösung des (15)-Problems, aber für diese Problemkategorie benötigt SAG/SAGA nur $Ö (N + D)$ des Gedächtnisses (siehe Abschnitt 3).Eine Variante von SDCA, die für allgemeinere Probleme mit SAG/SAGA geeignet ist $Ö (N D)$ Erinnerung, weil $v_i$ werden zu haben $D$ Vektor von Elementen. Ein letzter subtiler Nachteil von SDCA besteht darin, dass es implizit eine starke Konvexitätskonstante annimmt $μ$ gleich $λ$ .für $μ$ mehr als die $λ$ Problem: Die ursprüngliche VR-Methode ist SDCA in der Regel deutlich überlegen.

3.2. Festlegung der Kündigungsbedingungen

Im Bereich der Algorithmusoptimierung verlassen wir uns häufig auf theoretische Ergebnisse der iterativen Komplexität, um die Anzahl der Iterationen im ungünstigsten Fall vorherzusagen, die ein Algorithmus benötigt, um eine bestimmte Genauigkeit zu erreichen. Allerdings basieren diese theoretischen Grenzen oft auf einigen Konstanten, die wir nicht vorhersagen können, und in praktischen Anwendungen kann der Algorithmus oft die erwartete Genauigkeit in weniger Iterationen erreichen. Daher müssen wir einige Testkriterien festlegen, um zu bestimmen, wann der Algorithmus beendet werden soll.

Bei der traditionellen Methode des vollständigen Gradientenabstiegs (Full-GD) verwenden wir normalerweise die Norm des Gradienten $f(x_k) |$ Oder eine andere damit zusammenhängende Größe, um zu entscheiden, wann die Iteration gestoppt werden soll.Für die SVRG-Methode können wir das gleiche Kriterium übernehmen, aber verwenden $f(bar{x}_s) |$ als Grundlage für die Beurteilung.Obwohl wir für die SAG/SAGA-Methode nicht explizit den vollständigen Gradienten berechnen, nähert sich die Menge $ g_{bar{k}} $ allmählich an $f(x_k)$ , daher verwenden $g_{bar{k}} |$ als Stoppbedingung ist eine sinnvolle Heuristik.

Bei der SDCA-Methode können wir mit etwas zusätzlichem Aufzeichnungsaufwand den Gradienten des Doppelobjektivs verfolgen, ohne zusätzliche asymptotische Kosten hinzuzufügen.Darüber hinaus wäre es ein systematischerer Ansatz, die doppelte Lücke zu verfolgen, obwohl dies die Kosten erhöhen würde $Ö (N)$ Kostengünstig, aber es ist in der Lage, Kündigungsbedingungen mit doppeltem Gap-Nachweis bereitzustellen. Basierend auf der Optimalitätsbedingung stark konvexer Ziele verwendet die MISO-Methode außerdem eine prinzipielle Methode, die auf einer quadratischen Untergrenze basiert [41].

Im Folgenden sind mathematische Formeln und Variablen aufgeführt, die im Markdown-Format ausgedrückt werden:

Gradientennorm: $f(x_k) |$
Gradientennorm in der SVRG-Methode: $f(bar{x}_s) |$
Der Betrag des Approximationsgradienten in der SAG/SAGA-Methode: $ g_{bar{k}} $
Erhöhte Kosten pro Iteration: $Ö (N)$
MISO-Methode
quadratische Untergrenze

Bitte beachten Sie, dass der obige Inhalt eine Neuformulierung des Originaltextes ist und das Markdown-Format zur Darstellung mathematischer Formeln und Variablen verwendet.

3.3. Reduzieren Sie den Speicherbedarf

Obwohl der Stochastic Variational Reduction of Gradient (SVRG)-Algorithmus den Speicherbedarf früherer Variationsreduktionsmethoden eliminiert, werden in praktischen Anwendungen bei vielen Problemen die Algorithmen SAG (Stochastic Average Gradient Descent) und SAGA (Stochastic Average Gradient Descent with Gradient Accumulation) verwendet . neigen dazu, weniger Iterationen als der SVRG-Algorithmus zu erfordern.Dies löste einen Gedanken aus: Gibt es einige Probleme, die SAG/SAGA ermöglichen? $Ö (N D)$ Speicheranforderungen werden unten implementiert. In diesem Abschnitt wird eine Klasse linearer Modelle untersucht, bei denen der Speicherbedarf erheblich reduziert werden kann.

Betrachten Sie ein lineares Modell, bei dem jede Funktion $f_i(x)$ Es kann ausgedrückt werden als: $xi_i(mathbf{a}_i^top x)$ .Rechts $X$ Die Ableitung ergibt die Gradientenform:
$f_i(x) = xi'(mathbf{a}_i^top x) mathbf{a}_i$
Hier, $ξ^{'}$ äußern $ξ$ die Ableitung von.Vorausgesetzt, wir haben direkten Zugriff auf die Eigenvektoren $mathbf{a}_i$ Dann müssen wir zur Implementierung der SAG/SAGA-Methode nur den Skalar speichern $xi(mathbf{a}_i^top x)$ .Auf diese Weise variieren die Speicheranforderungen $Ö (N D)$ reduziert auf $Ö (N)$ . Auch der SVRG-Algorithmus kann sich diese Gradientenstruktur zunutze machen: indem er sie speichert $N$ Skalar können wir die Anzahl der pro „innerer“ SVRG-Iteration erforderlichen Gradientenauswertungen für diese Problemklasse auf 1 reduzieren.

Es gibt auch andere Arten von Problemen, beispielsweise probabilistische grafische Modelle, die ebenfalls die Möglichkeit bieten, den Speicherbedarf zu reduzieren [66]. Durch gezielte Datenstruktur- und Algorithmusoptimierung können die vom Algorithmus zur Laufzeit benötigten Speicherressourcen weiter reduziert werden.

Im Folgenden sind mathematische Formeln und Variablen aufgeführt, die im Markdown-Format ausgedrückt werden:

Lineare Modellfunktion: $f_i(x) = xi_i(mathbf{a}_i^top x)$
Farbverlaufsausdruck: $f_i(x) = xi'(mathbf{a}_i^top x) mathbf{a}_i$
Merkmalsvektor: $mathbf{a}_i$
Der Speicherbedarf reicht von $Ö (N D)$ Reduzieren $Ö (N)$ 。

3.4. Verarbeitung spärlicher Farbverläufe

Bei einigen Problemen ist der Gradient $f_i(x)$ Kann eine große Anzahl von Nullwerten enthalten, z. B. ein lineares Modell mit spärlichen Features.In diesem Fall kann der herkömmliche stochastische Gradientenabstiegsalgorithmus (SGD) effizient implementiert werden, wobei die Rechenkomplexität linear zur Anzahl der Nicht-Null-Elemente im Gradienten ist, die normalerweise viel kleiner als die Problemdimension ist $D$ . Bei Standardmethoden der Variationsreduktion (VR) wird dieser Vorteil jedoch nicht ausgenutzt. Glücklicherweise gibt es zwei bekannte Möglichkeiten, dies zu verbessern.

Die erste Verbesserung wurde von Schmidt et al. vorgeschlagen, die sich die Einfachheit des Aktualisierungsprozesses zunutze macht und eine Variante der „on-the-fly“-Berechnung implementiert, sodass die Kosten jeder Iteration proportional zur Anzahl ungleich Null sind Elemente.Am Beispiel von SAG (aber dieser Ansatz funktioniert für alle Varianten) erfolgt dies dadurch, dass nicht nach jeder Iteration der vollständige Vektor gespeichert wird $v_{ik}$ , berechnet aber nur diejenigen, die Elementen ungleich Null entsprechen $v_{ik_j}$ , indem jede Variable aktualisiert wird, seit das Element das letzte Mal ungleich Null war $v_{ik_j}$ 。

Die zweite Verbesserungsmethode wurde von Leblond et al. für SAGA vorgeschlagen, wodurch die Formel aktualisiert wird $x_{k+1} = x_k - gamma(nabla f_{ik}(x_k) - nabla f_{ik}(bar{x}_{ik}) + bar{g}_k)$ Zusätzliche Zufälligkeit wird eingeführt. Hier, $f_{ik}(x_k)$ Und $f_{ik}(bar{x}_{ik})$ ist spärlich, und $Strich{g}_k$ ist dicht.Bei dieser Methode ist der dichte Begriff $(Strich{g}_k)_j$ Jede Komponente von wird durch ersetzt $w_j (Strich{g}_k)_j$ ,In $mathbb{R}^d$ ist ein zufälliger, dünn besetzter Vektor, dessen Unterstützungssatz in enthalten ist $f_{ik}(x_k)$ , und es wird erwartet, dass es sich um einen konstanten Vektor handelt, bei dem alle Elemente gleich 1 sind. Auf diese Weise bleibt der Aktualisierungsprozess unvoreingenommen (wenn auch jetzt spärlich) und die erhöhte Varianz hat keinen Einfluss auf die Konvergenzrate des Algorithmus. Weitere Einzelheiten werden von Leblond et al. bereitgestellt.

Im Folgenden sind mathematische Formeln und Variablen aufgeführt, die im Markdown-Format ausgedrückt werden:

Gradient: $f_i(x)$
SGD-Update: $x_{k+1} = x_k - gamma(nabla f_{ik}(x_k) - nabla f_{ik}(bar{x}_{ik}) + bar{g}_k)$
Spärlicher Farbverlauf: $f_{ik}(x_k)$ Und $f_{ik}(bar{x}_{ik})$
Dichtes Gefälle: $Strich{g}_k$
Zufällige spärliche Vektoren: $m$
Erwartet einen konstanten Vektor: einen Vektor, bei dem alle Elemente gleich 1 sind.

Technologieaustausch

[Deep Learning] Grundlagen des grafischen Modells (7): Varianzreduktionsmethode bei der Optimierung des maschinellen Lernens (1)

1. Einleitung

1.1. Gradienten- und stochastische Gradientenabstiegsmethoden

1.2. Varianzproblem

1.3. Klassische Varianzreduktionsmethode

1.4. Moderne Varianzreduktionsmethoden

1.5. Erstes Beispiel einer Varianzreduktionsmethode: SGD²

1.6. Schnelle Konvergenz der Varianzreduktionsmethode

Annahme 1 (Lipschitz-Stetigkeit)

Annahme 2 (starke Konvexität)

2. Grundlegende Varianzreduktionsmethode

2.1. Stochastische Durchschnittsgradientenmethode (SAG)

2.2.SAGA-Methode

2.3.SVRG-Methode

2.4. SDCA und seine Varianten

3. Praktische Fragen der Varianzreduktion

3.1. SAG/SAGA/SVRG-Einstellung der Schrittgröße

3.2. Festlegung der Kündigungsbedingungen

3.3. Reduzieren Sie den Speicherbedarf

3.4. Verarbeitung spärlicher Farbverläufe

Persönliches Profil

meine Kontaktdaten