computational complexity?

[ramin]

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]

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

[ramin]

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]

Originally Posted by ramin

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]

• 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