Why large basis sets give better approximations to the exact solution of the Schrödinger equation?
The statistics analogy may not be applicable, but it illustrates what
  goes on in my head.


The overfitting analogy is indeed not applicable here. It is a totally different and unrelated phenomenon. Basically, when we are doing regression analysis we do not know the relationship between a dependent variable and independent variables. Then we can indeed have an overfitting problem when instead of fitting the actual relationship we start to describe some random noise. It generally happens when we do have too many parameters in a model, and we never know how many is too many. 

But when we are doing LCAO-MO we know the relationship between a dependent variable (say, energy) and independent variables (LCAO-MO fficients). ANd we are certain that the bigger the number of AOs (and correspondingly of the coefficients), the better result could be expected with the the exact solution corresponding to using infinitely many AOs. So we should not worry about anything like overfitting. Yes, by increasing the number of AOs in a basis set we increase the number of variational parameters, but we know it can't do any harm: in the worst case1 we will get the same energy as before the just another expansion of the basis.

This is similar to a Taylor series expansion of a function. The exact result corresponds to an infinite series, and by using a finite number of terms a function can only be approximated. But the more terms we use, the better approximation is. There is even a formal proof, but I think it should be intuitively clear that if an infinite series is the exact solution, than the later you truncate it the better approximation you get.



1) The worst case would be, for instance, when you expand a basis by including new functions that can be expressed as linear combinations of basis functions from the previously used basis set. You won't improve energy by doing so, but only increase the computational time. Note, that most of the programs have a simple defense mechanism against such situations: they are smart enough to detect the linear dependence in the basis and get rid of it prior to doing the calculations.