difference in learning rate between classic gradient descent and batch gradient descent

Question

I am learning how to use TensorFlow and started with a example of regression problem. So the first thing was a simple gradient descent using the learning_rate = 0.1 I noticed that the MSE was going up at every step. I managed to get it converge by putting learning_rate=0.00000005 (weird isn't it ? ).

Anyway, the next step was building a batch gradient descent batch_size=100 and learning_rate=0.1 which worked perfectly.

My question here is: Why such a difference between both learning rates ? I would understand if it was a difference of 10^-2 but here the difference is huge.

Both programs :

-Gradient descent

n_epochs = 1000
learning_rate = 0.00000005
m, n = housing.data.shape
print 2/m
scaled_housing_data_plus_bias = np.c_[np.ones((m, 1)), housing.data]

X = tf.constant(scaled_housing_data_plus_bias, dtype=tf.float32, name="X")
y = tf.constant(housing.target.reshape(-1, 1), dtype=tf.float32, name="y")
theta = tf.Variable(tf.truncated_normal([n + 1, 1],stddev=0.001), name="theta")
y_pred = tf.matmul(X, theta, name="y_pred")
error = y_pred - y
mse = tf.reduce_mean(tf.square(error), name="mse")
#gradients = tf.gradients(mse, [theta])[0]
#training_op = tf.assign(theta, theta - learning_rate * gradients)

#~~~! Very efficient optimize !~~~#
optimizer = tf.train.MomentumOptimizer(learning_rate=learning_rate,momentum=0.9)
training_op = optimizer.minimize(mse)

init = tf.global_variables_initializer()

with tf.Session() as sess:
    sess.run(init)

    for epoch in range(n_epochs):
        sess.run(training_op)
        if epoch % 100 == 0:
            print("Epoch", epoch, "MSE =", mse.eval())

    best_theta = theta.eval()
    print best_theta

-Batch gradient descent:

batch_size = 1000
n_batches = int(np.ceil(m / batch_size))
n_epochs = 1000
learning_rate = 0.01
m, n = housing.data.shape

scaled_housing_data_plus_bias = np.c_[np.ones((m, 1)), housing.data]
target = housing.target.reshape(-1, 1)

X = tf.placeholder(tf.float32, shape=(None, n + 1), name="X")
y = tf.placeholder(tf.float32, shape=(None, 1), name="y")

def fetch_batch(epoch, batch_index, batch_size):
    start_idx = (batch_index-1)*batch_size + 1
    end_idx = batch_index*batch_size
    if batch_index == 0:
        start_idx = 0
        end_idx=batch_size
    #print("s",start_idx,"e",end_idx)
    X_batch = X.eval(feed_dict={X: scaled_housing_data_plus_bias[start_idx:end_idx,]})
    y_batch = y.eval(feed_dict={y: target[start_idx:end_idx]})
    return X_batch, y_batch

with tf.Session() as sess:
    sess.run(init)
    for epoch in range(n_epochs):
        for batch_index in range(n_batches):
            X_batch, y_batch = fetch_batch(epoch, batch_index, batch_size)
            sess.run(training_op, feed_dict={X: X_batch, y: y_batch})
        if epoch % 100 == 0:
            print("Epoch", epoch, "MSE =", mse.eval())
    best_theta = theta.eval()
    print best_theta

Answer 1

Attempting to use theory to answer your question, not looking at the code.

SGD looks at one sample at a time and computes a gradient that, over the entire dataset, is supposed to be a good estimate of the "true" gradient. This means that there is often a lot of variance in the gradient, which a high learning rate would exacerbate. In contrast to this, GD (or batch gradient descent) looks at 100 samples at a time in your case, which means that the variance is not as high.

There are a lot of factors that determine what you saw with SGD. Maybe it converged at a fairly different minimum than GD, maybe the MSE was going up only at the start and if you had let it run with a higher learning rate, it would have eventually converged somewhere reasonable, maybe it already started from somewhere very close to a minimum, hence you needed to use a small learning rate. You can test the last hypothesis by seeing how much of a drop there was in MSE between the first step and the last. Compare that to GD. What about the initial MSE, say for one batch of GD and 100 iterations of SGD? How close are they?