<p>Let me attempt to partly answer the learning part, or to at least address some connections.
In <a href="http://en.wikipedia.org/wiki/Probably_approximately_correct_learning" rel="noreferrer">learning</a> (distributional issues aside), we usually want our algorithms to be able to not only <em>approximate</em> the target function (from a class) with a hypothesis, but also to be able <em>find</em> such a hypothesis (efficiently).  So, even though a certain class can universally approximate a given target, we are not done.</p>

<p>I am not an expert in neural networks, but training a neural network is not easy.  We have algorithms for training a neural network, like <a href="http://en.wikipedia.org/wiki/Backpropagation" rel="noreferrer">backpropogation</a>, but they won't always converge, or converge quickly enough, to meet the PAC learning criteria.
<a href="http://en.wikipedia.org/wiki/Boosting" rel="noreferrer">Boosting</a>, on the other hand says (roughly) how to turn a weak "approximator" into a strong one, but it in some sense assumes the difficulty away but giving the learner access to the weak approximator.</p>

CC BY-SA 2.5
2011-01-31T00:21:17.923Z
Thanks @Lev! This is very helpful. I'll look into PAC more carefully. Are there any other mathematical frameworks besides PAC that are used to study the tractability and approximation power of learners? Is PAC the de-facto learning theory?
Amelio Vazquez-Reina
CC BY-SA 2.5
2011-01-31T01:02:57.597Z
In some sense approximation doesn't fit so well into the PAC model because of ideas like boosting.  Once you can do (bounded) better than half, you can do arbitrarily well.  So when people talk about approximation in learning, they talk about approximating other types of things -- like the size of the best consistent hypothesis.  But, yes, when people say "learnable" they usually mean "PAC learnable."  There are, of course, many other models of learning: learning with membership and equivalence, online learning, reinforcement learning, active learning & more.  Each has its own conditions, etc.
Lev Reyzin
CC BY-SA 2.5
2011-01-30T18:19:58.807Z
2011-01-30T18:19:58.807Z
Lev Reyzin
<p>A decision tree is a simple function essentially.
According to the simple function approximation lemma, decision tree is universal approximator. 
See <a href="http://mathonline.wikidot.com/the-simple-function-approximation-theorem" rel="nofollow noreferrer">http://mathonline.wikidot.com/the-simple-function-approximation-theorem</a> for more details on simple function approximation lemma.</p>

CC BY-SA 4.0
2020-02-27T15:40:06.880Z
2020-03-05T13:37:12.823Z
2020-03-05T13:37:12.823Z
张子一
<p>I have an applied machine-learning and statistics background, and when I read the <a href="http://en.wikipedia.org/wiki/Cybenko_theorem" rel="noreferrer">Universal approximation theorem</a>, which (in the context of the learning theory of ANNs - Artificial Neural Networks) states (Wikipedia): </p>

<blockquote>
  <p>"the standard multilayer feed-forward
  network with a single hidden layer
  that contains finite number of hidden
  neurons, and with arbitrary activation
  function are universal approximators
  on a compact subset of $R^n$. "</p>
</blockquote>

<p>I wondered if there are any similar results (in terms of approximation power) for other types of learners (e.g. decision trees, boosting methods, SVMs, etc.). </p>

<p>This leads me to a second but related question: Is this a topic that is formally studied in TCS? If so, are there any good texts for somebody with an applied background?</p>

<p>Thanks</p>

<lg.learning><machine-learning>
Results on universal approximation for learners other than ANNs
Amelio Vazquez-Reina
# Results on universal approximation for learners other than ANNs

(Asked by: username_0 on 2011-01-30)

I have an applied machine-learning and statistics background, and when I read the [Universal approximation theorem](http://en.wikipedia.org/wiki/Cybenko_theorem), which (in the context of the learning theory of ANNs - Artificial Neural Networks) states (Wikipedia):

> "the standard multilayer feed-forward
> network with a single hidden layer
> that contains finite number of hidden
> neurons, and with arbitrary activation
> function are universal approximators
> on a compact subset of $R^n$. "

I wondered if there are any similar results (in terms of approximation power) for other types of learners (e.g. decision trees, boosting methods, SVMs, etc.).

This leads me to a second but related question: Is this a topic that is formally studied in TCS? If so, are there any good texts for somebody with an applied background?

Thanks

**Tags:** lg.learning, machine-learning

---

## 2 answers

### Answer by username_1 on 2011-01-30. Score: 5

Let me attempt to partly answer the learning part, or to at least address some connections.
In [learning](http://en.wikipedia.org/wiki/Probably_approximately_correct_learning) (distributional issues aside), we usually want our algorithms to be able to not only *approximate* the target function (from a class) with a hypothesis, but also to be able *find* such a hypothesis (efficiently). So, even though a certain class can universally approximate a given target, we are not done.

I am not an expert in neural networks, but training a neural network is not easy. We have algorithms for training a neural network, like [backpropogation](http://en.wikipedia.org/wiki/Backpropagation), but they won't always converge, or converge quickly enough, to meet the PAC learning criteria.
[Boosting](http://en.wikipedia.org/wiki/Boosting), on the other hand says (roughly) how to turn a weak "approximator" into a strong one, but it in some sense assumes the difficulty away but giving the learner access to the weak approximator.

> **Comments:**
> **username_0**: Thanks @Lev! This is very helpful. I'll look into PAC more carefully. Are there any other mathematical frameworks besides PAC that are used to study the tractability and approximation power of learners? Is PAC the de-facto learning theory?  
> **username_1**: In some sense approximation doesn't fit so well into the PAC model because of ideas like boosting.  Once you can do (bounded) better than half, you can do arbitrarily well.  So when people talk about approximation in learning, they talk about approximating other types of things -- like the size of the best consistent hypothesis.  But, yes, when people say "learnable" they usually mean "PAC learnable."  There are, of course, many other models of learning: learning with membership and equivalence, online learning, reinforcement learning, active learning & more.  Each has its own conditions, etc.  

---

### Answer by username_2 on 2020-02-27. Score: 1

A decision tree is a simple function essentially.
According to the simple function approximation lemma, decision tree is universal approximator.
See <http://mathonline.wikidot.com/the-simple-function-approximation-theorem> for more details on simple function approximation lemma.


---

