<p>I became familiar with the BSS model of computation recently. 
I find it to be a better model of computation to study complexity of numerical analysis methods (cf. Complexity and Real Computation; Blum, Cucker, Shub, Smale.) </p>

<p>Most of the existing PAC learning theory is concerned with standard computation model. I was wondering, </p>

<blockquote>
  <p>are there any research or literature regarding PAC learning in the BSS model?</p>
</blockquote>

<p>The reason is that most of practical methods of computation over real numbers are based on numerical analysis which seem disconnected from the standard PAC learning developed in TCS community. Whereas the BSS model seems natural and well-suited for such studies.  </p>

CC BY-SA 3.0
2013-03-29T10:26:00.940Z
Have you looked at http://www.svms.org/learnability/ABCH97.pdf or http://users.cecs.anu.edu.au/~williams/papers/P53.pdf ?
Aryeh
CC BY-SA 3.0
2013-03-30T00:40:22.010Z
Aryeh, thanks for the links - they are statistical results  as they point out in the paper-(This analysis of learnability is purely information-theoretic, and does not take into account computational complexity.) I was more interested in computational complexity results. For e.g., Exact NMF is known to be [hard](http://arxiv.org/pdf/0708.4149.pdf) in standard turing model and BSS model. I guess what I was trying to ask was if the the known hardness results about pac learning extend to other fields in general (and to reals specifically)
kumar
<cc.complexity-theory><reference-request><machine-learning><lg.learning>
PAC learning and computation over real numbers
kumar
# PAC learning and computation over real numbers

(Asked by: username_0 on 2013-03-26)

I became familiar with the BSS model of computation recently.
I find it to be a better model of computation to study complexity of numerical analysis methods (cf. Complexity and Real Computation; Blum, Cucker, Shub, Smale.)

Most of the existing PAC learning theory is concerned with standard computation model. I was wondering,

> are there any research or literature regarding PAC learning in the BSS model?

The reason is that most of practical methods of computation over real numbers are based on numerical analysis which seem disconnected from the standard PAC learning developed in TCS community. Whereas the BSS model seems natural and well-suited for such studies.

**Tags:** cc.complexity-theory, reference-request, machine-learning, lg.learning
> **Comments:**
> **username_1**: Have you looked at http://www.svms.org/learnability/ABCH97.pdf or http://users.cecs.anu.edu.au/~williams/papers/P53.pdf ?  
> **username_0**: Aryeh, thanks for the links - they are statistical results  as they point out in the paper-(This analysis of learnability is purely information-theoretic, and does not take into account computational complexity.) I was more interested in computational complexity results. For e.g., Exact NMF is known to be [hard](http://arxiv.org/pdf/0708.4149.pdf) in standard turing model and BSS model. I guess what I was trying to ask was if the the known hardness results about pac learning extend to other fields in general (and to reals specifically)  

---

## 0 answers

