They are not the same problem but they are highly related:

If you have a very good heuristic, then search is trivial, and learning good heuristics from data is a prediction problem.
On the other hand, prediction problems such as Structured prediction (the stuff LeCun does) entail search, and moreover most machine learning algorithms also require some kind of search in the training phase.