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.

  • $\begingroup$ Have you looked at svms.org/learnability/ABCH97.pdf or users.cecs.anu.edu.au/~williams/papers/P53.pdf ? $\endgroup$ – Aryeh Mar 29 '13 at 10:26
  • $\begingroup$ 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 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) $\endgroup$ – kumar Mar 30 '13 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.