LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   General Discussion of Machine Learning (http://book.caltech.edu/bookforum/forumdisplay.php?f=105)
-   -   computational complexity? (http://book.caltech.edu/bookforum/showthread.php?t=1186)

ramin 08-28-2012 11:52 AM

computational complexity?
 
Hi,

Professor Abu-Mostafa at times mentions computational complexity of different learning tasks (for example,I think he mentioned general solution to RBF with the width parameters is NP hard?). In addition, he sometimes refers to function approximation formulations of certain problems. Are there good introductory references to these two topics ?

yaser 08-28-2012 12:31 PM

Re: computational complexity?
 
Since these are pretty standard terms nowadays, I suggest you start with wikipedia for an introduction and follow up the references as needed.

ramin 08-28-2012 09:34 PM

Re: computational complexity?
 
Hi, sorry. I probably wasn't clear. I'm familiar with concepts of computational complexity but not with the proofs that are specific to the machine learning problems.

yaser 08-28-2012 10:09 PM

Re: computational complexity?
 
Quote:

Originally Posted by ramin (Post 4564)
Hi, sorry. I probably wasn't clear. I'm familiar with concepts of computational complexity but not with the proofs that are specific to the machine learning problems.

Got it. There is a book by Steven Judd in the 1980's that started this line of work. There are also more general results proving certain optimization problems are NP-hard. They are almost folklore now, but let me try to look up specific references.

vksheilds 08-31-2012 06:46 AM

Re: computational complexity?
 
  • A resource for outstanding research in computational complexity
  • Covers models of computation, complexity bounds, complexity classes and more
  • Explores the structure of complexity classes, algebraic complexity, cryptography and issues in robotics, logic and distributed computing


All times are GMT -7. The time now is 05:30 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.