I would agree that as a science machine learning is in its infancy. There's statistical learning theory, but arguably that's a fairly small subfield, if not a separate field completely. ML has largely been an engineering enterprise so far, but in my experience the interest in developing underlying theory has ramped up in recent years.

What we should be careful about is to not be too strict when defining "science". In my view the goal of any scientific field is to build understanding that is useful for predicting outcomes of experiments. Now, this understanding could be defined mathematically, but it doesn't have to be. Don't see why building heuristics can't be a part of this, assuming such heuristics reliably predict outcomes of experiments.