3
$\begingroup$

I have read that the update equation for stochastic gradient descent is as shown below, for each iteration, k. Does one iteration correspond to one training example? So for each example is there only one update to $\theta$?

$ \theta^{k+1} = \theta^k - \epsilon_k \frac{\partial L(\theta^k,z)}{\partial \theta^k} $

Update: Is it different for Online learning?

Improve this question
$\endgroup$
1
  • $\begingroup$ $\epsilon_k$ is sometimes a scalar, and sometimes a vector, per-feature, at each iteration. Further, either can be constant for all time, or decaying, or adaptive ... and the gradients can be smoothed or scaled or not. Many possibilities, more folklore than test cases. $\endgroup$
    – denis
    Commented Jun 24, 2014 at 13:22

1 Answer 1

Reset to default
3
$\begingroup$

Does one iteration correspond to one training example?

Yes.

So for each example is there only one update to $\theta$?

It is possible for a single example to be picked and used to update theta many times.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ In relation to the second answer: this actually depends on the implementation of SGD. In some cases, particularly with large data sets, there might be a single pass through a randomly shuffled data set. In other cases, there is a single pass through the shuffled data, another shuffle and pass through, and so on, until the convergence criterion is met. In the first version you would see each example precisely once, but otherwise you will see most examples multiple times. $\endgroup$
    – Fraijo
    Commented Nov 4, 2013 at 19:35
  • $\begingroup$ @Fraijo is the algo different for online learning? $\endgroup$
    – power
    Commented Nov 7, 2013 at 4:15
  • 1
    $\begingroup$ That's tough. I have seen one use of SGD in an online setting where every time a new observation came in it was used a single time to train and then thrown away. But in that case the volume of data was huge and you could assume a lack of correlation between observations. If the volume/velocity of the data is small enough it might be better to just make multiple passes. $\endgroup$
    – Fraijo
    Commented Nov 7, 2013 at 20:51
  • $\begingroup$ @Fraijo So if the volume is large and the data are correlated, does it become a "best effort" sort of thing? $\endgroup$
    – power
    Commented Nov 11, 2013 at 5:01
  • 1
    $\begingroup$ I should be careful here: correlation may, or may not be a problem depending on the situation. It is possible that highly correlated observations will cause issues when exploring the optimization space (if 1000 observations are all similar then you might push the wrong direction). In cases like that you can filter out observations (say only take 1 out of every 100) or do mini-batch after a large number of observations. Or you could decide it just doesn't matter. $\endgroup$
    – Fraijo
    Commented Nov 11, 2013 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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