Warum ist der Gradientenabstieg bei großen Datenmengen ineffizient?

Nehmen wir an, unser Datensatz enthält 1 Million Beispiele, dh , und wir möchten den Gradientenabstieg verwenden, um eine logistische oder lineare Regression für diesen Datensatz durchzuführen.$x_1, \ldots, x_{10^6}$

Was macht die Gradientenabstiegsmethode ineffizient?

Es sei daran erinnert, dass der Gradientenabstiegsschritt zum Zeitpunkt gegeben ist durch:$t$

$$w_{t+1} = w_{t} + \eta_t \nabla f(x)$$

wobei die Verlustfunktion ist.$f$

Ich sehe mit dem obigen Schritt nichts Ungewöhnliches, was dazu führt, dass der Algorithmus ineffizient ist. Ist es die Berechnung von ? Konnte diese Operation nicht vorberechnet werden, dh jedes ∂ $\nabla f(x)$ bereits berechnet und einfach an jedem Datenpunktxiausgewertet$\frac{\partial f}{\partial x}$$x_i?$

Es wäre hilfreich, wenn Sie einen Kontext für die Behauptung angeben, dass der Gradientenabstieg ineffizient ist. Ineffizient im Vergleich zu was?

Ich vermute, dass der fehlende Kontext hier der Vergleich mit dem stochastischen oder Batch-Gradienten-Abfall beim maschinellen Lernen ist. Hier erfahren Sie, wie Sie die Frage in diesem Zusammenhang beantworten können. Sie optimieren die Parameter des Modells, auch die Hyperparameter. Sie haben also die Kostenfunktion , wobei x i - Ihre Daten und Θ - Vektor von Parametern und L ( ) - Verlustfunktion. Um diese Kosten zu minimieren, verwenden Sie den Gradientenabstieg über die Parameter θ j : $\sum_{i=1}^n L(x_i|\Theta)$$x_i$$\Theta$$L()$ $\theta_j$

$$\frac{\partial}{\partial \theta_j}\sum_{i=1}^nL(\Theta|x_i)$$

Sie sehen also, dass Sie die Summe über alle Daten . Dies ist unglücklich, da dies bedeutet, dass Sie die Daten für jeden Schritt Ihres Gefälleverlaufs in einer Schleife durchlaufen. Auf diese Weise wird der Batch- und der stochastische Gradientenabstieg ermittelt: Was passiert, wenn wir aus dem Datensatz eine Stichprobe erstellen und den Gradienten anhand einer Stichprobe berechnen, nicht anhand des vollständigen Satzes? $x_{i=1,\dots,n}$ Hiernsist die Anzahl von Beobachtungen in der Probes. Wenn Ihre Stichprobe also 1/100 des Gesamtsatzes ausmacht, beschleunigen Sie Ihre Berechnungen um das 100-fache! Dies führt natürlich das Rauschen ein, das das Lernen verlängert, aber das Rauschen nimmt mit einer Rate von

$$\frac{\partial}{\partial \theta_j}\sum_{k=1}^{n_s}L(\Theta|x_k)$$ $n_s$$s$ während sich der Berechnungsbetrag umnerhöht, sodass dieser Trick funktionieren kann.$\sqrt n$$n$

Alternativ können Sie, anstatt zu warten, bis die vollständige Summe berechnet ist, diese in Chargen aufteilen und für jede Charge einen Schritt ausführen: ∑ M s = 1 ∑ n s i s = 1 . Auf diese Weise hätten Sie bis zur Berechnung der Summe über den gesamten Datensatz M Schritte ausgeführt. Dies wären lautere Schritte, aber das Geräusch wird mit der Zeit leiser.$\sum_{i=1}^n$$\sum_{s=1}^M\sum_{i_s=1}^{n_s}$

Es gibt zwei Möglichkeiten, wie ein Gradientenabstieg ineffizient sein kann. Interessanterweise führen sie jeweils zu einer eigenen Methode zum Reparieren, die fast gegensätzliche Lösungen sind. Die beiden Probleme sind:

(1) Es sind zu viele Aktualisierungen des Gefälleverlaufs erforderlich.

(2) Jeder Gradientenabstiegsschritt ist zu teuer.

In Bezug auf (1) ist der Gradientenabfall beim Vergleich des Gradientenabfalls mit Verfahren, die Informationen über Ableitungen zweiter Ordnung berücksichtigen, in Bezug auf die Verbesserung des Verlusts bei jeder Iteration in der Regel sehr ineffizient. Eine sehr Standardmethode, die Newton-Methode , benötigt im Allgemeinen viel weniger Iterationen für die Konvergenz, dh für die logistische Regression weisen 10 Iterationen der Newton-Methode häufig einen geringeren Verlust auf als die Lösung, die durch 5.000 Iterationen der Gradientenabnahme bereitgestellt wird. Für die lineare Regression ist dies sogar noch extremer. Es gibt eine geschlossene Lösung! Da jedoch die Anzahl der Prädiktoren sehr groß wird (dh über 500), kann die Newtonsche Methode / direktes Lösen nach linearer Regression pro Iteration zu teuer werden Aufgrund der Menge der erforderlichen Matrixoperationen wird der Gradientenabstieg erheblich weniger Kosten pro Iteration verursachen.

$O(nk)$$n$$k$$n = 10^{6}$$k < 100$$n = 10^{12}$$k = 10^3$wird sein. In diesem Fall sind Methoden attraktiver, die die Ableitung auf der Grundlage kleinerer Teilmengen der Daten approximieren, beispielsweise die stochastische Gradientenabnahme .

Ich sage, dass diese Korrekturen fast entgegengesetzt sind, da die Newton-Methode pro Aktualisierung teurer, aber effizienter (in Bezug auf die Verluständerung) ist, während die stochastische Gradientenabnahme weniger effizient ist, aber pro Aktualisierung viel rechenintensiver ist.

Lassen Sie mich zunächst eine Verbesserung Ihrer Notation vorschlagen. Insbesondere bezeichnen wir die Verlustfunktion mit$L(w)$ eher, als $f(x)$. Mit dem Brief$L$da es mir einfach eine persönliche Vorliebe von mir erinnert , dass wir es zu tun mit dem L oss. Die wesentlichere Änderung macht deutlich, dass der Verlust eine Funktion der Gewichte ist$w$ eher als die Daten $x$. Wichtig ist, dass der Gradient in Bezug auf$w$ nicht $x$. So

$$\nabla L(w) = \left(\frac{\partial L}{\partial w_1}, \dots, \frac{\partial L}{\partial w_D} \right),$$ wo $D$ ist die Dimensionalität Ihrer Daten.

Trotz der Tatsache, dass wir uns den Verlust als Funktion der Gewichte vorstellen sollten $w$hängt jede vernünftige Verlustfunktion immer noch vom gesamten Datensatz ab $x$(Wenn nicht, wäre es nicht möglich, etwas aus den Daten zu lernen!). In der linearen Regression verwenden wir zum Beispiel typischerweise die Verlustfunktion der Quadratsumme

$$L(w) = \sum_{i=1}^N (y_i - w^Tx_i)^2.$$ So evaluating the gradient $\nabla L(w)$ for a particular set of weights $w$ will require a sum over all $N$ points in the dataset $x$. If $N = 10^6$, then every incremental step in the gradient descent optimization will require on the order of a million operations, which is quite expensive.

Short answer: Calculating gradient needs to sum over all the data points. If we have large amount of data, then it takes a long time.

I have a detailed answer here.

How could stochastic gradient descent save time comparing to standard gradient descent?

---

On the other hand, always keep in mind there are direct methods in addition to iterative methods (gradient decent). If we want to solve a least square problem, direct method can be super efficient. For example, QR decomposition. If we do not have too many features, it is very fast.

When you verify it, it may surprise you: 5 million data points with 2 features, Solving the linear regression / least square takes couple of seconds!

x=matrix(runif(1e7),ncol=2)
y=runif(5e6)
start_time <- Sys.time()
lm(y~x)
end_time <- Sys.time()
end_time - start_time
# Time difference of 4.299081 secs

Although the two examples you mentioned are usually convex I'll add one point about non-convex problems. In my opinion there are two main reason why (batch) gradient descent might be considered "inefficient". The first point about the computational effort of calculating the gradient of a "large" sum of functions has already been very clearly outlined in the other answers. For non-convex problems however GD has the problem of usually getting stuck in a "close" local minimum. This minimum might be very bad in comparison to the global minimum. SGD or mini-batch GD have the "advantage" of wandering around (at least partially) randomly and thus might have the chance of finding a better local minimum. See this CV answer here. Or this other CV post outlining how randomness might be beneficial.