{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Useful starting lines\n",
    "%matplotlib inline\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "# Load the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime\n",
    "from helpers import *\n",
    "\n",
    "height, weight, gender = load_data(sub_sample=False, add_outlier=False)\n",
    "x, mean_x, std_x = standardize(height)\n",
    "y, tx = build_model_data(x, weight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y.shape, tx.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "### NB: throughout this laboratory the data has the following format: \n",
    "  * there are **N = 10000** data entries\n",
    "  * **y** represents the column vector containing weight information -- that which we wish to predict/the output (see also the first page of $\\texttt{exercise02.pdf}$). Its **shape** is **(N,)**.\n",
    "  * **tx** represents the matrix $\\tilde{X}$ formed by laterally concatenating a column vector of 1s to the column vector of height information -- the input data (see also the first page of $\\texttt{exercise02.pdf}$). Its **shape** is **(N,2)**."
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "# 1. Computing the Cost Function\n",
    "Fill in the `compute_loss` function below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_loss(y, tx, w):\n",
    "    \"\"\"Calculate the loss using either MSE or MAE.\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(N, )\n",
    "        tx: numpy array of shape=(N,2)\n",
    "        w: numpy array of shape=(2,). The vector of model parameters.\n",
    "\n",
    "    Returns:\n",
    "        the value of the loss (a scalar), corresponding to the input parameters w.\n",
    "    \"\"\"\n",
    "    # ***************************************************\n",
    "    # INSERT YOUR CODE HERE\n",
    "    # TODO: compute loss by MSE\n",
    "    # ***************************************************\n",
    "    raise NotImplementedError"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "# 2. Grid Search"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "Fill in the function `grid_search()` below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# from costs import *\n",
    "\n",
    "\n",
    "def grid_search(y, tx, grid_w0, grid_w1):\n",
    "    \"\"\"Algorithm for grid search.\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(N, )\n",
    "        tx: numpy array of shape=(N,2)\n",
    "        grid_w0: numpy array of shape=(num_grid_pts_w0, ). A 1D array containing num_grid_pts_w0 values of parameter w0 to be tested in the grid search.\n",
    "        grid_w1: numpy array of shape=(num_grid_pts_w1, ). A 1D array containing num_grid_pts_w1 values of parameter w1 to be tested in the grid search.\n",
    "\n",
    "    Returns:\n",
    "        losses: numpy array of shape=(num_grid_pts_w0, num_grid_pts_w1). A 2D array containing the loss value for each combination of w0 and w1\n",
    "    \"\"\"\n",
    "\n",
    "    losses = np.zeros((len(grid_w0), len(grid_w1)))\n",
    "    # ***************************************************\n",
    "    # INSERT YOUR CODE HERE\n",
    "    # TODO: compute loss for each combination of w0 and w1.\n",
    "    # ***************************************************\n",
    "    raise NotImplementedError\n",
    "    return losses"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "Let us play with the grid search demo now!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from grid_search import generate_w, get_best_parameters\n",
    "from plots import grid_visualization\n",
    "\n",
    "# Generate the grid of parameters to be swept\n",
    "grid_w0, grid_w1 = generate_w(num_intervals=10)\n",
    "\n",
    "# Start the grid search\n",
    "start_time = datetime.datetime.now()\n",
    "grid_losses = grid_search(y, tx, grid_w0, grid_w1)\n",
    "\n",
    "# Select the best combinaison\n",
    "loss_star, w0_star, w1_star = get_best_parameters(grid_w0, grid_w1, grid_losses)\n",
    "end_time = datetime.datetime.now()\n",
    "execution_time = (end_time - start_time).total_seconds()\n",
    "\n",
    "# Print the results\n",
    "print(\n",
    "    \"Grid Search: loss*={l}, w0*={w0}, w1*={w1}, execution time={t:.3f} seconds\".format(\n",
    "        l=loss_star, w0=w0_star, w1=w1_star, t=execution_time\n",
    "    )\n",
    ")\n",
    "\n",
    "# Plot the results\n",
    "fig = grid_visualization(grid_losses, grid_w0, grid_w1, mean_x, std_x, height, weight)\n",
    "fig.set_size_inches(10.0, 6.0)\n",
    "fig.savefig(\"grid_plot\")  # Optional saving"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "# 3. Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "Again, please fill in the functions `compute_gradient` below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_gradient(y, tx, w):\n",
    "    \"\"\"Computes the gradient at w.\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(N, )\n",
    "        tx: numpy array of shape=(N,2)\n",
    "        w: numpy array of shape=(2, ). The vector of model parameters.\n",
    "\n",
    "    Returns:\n",
    "        An numpy array of shape (2, ) (same shape as w), containing the gradient of the loss at w.\n",
    "    \"\"\"\n",
    "    # ***************************************************\n",
    "    # INSERT YOUR CODE HERE\n",
    "    # TODO: compute gradient vector\n",
    "    # ***************************************************\n",
    "    raise NotImplementedError"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "Please fill in the functions `gradient_descent` below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gradient_descent(y, tx, initial_w, max_iters, gamma):\n",
    "    \"\"\"The Gradient Descent (GD) algorithm.\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(N, )\n",
    "        tx: numpy array of shape=(N,2)\n",
    "        initial_w: numpy array of shape=(2, ). The initial guess (or the initialization) for the model parameters\n",
    "        max_iters: a scalar denoting the total number of iterations of GD\n",
    "        gamma: a scalar denoting the stepsize\n",
    "\n",
    "    Returns:\n",
    "        losses: a list of length max_iters containing the loss value (scalar) for each iteration of GD\n",
    "        ws: a list of length max_iters + 1 containing the model parameters as numpy arrays of shape (2, ),\n",
    "            for each iteration of GD (as well as the final weights)\n",
    "    \"\"\"\n",
    "    # Define parameters to store w and loss\n",
    "    ws = [initial_w]\n",
    "    losses = []\n",
    "    w = initial_w\n",
    "    for n_iter in range(max_iters):\n",
    "        # ***************************************************\n",
    "        # INSERT YOUR CODE HERE\n",
    "        # TODO: compute gradient and loss\n",
    "        # ***************************************************\n",
    "        raise NotImplementedError\n",
    "        # ***************************************************\n",
    "        # INSERT YOUR CODE HERE\n",
    "        # TODO: update w by gradient\n",
    "        # ***************************************************\n",
    "        raise NotImplementedError\n",
    "\n",
    "        # store w and loss\n",
    "        ws.append(w)\n",
    "        losses.append(loss)\n",
    "        print(\n",
    "            \"GD iter. {bi}/{ti}: loss={l}, w0={w0}, w1={w1}\".format(\n",
    "                bi=n_iter, ti=max_iters - 1, l=loss, w0=w[0], w1=w[1]\n",
    "            )\n",
    "        )\n",
    "\n",
    "    return losses, ws"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "Test your gradient descent function through gradient descent demo shown below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# from gradient_descent import *\n",
    "from plots import gradient_descent_visualization\n",
    "\n",
    "# Define the parameters of the algorithm.\n",
    "max_iters = 50\n",
    "gamma = 0.7\n",
    "\n",
    "# Initialization\n",
    "w_initial = np.array([0, 0])\n",
    "\n",
    "# Start gradient descent.\n",
    "start_time = datetime.datetime.now()\n",
    "gd_losses, gd_ws = gradient_descent(y, tx, w_initial, max_iters, gamma)\n",
    "end_time = datetime.datetime.now()\n",
    "\n",
    "# Print result\n",
    "exection_time = (end_time - start_time).total_seconds()\n",
    "print(\"GD: execution time={t:.3f} seconds\".format(t=exection_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Time Visualization\n",
    "from ipywidgets import IntSlider, interact\n",
    "\n",
    "\n",
    "def plot_figure(n_iter):\n",
    "    fig = gradient_descent_visualization(\n",
    "        gd_losses,\n",
    "        gd_ws,\n",
    "        grid_losses,\n",
    "        grid_w0,\n",
    "        grid_w1,\n",
    "        mean_x,\n",
    "        std_x,\n",
    "        height,\n",
    "        weight,\n",
    "        n_iter,\n",
    "    )\n",
    "    fig.set_size_inches(10.0, 6.0)\n",
    "\n",
    "\n",
    "interact(plot_figure, n_iter=IntSlider(min=1, max=len(gd_ws)))"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 4. Stochastic gradient descent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_stoch_gradient(y, tx, w):\n",
    "    \"\"\"Compute a stochastic gradient at w from a data sample batch of size B, where B < N, and their corresponding labels.\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(B, )\n",
    "        tx: numpy array of shape=(B,2)\n",
    "        w: numpy array of shape=(2, ). The vector of model parameters.\n",
    "\n",
    "    Returns:\n",
    "        A numpy array of shape (2, ) (same shape as w), containing the stochastic gradient of the loss at w.\n",
    "    \"\"\"\n",
    "\n",
    "    # ***************************************************\n",
    "    # INSERT YOUR CODE HERE\n",
    "    # TODO: implement stochastic gradient computation. It's the same as the usual gradient.\n",
    "    # ***************************************************\n",
    "    raise NotImplementedError\n",
    "\n",
    "\n",
    "def stochastic_gradient_descent(y, tx, initial_w, batch_size, max_iters, gamma):\n",
    "    \"\"\"The Stochastic Gradient Descent algorithm (SGD).\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(N, )\n",
    "        tx: numpy array of shape=(N,2)\n",
    "        initial_w: numpy array of shape=(2, ). The initial guess (or the initialization) for the model parameters\n",
    "        batch_size: a scalar denoting the number of data points in a mini-batch used for computing the stochastic gradient\n",
    "        max_iters: a scalar denoting the total number of iterations of SGD\n",
    "        gamma: a scalar denoting the stepsize\n",
    "\n",
    "    Returns:\n",
    "        losses: a list of length max_iters containing the loss value (scalar) for each iteration of SGD\n",
    "        ws: a list of length max_iters containing the model parameters as numpy arrays of shape (2, ), for each iteration of SGD\n",
    "    \"\"\"\n",
    "\n",
    "    # Define parameters to store w and loss\n",
    "    ws = [initial_w]\n",
    "    losses = []\n",
    "    w = initial_w\n",
    "\n",
    "    for n_iter in range(max_iters):\n",
    "        # ***************************************************\n",
    "        # INSERT YOUR CODE HERE\n",
    "        # TODO: implement stochastic gradient descent.\n",
    "        # ***************************************************\n",
    "        raise NotImplementedError\n",
    "\n",
    "        print(\n",
    "            \"SGD iter. {bi}/{ti}: loss={l}, w0={w0}, w1={w1}\".format(\n",
    "                bi=n_iter, ti=max_iters - 1, l=loss, w0=w[0], w1=w[1]\n",
    "            )\n",
    "        )\n",
    "    return losses, ws"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# from stochastic_gradient_descent import *\n",
    "\n",
    "# Define the parameters of the algorithm.\n",
    "max_iters = 50\n",
    "gamma = 0.1\n",
    "batch_size = 1\n",
    "\n",
    "# Initialization\n",
    "w_initial = np.array([0, 0])\n",
    "\n",
    "# Start SGD.\n",
    "start_time = datetime.datetime.now()\n",
    "sgd_losses, sgd_ws = stochastic_gradient_descent(\n",
    "    y, tx, w_initial, batch_size, max_iters, gamma\n",
    ")\n",
    "end_time = datetime.datetime.now()\n",
    "\n",
    "# Print result\n",
    "exection_time = (end_time - start_time).total_seconds()\n",
    "print(\"SGD: execution time={t:.3f} seconds\".format(t=exection_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Time Visualization\n",
    "from ipywidgets import IntSlider, interact\n",
    "\n",
    "\n",
    "def plot_figure(n_iter):\n",
    "    fig = gradient_descent_visualization(\n",
    "        sgd_losses,\n",
    "        sgd_ws,\n",
    "        grid_losses,\n",
    "        grid_w0,\n",
    "        grid_w1,\n",
    "        mean_x,\n",
    "        std_x,\n",
    "        height,\n",
    "        weight,\n",
    "        n_iter,\n",
    "    )\n",
    "    fig.set_size_inches(10.0, 6.0)\n",
    "\n",
    "\n",
    "interact(plot_figure, n_iter=IntSlider(min=1, max=len(sgd_ws)))"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "# 5. Effect of Outliers and MAE Cost Function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime\n",
    "from helpers import *\n",
    "\n",
    "# ***************************************************\n",
    "# INSERT YOUR CODE HERE\n",
    "# TODO: reload the data by subsampling first, then by subsampling and adding outliers\n",
    "# ***************************************************\n",
    "raise NotImplementedError\n",
    "\n",
    "x, mean_x, std_x = standardize(height)\n",
    "y, tx = build_model_data(x, weight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y.shape, tx.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from plots import gradient_descent_visualization\n",
    "\n",
    "# Define the parameters of the algorithm.\n",
    "max_iters = 50\n",
    "gamma = 0.7\n",
    "\n",
    "# Initialization\n",
    "w_initial = np.array([0, 0])\n",
    "\n",
    "# Start gradient descent.\n",
    "start_time = datetime.datetime.now()\n",
    "\n",
    "# ***************************************************\n",
    "# INSERT YOUR CODE HERE\n",
    "# TODO: fit the model to the subsampled data / subsampled data with outliers and visualize the cloud of points\n",
    "#       and the model fit\n",
    "# ***************************************************\n",
    "raise NotImplementedError\n",
    "\n",
    "\n",
    "end_time = datetime.datetime.now()\n",
    "\n",
    "# Print result\n",
    "exection_time = (end_time - start_time).total_seconds()\n",
    "print(\"GD: execution time={t:.3f} seconds\".format(t=exection_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Time Visualization\n",
    "from ipywidgets import IntSlider, interact\n",
    "\n",
    "\n",
    "def plot_figure(n_iter):\n",
    "    fig = gradient_descent_visualization(\n",
    "        gd_losses,\n",
    "        gd_ws,\n",
    "        grid_losses,\n",
    "        grid_w0,\n",
    "        grid_w1,\n",
    "        mean_x,\n",
    "        std_x,\n",
    "        height,\n",
    "        weight,\n",
    "        n_iter,\n",
    "    )\n",
    "    fig.set_size_inches(10.0, 6.0)\n",
    "\n",
    "\n",
    "interact(plot_figure, n_iter=IntSlider(min=1, max=len(gd_ws)))"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 6. Subgradient descent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_subgradient_mae(y, tx, w):\n",
    "    \"\"\"Compute a subgradient of the MAE at w.\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(N, )\n",
    "        tx: numpy array of shape=(N,2)\n",
    "        w: numpy array of shape=(2, ). The vector of model parameters.\n",
    "\n",
    "    Returns:\n",
    "        A numpy array of shape (2, ) (same shape as w), containing the subgradient of the MAE at w.\n",
    "    \"\"\"\n",
    "    # ***************************************************\n",
    "    # INSERT YOUR CODE HERE\n",
    "    # TODO: compute subgradient gradient vector for MAE\n",
    "    # ***************************************************\n",
    "    raise NotImplementedError"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def subgradient_descent(y, tx, initial_w, max_iters, gamma):\n",
    "    \"\"\"The SubGradient Descent (SubGD) algorithm.\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(N, )\n",
    "        tx: numpy array of shape=(N,2)\n",
    "        initial_w: numpy array of shape=(2, ). The initial guess (or the initialization) for the model parameters\n",
    "        max_iters: a scalar denoting the total number of iterations of GD\n",
    "        gamma: a scalar denoting the stepsize\n",
    "\n",
    "    Returns:\n",
    "        losses: a list of length max_iters containing the loss value (scalar) for each iteration of SubGD\n",
    "        ws: a list of length max_iters containing the model parameters as numpy arrays of shape (2, ), for each iteration of SubGD\n",
    "    \"\"\"\n",
    "    # Define parameters to store w and loss\n",
    "    ws = [initial_w]\n",
    "    losses = []\n",
    "    w = initial_w\n",
    "    for n_iter in range(max_iters):\n",
    "        # ***************************************************\n",
    "        # INSERT YOUR CODE HERE\n",
    "        # TODO: compute subgradient and loss\n",
    "        # ***************************************************\n",
    "        raise NotImplementedError\n",
    "        # ***************************************************\n",
    "        # INSERT YOUR CODE HERE\n",
    "        # TODO: update w by subgradient\n",
    "        # ***************************************************\n",
    "        raise NotImplementedError\n",
    "\n",
    "        ws.append(w)\n",
    "        losses.append(loss)\n",
    "        print(\n",
    "            \"SubGD iter. {bi}/{ti}: loss={l}, w0={w0}, w1={w1}\".format(\n",
    "                bi=n_iter, ti=max_iters - 1, l=loss, w0=w[0], w1=w[1]\n",
    "            )\n",
    "        )\n",
    "\n",
    "    return losses, ws"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the parameters of the algorithm.\n",
    "max_iters = 500\n",
    "gamma = 0.7\n",
    "batch_size = 1\n",
    "\n",
    "# Initialization\n",
    "w_initial = np.array([0, 0])\n",
    "\n",
    "# Start SubSGD.\n",
    "start_time = datetime.datetime.now()\n",
    "subgd_losses, subgd_ws = subgradient_descent(y, tx, w_initial, max_iters, gamma)\n",
    "end_time = datetime.datetime.now()\n",
    "\n",
    "# Print result\n",
    "exection_time = (end_time - start_time).total_seconds()\n",
    "print(\"SubGD: execution time={t:.3f} seconds\".format(t=exection_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ipywidgets import IntSlider, interact\n",
    "\n",
    "\n",
    "def plot_figure(n_iter):\n",
    "    fig = gradient_descent_visualization(\n",
    "        subgd_losses,\n",
    "        subgd_ws,\n",
    "        grid_losses,\n",
    "        grid_w0,\n",
    "        grid_w1,\n",
    "        mean_x,\n",
    "        std_x,\n",
    "        height,\n",
    "        weight,\n",
    "        n_iter,\n",
    "    )\n",
    "    fig.set_size_inches(10.0, 6.0)\n",
    "\n",
    "\n",
    "interact(plot_figure, n_iter=IntSlider(min=1, max=len(subgd_ws)))"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "source": [
    "# Stochastic Subgradient Descent\n",
    "\n",
    "**NB** for the computation of the subgradient you can reuse the `compute_subgradient` method that you implemented above, just making sure that you pass in a minibatch as opposed to the full data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stochastic_subgradient_descent(y, tx, initial_w, batch_size, max_iters, gamma):\n",
    "    \"\"\"Compute a stochastic subgradient at w from a data sample batch of size B, where B < N, and their corresponding labels.\n",
    "\n",
    "    Args:\n",
    "        y: numpy array of shape=(B, )\n",
    "        tx: numpy array of shape=(B,2)\n",
    "        initial_w: numpy array of shape=(2, ). The initial guess (or the initialization) for the model parameters\n",
    "        batch_size: a scalar denoting the number of data points in a mini-batch used for computing the stochastic subgradient\n",
    "        max_iters: a scalar denoting the total number of iterations of SubSGD\n",
    "        gamma: a scalar denoting the stepsize\n",
    "\n",
    "    Returns:\n",
    "        losses: a list of length max_iters containing the loss value (scalar) for each iteration of SubSGD\n",
    "        ws: a list of length max_iters containing the model parameters as numpy arrays of shape (2, ), for each iteration of SubSGD\n",
    "    \"\"\"\n",
    "\n",
    "    # Define parameters to store w and loss\n",
    "    ws = [initial_w]\n",
    "    losses = []\n",
    "    w = initial_w\n",
    "\n",
    "    for n_iter in range(max_iters):\n",
    "        # ***************************************************\n",
    "        # INSERT YOUR CODE HERE\n",
    "        # TODO: implement stochastic subgradient descent.\n",
    "        # ***************************************************\n",
    "        raise NotImplementedError\n",
    "\n",
    "        print(\n",
    "            \"SubSGD iter. {bi}/{ti}: loss={l}, w0={w0}, w1={w1}\".format(\n",
    "                bi=n_iter, ti=max_iters - 1, l=loss, w0=w[0], w1=w[1]\n",
    "            )\n",
    "        )\n",
    "    return losses, ws"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the parameters of the algorithm.\n",
    "max_iters = 500\n",
    "gamma = 0.7\n",
    "batch_size = 1\n",
    "\n",
    "# Initialization\n",
    "w_initial = np.array([0, 0])\n",
    "\n",
    "# Start SubSGD.\n",
    "start_time = datetime.datetime.now()\n",
    "subsgd_losses, subsgd_ws = stochastic_subgradient_descent(\n",
    "    y, tx, w_initial, batch_size, max_iters, gamma\n",
    ")\n",
    "end_time = datetime.datetime.now()\n",
    "\n",
    "# Print result\n",
    "exection_time = (end_time - start_time).total_seconds()\n",
    "print(\"SubSGD: execution time={t:.3f} seconds\".format(t=exection_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ipywidgets import IntSlider, interact\n",
    "\n",
    "\n",
    "def plot_figure(n_iter):\n",
    "    fig = gradient_descent_visualization(\n",
    "        subsgd_losses,\n",
    "        subsgd_ws,\n",
    "        grid_losses,\n",
    "        grid_w0,\n",
    "        grid_w1,\n",
    "        mean_x,\n",
    "        std_x,\n",
    "        height,\n",
    "        weight,\n",
    "        n_iter,\n",
    "    )\n",
    "    fig.set_size_inches(10.0, 6.0)\n",
    "\n",
    "\n",
    "interact(plot_figure, n_iter=IntSlider(min=1, max=len(subsgd_ws)))"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}