Stochastic Gradient Descent

 Stochastic Gradient Descent is a family of algorithms that solves the supervised learning problem. It cycles through the data, and concludes by arriving a couple examples.

Stochastic gradient descent only uses part of the data, not all of it. f(w) is a loss + regularizer, and the way to do this is to iterate through a series of Gradient Descents, and converge to the global optimum. There are squared errors and hinge loss functions, and we can differentiate that, find the gradient, which was discussed in the latest video. 

In stochastic Gradient Descent the Cost function is broken up into a series of term, calculate the terms, and update the terms using this gradient. We are updating our weights based on one sample, and the feature vector xi(k). 

We can take a cyclical approach, where we just walk through the training data in order sequentially. This is where we update sample 1, 2, 3, 4, 1, 2 ,3 ,4 

Another approach is to reshuffle and do everything in a random permutation, take the first 4 and reshuffle them.

2, 4, 1 3, 2, 1, 4, 3, 4, 3, 1, 2

The third approach is Stochastic Gradient Descent is to sample the data uniformly at random. We use the negative of the step size (see above picture). This results in approximately the same gradient averaging concept. 

Computing the gradient with respect to a sample is much easier vs computing the gradient in respect to the data. 

By using SGD, we can just read in the data we can update and discard it.

The noisy gradient operation tends to get some added regularization, avoiding the sensitivity of gradient descent. On average these gradients go in the same direction as the noiseless gradient. You can break down the cost function into N terms by including 1/N in the regularization term. You can then take the gradient of this function, and then afterwards. A is an N x M matrix. 

The second example derives gradient descent from LASSO. Our loss function is the squared error summed with all the training samples and regularized with the L1 norm of the weight vector. In this case we take the gradient of the 1-norm and differentiate with respect to Wl and the absolute value is not differentiable, so we have to find the subgradient of this function. The computation for this is written below. We cycle through all the data, and initialize the ground value, and should converge to the same solution vs. using all of the data at once.