Consider gradient boosting like gbm or xgboost.
I have a labelled dataset (X,y). If I don't care about over-fitting and I allow gbm or xgboost grow as much as needed, eventually can I reach the accuracy of 100% in predicting in training dataset?
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.Sign up to join this community
A necessary condition for any method to achieve 100% accuracy on the training set is that there exists a one-to-one mapping from inputs to outputs for points in the training set. If this condition doesn't hold--that is, at least one input point occurs multiple times in the training set with different output values--then no method can achieve 100% accuracy.
Even if the above condition holds, gradient boosting can't achieve 100% accuracy on arbitrary datasets if the base models aren't sufficiently powerful. In particular, if linear base models are used, then the final ensemble model will also be linear. And, if the true relationship between inputs and outputs is nonlinear, then 100% accuracy isn't possible.
But, it's common to use decision trees as base models for gradient boosting, which are nonlinear. In this case (and assuming the above one-to-one condition is true), it is possible to achieve 100% accuracy on an arbitrary training set, provided we don't restrict model growth. For example, suppose we allow decision trees of unlimited depth. In this case, we can memorize the entire training set using a single decision tree, and achieve 100% accuracy in a single iteration. Of course, this runs a severe risk of overfitting, so a limit on tree depth is imposed. But, even if tree depth is limited, we can still memorize the training set (and achieve 100% accuracy) by using an unlimited number of trees (i.e. boosting iterations). So, to combat overfitting, a limit on the number of iterations is also needed. Other forms of regularization are typically imposed as well (e.g. shrinkage and subsampling of datapoints/features).