let's assume that I want to train a stochastic gradient descent regression algorithm using a dataset that has N samples. Since the size of the dataset is fixed, I will reuse the data T times. At each iteration or "epoch", I use each training sample exactly once after randomly reordering the whole training set.
My implementation is based on Python and Numpy. Therefore, using vector operations can remarkably decrease computation time. Coming up with a vectorized implementation of batch gradient descent is quite straightforward. However, in the case of stochastic gradient descent I can not figure out how to avoid the outer loop that iterates through all the samples at each epoch.
Does anybody know any vectorized implementation of stochastic gradient descent?
EDIT: I've been asked why would I like to use online gradient descent if the size of my dataset is fixed.
From , one can see that online gradient descent converges slower than batch gradient descent to the minimum of the empirical cost. However, it converges faster to the minimum of the expected cost, which measures generalization performance. I'd like to test the impact of these theoretical results in my particular problem, by means of cross validation. Without a vectorized implementation, my online gradient descent code is much slower than the batch gradient descent one. That remarkably increases the time it takes to the cross validation process to be completed.
EDIT: I include here the pseudocode of my on-line gradient descent implementation, as requested by ffriend. I am solving a regression problem.
Method: on-line gradient descent (regression) Input: X (nxp matrix; each line contains a training sample, represented as a length-p vector), Y (length-n vector; output of the training samples) Output: A (length-p+1 vector of coefficients) Initialize coefficients (assign value 0 to all coefficients) Calculate outputs F prev_error = inf error = sum((F-Y)^2)/n it = 0 while abs(error - prev_error)>ERROR_THRESHOLD and it<=MAX_ITERATIONS: Randomly shuffle training samples for each training sample i: Compute error for training sample i Update coefficients based on the error above prev_error = error Calculate outputs F error = sum((F-Y)^2)/n it = it + 1
 "Large Scale Online Learning", L. Bottou, Y. Le Cunn, NIPS 2003.