chapter_optimization/momentum.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Momentum\n",
    ":label:`sec_momentum`\n",
    "\n",
    "In :numref:`sec_sgd` we reviewed what happens when performing stochastic gradient descent, i.e., when performing optimization where only a noisy variant of the gradient is available. In particular, we noticed that for noisy gradients we need to be extra cautious when it comes to choosing the learning rate in the face of noise. If we decrease it too rapidly, convergence stalls. If we are too lenient, we fail to converge to a good enough solution since noise keeps on driving us away from optimality.\n",
    "\n",
    "## Basics\n",
    "\n",
    "In this section, we will explore more effective optimization algorithms, especially for certain types of optimization problems that are common in practice.\n",
    "\n",
    "\n",
    "### Leaky Averages\n",
    "\n",
    "The previous section saw us discussing minibatch SGD as a means for accelerating computation. It also had the nice side-effect that averaging gradients reduced the amount of variance.\n",
    "\n",
    "$$\\mathbf{g}_t = \\partial_{\\mathbf{w}} \\frac{1}{|\\mathcal{B}_t|} \\sum_{i \\in \\mathcal{B}_t} f(\\mathbf{x}_{i}, \\mathbf{w}_{t-1}) = \\frac{1}{|\\mathcal{B}_t|} \\sum_{i \\in \\mathcal{B}_t} \\mathbf{g}_{i, t-1}.\n",
    "$$\n",
    "\n",
    "Here we used $\\mathbf{g}_{ii} = \\partial_{\\mathbf{w}} f(\\mathbf{x}_i, \\mathbf{w}_t)$ to keep the notation simple.\n",
    "It would be nice if we could benefit from the effect of variance reduction even beyond averaging gradients on a mini-batch. One option to accomplish this task is to replace the gradient computation by a \"leaky average\":\n",
    "\n",
    "$$\\mathbf{v}_t = \\beta \\mathbf{v}_{t-1} + \\mathbf{g}_{t, t-1}$$\n",
    "\n",
    "for some $\\beta \\in (0, 1)$. This effectively replaces the instantaneous gradient by one that's been averaged over multiple *past* gradients. $\\mathbf{v}$ is called *momentum*. It accumulates past gradients similar to how a heavy ball rolling down the objective function landscape integrates over past forces. To see what is happening in more detail let us expand $\\mathbf{v}_t$ recursively into\n",
    "\n",
    "$$\\begin{aligned}\n",
    "\\mathbf{v}_t = \\beta^2 \\mathbf{v}_{t-2} + \\beta \\mathbf{g}_{t-1, t-2} + \\mathbf{g}_{t, t-1}\n",
    "= \\ldots, = \\sum_{\\tau = 0}^{t-1} \\beta^{\\tau} \\mathbf{g}_{t-\\tau, t-\\tau-1}.\n",
    "\\end{aligned}$$\n",
    "\n",
    "Large $\\beta$ amounts to a long-range average, whereas small $\\beta$ amounts to only a slight correction relative to a gradient method. The new gradient replacement no longer points into the direction of steepest descent on a particular instance any longer but rather in the direction of a weighted average of past gradients. This allows us to realize most of the benefits of averaging over a batch without the cost of actually computing the gradients on it. We will revisit this averaging procedure in more detail later.\n",
    "\n",
    "The above reasoning formed the basis for what is now known as *accelerated* gradient methods, such as gradients with momentum. They enjoy the additional benefit of being much more effective in cases where the optimization problem is ill-conditioned (i.e., where there are some directions where progress is much slower than in others, resembling a narrow canyon). Furthermore, they allow us to average over subsequent gradients to obtain more stable directions of descent. Indeed, the aspect of acceleration even for noise-free convex problems is one of the key reasons why momentum works and why it works so well.\n",
    "\n",
    "As one would expect, due to its efficacy momentum is a well-studied subject in optimization for deep learning and beyond. See e.g., the beautiful [expository article](https://distill.pub/2017/momentum/) by :cite:`Goh.2017` for an in-depth analysis and interactive animation. It was proposed by :cite:`Polyak.1964`. :cite:`Nesterov.2018` has a detailed theoretical discussion in the context of convex optimization. Momentum in deep learning has been known to be beneficial for a long time. See e.g., the discussion by :cite:`Sutskever.Martens.Dahl.ea.2013` for details.\n",
    "\n",
    "### An Ill-conditioned Problem\n",
    "\n",
    "To get a better understanding of the geometric properties of the momentum method we revisit gradient descent, albeit with a significantly less pleasant objective function. Recall that in :numref:`sec_gd` we used $f(\\mathbf{x}) = x_1^2 + 2 x_2^2$, i.e., a moderately distorted ellipsoid objective. We distort this function further by stretching it out in the $x_1$ direction via\n",
    "\n",
    "$$f(\\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2.$$\n",
    "\n",
    "As before $f$ has its minimum at $(0, 0)$. This function is *very* flat in the direction of $x_1$. Let us see what happens when we perform gradient descent as before on this new function. We pick a learning rate of $0.4$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%mavenRepo snapshots https://oss.sonatype.org/content/repositories/snapshots/\n",
    "\n",
    "%maven ai.djl:api:0.7.0-SNAPSHOT\n",
    "%maven ai.djl:basicdataset:0.7.0-SNAPSHOT\n",
    "%maven org.slf4j:slf4j-api:1.7.26\n",
    "%maven org.slf4j:slf4j-simple:1.7.26\n",
    "\n",
    "%maven ai.djl.mxnet:mxnet-engine:0.7.0-SNAPSHOT\n",
    "%maven ai.djl.mxnet:mxnet-native-auto:1.7.0-a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load ../utils/plot-utils\n",
    "%load ../utils/Functions.java\n",
    "%load ../utils/GradDescUtils.java\n",
    "%load ../utils/Accumulator.java\n",
    "%load ../utils/StopWatch.java\n",
    "%load ../utils/Training.java\n",
    "%load ../utils/TrainingChapter11.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ai.djl.ndarray.*;\n",
    "import ai.djl.ndarray.types.*;\n",
    "import ai.djl.Device;\n",
    "import ai.djl.training.optimizer.Optimizer;\n",
    "import ai.djl.training.tracker.Tracker;\n",
    "import ai.djl.ndarray.index.NDIndex;\n",
    "\n",
    "import java.io.IOException;\n",
    "import ai.djl.translate.TranslateException;\n",
    "import org.apache.commons.lang3.ArrayUtils;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "float eta = 0.4f;\n",
    "BiFunction<Float, Float, Float> f2d = (x1, x2) -> 0.1f * x1 * x1 + 2 * x2 * x2;\n",
    "\n",
    "Function<Float[], Float[]> gd2d = (state) -> {\n",
    "    Float x1 = state[0], x2 = state[1], s1 = state[2], s2 = state[3];\n",
    "    return new Float[]{x1 - eta * 0.2f * x1, x2 - eta * 4 * x2, 0f, 0f};\n",
    "};\n",
    "\n",
    "GradDescUtils.showTrace2d(f2d, GradDescUtils.train2d(gd2d, 20));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Ellipsoid with Flat x1.](https://d2l-java-resources.s3.amazonaws.com/img/gd_flatx1.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By construction, the gradient in the $x_2$ direction is *much* higher and changes much more rapidly than in the horizontal $x_1$ direction. Thus we are stuck between two undesirable choices: if we pick a small learning rate we ensure that the solution does not diverge in the $x_2$ direction but we are saddled with slow convergence in the $x_1$ direction. Conversely, with a large learning rate we progress rapidly in the $x_1$ direction but diverge in $x_2$. The example below illustrates what happens even after a slight increase in learning rate from $0.4$ to $0.6$. Convergence in the $x_1$ direction improves but the overall solution quality is much worse."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "4"
    }
   },
   "outputs": [],
   "source": [
    "float eta = 0.6f;\n",
    "GradDescUtils.showTrace2d(f2d, GradDescUtils.train2d(gd2d, 20));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Ellipsoid with Flat x1 with Large Learning Rate.](https://d2l-java-resources.s3.amazonaws.com/img/gd_flatx1_large_lr.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Momentum Method\n",
    "\n",
    "The momentum method allows us to solve the gradient descent problem described\n",
    "above. Looking at the optimization trace above we might intuit that averaging gradients over the past would work well. After all, in the $x_1$ direction this will aggregate well-aligned gradients, thus increasing the distance we cover with every step. Conversely, in the $x_2$ direction where gradients oscillate, an aggregate gradient will reduce step size due to oscillations that cancel each other out.\n",
    "Using $\\mathbf{v}_t$ instead of the gradient $\\mathbf{g}_t$ yields the following update equations:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\mathbf{v}_t &\\leftarrow \\beta \\mathbf{v}_{t-1} + \\mathbf{g}_{t, t-1}, \\\\\n",
    "\\mathbf{x}_t &\\leftarrow \\mathbf{x}_{t-1} - \\eta_t \\mathbf{v}_t.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Note that for $\\beta = 0$ we recover regular gradient descent. Before delving deeper into the mathematical properties let us have a quick look at how the algorithm behaves in practice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "float eta = 0.6f;\n",
    "float beta = 0.5f;\n",
    "\n",
    "Function<Float[], Float[]> momentum2d = (state) -> {\n",
    "    Float x1 = state[0], x2 = state[1], v1 = state[2], v2 = state[3];\n",
    "    v1 = beta * v1 + 0.2f * x1;\n",
    "    v2 = beta * v2 + 4 * x2;\n",
    "    return new Float[]{x1 - eta * v1, x2 - eta * v2, v1, v2};\n",
    "};\n",
    "\n",
    "GradDescUtils.showTrace2d(f2d, GradDescUtils.train2d(momentum2d, 20));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Contour Momentum.](https://d2l-java-resources.s3.amazonaws.com/img/contour_gd_mom.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, even with the same learning rate that we used before, momentum still converges well. Let us see what happens when we decrease the momentum parameter. Halving it to $\\beta = 0.25$ leads to a trajectory that barely converges at all. Nonetheless, it is a lot better than without momentum (when the solution diverges)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "11"
    }
   },
   "outputs": [],
   "source": [
    "eta = 0.6f;\n",
    "beta = 0.25f;\n",
    "GradDescUtils.showTrace2d(f2d, GradDescUtils.train2d(momentum2d, 20));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Contour Momentum Less.](https://d2l-java-resources.s3.amazonaws.com/img/contour_gd_mom_less.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that we can combine momentum with SGD and in particular, minibatch-SGD. The only change is that in that case we replace the gradients $\\mathbf{g}_{t, t-1}$ with $\\mathbf{g}_t$. Last, for convenience we initialize $\\mathbf{v}_0 = 0$ at time $t=0$. Let us look at what leaky averaging actually does to the updates.\n",
    "\n",
    "### Effective Sample Weight\n",
    "\n",
    "Recall that $\\mathbf{v}_t = \\sum_{\\tau = 0}^{t-1} \\beta^{\\tau} \\mathbf{g}_{t-\\tau, t-\\tau-1}$. In the limit the terms add up to $\\sum_{\\tau=0}^\\infty \\beta^\\tau = \\frac{1}{1-\\beta}$. In other words, rather than taking a step of size $\\eta$ in GD or SGD we take a step of size $\\frac{\\eta}{1-\\beta}$ while at the same time, dealing with a potentially much better behaved descent direction. These are two benefits in one. To illustrate how weighting behaves for different choices of $\\beta$ consider the diagram below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/* Saved in GradDescUtils.java */\n",
    "public static Figure plotGammas(float[] time, float[] gammas,\n",
    "                              int width, int height) {\n",
    "    double[] gamma1 = new double[time.length];\n",
    "    double[] gamma2 = new double[time.length];\n",
    "    double[] gamma3 = new double[time.length];\n",
    "    double[] gamma4 = new double[time.length];\n",
    "\n",
    "    // Calculate all gammas over time\n",
    "    for (int i = 0; i < time.length; i++) {\n",
    "        gamma1[i] = Math.pow(gammas[0], i);\n",
    "        gamma2[i] = Math.pow(gammas[1], i);\n",
    "        gamma3[i] = Math.pow(gammas[2], i);\n",
    "        gamma4[i] = Math.pow(gammas[3], i);\n",
    "    }\n",
    "\n",
    "    // Gamma 1 Line\n",
    "    ScatterTrace gamma1trace = ScatterTrace.builder(Functions.floatToDoubleArray(time),\n",
    "            gamma1)\n",
    "            .mode(ScatterTrace.Mode.LINE)\n",
    "            .name(String.format(\"gamma = %.2f\", gammas[0]))\n",
    "            .build();\n",
    "\n",
    "    // Gamma 2 Line\n",
    "    ScatterTrace gamma2trace = ScatterTrace.builder(Functions.floatToDoubleArray(time),\n",
    "            gamma2)\n",
    "            .mode(ScatterTrace.Mode.LINE)\n",
    "            .name(String.format(\"gamma = %.2f\", gammas[1]))\n",
    "            .build();\n",
    "\n",
    "    // Gamma 3 Line\n",
    "    ScatterTrace gamma3trace = ScatterTrace.builder(Functions.floatToDoubleArray(time),\n",
    "            gamma3)\n",
    "            .mode(ScatterTrace.Mode.LINE)\n",
    "            .name(String.format(\"gamma = %.2f\", gammas[2]))\n",
    "            .build();\n",
    "\n",
    "    // Gamma 4 Line\n",
    "    ScatterTrace gamma4trace = ScatterTrace.builder(Functions.floatToDoubleArray(time),\n",
    "            gamma4)\n",
    "            .mode(ScatterTrace.Mode.LINE)\n",
    "            .name(String.format(\"gamma = %.2f\", gammas[3]))\n",
    "            .build();\n",
    "\n",
    "    Axis xAxis = Axis.builder()\n",
    "            .title(\"time\")\n",
    "            .build();\n",
    "\n",
    "    Layout layout = Layout.builder()\n",
    "            .height(height)\n",
    "            .width(width)\n",
    "            .xAxis(xAxis)\n",
    "            .build();\n",
    "\n",
    "    return new Figure(layout, gamma1trace, gamma2trace, gamma3trace, gamma4trace);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NDManager manager = NDManager.newBaseManager();\n",
    "\n",
    "float[] gammas = new float[]{0.95f, 0.9f, 0.6f, 0f};\n",
    "\n",
    "NDArray timesND = manager.arange(40f);\n",
    "float[] times = timesND.toFloatArray();\n",
    "display(plotGammas(times, gammas, 600, 400));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Practical Experiments\n",
    "\n",
    "Let us see how momentum works in practice, i.e., when used within the context of a proper optimizer. For this we need a somewhat more scalable implementation.\n",
    "\n",
    "### Implementation from Scratch\n",
    "\n",
    "Compared with (minibatch) SGD the momentum method needs to maintain a set of  auxiliary variables, i.e., velocity. It has the same shape as the gradients (and variables of the optimization problem). In the implementation below we call these variables `states`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NDList initMomentumStates(int featureDim) {\n",
    "    NDManager manager = NDManager.newBaseManager();\n",
    "    NDArray vW = manager.zeros(new Shape(featureDim, 1));\n",
    "    NDArray vB = manager.zeros(new Shape(1));\n",
    "    return new NDList(vW, vB);\n",
    "}\n",
    "\n",
    "public class Optimization {\n",
    "    public static void sgdMomentum(NDList params, NDList states, Map<String, Float> hyperparams) {\n",
    "        for (int i = 0; i < params.size(); i++) {\n",
    "            NDArray param = params.get(i);\n",
    "            NDArray velocity = states.get(i);\n",
    "            // Update param\n",
    "            velocity.muli(hyperparams.get(\"momentum\")).addi(param.getGradient());\n",
    "            param.subi(velocity.mul(hyperparams.get(\"lr\")));\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us see how this works in practice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "AirfoilRandomAccess airfoil = TrainingChapter11.getDataCh11(10, 1500);\n",
    "\n",
    "public TrainingChapter11.LossTime trainMomentum(float lr, float momentum, int numEpochs) \n",
    "    throws IOException, TranslateException {\n",
    "    int featureDim = airfoil.getFeatureArraySize();\n",
    "    Map<String, Float> hyperparams = new HashMap<>();\n",
    "    hyperparams.put(\"lr\", lr);\n",
    "    hyperparams.put(\"momentum\", momentum);\n",
    "    return TrainingChapter11.trainCh11(Optimization::sgdMomentum, initMomentumStates(featureDim), hyperparams, airfoil, featureDim, numEpochs);\n",
    "}\n",
    "\n",
    "trainMomentum(0.02f, 0.5f, 2);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we increase the momentum hyperparameter `momentum` to 0.9, it amounts to a significantly larger effective sample size of $\\frac{1}{1 - 0.9} = 10$. We reduce the learning rate slightly to $0.01$ to keep matters under control."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trainMomentum(0.01f, 0.9f, 2);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reducing the learning rate further addresses any issue of non-smooth optimization problems. Setting it to $0.005$ yields good convergence properties."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "trainMomentum(0.005f, 0.9f, 2);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Concise Implementation\n",
    "\n",
    "There is very little to do in DJL since the standard `Sgd` solver already had momentum built in. Setting matching parameters yields a very similar trajectory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Tracker lrt = Tracker.fixed(0.005f);\n",
    "Optimizer sgd = Optimizer.sgd().setLearningRateTracker(lrt).optMomentum(0.9f).build();\n",
    "\n",
    "TrainingChapter11.trainConciseCh11(sgd, airfoil, 2);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Theoretical Analysis\n",
    "\n",
    "So far the 2D example of $f(x) = 0.1 x_1^2 + 2 x_2^2$ seemed rather contrived. We will now see that this is actually quite representative of the types of problem one might encounter, at least in the case of minimizing convex quadratic objective functions.\n",
    "\n",
    "### Quadratic Convex Functions\n",
    "\n",
    "Consider the function\n",
    "\n",
    "$$h(\\mathbf{x}) = \\frac{1}{2} \\mathbf{x}^\\top \\mathbf{Q} \\mathbf{x} + \\mathbf{x}^\\top \\mathbf{c} + b.$$\n",
    "\n",
    "This is a general quadratic function. For positive semidefinite matrices $\\mathbf{Q} \\succ 0$, i.e., for matrices with positive eigenvalues this has a minimizer at $\\mathbf{x}^* = -\\mathbf{Q}^{-1} \\mathbf{c}$ with minimum value $b - \\frac{1}{2} \\mathbf{c}^\\top \\mathbf{Q}^{-1} \\mathbf{c}$. Hence we can rewrite $h$ as\n",
    "\n",
    "$$h(\\mathbf{x}) = \\frac{1}{2} (\\mathbf{x} - \\mathbf{Q}^{-1} \\mathbf{c})^\\top \\mathbf{Q} (\\mathbf{x} - \\mathbf{Q}^{-1} \\mathbf{c}) + b - \\frac{1}{2} \\mathbf{c}^\\top \\mathbf{Q}^{-1} \\mathbf{c}.$$\n",
    "\n",
    "The gradient is given by $\\partial_{\\mathbf{x}} f(\\mathbf{x}) = \\mathbf{Q} (\\mathbf{x} - \\mathbf{Q}^{-1} \\mathbf{c})$. That is, it is given by the distance between $\\mathbf{x}$ and the minimizer, multiplied by $\\mathbf{Q}$. Consequently also the momentum  is a linear combination of terms $\\mathbf{Q} (\\mathbf{x}_t - \\mathbf{Q}^{-1} \\mathbf{c})$.\n",
    "\n",
    "Since $\\mathbf{Q}$ is positive definite it can be decomposed into its eigensystem via $\\mathbf{Q} = \\mathbf{O}^\\top \\boldsymbol{\\Lambda} \\mathbf{O}$ for an orthogonal (rotation) matrix $\\mathbf{O}$ and a diagonal matrix $\\boldsymbol{\\Lambda}$ of positive eigenvalues. This allows us to perform a change of variables from $\\mathbf{x}$ to $\\mathbf{z} := \\mathbf{O} (\\mathbf{x} - \\mathbf{Q}^{-1} \\mathbf{c})$ to obtain a much simplified expression:\n",
    "\n",
    "$$h(\\mathbf{z}) = \\frac{1}{2} \\mathbf{z}^\\top \\boldsymbol{\\Lambda} \\mathbf{z} + b'.$$\n",
    "\n",
    "Here $c' = b - \\frac{1}{2} \\mathbf{c}^\\top \\mathbf{Q}^{-1} \\mathbf{c}$. Since $\\mathbf{O}$ is only an orthogonal matrix this does not perturb the gradients in a meaningful way. Expressed in terms of $\\mathbf{z}$ gradient descent becomes\n",
    "\n",
    "$$\\mathbf{z}_t = \\mathbf{z}_{t-1} - \\boldsymbol{\\Lambda} \\mathbf{z}_{t-1} = (\\mathbf{I} - \\boldsymbol{\\Lambda}) \\mathbf{z}_{t-1}.$$\n",
    "\n",
    "The important fact in this expression is that gradient descent *does not mix* between different eigenspaces. That is, when expressed in terms of the eigensystem of $\\mathbf{Q}$ the optimization problem proceeds in a coordinate-wise manner. This also holds for momentum.\n",
    "\n",
    "$$\\begin{aligned}\n",
    "\\mathbf{v}_t & = \\beta \\mathbf{v}_{t-1} + \\boldsymbol{\\Lambda} \\mathbf{z}_{t-1} \\\\\n",
    "\\mathbf{z}_t & = \\mathbf{z}_{t-1} - \\eta \\left(\\beta \\mathbf{v}_{t-1} + \\boldsymbol{\\Lambda} \\mathbf{z}_{t-1}\\right) \\\\\n",
    "    & = (\\mathbf{I} - \\eta \\boldsymbol{\\Lambda}) \\mathbf{z}_{t-1} - \\eta \\beta \\mathbf{v}_{t-1}.\n",
    "\\end{aligned}$$\n",
    "\n",
    "In doing this we just proved the following theorem: Gradient Descent with and without momentum for a convex quadratic function decomposes into coordinate-wise optimization in the direction of the eigenvectors of the quadratic matrix.\n",
    "\n",
    "### Scalar Functions\n",
    "\n",
    "Given the above result let us see what happens when we minimize the function $f(x) = \\frac{\\lambda}{2} x^2$. For gradient descent we have\n",
    "\n",
    "$$x_{t+1} = x_t - \\eta \\lambda x_t = (1 - \\eta \\lambda) x_t.$$\n",
    "\n",
    "Whenever $|1 - \\eta \\lambda| < 1$ this optimization converges at an exponential rate since after $t$ steps we have $x_t = (1 - \\eta \\lambda)^t x_0$. This shows how the rate of convergence improves initially as we increase the learning rate $\\eta$ until $\\eta \\lambda = 1$. Beyond that things diverge and for $\\eta \\lambda > 2$ the optimization problem diverges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "float[] lambdas = new float[]{0.1f, 1f, 10f, 19f};\n",
    "float eta = 0.1f;\n",
    "\n",
    "float[] time = new float[0];\n",
    "float[] convergence = new float[0];\n",
    "String[] lambda = new String[0]; \n",
    "for (float lam : lambdas) {\n",
    "    float[] timeTemp = new float[20];\n",
    "    float[] convergenceTemp = new float[20];\n",
    "    String[] lambdaTemp = new String[20];\n",
    "    for (int i = 0; i < timeTemp.length; i++) {\n",
    "        timeTemp[i] = i;\n",
    "        convergenceTemp[i] = (float) Math.pow(1 - eta * lam, i);\n",
    "        lambdaTemp[i] = String.format(\"lambda = %.2f\", lam);\n",
    "    }\n",
    "    time = ArrayUtils.addAll(time, timeTemp);\n",
    "    convergence = ArrayUtils.addAll(convergence, convergenceTemp);\n",
    "    lambda = ArrayUtils.addAll(lambda, lambdaTemp);\n",
    "}\n",
    "\n",
    "Table data = Table.create(\"data\")\n",
    "    .addColumns(\n",
    "        DoubleColumn.create(\"time\", Functions.floatToDoubleArray(time)),\n",
    "        DoubleColumn.create(\"convergence\", Functions.floatToDoubleArray(convergence)),\n",
    "        StringColumn.create(\"lambda\", lambda)\n",
    ");\n",
    "\n",
    "LinePlot.create(\"convergence vs. time\", data, \"time\", \"convergence\", \"lambda\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To analyze convergence in the case of momentum we begin by rewriting the update equations in terms of two scalars: one for $x$ and one for the momentum $v$. This yields:\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix} v_{t+1} \\\\ x_{t+1} \\end{bmatrix} =\n",
    "\\begin{bmatrix} \\beta & \\lambda \\\\ -\\eta \\beta & (1 - \\eta \\lambda) \\end{bmatrix}\n",
    "\\begin{bmatrix} v_{t} \\\\ x_{t} \\end{bmatrix} = \\mathbf{R}(\\beta, \\eta, \\lambda) \\begin{bmatrix} v_{t} \\\\ x_{t} \\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "We used $\\mathbf{R}$ to denote the $2 \\times 2$ governing convergence behavior. After $t$ steps the initial choice $[v_0, x_0]$ becomes $\\mathbf{R}(\\beta, \\eta, \\lambda)^t [v_0, x_0]$. Hence, it is up to the eigenvalues of $\\mathbf{R}$ to detmine the speed of convergence. See the [Distill post](https://distill.pub/2017/momentum/) of :cite:`Goh.2017` for a great animation and :cite:`Flammarion.Bach.2015` for a detailed analysis. One can show that $0 < \\eta \\lambda < 2 + 2 \\beta$ momentum converges. This is a larger range of feasible parameters when compared to $0 < \\eta \\lambda < 2$ for gradient descent. It also suggests that in general large values of $\\beta$ are desirable. Further details require a fair amount of technical detail and we suggest that the interested reader consult the original publications.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* Momentum replaces gradients with a leaky average over past gradients. This accelerates convergence significantly.\n",
    "* It is desirable for both noise-free gradient descent and (noisy) stochastic gradient descent.\n",
    "* Momentum prevents stalling of the optimization process that is much more likely to occur for stochastic gradient descent.\n",
    "* The effective number of gradients is given by $\\frac{1}{1-\\beta}$ due to exponentiated downweighting of past data.\n",
    "* In the case of convex quadratic problems this can be analyzed explicitly in detail.\n",
    "* Implementation is quite straightforward but it requires us to store an additional state vector (momentum $\\mathbf{v}$).\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Use other combinations of momentum hyperparameters and learning rates and observe and analyze the different experimental results.\n",
    "1. Try out GD and momentum for a quadratic problem where you have multiple eigenvalues, i.e., $f(x) = \\frac{1}{2} \\sum_i \\lambda_i x_i^2$, e.g., $\\lambda_i = 2^{-i}$. Plot how the values of $x$ decrease for the initialization $x_i = 1$.\n",
    "1. Derive minimum value and minimizer for $h(\\mathbf{x}) = \\frac{1}{2} \\mathbf{x}^\\top \\mathbf{Q} \\mathbf{x} + \\mathbf{x}^\\top \\mathbf{c} + b$.\n",
    "1. What changes when we perform SGD with momentum? What happens when we use mini-batch SGD with momentum? Experiment with the parameters?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "14.0.1+7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}