{"id":626,"date":"2018-03-26T03:14:36","date_gmt":"2018-03-26T03:14:36","guid":{"rendered":"http:\/\/kusuaks7\/?p=231"},"modified":"2025-05-23T10:48:27","modified_gmt":"2025-05-23T10:48:27","slug":"gradient-descent-algorithm-and-its-variants","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/ai-ml\/gradient-descent-algorithm-and-its-variants\/","title":{"rendered":"Gradient Descent Algorithm and Its Variants"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tReady to learn Machine Learning? Browse courses<\/a>\u00a0like\u00a0Machine Learning Foundations: Supervised Learning<\/a> developed by industry thought leaders and Experfy in Harvard Innovation Lab.<\/em><\/strong>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
<\/center>Optimization<\/strong>\u00a0refers to the task of minimizing\/maximizing an objective function\u00a0f(x)<\/em>parameterized by\u00a0x<\/em>. In machine\/deep learning terminology, it\u2019s the task of minimizing the cost\/loss function\u00a0J(w)<\/em>\u00a0parameterized by the model\u2019s parameters\u00a0w\u2208Rdw\u2208Rd. Optimization algorithms (in case of minimization) have one of the following goals:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
    \n \t
  • Find the global minimum of the objective function. This is feasible if the objective function is convex, i.e. any local minimum is a global minimum.<\/li>\n \t
  • Find the lowest possible value of the objective function within its neighborhood. That\u2019s usually the case if the objective function is not convex as the case in most deep learning problems.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\tThere are three kinds of optimization algorithms:\n
      \n \t
    • Optimization algorithm that is not iterative and simply solves for one point.<\/li>\n \t
    • Optimization algorithm that is iterative in nature and converges to acceptable solution regardless of the parameters initialization such as gradient descent applied to logistic regression.<\/li>\n \t
    • Optimization algorithm that is iterative in nature and applied to a set of problems that have non-convex cost functions such as neural networks. Therefore, parameters\u2019 initialization plays a critical role in speeding up convergence and achieving lower error rates.<\/li>\n<\/ul\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t\tGradient Descent<\/strong>\u00a0is the most common optimization algorithm in\u00a0machine learning<\/em>and\u00a0deep learning<\/em>. It is a first-order optimization algorithm. This means it only takes into account the first derivative when performing the updates on the parameters. On each iteration, we update the parameters in the opposite direction of the gradient of the objective function\u00a0J(w)<\/em>\u00a0w.r.t the parameters where the gradient gives the direction of the steepest ascent. The size of the step we take on each iteration to reach the local minimum is determined by the learning rate \u03b1. Therefore, we follow the direction of the slope downhill until we reach a local minimum.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t\tIn this notebook, we\u2019ll cover gradient descent algorithm and its variants:\u00a0Batch Gradient Descent, Mini-batch Gradient Descent, and Stochastic Gradient Descent<\/em>.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t\tLet\u2019s first see how gradient descent and its associated steps works on logistic regression before going into the details of its variants. For the sake of simplicity, let\u2019s assume that the logistic regression model has only two parameters: weight\u00a0w<\/em>\u00a0and bias\u00a0b<\/em>.\n
        \n \t
      1. Initialize weight\u00a0w<\/em>\u00a0and bias\u00a0b<\/em>\u00a0to any random numbers.<\/li>\n \t
      2. Pick a value for the learning rate \u03b1. The learning rate determines how big the step would be on each iteration.Therefore, plot the cost function against different values of \u03b1 and pick the value of \u03b1 that is right before the first value that didn\u2019t converge so that we would have a very fast learning algorithm that converges\n
        <\/center> \n
          \n \t
        • If \u03b1 is very small, it would take long time to converge and become computationally expensive.<\/li>\n \t
        • IF \u03b1 is large, it may fail to converge and overshoot the minimum.<\/li>\n \t
        • The most commonly used rates are :\u00a00.001, 0.003, 0.01, 0.03, 0.1, 0.3<\/em>.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
          \n\t\t\t\t\t\t
          \n\t\t\t\t\t
          \n\t\t\t
          \n\t\t\t\t\t\t
          \n\t\t\t\t
          \n\t\t\t\t\t\t\t\t\t<\/li>\n \t
        • Make sure to scale the data if it\u2019s on very different scales. If we don\u2019t scale the data, the level curves (contours) would be narrower and taller which means it would take longer time to converge (see figure 3).\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
          \n\t\t\t\t\t\t
          \n\t\t\t\t\t
          \n\t\t\t
          \n\t\t\t\t\t\t
          \n\t\t\t\t
          \n\t\t\t\t\t\t\t\t\tScale the data to have \u03bc = 0 and \u03c3 = 1. Below is the formula for scaling each example:\n

          <\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

          \n\t\t\t\t\t\t
          \n\t\t\t\t\t
          \n\t\t\t
          \n\t\t\t\t\t\t
          \n\t\t\t\t
          \n\t\t\t\t\t\t\t\t\t<\/ol>\n
            \n \t
          • On each iteration, take the partial derivative of the cost function\u00a0J(w)<\/em>\u00a0w.r.t each parameter (gradient):\n

            \n<\/p>\nThe update equations are:\n

            \n<\/p>\n <\/li>\n<\/ul>\n

            An illustration of how gradient descent algorithm uses the first derivative of the loss function to follow downhill it’s minimum.<\/center>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
            \n\t\t\t\t\t\t
            \n\t\t\t\t\t
            \n\t\t\t
            \n\t\t\t\t\t\t
            \n\t\t\t\t
            \n\t\t\t\t\t\t\t\t\t
              \n \t
            • Continue the process until the cost function converges. That is, until the error curve becomes flat and doesn\u2019t change.<\/li>\n \t
            • For the sake of illustration, let\u2019s assume we don\u2019t have bias. If the slope of the current value of\u00a0w > 0<\/em>, this means that we are to the right of optimal\u00a0w<\/em>*. Therefore, the update will be negative, and will start getting close to the optimal values of\u00a0w<\/em>*. However, if it\u2019s negative, the update will be positive and will increase the current values of\u00a0w<\/em>\u00a0to converge to the optimal values of\u00a0w<\/em>*(see figure 4):<\/li>\n \t
            • In addition, on each iteration, the step would be in the direction that gives the\u00a0maximum<\/em>\u00a0change since it\u2019s perpendicular to level curves at each step.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
              \n\t\t\t\t\t\t
              \n\t\t\t\t\t
              \n\t\t\t
              \n\t\t\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\tNow let\u2019s discuss the three variants of gradient descent algorithm. The main difference between them is the amount of data we use when computing the gradients for each learning step. The trade-off between them is the accuracy of the gradient versus the time complexity to perform each parameter\u2019s update (learning step).\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
              \n\t\t\t\t\t\t
              \n\t\t\t\t\t
              \n\t\t\t
              \n\t\t\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t

              Batch Gradient Descent<\/strong><\/h3><\/h3>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
              \n\t\t\t\t\t\t
              \n\t\t\t\t\t
              \n\t\t\t
              \n\t\t\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\tBatch Gradient Descent is when we sum up over all examples on each iteration when performing the updates to the parameters. Therefore, for each update, we have to sum over all examples:\n

              <\/p>\n\n

              for i in range(num_epochs):\ngrad = compute_gradient(data, params)\nparams = params - learning_rate * grad\n<\/code><\/pre>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
              \n\t\t\t\t\t\t
              \n\t\t\t\t\t
              \n\t\t\t
              \n\t\t\t\t\t\t
              \n\t\t\t\t
              \n\t\t\t\t\t\t\t\t\tThe main advantages:\n
                \n \t
              • We can use fixed learning rate during training without worrying about learning rate decay.<\/li>\n \t
              • It has straight trajectory towards the minimum and it is guaranteed to converge in theory to the global minimum if the loss function is convex and to a local minimum if the loss function is not convex.<\/li>\n \t
              • It has unbiased estimate of gradients. The more the examples, the lower the standard error.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                \n\t\t\t\t\t\t
                \n\t\t\t\t\t
                \n\t\t\t
                \n\t\t\t\t\t\t
                \n\t\t\t\t
                \n\t\t\t\t\t\t\t\t\tThe main disadvantages:\n
                  \n \t
                • Even though we can use vectorized implementation, it may still be slow to go over all examples especially when we have large datasets.<\/li>\n \t
                • Each step of learning happens after going over all examples where some examples may be redundant and don\u2019t contribute much to the update.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                  \n\t\t\t\t\t\t
                  \n\t\t\t\t\t
                  \n\t\t\t
                  \n\t\t\t\t\t\t
                  \n\t\t\t\t
                  \n\t\t\t\t\t
                  Mini-Batch Gradient Descent<\/strong><\/h3><\/h3>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                  \n\t\t\t\t\t\t
                  \n\t\t\t\t\t
                  \n\t\t\t
                  \n\t\t\t\t\t\t
                  \n\t\t\t\t
                  \n\t\t\t\t\t\t\t\t\tInstead of going over all examples, Mini-batch Gradient Descent sums up over lower number of examples based on batch size. Therefore, learning happens on each mini-batch of\u00a0b<\/em>\u00a0examples:\n
                  <\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                  \n\t\t\t\t\t\t
                  \n\t\t\t\t\t
                  \n\t\t\t
                  \n\t\t\t\t\t\t
                  \n\t\t\t\t
                  \n\t\t\t\t\t\t\t\t\t
                    \n \t
                  • Shuffle the training dataset to avoid pre-existing order of examples.<\/li>\n \t
                  • Partition the training dataset into\u00a0b<\/em>\u00a0mini-batches based on the batch size. If the training set size is not divisible by batch size, the remaining will be its own batch.<\/li>\n<\/ul>\n
                    for i in range(num_epochs):\nnp.random.shuffle(data)\nfor batch in radom_minibatches(data, batch_size=32):\ngrad = compute_gradient(batch, params)\nparams = params - learning_rate * grad\n<\/code><\/pre>\nThe batch size is something we can tune. It is usually chosen as power of 2 such as 32, 64, 128, 256, 512, etc. The reason behind it is because some hardware such as GPUs achieve better runtime with common batch sizes such as power of 2.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                    \n\t\t\t\t\t\t
                    \n\t\t\t\t\t
                    \n\t\t\t
                    \n\t\t\t\t\t\t
                    \n\t\t\t\t
                    \n\t\t\t\t\t\t\t\t\t\nThe main advantages:\n
                      \n \t
                    • Faster than Batch version because it goes through a lot less examples than Batch (all examples).<\/li>\n \t
                    • Randomly selecting examples will help avoid redundant examples or examples that are very similar that don\u2019t contribute much to the learning.<\/li>\n \t
                    • With batch size < size of training set, it adds noise to the learning process that helps improving generalization error.<\/li>\n \t
                    • Even though with more examples the estimate would have lower standard error, the return is less than linear compared to the computational burden we incur.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                      \n\t\t\t\t\t\t
                      \n\t\t\t\t\t
                      \n\t\t\t
                      \n\t\t\t\t\t\t
                      \n\t\t\t\t
                      \n\t\t\t\t\t\t\t\t\tThe main disadvantages:\n
                        \n \t
                      • It won\u2019t converge. On each iteration, the learning step may go back and forth due to the noise. Therefore, it wanders around the minimum region but never converges.<\/li>\n \t
                      • Due to the noise, the learning steps have more oscillations (see figure 5) and requires adding learning-decay to decrease the learning rate as we become closer to the minimum.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t\t
                        \n\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t
                        \n\t\t\t\t\t\t\t\t\t
                        <\/center>With large training datasets, we don\u2019t usually need more than 2-10 passes over all training examples (epochs). Note: with batch size\u00a0b = m<\/em>, we get the Batch Gradient Descent.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t\t
                        \n\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t
                        \n\t\t\t\t\t
                        Stochastic Gradient Descent<\/strong><\/h3>\n<\/h3>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t\t
                        \n\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t
                        \n\t\t\t\t\t\t\t\t\tInstead of going through all examples, Stochastic Gradient Descent (SGD) performs the parameters update on each example\u00a0(x#k8SjZc9Dxki, y#k8SjZc9Dxki)<\/em>. Therefore, learning happens on every example:\n
                        <\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t\t
                        \n\t\t\t
                        \n\t\t\t\t\t\t
                        \n\t\t\t\t
                        \n\t\t\t\t\t\t\t\t\t
                          \n \t
                        • Shuffle the training dataset to avoid pre-existing order of examples.<\/li>\n \t
                        • Partition the training dataset into\u00a0m<\/em>\u00a0examples.<\/li>\n<\/ul>\n
                          for i in range(num_epochs):\nnp.random.shuffle(data)\nfor example in data:\ngrad = compute_gradient(example, params)\nparams = params - learning_rate * grad\n<\/code><\/pre>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                          \n\t\t\t\t\t\t
                          \n\t\t\t\t\t
                          \n\t\t\t
                          \n\t\t\t\t\t\t
                          \n\t\t\t\t
                          \n\t\t\t\t\t\t\t\t\tIt shares most of the advantages and the disadvantages with mini-batch version. Below are the ones that are specific to SGD:\n
                            \n \t
                          • It adds even more noise to the learning process than mini-batch that helps improving generalization error. However, this would increase the run time.<\/li>\n \t
                          • We can\u2019t utilize vectorization over 1 example and becomes very slow. Also, the variance becomes large since we only use 1 example for each learning step.<\/li>\n<\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                            \n\t\t\t\t\t\t
                            \n\t\t\t\t\t
                            \n\t\t\t
                            \n\t\t\t\t\t\t
                            \n\t\t\t\t
                            \n\t\t\t\t\t\t\t\t\tBelow is a graph that shows the gradient descent\u2019s variants and their direction towards the minimum:\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                            \n\t\t\t\t\t\t
                            \n\t\t\t\t\t
                            \n\t\t\t
                            \n\t\t\t\t\t\t
                            \n\t\t\t\t
                            \n\t\t\t\t\t\t\t\t\t
                            <\/center>As the figure above shows, SGD direction is very noisy compared to mini-batch.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                            \n\t\t\t\t\t\t
                            \n\t\t\t\t\t
                            \n\t\t\t
                            \n\t\t\t\t\t\t
                            \n\t\t\t\t
                            \n\t\t\t\t\t
                            Challenges<\/strong><\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
                            \n\t\t\t\t\t\t
                            \n\t\t\t\t\t
                            \n\t\t\t
                            \n\t\t\t\t\t\t
                            \n\t\t\t\t
                            \n\t\t\t\t\t\t\t\t\tBelow are some challenges regarding gradient descent algorithm in general as well as its variants – mainly batch and mini-batch:\n