01-gradient_descent.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gradient Descent\n",
    "\n",
    "In this class we will code one of the oldest (and most efficient!) optimization methods (Cauchy, Augustin (1847). _Méthode générale pour la résolution des systèmes d'équations simultanées_).\n",
    "\n",
    "## The intuition\n",
    "\n",
    "go in the direction of steepest descent\n",
    "\n",
    "<img style=\"margin-left:0\" width=\"300px\" src=\"https://upload.wikimedia.org/wikipedia/commons/f/ff/Gradient_descent.svg\" />\n",
    "\n",
    "## More formally\n",
    "\n",
    "We want to minimize a function $f: \\mathbb{R}^p \\to \\mathbb{R}$ which is differentiable. Then we construct a sequence $x^1, x^2 , \\ldots$ by the recusive formula\n",
    "\n",
    "$$x^{k+1} = x^k - \\gamma \\nabla f(x^k) \\quad$$\n",
    "\n",
    "where $\\gamma$ is the step-size. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step size\n",
    "\n",
    "* How to choose the step size?\n",
    "\n",
    "The theory says that the optimum is given by $\\frac{1}{L}$, where $L$ is the Lipschitz constant of the gradient of $f$.\n",
    "\n",
    "## Gradient descent for least squares\n",
    "\n",
    "We will now code a gradient descent scheme. The first thing is to define what is the loss that we want to optimize. We will start with a least squares loss:\n",
    "\n",
    "$$f(x) = \\frac{1}{2}\\|b - Ax\\|^2$$\n",
    "for some given matrices $A$ and vector $b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.random.seed(0)\n",
    "\n",
    "n_samples, n_features = 10, 5\n",
    "A = np.random.randn(n_samples, n_features)\n",
    "w = np.random.randn(n_features)\n",
    "b = A.dot(w) + np.random.randn(n_samples)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.76405235,  0.40015721,  0.97873798,  2.2408932 ,  1.86755799],\n",
       "       [-0.97727788,  0.95008842, -0.15135721, -0.10321885,  0.4105985 ],\n",
       "       [ 0.14404357,  1.45427351,  0.76103773,  0.12167502,  0.44386323],\n",
       "       [ 0.33367433,  1.49407907, -0.20515826,  0.3130677 , -0.85409574],\n",
       "       [-2.55298982,  0.6536186 ,  0.8644362 , -0.74216502,  2.26975462],\n",
       "       [-1.45436567,  0.04575852, -0.18718385,  1.53277921,  1.46935877],\n",
       "       [ 0.15494743,  0.37816252, -0.88778575, -1.98079647, -0.34791215],\n",
       "       [ 0.15634897,  1.23029068,  1.20237985, -0.38732682, -0.30230275],\n",
       "       [-1.04855297, -1.42001794, -1.70627019,  1.9507754 , -0.50965218],\n",
       "       [-0.4380743 , -1.25279536,  0.77749036, -1.61389785, -0.21274028]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10,)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.42833187,  0.06651722,  0.3024719 , -0.63432209, -0.36274117,\n",
       "       -0.67246045, -0.35955316, -0.81314628, -1.7262826 ,  0.17742614])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b - A.dot(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "def func(x):\n",
    "    return 0.5 * np.sum((b - np.dot(A, x)) ** 2)\n",
    "\n",
    "def grad(x):\n",
    "    return - A.T.dot(b - np.dot(A, x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "403.68145991617422"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "func(np.array([0, 1, 2, 3, 4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Implemented algorithm:\n",
    "\n",
    "max_iter = 100\n",
    "# Lipschitz constant\n",
    "L = np.linalg.norm(A.T.dot(A))\n",
    "step_size = 1. / L\n",
    "# initial guess\n",
    "xk = np.zeros(n_features)\n",
    "for i in range(max_iter):\n",
    "    xk = xk - step_size * grad(xk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize convergence\n",
    "\n",
    "Once we started the algorithm. How to know if its working properly?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "# imports matplotlib, a plotting library\n",
    "%pylab inline\n",
    "\n",
    "cost_history = []\n",
    "grad_history = []\n",
    "xk = np.zeros(n_features)\n",
    "for i in range(max_iter):\n",
    "    xk = xk - step_size * grad(xk)\n",
    "    cost_history.append(func(xk)) # .. insert this line to keep track of iterates ..\n",
    "    grad_history.append(np.linalg.norm(grad(xk)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEACAYAAAC9Gb03AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAG6JJREFUeJzt3X2UXXV97/H3J0wSeUx4cngIYaSKGHwYoUKQ2kzpBQXu\nDbeiQNXLjatL8CEXFz6sq10I2q4+rK7eCkYQqMoUq0BBpbFiUYQBxRqQ5EggoKEFicFEA8ZWUEjC\n9/6xz/A7c3Jm5kxmz97nnP15rbXXnN8+v9n7d76Z/GbPZ++zjyICMzPrXbPKHoCZmc0sT/RmZj3O\nE72ZWY/zRG9m1uM80ZuZ9ThP9GZmPa6tiV7SY5J+KGmNpHvG6fMpSesl1SQN5jtMMzPbVX1t9nse\nGIqIX7Z6UtKpwO9ExMskHQ9cCSzOaYxmZjYN7UY3mqTvGcC1ABGxCpgnqX+aYzMzsxy0O9EH8C1J\n90p6V4vnDwU2NLQ31teZmVnJ2o1uToyIn0k6kGzCfygivjuTAzMzs3y0NdFHxM/qX38h6avAcUDj\nRL8ROKyhvaC+bgxJvrGOmdkuiAjt6vdOGt1I2kPSXvXHewKnAA80dVsJnFvvsxjYGhGbxxkuq1cH\nEdVeLrnkktLH0CmLa+FauBYTL9PVzhF9P/DV+tF4H/DFiPimpPOBiIirI+IWSadJegR4GnjnRBvc\ntm3a4+56jz32WNlD6BiuReJaJK5Ffiad6CPiUWCn6+Ij4qqm9vJ2d/rcc+32NDOz6SrlnbE+oodl\ny5aVPYSO4VokrkXiWuRHeeQ/be9MCghuvRVOOaWw3ZqZdTVJxEyejJ0Jjm5gZGSk7CF0DNcicS0S\n1yI/jm7MzHpcKdHNDTfAWWcVtlszs67m6MbMzCbk6KYkzh8T1yJxLRLXIj+e6M3MelwpGf2KFbC8\n7bdXmZlVW1dm9D6iNzMrjif6kjh/TFyLxLVIXIv8+KobM7MeV0pGf/HF8IlPFLZbM7Ou5ozezMwm\n5OimJM4fE9cicS0S1yI/PqI3M+txpWT073kPXHFFYbs1M+tqXZnRO7oxMyuOo5uSOH9MXIvEtUhc\ni/y0PdFLmiVptaSVLZ5bImlr/fnVki6aaFue6M3MitN2Ri/pQuBYYJ+IWNr03BLgg83rW2wjIDjz\nTLjppl0dsplZtRSS0UtaAJwGfHaibu3u1Ef0ZmbFaTe6+STwYWCiw/8TJNUkfV3Sook25one+WMj\n1yJxLRLXIj+TTvSSTgc2R0SN7Ki91ZH7fcDCiBgEPg3cPNE2fdWNmVlx+trocyKwVNJpwO7A3pKu\njYhzRztExK8bHn9D0hWS9ouIp3be3DLWrx/g4x+H+fPnMzg4yNDQEJB+g1ehPTQ01FHjcbtz2qM6\nZTxltUfXdcp4imyPjIwwPDwMwMDAANM1pTdMjXfSVVJ/RGyuPz4O+KeI2Gl0oydjTzgBvve96Q3c\nzKwqSnvDlKTzJZ1Xb75F0gOS1gCXAmdP9L2Obpw/NnItEtcicS3y005084KIuBO4s/74qob1lwOX\nt7sdn4w1MytOKfe6ecUrYN26wnZrZtbVfK8bMzObkO91UxLnj4lrkbgWiWuRH0/0ZmY9rpSMfv/9\nYcuWwnZrZtbVujKj9xG9mVlxfDK2JM4fE9cicS0S1yI/PqI3M+txpWT0ADt2wKxSfs2YmXWXrszo\nwUf1ZmZF8URfEuePiWuRuBaJa5EfT/RmZj2utIx+0ybo7y9s12ZmXcsZvZmZTcgTfUmcPyauReJa\nJK5Ffkqb6P2mKTOzYpSW0a9dC698ZWG7NjPrWs7ozcxsQo5uSuL8MXEtEtcicS3y0/ZEL2mWpNWS\nVo7z/KckrZdUkzQ42fZ8RG9mVoy2M3pJFwLHAvtExNKm504FlkfE6ZKOBy6LiMUttvFCRn/77fAH\nfzDd4ZuZ9b5CMnpJC4DTgM+O0+UM4FqAiFgFzJM04duhqh7dmJkVpd3o5pPAhxk9HN/ZocCGhvbG\n+rpxVT26cf6YuBaJa5G4Fvnpm6yDpNOBzRFRkzQE7PKfD5llwABf+AI88sh8BgcHGRoaAtI/rNvV\nao/qlPGU2a7Vah01njLbtVqto8ZTZHtkZITh4WEABgYGmK5JM3pJfwm8A9gO7A7sDXwlIs5t6HMl\ncEdE3FBvPwwsiYjNTdt6IaO//no4++xpj9/MrOfNeEYfEX8aEQsj4gjgHOD2xkm+biVwbn1Ai4Gt\nzZN8s6pHN2ZmRdnl6+glnS/pPICIuAV4VNIjwFXAeyf7/qpP9M2xRZW5FolrkbgW+Zk0o28UEXcC\nd9YfX9X03PKpbMtX3ZiZFaO0e92sWAHLp/SrwcysmnyvGzMzm5DvdVMS54+Ja5G4FolrkR8f0ZuZ\n9bjSMvqLL4ZPfKKwXZuZda2uzeirHt2YmRXF0U1JnD8mrkXiWiSuRX480ZuZ9bjSMvp3vxs+85nC\ndm1m1rW6NqP3Eb2ZWTE80ZfE+WPiWiSuReJa5MdX3ZiZ9bjSMvozz4Sbbips12ZmXcsZvZmZTcjR\nTUmcPyauReJaJK5FfnxEb2bW40rL6N/wBrjrrsJ2bWbWtZzRm5nZhDzRl8T5Y+JaJK5F4lrkZ9KJ\nXtJcSaskrZG0VtIlLfoskbRV0ur6ctFk2636yVgzs6K0ldFL2iMinpG0G3A3cEFE3NPw/BLggxGx\ndJLtvJDRH3UUPPTQtMZuZlYJhWT0EfFM/eFcoI/R2bppLFPZcdWjGzOzorQ10UuaJWkNsAn4VkTc\n26LbCZJqkr4uadFk26x6dOP8MXEtEtcicS3y09dOp4h4HnitpH2AmyUtioh1DV3uAxbW451TgZuB\nI1tvbRkwwFNPwaWXzmdwcJChoSEg/cO6Xa32qE4ZT5ntWq3WUeMps12r1TpqPEW2R0ZGGB4eBmBg\nYIDpmvJ19JI+BjwdEX83QZ9HgWMj4qmm9S9k9PvvD1u2TH3AZmZVM+MZvaQDJM2rP94dOBl4uKlP\nf8Pj48h+gYyZ5JtVPboxMytKOxn9wcAdkmrAKuDWiLhF0vmSzqv3eYukB+o5/qXA2ZNttOonY5tj\niypzLRLXInEt8jNpRh8Ra4FjWqy/quHx5cDlU9lx1Sd6M7OilHavG4AdO2BWae/NNTPrDl17rxvw\nUb2ZWRE80ZfE+WPiWiSuReJa5KfUid5X3piZzbxSM/pNm6C/f4JvMDMzZ/RmZjYxRzclcf6YuBaJ\na5G4FvnxEb2ZWY8rNaNfuxZe+crCdm9m1pW6OqOvcnRjZlYURzclcf6YuBaJa5G4FvnxRG9m1uNK\nzei//W046aTCdm9m1pW6OqP3Eb2Z2czzRF8S54+Ja5G4FolrkR9fdWNm1uNKzeivvx7OnvSzqMzM\nqs0ZvZmZTcjRTUmcPyauReJaJK5Ffiad6CXNlbRK0hpJayVdMk6/T0laL6kmabCdnfuI3sxs5rWV\n0UvaIyKekbQbcDdwQUTc0/D8qcDyiDhd0vHAZRGxuMV2xmT0K1bA8uV5vAwzs95VSEYfEc/UH84F\n+micrTNnANfW+64C5kma9CNFqhzdmJkVpa2JXtIsSWuATcC3IuLepi6HAhsa2hvr6yZU5ejG+WPi\nWiSuReJa5KevnU4R8TzwWkn7ADdLWhQR63Ztl8uAAQDuvHM+xx8/yNDQEJD+Yd2uVntUp4ynzHat\nVuuo8ZTZrtVqHTWeItsjIyMMDw8DMDAwwHRN+Tp6SR8Dno6Iv2tYdyVwR0TcUG8/DCyJiM1N3zsm\no//Yx+DP/mwaozczq4AZz+glHSBpXv3x7sDJwMNN3VYC59b7LAa2Nk/yrVQ5ujEzK0o7Gf3BwB2S\nasAq4NaIuEXS+ZLOA4iIW4BHJT0CXAW8t52dV/lkbHNsUWWuReJaJK5FfibN6CNiLXBMi/VXNbWn\nfKGkj+jNzGZeqfe6efe74TOfKWz3ZmZdqavvdVPl6MbMrCi+qVlJnD8mrkXiWiSuRX480ZuZ9bhS\nM/o3vxm+/OXCdm9m1pW6OqP3Eb2Z2czzRF8S54+Ja5G4FolrkR9fdWNm1uNKzejf8Aa4667Cdm9m\n1pWc0ZuZ2YQc3ZTE+WPiWiSuReJa5MdH9GZmPa7UjP6oo+ChhwrbvZlZV+rqjL7K0Y2ZWVEc3ZTE\n+WPiWiSuReJa5McTvZlZjys1o99vP3jyycJ2b2bWlbo6o/cRvZnZzPNEXxLnj4lrkbgWiWuRn0kn\nekkLJN0u6UFJayVd0KLPEklbJa2uLxe1s3NfdWNmNvMmzeglHQQcFBE1SXsB9wFnRMTDDX2WAB+M\niKWTbGtMRg+wYwfMKvXvCjOzzjbjGX1EbIqIWv3xr4GHgENbjaWdHc6ePbZd5fjGzKwIUzqWljQA\nDAKrWjx9gqSapK9LWjTeNpon+qrGN84fE9cicS0S1yI/fe12rMc2NwHvrx/ZN7oPWBgRz0g6FbgZ\nOLLVdrZtWwYM1FvzueOOQZYuHQLSP+zQkNtVao/qlPGU2a7Vah01njLbtVqto8ZTZHtkZITh4WEA\nBgYGmK62rqOX1Af8C/CNiLisjf6PAsdGxFNN6+PAA4Nf/CKt27QJ+vunOmwzs+oo6jr6zwPrxpvk\nJfU3PD6O7BfIU636OroxMytWO5dXngi8HThJ0pr65ZNvknS+pPPq3d4i6QFJa4BLgbPH296cOWPb\nVT0Z2xxbVJlrkbgWiWuRn0kz+oi4G9htkj6XA5e3s0NfdWNmVqzC73WzaFGwbl1ad//98KpXFTYE\nM7Ou03X3unF0Y2ZWrMInekc3GeePiWuRuBaJa5Gf0id6X3VjZjazCs/oh4aCxl/U3/42nHRSYUMw\nM+s6XZfRO7oxMytW6RN9VaMb54+Ja5G4FolrkR9fdWNm1uMKz+jf+tbgxhvTuuuug3POKWwIZmZd\nxxm9mZlNyNFNSZw/Jq5F4lokrkV+Sj+ir+rJWDOzopQ+0Vf1iH70wwbMtWjkWiSuRX4c3ZiZ9bjS\nj+irGt04f0xci8S1SFyL/JQ+0fuI3sxsZjm6KYnzx8S1SFyLxLXIT+lH9FWNbszMilL4RP+iF41t\nP/100SPoDM4fE9cicS0S1yI/7Xw4+AJJt0t6UNJaSReM0+9TktZLqkkaHG97Bx88tr1x41SHbGZm\nUzHpvW4kHQQcFBE1SXsB9wFnRMTDDX1OBZZHxOmSjgcui4jFLbYVd90V/P7vp3W/+7tw7735vBgz\ns1404/e6iYhNEVGrP/418BBwaFO3M4Br631WAfMk9bfa3mGHjW3/9KdTHrOZmU3BlDJ6SQPAILCq\n6alDgQ0N7Y3s/MsAgEMOATX8Xtq8uZonZJ0/Jq5F4lokrkV++trtWI9tbgLeXz+y3yXnnbeMPfYY\nqJ+EnU/EIE88McTAQPqHHb2syu1qtEd1ynjKbNdqtY4aT5ntWq3WUeMpsj0yMsLw8DAAAwMDTFdb\n96OX1Af8C/CNiLisxfNXAndExA319sPAkojY3NQvIoLXvQ5+8IO0/jvfgd/7vWm9DjOznlXU/eg/\nD6xrNcnXrQTOrQ9oMbC1eZJv1JzTb9jQup+ZmU1fO5dXngi8HThJ0hpJqyW9SdL5ks4DiIhbgEcl\nPQJcBbx3om0uWDC2XcUTss2xRZW5FolrkbgW+Zk0o4+Iu4Hd2ui3vN2d+ojezKw4hX9mbERw3XXw\ntrel9X/0R/CVrxQ2DDOzrtJ1nxkLPqI3MytSKRO9M3rnj41ci8S1SFyL/JQy0ftNU2ZmxSklo4fs\n5mabNqXnHn0UcnhfgJlZz+nKjB6c05uZFaW0ib7qOb3zx8S1SFyLxLXIj4/ozcx6nI/oSzJ6IyNz\nLRq5FolrkR8f0ZuZ9Tgf0ZfE+WPiWiSuReJa5MdH9GZmPa606+i3bYO5c6Fx988+C3PmFDYcM7Ou\n0LXX0c+eDQcdNHbdxo3ljMXMrJeVNtFDtXN654+Ja5G4FolrkZ9SJ/rmnL5KE72ZWVE66oi+Sidk\nfY1w4lokrkXiWuTHR/RmZj2unc+M/ZykzZLuH+f5JZK21j9LdrWki9rdeZWP6J0/Jq5F4lokrkV+\nJv3MWOAaYAVw7QR97oqIpVPduY/ozcxmXlvX0Us6HPhaRLy6xXNLgA9FxP9oYzvRuL/HH4fDD0/P\nz54NP/lJdq96MzPLdMp19CdIqkn6uqRF7X7TYYfBS1+a2tu2wRVX5DQiMzMD8pno7wMWRsQg8Gng\n5na/UYILLhi77sor4Te/yWFUHc75Y+JaJK5F4lrkp52MfkIR8euGx9+QdIWk/SLiqVb9ly1bxkD9\nMwPnz5/Py18+yLx5Q/zqVwAjbNkC//iPQ7zrXekfevQyK7d7sz2qU8ZTZrtWq3XUeMps12q1jhpP\nke2RkRGGh4cBXpgvp6PdjH6ALKN/VYvn+iNic/3xccA/RUTLkTVn9KM+/GH4279N7UWL4IEHxn6A\nuJlZVU03o590opf0JWAI2B/YDFwCzAEiIq6W9D7gPcA24DfAhRGxapxttZzoH38cjjgCduxI6/71\nX+GNb9yFV2Rm1mNm/GRsRLwtIg6JiLkRsTAiromIqyLi6vrzl0fEKyPitRHx+vEm+YksXAhvecvY\ndZ/85FS30l2aY4sqcy0S1yJxLfJT6jtjG1144dj2rbfCn//52NsYm5nZ1JV2P/pWXv96+Ld/G7vu\nox+Fv/gL5/VmVl2dch19LlasgD33HLvur/4KPvCBsfm9mZm1r6Mm+mOPhW9+E/bZZ+z6Sy+FE06A\ntWvLGddMcP6YuBaJa5G4FvnpqIkesvjmtttg333Hrr/3XjjmGLj44mq8ocrMLC8dldE3+uEP4ZRT\n4Oc/3/m5Qw6Biy6CP/kTf8asmfW+nsroG73mNVCrwZln7vzcE0/Ae98LRx0FV1/tI3wzs4l07EQP\n2V0sb7oJvvzlnT9IHODRR+H887Obo110UfYLoFs4f0xci8S1SFyL/HT0RD/qzW+GdevgQx+CF71o\n5+effDK7BHPhQli6FG6+ObsTppmZdXBGP54nnsgm9b//+4kn8wMOyGKft74VliyBvmnfvs3MrBwz\nfq+bPOUx0Y96/HH49KezjD678+X4DjwQTj8dTjsNTj4Z5s/PZQhmZoXo2ZOxk1m4EP7mb7KPH1yx\nAo4+evy+v/gFDA/DWWdlR/onnphl+rfdBs88U9iQx3D+mLgWiWuRuBb56dqJftRee8Hy5dmbqe65\nB97zHpg3b/z+O3bA976XxT8nn5z1fd3rsg9A+eIX4Uc/guefL278ZmYzrWujm4k8+2x2tH7jjdmJ\n2cminWZ77gmDg/DqV2d/KRx9dHaP/AMP9D13zKx4lc3o2/Xcc3D33XDLLdmybt2ub2v+fHjZy+DI\nI7P75w8MwEtekn3A+aGHwty5uQ3bzOwFnuin6Kc/hZGRtPz7v+e37f5+WLAge+fuwQdnS39/trz4\nxdlfBPvvn93e4TvfGXnhI8SqbmTEtRjlWiSuRTLdib5yFx0uWADveEe2QHaLhe9/P7s98g9+AGvW\nZNfl74rNm7Plvvsm7idl8VB/fzbp77tvdq5g3rzshm777AN775193WuvbNlzz7TssUf2dffds/cV\nzJ7tSMnMxle5I/rJRMCGDdmE/+CDafnxjzv3VguzZqVJf+7c9HXOnOzr6OPZs9PXVktf39hlt93S\n1/GWWbN2/tpqkSb/OtECk68ffdzOulGt+jU/btWear+pbGOq37+rfHDQ+fbaK0sGHN0U5Pnnszdr\n/fjH8Mgj2e0XRpcNG2DTJn8alpnl65xz4LrrCohuJH0O+O/A5oh49Th9PgWcCjwNLIuI2q4OqFPN\nmpXFPgsWwEkn7fz8c89lvwg2boSf/SwtP/95tmzenEVCW7aMXgU0QvaZ6+ZaNBrBtRg1gmuRj3Yy\n+muAFcC1rZ6UdCrwOxHxMknHA1cCi/MbYneYMye7CmdgYPK+27fDX/91jbPOGuKpp+CXv8wm///8\nz/T1v/4rLU8/nZZnnsmWp5/OoqTf/jbbXner4f/Qo1yLxLXIy6QTfUR8V9LhE3Q5g/ovgYhYJWme\npP6I2JzXIHtNXx9s376VI4/MZ3vbt2eT/rPPZhP/b3+bPX7uufS1cdm2beyyfXv6Orps25a9uWy0\nvWNHFl/t2LHzEjH28fPPp76N7ebHo8v69Vs54oj0fONzo3FY87rm9aOP21k3qlW/5set2lPtN5Vt\nbNmylQMOaP/7d1U3xIxPPrmV/fcvexTlanXX3l2Rx1U3hwIbGtob6+s80Rekry+7Smfvvcseya75\n+MezxVyLRq5Ffrr+Fgjd6rHHHit7CB3DtUhci8S1yE9bV93Uo5uvtToZK+lK4I6IuKHefhhY0iq6\nkdQFfzCamXWeIt4wpfrSykrgfcANkhYDW8fL56czUDMz2zXtXF75JbJT3/tLehy4BJgDRERcHRG3\nSDpN0iNkl1e+cyYHbGZmU1PoG6bMzKx4hZ2MlfQmSQ9L+rGk/1vUfjuBpAWSbpf0oKS1ki6or99X\n0jcl/UjSrZImuJN+75A0S9JqSSvr7arWYZ6kGyU9VP/ZOL7CtbhQ0gOS7pf0RUlzqlQLSZ+TtFnS\n/Q3rxn39kj4qaX39Z+eUybZfyEQvaRbwaeCNwNHAH0s6qoh9d4jtwAci4mjgBOB99df/EeC2iHg5\ncDvw0RLHWKT3A403jK5qHS4DbomIVwCvAR6mgrWQdAjwf4Bj6hd89AF/TLVqcQ3Z/Nio5euXtAg4\nC3gF2R0JrpAmvnNRUUf0xwHrI+InEbENuJ7sjVaVEBGbRm8LERG/Bh4CFpDV4B/q3f4B+J/ljLA4\nkhYApwGfbVhdxTrsA7whIq4BiIjtEfErKliLut2APSX1AbuTvR+nMrWIiO8Cv2xaPd7rXwpcX/+Z\neQxYTzbHjquoib75TVU/ra+rHEkDwCDwfeCFdxBHxCbgxeWNrDCfBD4MNJ4cqmIdXgJskXRNPca6\nWtIeVLAWEfEE8P+Ax8km+F9FxG1UsBZNXjzO6x/vTarj8humCiRpL+Am4P31I/vmM+E9fWZc0ulk\nN8erMf7lutDjdajrA44BLo+IY8iuWPsIFfuZAJA0n+zo9XDgELIj+7dTwVpMYpdff1ET/UZgYUN7\nQX1dZdT/JL0J+EJE/HN99WZJ/fXnDwJ+Xtb4CnIisFTSfwDXASdJ+gKwqWJ1gOyv2g0R8YN6+8tk\nE3/VfiYA/hvwHxHxVETsAL4KvJ5q1qLReK9/I3BYQ79J59OiJvp7gZdKOlzSHOAcsjdaVcnngXUR\ncVnDupXAsvrj/w38c/M39ZKI+NOIWBgRR5D9DNweEf8L+BoVqgNA/U/yDZJGb233h8CDVOxnou5x\nYLGkF9VPKv4h2cn6qtWi+Y2p473+lcA59SuTXgK8FLhnwi1HRCEL8CbgR2QnDj5S1H47YSE7kt1B\ndt/VNcDqej32A26r1+WbwPyyx1pgTZYAK+uPK1kHsitt7q3/XHwFmFfhWlxCdpHC/WQnHmdXqRbA\nl4AngGfJfvG9E9h3vNdPdgXOI/WanTLZ9v2GKTOzHueTsWZmPc4TvZlZj/NEb2bW4zzRm5n1OE/0\nZmY9zhO9mVmP80RvZtbjPNGbmfW4/w/cYSjvWMwuFwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x110d6de10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plot the cost\n",
    "plt.plot(cost_history, lw=4)\n",
    "plt.grid()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAECCAYAAAD3vwBsAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XuQVOW19/HvAkRUEieJHiOgDK+K+CpIvKAeNekKGiBE\n8XZUFLnF+GpZKtFKob6nalqr3qgniVGPl5gTLga5HI33RE9EsRMRcwAVgSiXKoOiKDExeoIRQWa9\nfzw97mGY7pnu6enevffvU0XJ3rPpeWY51av3Wnuvbe6OiIikT49aL0BERGpDCUBEJKWUAEREUkoJ\nQEQkpZQARERSSglARCSllABERFJKCUBEJKV6dfc3MLNxwFjgC8BMd1/Y3d9TREQ6ZtW6E9jMGoAf\nufv3qvINRUSkqJJLQGY2w8w2m9nKNvtHm9kaM1tnZtPb+af/CtxV7kJFRKSyyukBzAJGtd5hZj2A\nO/P7DwfGm9mQVl+/GXjS3Vd0Ya0iIlJBJScAd18M/K3N7hHAend/0923AwuAcQBmdgUwEjjHzC7p\n4npFRKRCKtUE7g9sbLX9NiEp4O7/Dvx7sX9sZhpJKiJSBne3cv9tbC4DdXf9caepqanma4jLH8VC\nsVAsiv/pqkolgHeAA1ttD8jv67RsNksul6vQcurXhg0bar2E2FAsIopFRLGAXC5HNpvt8uuUmwAs\n/6fFMuBgMxtoZr2B84HHS3nBbDZLJpMpczkiIumRyWRqkwDMbB6wBBhsZm+Z2RR33wFcATwN/BFY\n4O6vl/K6OgMIJk+eXOslxIZiEVEsIopF5c4AqnYjWNFFmHkc1iEiUk/MDE9CE1gCnQVFFIuIYhFR\nLConNglAJSARkc5RCUhEJOVUAhIRkbLEJgGoBBQoBhHFIqJYRBSLypWAuv15AJ1ViR9GRCQNMpkM\nmUyGG264oUuvox6AiEidSkwPQCUgEZHO0VVACZXL5TQSI0+xiCgWEcUikpgzABERqS6dAYiI1KnE\nnAGoByAi0jnqASSU6psRxSKiWEQUi0hizgBERKS6dAYgIlKndAYgIiJlUQKIGTXCI4pFRLGIKBaV\nE5sEoKuAREQ6R1cBiYiknHoAIiJSFiWAmFEZLKJYRBSLiGJROUoAIiIppR6AiEidUg9ARETKogQQ\nM6pvRhSLiGIRUSwqJzYJQPcBiIh0ju4DEBFJOfUARESkLEoAMaMyWESxiCgWEcWicpQARERSSj0A\nEZE6pR6AiIiURQkgZlTfjCgWEcUiolhUTrcnADMbZGa/MLMHih133XXdvRIREWmtaj0AM3vA3c8t\n8DU//njnxRershQRkUSoeg/AzGaY2WYzW9lm/2gzW2Nm68xseqmvu2IFbN9e6r8SEZFylVMCmgWM\nar3DzHoAd+b3Hw6MN7Mhbf5d0Sy1dSu89loZq0kY1TcjikVEsYgoFpVTcgJw98XA39rsHgGsd/c3\n3X07sAAYB2BmXzaze4DhHZ0ZLF9e6mpERKRcvSr0Ov2Bja223yYkBdz9A+Cyjl9iMvfc08jGjdDQ\n0MDw4cPJZDJAlPHTsJ3JZGK1Hm3HZ7tFXNZTq+2WfXFZTzW3c7kcs2fPBqCxsZGuKqsJbGYDgSfc\nfVh++2xglLtfkt+eAIxw9ys7+XoOzrHHwtKlJS9HRCSV4nIj2DvAga22B+T3lSDLK6/k2LatQiuq\nU20/7aWZYhFRLCKKReXGQZebAIydm7rLgIPNbKCZ9QbOBx4v7SWzfPZZhtWry1yRiEhKZDKZ2jwP\nwMzmARngK8BmoMndZ5nZGOA2QlKZ4e43l/CaDmEd994Ll1xS0pJERFKpqyWgkpvA7n5Bgf1PAU+V\nuxDIAhmWL88oAYiIFJHL5SpSCovRLKAsIQHUeh21pfpmRLGIKBYRxaJyJaBKXQZaAVkgw6pVGbZu\nhT59ar0eEZF4qtQZQGyeB9DSAwD47/+GESNquCARkToQl8tAKyrtZSARkWqIUQLIAjkg3QlA9c2I\nYhFRLCKKRe3vA+gGWcLVpelOACIiHanZfQDdoW0PoEcP+PvfYc89a7goEZGYS0wP4KCDor83N8PL\nL9duLSIiaRCbBLDHHllaegAAL7xQq5XUluqbEcUiolhEFIsE9gAuuyxLSw8A4Pnna7USEZF4S1wP\nYOVKZ9iwaF9DA/z1r6EfICIiu0pMD+Dww+FLX4q2P/wQTQYVEelGsUkAN96Y5dBDczvtW7y4Nmup\nJdU3I4pFRLGIKBYJ7AFks1nOOCOz0z71AUREdpW4HoC7s2QJnHhitL9/f9i4EazsCpeISHJ1tQcQ\nqwSwbRvsvTds3Rp97Y03YNCg2q1NRCSuEtMEBujdG447bud9aSsDqb4ZUSwiikVEsaicWCUAgJNP\n3nk7jY1gEZFqiE0JqKmpiUwmw6efZhg9OvrakCHw+uu1W5uISNy0PBDmhhtuSE4PAOB//ifcD9Dc\nHH39z3+Gffet0eJERGIqUT0AgC9+EYYP33lfmspAqm9GFIuIYhFRLCondgkAdu0DLFpUm3WIiCRZ\n7EpAAI8+CmeeGX19v/3g7behV4weYS8iUmuJKwEBjBoVSkEtNm+GZ5+t3XpERJIolglgjz3gnHN2\n3jdnTm3WUm2qb0YUi4hiEVEsKic2CSCbze70P3bChJ2//sgjsGVLddckIhJHlRoGF8seAITLQAcO\nDLX/FnPm7JoYRETSKpE9AAgPgrnwwp333X9/bdYiIpJEsU0AsOun/YUL4b33arOWalF9M6JYRBSL\niGJRObFOAEccAUceGW03N8OCBbVbj4hIksS2B9Dixz+GH/wg2h48GFasCFcKiYikWWJ7AC3Gj9/5\ngTDr1sH3v1+79YiIJEXsE0D//jB58s777r0XHnywJsvpdqpvRhSLiGIRUSwqJ/YJAOD22+Hgg3fe\nd/HF4WlhIiJSnm7vAZjZnsDdwKfA79x9XjvHFOwBtHj5ZTjhBNi2Ldp35JHhBjE9MlJE0qgeegBn\nAQ+6+/8BTi/3RY46Cn70o533vfoqDBsGM2ZADHrZIiJ1peQEYGYzzGyzma1ss3+0ma0xs3VmNr3V\nlwYAG/N/39GFtXLFFTBu3M77tmwJ5aDTToNVq7ry6vGg+mZEsYgoFhHFonLKOQOYBYxqvcPMegB3\n5vcfDow3syH5L28kJAGAsk9VwveBX/4Svv3tXb/2m9+Es4GzzoJXXunKdxERSYeyegBmNhB4wt2H\n5bePB5rcfUx++1rA3f2WfA/gTuATYLG7z2/n9TrsAbTmHq4EuuYa+Mc/2j/mm9+Eq66CsWOhZ88S\nf0ARkTrQ1R5ApR6x0p+ozAPwNjACwN3/AUzt6AUmT55MY2MjAA0NDQwfPpxMJgNEp3wt27/7XY4h\nQ+DVVzNMmgRLluTyr5LJ/zfHokWwaFGGQYNg1Kgco0fDuHHtv562ta1tbdfDdi6XY/bs2QCfv192\nibuX/AcYCKxstX028PNW2xOAO0p4PS/Xjh3ujz7qfvTR7uHcoP0/u+/uPnGi+4svujc3l/3tut1z\nzz1X6yXEhmIRUSwiikUk/95Z1vu4u1fsKqB3gANbbQ/I7+u0ts8D6KwePUJjeNkyePLJXZ8n3OLT\nT0P/4IQTwkPn77oLPvqo5G8nIlJzuVo+D8DMGgk9gKH57Z7AWmAk8C6wFBjv7q938vW8nHUU8sor\ncMcdMG/ezvcNtLXnnnDeefC978Hxx+88ckJEJO6qfh+Amc0DlgCDzewtM5vi7juAK4CngT8CCzr7\n5t+i3DOA9nztazBrFmzcCDffXPhGsX/8Ixz3z/8criC64w744IOKLEFEpNvU9Ayg0ip9BtBWczP8\n9rfws5/Br38dtgvZffdwKenFF0MmE0pM1ZTL5T5v/qSdYhFRLCKKRaQe7gSuuR49YMwYeOwxePNN\nyGZhwID2j/30U5g/H0aODKOnf/hD2LSpqssVEamK2JwBNDU1kclkqpbZd+yA//ov+I//CGcFO4rc\no9yzZ0ggF18cbkLbbbeqLFFEpF25XI5cLscNN9zQpTOA2CSAWq5j0yaYPTvMFOpowuh++8GkSTB1\nKhx6aFWWJyLSLpWAKqBfP7j+eli/Hp59Fs4/H3r3bv/YzZvh3/4NhgyBk04KTeQtWyq3lko1wpNA\nsYgoFhHFonJikwAqeRVQuXr0CCMk5s8PZwW33w5DhxY+/oUXwpnA/vuH8tCLL2oqqYh0P10FVCXu\nsHx5KA/Nmwd//3vx4w87LCSFiy4K5SIRke7S1RKQEkAJPv4YHnooJIPf/774sb16hUF0U6eGxnGv\nSk1dEhHJS0wPIA4loI7stRdMnAi/+114OP2114byT3s++yxcdjpuHBxwAEyfDmvWdPw94h6DalIs\nIopFRLGoXAkoVgmgnm7uOOQQuOkmeOsteOIJOOOMwp/y33svNI4POyw0jmfO7LiUJCJSSCaTUQ8g\nbv78Z5gzJ7zBv/Za8WP32gvOPTeUiE48UXOIRKR06gHEkDssXRoSwfz5HX/aP+SQkAgmTgyXpIqI\ndEZiegBJYgbHHReeWvbuu3DfffCNbxQ+fv16uO660Cs44YQcDz9cfIppWqjWG1EsIopF5cQmAdRD\nE7gcLY3jXC680V9/PfTv3/6xzc3whz/A2WeHY66+GlavrupyRaQO6D6AOrZjByxcGC4nfewx2L69\n+PHHHhtKROefDw0N1VmjiMSfegB17i9/gblzQzJYtar4sX36hLODqVNrM6paROJFPYA6t88+cNVV\n8Oqr4bGW48bl2Hvv9o/dujUki5Ej4aCD4MYbw3jrpEpiSbBcikVEsagcJYCYMINjjoFp00LjeO5c\nOOWUwsdv2ABNTeFpZ9/6FixYEBKEiEhnxaYEVO3nAdSLDRvCqOrZszv+tN/QABdcEEpERx2lewtE\nkkrPA0iZ5uZwJdHMmWEeUUef9ocNC4ngwgtDmUlEkkc9gIQpVN9sGVV9//2hRHTPPeHqoEJWrgzl\npH794Jxz4Mknw3yieqJab0SxiCgWlaMEUIcaGuDSS8PdxqtWhfsFCn3K3749nDGMHQsDB0YPvhER\nUQkoIbZtC882njUrfNpvbi5+/MknhxLROedA377VWaOIVJbuA5BdbNoUhtLNmNHxp/2+feG880Iy\nOOEENY5F6ol6AAlTifpmv37h+QNr18Lzz8OUKWEkRXu2bAmJ4sQTw7jqW24JPYY4UK03olhEFIvK\nUQJIMLPo+QPvvRf+e9JJhY9fuzY85OaAA+C00+CRRzSUTiTJYlMC0n0A1bNuXXRvQUef9vfdNzzf\neOpUOPzwaqxORDqi+wCkyz77DJ5+OpSAnnii46F0I0ZEQ+kKjasQkepRDyBhqlnf7NUrPLD+oYfg\nnXfgpz+FI44ofPzSpeHy069+FSZMgEWLOr7aqCtU640oFhHFonKUAAQIpZ5p08INZMuWwWWXFf6U\nn7ahdCJJpRKQFPTJJ6ERPHMmPPts8WPNwvC6qVPhjDPC6GoR6V66D0CqopyhdN/9Lnzta7q3QKS7\nqAeQMHGtbzY2QjYLb7wBzzwD48fD7ru3f+yHH8Ldd8PRR4cEcPvt4cE3pYprLGpBsYgoFpWjBCAl\n6dEj1P7nzQuXkN59d/GhdK++Gg2l+5d/qc+hdCJJ1a0lIDMbBPxf4Ivufm6R41QCqnOrVoU5RHPm\ndPxpv18/mDQp3KF8yCHVWZ9IEtVFD8DMHlACSAcNpROpnqr0AMxshpltNrOVbfaPNrM1ZrbOzKaX\nuwiJ1Ht9s3dvOOuscGPZxo1w000weHDh41tmFe2/P1x8MSxZAi2fBeo9FpWkWEQUi8rpbA9gFjCq\n9Q4z6wHcmd9/ODDezIbkv3aRmd1qZvu3HF6h9Uod6dcvzBZaswYWLw6f9EsZSvfXv1Z3vSJp0+kS\nkJkNBJ5w92H57eOBJncfk9++FnB3v6XVv/ky8P+AU4BftP5am9dWCSgltmyBBx8M9xYsXlz82J49\nYcyYkDjGjg1nFyISqVoPoJ0EcDYwyt0vyW9PAEa4+5UlL0IJIJU0lE6ka7qaAHpVcjFdMXnyZBob\nGwFoaGhg+PDhn08Gban5pWG7dX0zDuvp7u0f/hBGjsyxdCm89FKGxx+H7dujGEAGyPH++3DrrRlu\nvRWGDMkxZgw0NWXYe+94/Tzdtb1ixQqmTZsWm/XUcvu2225L9fvD7NmzAT5/v+yKrpaAsu4+Or+9\nSwmo04vQGcDncrnc5//j0+j998OcoRkzYPXqHCEBtK9Pn3D10JQpkMmEexSSKu2/F60pFpFqloAa\nCQlgaH67J7AWGAm8CywFxrv76yUvQs8DkDbc4aWXQq9g3jz46KPixzc2hkQwaRIMHFiVJYrUTK6a\nzwMws3mEj2JfATYTmr+zzGwMcBvhaqIZ7n5zWYvQGYAU0TKUbtasMIaiGLNwp/LUqXDmmRpKJ8lW\nlfsA3P0Cd+/n7ru7+4HuPiu//yl3P9TdDyn3zb9FNpv9vNaVZopBpCUWe+wRhsstXAh/+lOYSVTo\nU757SBIXXBDuLbj8cnj55ejegnql34uIYhFikM1mu/w6samaZrNZlX+kQ42N0NRU+lC64cPLH0on\nEjeZTKYiCSA246DVA5By/e1vsGBBaBy/9FLxY3fbDcaNC/2Cb30rPBVNpN5UtQfQ3dQDkErRUDpJ\nEz0PIGFU34yUE4uhQ+HWW8Mzjh9+GL7zncKXh27aFM0q+vrXww1pW7Z0acndRr8XEcWicmKTANQE\nlkrq3TtcBVTuULoXXqj/xrEkV6WawCoBSWq4h2mjM2bAAw/Axx8XP37w4HA56cSJITGIxE1dPA+g\nw0UoAUiVtQylmzEjfNovRkPpJK7UA0gYlcEi3RmLvn1DyWfxYli7NoytLvQpf8eO8JCbs86CAQPg\nmmtg9epuW1q79HsRUSwqJzYJQD0AqZXBg0OP4K23whv92WeHy0XbE4bShWbzccfBvfd2PKZCpNLU\nAxDpRu+/D/ffH2YRdfRpv0+fkDSmTk3+UDqJF/UARLpRy1C6GTNg/nwNpZN4UQ8gYVQGi8QhFmZw\nzDFwzz3hoTVz58IppxQ+fsOGMKpi0KBwp/H8+bB1a9fXEYdYxIViUTmxSQDqAUjclTqUbuHCnYfS\nvfSS7i2QylAPQCQGmpth0aIwfuKhh+DTT4sfP2xY6BVceCHss0911ijJpR6ASEy0DKWbOROWLy9+\n7G67wemnh2SgoXRSLvUAEkZlsEi9xeJLX4LLLoNly2DlSvj+9wt/yt++PZwxjB0bykjXXw/r1xd+\n7XqLRXdSLCpHCUCkGyR1KJ0ki0pAIlWyaVMYUz1zJqxbV/zYvn3hvPNCieiEE8LVSCJtJaYHoAfC\nSFqUOpTu0EPDvQUaSict9ECYhMrlckqCeWmIReeH0uXo2TOjoXSk4/eis9QEFqljbYfSXXddeFJZ\ne+IwlE6SRWcAIjHz2Wfw9NOhV/D44+GKoWKOPTacFYwfD3vvXZ01SjwkpgcQh3WIxI2G0kkxKgEl\njK5xjigWsO++4X6CO+7IsWwZXHpp4U/5W7eGWUUjR8JBB8ENN8Cbb1Z3vdWg34vKUQIQqQNth9LN\nmxfe6AtdHrphQ5hVNGgQnHpq5YbSSbKoBCRSxzZsgPvuC7OIOvq039AQhtNNnQpHHaV7C5IgMT0A\n3QcgUr7mZnjuudAr0FC65NN9AAmla5wjikWklFgkfSidfi8iagKLyE7aDqWbNq1yQ+kkWXQGIJIC\n27aFm8hmzoSnngolo2JOPjmcFZxzTrhZTeIpMT2AOKxDJA00lC45VAJKGF3jHFEsIpWMRb9+MH06\nrFkDzz8f3tz32qv9Y7dsCXOKTjwRDjsMbrklXIZaS/q9qBwlAJGUMoOTTgpv8O+9F/570kmFj1+7\nFq69Fg44AE47LTznYNu26q1XKk8lIBHZybp14aE0990XykXF7LsvTJgQziKOOKIqy5NWYt0DMLNx\nwFjgC8BMd19Y4DglAJGYKXUo3YgRIRGcf76G0lVLrHsA7v6Yu18CXAac253fKylU34woFpFaxKJX\nL/j2t+FXvwqPtvzpT8OjLgtZujTMKvrqV8NZwaJFHV9tVA79XlROpxKAmc0ws81mtrLN/tFmtsbM\n1pnZ9CIv8a/AXV1ZqIjUzr77hvsJXn01vNFfdlnnh9LdeGMyh9IlQadKQGZ2ErAF+KW7D8vv6wGs\nA0YCm4BlwPnuvsbMLgK+BvwYuBJ42t0XFXl9lYBE6swnn8Cjj4bm8bPPFj/WLCSEqVPhzDPD6Grp\nuqr1AMxsIPBEqwRwPNDk7mPy29cC7u63tPo3VwATCclhhbv/vMBrKwGI1DENpauNWiaAs4FR+Ro/\nZjYBGOHuV5a8CDOfNGkSjY2NADQ0NDB8+PDP53201PzSsN26vhmH9dRyu2VfXNZTy+0VK1Ywbdq0\n2Kyn0HZzM9x2W46nnoLFizP5EdTh65DJ/zfaHjYMTj45x6mnwrhxnft+t912W6rfH2bPng1AY2Nj\n9YbBdXcC0BlAkNOgq88pFpF6jMWHH0ZD6ZYtK37sbrvBuHHRULqePQsfW4+x6C61LgFl3X10fnuX\nElCnF6Fx0CKJtmpVSAT33w9/+UvxY/v3h4kTYcoUOOSQ6qyv3uSqPQ7azBoJCWBofrsnsJbQBH4X\nWAqMd/fXS16EzgBEUkFD6SqrKvcBmNk8YAkw2MzeMrMp7r4DuAJ4GvgjsKCcN/8W2Wx2p9pvWikG\nEcUikpRY9O4NZ50VksDGjXDzzTB4cOHjn38+nAnsvz9cfDEsWQLPPZer2nrjKpfLkc1mu/w6GgUR\nM6pvRhSLSJJj4Q4vvBCuIPrP/4SPPy5+/AEH5Lj88gwTJ4bEkGaxHgXR6UUoAYgIYfrogw+GEtHi\nxcWP7dkTxowJJaKxY8PZRdrEehREKVQCEpG+fUPJ5/nno+mjhT7l79gRSklnnRUax1dfDatXV3e9\ntaISUEIl+VS/VIpFJM2x2HUoXY7onoJdHXtsNJSuoaFaq6yNxJwBiIi0p+1QussvLz56etmyMKto\n//27dyhdEsTmDED3AYhIZ7nD8uWhcTxvHnz0UfHjGxth8uTwZ+DAKiywm1X9PoDupBKQiJTrk0/g\nkUdCMnjmmeLHJm0onUpACaNGeESxiCgWkbax2GOPMFxu4UL4058gmy38Kd89JIkLLgglossvh5de\nCvvTSAlARBKjsRGamuCNN6I3+kKf8j/8EO6+G445BoYPh9tv73hMRdLEpgSkHoCIdIdyhtJNmRKG\n0vXqVZ01lko9ABGREq1aFXoFc+Z0/Gm/Xz+YNCneQ+nUA0gY1XojikVEsYh0JRZDh8Ktt4bLSR9+\nONxB3KPAu+CmTXDTTWFW0de/DrNnhzuVk0QJQERSp3fvcBVQV4bSJaFoEZsSkHoAIlJL7uGNfebM\nzg2lO/TQkBRqMZROPQARkW6yZUu483jmzPDpv5haDqVTDyBhVOuNKBYRxSJSjVj07RvuGv7970sb\nSjdgAFxzTf0MpVMCEBEpYvDg0Ax+6y34zW/CG/1uu7V/7Pvvhybz0KEwYgT87GfhMtS4UglIRKRE\n778Pc+eGEtGqVcWP7dMHzj47lIgymcJXHZVDD4QREakRd3j55ZAI5s6t/lC6xPQA9ECYQDGIKBYR\nxSISp1iYwdFHw113wbvvhiRwyimFj9+wIcwqGjQITj0V5s8Pw+xKVakHwsQqAegSUBGpV22H0jU1\ndW4oXb9+pQ+ly2QyeiKYiEicNTfDc8+FEtHDD8PWrcWPHzYs3FswYQLss0/Hr68egIhIHSh1KN3p\np4fGcbGhdInpAUgQp/pmrSkWEcUiUq+xaGiASy+FpUvDlUNXX134U/727fDQQ+HGsoED4frrYf36\nyq9JCUBEpMqOOAJ+8pMwlO6hh+A736nNUDqVgEREYmDTpjCmeuZMWLeu+LHHHhvOJBJTAtJloCKS\nZv36wfTpsGYNLF4c6v977dX+sUcfXZnLQHUGEDO5XE6Xw+YpFhHFIpKmWGzZAg8+GB5i0zKUrmfP\nUDrab7+unwHE9IFnIiLSt2+4LHTKlFAWmj0bPvggvPlXgs4ARETqVGJ6ACIiUl1KADGjRnhEsYgo\nFhHFonKUAEREUko9ABGROqUegIiIlKVbE4CZDTGze8zsATO7tDu/V1KovhlRLCKKRUSxqJxuTQDu\nvsbdLwPOA/65O79XUqxYsaLWS4gNxSKiWEQUi8rpVAIwsxlmttnMVrbZP9rM1pjZOjObXuDfngb8\nGniy68tNvg/j/ATpKlMsIopFRLGonM6eAcwCRrXeYWY9gDvz+w8HxpvZkPzXLjKzW81sf3d/wt3H\nAhMquG4REemiTo2CcPfFZtb24WYjgPXu/iaAmS0AxgFr3H0OMMfMvmFm1wK7A7+p4LoTa8OGDbVe\nQmwoFhHFIqJYVE6nLwPNJ4An3H1YfvtsYJS7X5LfngCMcPcrS16Ema4BFREpQ90Pg+vKDyAiIuXp\nylVA7wAHttoekN8nIiJ1oJQEYPk/LZYBB5vZQDPrDZwPPF7JxYmISPfp7GWg84AlwGAze8vMprj7\nDuAK4Gngj8ACd3+9+5YqIiKV1KkE4O4XuHs/d9/d3Q9091n5/U+5+6Hufoi731zqN+/MfQRJZWYD\nzGyRmf3RzFaZ2ZX5/V8ys6fNbK2Z/dbM9q71WqvFzHqY2ctm9nh+O5WxMLO9zexBM3s9//txXIpj\n8X0zW21mK81srpn1Tkss2rv/qtjPbmbXmdn6/O/NtzrzPWo2C6jYfQQp8RlwtbsfDpwAXJ7/+a8F\nnnH3Q4FFwHU1XGO1XQW81mo7rbG4HXjS3Q8DjgTWkMJYmFk/QpXhqPzVh72A8aQnFrvcf0WBn93M\n/jdwLnAYMAa428w6vLimlsPgPr+PwN23Ay33EaSCu7/n7ivyf98CvE5opI8D7ssfdh9wRm1WWF1m\nNgD4NvCLVrtTFwsz+yJwcquz7M/c/SNSGIu8nsBeZtYL2INwoUkqYuHui4G/tdld6Gc/nVCG/8zd\nNwDrCe+xRdUyAfQHNrbafju/L3XMrBEYDvwB2M/dN0NIEsA/1W5lVfVT4AdA63tC0hiLQcBfzGxW\nvhz2czMYUVvrAAAB0klEQVTbkxTGwt03AT8B3iK88X/k7s+Qwli08k8Ffva276fv0In3U42DrjEz\n6wv8CrgqfybQ9qa4xN8kZ2Zjgc35M6Jip62JjwWhzHEUcJe7HwV8TDjtT+PvRQPhE+9AoB/hTOBC\nUhiLIrr0s9cyAaT+PoL8ae2vgDnu/lh+92Yz2y//9a8Cf67V+qroROB0M3sDmA9808zmAO+lMBZv\nAxvdfXl++yFCQkjj78UpwBvu/kH+qsNHCFOF0xiLFoV+9neAA1od16n301omAN1HADOB19z99lb7\nHgcm5/8+CXis7T9KGne/Pn912f8i/B4scveLgCdIXyw2AxvNbHB+10jCZdap+70glH6ON7M++Ybm\nSMJFAmmKRdv7rwr97I8D5+evkhoEHAws7fDFa/koRjMbTbjioQcwo5xLSeuVmZ0I/B5YRTiNc+B6\nwv+0BwjZ/E3gXHdPzfxbM/sGcI27n25mXyaFsTCzIwnN8N2AN4AphGZoGmPRRPhQsB14BbgY+AIp\niEX+/qsM8BVgM9AEPAo8SDs/u5ldB3yXEKur3P3pDr+HnsUrIpJOagKLiKSUEoCISEopAYiIpJQS\ngIhISikBiIiklBKAiEhKKQGIiKTU/wfkam5zb/9JLgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1110b02b0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(grad_history, lw=4)\n",
    "plt.grid()\n",
    "plt.yscale('log')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise (20 min): \n",
    "\n",
    "Use the gradient descent algorithm to solve a logistic regression problem. The data is given below. You will need to:\n",
    "\n",
    " * Define the function\n",
    " * Define the gradient\n",
    " * Compute the step size\n",
    " * Perform gradient descent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.random.seed(0)\n",
    "\n",
    "n_samples, n_features = 10, 5\n",
    "A = np.random.randn(n_samples, n_features)\n",
    "w = np.random.randn(n_features)\n",
    "b = np.sign(A.dot(w) + np.random.randn(n_samples))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-1.,  1.,  1., -1.,  1., -1.,  1., -1., -1.,  1.])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def loss_logistic(x):\n",
    "    p = b * A.dot(x)\n",
    "    return -np.sum(np.log(1.0 / (1.0 + np.exp(-p))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6.9314718055994531"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x0 = np.zeros(n_features)\n",
    "loss_logistic(x0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def phi(t):\n",
    "    return  1. / (1 + np.exp(-t))\n",
    "\n",
    "def grad(x):\n",
    "    z = phi(b * A.dot(x))\n",
    "    z0 = (z - 1) * b\n",
    "    grad_w = A.T.dot(z0) \n",
    "    return grad_w\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "cost_history = []\n",
    "grad_history = []\n",
    "xk = np.zeros(n_features)\n",
    "for i in range(max_iter):\n",
    "    xk = xk - 4 * step_size * grad(xk)\n",
    "    cost_history.append(loss_logistic(xk)) # .. insert this line to keep track of iterates ..\n",
    "    grad_history.append(np.linalg.norm(grad(xk)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAECCAYAAAD3vwBsAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGbtJREFUeJzt3XmQVOW5x/HfM2xKRGFUFAYdUERcCpAkZnGbaAwmN8GY\nxRK34L2WWYwaTRnRVIqmKpUbTaIxQWNuggsuFyVXr0tMRI0dNa43ZkRZBEF2QUTAnTDw3j/e7rw9\nw8zQ0326z+k+30/VqT7nnZ7utx+m+uF9n/OeY845AQDSpyHuDgAA4kECAICUIgEAQEqRAAAgpUgA\nAJBSJAAASCkSAACkFAkAAFKq4gnAzEaY2e/N7K5KvxcAoHgVTwDOudecc+dW+n0AAD3T4wRgZjPM\nbJ2Zze3QfpKZLTSzRWZ2WXRdBABUQikjgJskTShsMLMGSdNz7YdJmmRmozv8npXUQwBARfQ4ATjn\nnpS0sUPzkZIWO+eWO+e2Spol6WRJMrNGM/uNpHGMDAAgOXpH9DpNklYWHK+STwpyzr0l6dvd/bKZ\ncUlSACiBc67k2ZXEnAbqnGNzTlOnTo29D0nZiAWxIBbdb+WKKgGslrR/wfGwXBt6aNmyZXF3ITGI\nRUAsAmIRnVITgKl9Ufd5SSPNrNnM+ko6TdJ95XYOAFA5pZwGeoekpySNMrMVZnaOc26bpAskzZE0\nT9Is59yCaLuaDpMnT467C4lBLAJiERCL6FgU80hld8LMTZ06VS0tLWppaYm7OwCQaNlsVtlsVtOm\nTZMrowicmASQhH4kQTabJQnmEIuAWATEIjCzshJAYs4CAgBUFyMAAKhRjAAAACVJTALIZDLKZrNx\ndyN2xCAgFgGxCIiFj0Emkyn7daK6FETZovgwAJAG+TMmp02bVtbrUAMAgBpFDQAAUBISQMIwvxkQ\ni4BYBMQiOiQAAEgpagAAUKPqpgbAaaAAUJyoTgNlBJAwXOckIBYBsQiIRVA3IwAAQHUxAgCAGsUI\nAABQEhJAwlAID4hFQCwCYhEdEgAApFRiagDcEhIAisMtIQEg5SgC1xnmNwNiERCLgFhEhwQAACnF\nFBAA1CimgAAAJSEBJAzzmwGxCIhFQCyiQwIAgJSiBgAANapuagDcDwAAisP9AOoU1zoPiEVALAJi\nEdTNCAAAUF2MAACgRjECAACUhASQMBTCA2IREIuAWESHBAAAKUUNAABqFDUAAEBJSAAJw/xmQCwC\nYhEQi+iQAAAgpRJTA+CewABQHO4JDAApRxG4zjC/GRCLgFgExCI6JAAASCmmgACgRjEFBAAoCQkg\nYZjfDIhFQCwCYhEdEgAApBQ1AACoUdQAAAAlIQEkDPObAbEIiEVALKJDAgCAlKIGAAA1ihoAAKAk\niUkAmUyGuT0xv1mIWATEIiAWPgaZTKbs1+ldfleiEcWHAYA0yF86f9q0aWW9DjUAAKhR1AAAACVJ\nTAKYNy/uHiQD85sBsQiIRUAsopOYBHD99XH3AADSJTE1gGOOcXr88bh7AgC1o9waQGISwKBBThs2\nSFbyRwGAdKmbIvDGjdKaNXH3In7MbwbEIiAWAbGITmISgCS99FLcPQCA9EjMFJDkdNVV0qWXxt0b\nAKgNdTMFJEkvvxx3DwAgPRKVAJgCYn6zELEIiEVALKKTqAQwf77U1hZ3LwAgHRJVA5CkBQuk0aNj\n7hAA1IC6qgFI1AEAoFoSlwDSXgdgfjMgFgGxCIhFdEgAAJBSiasBjBwpLV4cc4cAoAbUzbWA8gnA\nTHr3Xal//5g7BQAJV0dF4IykrJzzp4OmFfObAbEIiEVALKK7J3DCEkCLJOoAANCdlpaWSBJA4qaA\nJOnii6Wrr46xQwBQA+poCihgLQAAVF4iE0Cap4CY3wyIRUAsAmIRncQkgL59w/7atdIbb8TXFwBI\ng8TUAMaPd3rhhdB2553SqafG1ycASLq6qQEcf3z744cfjqcfAJAWiUkAJ57Y/vjhh6UEDE6qjvnN\ngFgExCIgFtFJTAI45hipX79wvHy59Oqr8fUHAOpdYmoAzjmdeKL0yCOhffp06fzz4+sXACRZ3dQA\npM6ngQAAlZHoBPDYY+m7RSTzmwGxCIhFQCyik6gEMHastPfe4fjtt6XnnouvPwBQzxJVA5CkSZOk\nWbPCzzIZaerUePoFAElWVzUAacdpoDlz4ukHANS7xCeAZ5+VNm+Opy9xYH4zIBYBsQiIRXQSlwD2\n2086+OBwvG2bLwYDAKKVuBqAJF14ofTrX4efn366dPvtMXQMABKs7moAknTKKe2P7747XdNAAFAN\niUwAxx0nNTeH4w8/lGbPjq8/1cT8ZkAsAmIREIvoJDIBNDRIZ5/dvu3mm2PpCgDUrUTWACRpyRJp\n5Mj2z1u0SDrooCp2DAASrC5rAJJ04IHS0Ue3b5s5M56+AEA9SmwCkKTJk9sfz5wpbd8eS1eqhvnN\ngFgExCIgFtFJdAL4+telXXcNxytWSPzbA0A0ElsDyDvzzPZrAM44Q7rttip1DAASrG5rAHkdp4Hu\nvFNatiyOngBAfal4AjCz/mZ2s5n91sxO7+nvH3+8NGpUOG5rk666KsoeJgvzmwGxCIhFQCyiU40R\nwFckzXbOfVPSxJ7+ckODdPnl7dtmzJDWrImmcwCQVj2uAZjZDElflLTOOTemoP0kSb+UTyoznHNX\n5tqnSHrQOTfXzG53zp3RyWt2WQOQpK1b/fn/y5eHtosvlq6+ukddB4C6EkcN4CZJEzp0okHS9Fz7\nYZImmdno3I9XShqWf2opnezTR5oypX3bDTdI69eX8moAAKmEBOCce1LSxg7NR0pa7Jxb7pzbKmmW\npJNzP7tH0tfM7DpJ95fa0XPOkYYODccffCBdc02pr5ZczG8GxCIgFgGxiE7viF6nSf5/+nmr5JOC\nnHPvS/r3nb3A5MmTNXz4cEnSwIEDNW7cOLW0tEgK/+A/+EGLvvc9SfLH06e36KKLpAUL/HHH53Nc\n28d5SelPnMetra2J6k+cx62trYnqTzWPs9msbs5dGC3/fVmOktYBmFmzpPvzNQAz+6qkCc6583LH\nZ0o60jl3YZGv120NIO/996Xhw9tP/Zx9tnTLLT3+CABQ85KyDmC1pP0Ljofl2iLVv790xRXt22bO\nlJ54Iup3AoD6V2oCMLUv6D4vaaSZNZtZX0mnSbqv3M515vzzpcMPb9/2ne/4M4XqQcfpjzQjFgGx\nCIhFdHqcAMzsDklPSRplZivM7Bzn3DZJF0iaI2mepFnOuQXRdtXr00e6/vr2bS+/LE2fXol3A4D6\nlZhrAU2dOlUtLS3/KnzszNlnS7feGo53201auFBqaqpMHwEgKbLZrLLZrKZNm1ZWDSAxCaCn/Vi3\nzl8i4u23Q9sJJ0hz5vjVwwBQ75JSBK66ffaRfvzj9m2PPipdeWU8/YkK85sBsQiIRUAsolOzCUDy\nxd+OM0Y/+pH09NOxdAcAakrNTgHlrV4tjR0rbdgQ2pqbpdZWaeDAiDoIAAmU2imgvKYmKbcw7l+W\nL/dF4m3bYukSANSExCSATCZT8tzeF78oXXRR+7b775cuuaT8flUb85sBsQiIRUAsfAwymUzZr5Oo\nBFDsKaCdufJKafz49m2/+pV07bXl9QsAkqalpSWSBFDzNYBCq1dLn/iEfwyvLd19t/TlL5f98gCQ\nKKmvARRqapIefFAaMCC0OSeddpr00EPx9QsAkqiuEoAkjRkjzZ4t9eoV2rZskU4+WfrTn+LrV7GY\n3wyIRUAsAmIRnbpLAJI0YYK/Y1ihLVv8NNADD8TTJwBImsTUAHp6LaBiXHed9N3vtm/r00e68Ubp\nzDMjexsAqKrUXwuoWDfcIH372zu2T5vmVw1byaEDgHhRBN6Jb31L+u1vd2yfOlX6xjf81FCSML8Z\nEIuAWATEIjp1nwAk6bzzpDvukPr2bd9+663SscdKy5bF0i0AiFXdTwEVevJJXwguvG6Q5K8ZdMst\n0sSJFe8CAESGKaAeOPpof6XQgw5q375pkz9N9OKLpQ8+iKdvAFBtqUoAkv/yf+YZ6Utf2vFnv/yl\nNG6c9NRT1e9XHvObAbEIiEVALKKTugQgSY2N0r33Sj//efsFY5K0aJEfKXz/+9K778bTPwCohsTU\nACqxDqAYTz0lnX66v4R0R01N0i9+IZ16KqeLAkgO1gFE6J13pEsv7fx0UUn6zGeka67xN54BgKSg\nCByBAQP8grGHH5b233/Hnz/2mHTEEX718GuvVbYvzG8GxCIgFgGxiA4JoMBnPyvNmydddpm/ZEQh\n56Tbb5cOPtjfi7izKSMAqCVMAXXhlVekCy7wo4LO9O7tbzs5ZcqOp5UCQDWUOwVEAuiGc/4S0lOm\nSC+91PlzzPwCsksukY45hmIxgOqhBlBBZtIXviD94x/SzJnS8OE7Psc5f0rpccdJH/uYNGOG9N57\npb8n85sBsQiIRUAsokMCKEKvXtJZZ/k1AjfeKI0c2fnzXnhBOvdcaehQfxnqF1+sbj8BoCeYAipB\nW5t0113Sz34mtbZ2/9wxY6TJk/1ag332qUr3AKRE3UwBZTKZmhna9e7tv9BfeMGfIjpxYtdz/3Pn\n+vrA0KHS5z7nRxAbN1a3vwDqSzabVSaTKft1GAFEZOlS6Xe/81/wb7zR/XP79JGOP176ylf8RegK\nRwbZbLbqq6GTilgExCIgFkHdjABq3QEHSP/5n9LKldKdd0qf/7zU0EV0t26VHnpI+uY3pSFDpE9/\nWvrJT/xoocbzIIAawgiggtas8YvHbrvNf7kXY9gwf1P7CRP8wrRBgyrbRwC1i3UANWLBAj8ymDXL\nLzIrRkOD9NGP+umiE07wI4WPfKSy/QRQO0gANcY5nwzuuUe6+25fSG4vK6ml09/t3Vv6+Mf9moNj\nj5U+9Sl/N7N6xVxvQCwCYhGUmwB6R9kZ7JyZdOihfvvhD6VVq6Q//lF64AHp0Ue7vyNZW5u/o9nT\nT0s//al/rcMPl446yieDT37SX5aC1cgAisEIIEE+/FB64glfIH7oIenll3v+Go2NfpRQuA0ZEn1f\nAcSPKaA6tm6dX2fw6KP+ccmS0l5nyBBfSxg/3l/W+ogj/GWvGSkAtY0EUGe6m99cvVp6/HHpr3+V\n/vY3f+nqUsM2aJC/wc2YMWE79NBkFZmZ6w2IRUAsAmoAKdLUJE2a5DdJ2rTJ39LymWf89uyz0ttv\nF/daGzdK2azf8sz8eobDD5cOO8xvhx4qjR4t7bJL1J8GQNwSMwKI657A9WT7dmnhQun558P24ovS\nli3lva6ZNGKEdMghfhs9Omx77hlN3wEUj3sCoyhbt/rTTv/+d39Z69ZWv73zTjSv39jo75I2apTf\nDjrIbyNHSrvtFs17AOgcNYA6U435ze3b/b2N587124sv+hveLFkS7aUo9t3XJ4KRI6UDD2y/NTbu\nvAjNXG9ALAJiEVADQI81NIQv4lNOCe3vvy/Nn+9PP50/3xeZ580r/f7Ha9f67cknd/zZ7rv7esOI\nEeExvzU3S/37l/aeAIrHCAA79d57/vIVCxb4GsMrr/jHxYv92oVKGDzY34EtvzU3h23//X0CAdKO\nKSDEZvt2f/XTRYt8Uli82G+LFknLlknbtlXuvQcO9ImgcNtvv/A4dKi/7DZQz0gAdaZe5je3bvVT\nR6++6relS32NYckSv9/dJS+CrLq6LtLOmPkFcMOG+YSQf2xq8vvDhvkk0bdvSS9fdfXydxEFYhFQ\nA0Ai9ekTCsAdOedXOS9d6ovRhY/Ll/tRRbmjB+f85bjXrJGee67r5w0e7JNCPjHk95uafIJoavKj\nDVZNox4xAkDitLX5i+QtX+6nkpYt8/v5bcUKP8Koll139ckgvw0Z0n4/f7z77iQKVBdTQEid7dv9\nbTfzyWDlSv+Y31+50o8wqi2fKPJJYcgQfypsx/299ur6bnFAT5AA6gzzm0E5sdiyxV87adWqkBTy\nx6tW+f21a+O5BWevXn7qKZ8U9t3X3xc6v1/Ylh9V8HcREIuAGgDQiX79/PqCAw7o+jlbt0qvv+4T\nwpo1Pinkt8Lj99+Ptm/btvn3ff31nT+3Xz+fDHbd1a+wzieGjtvgwdQq0HOMAIBuOOcvm5FPCGvW\n+C/u1av9Y/54zZrKrYkoVt++PhHkE0LHx8L9vfbiNNl6wBQQkADOSZs3h2Swdm34X35+P/+4aVPc\nvfUaG0NiKNz23nvH/UGDqFskUd1MAWUyGa4GKuY3C9VSLMz8FMzAgf6Kqd358ENfpH79df+YTwz5\n/cKfhfUSWZW6JqIrb73lt4ULd/7cXr38qCGfFPKJIb/fcWtsrFzCqKW/i0rJXw20XIwAEoY/7iDt\nsXBOevddnxT+/Oeshgxp0bp12mF74w3/+N57cfc4aGjwlwrfe2+fODpLEvn2vfbyW79+xb122v8u\nCjEFBECSTwD5ZFCYGAof8/tvvRXPGVDdGTCgfULoaj+/MS1FAgBQgrY2acMGnwzWr2+fHNavD235\nx2LvNFdNDQ1+qqljYshve+654/4ee9RX0iAB1BmGtwGxCOKOxZYtOyaGjvuFbZVNGFmVWg/JT011\nlhzy7R2PGxt9DSSJ6qYIDCC5+vULF9ErxpYtfoSRTwpvvrljoli/Pjxnw4bKXj02b/v28N7Fyhf4\nCxNEMVst3NOCEQCA2G3f7k+PzSeKN99snzQ2bAjH+f3Nm+Pudfd22aX9KKLjfsfHPff0dY2eXKGW\nKSAAqfTPf/pidmGy6CxRvPmm39+wIbp7YVfSgAGdJ4nC/ZYWf3MkEkCdiXuuN0mIRUAsgnKvEZVP\nBoXTT/lkUfiz/HFSFu4Vmj1b+trXqAEAQNH69QuX8i5WW5sfaRQmh2K2Sl6yvLExmtdhBAAAEXPO\nr8vomBQKE0l+v/Cx2PUZra3S2LGMAAAgccyk3XbzW3Nz8b+XL4Zv3Ng+UXRMFkOGRNTPJPzPmxFA\nwFxvQCwCYhEQi6DcEUAdrYkDAPQEIwAAqFGMAAAAJSEBJEwU1/iuF8QiIBYBsYgOCQAAUooaAADU\nqLqpAWQyGYZ2AFCEbDarTCZT9uswAkgYznEOiEVALAJiEdTNCAAAUF2MAACgRjECAACUhASQMBTC\nA2IREIuAWESHBAAAKUUNAABqFDUAAEBJSAAJw/xmQCwCYhEQi+iQAAAgpagBAECNogYAACgJCSBh\nmN8MiEVALAJiER0SAACkFDUAAKhR1AAAACUhASQM85sBsQiIRUAsokMCAICUogYAADWKGgAAoCQk\ngIRhfjMgFgGxCIhFdEgAAJBS1AAAoEZRAwAAlIQEkDDMbwbEIiAWAbGIDgkAAFKKGgAA1ChqAACA\nklQ0AZjZCDP7vZndVcn3qSfMbwbEIiAWAbGITkUTgHPuNefcuZV8j3rT2toadxcSg1gExCIgFtEp\nKgGY2QwzW2dmczu0n2RmC81skZldVpkupsumTZvi7kJiEIuAWATEIjrFjgBukjShsMHMGiRNz7Uf\nJmmSmY3O/ewsM7vazIbknx5RfwEAESkqATjnnpS0sUPzkZIWO+eWO+e2Spol6eTc8291zl0iaYuZ\n/UbSOEYIxVm2bFncXUgMYhEQi4BYRKfo00DNrFnS/c65Mbnjr0qa4Jw7L3d8pqQjnXMX9rgTZpwD\nCgAlKOc00N5RdqRU5XwAAEBpyjkLaLWk/QuOh+XaAAA1oCcJwNS+mPu8pJFm1mxmfSWdJum+KDsH\nAKicYk8DvUPSU5JGmdkKMzvHObdN0gWS5kiaJ2mWc25B5boKAIhSsWcBne6cG+qc6+ec2985d1Ou\n/U/OuYOdcwc5537a0zdP8zoCMxtmZn8xs3lm9pKZXZhrH2Rmc8zsFTN7yMz2iLuv1WJmDWb2gpnd\nlztOZSzMbA8zm21mC3J/H59IcSwuNrOXzWyumd1uZn3TEovO1l9199nN7HIzW5z7u/lcMe8R27WA\nultHkBJtki5xzh0m6VOSzs99/imSHnHOHSzpL5Iuj7GP1XaRpPkFx2mNxbWSHnTOHSJprKSFSmEs\nzGyo/CzD+NzZh70lTVJ6YrHD+it18dnN7FBJp0o6RNLnJV1vZjs9uSbOi8F1uY4gDZxza51zrbn9\ndyUtkC+knyzpltzTbpH05Xh6WF1mNkzSFyT9vqA5dbEws90lHVMwym5zzm1WCmOR00vSR8yst6Rd\n5U80SUUsulh/1dVnnyg/Dd/mnFsmabH8d2y34kwATZJWFhyvyrWljpkNlzRO0jOS9nHOrZN8kpA0\nOL6eVdU1ki6VVLgmJI2xGCHpTTO7KTcd9l9m1l8pjIVzbo2kX0haIf/Fv9k594hSGIsCg7v47B2/\nT1eriO9TLgcdMzPbTdIfJF2UGwl0XBRX94vkzOzfJK3LjYi6G7bWfSzkpznGS7rOOTde0nvyw/40\n/l0MlP8fb7OkofIjgTOUwlh0o6zPHmcCSP06gtyw9g+SbnXO3ZtrXmdm++R+vq+kN+LqXxUdJWmi\nmS2V9N+SjjezWyWtTWEsVkla6Zz7v9zx/8gnhDT+XXxW0lLn3Fu5sw7vkfRppTMWeV199tWS9it4\nXlHfp3EmANYRSDdKmu+cu7ag7T5Jk3P735B0b8dfqjfOuStyZ5cdIP938Bfn3FmS7lf6YrFO0koz\nG5VrOkH+NOvU/V3IT/180sx2yRU0T5A/SSBNsei4/qqrz36fpNNyZ0mNkDRS0nM7ffE4b8VoZifJ\nn/HQIGlGKaeS1iozO0rS45Jekh/GOUlXyP+j3SWfzZdLOtU5l5rr35rZcZK+75ybaGaNSmEszGys\nfDG8j6Slks6RL4amMRZT5f9TsFXSPySdK2mAUhCL3PqrFkl7Slonaaqk/5U0W518djO7XNJ/yMfq\nIufcnJ2+B/fiBYB0oggMAClFAgCAlCIBAEBKkQAAIKVIAACQUiQAAEgpEgAApNT/A/vSe6wKW5Fe\nAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x110e1b668>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(grad_history, lw=4)\n",
    "plt.grid()\n",
    "plt.yscale('log')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}