14_Stochastic_Gradient_Descent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stochastic Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Überblick"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In viele Anwendungen hat $f$ die Struktur\n",
    "  \\begin{equation*} \n",
    "  f(x) = \\frac{1}{n} \\sum_{i=1}^n f_i(x),\n",
    "  \\quad\n",
    "  f_i \\text{ differenzierbar},\n",
    "  \\end{equation*}\n",
    "z.B. wenn $f_i$ die Loss-Funktion zum $i$-ten Trainings-Datensatz ist.\n",
    "  \n",
    "Bei einfachem Gradient-Descent muss in jedem Schritt\n",
    "  \\begin{equation*} \n",
    "  f'(x) = \\frac{1}{n} \\sum_{i=1}^n f'_i(x),\n",
    "  \\end{equation*}\n",
    "  berechnet werden.\n",
    "Dies wird nun wie folgt vereinfacht:\n",
    "\n",
    " - wähle in jedem Schritt zufällig (gleichverteilt) ein $i_t\\in\\{1,\\ldots,n\\}$ aus\n",
    "  \n",
    " - setze\n",
    "   \\begin{equation*} \n",
    "   x_{t+1} = x_t - \\gamma_t f'_{i_t}(x_t)\n",
    "   \\end{equation*}\n",
    "   \n",
    "Man bezeichnet\n",
    "   \\begin{equation*} \n",
    "   g_t = g(i_t, x_t) = f'_{i_t}(x_t)\n",
    "   \\end{equation*}\n",
    "als *stochastischen Gradienten*.\n",
    "Der Aufwand pro Schritt wird im Vergleich zum einfachen Gradient-Descent-Verfahren um\n",
    "   den Faktor $n$ reduziert."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vorüberlegungen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine direkte Übertragung der Konvergenzanalysen des Gradient-Descent-Verfahrens funktioniert zunächst nicht.\n",
    "\n",
    "Bei Gradient-Descent hatten wir aus der Konvexitätsbedingung\n",
    "  \\begin{equation*} \n",
    "  f(y) \\geq f(x) + f'(x)(y-x)\n",
    "  \\end{equation*}\n",
    "die Ungleichung\n",
    "  \\begin{equation*} \n",
    "  f_t - f_\\ast \\leq f_t' (x_t - x_\\ast)\n",
    "  \\end{equation*}\n",
    "abgeleitet und die weiteren Untersuchungen darauf aufgebaut.\n",
    "\n",
    "Bei Stochastic-Gradient-Descent geht das nicht, da\n",
    "  $g_t \\neq f'(x_t)$.\n",
    "Wir können aber zeigen, dass die Ungleichung für Erwartungswerte\n",
    "  gilt:\n",
    "  \n",
    "- ist $i_t\\in\\{1,\\ldots,n\\}$ eine gleichverteilte Zufallsvariable, dann gilt\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{P}(i_t=k) = \\frac{1}{n} \\quad \\forall k\\in\\{1,\\ldots,n\\}\n",
    "  \\end{equation*}\n",
    "  und somit\n",
    "  \\begin{align*}\n",
    "  \\mathbb{E}_{i_t}(g_t)\n",
    "  &= \\sum_{k=1}^n f'_{i_t}(x_t)\\mathbb{P}(i_t=k)\\\\\n",
    "  &= \\frac{1}{n}\\sum_{k=1}^n f'_{i_t}(x_t)\\\\\n",
    "  &= f'(x_t)\n",
    "  \\end{align*}\n",
    "  \n",
    "- $g_t$ ist also ein erwartungstreuer Schätzer von $f'(x_t)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir beginnen mit einer grundlegenden Abschätzung für Stochastic-Gradient-Descent\n",
    "  \\begin{equation*} \n",
    "  x_{t+1} = x_t - \\gamma \\underbrace{g(i_t, x_t)}_{g_t}.\n",
    "  \\end{equation*}\n",
    "  \n",
    "  \n",
    "**Lemma:** Ist $f'$ Lipschitz-stetig mit Konstante $L$, dann gilt\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}_{i_t}(f_{t+1}) - f_t\n",
    "    \\leq\n",
    "  - \\gamma f'_t \\ \\mathbb{E}_{i_t}(g_t) \n",
    "  + \\frac{1}{2} \\gamma^2 L \\ \\mathbb{E}_{i_t}(\\|g_t\\|_2^2).\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "- ist $f'$ Lipschitz-stetig dann gilt (siehe Gradient-Descent) \n",
    "    \\begin{equation*} \n",
    "    f(y) \\leq f(x) + f'(x)(y-x) + \\frac{1}{2} L \\|y-x\\|_2^2\n",
    "    \\end{equation*}\n",
    "   \n",
    "- mit $y=x_{t+1}$, $x=x_t$ erhalten wir\n",
    "    \\begin{equation*} \n",
    "    f_{t+1} - f_t \\leq f'_t(x_{t+1}-x_t) + \\frac{1}{2} L \\|x_{t+1}-x_t\\|_2^2\n",
    "    \\end{equation*}\n",
    "   \n",
    "- wegen $x_{t+1} - x_t = - \\gamma g_t$ ist\n",
    "    \\begin{equation*} \n",
    "    f_{t+1} - f_t \\leq -\\gamma f'_t g_t + \\frac{1}{2} \\gamma^2 L   \\|g_t\\|_2^2\n",
    "    \\end{equation*}\n",
    "   \n",
    "- bilden wir auf beiden Seiten $\\mathbb{E}_{i_t}$ und beachten wir, dass\n",
    "    $f_t$, $f'_t$ nicht von $i_t$ abhängen, dann folgt\n",
    "    \\begin{equation*} \n",
    "    \\mathbb{E}_{i_t}(f_{t+1}) - f_t\n",
    "    \\leq\n",
    "    - \\gamma f'_t \\ \\mathbb{E}_{i_t}(g_t) \n",
    "    + \\frac{1}{2} \\gamma^2 L \\ \\mathbb{E}_{i_t}(\\|g_t\\|_2^2)\n",
    "    \\end{equation*}\n",
    "   \n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:** \n",
    " \n",
    "- der erwartete Abstieg ist beschränkt durch\n",
    "    den Erwartunsgwert der Richtungsableitung von $f$ in Richtung $g_t$\n",
    "    \\begin{equation*} \n",
    "    f'_t \\ \\mathbb{E}_{i_t}(g_t)\n",
    "    =\n",
    "    \\mathbb{E}_{i_t}(g_t)^T f'_t \n",
    "    \\end{equation*}\n",
    "  sowie\n",
    "    \\begin{equation*} \n",
    "    \\mathbb{E}_{i_t}(\\|g_t\\|_2^2)\n",
    "    \\end{equation*}\n",
    "   \n",
    "- wie man zu $x_t$ gekommen ist, spielt keine Rolle (Markov-Eigenschaft)\n",
    "  \n",
    "- ist $g_t$ ein erwartungstreuer Schätzer, d.h. $\\mathbb{E}_{i_t}(g_t)=f'_t$,\n",
    "    dann folgt\n",
    "    \\begin{align*}\n",
    "    \\mathbb{E}_{i_t}(f_{t+1}) - f_t\n",
    "    & \\leq\n",
    "    - \\gamma f'_t \\ \\mathbb{E}_{i_t}(g_t) \n",
    "    + \\frac{1}{2} \\gamma^2 L \\ \\mathbb{E}_{i_t}(\\|g_t\\|_2^2) \\\\\n",
    "    &\\leq \n",
    "    - \\gamma \\|f'_t\\|_2^2\n",
    "    + \\frac{1}{2} \\gamma^2 L \\ \\mathbb{E}_{i_t}(\\|g_t\\|_2^2)\n",
    "    \\end{align*}\n",
    "    \n",
    "- kann $\\mathbb{E}_{i_t}(\\|g_t\\|_2^2)$ \"deterministisch\" beschränkt werden, dann\n",
    "    erhalten wir wieder einen hinreichenden Abstieg\n",
    "    \n",
    "    \n",
    "**Definition:** Es sei\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{V}_{i_t} = \\mathbb{E}_{i_t}(\\|g_t\\|_2^2) - \\|\\mathbb{E}_{i_t}(g_t) \\|_2^2.\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für den Rest des Kapitels treffen wir folgende Annahmen:\n",
    "\n",
    "- $x_t \\in X$, $X$ offen, $f|_X \\geq \\bar{f}$\n",
    " \n",
    "- $\\exists c_G \\geq c > 0$ so dass $\\forall t$ gilt\n",
    "    \\begin{equation*} \n",
    "    f_t \\ \\mathbb{E}_{i_t}(g_t) \\geq c \\| f'_t \\|_2^2,\n",
    "    \\quad\n",
    "    \\| \\mathbb{E}_{i_t}(g_t) \\|_2 \\leq c_G \\| f'_t \\|_2\n",
    "    \\end{equation*}\n",
    "   \n",
    "- $\\exists M,M_V \\geq 0$ mit\n",
    "    \\begin{equation*} \n",
    "    \\mathbb{V}_{i_t} \\leq M + M_V \\| f'_t \\|_2^2\n",
    "    \\end{equation*}\n",
    "   \n",
    "\n",
    "**Bemerkung:** Ist $g_t$ ein erwartungstreuer Schätzer von $f'_t$, dann\n",
    "  ist $c=c_G=1$.\n",
    "  \n",
    "\n",
    "Aus der Annahme folgt nun\n",
    "  \\begin{align*}\n",
    "    \\mathbb{E}_{i_t}(\\|g_t\\|_2^2)\n",
    "    &  =   \\mathbb{V}_{i_t} +  \\| \\mathbb{E}_{i_t}(g_t) \\|_2^2\\\\\n",
    "    &\\leq  M + M_V \\| f'_t \\|_2^2 + c_G^2 \\| f'_t \\|_2^2 \\\\\n",
    "    &\\leq  M + \\underbrace{(M_V + c_G^2)}_{M_G \\geq 0} \\| f'_t \\|_2^2 .\n",
    "  \\end{align*}\n",
    "Kombiniert mit dem letzten Lemma erhalten wir\n",
    "  \\begin{align*}\n",
    "  \\mathbb{E}_{i_t}(f_{t+1}) - f_t\n",
    "  &\\leq\n",
    "    - \\gamma f'_t \\ \\mathbb{E}_{i_t}(g_t) \n",
    "    + \\frac{1}{2} \\gamma^2 L \\ \\mathbb{E}_{i_t}(\\|g_t\\|_2^2)\\\\\n",
    "  &\\leq -\\gamma c \\| f'_t \\|_2^2 \n",
    "        +\\frac{1}{2} \\gamma^2 L \\big(M + M_G \\| f'_t \\|_2^2 \\big) \\\\\n",
    "  &= -\\gamma \\big(c - \\frac{\\gamma L}{2} M_G \\big) \\| f'_t \\|_2^2 \n",
    "     + \\frac{1}{2} \\gamma^2 L M\n",
    "  \\end{align*}\n",
    "und somit\n",
    "\n",
    "\n",
    "**Lemma:**\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}_{i_t}(f_{t+1}) - f_t \n",
    "  \\leq\n",
    "     -\\gamma \\big(c - \\frac{\\gamma L}{2} M_G \\big) \\|  f'_t \\|_2^2 \n",
    "     + \\frac{1}{2} \\gamma^2 L M\n",
    "  \\end{equation*}\n",
    "  \n",
    "\n",
    "**Bemerkung:**\n",
    "\n",
    "  - die rechte Seite der Abschätzung ist deterministisch\n",
    "  \n",
    "  - die Schranke für $\\mathbb{E}_{i_t}(f_{t+1}) - f_t$ hängt nur von $x_t$ und $i_t$\n",
    "    ab und *nicht* von früheren $x_s$, $s<t$\n",
    "    \n",
    "  - ist $\\gamma$ klein genug, dann ist $\\mathbb{E}_{i_t}(f_{t+1}) - f_t < 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Konvergenz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$f$ sei jetzt differenzierbar, $L$-glatt und $\\mu$-konvex \n",
    "  und zusätzlich soll $x_\\ast$ mit $f_\\ast = f(x_\\ast) = \\inf_x f(x)$ existieren.\n",
    "Wir werden nun zeigen, dass wir unter diesen Voraussetzungen bei konstanter\n",
    "  Schrittweite $\\gamma$ zwar keine Konvergenz erhalten, aber zumindest in\n",
    "  eine Umgebung von $x_\\ast$ gelangen, deren Größe asymptotisch proportional\n",
    "  zu $\\gamma$ ist.\n",
    "  \n",
    "Wir verwenden im Folgenden die Notation\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}(f_{t}) = \\mathbb{E}_{i_{0}}\\ldots\\mathbb{E}_{i_{t-1}}(f_t).\n",
    "  \\end{equation*}\n",
    "  \n",
    "  \n",
    "**Satz:**\n",
    "Es sei $f$ differenzierbar, $L$-glatt, $\\mu$-konvex \n",
    "  und es existiere \n",
    "  $x_\\ast$ mit $f_\\ast = f(x_\\ast)= \\inf_x f(x)$.\n",
    "  Ist\n",
    "  \\begin{equation*} \n",
    "  0 < \\gamma \\leq \\frac{c}{L M_G}\n",
    "  \\end{equation*}\n",
    "dann gilt\n",
    "  \\begin{align*} \n",
    "  \\mathbb{E}(f_{t} - f_\\ast) \n",
    "  &\\leq \n",
    "  \\frac{\\gamma L M}{2 \\mu c} \n",
    "  + (1-\\gamma \\mu c)^{t-1} \n",
    "    \\big(\\mathbb{E}(f_1 - f_\\ast) - \\frac{\\gamma L M}{2 \\mu c}\\big)\\\\\n",
    "  &\\xrightarrow{t \\to \\infty} \\frac{\\gamma L M}{2 \\mu c}.\n",
    "  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "- aus dem letzten Lemma im vorherigen Abschnitt wissen wir\n",
    "   \\begin{align*} \n",
    "   \\mathbb{E}_{i_t}(f_{t+1} - f_t)\n",
    "   &=\n",
    "   \\mathbb{E}_{i_t}(f_{t+1}) - f_t \n",
    "   \\\\\n",
    "   &\\leq\n",
    "      -\\gamma \\big(c - \\frac{\\gamma L}{2} M_G \\big) \\|  f'_t \\|_2^2 \n",
    "      + \\frac{1}{2} \\gamma^2 L M\n",
    "   \\end{align*}\n",
    "  \n",
    "- wegen \n",
    "  \\begin{equation*} \n",
    "  0 < \\gamma \\leq \\frac{c}{L M_G}\n",
    "  \\end{equation*}\n",
    "  ist\n",
    "  \\begin{equation*} \n",
    "  \\frac{\\gamma L}{2}M_G  \\leq \\frac{c}{2},\n",
    "  \\end{equation*}\n",
    "  und deshalb\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}_{i_t}(f_{t+1}) - f_t \n",
    "  \\leq\n",
    "     - \\frac{\\gamma c}{2} \\|  f'_t \\|_2^2 \n",
    "     + \\frac{1}{2} \\gamma^2 L M\n",
    "  \\end{equation*}\n",
    "  \n",
    "- oben hatten wir gesehen, dass für $\\mu$-konvexe Funktionen auf $\\mathbb{R}^d$\n",
    "  \\begin{equation*} \n",
    "  f(x) - f_\\ast \\leq \\frac{1}{2\\mu} \\|f'(x)\\|_2^2 \n",
    "  \\end{equation*}\n",
    "  gilt, also\n",
    "  \\begin{equation*} \n",
    "  \\|  f'_t \\|_2^2  \\geq 2\\mu(f_t - f_\\ast)\n",
    "  \\end{equation*}\n",
    "  und somit\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}_{i_t}(f_{t+1}- f_\\ast) - (f_t - f_\\ast)\n",
    "  \\leq\n",
    "     -\\gamma\\mu c (f_t - f_\\ast)\n",
    "     + \\frac{1}{2} \\gamma^2 L M\n",
    "  \\end{equation*}\n",
    " \n",
    "- nun bilden wir auf beiden Seiten die Erwartungswerte \n",
    "    $\\mathbb{E}_{i_1} \\ldots \\mathbb{E}_{i_{t-1}}$ und\n",
    "  erhalten\n",
    "    \\begin{equation*} \n",
    "    \\mathbb{E}(f_{t+1}- f_\\ast) - \\mathbb{E}(f_t - f_\\ast)\n",
    "    \\leq\n",
    "      -\\gamma\\mu c \\mathbb{E}(f_t - f_\\ast)\n",
    "      + \\frac{1}{2} \\gamma^2 L M\n",
    "    \\end{equation*}\n",
    "  also\n",
    "    \\begin{equation*} \n",
    "    \\mathbb{E}(f_{t+1}- f_\\ast) \n",
    "    \\leq\n",
    "      (1 -\\gamma\\mu c) \\mathbb{E}(f_t - f_\\ast)\n",
    "      + \\frac{1}{2} \\gamma^2 L M\n",
    "    \\end{equation*}\n",
    "  \n",
    "- subtrahiert man $\\frac{\\gamma L M}{2 \\mu c}$\n",
    "  auf beiden Seiten, so ergibt sich\n",
    "    \\begin{align*}\n",
    "    \\mathbb{E}(f_{t+1}- f_\\ast) - \\frac{\\gamma L M}{2 \\mu c}\n",
    "    & \\leq\n",
    "     (1 -\\gamma\\mu c) \\mathbb{E}(f_t - f_\\ast)\n",
    "     + \\frac{1}{2} \\gamma^2 L M - \\frac{\\gamma L M}{2 \\mu c} \\\\\n",
    "    & = \n",
    "     (1 -\\gamma\\mu c) \n",
    "     \\big(\n",
    "     \\mathbb{E}(f_t - f_\\ast) - \\frac{\\gamma L M}{2 \\mu c}\n",
    "     \\big)\n",
    "   \\end{align*}\n",
    "   \n",
    "- wegen $\\mu \\leq L$ und $M_G \\geq c_G^2 \\geq c^2$ ist \n",
    "    \\begin{equation*} \n",
    "    0 < \\gamma\\mu c \n",
    "      \\leq \\frac{\\mu c^2}{L M_G}\n",
    "      \\leq \\frac{c^2}{M_G}\n",
    "      \\leq 1\n",
    "    \\end{equation*}\n",
    "   \n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ohne \"Rauschen\" ist $M=0$ und\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}(f_{t} - f_\\ast) \n",
    "  \\leq \n",
    "  (1-\\gamma \\mu c)^{t-1} \\mathbb{E}(f_1 - f_\\ast)\n",
    "  \\end{equation*}\n",
    "so dass wir eine Komplexität von $\\mathcal{O}\\big(\\log(\\frac{1}{\\varepsilon})\\big)$\n",
    "  erhalten.\n",
    "  \n",
    "Mt \"Rauschen\" haben wir\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}(f_{t} - f_\\ast) \n",
    "  \\leq \n",
    "  \\underbrace{\\frac{\\gamma L M}{2 \\mu c}}_{\\text{fix}}\n",
    "  + \\underbrace{\n",
    "    (1-\\gamma \\mu c)^{t-1} \n",
    "    \\big(\\mathbb{E}(f_1 - f_\\ast) - \\frac{\\gamma L M}{2 \\mu c}\\big)\n",
    "    }_{\\text{geometrische Reduktion}},\n",
    "  \\end{equation*}\n",
    "d.h. wir erreichen\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}(f_{t} - f_\\ast) \n",
    "  \\leq \\frac{\\gamma L M}{2 \\mu c} + \\varepsilon\n",
    "  \\end{equation*}\n",
    "in \n",
    "  \\begin{equation*} \n",
    "  t = \\mathcal{O}\\big(\\log(\\frac{1}{\\varepsilon})\\big)\n",
    "  \\end{equation*}\n",
    "Schritten.\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\frac{\\gamma L M}{2 \\mu c}$ wird klein, wenn $\\gamma$ klein wird, wobei\n",
    "  dann aber $1 - \\gamma\\mu c$ nahe bei $1$ liegt, so dass die geometrische\n",
    "  Reduktion nur sehr langsam ist.\n",
    "  \n",
    "Dies führt auf die Idee des Restarts:\n",
    "\n",
    " - starte mit einer Schrittweite $\\gamma^{(1)}$ und iteriere bis\n",
    "   \\begin{equation*} \n",
    "   \\mathbb{E}(f_{t} - f_\\ast) \n",
    "   \\leq \\frac{\\gamma^{(1)} L M}{2 \\mu c} + \\varepsilon^{(1)}\n",
    "   \\end{equation*}\n",
    "  \n",
    " - verkürze die Schrittweite auf $\\gamma^{(2)} < \\gamma^{(1)}$ und iteriere bis\n",
    "   die rechte Seite hinreichend klein ist\n",
    "   \n",
    "Das kann man soweit ausbauen, dass man in jedem Schritt die Schrittweite\n",
    "  $\\gamma$ anpasst."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Satz:**\n",
    "Es sei $f$ differenzierbar, $L$-glatt, $\\mu$-konvex. \n",
    "Es existiere ein $x_\\ast$ mit $f_\\ast = f(x_\\ast)=\\inf_x f(x)$ und\n",
    "es sei\n",
    "  \\begin{equation*} \n",
    "  \\gamma_t = \\frac{\\beta}{\\gamma + t},\n",
    "  \\quad\n",
    "  \\beta > \\frac{1}{\\mu c},\n",
    "  \\quad\n",
    "  \\gamma > 0,\n",
    "  \\quad\n",
    "  \\gamma_1 < \\frac{c}{L M_G}.\n",
    "  \\end{equation*}\n",
    "Dann gilt\n",
    "  \\begin{equation*} \n",
    "  \\mathbb{E}(f_{t} - f_\\ast) \n",
    "  \\leq \n",
    "  \\frac{\\nu}{\\gamma + t}\n",
    "  \\end{equation*}\n",
    "mit\n",
    "  \\begin{equation*}\n",
    "  \\nu = \\max\n",
    "  \\Big(\n",
    "    \\frac{\\beta^2 L M}{2(\\beta\\mu c -1)},\n",
    "    (\\gamma+1)\\ \\mathbb{E}(f_{1} - f_\\ast)\n",
    "  \\Big).\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "- aus den Voraussetzungen folgt\n",
    "   \\begin{equation*} \n",
    "   \\gamma_t L M_G \\leq \\gamma_1 L M_G \\leq c\n",
    "   \\quad\n",
    "   \\forall t\n",
    "   \\end{equation*}\n",
    " \n",
    "- mit $\\gamma = \\gamma_t$ folgt aus dem letzten Lemma\n",
    "   \\begin{align*}\n",
    "   \\mathbb{E}_{i_t}(f_{t+1}) - f_t \n",
    "   &\\leq\n",
    "     -\\gamma_t \\big(c - \\frac{\\gamma_t L}{2} M_G \\big) \\| f'_t \\|_2^2 \n",
    "     + \\frac{1}{2} \\gamma_t^2 L M \\\\\n",
    "   &=\n",
    "     \\big( -\\gamma_t c + \\gamma_t \\frac{\\gamma_t L  M_G}{2} \\big) \\| f'_t \\|_2^2 \n",
    "     + \\frac{1}{2} \\gamma_t^2 L M \\\\\n",
    "   &\\leq\n",
    "     - \\frac{1}{2} \\gamma_t c  \\| f'_t \\|_2^2   \n",
    "     + \\frac{1}{2} \\gamma_t^2 L M \\\\\n",
    "   \\end{align*}\n",
    "     \n",
    "- wegen der $\\mu$-Konvexität von $f$ auf $\\mathbb{R}^d$ gilt wieder\n",
    "   \\begin{equation*} \n",
    "   \\|  f'_t \\|_2^2  \\geq 2\\mu(f_t - f_\\ast)\n",
    "   \\end{equation*}\n",
    "  und somit\n",
    "   \\begin{equation*} \n",
    "   \\mathbb{E}_{i_t}(f_{t+1}) - f_t \n",
    "   \\leq\n",
    "     - \\gamma_t \\mu c  (f_t - f_\\ast)   \n",
    "     + \\frac{1}{2} \\gamma_t^2 L M ,\n",
    "   \\end{equation*}\n",
    "  bzw.\n",
    "   \\begin{equation*} \n",
    "   \\mathbb{E}_{i_t}(f_{t+1}) - f_\\ast - (f_t - f_\\ast)\n",
    "   \\leq\n",
    "     - \\gamma_t \\mu c  (f_t - f_\\ast)   \n",
    "     + \\frac{1}{2} \\gamma_t^2 L M\n",
    "   \\end{equation*}\n",
    "   \n",
    "- nun bilden wir auf beiden Seiten die Erwartungswerte \n",
    "   $\\mathbb{E}_{i_1} \\ldots \\mathbb{E}_{i_{t-1}}$ und erhalten\n",
    "   \\begin{equation*} \n",
    "   \\mathbb{E}(f_{t+1} - f_\\ast)\n",
    "   \\leq\n",
    "     (1- \\gamma_t \\mu c) \\ \\mathbb{E}(f_t - f_\\ast)   \n",
    "     + \\frac{1}{2} \\gamma_t^2 L M   \n",
    "   \\end{equation*}\n",
    "   \n",
    "- per Induktion können wir nun die Aussage des Satzes beweisen\n",
    " \n",
    "- für $t=1$ folgt die Behauptung direkt aus der Definition von $\\nu$\n",
    " \n",
    "- für den Schritt $t \\to t+1$ erhalten wir\n",
    "   \\begin{align*}\n",
    "   \\mathbb{E}(f_{t+1} - f_\\ast)\n",
    "   & \\leq  \n",
    "     (1- \\gamma_t \\mu c) \\ \\mathbb{E}(f_t - f_\\ast)   \n",
    "     + \\frac{1}{2} \\gamma_t^2 L M \\\\\n",
    "   & \\leq  \n",
    "     \\big(1- \\frac{\\beta}{\\gamma + t}\\mu c\\big) \\ \\mathbb{E}(f_t - f_\\ast)   \n",
    "     + \\frac{1}{2} \\frac{\\beta^2}{(\\gamma + t)^2} L M \\\\\n",
    "   & \\leq  \n",
    "     \\big(1- \\frac{\\beta}{\\gamma + t}\\mu c\\big) \\ \\frac{\\nu}{\\gamma + t}   \n",
    "     + \\frac{1}{2} \\frac{\\beta^2}{(\\gamma + t)^2} L M \\\\\n",
    "   & =  \n",
    "     \\frac{(\\gamma + t - \\beta\\mu c)\\nu}{(\\gamma + t)^2}\n",
    "     + \\frac{\\beta^2 L M}{2 (\\gamma + t)^2}  \\\\\n",
    "   & =  \n",
    "     \\frac{\\gamma + t - 1}{(\\gamma + t)^2}\\nu\n",
    "     - \\frac{\\beta\\mu c-1}{(\\gamma + t)^2}\\nu\n",
    "     + \\frac{\\beta^2 L M}{2 (\\gamma + t)^2}\n",
    "     \\\\\n",
    "   & =  \n",
    "     \\frac{\\gamma + t - 1}{(\\gamma + t)^2}\\nu\n",
    "     +\n",
    "     %\\underbrace{\n",
    "     \\frac{\\beta^2 L M - 2(\\beta\\mu c-1)\\nu}{2 (\\gamma + t)^2}\n",
    "     %}_{\\leq 0 \\ \\text{nach Definition von}\\ \\nu} \n",
    "   \\end{align*}\n",
    "   \n",
    "- nach Definition von $\\nu$ gilt\n",
    "   \\begin{equation*} \n",
    "   \\nu \\geq \\frac{\\beta^2 L M}{2(\\beta\\mu c -1)}\n",
    "   \\end{equation*}\n",
    "  also\n",
    "   \\begin{equation*} \n",
    "   \\beta^2 L M - 2(\\beta\\mu c-1)\\nu \\leq 0\n",
    "   \\end{equation*}\n",
    "  und somit \n",
    "   \\begin{align*}\n",
    "   \\mathbb{E}(f_{t+1} - f_\\ast) \n",
    "   &\\leq \\frac{\\gamma + t - 1}{(\\gamma + t)^2}\\nu \\\\\n",
    "   &\\leq \\frac{(\\gamma + t - 1)(\\gamma + t + 1)}{(\\gamma + t)^2}\n",
    "         \\frac{\\nu}{\\gamma + t + 1} \\\\\n",
    "   &= \\frac{(\\gamma + t)^2 - 1}{(\\gamma + t)^2}\n",
    "         \\frac{\\nu}{\\gamma + t + 1} \\\\\n",
    "   &\\leq \\frac{\\nu}{\\gamma + t + 1}\n",
    "   \\end{align*}\n",
    "   \n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zusammenfassung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ist $f: \\mathbb{R}^d \\to  \\mathbb{R}$ differenzierbar, $L$-glatt und $\\mu$-konvex \n",
    "   mit $f_\\ast = f(x_\\ast) = \\inf_x f(x)$ dann haben wir für Stochastic-Gradient-Descent\n",
    "   \\begin{equation*} \n",
    "   x_{t+1} = x_t - \\gamma_t f'_{i_t}(x_t)\n",
    "   \\end{equation*}\n",
    "   folgende Ergebnisse gezeigt:\n",
    "   \n",
    "   - ist $\\gamma$ konstant, dann ist\n",
    "     \\begin{equation*} \n",
    "     \\mathbb{E}(f_t) - f_\\ast \\leq c(\\gamma) + \\varepsilon\n",
    "     \\end{equation*}\n",
    "     in $\\mathcal{O}(\\log\\frac{1}{\\varepsilon})$ Schritten\n",
    "     \n",
    "   - ist $\\gamma \\sim \\frac{1}{t}$, dann ist\n",
    "     \\begin{equation*} \n",
    "     \\mathbb{E}(f_t) - f_\\ast \\leq  \\varepsilon\n",
    "     \\end{equation*}\n",
    "     mit $t = \\mathcal{O}(\\frac{1}{\\varepsilon})$\n",
    "     \n",
    "- Gradient-Descent liefert für $f$ $L$-glatt und $\\mu$-konvex $, 0 < \\gamma \\leq \\frac{1}{L}$\n",
    "    \\begin{equation*} \n",
    "    f_{t}-f_\\ast \\leq \\varepsilon\n",
    "    \\end{equation*}\n",
    "    in $t = \\mathcal{O}\\Big( \\log\\big(\\frac{1}{\\varepsilon}\\big) \\Big)$ Schritten\n",
    "    \n",
    "Bei Stochastic-Gradient-Descent benötigen wir also deutlich mehr Schritte,\n",
    "  wobei jeder einzelne Schritt wegen der vereinfachten Gradientenberechnung $f'_{i_t}$\n",
    "  sehr viel weniger Aufwand verursacht.\n",
    "     \n",
    "Proximal- bzw. Subgradienten-Verfahren können analog \"umgebaut\" werden."
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.6"
  },
  "nbTranslate": {
   "displayLangs": [
    "fr",
    "en"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": false,
   "sourceLang": "en",
   "targetLang": "fr",
   "useGoogleTranslate": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}