Can I use a tiny Validation set? I understand the reasoning behind splitting the data into a Test set and a Validation set. I also understand that the size of the split will depend on the situation but will generally vary from 50/50 to 90/10.
I built a RNN to correct spelling and start with a data set of ~5m sentences. I shave off 500k sentences and then train with the remaining ~4.5m sentences. When the training is done I take my validation set and compute the accuracy.
The interesting thing is that after only 4% of my validation set I have an accuracy of 69.4% and this percentage doesn't change by more than 0.1% in either direction. Eventually I just cut the validation short because the number is stuck at 69.5%.
So why slice off 10% for Validation when I could probably get away with 1%? Does it matter?
 A: In the article Asymptotic Statistical Theory of Overtraining and Cross-Validation by Shun-ichi Amari et al. [1] they study the optimal amount of samples to leave out as a validation set (for the purpose of early stopping) and conclude that the optimal split is $1/\sqrt{2N}$, where $N$ is the number of samples available. In your case $N=5\cdot10^6$ and the optimal split is $\approx 0.00032=0.032\%$. According to the formula 1580 samples should be optimal in your case.
[1] https://www.ncbi.nlm.nih.gov/pubmed/18255701
A: Larger validation sets give more accurate estimates of out-of-sample performance. But as you've noticed, at some point that estimate might be as accurate as you need it to be, and you can make some rough predictions as to the validation sample size you need to reach that point.
For simple correct/incorrect classification accuracy, you can calculate the standard error of the estimate as $\sqrt{p(1−p)/n}$ (standard deviation of a Bernouilli variable), where $p$ is the probability of a correct classification, and $n$ is the size of the validation set. Of course you don't know $p$, but you might have some idea of its range. E.g. let's say you expect an accuracy between 60-80%, and you want your estimates to have a standard error smaller than 0.1%:
$$
\sqrt{p(1−p)/n}<0.001
$$
How large should $n$ (the size of the validation set) be? For $p=0.6$ we get:
$$
n > \frac{0.6-0.6^2}{0.001^2}=240,000
$$
For $p=0.8$ we get:
$$
n > \frac{0.8-0.8^2}{0.001^2}=160,000
$$
So this tells us you could get away with using less than 5% of your 5 million data samples, for validation. This percentage goes down if you expect higher performance, or especially if you are satisfied with a lower standard error of your out-of-sample performance estimate (e.g. with $p=0.7$ and for a s.e. < 1%, you need only 2100 validation samples, or less than a twentieth of a percent of your data).
These calculations also showcase the point made by Tim in his answer, that the accuracy of your estimates depends on the absolute size of your validation set (i.e. on $n$), rather than its size relative to the training set. 
(Also I might add that I'm assuming representative sampling here. If your data are very heterogeneous you might need to use larger validation sets just to make sure that the validation data includes all the same conditions etc. as your train & test data.)
A: Nice discussion of this problem is provided by Andrew Ng on his Deep Learning course on Coursera.org. As he notes, the standard splits like 8:2, or 9:1 are valid if your data is small to moderately big, but many present day machine learning problems use huge amounts of data (e.g. millions of observations as in your case), and in such scenario you could leave 2%, 1%, or even less of the data as a test set, taking all the remaining data for your training set (he actually argues for using also a dev set). As he argues, the more data you feed your algorithm, the better for its performance and this is especially true for deep learning* (he also notes that this must not be the cases for non-deep learning machine learning algorithms).
As already noticed in comment by Alex Burn, it is not really about size of your test set, but about its representativeness for your problem. Usually with larger size of the data we hope for it to be more representative, but this does not have to be the case. This is always a trade-off and you need to make problem-specific considerations. There is no rules telling that test set should not be less then X cases, or less then Y% of your data.
* - Disclaimer: I am repeating Andrew Ng's arguments in here, I wouldn't consider myself as a specialist in deep learning.
