Berechnung der Konvergenzrate beim Gradientenverfahren

29.11.2023, 11:21	SilverFox	Auf diesen Beitrag antworten »
Berechnung der Konvergenzrate beim Gradientenverfahren Meine Frage: Ich recherchiere gerade zum Gradientenverfahren. Dabei betrachte ich den konvexen Fall mit Lipschitz-stetigen Gradienten. Als Quelle benutze ich Nesterov's "Lectures on convex optimitzation". Dort schreibt er als Resultat für den konvexen Fall $\begin{eqnarray} <br /> f(x_k) - f^ \leq \frac{2L \\|x_0-x^\\|^2}{k+4}<br /> \end{eqnarray}$ und für den stark konvexen Fall $\begin{eqnarray} <br /> f(x_k) -f^ \leq \frac{L}{2} (\frac{L-\mu}{L+\mu})^{2k}\\|x_0-x^\\|^2 <br /> \end{eqnarray}$ , wobei L die Lipschitz-Konstante ist und $\begin{eqnarray} \mu \end{eqnarray}$ der Faktor der starken Konvexität. Meine Frage ist, wie man daraus die Konvergenzrate berechnet? Für den ersten Fall (konvex) habe ich in einem anderen Paper die Rate $\begin{eqnarray} \mathcal{O}(\frac{1}{k}) \end{eqnarray}$ gefunden. Wie berechne ich das analoge Ergebnis für den stark konvexen Fall? Meine Ideen: Bei Recherche zur Konvergenzrate stoße ich immer nur auf Definitionen zur linearen Konvergenz, Konvergenz der Ordnung p usw. Allerdings finde ich keine Erklärung, wie man von solchen Formeln oben auf die Landau-Notation kommt (die in numerischen Papern meist standardmäßig verwendet wird). Danke schonmal im Voraus
29.11.2023, 20:16	IfindU	Auf diesen Beitrag antworten »
RE: Berechnung der Konvergenzrate beim Gradientenverfahren Man wird wohl davon ausgehen, dass $\begin{eqnarray} L, x_0, x^, \mu \end{eqnarray}$ alle unabhängig von $\begin{eqnarray} k \end{eqnarray}$ sind. D.h. man kann definieren $\begin{eqnarray} C = \frac L 2 \\| x_0 - x^* \\|^2 \end{eqnarray}$ und hat $\begin{eqnarray} f(x_k) - f^* \leq C \cdot \left ( \frac { L - \mu } {L + \mu} \right)^{2k} \end{eqnarray}$ . Für (vermutlich die Annahmen) $\begin{eqnarray} 0 < \mu < L \end{eqnarray}$ hat man für $\begin{eqnarray} q = \frac { L - \mu } {L + \mu} \end{eqnarray}$ dann $\begin{eqnarray} 0 < q < 1 \end{eqnarray}$ . Insb. gilt dann $\begin{eqnarray} q^{2k} \to 0 \end{eqnarray}$ falls $\begin{eqnarray} k\to\infty \end{eqnarray}$ . Noch einmal zusammen genommen $\begin{eqnarray} f(x_k) - f^* \leq C \cdot q^{2k} \end{eqnarray}$ . D.h. in dem Fall wäre eine* Möglichkeit $\begin{eqnarray} \mathcal O (q^{2k}) \end{eqnarray}$ zu nehmen. Oder $\begin{eqnarray} \mathcal O (q^{k}) \end{eqnarray}$ oder sogar $\begin{eqnarray} \mathcal O (\frac 1 k) \end{eqnarray}$ . Landau-Notation ist alles andere als eindeutig. Das erste ist das "stärkste" was man hieraus ableiten kann. (Mit der Nebenbemerkung, dass es nur gilt, dass $\begin{eqnarray} \| f(x_k) - f^\| \end{eqnarray}$ die Ungleichung erfüllt, oder $\begin{eqnarray} \mathcal O \end{eqnarray*}$ schwächer definiert wird als normal).

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »