What are the precise/exact halting conditions for batch Gradient Descent (GD) when working with data with random noise?

Question

I was trying to understand the different alternatives there are for halting batch gradient descent and concluding that one has reached some minimum (local or global). In the presence of noisy data (similar to what "real" data is) the empirical risk curve might not look very convex in every iteration of GD (right?even if the curve is provably convex?). Hence, I was wondering, in this scenario with noise (and most similar to the real world), how does one decide when a (global or local) minimum has been reached?

I did see the following question How to define the termination condition for gradient descent? trying to address something similar but wasn't quite sure if the current answer addressed the issue in enough detail. In particular, the third bullet point says:

reltol, which is like your second suggestion--stop when the improvement drops below a threshold. I don't actually know how much theory there is on this, but you'll probably tend to get lower minima this way than with a small maximum number of iterations. If that's important to you, then it might be worth running the code for more iterations.

in particular, the way I interpret this suggestion is to use some kind of update rule that has a while loop with a condition similar to:

• "While current error - previous error keeps decreasing, then keep doing batch gradient descent (GD), if the decrease is not large enough or if there is an increase in the cost then stop"

That kind of update rule would make total sense if we knew our curve was perfectly convex, however, with noisy data (or real data), I'd suspect that this terminating condition might not a good idea (I might be totally wrong, hence the question). So the things I'd like to address are:

1. Is it reasonable to expect in batch gradient descent that every step of GD that the training/total cost is to decrease? Even in the presence of noise?
2. Is basing our halting condition on a single iteration ever a good idea on data with randomness? Might we see a moment when out cost increases for a tiny bit and the decreases? Or is that sort of weird behaviour only something one would expect from stochastic gradient descent?
3. Is there a situation where you can mathematically prove that batch GD monotonically decreases the error cost?
4. Is using something like a "moving average" a better idea? What I mean by that is that for every iteration up to the current one we have an average of the previous $m$ training costs and once this moving average stops decreasing in a significant way (or increases) then we halt GD and output the current parameter of our model. Is this reasonable for batch gradient descent or does this only (potentially) make sense for stochastic gradient descent?
5. Another thing could be to track the size of the gradient? If the gradient is exactly zero, then obviously we've reached a critical point (we'd probably need to do further tests to make sure its not a stadle point or inflection point...), is this a good idea or what do people actually use?

Answer 1

That kind of update rule would make total sense if we knew our curve was perfectly convex, however, with noisy data (or real data), I'd suspect that this terminating condition might not a good idea (I might be totally wrong, hence the question).

You kept the cost function completely out of the picture! While your argument holds truth when using root-mean-square deviation (RMSD), it falls apart when you consider cross-entropy error. You might refer to Andrew Ng's Coursera course. He actually explains this concept very well in one of his lessons (see Week 3: Logistic Regression Model).