<p>I recommend <em><a href="https://books.google.ca/books?id=UH6XRoEQ4h8C" rel="nofollow">Neural Network Learning: Theoretical Foundations</a></em> 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2016-06-12T19:28:42.893Z
AFAIU, statisticians do study the statistical perspective. By "nobody" I guess you mean "no computer scientist".
Kaveh
CC BY-SA 3.0
2016-06-12T19:42:13.360Z
I think modern statisticians are very much aware of computational issues.
Aryeh
CC BY-SA 3.0
2016-06-12T19:45:13.693Z
I am not saying they are not :) I am not an expert on this but don't statisticians still study these problems without the computational complexity restrictions? That is at least my impression based on discussions I have had with ML people at our department.
Kaveh
CC BY-SA 3.0
2016-06-12T20:00:49.213Z
I'm also not an expert but I think it would be difficult to get a paper into, say, Ann. Stat., that was using an infeasible learning method. What's more reasonable is the use of oracles: call a black box to minimize some reasonable sample-dependent function. But JMLR publishes such papers also.
Aryeh
CC BY-SA 3.0
2016-06-13T09:09:36.597Z
Anthony and Bartlett seems like exactly the kind of book I was looking for.
Jack M
CC BY-SA 3.0
2016-06-12T19:03:15.903Z
2016-06-13T05:57:08.873Z
2016-06-13T05:57:08.873Z
Aryeh
<p>I can also recommend <em>Computational Learning Theory</em> by Kearns and Vazirani.</p>

<p>The book is general, not assuming any specific underlying structure to the learning algorithm like a neural net, instead it considers more generally algorithms for approximating functions based on sample training data.</p>

<p>The book seems very theoretical and rigorous, with proofs of NP-hardness and such results, Vapnik-Chervonenkis dimension, and a cute chapter on a theorem they call a formalized version of Occam's razor, which states (very) roughly that if a data sample is drawn from a probability distribution P, then the simplest (in a Kolmogorov-y sense) function consistent with that sample will have the best predictive power for future data drawn according to P.</p>

CC BY-SA 3.0
2016-08-20T21:57:39.287Z
2016-08-20T21:57:39.287Z
Jack M
<p>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.</p>

<p>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$.</p>

<p>What theorems exist to guarantee that we do indeed converge to $f$, or even that a network <em>exists</em> 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$.</p>

<p>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?</p>

CC BY-SA 3.0
2016-06-12T18:42:37.310Z
1. Computational learning theory and machine learning (practice) have a very small intersection. There are very few if any results of the type you describe about neutral networks. 2. For computational learning theory have a look at Kearns and Vazirani's book. 3. For machine learning pick a standard textbook, e.g. Bishop's or Murphy's.
Kaveh
CC BY-SA 3.0
2016-06-12T19:02:47.050Z
@Kaveh Well, I know for neural nets there is at least [this](https://en.wikipedia.org/wiki/Universal_approximation_theorem) theorem.
Jack M
CC BY-SA 3.0
2016-06-12T19:16:11.607Z
See Aryeh's answer below. There are three strands: 1. Computational learning theory which is part of theoretical computer science. It is mathematically rigorous and cares about computational complexity of learning algorithms but the results are for general distributions and almost everything interesting in practice is shown to be hard to learn under general distributions. 2. Statistics which typically ignores the computation complexity aspects of learning algorithms.
Kaveh
CC BY-SA 3.0
2016-06-12T19:19:51.297Z
3. Machine learning which cares only about distributions in practice which are hard to model rigorously. They seldom have mathematical theorems showing efficiency of algorithms or convergence because their algorithms often only work on those specific practical distributions which are hard to model mathematically and prove theorems about. Algorithms are typically compared based on how they well perform on benchmarks, e.g. a new break through algorithm might perform 5% better than the best previous algorithms but no rigorous theorem is given why it performs better.
Kaveh
<machine-learning>
Convergence and representation theorems for machine learning
Jack M
# Convergence and representation theorems for machine learning

(Asked by: username_0 on 2016-06-12)

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?

**Tags:** machine-learning

> **Comments:**
> **username_1**: 1. Computational learning theory and machine learning (practice) have a very small intersection. There are very few if any results of the type you describe about neutral networks. 2. For computational learning theory have a look at Kearns and Vazirani's book. 3. For machine learning pick a standard textbook, e.g. Bishop's or Murphy's.  
> **username_0**: @username_1 Well, I know for neural nets there is at least [this](https://en.wikipedia.org/wiki/Universal_approximation_theorem) theorem.  
> **username_1**: See username_2's answer below. There are three strands: 1. Computational learning theory which is part of theoretical computer science. It is mathematically rigorous and cares about computational complexity of learning algorithms but the results are for general distributions and almost everything interesting in practice is shown to be hard to learn under general distributions. 2. Statistics which typically ignores the computation complexity aspects of learning algorithms.  
> **username_1**: 3. Machine learning which cares only about distributions in practice which are hard to model rigorously. They seldom have mathematical theorems showing efficiency of algorithms or convergence because their algorithms often only work on those specific practical distributions which are hard to model mathematically and prove theorems about. Algorithms are typically compared based on how they well perform on benchmarks, e.g. a new break through algorithm might perform 5% better than the best previous algorithms but no rigorous theorem is given why it performs better.  

---

## 2 answers

### Answer by username_2 on 2016-06-12. Score: 4 | Accepted answer

I recommend *[Neural Network Learning: Theoretical Foundations](https://books.google.ca/books?id=UH6XRoEQ4h8C)* 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.

> **Comments:**
> **username_1**: AFAIU, statisticians do study the statistical perspective. By "nobody" I guess you mean "no computer scientist".  
> **username_2**: I think modern statisticians are very much aware of computational issues.  
> **username_1**: I am not saying they are not :) I am not an expert on this but don't statisticians still study these problems without the computational complexity restrictions? That is at least my impression based on discussions I have had with ML people at our department.  
> **username_2**: I'm also not an expert but I think it would be difficult to get a paper into, say, Ann. Stat., that was using an infeasible learning method. What's more reasonable is the use of oracles: call a black box to minimize some reasonable sample-dependent function. But JMLR publishes such papers also.  
> **username_0**: Anthony and Bartlett seems like exactly the kind of book I was looking for.  

---

### Answer by username_0 on 2016-08-20. Score: 2

I can also recommend *Computational Learning Theory* by Kearns and Vazirani.

The book is general, not assuming any specific underlying structure to the learning algorithm like a neural net, instead it considers more generally algorithms for approximating functions based on sample training data.

The book seems very theoretical and rigorous, with proofs of NP-hardness and such results, Vapnik-Chervonenkis dimension, and a cute chapter on a theorem they call a formalized version of Occam's razor, which states (very) roughly that if a data sample is drawn from a probability distribution P, then the simplest (in a Kolmogorov-y sense) function consistent with that sample will have the best predictive power for future data drawn according to P.


---

