Theoretical error bounds of classification and regression trees So, some algorithms were motivated by theoretical work, such as in the case of boosting.
Adaboost was introduced as an algorithm for solving the hypothesis boosting problem.
The bounds on the training error and generalization error were formulated along many other extensions and explanations about how and why the algorithm works.
My questions: 1.) Regarding classification and regression tress (CART), would it be correct to say that learning a decision tree was motivated by data and not by theory?
2.) Regarding classification and regression tress, are there theoretical bounds on the training and testing errors? If so a reference would be great.
 A: 
would it be correct to say that learning a decision tree was motivated by data and not by theory?

It depends on what you mean by "motivated by data". There are many different tree building algorithms that have been devised, some with more theoretical underpinnings / justification than others. We tend to define a decision tree as being good by it having the lowest possible depth to obtain the best accuracy, which is NP-hard. So its not an easy problem to solve. All of our difference tree inducing algorithms can be seen as different feeble attempts at producing heuristics for a difficult problem. Though some of the more recent (if rarer) decision tree papers have more theoretical results (See the Extra Trees paper as an example). 
k-means is an algorithm similar to decision trees in that we had an initial idea, quickly proved that it was very difficult - and simple came up with heuristics until it worked. Only recently did we get some more theoretical results (k-means++) of real use, but still - its comes off as a very "well, it works!" kinda method. 

Regarding classification and regression tress, are there theoretical bounds on the training and testing errors? If so a reference would be great.

There appear to be some, but I don't know how many exist. Especially considering the many different tree learning methods.
