GradientDescent.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "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.7.1-final"
    },
    "colab": {
      "name": "GradientDescent.ipynb",
      "provenance": [],
      "collapsed_sections": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OUXUbvIcbmSy"
      },
      "source": [
        "# Data Generation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WPlLJzl9bmS6"
      },
      "source": [
        "%matplotlib inline\n",
        "import numpy as np\n",
        "import numpy.linalg as la\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "dim_theta = 10\n",
        "data_num = 1000\n",
        "scale = .1\n",
        "\n",
        "theta_true = np.ones((dim_theta,1))\n",
        "print('True theta:', theta_true.reshape(-1))\n",
        "\n",
        "A = np.random.uniform(low=-1.0, high=1.0, size=(data_num,dim_theta))\n",
        "y_data = A @ theta_true + np.random.normal(loc=0.0, scale=scale, size=(data_num, 1))\n",
        "\n",
        "A_test = np.random.uniform(low=-1.0, high=1.0, size=(50, dim_theta))\n",
        "y_test = A_test @ theta_true + np.random.normal(loc=0.0, scale=scale, size=(50, 1))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZU_XvbFtbmTT"
      },
      "source": [
        "# Solving for the exact mean squared loss (solving Ax = b)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BmhrX7mHbmTW"
      },
      "source": [
        "print('Not implemented.')\n",
        "\n",
        "'''\n",
        "Hints:\n",
        "1. See the least squares solution to Ax = b (when it is covered in lecture).\n",
        "\n",
        "2. Use Numpy functions like Numpy's linear algebra functions to solve for x in Ax = b.\n",
        "In fact, the linear algebra module is already imported with ```import numpy.linalg as la```.\n",
        "\n",
        "3. Use the defined variable A in Ax = b. Use y_data as b. Use theta_pred as x.\n",
        "'''\n",
        "theta_pred = NotImplemented # TODO: Implement the analytical solution\n",
        "\n",
        "print('Empirical theta', theta_pred.reshape(-1))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xeV_SKF_bmTj"
      },
      "source": [
        "# SGD Variants Noisy Function"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SvwmLrlAbmTn"
      },
      "source": [
        "batch_size = 1\n",
        "max_iter = 1000\n",
        "lr = 0.001\n",
        "theta_init = np.random.random((10,1)) * 0.1"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1hVSuTZxbmT2"
      },
      "source": [
        "def noisy_val_grad(theta_hat, data_, label_, deg_=2.):\n",
        "    gradient = np.zeros_like(theta_hat)\n",
        "    loss = 0\n",
        "    \n",
        "    for i in range(data_.shape[0]):\n",
        "        x_ = data_[i, :].reshape(-1,1)\n",
        "        y_ = label_[i, 0]\n",
        "        err = np.sum(x_ * theta_hat) - y_\n",
        "        \n",
        "        print('Not implemented.')\n",
        "\n",
        "        '''\n",
        "        Hints:\n",
        "        1. Find the gradient and loss for each data point x_.\n",
        "        2. For grad, you need err, deg_, and x_.\n",
        "        3. For l, you need err and deg_ only.\n",
        "        4. Checkout the writeup for more hints.\n",
        "        '''\n",
        "        grad = NotImplemented # TODO: Implement the analytical gradient\n",
        "        l = NotImplemented # TODO: Implement the loss function\n",
        "        \n",
        "        loss += l / data_.shape[0]\n",
        "        gradient += grad / data_.shape[0]\n",
        "        \n",
        "    return loss, gradient"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B5abUl0ibmUF"
      },
      "source": [
        "# Running SGD Variants"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xybXkEd7bmUJ"
      },
      "source": [
        "#@title Parameters\n",
        "deg_ = 2. #@param {type: \"number\"}\n",
        "num_rep = 10 #@param {type: \"integer\"}\n",
        "max_iter = 1000 #@param {type: \"integer\"}\n",
        "fig, ax = plt.subplots(figsize=(10,10))\n",
        "best_vals = {}\n",
        "test_exp_interval = 50 #@param {type: \"integer\"}\n",
        "grad_artificial_normal_noise_scale = 0. #@param {type: \"number\"}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UM80QBNFbmUV"
      },
      "source": [
        "for method_idx, method in enumerate(['adam', 'sgd', 'adagrad']):\n",
        "    test_loss_mat = []\n",
        "    train_loss_mat = []\n",
        "    \n",
        "    for replicate in range(num_rep):\n",
        "        if replicate % 20 == 0:\n",
        "            print(method, replicate)\n",
        "            \n",
        "        if method == 'adam':\n",
        "            print('Adam Not implemented.')\n",
        "            beta_1 = 0.9\n",
        "            beta_2 = 0.999\n",
        "            m = NotImplemented # TODO: Initialize parameters\n",
        "            v = NotImplemented\n",
        "            epsilon = NotImplemented\n",
        "\n",
        "        if method == 'adagrad':\n",
        "            print('Adagrad Not implemented.')\n",
        "            epsilon = NotImplemented # TODO: Initialize parameters\n",
        "            squared_sum = NotImplemented\n",
        "            \n",
        "        theta_hat = theta_init.copy()\n",
        "        test_loss_list = []\n",
        "        train_loss_list = []\n",
        "\n",
        "        for t in range(max_iter):\n",
        "            idx = np.random.choice(data_num, batch_size) # Split data\n",
        "            train_loss, gradient = noisy_val_grad(theta_hat, A[idx,:], y_data[idx,:], deg_=deg_)\n",
        "            artificial_grad_noise = np.random.randn(10, 1) * grad_artificial_normal_noise_scale + np.sign(np.random.random((10, 1)) - 0.5) * 0.\n",
        "            gradient = gradient + artificial_grad_noise\n",
        "            train_loss_list.append(train_loss)\n",
        "            \n",
        "            if t % test_exp_interval == 0:\n",
        "                test_loss, _ = noisy_val_grad(theta_hat, A_test[:,:], y_test[:,:], deg_=deg_)\n",
        "                test_loss_list.append(test_loss)                \n",
        "            \n",
        "            if method == 'adam':\n",
        "                print('Adam Not implemented.') # TODO: Implement Adam\n",
        "                m = NotImplemented\n",
        "                v = NotImplemented\n",
        "                m_hat = NotImplemented\n",
        "                v_hat = NotImplemented\n",
        "                theta_hat = theta_hat - lr * NotImplemented\n",
        "            \n",
        "            elif method == 'adagrad':\n",
        "                print('Adagrad Not implemented.')\n",
        "                squared_sum = squared_sum + NotImplemented # TODO: Implement Adagrad\n",
        "                theta_hat = theta_hat - lr * NotImplemented\n",
        "            \n",
        "            elif method == 'sgd':\n",
        "                theta_hat = theta_hat - lr * gradient\n",
        "        \n",
        "        test_loss_mat.append(test_loss_list)\n",
        "        train_loss_mat.append(train_loss_list)\n",
        "        \n",
        "    print(method, 'done')\n",
        "    x_axis = np.arange(max_iter)[::test_exp_interval]\n",
        "    \n",
        "    print('test_loss_np is a 2d array with num_rep rows and each column denotes a specific update stage in training')\n",
        "    print('The elements of test_loss_np are the test loss values computed in each replicate and training stage.')\n",
        "    test_loss_np = np.array(test_loss_mat)\n",
        "    \n",
        "    print('Not implemented.')\n",
        "    '''\n",
        "    Hints:\n",
        "    1. Use test_loss_np in np.mean() with axis = 0\n",
        "    '''\n",
        "    test_loss_mean = NotImplemented # TODO: Calculate the mean test loss\n",
        "\n",
        "    '''\n",
        "    Hints:\n",
        "    1. Use test_loss_np in np.std() with axis = 0 \n",
        "    2. Divide by np.sqrt() using num_rep as a parameter\n",
        "    '''\n",
        "    test_loss_se = NotImplemented # TODO: Calculate the standard error for test loss\n",
        "\n",
        "    plt.errorbar(x_axis, test_loss_mean, yerr=2.5*test_loss_se, label=method)\n",
        "    best_vals[method] = min(test_loss_mean)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EGmQD7nDbmUg"
      },
      "source": [
        "best_vals = { k: int(v * 1000) / 1000. for k,v in best_vals.items() } # A weird way to round numbers\n",
        "plt.title(f'Test Loss \\n(objective degree: {deg_},  best values: {best_vals})')\n",
        "plt.ylabel('Test Loss')\n",
        "plt.legend()\n",
        "plt.xlabel('Updates')"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}