{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MA934 - Week 9 (assessed!) Problem Sheet\n",
    "\n",
    "## Deadline: 17:00 (UK time) on Friday 8 December \n",
    "\n",
    "For this assignment, you must create a new Jupyter notebook called MA934_Week9_UniID.ipynb to contain the implementations that you write. This should also be exported as a .pdf file such that all execution output (from data to plots) is visible as produced on your own machine. You can separate out individual tasks if you prefer, but the full submission should be made as a single .zip via [our website](/fac/sci/mathsys/courses/msc/ma934/resources/assessedwork/ma934declaration). The platform will not allow you to upload more than one file.\n",
    "\n",
    "A few tips:\n",
    "- please make sure to debug intermediate outputs as you code along. You are welcome to design smaller test cases and toy problems to verify your work (even if they are not part of the final submission).\n",
    "- consider possible forms of input or arguments and make sure your solution can cope with *interesting* cases.\n",
    "- do not forget to comment your code and use Markdown cells to explain what you are doing. A perfectly functional solution with no information about the thought process will not receive more than a subset of the points (~$70\\%$ depending on the difficulty of the problem and how transparent the algorithm flow is). \n",
    "- generally getting used to writing tidy solutions is good practice. Feel free to use [online resources](https://www.ibm.com/docs/en/watson-studio-local/1.2.3?topic=notebooks-markdown-jupyter-cheatsheet) for editing guidance.\n",
    "\n",
    "The problems below provide an opportunity to explore the gradient descent and its stochastic counterpart, putting the previously built theoretical foundation to good use. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1 - Gradient descent [60 marks]\n",
    "\n",
    "Consider the following optimisation problem in $\\mathbb{R}^n$\n",
    "\n",
    "$$\\min_{\\substack{\\mathbf{x} \\in \\mathbb{R}^n} } f(\\mathbf{x})$$\n",
    "\n",
    "where $f(\\mathbf{x})$ is the quartic function defined as\n",
    "\n",
    "$$ f(\\mathbf{x}) = \\frac{1}{4} \\left( (\\mathbf{x} - \\mathbf{x}_*)^T A\\cdot (\\mathbf{x} - \\mathbf{x}_*)\\right)^2 $$\n",
    "\n",
    "with \n",
    "\n",
    "$$ A = \\left( \n",
    "\\begin{array}{ccccc} \n",
    "\\frac{\\lambda+1}{2} & \\frac{\\lambda - 1}{2} & 0 &\\ldots & 0\\\\ \n",
    "\\frac{\\lambda-1}{2} & \\frac{\\lambda + 1}{2} & 0 &\\ldots & 0\\\\\n",
    "0 & 0 & 1 &\\ldots & 0\\\\ \n",
    "\\vdots & \\vdots & \\vdots &\\ddots & \\vdots\\\\ \n",
    "0 & 0 & 0 &\\ldots & 1\n",
    "\\end{array}\n",
    "\\right),\n",
    "$$\n",
    "$$\n",
    "\\mathbf{x}_* = \\left( \\begin{array}{c}\n",
    "\\sqrt{2}\\\\\n",
    "\\sqrt{3}\\\\\n",
    "1\\\\\n",
    "\\vdots\\\\\n",
    "1\n",
    "\\end{array}\n",
    "\\right)\n",
    "$$\n",
    "and $\\lambda > 0$ is a parameter that controls the shape of the objective function. A reasonable range of values for $\\lambda$ is $\\frac{1}{10} \\leq \\lambda \\leq 10$.\n",
    "\n",
    "* Write down the solution of this problem. [5 marks]\n",
    "* Write down the eigenvalues of the matrix $A$. [5 marks]\n",
    "* Derive a formula for the gradient, $\\nabla f(\\mathbf{x})$, at any point in $\\mathbb{R}^n$. [5 marks]\n",
    "* Use your results to implement the gradient descent algorithm in Python. Use your algorithm to numerically solve the above problem with $n=2$ and $\\lambda=2$. A good initial point is $\\mathbf{x}_0 = 5\\,\\mathbf{x}_*$.  A good tolerance is $\\varepsilon = 10\\, \\epsilon_m$. **Note:** You will need to write your own *Golden Section Search* code as part of this task, which is a small subproblem in itself. Make sure you verify your implementation with smaller datasets before deploying it within the context of the larger problem. [25 marks]\n",
    "* Plot how the distance from the minimum decreases as s function of the number of iterations and empirically determine the convergence rate of the algorithm. [10 marks]\n",
    "* Determine empirically how the number of steps required to solve the problem varies with $\\lambda$ when $n=3$. [10 marks]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2 - Stochastic gradient descent [40 marks]\n",
    "\n",
    "Consider the following linear model expressing a noisy relationship between a target variable, $y \\in \\mathbb{R}$ and a set of predictor variables, $\\mathbf{x} \\in \\mathbb{R}^n$:\n",
    "\n",
    "$$ y = \\mathbf{\\alpha}^T \\, \\mathbf{x} + \\xi $$\n",
    "\n",
    "where $\\mathbf{\\alpha} \\in \\mathbb{R}^n$ is a set of parameters and $\\xi \\sim N(0, \\sigma^2)$ is a normal random variable with mean 0 and variance $\\sigma^2$ representing the error. We are given a set of $m$ observations\n",
    "\n",
    "$$Y = \\left\\{(\\mathbf{x}^{(i)},\\, y^{(i)})\\ : i=1\\ldots m \\right\\}$$\n",
    "\n",
    "Our task is to find the \"best\" set of parameters, $\\mathbf{\\alpha}_*$ given the observations by solving the ordinary least squares problem:\n",
    "\n",
    "$$\\mathbf{\\alpha}_* = \\min_{\\substack{\\mathbf{\\alpha} \\in \\mathbb{R}^n} } F(\\mathbf{\\alpha}\\, |\\, Y)$$\n",
    "\n",
    "where\n",
    "\n",
    "$$ F(\\mathbf{\\alpha}\\, |\\, Y) = \\frac{1}{2}\\, \\frac{1}{m} \\sum_{i=1}^m\\left( y^{(i)} - \\mathbf{\\alpha}^T\\,\\mathbf{x}^{(i)}\\right)^2$$\n",
    "\n",
    "Create a test problem with the following specifications (you can of course vary the parameters):\n",
    "\n",
    "```\n",
    "n=10\n",
    "m=100\n",
    "xmax = 10.0\n",
    "sigma = 0.25\n",
    "```\n",
    "\n",
    "* Solve the problem using the gradient descent code you have written above. Due to the noise, you should not expect to recover the exact \"true\" value of $\\alpha_*$ used to generate the test data but you should be close if the noise is not too large. [15 marks]\n",
    "* Modify your code to do the optimisation using stochastic gradient descent and compare the results graphically. [15 marks]\n",
    "* Fix $n=10$ and $m=250$. Compare the performance of your stochastic gradient descent algorithm with different learning rates. Can you find one that performs well? [10 marks]\n",
    "\n",
    "**Hint:** for both Task 1 and Task 2 you may wish to consult [the provided resources](https://warwick.summon.serialssolutions.com/#!/search/document?ho=t&include.ft.matches=f&fvf=ContentType,Newspaper%20Article,t%7CContentType,Book%20Review,t&l=en-UK&q=Understanding%20Machine%20Learning:%20From%20Theory%20to%20Algorithms&id=FETCHMERGED-warwick_catalog_b279036183) on the module webpage, as well as [nicely explained tutorials](https://realpython.com/gradient-descent-algorithm-python/) on the subject matter. This will help you craft your own code and specialise it for the problems at hand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}