Convergence and representation theorems for machine learning
I recommend Neural Network Learning: Theoretical Foundations by Anthony and Bartlett. You'll find exhaustive answers to your questions there. Very briefly, theoretical learning problems tend to separate very cleanly into two orthogonal components: statistical and computational. Thus, a universal learner unconstrained by computational issues could construct the smallest Turing machine (or MATLAB program) consistent with the input data; such a learner would be near-optimal statistically in a well-defined sense.

Nobody studies such learners (beyond intro-class homework problems) because they are computationally infeasible (actually uncomputable, in my example). When computational constraints enter the picture, it becomes much more nuanced: often times, what is the obvious course of action for the statistician is dismissed out of hand as infeasible by the algorithmist.

In any case, the Anthony+Bartlett book seems like the perfect introduction for a mathematically inclined beginner.