In the cases where there are no physical-world measurements, as with inputs and outputs to many machine learning problems, it is math. "Experiments" using randomized algorithms and measuring the results, themselves, certainly don't qualify as science.
In the twentieth century we learned that math is bigger than we can possibly handle with anything like traditional mathematical rigor. There is no contradiction in saying one is running an experiment on math when it is not possible even in theory to obtain the result of the experiment through any means more efficient than simply running the experiment. And given Computer Science's focus on things that are, generally, Turing Complete, proving that that is frequently the case is a sophomore-level homework problem in any decent curriculum. (See "Rice's Theorem".)
The idea of "math" you get in school is not wrong, but very incomplete. "Experimental math" is a perfectly valid field of study; mathematics itself proved it, about a hundred years ago. Theories are made, predictions are given, and there's no way to prove or disprove them until the experiment is run, at which point you still only have evidence, not proof (in general); sounds pretty scientific to me.
