# Gradient Descent and its Variants

I know there is a lot of topic regarding this on the internet, and trust me, I've googled it. But things are getting more and more confused for me.

From my understanding, Optimization refers to the task of minimizing/maximizing an objective function $$f(x)$$ parameterized by $$x$$. In machine/deep learning terminology, it’s the task of minimizing the cost/loss function $$J(w)$$ parameterized by the model’s parameters $$w ∈ R^d$$.

Gradient Descent is the most common optimization algorithm in machine learning and deep learning. It is a first-order optimization algorithm. This means it only takes into account the first derivative when performing the updates on the parameters.

Could anyone explain in simple words (and maybe with an example/Math behind) how Batch Gradient Descent, Mini-batch Gradient Descent, and Stochastic Gradient Descent works & difference between them?

• In my opinion, the only difference is the objective function that changes during optimization while the algorithm update is the same.
– Reda
May 16, 2020 at 13:53

So below I'll explain the meaning of gradient descent, stochastic gradient descent (with a mini-batch size of $$1$$), and mini-batch stochastic gradient descent.
Suppose we're minimizing $$\tag{1} f(x) = \frac{1}{N} \sum_{i=1}^N f_i(x).$$ Let's assume the functions $$f_i: \mathbb R^n \to \mathbb R$$ are differentiable. The gradient descent iteration is $$x^{k+1} = x^k - t \nabla f(x^k).$$ Here $$t$$ is the step size, also known as the learning rate, for our optimization algorithm.
In stochastic gradient descent (with a mini-batch size of $$1$$), each time we update $$x$$ we compute the gradient using only one of the terms, selected at random, from the big sum (1). So in SGD we update $$x$$ as follows: $$x^{k+1} = x^k - t \nabla f_i(x^k),$$ where $$i$$ is selected at random from $$\{1,2, \ldots, N \}$$. The index $$i$$ can be selected either with replacement or without replacement. I believe without replacement is more common and tends to work a little better.
In the mini-batch version of stochastic gradient descent, with a mini-batch size of $$M$$, each time we update $$x$$ we compute the gradient using only $$M$$ of the terms, selected at random, from the big sum (1). So the minibatch SGD update is $$x^{k+1} = x^k - t \left( \frac{1}{M} \sum_{i \in S_k} \nabla f_i(x^k) \right),$$ where $$S_k$$ is a randomly selected $$M$$-element subset of $$\{1, 2, \ldots, N \}$$. Usually the subset $$S_k$$ is not allowed to intersect with any of the previous subsets $$S_1, \ldots S_{k-1}$$ until we have completely exhausted the set of possible indices $$S = \{1,2, \ldots, N \}$$, at which point we make another full sweep through $$S$$, then another full sweep through $$S$$, and so on. Each full sweep through $$S$$ is called one "epoch".