choice between splines and polinomial interpolation (either Newton or Lagrange - deterministic ones) stops at really huge data - splines are more flexible ("using many polynomials in a piecewisepiece-wise function rather than defining one overall polynomial")...
And the problem of overfitting is really the problem of another causes (see marked answer - as of stat. view or here as of ML view) - can create your own ML-solution or NeuralNetwork with keras or tensorflow