4
$\begingroup$

Calculating gradient needs to sum over all the data points. So, SGD can be viewed as "using one data point to weakly approximate the gradient" to save time.

Intuitively, I would think One epoch for SGD and One iteration for GD are the same, but they are not. The result for One epoch for SGD is much better than One iteration for GD (Better means the lower loss value)

Why approximately same amount of computations would have such large difference? Any intuitive explanation? If SGD is this good, can we completely replace GD?


Here are the math and code to illustrate my question.

Objective $$\underset x {\text{minimize}}~~\|Ax-b\|^2$$ Exact gradient $$2A^T(Ax-b)$$ Approximated gradient from data $i$. $$2(a_i^Tx-b_i)a_i $$

SGD 1 epoch loss value ~= 123, GD 1 iteration loss value ~=42613

set.seed(0) 
n_data=1e3
n_feature=2
A=matrix(runif(n_data*n_feature),ncol=n_feature)
b=runif(n_data)
sq_loss<-function(A,b,x){
  e=A %*% x -b
  v=crossprod(e)
  return(v[1])
}
sq_loss_gr<-function(A,b,x){
  v=t(A) %*% A %*% x - t(A) %*% b
  return(2*v)
}
sq_loss_gr_approx<-function(A,b,x,i){
  # ith data point
  gr=2*(crossprod(A[i,],x)-b[i])*A[i,]
  return(gr)
}
# ------- SGD 1 epoch
x=c(1,1)
alpha=0.01
N_iter=n_data
for (i in 1:N_iter){
  x=x-alpha*sq_loss_gr_approx(A,b,x,i)
}
print(sq_loss(A,b,x))
# ------- GD 1 iteration
x=c(1,1)
alpha=0.01
N_iter=1
for (i in 1:N_iter){
  x=x-alpha*sq_loss_gr(A,b,x)
}
print(sq_loss(A,b,x))
$\endgroup$
  • $\begingroup$ It would help folks if you wrote out the optimization problem you're solving, the gradient, as well as the error distribution (and how they're combined) contributing to the gradient in both the approx and non-approx forms. $\endgroup$ – Mark L. Stone Sep 13 '16 at 18:10
  • $\begingroup$ @MarkL.Stone thanks. Are you asking me to revise the question? or giving me clues to the answer of my question. $\endgroup$ – Haitao Du Sep 13 '16 at 18:13
  • $\begingroup$ Suggesting you edit question to make math clear without going through code. I have lots of hints, but am busy, so will probably leave answer to others. $\endgroup$ – Mark L. Stone Sep 13 '16 at 18:15
  • $\begingroup$ @hxd1011 another thing to note is that for SGD you are updating the residual $r=Ax-b$ every time you update $x$ over the SGD epoch, so SGD explores different gradients on the curved error surface. In this way, SGD vs. BGD is reminiscent of Gauss-Seidel vs. Jacobi iteration, two basic iterative methods for linear systems. When applied to the normal equations in your linear LSQR case, this comparison may be exact ($\Delta x$ update directions for SGD=Gauss-Seidel and for BGD=Jacobi). This is discussed in sec 8.2 of this book. $\endgroup$ – GeoMatt22 Sep 13 '16 at 22:52
4
$\begingroup$

Just to clarify: this isn't SGD, it's really more of a Batch Gradient Descent. For SGD, you'd randomly sample points, whereas here you are moving across all your points, one at a time. Also, it's not fair to compare these algorithms with the same $\alpha$. You're taking many one directional steps with your "SGD" but one big step with your GD. Try using $\alpha=0.001$ in your GD and you'll get comparable losses in one iteration. In general, Batch gradient descent should be slower than GD because you'll overshoot more often.

For true SGD remember to let your alpha tend to 0, something like $\frac{1}{10i}$ for example. Keeping it constant risks jumping around your minimum. In the case of least squares, I believe it's enough for $\alpha$ to be less than the maximum possible value of $1/|\nabla f|$

$\endgroup$
  • $\begingroup$ thanks Alex, I think you answered my question. The problem is using same $\alpha$. Just a small additional question, Could you clarify what is $\frac 1 {10i}$ $\endgroup$ – Haitao Du Sep 13 '16 at 21:03
  • $\begingroup$ are you saying in each iteration, we want $\alpha=\alpha/10$? then how would that related to $i$? $\endgroup$ – Haitao Du Sep 13 '16 at 21:13
  • 2
    $\begingroup$ I've rephrased it slightly: For true SGD, you need the learning rate to go to 0 to guarantee convergence. It should be fine without this for GD given the new info I added. So one option is $1/10i$ where $i$ is the epoch. $\endgroup$ – Alex R. Sep 13 '16 at 21:14
  • $\begingroup$ For convergence guarantees one can look into the Robbins-Monro conditions: en.wikipedia.org/wiki/… $\endgroup$ – Bar Sep 21 '16 at 15:59

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.