DLBook_ch08.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chapter 8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Optimization for Training Deep Models"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.1 How Learning Differes from Pure Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong>ML/DL Optimization </strong>: <br>\n",
    " 1. acts indirectly - reduce cost function $J(\\theta)$ to improve $P$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong>Pure Optimization</strong>: <br>\n",
    "1. acts directly - minimize $J$ is the goal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Objective function: <br>\n",
    "\n",
    "\n",
    "\\begin{equation*}\n",
    "J^{*}(\\theta) =  \\mathop{\\mathbb{E}}_{(x,y) \\sim p_{data}} L(f(x;\\theta),y)\n",
    "\\end{equation*}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.1.1 Empirical Risk Minimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above equation is known as <strong> risk </strong>\n",
    "<br> but in reality, the true underlying distribution $p_{data}$ is not known\n",
    "<br> replacing the true distribution $p(x,y)$ with empirical distribution $\\hat{p}(x,y)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong> empirical risk: </strong>\n",
    "\\begin{equation*}\n",
    "\\mathop{\\mathbb{E}}_{x,y \\sim \\hat{p}_{data}(x,y)} [L(f(x;\\theta),y)] = \\frac{1}{m} \\sum\\limits_{i=1}^m L(f(x^{(i)};\\theta), y^{(i)})\n",
    "\\end{equation*}\n",
    "where $m$ is the number of training examples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, empirical risk minimization is prone to overfitting <br>\n",
    " - models with High Capacity can simply memorize the training set\n",
    " - many useful loss functions such as 0-1 loss have no useful derivatives\n",
    "<br>$\\therefore$ emprical risk minimization is rarely used in DL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.1.2 Surrogate Loss Functions and Early Stopping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong> surrogate loss function </strong> is used as a proxy, and has advantages over the original loss function. \n",
    "<br> Negative Log-Likelihood is typically used as a surrogate for the 0-1 loss."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Important Difference between Optimization in General and Optimization in ML/DL:\n",
    "<br> ML usually minimizes a surrogate loss function but <strong> halts when a convergence criterion based on early stopping is satisfied </strong> \n",
    "<br>whereas for the pure optimization, it is considered to have converged when the <strong> gradient becomes very small </strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.1.3 Batch and Minibatch Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ML: Objective function usually decomposes as a <strong> sum over the training examples </strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For Example, MLE: <br>\n",
    "\n",
    "\\begin{equation*}\n",
    "\\theta_{ML} = arg\\max\\limits_{\\theta} \\sum\\limits_{i=1}^m log p_{model} (x^{(i)}, y^{(i)}; \\theta) \n",
    "\\end{equation*}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maximizing this sum is equivalent to maximizing the Expectation over the Empirical distribution defined by the training set: <br>\n",
    "\\begin{equation*}\n",
    "\\mathop{\\mathbb{E}}_{x,y \\sim \\hat{p}_{data}} log p_{model}(x, y; \\theta)\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most commonly used property is the gradient: <br>\n",
    "\\begin{equation*}\n",
    "\\nabla_{\\theta} \\:J(\\theta) = \\mathop{\\mathbb{E}}_{x,y \\sim \\hat{p}_{data}} \\nabla_{\\theta}\\: log\\: p_{model} (x, y; \\theta)\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Computing this expectation exactly is very expensive <br>\n",
    " - instead, compute these expectations by randomly sampling a small number of examples from the dataset, then taking the Average over only those examples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. The Standard Error of the Mean is given by: <br>\n",
    "\\begin{equation*}\n",
    "SE(\\hat{\\mu}_m) = \\sqrt{Var\\bigg[\\frac{1}{m}\\sum\\limits_{i=1}^mx^{(i)}\\bigg]} = \\frac{\\sigma}{\\sqrt{m}}\n",
    "\\end{equation*}\n",
    "<br> where $\\sigma$ is the true standard deviation of the value of the samples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The denominator of $\\sqrt{m}$ shows that there iare <strong> less than linear returns </strong> to using more examples to estimate the gradient."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. We may find large number of examples that all make very similar contributions to the gradient - <strong>redundant samples</strong>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<strong> batch / deterministic </strong>: use entire training set <br>\n",
    "<strong> online </strong>: use examples drawn from a continuous stream of new data <br>\n",
    "<strong> minibatch / stochastic </strong>: use more than one but less than all of training examples <br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "minibatch sizes are decided by following factors:\n",
    "- larger batches = more accurate estimate of gradient, but with less than linear returns\n",
    "- small batches do not utilize multi-core architectures\n",
    "- small batches can offer a regularizing effect - due to noise they add to learning process. Generalization error is often best for a batch size of 1. But learning will take more time - more steps + reduced learning rate to maintain stability due to high variance in gradient estimate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Update methods based only on the gradient $\\mathbf{g}$ are usually relatively robust and can handle smaller batch sizes like 100. <br>\n",
    "Second-order methods that compute updates such as $\\mathbf{H^{-1}g}$ typically require much larger batch sizes like 10,000. - to minimize fluctuations in the estimates of *$\\mathbf{H^{-1}g}$*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $\\mathbf H$ is poorly conditioned, very small changes in the estimate of $\\mathbf g$ can cause large changes in the update $\\mathbf H^{-1}g$, even if $\\mathbf H$ were estimated perfectly "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall from **4.2 Poor Conditioning**: <br>\n",
    "$f(x) \\; = \\; A^{-1}x $ <br>\n",
    "$A \\; \\in \\; \\mathbb{R}^{n\\times n} $ has an eigenvalue decomposition<br>\n",
    "condition number is: $\\max \\limits_{i,j}\\|\\frac{\\lambda_i}{\\lambda_j}\\|$\n",
    "<br> This is the ratio of the magnitude of the largest and smallest eigenvalue\n",
    "<br> when condition number is large, matrix inversion is particularly sensitive to error in the input\n",
    "<br> Poorly conditioned matrices amplify pre-existing erros when we multiply by the true matrix inverse."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Important to select minibatches **randomly**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.2 Challenges in Neural Network Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.2.1 Ill-Conditioning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most prominent challenge is ill-conditioning of the Hessian matrix $H$ <br>\n",
    "It can manifest by causing SGD to get 'stuck' in the sense that even very small steps increase the cost function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Newton's method is an excellent tool for minimizing convex functions with poorly conditioned Hessian matrices, but in the subsequent sections we will argue that Newton’s method requires significant modification before it can be applied to neural networks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.2.2 Local Minima"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nearly any deep model is essentially guaranteed to have an extremely large number of local minima. However, as we will see, this is not necessarily a major problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Neural networks and any models with multiple equivalently parametrized latent\n",
    "variables all have multiple local minima because of the **model identifiability**\n",
    "problem. A model is said to be identifiable if a sufficiently large training set can rule out all but one setting of the model’s parameters. Models with latent variables are often not identifiable because we can obtain equivalent models by exchanging latent variables with each other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we have m layers with n units each, then there are n ! m ways of arranging the hidden units. This kind of non-identifiability is known as **weight space symmetry.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These model identifiability issues mean that there can be an extremely large\n",
    "or even uncountably infinite amount of local minima in a neural network cost\n",
    "function. However, all of these local minima arising from non-identifiability are\n",
    "equivalent to each other in cost function value. As a result, these local minima are not a problematic form of non-convexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For sufficiently large neural networks, most local minima have a\n",
    "low cost function value, and that it is not important to find a true global minimum rather than to find a point in parameter space that has low but not minimal cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.2.3 Plateaus, Saddle Points and Other Flat Regions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For many high-dimensional non-convex functions, local minima (and maxima)\n",
    "are in fact rare compared to another kind of point with zero gradient: a **saddle\n",
    "point.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At a saddle point, the Hessian matrix has both positive and negative eigenvalues. Points lying along eigenvectors associated withpositive eigenvalues have greater cost than the saddle point, while points lying along negative eigenvalues have lower value. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In low- dimensional spaces, local minima are common. In higher dimensional spaces, local minima are rare and saddle points are more common. For a function $f : \\mathbb{R}^n → \\mathbb{R}$ of this type, the expected ratio of the number of saddle points to local minima grows exponentially with n ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand the intuition behind this behavior, observe that the Hessian matrix at a local minimum has only positive eigenvalues. The Hessian matrix at a saddle point has a mixture of positive and negative eigenvalues. Imagine that the sign of each eigenvalue is generated by flipping a coin. In a single dimension, it is easy to obtain a local minimum by tossing a coin and getting heads once. In n -dimensional space, it is exponentially unlikely that all n coin tosses willbe heads"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gradient descent is designed to move “downhill” and is not explicitly designed\n",
    "to seek a critical point. Newton’s method, however, is designed to solve for a\n",
    "point where the gradient is zero. Without appropriate modification, it can jump\n",
    "to a saddle point. The proliferation of saddle points in high dimensional spaces\n",
    "presumably explains why second-order methods have not succeeded in replacing\n",
    "gradient descent for neural network training. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dauphin et al. 2014 introduced a **saddle-free Newton method** for second-order optimization and showed that it improves significantly over the traditional version. Second-order methods remain difficult to scale to large neural networks, but this saddle-free approach holds promise if it could be scaled."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.2.4 Cliffs and Exploding Gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Neural networks with many layers often have extremely steep regions resembling\n",
    "cliffs. These result from the multiplication of several large weights together."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cliff can be dangerous whether we approach it from above or from below,\n",
    "but fortunately its most serious consequences can be avoided using the gradient\n",
    "clipping heuristic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cliff\n",
    "structures are most common in the cost functions for recurrent neural networks,\n",
    "because such models involve a multiplication of many factors, with one factor\n",
    "for each time step. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.2.5 Long-Term Dependencies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that $W$ has an eigendecomposition $W\\;=\\;Vdiag(\\lambda)V^{-1}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$W^{t}\\;=\\;(Vdiag(\\lambda)V^{-1})^{t}\\;=\\;Vdiag(\\lambda)^{t}V^{-1}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Vanishing and exploding gradient problem** refers to the fact that gradients\n",
    "through such a graph are also scaled according to diag ( λ ) t . Vanishing gradients\n",
    "make it difficult to know which direction the parameters should move to improve\n",
    "the cost function, while exploding gradients can make learning unstable. The cliff\n",
    "structures described earlier that motivate gradient clipping are an example of the\n",
    "exploding gradient phenomenon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tt is not surprising that $x^{T}W^{t}$ will eventually discard all components of **$x$** that are orthogonal to the principal eigenvector of $W$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.2.6 Inexact Gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most optimization algorithms are designed with the assumption that we have\n",
    "access to the exact gradient or Hessian matrix. In practice, we usually only have\n",
    "a noisy or even biased estimate of these quantities. Nearly every deep learning\n",
    "algorithm relies on sampling-based estimates at least insofar as using a minibatch\n",
    "of training examples to compute the gradient."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.2.7 Poor Correspondence between Local and Global Structure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.2.8 Theoretical Limits of Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Several theoretical results show that there are limits on the performance of any\n",
    "optimization algorithm we might design for neural networks (Blum and Rivest,\n",
    "1992; Judd 1989; Wolpert and MacReady 1997). Typically these results have\n",
    "little bearing on the use of neural networks in practice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.3  Basic Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.3.1 Stochastic Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**while** stopping criterion not met **do**\n",
    "> Sample minibatch \n",
    "    <br>Compute gradient estimate: $\\hat{g} \\leftarrow +\\frac{1}{m}\\nabla_\\theta \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br>Apply update: $\\theta \\leftarrow \\theta - \\epsilon\\hat{g}$  \n",
    "\n",
    "**end while**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " SGD gradient estimator introduces a source of noise (the\n",
    "random sampling of m training examples) that does not vanish even when we arrive\n",
    "at a minimum. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A sufficient condition to guarantee convergence of SGD is that"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ \\sum\\limits_{k=1}^{\\infty} \\epsilon_k = \\infty$ and,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ \\sum\\limits_{k=1}^{\\infty} \\epsilon_{k}^{2} < \\infty$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In practice, it is common to decay the learning rate linearly until iteration $\\tau$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\epsilon_k\\;=\\;(1-\\alpha)\\epsilon_0 + \\alpha\\epsilon_\\tau$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "with $\\alpha\\;=\\;\\frac{k}{\\tau}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.3.2 Momentum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**while** stopping criterion not met **do**\n",
    "> Sample minibatch \n",
    "    <br>Compute gradient estimate: $ \\hat{g} \\leftarrow +\\frac{1}{m}\\nabla_\\theta \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br> Compute velocity update: $v \\leftarrow \\alpha v - \\epsilon g$\n",
    "    <br>Apply update: $\\theta \\leftarrow \\theta + v$  \n",
    "\n",
    "**end while**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.3.3 Nesterov Momentum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**while** stopping criterion not met **do**\n",
    "> Sample minibatch \n",
    "    <br> Apply interim update: $\\tilde{\\theta} \\leftarrow \\theta + \\alpha v$\n",
    "    <br>Compute gradient estimate (at interim point): $ g \\leftarrow +\\frac{1}{m}\\nabla_\\theta \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br> Compute velocity update: $v \\leftarrow \\alpha v - \\epsilon g$\n",
    "    <br>Apply update: $\\theta \\leftarrow \\theta + v$  \n",
    "\n",
    "**end while**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.4 Parameter Initialization Strategies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Glorot and Bengio\n",
    "(2010) suggest using the **normalized initialization**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$W_{i,j} \\sim U \\bigg(-\\sqrt{\\frac{6}{m+n}},\\sqrt{\\frac{6}{m+n}}\\bigg)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.5 Algorithms with Adaptive Learning Rates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.5.1 AdaGrad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**while** stopping criterion not met **do**\n",
    "> Sample minibatch \n",
    "    <br>Compute gradient: $ g \\leftarrow \\frac{1}{m}\\nabla_\\theta \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br>Accumulate squared gradient: $r \\leftarrow r + g \\odot g $\n",
    "    <br> Compute update: $\\varDelta\\theta \\leftarrow - \\frac{\\epsilon}{\\delta + \\sqrt{r}} \\odot g$\n",
    "    <br>Apply update: $\\theta \\leftarrow \\theta + \\varDelta\\theta$  \n",
    "\n",
    "**end while**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.5.2 RMSProp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**while** stopping criterion not met **do**\n",
    "> Sample minibatch \n",
    "    <br>Compute gradient: $ g \\leftarrow \\frac{1}{m}\\nabla_\\theta \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br>Accumulate squared gradient: $r \\leftarrow \\rho r + (1-\\rho)g \\odot g $\n",
    "    <br> Compute update: $\\varDelta\\theta \\leftarrow - \\frac{\\epsilon}{\\sqrt{\\delta+r}} \\odot g$ \n",
    "    <br>Apply update: $\\theta \\leftarrow \\theta + \\varDelta\\theta$  \n",
    "\n",
    "**end while**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.5.3 Adam"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**while** stopping criterion not met **do**\n",
    "> Sample minibatch \n",
    "    <br>Compute gradient: $ g \\leftarrow \\frac{1}{m}\\nabla_\\theta \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br>$t \\leftarrow t + 1 $\n",
    "    <br>Update biased first moment estimate: $s \\leftarrow \\rho_1 s + (1-\\rho_1)g$\n",
    "    <br>Update biased second moment estimate: $r \\leftarrow \\rho_2 r + (1-\\rho_2)g\\odot g$\n",
    "    <br> Correct bias in first moment: $\\hat{s} \\leftarrow \\frac{s}{1-\\rho_1^t}$\n",
    "    <br> Correct bias in second moment: $\\hat{r} \\leftarrow \\frac{r}{1-\\rho_2^t}$\n",
    "    <br> Compute update: $\\varDelta\\theta \\leftarrow - \\epsilon \\frac{\\hat{s}}{\\sqrt{\\hat{r}} + \\delta}$ \n",
    "    <br>Apply update: $\\theta \\leftarrow \\theta + \\varDelta\\theta$  \n",
    "\n",
    "**end while**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.6 Approximate Second-Order Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Empirical Risk:<br>\n",
    "$J(\\theta) = \\mathbb{E}_{x,y\\sim\\hat{p}_data (x,y)} [L(f(x;\\theta),y)] = \\frac{1}{m}\\sum\\limits_{i=1}^{m}L(f(x^{(i)};\\theta),y^{(i)})\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.6.1 Newton's Method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In contrast to first-order methods, second-order methods make use of second derivatives to improve optimization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Newton’s method is an optimization scheme based on using a second-order Tay-\n",
    "lor series expansion to approximate $J(\\theta)$ near some point $\\theta_0$ , ignoring derivatives of higher order:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\n",
    "J(\\theta) \\approx J(\\theta_0) + (\\theta - \\theta_0)^{T}\\nabla_\\theta J(\\theta_0) + \\frac{1}{2}(\\theta - \\theta_0)^{T} H (\\theta - \\theta_0)\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solve for the critical point of this function, we obtain the **Newton parameter update rule:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\n",
    "    \\theta^{*} = \\theta_0 - H^{-1}\\nabla_\\theta J(\\theta_0)\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus for a locally quadratic function (with positive definite $H$), by rescaling\n",
    "the gradient by $H^{−1}$ , Newton’s method jumps directly to the minimum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**while** stopping criterion not met **do**\n",
    "> Compute gradient: $ g \\leftarrow \\frac{1}{m}\\nabla_\\theta \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br>Compute Hessian: $ H \\leftarrow \\frac{1}{m}\\nabla_\\theta^2 \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br>Compute Hessian Inverse: $H^{-1}$\n",
    "    <br>Compute update: $\\varDelta\\theta = -H^{-1}g$\n",
    "    <br>Apply update: $\\theta = \\theta + \\varDelta\\theta$  \n",
    "\n",
    "**end while**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Common regularization strategies include adding a constant, $\\alpha$ along the diagonal of the Hessian. The regularized update becomes:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\n",
    "    \\theta^* = \\theta_0 - [H(f(\\theta_0)) + \\alpha I]^{-1} \\nabla_\\theta f(\\theta_0)\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " application of Newton’s method for training large neural\n",
    "networks is limited by the significant computational burden it imposes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of elements in the Hessian is squared in the number of parameters, so with k parameters, Newton’s method would require the inversion of a k k ×\n",
    "matrix—with computational complexity of $O(k^3)$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, since the parameters will change with every update, the inverse Hessian has to be computed at *every training iteration*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.6.2 Conjugate Gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Conjugate gradients is a method to efficiently avoid the calculation of the inverse Hessian by iteratively descending conjugate directions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " we seek to find a search direction that is conjugate to the previous line search direction, i.e. it will not undo progress made in that direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " By definition, at\n",
    "the minimum of the objective along a given direction, the gradient at the final point is\n",
    "orthogonal to that direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "at training iteration $t$, the next search direction $d_t$ takes the form:\n",
    "<br>\n",
    "$d_t = \\nabla_\\theta J(\\theta) + \\beta_t d_{t-1}$\n",
    "<br>where $\\beta_t$ is a coefficient whose magnitude controls how much of the direction, $d_{t-1}$ we should add back to the current search direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Two directions, $d_t$ and $d_{t−1}$ , are defined as conjugate if $d_t^T H d_{t-1} = 0$, where $H$ is the Hessian matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The straightforward way to impose conjugacy would involve calculation of the\n",
    "eigenvectors of $H$ to choose $\\beta_t$, which would not satisfy our goal of developing a method that is more computationally viable than Newton’s method for large problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Two popular methods for computing the $\\beta_t$ are:\n",
    "<br>\n",
    "1. Fletcher-Reeves:<br>\n",
    " $\\beta_t = \\ \\cfrac{\\nabla_\\theta J(\\theta_t)^T \\nabla_\\theta J(\\theta_t)}\n",
    " {\\nabla_\\theta J(\\theta_{t-1})^T \\nabla_\\theta J(\\theta_{t-1}}$\n",
    "<br> <br>\n",
    "2. Polak-Ribeiere:<br>\n",
    " $\\beta_t = \\ \\cfrac{(\\nabla_\\theta J(\\theta_t) - \\nabla_\\theta J(\\theta_{t-1}))^T \\nabla_\\theta J(\\theta_t)}\n",
    " {\\nabla_\\theta J(\\theta_{t-1})^T \\nabla_\\theta J(\\theta_{t-1}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The conjugate gradient method**\n",
    "\n",
    "**while** stopping criterion not met **do**\n",
    "\n",
    ">Initialize the gradient $g_t = 0$ \n",
    "    <br>Compute gradient: $ g_t \\leftarrow \\frac{1}{m}\\nabla_\\theta \\Sigma_{i} L(f(x^{(i)};\\theta), y^{(i)}) $\n",
    "    <br>Compute $\\beta_t = \\cfrac{(g_t - g_{t-1})^T g_t}{g_{t-1}^T g_{t-1}} $\n",
    "    <br>Compute search direction: $ \\rho_t = -g_t + \\beta_t \\rho_{t-1} $\n",
    "    <br> Perform line search to find: $ \\epsilon^* = argmin_\\epsilon \\frac{1}{m} \\sum\\limits_{i=1}^{m}L(f(x^{(i)};\\theta_t + \\epsilon \\rho_t), y^{(i)}) $\n",
    "    <br>Apply update: $\\theta_{t+1} = \\theta_t + \\epsilon^* \\rho_t$\n",
    "    <br>$t \\leftarrow t + 1 $\n",
    "\n",
    "**end while**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Nonlinear Conjugate Gradients:** <br>\n",
    "Without any assurance that the objective is quadratic, the conjugate directions are no longer assured to remain at the minimum of the objective for previous\n",
    "directions. As a result, the nonlinear conjugate gradients algorithm includes\n",
    "occasional resets where the method of conjugate gradients is restarted with line\n",
    "search along the unaltered gradient."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.6.3 BFGS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Broyden-Fletcher-Goldfarb-Shanno**  algorithm attempts to\n",
    "bring some of the advantages of Newton’s method without the computational\n",
    "burden. In that respect, BFGS is similar to the conjugate gradient method.\n",
    "However, BFGS takes a more direct approach to the approximation of Newton’s\n",
    "update"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The approach adopted by quasi-Newton methods (of which\n",
    "the BFGS algorithm is the most prominent) is to approximate the inverse with\n",
    "a matrix $M_t$ that is iteratively refined by low rank updates to become a better\n",
    "approximation of $H^{-1}$ ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once the inverse Hessian approximation $M_t$ is updated, the direction of descent $\\rho_t$ is determined by $\\rho_t = M_t g_t$.  A line search is performed in this direction to determine the size of the step, $\\epsilon^*$ , taken in this direction. The final update to the parameters is given by: <br>\n",
    "$\\theta_{t+1} = \\theta_t + \\epsilon^* \\rho_t$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unlike conjugate gradients, the success of the approach is not heavily dependent\n",
    "on the line search finding a point very close to the true minimum along the line.\n",
    "Thus, relative to conjugate gradients, BFGS has the **advantage** that it can spend **less time refining each line search**. On the other hand, the BFGS algorithm must **store the inverse Hessian matrix, $M$ , that requires $O(n^2)$ memory,** making BFGS\n",
    "impractical for most modern deep learning models that typically have millions of\n",
    "parameters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " The L-BFGS algorithm computes the approximation $M$ using the same method as the BFGS algorithm, but beginning with the assumption that $M^{(t−1)}$ is the identity matrix, rather than storing the approximation from one step to the next."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The L-BFGS strategy with no storage described here can be\n",
    "generalized to include more information about the Hessian by storing some of the\n",
    "vectors used to update $M$ at each time step, which costs only $O(n)$per step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.7 Optimization Strategies and Meta-Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.7.1 Batch Normalization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Batch normalization (Ioffe and Szegedy 2015) is one of the most exciting recent \n",
    "innovations in optimizing deep neural networks and it is actually **not an optimization algorithm at all**. Instead, it is a method of **adaptive reparametrization**, motivated by the difficulty of training very deep models."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Very deep models involve the composition of several functions or layers. The\n",
    "gradient tells how to update each parameter, under the assumption that the other\n",
    "layers do not change. In practice, we update all of the layers simultaneously."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " This makes it very hard to choose an appropriate learning rate, because the effects of an update to the parameters for one layer depends so strongly on all of the other layers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Batch normalization provides an elegant way of reparametrizing almost any deep\n",
    "network. The reparametrization significantly reduces the problem of coordinating\n",
    "updates across many layers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $H$ be a minibatch of activations of the layer\n",
    "to normalize, arranged as a design matrix, with the activations for each example\n",
    "appearing in a row of the matrix. To normalize $H$ , we replace it with: <br>\n",
    "$H' = \\cfrac{H - \\mu}{\\sigma}$\n",
    "<br>where $\\mu$ is  a vector containing the mean of each unit and $\\sigma$ is a vector containing the standard deviation of each unit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At training time, <br>\n",
    "$\\mu = \\cfrac{1}{m} \\sum\\limits_{i}H_{i,:}$ <br>\n",
    "and <br>\n",
    "$\\sigma = \\sqrt{\\delta + \\cfrac{1}{m}\\sum\\limits_{i} (H - \\mu)_i^2}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Crucially, **we back-propagate through\n",
    "these operations** for computing the mean and the standard deviation, and for\n",
    "applying them to normalize H . This means that the gradient will never propose\n",
    "an operation that acts simply to increase the standard deviation or mean of\n",
    "h i ; the normalization operations remove the effect of such an action and zero\n",
    "out its component in the gradient. This was a major innovation of the batch\n",
    "normalization approach."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At test time,$\\mu$ and $\\sigma$ may be replaced by running averages that were collected during training time. This allows the model to be evaluated on a single example, without needing to use definitions of $\\mu$ and $\\sigma$ that depend on an entire minibatch."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Batch normalization acts to\n",
    "standardize only the mean and variance of each unit in order to stabilize learning,\n",
    "but allows the relationships between units and the nonlinear statistics of a single\n",
    "unit to change."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Normalizing the mean and standard deviation of a unit can reduce the expressive\n",
    "power of the neural network containing that unit. In order to maintain the\n",
    "expressive power of the network, it is common to replace the batch of hidden unit\n",
    "activations $H$ with $\\gamma H' + \\beta$ rather than simply the normalized $H'$ The variables $\\gamma$ and $\\beta$ are learned parameters that allow the new variable to have any mean and standard deviation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " new parametrization can represent\n",
    "the same family of functions of the input as the old parametrization, but the new\n",
    "parametrization has different **learning dynamics.** <br>\n",
    " In the new parametrization, the mean of $\\gamma H' + \\beta$ is\n",
    "determined solely by $\\beta$ . The new parametrization is much easier to learn with\n",
    "gradient descent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.7.2 Coordinate Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we minimize $f(x)$ with respect to a single variable $x_i$, then minimize it with respect to another variable $x_j$ and so on,\n",
    "repeatedly cycling through all variables, we are guaranteed to arrive at a (local) minimum. This practice is known as **coordinate descent** , because we optimize one coordinate at a time. More generally, **block coordinate descent** refers to\n",
    "minimizing with respect to a subset of the variables simultaneously"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coordinate descent makes the most sense when the different variables in the\n",
    "optimization problem can be clearly separated into groups that play relatively\n",
    "isolated roles, or when optimization with respect to one group of variables is\n",
    "significantly more efficient than optimization with respect to all of the variables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Coordinate descent is not a very good strategy when the value of one variable\n",
    "strongly influences the optimal value of another variable, as in the function $f(x) = (x_1 - x_2)^2 + \\alpha(x_1^2+x_2^2)$ where $\\alpha$ is a positive constant.  The first term encourages\n",
    "the two variables to have similar value, while the second term encourages them\n",
    "to be near zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.7.3 Polyak Averaging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Polyak averaging (Polyak and Juditsky 1992) consists of averaging together several\n",
    "points in the trajectory through parameter space visited by an optimization\n",
    "algorithm. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "if $t$ iterations of gradient descent visit points $\\theta^{(1)},...,\\theta^{(t)}$, then the output of the Polyak averaging algorithm is $\\hat{\\theta}^{(t)} = \\frac{1}{t}\\sum_i \\theta^{(i)}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The basic idea is that the\n",
    "optimization algorithm may leap back and forth across a valley several times\n",
    "without ever visiting a point near the bottom of the valley. The average of all of\n",
    "the locations on either side should be close to the bottom of the valley though."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "when applying Polyak averaging to **non-convex** problems, it is typical to use an exponentially decaying running average: <br>\n",
    "$\n",
    "    \\hat{\\theta}^{(t)} = \\alpha \\hat{\\theta}^{(t-1)} + (1-\\alpha)\\theta^{(t)}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.7.4 Supervised Pretraining"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.7.5 Designing Models to Aid Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 8.7.6 Continuation Methods and Curriculum Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}