HW/AM207_HW6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework #6 (Due 10/21/2021, 11:59pm)\n",
    "## Descent Algorithms for Optimization\n",
    "\n",
    "**AM 207: Advanced Scientific Computing**<br>\n",
    "**Instructor: Weiwei Pan**<br>\n",
    "**Fall 2021**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Name:**\n",
    "\n",
    "**Students collaborators:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Instructions:\n",
    "\n",
    "**Submission Format:** Use this notebook as a template to complete your homework. Please intersperse text blocks (using Markdown cells) amongst `python` code and results -- format your submission for maximum readability. Your assignments will be graded for correctness as well as clarity of exposition and presentation -- a “right” answer by itself without an explanation or is presented with a difficult to follow format will receive no credit.\n",
    "\n",
    "**Code Check:** Before submitting, you must do a \"Restart and Run All\" under \"Kernel\" in the Jupyter or colab menu. Portions of your submission that contains syntactic or run-time errors will not be graded.\n",
    "\n",
    "**Libraries and packages:** Unless a problems specifically asks you to implement from scratch, you are welcomed to use any `python` library package in the standard Anaconda distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Import basic libraries\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import sklearn as sk\n",
    "from sklearn.linear_model import LinearRegression\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description: Minimizing the Cost of a Construction Project\n",
    "\n",
    "Suppose you are building a pricing model for laying down new fibre optics high-speed internet cables under region in the Boston area. Your model takes as input a pair of  coordinates, $(x, y)$, and contains two parameters, $\\lambda_1, \\lambda_2$. Given a coordinate, $(x, y)$, and model parameters, the loss in revenue corresponding to the price model at location $(x, y)$ is described by\n",
    "\n",
    "$$\n",
    "L(x, y, \\lambda_1, \\lambda_2) = 0.000045\\lambda_2^2 y - 0.000098\\lambda_1^2 x + 0.003926\\lambda_1 x\\exp\\left\\{\\left(y^2 - x^2\\right)\\left(\\lambda_1^2 + \\lambda_2^2\\right)\\right\\}\n",
    "$$\n",
    "\n",
    "Read the data contained in `HW6_data.csv`. This is a set of coordinates $\\{(x_n, y_n)\\}$ configured on the curve $y^2 - x^2 = -0.1$. In this problem, we find parameters $\\lambda_1, \\lambda_2$ that minimize the net loss over the entire dataset of coordinates $(x_n, y_n)$.\n",
    "\n",
    "### Part I: Cost minimization with descent algorithms\n",
    "\n",
    "1. (**Visualizing the Optimization Landscape**) Using level curves (see In-Class Exercise #1) and a 3D plot, visually verify that at $\\lambda_1 = 2.05384, \\lambda_2 = 0$, the loss function $L$ is globally minimized.<br><br>\n",
    "\n",
    "2. (**Gradient Descent**) Implement gradient descent for minimizing the **average** of $L$ over the locations given in the data, using the learning rate of 1.0 and initialization of $\\lambda_1 = 2, \\lambda_2 = 1$. Visually determine if your algorithm has converged. \n",
    "\n",
    "  **Hint:** You may need to visualize the behavior over the total number of iterations as well as its value over the last couple of hundreds of iterations to check for convergence.<br><br>\n",
    "\n",
    "3. (**Stochastic Gradient Descent**) Implement stochastic gradient descent for minimizing the **average** of $L$ over the locations in the mini-batch, using the learning rate of 1.0 and initialization of $\\lambda_1 = 2, \\lambda_2 = 1$ and mini-batch size of 1. Visually determine if your algorithm has converged.\n",
    "\n",
    "  **Hint:** You may need to visualize the behavior over the total number of iterations as well as its value over the last couple of hundreds of iterations to check for convergence.<br><br>\n",
    "\n",
    "4. (**How to Compare GD and SGD Fairly**) Argue that minimizing the average loss over the locations is equivalent to minimizing the net loss. However, minimizing the average loss makes it possible to compare gradient descent and stochastic gradient descent on equal terms. Explain why this is true.<br><br>\n",
    "\n",
    "5. (**Comparing the Efficiency of GD and SGD**) Compute the average time it takes to update the parameter estimation in each iteration of the two implementations. Which method is faster? Briefly explain why this result should be expected.\n",
    "\n",
    "  Compare the number of iterations it takes for each algorithm to obtain an estimate accurate to `1e-3` (in this case, you know the true global optima so you can check the norm $\\|(\\lambda_1, \\lambda_2) - (\\lambda_1^{\\text{true}}, \\lambda_2^{\\text{true}})\\|_2$ ). Which method converges to the optimal point in fewer iterations? Briefly explain why this result should be expected.<br><br>\n",
    "\n",
    "6. (**Comparing Sensitivity of GD and SGD to Learning Rate**) Compare the performance of both gradient descent methods for the following learning rates: 1000, 100, 1., 0.1. Based on your observations, briefly describe the effect of the choice of learning rate on the performance of each algorithm. In particular, which algorithm is more sensitve to the learning rate?\n",
    "\n",
    "  **Hint:** You may need to visualize the behavior over the total number of iterations as well as its value over the first and last couple of hundreds of iterations separately to isolate trends.<br><br>\n",
    "\n",
    "\n",
    "7. (**Comparing Sensitivity of GD and SGD to Initialization**) Document the behaviour of your two descent algorithms for the following starting points, and for learning rates of 10 and 50:\n",
    "  - $(\\lambda_1, \\lambda_2) = (-2.47865, 0)$\n",
    "  - $(\\lambda_1, \\lambda_2) = (-3, 0)$\n",
    "  - $(\\lambda_1, \\lambda_2) = (-5, 0)$\n",
    "  - $(\\lambda_1, \\lambda_2) = (-10, 0)$\n",
    "\n",
    "  Based on your visualization of the graph/contour map of the lost function as well as the visualization of the loss function during descent, explain what is happening to your descent algorithms for each initialization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part II: Broader Impact Analysis\n",
    "\n",
    "Starting in 2020, major machine learning conferences are beginning to ask authors as well as reviewers to explicitly consider the broader impact of new machine learning methods. To properly evaluate the potential good or harm that a piece of technology (AI or not) can do to the general public, we need to be aware that no technology is deployed in ideal conditions or in perfectly neutral contexts. In order to assess the potential broader impact of technology, we need to analyze the social systems/institutions of which these technologies will become a part.\n",
    "\n",
    "To help you analyze the broader impact of your technology, begin by considering the following questions:\n",
    "\n",
    "I. Identify the relevant socio-technical systems\n",
    "  - In what social, political, economic system could the tech be deployed?\n",
    "  - How would the tech be used in these systems (what role will it take in the decision making processes)?<br><br>\n",
    "  \n",
    "II. Identify the stakeholders\n",
    "  - Who are the users?\n",
    "  - Who are the affected communities (are these the users)?\n",
    "  \n",
    "    ***Hint:*** users are typically decision makers who will use the technology as decision aids (e.g. doctors), whereas affected communities may be folks who are impacted by these decisions but who are not represented in the decision making process (e.g. patients).<br><br>\n",
    "    \n",
    "III. What types of harm can this tech do?\n",
    "  - What kinds of failures can this tech have?\n",
    "  - What kinds of direct harm can these failures cause?\n",
    "  - What kinds of harm can the socio-technical system cause?\n",
    "  \n",
    "    ***Hint:*** many technical innovations have niche applications, they may sit in a long chain of decision making in a complex system. As such, it may seem, at first glance, that these technologies have no immediate real-life impact. In these cases, it’s helpful to think about the impact of the entire system and then think about how the proposed innovations aid, hamper or change the goals or outcomes of this system.<br><br>\n",
    "    \n",
    "IV. What types of good can this tech do?\n",
    "  - What kinds of needs do these users/communities have?\n",
    "  - What kinds of constraints do these users/communities have?\n",
    "\n",
    "1. **(Impact)** Analyze the broader impact of this pricing model. Focus on anticipating ways these models can interact with other components of the decision systems in which they will be deployed, identifying end-users, affected communities as well as anticipating the effects (positive and negative) on affected communities (in particular, does the model have the same effect on all subpopulations in the affected communities?). \n",
    "\n",
    "  ***Hint:*** the objective function we are minimizing here is the construction cost, who benifits from minimizing the this objective function, whose utility function might be in tension with this objective function?\n",
    "  \n",
    "  How do the quirks and artifacts of the optimization algorithm impact the end-user (i.e. how is your end-user affected by the optimization procedure and the hyperparameters you choose)? How do your design choices in optimization impact the affected community?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}