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.
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$.