#1




computational complexity?
Hi,
Professor AbuMostafa 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 ? 
#2




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.
__________________
Where everyone thinks alike, no one thinks very much 
#3




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.

#4




Re: computational complexity?
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 NPhard. They are almost folklore now, but let me try to look up specific references.
__________________
Where everyone thinks alike, no one thinks very much 
#5




Re: computational complexity?

Thread Tools  
Display Modes  

