Why one epoch for stochastic gradient descent (SGD) is much better than one iteration for gradient decent (GD)?

Question

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))

Answer 1

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