12_Subgradient_Descent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Subgradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Überblick"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bisher haben wir immer $f\\in C^1(\\mathbb{R}^d)$ vorausgesetzt.\n",
    "In der Praxis trifft das nicht immer zu (Lasso, RELU-MLP).\n",
    "\n",
    "Ist $f$ konvex, dann existiert in jedem Punkt der Subgradient.\n",
    "Wir benutzen jetzt bei Gradient Descent statt des \n",
    "(eventuell nicht existierenden) Gradienten einen Subgradienten.\n",
    "\n",
    "Die fehlende Glattheit von $f$ wird sich negativ auf die Konvergenzgeschwindigkeit auswirken."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grundlagen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definition**:\n",
    "\n",
    "- ist $f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\rightarrow \\mathbb{R}$, \n",
    "    dann ist $g\\in \\mathbb{R}^d$ *Subgradient* von $f$ in $x\\in \\mathrm{dom}(f)$, falls\n",
    "    \\begin{equation*} \n",
    "    f(y) \\geq f(x) + g^T(y-x) \\quad \\forall y\\in\\mathrm{dom}(f)\n",
    "    \\end{equation*}\n",
    "    \n",
    "- die Menge aller Subgradienten von $f$ an der Stelle $x$ bezeichnen wir mit    \n",
    "    \\begin{equation*} \n",
    "    \\partial f(x) = \\big\\{g\\ |\\ g\\ \\text{ist Subgradient von}\\ f\\ \\text{in}\\ x\\big\\}\n",
    "    \\end{equation*}\n",
    "    \n",
    "\n",
    "**Beispiel:** Ist $f(x)=|x|$, dann ist $\\partial f(0) = [-1,1]$, denn\n",
    "\\begin{equation*} \n",
    "|y| = f(y) \\geq f(0) + g(y-0) = gy \\quad \\forall y\\in\\mathbb{R}\n",
    "\\end{equation*}\n",
    "genau dann wenn\n",
    "\\begin{equation*} \n",
    "g \\in [-1,1].\n",
    "\\end{equation*}\n",
    "  \n",
    "  \n",
    "**Lemma**: Ist $f$ differenzierbar in $x$, dann gilt $\\partial f(x) \\subset \\{f'(x)\\}$, also\n",
    "  $\\partial f(x) = \\{f'(x)\\}$ oder $\\partial f(x) = \\emptyset$.\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Ungleichung $f(y) \\geq f(x) + g^T(y-x)$ sieht aus wie die Konvexitätsbedingung für $C^1$-Funktionen,\n",
    "  nur dass $f'(x)$ durch $g$ ersetzt wurde. \n",
    "Dies ist kein Zufall.\n",
    "\n",
    "\n",
    "**Lemma**: $f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\rightarrow \\mathbb{R}$ ist konvex \n",
    "  genau dann, wenn $\\mathrm{dom}(f)$ konvex ist und\n",
    "  \\begin{equation*} \n",
    "  \\partial f(x) \\neq \\emptyset\n",
    "  \\quad\n",
    "  \\forall x\\in\\mathrm{dom}(f).\n",
    "  \\end{equation*}\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "\"$\\Rightarrow$\"\n",
    "\n",
    "- ist $f$ konvex, so ist $\\mathrm{epi}(f)$ konvex \n",
    "  \n",
    "- $\\partial f(x) \\neq \\emptyset$ folgt aus dem\n",
    " [Existenzsatz für Stützhyperebenen](https://de.wikipedia.org/wiki/St%C3%BCtzhyperebene) für konvexe Mengen angewandt auf $\\mathrm{epi}(f)$\n",
    "\n",
    "\"$\\Leftarrow$\"\n",
    "\n",
    "- nach Voraussetzung ist $\\mathrm{dom}(f)$ konvex \n",
    "  und $\\partial f(x) \\neq \\emptyset$, d.h.\n",
    "  es existiert $g(x) \\in \\partial f(x)$ mit\n",
    "\\begin{equation*} \n",
    "f(y) \\geq f(x) +g(x) (y-x) \\quad \\forall x,y\\in \\mathrm{dom}(f)\n",
    "\\end{equation*}\n",
    "\n",
    "- für $t\\in \\left[ 0,1\\right]$ setzen wir\n",
    "\\begin{equation*} \n",
    "z= (1-t) x+ty\n",
    "\\end{equation*}\n",
    "\n",
    "- dann ist $z\\in \\mathrm{dom}(f)$ und\n",
    "\\begin{equation*} \n",
    "\\begin{aligned}\n",
    "f(x) \n",
    "&\\geq f(z) + g(z) (x-z) \n",
    "\\\\ \n",
    "f(y) \n",
    "&\\geq f(z) + g(z) (y-z)\n",
    "\\end{aligned}\n",
    "\\end{equation*}\n",
    "\n",
    "- multiplizieren wir die erste Ungleichung mit $1-t$, die zweite mit $t$ und addieren die Ergebnisse, dann erhalten wir\n",
    "\\begin{align*}\n",
    " (1-t) f(x) + t f(y) \n",
    "&\\geq (1-t)\\big(f(z) +g(z)  (x-z) \\big) \n",
    "\\\\\n",
    "& \\quad + t \\big(f(z) +g(z) (y-z)\\big)\\\\\n",
    "&= f(z) +g(z) \\big( \\underbrace{( 1-t) x+ty}_z -z\\big)\\\\\n",
    "&= f(z) \\\\\n",
    "&= f\\big(( 1-t) x+ty \\big)\n",
    "\\end{align*}\n",
    "\n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Existenz von Subgradienten und Konvexität sind also äquivalent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Einige weitere Eigenschaften des Gradienten lassen sich auch auf Subgradienten übertragen.\n",
    "Für Lipschitz-Stetigkeit bei $C^1$-Funktionen $f$ hatten wir $\\|f'(x)\\|\\leq L_f$.\n",
    "Dies gilt analog auch für Subgradienten.\n",
    "\n",
    "\n",
    "**Lemma**: $f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\rightarrow \\mathbb{R}$ konvex, $\\mathrm{dom}(f)$ offen.\n",
    "  Dann ist\n",
    "  \\begin{equation*} \n",
    "  \\|f(x) - f(y)\\| \\leq L_f \\|x - y\\| \\quad \\forall x,y\\in \\mathrm{dom}(f)\n",
    "  \\end{equation*}\n",
    "äquivalent zu\n",
    "  \\begin{equation*} \n",
    "  \\|g\\| \\leq L_f \\quad \\forall g \\in \\partial f(x) \\quad \\forall x\\in \\mathrm{dom}(f).\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis**: \n",
    "\n",
    "\"$\\Rightarrow$\"\n",
    "\n",
    "  - für $x \\in \\mathrm{dom}(f)$, $g \\in \\partial f(x)$, $\\varepsilon>0$ definieren wir\n",
    "  \\begin{equation*} \n",
    "    y = \n",
    "    \\begin{cases}\n",
    "    x + \\varepsilon \\frac{g}{\\|g\\|} & g \\neq 0\\\\\n",
    "    x & g=0\n",
    "    \\end{cases}\n",
    "    \\end{equation*}\n",
    "  \n",
    "- damit folgt\n",
    "    \\begin{equation*} \n",
    "    y -x = \n",
    "    \\begin{cases}\n",
    "    \\varepsilon \\frac{g}{\\|g\\|} & g \\neq 0\\\\\n",
    "    0 & g=0\n",
    "    \\end{cases}\n",
    "    \\end{equation*}\n",
    "  bzw.\n",
    "    \\begin{equation*} \n",
    "    \\|y-x\\|\n",
    "    = \n",
    "    \\begin{cases}\n",
    "    \\varepsilon & g \\neq 0\\\\\n",
    "    0 & g=0 \n",
    "    \\end{cases}\n",
    "    \\leq \\varepsilon\n",
    "    \\end{equation*}\n",
    "  \n",
    "- wegen $\\mathrm{dom}(f)$ offen ist für $\\varepsilon>0$ hinreichend klein \n",
    "  auch $y\\in\\mathrm{dom}(f)$\n",
    "  \n",
    "- außerdem gilt\n",
    "    \\begin{equation*} \n",
    "    g^T(y-x)\n",
    "    = \n",
    "    \\begin{cases}\n",
    "    \\varepsilon\\frac{g^T g}{\\|g\\|} & g \\neq 0\\\\\n",
    "    0 & g=0 \n",
    "    \\end{cases}\n",
    "    = \\varepsilon\\|g\\|\n",
    "    \\end{equation*}\n",
    "  \n",
    "- wegen $g \\in \\partial f(x)$ ist dann\n",
    "    \\begin{equation*} \n",
    "    f(y) \\geq f(x) + g^T(y-x) = f(x) + \\varepsilon\\|g\\| \n",
    "    \\end{equation*}\n",
    "  \n",
    "- da $f$ Lipschitz-stetig ist folgt\n",
    "    \\begin{equation*} \n",
    "    L_f \\varepsilon \\geq L_f \\|y-x\\| \\geq f(y) - f(x) \\geq \\varepsilon\\|g\\|, \n",
    "    \\end{equation*}\n",
    "  also\n",
    "    \\begin{equation*} \n",
    "    \\|g\\| \\leq L_f\n",
    "    \\end{equation*}\n",
    "    \n",
    "\"$\\Leftarrow$\"\n",
    "  \n",
    "- für $x,y \\in \\mathrm{dom}(f)$ und $g \\in \\partial f(x)$ gilt\n",
    "    \\begin{equation*} \n",
    "    f(y) \\geq f(x) + g^T(y-x)\n",
    "    \\end{equation*}\n",
    "  also\n",
    "    \\begin{equation*} \n",
    "    f(x) - f(y) \\leq  g^T(x-y)\n",
    "    \\end{equation*}\n",
    "    \n",
    "- mit Cauchy-Schwartz und $\\|g\\| \\leq L_f$ folgt\n",
    "    \\begin{equation*} \n",
    "    f(x) - f(y) \\leq  \\|g\\| \\|x-y\\| \\leq L_f \\|x -y\\| \n",
    "    \\end{equation*}    \n",
    "    \n",
    "- Vertauschen von $x$ und $y$ liefert schließlich\n",
    "    \\begin{equation*} \n",
    "    |f(x) - f(y)| \\leq L_f \\|x -y\\| \\quad \\forall x,y \\in \\mathrm{dom}(f)\n",
    "    \\end{equation*}    \n",
    "    \n",
    "$\\square$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Satz**: $f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\rightarrow \\mathbb{R}$, $x \\in \\mathrm{dom}(f)$, dann gilt\n",
    "  \\begin{equation*} \n",
    "  0 \\in \\partial f(x) \n",
    "  \\quad\\Leftrightarrow\\quad\n",
    "  x\\ \\text{ist globales Minimum von}\\ f.\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis**: \n",
    "  \n",
    "\"$\\Rightarrow$\"\n",
    "  \n",
    "- ist $0 \\in \\partial f(x)$, dann folgt aus der Definition des Subgradienten\n",
    "    \\begin{equation*} \n",
    "    f(y) \\geq f(x) + 0^T(y-x) =  f(x) \\quad \\forall y\\in\\mathrm{dom}(f)\n",
    "    \\end{equation*}\n",
    "    \n",
    "\"$\\Leftarrow$\"\n",
    "  \n",
    "- ist $x \\in\\mathrm{dom}(f)$ globales Minimum, dann gilt\n",
    "    \\begin{equation*} \n",
    "    f(y) \\geq f(x) = f(x) + 0^T(y-x)  \\quad \\forall y\\in\\mathrm{dom}(f)\n",
    "    \\end{equation*}\n",
    "\n",
    "$\\square$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:**\n",
    "\n",
    "- die Bedingung $0 \\in \\partial f(x)$ ist stärker als $f'(x)=0$ bei $C^1$-Funktionen\n",
    "  \n",
    "- $f'(x)=0$ ist nur eine *notwendige Bedingung* für *lokale* Minima, d.h.\n",
    "    aus $f'(x)=0$ alleine kann man i.A. nicht folgern, dass $x$ ein lokales\n",
    "    oder gar globales Minimum ist\n",
    "    \n",
    "- dagegen garantiert $0 \\in \\partial f(x)$ immer, dass $x$ globales Minimum ist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vorüberlegungen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir betrachten nun *Subgradient-Descent*\n",
    "  \\begin{equation*} \n",
    "  x_{t+1} = x_t - \\gamma_t g_t, \\quad g_t \\in \\partial f(x_t).\n",
    "  \\end{equation*}\n",
    "Dabei ist $g_t$ *irgendein* Element aus $\\partial f(x_t)$.\n",
    "\n",
    "Ist $f$ konvex, dann ist $\\partial f(x) \\neq \\emptyset$ $\\forall x$,\n",
    "  so dass immer mindestens ein $g_t$ existiert.\n",
    "\n",
    "Ist $f$ konvex und in $x_t$ differenzierbar, dann gilt\n",
    "  \\begin{equation*} \n",
    "  \\partial f(x_t) = \\{ f'(x_t)\\}\n",
    "  \\end{equation*}\n",
    "und somit\n",
    "  \\begin{equation*} \n",
    "  g_t = f'(x_t).\n",
    "  \\end{equation*}\n",
    "Wir lassen auch variable Schrittweite $\\gamma_t$ zu."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unter diesen Voraussetzungen wollen wir analog zu Gradient-Descent die Konvergenzeigenschaften untersuchen.\n",
    "Viele Ergebnisse lassen sich direkt übertragen, indem man einfach $f'_t$ durch $g_t$ ersetzt.\n",
    "\n",
    "Für Schrittweite $\\gamma$ erhalten wir damit\n",
    "  \\begin{equation*} \n",
    "  g_{t}^T\\left(x_{t}-x_{*}\\right) \n",
    "  =\\frac{1}{2 \\gamma}\\big(\\gamma^{2}\\|g_{t}\\|_{2}^{2}+\\|x_{t}-x_{*}\\|_{2}^{2}-\\|x_{t+1}-x_{*}\\|_{2}^{2}\\big).\n",
    "  \\end{equation*}\n",
    "  \n",
    "Da $g_t$ Subgradient in $x_t$ ist, gilt\n",
    "  \\begin{equation*} \n",
    "  f_\\ast \\geq f_t + g_t^T (x_\\ast - x_t)\n",
    "  \\end{equation*}\n",
    "und somit\n",
    "  \\begin{align*} \n",
    "  f_t - f_\\ast \n",
    "  &\\leq g_t^T (x_t - x_\\ast)\n",
    "  \\\\\n",
    "  &=\\frac{1}{2 \\gamma}\\big(\\gamma^{2}\\|g_{t}\\|_{2}^{2}+\\|x_{t}-x_{*}\\|_{2}^{2}-\\|x_{t+1}-x_{*}\\|_{2}^{2}\\big).\n",
    "  \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lipschitz-Stetigkeit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lipschitz-Stetigkeit von $f$, d.h.\n",
    "  \\begin{equation*} \n",
    "  \\|f(y) - f(x)\\| \\leq L_f \\|y - x\\| \\quad \\forall x,y\\in\\mathbb{R}^d\n",
    "  \\end{equation*}\n",
    "ist äquivalent zu\n",
    "  \\begin{equation*} \n",
    "  \\|g\\| \\leq L_f  \\quad \\forall g\\in \\partial f(x) \\quad \\forall x\\in\\mathbb{R}^d.\n",
    "  \\end{equation*}\n",
    "Damit erhalten wir aus der letzten Ungleichung im vorherigen Abschnitt\n",
    "  \\begin{equation*} \n",
    "  f_t - f_\\ast \n",
    "  \\leq \\frac{1}{2 \\gamma}\\big(\\gamma^{2}L_f^{2}+\\|x_{t}-x_{*}\\|_{2}^{2}-\\|x_{t+1}-x_{*}\\|_{2}^{2}\\big)\n",
    "  \\end{equation*}\n",
    "und somit\n",
    "  \\begin{align*} \n",
    "  \\sum_{t=0}^{T-1} (f_t - f_\\ast)\n",
    "  & \\leq \n",
    "  \\frac{\\gamma}{2}T L_f^2 \n",
    "  + \\frac{1}{2\\gamma} \n",
    "  \\big( \n",
    "  \\underbrace{\\|x_{0}-x_{*}\\|_{2}^{2}}_{e_0^2}\n",
    "  -\n",
    "  \\underbrace{\\|x_{T}-x_{*}\\|_{2}^{2}}_{\\geq 0}\n",
    "  \\big)\n",
    "  \\\\\n",
    "  & \\leq \\frac{\\gamma T L_f^2}{2} + \\frac{e_0^2}{2\\gamma},\n",
    "  \\end{align*}\n",
    "was identisch ist mit der Abschätzung bei Gradient-Descent.\n",
    "  \n",
    "Somit erhalten wir in diesem Fall auch die selbe Konvergenzaussage\n",
    "  wie bei Gradient-Descent.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Satz:** $f:\\mathbb{R}^d\\to \\mathbb{R}$, konvex, L-stetig mit Konstante $L_f$\n",
    "  und es existiere $x_\\ast = \\mathrm{argmin}_{x\\in\\mathbb{R}^d}f(x)$.\n",
    "Mit $\\gamma = \\frac{c}{T^\\omega}$, $\\omega\\in(0,1)$, gilt\n",
    "  \\begin{align*} \n",
    "  \\min_{t=0,\\ldots,T-1}(f_t - f_\\ast)\n",
    "  &\\leq \\frac{1}{T} \\sum_{t=0}^{T-1} (f_t - f_\\ast)\\\\\n",
    "  &= \\mathcal{O}\\Big(\\big(\\frac{1}{T}\\big)^{\\min(\\omega,1-\\omega)}\\Big)\n",
    "  \\quad \n",
    "  \\text{für}\n",
    "  \\quad\n",
    "  T\\to\\infty.\n",
    "  \\end{align*}\n",
    "Die optimale Ordnung ist $\\frac{1}{2}$ für $\\omega=\\frac{1}{2}$.\n",
    "Mit $e_0 = \\|x_0 - x_\\ast\\|$, $\\gamma = \\frac{e_0}{L_f\\sqrt{T}}$ gilt außerdem\n",
    "  \\begin{equation*} \n",
    "  \\min_{t=0,\\ldots,T-1}(f_t - f_\\ast)\n",
    "  \\leq \\frac{1}{T} \\sum_{t=0}^{T-1} (f_t - f_\\ast)\n",
    "  \\leq \\frac{L_f e_0}{\\sqrt{T}}.\n",
    "  \\end{equation*}  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $L$-Glattheit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bei differenzierbarem $f$ hatten wir unter zusätzlichen   Voraussetzungen ($L$-Glattheit, $\\mu$-Konvexität) höhere Konvergenzraten nachweisen können.\n",
    "\n",
    "Bei $L$-Glattheit stoßen wir hier auf ein Problem.\n",
    "Wie das folgende Lemma zeigt, sind $L$-glatte Funktionen mit existierenden Subgradienten automatisch differenzierbar.\n",
    "  \n",
    "  \n",
    "**Lemma:**\n",
    "$f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\to \\mathbb{R}$,\n",
    "  $\\mathrm{dom}(f)$ offen und in $x\\in \\mathrm{dom}(f)$\n",
    "  gelte $\\partial f(x)\\neq\\emptyset$.\n",
    "Gibt es ein $L\\ge 0$ so dass für $g_x \\in \\partial f(x)$\n",
    "  \\begin{equation*} \n",
    "  f(y) \\leq f(x) + g_x^T (y-x) + \\frac{L}{2}\\|y-x\\|_2^2\n",
    "  \\quad \\forall y\\in\\mathrm{dom}(f)\n",
    "  \\end{equation*}\n",
    "  gilt, dann ist $f$ differenzierbar in $x$ und $f'(x)=g_x$.\n",
    "  \n",
    "  \n",
    "**Beweis:**\n",
    "\n",
    "- wegen $g_x \\in \\partial f(x)$ gilt\n",
    "    \\begin{equation*} \n",
    "    f(y) \\geq f(x) + g_x^T(y-x) \\quad \\forall y\\in\\mathrm{dom}(f)\n",
    "    \\end{equation*}\n",
    "  und es folgt\n",
    "    \\begin{equation*} \n",
    "    0 \\leq f(y) - \\big(f(x) + g_x^T (y-x)\\big) \\leq \\frac{L}{2} \\|y-x\\|_2^2\n",
    "    \\end{equation*}\n",
    "    \n",
    "- also ist für $y \\to x$\n",
    "    \\begin{equation*} \n",
    "    \\big| f(y) - \\big(f(x) + g_x^T (y-x)\\big) \\big|= {\\scriptstyle \\mathcal{O}}(\\|y-x\\|)\n",
    "    \\end{equation*}\n",
    "  und somit $f$ in $x$ differenzierbar mit Ableitung $f'(x)=g_x$\n",
    "    \n",
    "$\\square$  \n",
    "  \n",
    "  \n",
    "Verlangen wir also $L$-Glattheit für subdifferenzierbare\n",
    "Funktionen (z.B. $f$ konvex), so landen wir wieder beim differenzierbarem Fall."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $\\mu$-Konvexität"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\mu$-Konvexität lässt sich einfach auf den subdifferenzierbare Funktionen verallgemeinern.\n",
    "\n",
    "\n",
    "**Definition:**\n",
    "$f:\\mathbb{R}^d \\supset \\mathrm{dom}(f) \\to \\mathbb{R}$\n",
    "  heißt $\\mu$-konvex, falls\n",
    "  \\begin{equation*} \n",
    "  f(y) \\geq f(x) + g^T (y-x) + \\frac{\\mu}{2}\\|y-x\\|_2^2\n",
    "  \\quad \\forall g \\in \\partial f(x)\n",
    "  \\quad \\forall x,y\\in\\mathrm{dom}(f).\n",
    "  \\end{equation*}\n",
    "  \n",
    "\n",
    "Wie im letzten Kapitel erklärt, müssen wir bei nicht differenzierbarem $f$ auf $L$-Glattheit verzichten, was einige Schwierigkeiten verursachen wird.\n",
    "\n",
    "Die Probleme die sich dabei ergeben werden wir am folgenden Beispiel näher untersuchen.\n",
    "\n",
    "\n",
    "**Beispiel:**\n",
    "\n",
    "- für die Funktion $f:\\mathbb{R}\\to\\mathbb{R}$\n",
    "  \\begin{equation*} \n",
    "  f(x) \n",
    "  = e^{|x|}\n",
    "  = \\begin{cases}\n",
    "    e^{-x} & x<0\\\\\n",
    "    e^{x} & 0 \\leq x\n",
    "    \\end{cases}\n",
    "  \\end{equation*}\n",
    "  erhalten wir als Subgradient\n",
    "  \\begin{equation*} \n",
    "  \\partial f(x) \n",
    "  = \\begin{cases}\n",
    "    \\mathrm{sign}(x)\\ e^{|x|} & x \\neq 0\\\\\n",
    "    [-1,1] & x = 0\n",
    "    \\end{cases}\n",
    "  \\end{equation*}\n",
    "  \n",
    "- $f$ ist $\\mu$-konvex mit $\\mu=1$ (Übung)\n",
    "  \n",
    "- $\\mu$-Konvexität liefert nur eine Schranke nach unten, d.h. $f$\n",
    "    kann sehr stark wachsen und somit kann $\\partial f$ sehr große \n",
    "    Werte annehmen\n",
    "  \n",
    "- ist dies der Fall, dann können bei Subgradient-Descent \n",
    "    \"Overshoots\" auftreten\n",
    "    \n",
    "- um dies zu kompensieren und Konvergenz zu sichern, muss\n",
    "    die Schrittweite $\\gamma$ sehr klein gewählt werden\n",
    "    \n",
    "- für \"brave\" Funktionen $f$ verursacht das aber unnötigen Aufwand\n",
    "  \n",
    "- als Konsequenz muss die Schrittweite entsprechend an $f$ angepasst \n",
    "    werden"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beim einfachen Gradient-Descent hat die $L$-Glattheit (als Beschränkung nach oben) dieses Problem beseitigt.\n",
    "Da  $L$-Glattheit hier nicht zur Verfügung steht, werden wir\n",
    "  unter der zusätzlichen Annahme \n",
    "  \\begin{equation*} \n",
    "  \\|g_t\\| \\leq B \\quad \\forall t\n",
    "  \\end{equation*}\n",
    "und $t$-abhängiger Schrittweite $\\gamma_t$\n",
    "  das folgende Konvergenz-Resultat für Subgradient-Descent\n",
    "  beweisen.\n",
    "  \n",
    "  \n",
    "**Satz:** $f$ sei $\\mu$-konvex und es existiere $x_\\ast$.\n",
    "Für\n",
    "  \\begin{equation*} \n",
    "  \\gamma_t = \\frac{2}{\\mu(t+1)}\n",
    "  \\end{equation*}\n",
    "erhalten wir für Subgradient-Descent\n",
    "  \\begin{equation*} \n",
    "  f\\Big(\n",
    "  \\underbrace{\\frac{2}{T(T+1)} \\sum_{t=1}^T t x_t}\n",
    "   _{\\text{Konvexkombination der }x_t}\n",
    "  \\Big) - f_\\ast\n",
    "  \\leq\n",
    "  \\frac{2 B^2}{\\mu(T+1)}\n",
    "  \\end{equation*}\n",
    "mit\n",
    "  \\begin{equation*} \n",
    "  B = \\max_{t=1,\\ldots,T}\\|g_t\\|_2.\n",
    "  \\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Beweis:**\n",
    "\n",
    "- aus den Vorüberlegungen wissen wir\n",
    "    \\begin{equation*} \n",
    "    g_{t}^T(x_{t}-x_{*}) \n",
    "    =\\frac{1}{2 \\gamma_t}\n",
    "    \\big(\n",
    "    \\gamma_t^{2}\\|g_{t}\\|_{2}^{2}\n",
    "    +\\|x_{t}- x_{*}\\|_{2}^{2}\n",
    "    -\\|x_{t+1}-x_{*}\\|_{2}^{2}\n",
    "    \\big)\n",
    "    \\quad \n",
    "    \\end{equation*}\n",
    "   \n",
    "- aus der $\\mu$-Konvexität von $f$ folgt mit $y=x_\\ast$, $x=x_t$\n",
    "    \\begin{equation*} \n",
    "    f_\\ast \n",
    "    \\geq \n",
    "    f_t + g_t^T (x_\\ast-x_t) + \\frac{\\mu}{2}\\|x_\\ast-x_t\\|_2^2\n",
    "    \\end{equation*}\n",
    "  also\n",
    "    \\begin{equation*} \n",
    "    f_t - f_\\ast  \n",
    "    \\leq \n",
    "    g_t^T (x_t-x_\\ast)\n",
    "    - \\frac{\\mu}{2}\\|x_t-x_\\ast\\|_2^2\n",
    "    \\end{equation*}\n",
    "  und somit\n",
    "    \\begin{align*}\n",
    "    f_t - f_\\ast\n",
    "    &\\leq\n",
    "     \\frac{1}{2 \\gamma_t}\n",
    "     \\big(\n",
    "     \\gamma_t^{2}\\|g_{t}\\|_{2}^{2}\n",
    "     +\\|x_{t}- x_{*}\\|_{2}^{2}\n",
    "     -\\|x_{t+1}-x_{*}\\|_{2}^{2}\n",
    "     \\big)\n",
    "     - \\frac{\\mu}{2}\\|x_t-x_\\ast\\|_2^2 \\\\\n",
    "    &\\leq\n",
    "     \\frac{B^2}{2}\\gamma_t\n",
    "     + \\frac{1}{2}\n",
    "       \\big(\\frac{1}{\\gamma_t} - \\mu\\big) \\|x_{t}- x_{*}\\|_{2}^{2}\n",
    "     - \\frac{1}{2 \\gamma_t} \\|x_{t+1}-x_{*}\\|_{2}^{2}\n",
    "    \\end{align*}\n",
    "   \n",
    "- multiplizieren wir mit $t$ und setzen wir wieder\n",
    "    $e_t = \\|x_{t}- x_{*}\\|_{2}$, so erhalten wir\n",
    "    \\begin{equation*} \n",
    "    t(f_t - f_\\ast)\n",
    "    \\leq\n",
    "    \\frac{t}{2} \n",
    "    \\Big(\n",
    "    B^2 \\gamma_t\n",
    "    + \\underbrace{\\big(\\frac{1}{\\gamma_t} - \\mu\\big)}_{\\alpha_t} \\ e_t^2\n",
    "    - \\underbrace{\\frac{1}{\\gamma_t}}_{\\beta_t} \\ e_{t+1}^2\n",
    "    \\Big)\n",
    "    \\end{equation*}\n",
    "    \n",
    "- Summation über $t$ liefert\n",
    "    \\begin{align*}\n",
    "    \\sum_{t=1}^T t(f_t - f_\\ast)\n",
    "    & = \n",
    "    \\sum_{t=0}^T t(f_t - f_\\ast)\\\\\n",
    "    & \\leq\n",
    "    \\sum_{t=0}^T\n",
    "    \\frac{t}{2} \n",
    "    \\Big(B^2 \\gamma_t + \\alpha_t e_t^2 - \\beta_t e_{t+1}^2\\Big)\\\\\n",
    "    & = \n",
    "    \\frac{B^2}{2} \\sum_{t=1}^T t \\gamma_t\n",
    "    + \\frac{1}{2}\n",
    "    \\Big(\n",
    "    \\sum_{t=0}^T t \\alpha_t e_t^2  - \\sum_{t=0}^T t \\beta_t e_{t+1}^2\n",
    "    \\Big)\\\\\n",
    "    & = \n",
    "    \\frac{B^2}{2} \\sum_{t=1}^T t \\gamma_t\n",
    "    + \\frac{1}{2}\n",
    "    \\Big(\n",
    "      \\sum_{t=0}^{T-1} (t+1) \\alpha_{t+1} e_{t+1}^2  \n",
    "    - \\sum_{t=0}^T t \\beta_t e_{t+1}^2\n",
    "    \\Big)\\\\\n",
    "    & = \n",
    "    \\frac{B^2}{2} \\sum_{t=1}^T t \\gamma_t\n",
    "    + \\frac{1}{2}\n",
    "    \\Big(\n",
    "      \\sum_{t=0}^{T-1} \\big((t+1) \\alpha_{t+1} - t \\beta_t\\big) e_{t+1}^2  \n",
    "    - \\beta_T e_{T+1}^2   \n",
    "    \\Big)\\\\\n",
    "    & \\leq \n",
    "    \\frac{B^2}{2} \\sum_{t=1}^T t \\gamma_t\n",
    "    + \\frac{1}{2}\n",
    "    \\Big(\n",
    "      \\sum_{t=0}^{T-1} \\big((t+1) \\alpha_{t+1} - t \\beta_t\\big) e_{t+1}^2  \n",
    "    \\Big)\n",
    "    \\end{align*}    \n",
    "    \n",
    "- $\\alpha_t$ und $\\beta_t$ hängen nur von $\\gamma_t$ und $\\mu$ ab\n",
    "\n",
    "- kann man $\\gamma_t$ so wählen, dass\n",
    "  \\begin{equation*} \n",
    "  (t+1) \\alpha_{t+1} - t \\beta_t \\leq 0\n",
    "  \\quad \\forall t \\geq 0\n",
    "  \\end{equation*}\n",
    "  gilt, dann kann der zweite Summand auf der rechten Seite mit $0$\n",
    "  nach oben abgeschätzt werden\n",
    "  \n",
    "- für\n",
    "  \\begin{equation*} \n",
    "  \\gamma_t = \\frac{2}{\\mu(t+1)}\n",
    "  \\end{equation*}\n",
    "  ist\n",
    "  \\begin{align*}\n",
    "  (t+1) \\alpha_{t+1} - t \\beta_t \n",
    "  &= (t+1) \\big(\\frac{1}{\\gamma_{t+1}} - \\mu\\big) - t \\frac{1}\n",
    "     {\\gamma_t}\\\\\n",
    "  &= (t+1) \\big(\\frac{\\mu(t+2)}{2} - \\mu\\big) - t \\frac{\\mu(t+1)}{2}\\\\\n",
    "  &= \\frac{\\mu}{2} (t+1)t - t\\frac{\\mu}{2} (t+1)\\\\\n",
    "  &= 0\n",
    "  \\end{align*}\n",
    "  und damit\n",
    "  \\begin{equation*} \n",
    "  \\sum_{t=1}^T t(f_t - f_\\ast) \n",
    "  \\leq \n",
    "  \\frac{B^2}{2} \\sum_{t=1}^T t \\gamma_t\n",
    "  \\end{equation*}\n",
    "  \n",
    "- wegen\n",
    "  \\begin{equation*} \n",
    "  \\frac{2}{T(T+1)}\\sum_{t=1}^T t = 1,\n",
    "  \\end{equation*}\n",
    "  der Konvexität von $f$ und der Jensen-Ungleichung\n",
    "  erhalten wir \n",
    "  \\begin{align*}\n",
    "  f\\Big(\\frac{2}{T(T+1)}\\sum_{t=1}^T t x_t \\Big) - f_\\ast\n",
    "  &\\leq \\Big(\\frac{2}{T(T+1)}\\sum_{t=1}^T t f_t \\Big) - f_\\ast\\\\\n",
    "  &= \\frac{2}{T(T+1)}\\sum_{t=1}^T t (f_t - f_\\ast)\\\\\n",
    "  &\\leq \\frac{B^2}{T(T+1)} \\sum_{t=1}^T t \\gamma_t\n",
    "  \\end{align*} \n",
    "  \n",
    "- mit\n",
    "  \\begin{equation*} \n",
    "  \\gamma_t = \\frac{2}{\\mu(t+1)}\n",
    "  \\end{equation*}\n",
    "  folgt\n",
    "  \\begin{equation*} \n",
    "  \\sum_{t=1}^T t \\gamma_t\n",
    "  = \\frac{2}{\\mu} \\sum_{t=1}^T \\frac{t}{t+1} \\leq \\frac{2}{\\mu} T\n",
    "  \\end{equation*}\n",
    "  und somit schließlich\n",
    "  \\begin{equation*} \n",
    "  f\\Big(\\frac{2}{T(T+1)}\\sum_{t=1}^T t x_t \\Big) - f_\\ast\n",
    "  \\leq \\frac{2B^2}{\\mu(T+1)}\n",
    "  \\end{equation*}\n",
    "  \n",
    "$\\square$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bemerkung:**\n",
    "\n",
    "- in der oberen Schranke steckt $x_0$ nicht explizit drin, geht aber\n",
    "    implizit über $B$ ein ($\\|g_t\\|_2 \\leq B$ $\\forall t$)\n",
    "   \n",
    "- für $f$ differenzierbar, $\\mu$-konvex und $L$-glatt hatten wir bei\n",
    "    Gradient-Descent die Komplexität $\\mathcal{O}\\big(\\log(\\frac{1}{\\varepsilon})\\big)$\n",
    "   \n",
    "- für $f$ $\\mu$-konvex, $\\|g_t\\|_2 \\leq B$ $\\forall t$ bekommen wir\n",
    "    bei Subgradient-Descent nur die Komplexität $\\mathcal{O}\\big(\\frac{1}{\\varepsilon}\\big)$, \n",
    "    d.h. aus fehlender Glattheit von $f$ kann wieder langsamere Konvergenz folgen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zusammenfassung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ist $f$ konvex und nicht differenzierbar, dann benutzt man bei Gradient-Descent statt des \n",
    "  (eventuell nicht  existierenden) Gradienten einen Subgradienten.\n",
    "  \n",
    "Für das *nicht restringierte Optimierungsproblem* haben wir folgendes \n",
    "  Konvergenzverhalten nachgewiesen:\n",
    "\n",
    "  - $f$ konvex und Lipschitz-stetig, $\\gamma = \\frac{c}{\\sqrt{T}}$, $c>0$:\n",
    "    \\begin{equation*} \n",
    "    \\min_{t=0,\\ldots,T-1}(f_t - f_\\ast)\n",
    "    \\leq \\frac{L_f e_0}{\\sqrt{T}}\n",
    "    \\end{equation*}  \n",
    "    also\n",
    "    \\begin{equation*} \n",
    "    \\min_{t=0,\\ldots,T-1}(f_t - f_\\ast) \\leq \\varepsilon\n",
    "    \\quad \\Rightarrow\\quad\n",
    "    T = \\mathcal{O}\\big(\\frac{1}{\\varepsilon^2}\\big)\n",
    "    \\end{equation*}\n",
    "    \n",
    "  - $f$ $\\mu$-konvex mit $\\mu>0$ und $\\|g_t\\|\\leq B$,\n",
    "    $\\gamma_t = \\frac{2}{\\mu(t+1)}$\n",
    "    \\begin{equation*} \n",
    "    f\\Big(\\frac{2}{T(T+1)} \\sum_{t=1}^T t x_t\\Big) - f_\\ast\n",
    "    \\leq\n",
    "    \\frac{2 B^2}{\\mu(T+1)},\n",
    "    \\end{equation*}\n",
    "    also\n",
    "    \\begin{equation*} \n",
    "    f\\Big(\\frac{2}{T(T+1)} \\sum_{t=1}^T t x_t\\Big) - f_\\ast\n",
    "    \\leq \\varepsilon\n",
    "    \\quad \\Rightarrow\\quad\n",
    "    T = \\mathcal{O}\\Big( \\frac{1}{\\varepsilon} \\Big)\n",
    "    \\end{equation*}\n",
    "    \n",
    "Im ersten Fall benötigen wir für Genauigkeit $\\varepsilon$\n",
    "  den selben asymptotischen Aufwand wie bei \n",
    "  differenzierbarem $f$.\n",
    "  \n",
    "Im zweiten Fall steigt der\n",
    "  Aufwand von $\\mathcal{O}\\Big( \\log\\big(\\frac{1}{\\varepsilon}\\big) \\Big)$\n",
    "  auf $\\mathcal{O}\\Big( \\frac{1}{\\varepsilon} \\Big)$, d.h. durch die\n",
    "  reduzierten Glattheitsanforderungen an $f$ reduziert sich hier\n",
    "  die Konvergenzgeschwindigkeit."
   ]
  }
 ],
 "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
}