Convergence and representation theorems for machine learning I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology.

Let's say we have a function $f:X \to Y$, and we want to develop a neural network to compute this function. For instance, $X$ could be $\{0, 1, ... 255\}^N$ for some large $N$, and $Y$ could be $\{0, 1\}$, if we wanted to build a network that performs a binary classification on images of $N$ pixels. We have some algorithm which adjusts, maybe stochastically or maybe deterministically, the weights and parameters of our network, creating a sequence of networks which should converge to $f$.

What theorems exist to guarantee that we do indeed converge to $f$, or even that a network exists to represent $f$? If we don't want to make assumptions about $f$, we would need some theorem establishing that given any function $f$, and any initial network, the sequence of networks generated by the learning algorithm will converge to $f$.

I'm not just interested in neural nets, though. Are there textbooks on machine learning which cover this sort of thing in depth? What keywords should I be looking out for?
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.