effect of increasing the number of iterations while optimising logistic regression cost function

Question

I am taking an online Deep learning class from Andrew Ng and it starts with optimising a classifier based on Logistic Regression. During the online assignment there was one paragraph which does not make sense to me:

You can see the cost decreasing. It shows that the parameters are being learned. However, you see that you could train the model even more on the training set. Try to increase the number of iterations in the cell above and rerun the cells. You might see that the training set accuracy goes up, but the test set accuracy goes down. This is called overfitting.

I cannot understand why increasing the number of iterations will result in overfitting? I can understand that increasing model complexity can result in overfitting but cannot understand why increasing the number of gradient descent iterations for the logistic regression cost function can overfit.

Is the statement wrong or have I failed to understand some important concept?

Answer 1

I share your confusion about vanilla logistic regression. That is, when you are working with an unpenalised likelihood/objective function. This is where the iterations are not really about model selection, but rather about finding the maximum of a non-linear function.

However....having said this...if you think of the starting point for the algorithm, which is often intercept (or bias) equal to log odds for the whole dataset, and everything else equal to zero. This could be a "simple" model, and you can think of your actual model as the "complex" model. As you do the iterations, the parameters move from the "simple" to the "complex" model.

We can then imagine finding the MLE for a logistic model with "too many" predictors. The idea is that the iterations always start from a model with "too few" predictors. The "hand wavy" argument goes that somewhere in the middle iterations might be a nice "good fit". This is obviously dependent on how the iterations of the algorithm are done, such as how quickly it converges, and how much parameters are allowed to vary at each iteration.

Hope this helps!

Answer 2

The statement is correct and complexity of the model has nothing to with the overfitting.

Real world data has noise in it. This noise is expressed by random changes in values you provide to the classifier. Because of this, the classifiers do not learn on a model, but rather on a combination of model with a background.

Noise changes the output of the model, but to a much lesser extent than model parameters do (otherwise, you can't really train a classifier on this data). So, for a linear model, you'd get something like this:

As you can see, while the real model is linear, the data you submit is not. As you increase the number of iterations, the precision with which logistical regression tries to fit the data grows - the regression algorithm modifies model parameters to account for noise induced fluctuations.

This way, you get a set of parameters that perfectly fit a training set, but are useless outside of it. This kind of mistake is called overfitting.

Answer 3

With a sufficiently complex (or you might say overly complex or perhaps "very flexible" - think neural network) model, if you iterate long enough, you will overfit.

If you are using an insufficiently complex model, then you can iterate until the cost function no longer changes (for a standard logistic regression with a suitable loss function that's simply the maximum likelihood estimate) and will not overfit.

Overly complex is of course always relative to how much data you have. I.e. with lots of data it tends to be relatively harder to overfit than with less data for a given model.

Many logistic regression models will tend to be in the less complex bucket, but you people do also use logistic regression models with so many parameters that they are bound to overfit for a given dataset.