1
$\begingroup$

I understand the difference between batch and stochastic gradient descent as follows: let's say there are only two samples and two features. Let the function used to estimate $y^{(i)}$ be: $$h_{\theta}(x^{(i)}) = \theta_1x_1^{(i)}+\theta_2x_2^{(i)}$$

Specifically the batch gradient descent algorithm will go something like this: in the first "update" step, $$\hat{\theta}_1 = \theta_1 + \alpha\sum_{i=1}^2\big(y^{(i)}-h_{\theta}(x^{(i)})\big)x_1^{(i)}$$ $$\hat{\theta}_2 = \theta_2 + \alpha\sum_{i=1}^2\big(y^{(i)}-h_{\theta}(x^{(i)})\big)x_2^{(i)}$$

i.e., each $\theta_j$ is updated in a single "update step" to the new value $\hat{\theta}_j$. And then more "update steps" will be performed till both $\theta_1$ and $\theta_2$ converge.

Question 1: when $\theta_2$ is being updated in the first "update step" to $\hat{\theta}_2$, does the calculation of $h_{\theta}(x^{(i)})$ involve using the old value of $\theta_1$ or the updated value of that parameter? i.e., do we say $$h_{\theta}(x^{(i)}) = \theta_1x_1^{(i)} + \theta_2x_2^{(i)}$$ or $$h_{\theta}(x^{(i)}) = \hat{\theta}_1x_1^{(i)} + \theta_2x_2^{(i)}$$

I also wanted to clarify my understanding of stochastic gradient descent (not talking about mini-batch). This time the first "update" step looks like: $$\hat{\theta}_1 = \theta_1 + \alpha\big(y^{(r)}-h_{\theta}(x^{(r)})\big)x_1^{(r)}$$ $$\hat{\theta}_2 = \theta_2 + \alpha\big(y^{(s)}-h_{\theta}(x^{(s)})\big)x_2^{(s)}$$

Then this "update step" is repeated till the $\theta$'s converge (hopefully my understanding is correct). Same question as before applies to this case as well: to calculate $h_{\theta}(x^{(s)})$, do we use the old value $\theta_1$ or the updated value $\hat{\theta}_1$?

Question 2: I've read that a random sample is chosen in each update. Is that same random sample used for the update of all the $\theta_j$'s (i.e. is $r$ necessarily equal to $s$), or is a different random sample chosen for calculating the update to each $\theta_j$ (i.e. $r$ may not be the same as $s$)?

Please correct me if I got any of the theory wrong. Apologies if the question is too verbose or if this has been asked in part, but I've tried browsing many related questions and these things weren't addressed in those, as far as I could see.

$\endgroup$
1
$\begingroup$

Question 1: when θ2 is being updated in the first "update step" to θ̂ 2, does the calculation of hθ(x(i)) involve using the old value of θ1 or the updated value of that parameter?

You use the old value. You calculate all the gradients with respect to old values, and update the parameters. Commonly, your $\theta_1$ and $\theta_2$ would be in a vector to speed up the calculations, and you calculate the gradient vector consisting of the derivatives for each variable. That way, you wouldn't be exposed to this. Always remember your parameters as a vector, i.e. $\Theta=[\theta_j,..]$.

This time the first "update" step looks like

I'm afraid that's not the first update step, because $x^{(r)}$ and $x^{(s)}$ are different samples. In SGD, you choose one sample, e.g. $x^{(r)}$, and you update all your parameters for that sample (together as above), then proceed to next sample. The first equation you wrote updates $\theta_1$ using $x^{(r)}$, and the second one updates $\theta_2$ using $x^{(s)}$.

Your Q2 iterates over your incorrect equations of SGD in Q1. When you choose a sample, random or not, you update all the system parameters, such that every member of the system learns something from that sample (unless you're applying some kind of dropout mechanism just like in neural networks).

I also advise you to check out the Example section here.

$\endgroup$

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.