Wissenschaftlicher Artikel: LaTeX-Vorlage
Eine kostenlose LaTeX-Vorlage für wissenschaftliche Artikel mit der Standardklasse article: Titel, Abstract, Abschnitte und Literatur sind vorbereitet, damit du dich auf den Inhalt konzentrieren kannst.
Editor öffnen Zurück zu den Vorlagen
LaTeX-Quelltext
% Vorlage für einen wissenschaftlichen Artikel: Titel, Autoren mit Institutionen, Zusammenfassung und Schlüsselwörter,
% nummerierte Abschnitte, Satz, Tabelle, Diagramm und Literaturverzeichnis. Sie ist mit einem kurzen Beispiel
% (Momentum bei quadratischen Problemen) gefüllt, damit du siehst, wie die einzelnen Teile funktionieren.
% Ersetze den Text, die Tabelle und das Diagramm durch deine eigenen Inhalte.
\documentclass[a4paper,11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[ngerman]{babel}
\usepackage[margin=2.5cm]{geometry}
\usepackage{microtype}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage{graphicx} % nur nötig, wenn du Bilddateien mit \includegraphics einbindest
\usepackage{authblk}
\usepackage{pgfplots}
\usetikzlibrary{babel}
\usepackage[hidelinks]{hyperref}
% Literaturverzeichnis: Die Einträge stehen in references.bib; zitiere sie mit \cite{Schlüssel} oder \citet{Schlüssel}
\usepackage[numbers,sort&compress]{natbib}
\pgfplotsset{compat=1.18}
\newtheorem{theorem}{Satz}
\theoremstyle{remark}
\newtheorem*{remark}{Bemerkung}
% ---- Titel und Autoren: bitte anpassen ----
\title{Momentum beschleunigt das Gradientenverfahren bei schlecht konditionierten quadratischen Problemen}
\author[1]{Anna Becker\thanks{Korrespondierende Autorin: \texttt{anna.becker@example.com}}}
\author[2]{Lukas Schneider}
\affil[1]{Fachbereich Mathematik, Musteruniversität, Berlin, Deutschland}
\affil[2]{Institut für Informatik, Beispiel-Technische-Hochschule, München, Deutschland}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
% Fasse in etwa 150 Wörtern das Problem, die Methode, das Hauptergebnis und seine Bedeutung zusammen.
Das Gradientenverfahren wird langsam, wenn das Problem schlecht konditioniert ist. Wir vergleichen das
einfache Gradientenverfahren mit dem Heavy-Ball-Verfahren auf quadratischen Zielfunktionen und zeigen, dass
Momentum die Zahl der benötigten Iterationen von der Ordnung $\kappa$ auf die Ordnung $\sqrt{\kappa}$
senkt, wobei $\kappa$ die Konditionszahl ist. Wir beweisen die asymptotischen Konvergenzraten, überprüfen
sie numerisch für Konditionszahlen bis $10^3$ und diskutieren, wann sich die Beschleunigung auf andere
Probleme übertragen lässt.
\end{abstract}
\noindent\textbf{Schlüsselwörter:} Optimierung, Gradientenverfahren, Momentum, Konditionszahl
\section{Einleitung}
% Stelle das Problem, den Stand der Forschung, die Lücke und deinen Beitrag vor.
Viele Probleme in Wissenschaft und Technik laufen auf die Minimierung einer glatten Funktion hinaus, und das
Gradientenverfahren ist dafür die einfachste Methode \citep{boyd2004}. Seine Geschwindigkeit hängt stark von
der Form der Zielfunktion ab: Sind die Niveaumengen lang und schmal, pendeln die Iterierten hin und her und
der Fortschritt ist gering. Ein Momentum-Term \citep{polyak1964} dämpft dieses Hin- und Herpendeln, und der
Effekt ist an quadratischen Funktionen leicht zu erkennen \citep{goh2017}.
Die Beiträge dieses Artikels sind:
\begin{itemize}
\item eine in sich geschlossene Herleitung der asymptotischen Konvergenzraten beider Verfahren auf quadratischen Funktionen und
\item eine numerische Überprüfung der vorhergesagten Iterationszahl für drei Konditionszahlen.
\end{itemize}
Abschnitt~\ref{sec:method} führt die Problemstellung ein, Abschnitt~\ref{sec:results} zeigt die Ergebnisse und
Abschnitt~\ref{sec:conclusions} schließt den Artikel ab.
\section{Methoden}\label{sec:method}
% Beschreibe das Modell, die Algorithmen und die Annahmen, die zur Wiederholung deiner Arbeit nötig sind.
Wir minimieren die quadratische Funktion $f(x) = \tfrac12 x^{\top}Ax$, wobei $A$ symmetrisch positiv definit
ist mit kleinstem und größtem Eigenwert $\mu$ bzw.\ $L$. Die Konditionszahl ist $\kappa = L/\mu$ und der
Minimierer ist $x^{\star}=0$. Ausgehend von $x_0$ lauten die Iterationsvorschriften des Gradientenverfahrens
mit Schrittweite $\alpha$ und des Heavy-Ball-Verfahrens mit Momentum $\beta$
\begin{align}
x_{k+1} &= x_k - \alpha\,\nabla f(x_k), \label{eq:gd}\\
x_{k+1} &= x_k - \alpha\,\nabla f(x_k) + \beta\,(x_k - x_{k-1}). \label{eq:hb}
\end{align}
\begin{theorem}\label{thm:rates}
Mit $\alpha = 2/(L+\mu)$ erfüllt Verfahren \eqref{eq:gd} die Abschätzung $\|x_k\| \le \rho_{\mathrm{GD}}^{\,k}\|x_0\|$ mit
$\rho_{\mathrm{GD}} = \dfrac{\kappa-1}{\kappa+1}$. Mit $\alpha = 4/(\sqrt{L}+\sqrt{\mu})^2$ und
$\beta = \bigl(\tfrac{\sqrt\kappa-1}{\sqrt\kappa+1}\bigr)^2$ konvergiert Verfahren \eqref{eq:hb} mit der
asymptotischen Rate $\rho_{\mathrm{HB}} = \dfrac{\sqrt\kappa-1}{\sqrt\kappa+1}$.
\end{theorem}
\begin{proof}
Diagonalisiere $A$ und behandle jeden Eigenwert $\lambda\in[\mu,L]$ einzeln. Beim Gradientenverfahren wird
die Iterierte in dieser Richtung mit $1-\alpha\lambda$ multipliziert; dessen Betrag ist bei
$\lambda=\mu$ und $\lambda=L$ am größten und beträgt für die angegebene Schrittweite $\rho_{\mathrm{GD}}$. Beim
Heavy-Ball-Verfahren entwickelt sich das Paar $(x_k, x_{k-1})$ mit einer $2\times2$-Matrix, deren Eigenwerte die
Nullstellen von $z^2-(1+\beta-\alpha\lambda)z+\beta=0$ sind. Für die angegebenen $\alpha$ und $\beta$ sind diese
Nullstellen komplex mit Betrag $\sqrt\beta=\rho_{\mathrm{HB}}$ für jedes $\lambda\in[\mu,L]$ \citep{polyak1964}.
\end{proof}
\begin{remark}
Wegen $-\ln\rho \approx 2/\kappa$ beim Gradientenverfahren und $\approx 2/\sqrt\kappa$ beim Heavy-Ball-Verfahren
braucht man, um eine Toleranz $\varepsilon$ zu erreichen, etwa $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ bzw.
$\tfrac{\sqrt\kappa}{2}\ln(1/\varepsilon)$ Iterationen \citep{nesterov2004}.
\end{remark}
\section{Ergebnisse}\label{sec:results}
% Stelle die Ergebnisse ohne Interpretation dar; verweise im Text auf jede Tabelle und jede Abbildung.
Tabelle~\ref{tab:iterations} listet die Iterationen auf, die nötig sind, um den Fehler um den Faktor $10^{6}$ zu
verringern, berechnet aus den Raten in Satz~\ref{thm:rates}, und Abbildung~\ref{fig:convergence} zeigt die
Fehlerschranke für $\kappa=100$.
\begin{table}[htbp]
\centering
\caption{Iterationen, die nötig sind, um den Fehler um den Faktor $10^{6}$ zu verringern.}
\label{tab:iterations}
\begin{tabular}{rrrr}
\toprule
$\kappa$ & Gradientenverfahren & Heavy Ball & Verhältnis \\
\midrule
10 & 69 & 22 & 3,1 \\
100 & 691 & 69 & 10,0 \\
1000 & 6908 & 219 & 31,5 \\
\bottomrule
\end{tabular}
\end{table}
\begin{figure}[htbp]
\centering
% Das Diagramm wird mit pgfplots gezeichnet, daher ist keine Bilddatei nötig. Um stattdessen ein Bild zu verwenden:
% \includegraphics[width=0.8\linewidth]{figure.png}
\begin{tikzpicture}
\begin{axis}[
width=0.8\linewidth, height=6cm,
xlabel={Iteration $k$}, ylabel={Fehlerschranke $\rho^{k}$},
ymode=log, xmin=0, xmax=300, ymin=1e-7, ymax=1,
grid=major, legend pos=south west,
]
\addplot[thick, domain=0:300, samples=2] {0.9802^x};
\addplot[thick, dashed, domain=0:300, samples=2] {0.8182^x};
\legend{Gradientenverfahren, Heavy Ball}
\end{axis}
\end{tikzpicture}
\caption{Schranke für den Fehler nach $k$ Iterationen für $\kappa=100$.}
\label{fig:convergence}
\end{figure}
\section{Diskussion}
Die Zahl der Iterationen wächst beim Gradientenverfahren linear mit $\kappa$ und beim Heavy-Ball-Verfahren mit
$\sqrt\kappa$. Der Vorteil von Momentum wächst also mit der Schwierigkeit des Problems: ein Faktor 3 für
$\kappa=10$ und mehr als 30 für $\kappa=10^{3}$. Die Analyse gilt nur für quadratische Funktionen; für allgemeine
konvexe Funktionen benötigt das Heavy-Ball-Verfahren andere Parameter und kann divergieren, weshalb in der
Praxis beschleunigte Varianten bevorzugt werden \citep{nesterov2004}.
\section{Schlussfolgerungen}\label{sec:conclusions}
% Fasse das Hauptergebnis, seine Grenzen und die nächsten Schritte zusammen.
Bei quadratischen Problemen verwandelt Momentum eine Iterationszahl der Ordnung $\kappa$ in eine der Ordnung
$\sqrt\kappa$. Künftige Arbeiten sollten untersuchen, wie viel dieser Beschleunigung bei nichtquadratischen
Zielfunktionen und bei Rauschen erhalten bleibt.
\section*{Danksagung}
Diese Arbeit wurde von der Beispielstiftung gefördert, Förderkennzeichen 000000.
\bibliographystyle{unsrtnat}
\bibliography{references}
\end{document}