# Issues with stochastic gradient descent

I am using stochastic gradient descent to learn a model. Here is the plot of the objective function for the iterations. I am trying to maximize the function value.

Taking the average of 500 iterations, I have this next plot

As you can see the function value is increasing and we can say the algorithm is converging. However, looking at the first plot, we can see that the function never actually went past a certain threshold. Even though the minimum value it could reach went on converging with the iterations, the maximum value that it could attain remained almost the same.

So can we say the algorithm is converging?

-

Yes, you can say that the algorithm is converging because it is increasing the objective value on average.

The most tricky part of stochastic gradient descent (SGD) is the 'learning rate'. Common choices are 1/t, 1/sqrt(t), D/(G*t) where t is the iteration number, D is the max diameter of your feasible set, and G is the infinity-norm of the current gradient. You should experiment with these. You can even split your data into two for cross validation of the learning rate.

Another thing you can try is mini-batch SGD. In this variant, instead of using a single data point to compute the gradient, you use a batch of points like 10,20. This way, the objective-versus-trial plot (the first plot) will be smoother and will look like the second plot you have.

-

The right way to monitor convergence is actually to measure the very objective you are optimizing. In your case, this is the average of the error over the whole training set. So the correct way would be to do a pass over the training set evere $k$ iterations only for the purpose of calculating your loss.

This is of course terribly inefficient for big data sets, but everything else is basically a heuristic. Here are some that I use:

• Calculcate the loss on a fixed batch every $k$ iterations (use as many samples as you can afford computation time wise). This removes the stochasticity. Ideally, you would do this on a held out validation set that you do not use for estimation of the gradient and which also tells you when to stop optimizing. (That is, when that error rises).
• Take a moving average (similar to you second plot).
• Fit an exponential to your error curve and see whether the gradient of that fit is low.
• Check the absolute values of your gradients and stop if they fall below some threshold.
-

Yes, it's converging, but difficult to see (or measure programmatically) from the first plot. You can try averaged SGD, where you use the average of the usual noisy SGD-trained parameters as the true model parameters. See Xu, 2011, "Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent." The averaged parameters should converge faster, and it should make your plots look much smoother.

-