Is machine learning an heuristic method? I'm asking this out of curiosity.
In the past I have thought of an heuristic as a "quick and dirty" rule not based on data analysis, as opposed to a solution which uses machine learning or statistical models.
For example imagine I have the following classification problem: are products listed in different e-commerce websites the same physical product? 
One could simply define an initial heuristic that if product titles similarity is below an arbitrary level than products are considered different otherwise they are considered the same. This would be what I call an heuristic.
On the other hand, tagging data, training a model and cross validate to get best threshold to classify products is NOT an heuristic. 
However if I read Wikipedia definition of Heuristic it says that it is a practical method that does not guarantee to be optimal or perfect. This seems very general and it seems that it could be extended to machine learning.
Can anyone help me understand the distinction a bit better?
 A: There are parts that are heuristic in machine learning, e.g. the choice of variables (inputs) and topology of the neural net. However, to call the whole thing heuristic would be wrong, since there's optimization involved. 
For instance, if you said "we observed that customers who who by apples are twice likely to buy pears too, hence let's offer them pears in the online store" - this would be a heuristic. If instead you gathered all the data on customer behavior, and run a machine learning algo to come up with shopping suggestions that would not be a heuristic anymore. 
However, as I wrote in the beginning, your decision to not include the current outside temperature into the variable (feature) list would be based on heuristic, most likely.
A: The problem with this kind of definition is that it is ambiguous and can be understood differently by different people and in different contexts. Wikipedia says that,

heuristic, is any approach to problem-solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals.

How do you know that the solution is optimal or perfect? When you are dealing with random phenomena, then you cannot get "perfect" results (i.e., always correct). What machine learning algorithms give you, is the "best you can get" results, given certain conditions are met. Moreover, each of the algorithms that are commonly used gives you some guarantees for optimality in certain scenarios (if they didn't, we wouldn't use them).
Heuristics have very similar, though more precise, meaning in computer science, tl;dr: they are algorithms that seek an approximate, opinionated solution rather than the exact one. In machine learning, there is usually no exact solutions, so it is not achievable by any algorithm.
A: It is surprisingly hard to formalize what is meant by 'algorithm'; Wikipedia has a nice summary here. Some definitions require an algorithm to provably produce correct output every single time (or with some bounded guarantee). 
In that sense, the applications of machine learning are usually heuristic. There is no way to prove that a customer will definitely buy the items your recommender system suggests, or that the presence/absence of certain keywords distinguishes spam from valid email. Thus, a function like bool is_spam(std::string email_text, Model &mdl) is a heuristic.
On the other hand, the...procedure implemented in that function, or the ones that finds the support vectors of your SVM, updates the weights of your deep network, collates n-grams, etc. are often algorithms. You can prove, for example, that stochastic gradient descent will stop at a local minimum (e.g., like this). The heuristic part comes from using that local minimum to solve a practical problem.
Some classification "systems" also have heuristic pieces. For example, the training data might be smoothed or segmented in some way that happens to work well for typical inputs, but isn't provably optimal. 
