How to implement momentum in mini-batch gradient descent?

Question

I understand the idea behind momentum, and how to implement it with batch gradient descent, but I'm not sure how to implement it with mini-batch gradient descent. As I understand it, implementing momentum in batch gradient descent goes like this:

for example in training_set:
    calculate gradient for this example
    accumulate the gradient
for w, g in weights, gradients:
    w = w - learning_rate * g + momentum * gradients_at[-1]

Where gradients_at records the gradients for each weight at backprop iteration t.

Is this correct? If so, what modifications are necessary to apply this technique in mini-batch gradient descent?

Answer 1

The only difference between a batch and a mini-batch is that you're using part of the data set rather than the entire dataset during each epoch. Thus, you would calculate the gradient for only a subset of the samples in your training set and use these during each update epoch. Repeat for many epochs, where each epoch contains a different subset of the the full dataset.

Answer 2

The difference between Gradient Descent, Stochastic Gradient Descent, and Mini-batch Gradient Descent is the next:

• Gradient Descent: You take all the data to compute the gradient.
• Stochastic Gradient Descent: You only take 1 point to compute the gradient (the bath size is 1) It is faster than Gradient Descent but is too noisy and is affected by the data variance.
• Mini-Batch Gradient Descent: you take n points (n< data_size) to compute the gradient. Normally you take n aleatory points. As a note, if you take in Mini-batch gradient descent n==data_size you will be computing normal gradient descent. The difference between Stochastic Gradient Descent and Mini-batch Gradient descent is the size we take for computing the gradient.

The algorithm to get the gradient is the same.

def stochastic_gradient_descent_step(m,b,data_sample):

    n_points = data_sample.shape[0] #size of data
    m_grad = 0
    b_grad = 0
    stepper = 0.0001 #this is the learning rate

    for i in range(n_points):

        #Get current pair (x,y)
        x = data_sample[i,0]
        y = data_sample[i,1]
        if(math.isnan(x)|math.isnan(y)): #it will prevent for crashing when some data is missing
            #print("is nan")
            continue

        #you will calculate the partical derivative for each value in data
        #Partial derivative respect 'm'
        dm = -((2/n_points) * x * (y - (m*x + b)))

        #Partial derivative respect 'b'
        db = - ((2/n_points) * (y - (m*x + b)))


        #Update gradient
        m_grad = m_grad + dm
        b_grad = b_grad + db

    #Set the new 'better' updated 'm' and 'b'   
    m_updated = m - stepper*m_grad
    b_updated = b - stepper*b_grad
    #print('m ', m)
    ##print('steepr*gradient ',stepper*m_grad)
    #print('m_updated', m_updated)
    '''
    Important note: The value '0.0001' that multiplies the 'm_grad' and 'b_grad' is the 'learning rate', but it's a concept
    out of the scope of this challenge. For now, just leave that there and think about it like a 'smoother' of the learn, 
    to prevent overshooting, that is, an extremly fast and uncontrolled learning.
    '''

    return m_updated,b_updated

We add the next function to get the batch that we are going to use

def getSmallRandomDataSample(data, batch_size, shuffle=True): #this method only covers the solution when suffle is true
    #stolchastic gradient descent

    #it will take tha batch of size 1, Im just putting this here so you can see the difference. You can delete the next 
    #two lines and it will work.
    if(batch_size==1):
        return np.array([random.choice(data)])
    #mini-batch gradient descent
    if(batch_size< data.shape[0]):
        if(shuffle):
            #the first two line are simulating like if we were choosing randomly points from the data
            index = np.random.permutation(data.shape[0]) #first suffle the index of data
            index = index[0:batch_size] #then we take the batch 
            #algorithm for getting the sample_data
            data_sample=[]
            for i in index:
                data_sample.append(data[i])
            return np.array(data_sample)

We execute the code with the next step

max_epochs = 100
print('Starting line: y = %.2fx + %.2f - Error: %.2f' %(m,b,sse))
start = time.time()
for i in range(max_epochs):
    data_sample = getSmallRandomDataSample(data,1)
    m,b = stochastic_gradient_descent_step(m,b,data_sample)
    sse = SSE(m,b,data)
    if(i%10==0):
        end = time.time()
        print('time consumtion = ',end-start)
        print('iteration ', i)
        start = time.time()
    #print('At step %d - Line: y = %.2fx + %.2f - Error: %.2f' %(i+1,m,b,sse))
print('\nBest  line: y = %.2fx + %.2f - Error: %.2f' %(m,b,sse))

You can check a complete example with some extra notes in my github repo