0
$\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$

1 Answer 1

0
$\begingroup$

Your method is not SGD, it is just gradient descent and you are splitting up the calculation for the gradient.

Suppose

$$ G := \nabla_\theta \sum_{i=1}^{100} J(x_i, \theta_k).$$

And let

$$G_j := \nabla_\theta \sum_{I=(10*(j-1))+1}^{10*j} J(x_i, \theta_k).$$

Then due to the linearity of the gradient, we have that

$$ G = G_1 + \ldots + G_{10}.$$

Note the term that you are subtracting from $\theta_{k+\frac{j}{10}}$ to get $\theta_{k+\frac{j+1}{10}}$ is $\alpha G_{j+1}$. Thus, you have that

$$ \theta_{k+1} = \theta_{k+\frac{9}{10}} - \alpha G_{10} = \theta_{k+\frac{8}{10}} - \alpha G_{9} - \alpha G_{10} = \ldots = \theta_{k} - \alpha \sum_{j=1}^10 G_j = \theta_k - \alpha G.$$

$\endgroup$
3
  • $\begingroup$ So why isn't my method used in practice instead of SGD? Since SGD suffers from randomness, then I am not sure why it is better than my method. $\endgroup$
    – mhdadk
    Oct 7, 2021 at 3:16
  • 1
    $\begingroup$ Oh when you use SGD you want the randomness!! Specifically it helps you avoid local minima and saddle points see stats.stackexchange.com/questions/49528/… and stats.stackexchange.com/questions/232056/… $\endgroup$ Oct 7, 2021 at 3:19
  • $\begingroup$ Thanks for the links. While SGD may allow you to jump away from shallow local minima, it seems that there aren't any guarantees that it won't jump away from a deep local minimum to a shallower one. Any thoughts? $\endgroup$
    – mhdadk
    Oct 7, 2021 at 3:24

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.