1
$\begingroup$

Consider the following cost function $$ \sum_{i=1}^{100} J(\mathbf{x}_i,\theta) $$ where $\mathbf{x}_i \in \mathbb{R}^d$, $\theta \in \mathbb{R}^K$, and $J$ is some function. Suppose I want to minimize this function with respect to $\theta$ using gradient descent. The update rule would be $$ \theta_{k+1} \leftarrow \theta_k - \alpha \cdot \nabla_\theta \sum_{i=1}^{100} J(\mathbf{x}_i,\theta_k) $$ where $\alpha$ is some step size. Suppose that I can't fit the entire cost function into memory, and so I split the summation up like this $$ \theta_{k+1} \leftarrow \theta_k - \alpha \cdot \nabla_\theta \left(\sum_{i=1}^{10} J(\mathbf{x}_i,\theta_k) + \sum_{i=11}^{20} J(\mathbf{x}_i,\theta_k) + \cdots + \sum_{i=91}^{100} J(\mathbf{x}_i,\theta_k)\right) $$ I can then distribute $\alpha$ and the gradient operator $\nabla_\theta$ like this $$ \theta_{k+1} \leftarrow \theta_k - \left(\alpha \cdot \sum_{i=1}^{10} \nabla_\theta J(\mathbf{x}_i,\theta_k) + \alpha \cdot \sum_{i=11}^{20} \nabla_\theta J(\mathbf{x}_i,\theta_k) + \cdots + \alpha \cdot \sum_{i=91}^{100} \nabla_\theta J(\mathbf{x}_i,\theta_k)\right) $$ I could then bring out the first term in the summation like this $$ \theta_{k+1} \leftarrow \theta_k - \alpha \cdot \sum_{i=1}^{10} \nabla_\theta J(\mathbf{x}_i,\theta_k) - \left(\alpha \cdot \sum_{i=11}^{20} \nabla_\theta J(\mathbf{x}_i,\theta_k) + \cdots + \alpha \cdot \sum_{i=91}^{100} \nabla_\theta J(\mathbf{x}_i,\theta_k)\right) $$ Now let $$ \theta_{k+\frac{1}{10}} \leftarrow \theta_k - \alpha \cdot \sum_{i=1}^{10} \nabla_\theta J(\mathbf{x}_i,\theta_k) $$ such that the update rule now becomes $$ \theta_{k+1} \leftarrow \theta_{k+\frac{1}{10}} - \left(\alpha \cdot \sum_{i=11}^{20} \nabla_\theta J(\mathbf{x}_i,\theta_k) + \cdots + \alpha \cdot \sum_{i=91}^{100} \nabla_\theta J(\mathbf{x}_i,\theta_k)\right) $$ I can then repeat the process by bringing out the first term in the summation, $$ \theta_{k+1} \leftarrow \theta_{k+\frac{1}{10}} - \alpha \cdot \sum_{i=11}^{20} \nabla_\theta J(\mathbf{x}_i,\theta_k) - \left(\alpha \cdot \sum_{i=21}^{30} \nabla_\theta J(\mathbf{x}_i,\theta_k) + \cdots + \alpha \cdot \sum_{i=91}^{100} \nabla_\theta J(\mathbf{x}_i,\theta_k)\right) $$ and then letting $$ \theta_{k+\frac{2}{10}} \leftarrow \theta_{k+\frac{1}{10}} - \alpha \cdot \sum_{i=11}^{20} \nabla_\theta J(\mathbf{x}_i,\theta_k) $$ By repeating this process, I will eventually reach the final value of $\theta_{k+1}$, but I will have done so by computing a more tractable gradient that can fit into memory. As far as I understand, stochastic (or mini-batch) gradient descent (SGD) is different from this method, as it computes the gradient with respect to the new parameter value at each step. That is, instead of using the update rule $$ \theta_{k+\frac{2}{10}} \leftarrow \theta_{k+\frac{1}{10}} - \alpha \cdot \sum_{i=11}^{20} \nabla_\theta J(\mathbf{x}_i,\theta_k) $$ SGD uses the update rule $$ \theta_{k+\frac{2}{10}} \leftarrow \theta_{k+\frac{1}{10}} - \alpha \cdot \sum_{i=11}^{20} \nabla_\theta J(\mathbf{x}_i,\theta_{k+\frac{1}{10}}) $$ Is my method truly different from SGD? Or is it just SGD in disguise? Also, if my method is different, why is it not more commonly used in practice, since it achieves the same goal of SGD of allowing large-scale gradient descent?

$\endgroup$
2
$\begingroup$

The proposed method is standard gradient descent with a reordering of the computation. I doesn't change anything for memory use, since there is no need to keep every element of the sum in memory anyway.

Explained differently, the strength of SGD is to take multiple steps with partial information. Your algorithm evaluates every gradient at $\theta_k$, so only performs the full gradient descent step.

$\endgroup$
4
  • $\begingroup$ Thanks for the answer. The problem that I notice with SGD is that at each step, the cost function has changed, so the minimum becomes a moving target. How is this better than normal gradient descent, where the location of the minimum doesn't change after every step? $\endgroup$
    – mhdadk
    Oct 7 '21 at 11:05
  • 1
    $\begingroup$ If each gradient evaluation only has a small error relative to the actual gradient, many slightly imprecise steps can be much better than a single precise step - they can follow the curvature of the function for example. SGD is mostly used for neural networks, where you basically don't have a choice given the size of the datasets - and it helps with generalization. $\endgroup$ Oct 7 '21 at 19:15
  • $\begingroup$ But my method can also be used for neural networks too, right? Since I only need to compute the gradient for every 10 examples and not every 100 examples. $\endgroup$
    – mhdadk
    Oct 7 '21 at 19:30
  • 1
    $\begingroup$ Your method after all steps is equivalent to a single step of gradient descent. So no, it's not useful $\endgroup$ Oct 7 '21 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.