How to know the stochastic gradient descent is converging when the objective function is expensive to compute

How can I know if the stochastic gradient descent algorithm is converging. I cannot plot my objective function and take its average for lets say every 1000 iterations to see the trend.

My objective function itself is huge, so it takes lot of time to compute the objective function itself. In this situation, how to determine if the algorithm is converging.

I know what the parameter values should be. But I see the algorithm is fluctuating around a value which is smaller than the actual one. My function has a global maxima. So it should reach that maxima isn't it? The function is concave

-
so you are taking the average of your error for about 100 iterations and then what...? if your current error is close enough do you conclude that SGD has converged? – Charlie Parker Aug 24 '15 at 3:05

Yes, if your cost function is convex, stochastic gradient descent (SGD) should converge.

If computing the cost value takes too much time, then you can estimate it by computing the cost over a randomly sampled subset of your dataset. You can naturally do this in the mini-batch setting.

-
Actually my problem is it kind of gets stuck around a parameter value that is less than the actual parameter value that should have come. For eg if my parameter value is 6 it kind of fluctuates around 4. Is it normal? – user31820 Aug 9 '12 at 17:22
I don't think it is. I would remove any kind of convergence criteria and let it run for some time with c/t learning rate. Play with the values of c. Also, it is important to carefully inspect the situation when your SGD stops. Compute and look at the batch gradient at that point of time. That's all I can think of. – emrea Aug 9 '12 at 17:29

One approach is to use "progressive validation error" for SGD diagnostics as per "Beating the Hold-Out: Bounds for K-fold and Progressive Cross-Validation"

Basically, every new case is first plugged into your loss function, and only then is passed to SGD, and the resulting loss function values are averaged across "recent" cases (typically, the loss function is printed out for each 2^Nth case, where N=1,2,3,.. using all data points since the last print out)

This gives a decent estimate of the test error and avoids the computational problems you've mentioned (since you don't have to calculate the loss function using all data for every print out).

-