I've been toying around with logistic regression with various batch optimization algorithms (conjugate gradient, newton-raphson, and various quasinewton methods). One thing I've noticed is that sometimes, adding more data to a model can actually make training the model take much less time. Each iteration requires looking at more data points, but the total number of iterations required can drop significantly when adding more data. Of course, this only happens on certain data sets, and at some point adding more data will cause the optimization to slow back down.
Is this a well studied phenomenon? Where can I find more information about why/when this might happen?