Regularization in Neural networks

One way to regularize a neural network is "early stopping" , meaning that I don't let the weights get to their optimal values (based on the cost function calculated on the training data) but stop the gradient descent process before they do. I understand why it's true when using batch gradient descent because I just stop the optimization process on all samples after i.e 10 iterations instead of 50. What I don't understand is how can it be true when using online gradient descent? It means that I stop the process before using all of my samples. It seems like a paradox that when wanting to regularize in order to solve a high variance problem I stop the learning process before using all samples,when in order to solve a high variance problem I would actually want to use as many samples as possible.

• in order to avoid over-fitting I would actually want to use as many samples as possible Is that what you mean, or is it a typo? Perhaps in order to avoid under-fitting or in order to reduce variance or something like that? Apr 21, 2015 at 19:22
• Maybe I'm wrong but what I understood is that if someone has already decided how many parameters I will have in my hidden layer, training on more samples won't hurt me. It will help me in a high variance-low bias problem and it won't help me(but won't hurt me either) in high bias-low variance problem. by overfitting I mean "degradation in performance on test set due to high variance".I will edit. Apr 21, 2015 at 20:06

Just a guess, but training using something like SGD (which can be considered a type of online learning, in the sense that it sees only a fraction of the data at a time) looks like this w.r.t. the objective function.

That is, the "trajcetory" of the objective is declining, but it's stochastically bouncing around. Early stopping means you're picking a point earlier in that trajectory, with parameters that are "suboptimal" in the sense that lower entropy could be obtained on the training data with further training and fine-tuning of parameter estimates.

Later in your question, you write that you expect more samples can avoid over-fitting. More training samples can provide more precise parameter estimates, but can't prevent over-fitting on its own. Especially in the case of neural nets, the NN can learn a very complicated function (in the presence of almost any amount of data), but that function may not generalize well to unseen data.

Consider a continuum from an underfit model to an optimal model to an overfit model. More training data can move you from underfit to optimal, but moving from optimal to overfit can happen because of a failure to regularize; in the early-stopping paradigm, that means using all available data.

Note that there are alternative strategies to addressing overfitting in neural nets, though. One approach is to place a prior over the parameters that penalizes values further from 0. This is usually expressed as adding a term $\lambda\sum_i w_i^2$ to the objective function, where $w$ is the vector of weights, i.e. a 0-mean Gaussian prior over each $w_i$, with variance controlled via $\lambda$. Cross-validation is used to select the optimal $\lambda$.

• Of course I'm considering the out-of-sample performance. The cost function of the test set (or cv set) should decrease when using more samples. Have a look at slide 27 in the following link: d396qusza40orc.cloudfront.net/ml/docs/slides/Lecture10.pdf Apr 21, 2015 at 19:13
• Sure. But I'm thinking about a continuum from an underfit model to an optimal model to an overfit model. More training data can move you from underfit to optimal, but moving from optimal to overfit can happen because of a failure to regularize; in the early-stopping paradigm, that means using all available data.
– Sycorax
Apr 21, 2015 at 19:20
• Note that slide 29 states that getting more training samples is a solution to high variance; an alternative cause for poor fit would not be addressed by this solution.
– Sycorax
Apr 21, 2015 at 19:40
• Right,But I'm assuming this very case of high variance. So person A tells me: "Be wise - Regularize!"(last solution to high variance in slide 29) so I'm coming to stop my online learning early but then person B shouts: "stop! more samples will surely help you!"(first solution to high variance in slide 29), so which one is right? Apr 21, 2015 at 19:58
• BTW, the regularization you suggested and early stopping are equivalent (refer to pages 259-260 in Bishop). Apr 21, 2015 at 19:59