View Single Post
Old 01-28-2013, 11:45 AM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Q5, K dependency on N?

Originally Posted by palmipede View Post
Speaking of computational complexity, some hard problems like boolean satisfiability (e.g. 3-SAT) have been observed to have easy solution times for the average random instances of the problem but is no practical upper bound on the solution times of the worst cases.

I wonder what does that mean for learning? Are there known cases of phase transition in learning time?
An example in machine learning is that finding the global minimum in neural networks has been shown to be NP-hard, but simple algorithms like stochastic gradient descent (leading to backpropogation) with some heuristics work fine in practice to find good local minima.
Where everyone thinks alike, no one thinks very much
Reply With Quote