Is it a good strategy to train on a small train set, letting it overfit, then adding more training data and repeating ad infinitum? This may be a silly idea. I have a huge dataset with billions of data points, and it would take a long time to run an epoch over all the data set. So
I was thinking of using the following strategy:


*

*Train a deep NN on a small sample of the data, constantly saving checkpoint models,
and stop it when validation loss plateaus.

*Take the best model from step 1, append new data to the training set, and train again until validation loss plateaus.

*Repeat steps 1 and 2.


My intuition is as follows: perhaps I don't need to use all the data to train a model. Therefore, at every point, the model learns what it can from the small dataset (without overfitting), and once it starts to overfit we simply give it mor data. This strategy would ensure that the model takes only the minimum amount of data needed to ensure a good model, and would decrease training time.
Is this a coherent strategy? Would this be a faster way of training, or would it introduce some variance?
 A: You've more-or-less described a learning curve: a plot of the (average) performance of a model against varying amounts of training data.  As you've suggested, at a certain point, additional data is not going to help you extract more signal from whatever phenomenon you're studying. Learning curves can be useful to make inferences about how much data is required for a specific problem before you reach a point of diminishing returns.
Learning curves do not include a step of "overfitting" the data, though. The way that a learning curve works is that for each size of training data, you repeat your procedure of model fitting (e.g. cross-validation to select regularization parameters) and report the best out-of-sample performance of the model selected by your procedure. You may repeat this step several times and take the average, using different training data each time. Then you repeat this process, for all training data sizes of interest. 
Learning curves are described briefly in Elements of Statistical Learning and How large a training set is needed?
A: If your goal is to avoid training on a massive dataset, I don't see any advantages to this method over simply training on subsamples of your larger dataset. i.e. What is the advantage of training over a small, fixed subsample $X_F$ over 10 epochs rather than training on 10 different (random) subsamples of the same size $X_1 ... X_{10}$ ? The obvious disadvantage is that you expose your model to less data.
