# Definition of model complexity in XGBoost

I am having a hard time trying to understand the mathematical principle behind XGBoost. What really bothers me is the definition of the model complexity:

$$\Omega(f) = \gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2$$

Can someone tell me what $γ$ and $λ$ stand for?

• A good place to start would be to read about what the algorithm actually does. arxiv.org/pdf/1603.02754v3.pdf – Sycorax Aug 12 '16 at 15:42
• yes, the website is a simplified version with informal math descriptions. – Haitao Du Aug 12 '16 at 15:46
• I answered a very similar question here: stats.stackexchange.com/questions/178012/… – Matthew Drury Aug 12 '16 at 16:09
• @MatthewDrury what? exactly same question? we should mark this as duplicate – Haitao Du Aug 12 '16 at 16:16
• I wasn't completely confident of that, as this seems to ask for the definition of those parameters. I must admit, I'm sketchy on the definition of duplicate, and I tend to err on the conservative side of marking duplicates. – Matthew Drury Aug 12 '16 at 16:17

In general, model complexity can be defined as a function of number of free parameters: the more free parameters a model has, the more complex the model is. In addition, if a model has many parameters but we put many restrictions to them, so they are not that "free", it would also give us a "simpler" model. That is the key idea behind regularization.

There are different definitions of model complexity. AIC and BIC are widely used. In the link you provided, the notations are not standardized or widely used in statistics / machine learning fields but with some customization of author's preference. As mentioned in the document, $$T$$ is number of leaves in a boosting tree and $$w_i$$ is score for each leaves. So intuitively, the more leaves we have, the more free parameters we have, and the large the weights are the more complex the model is (which is similar to ridge regression)

To conclude, as mentioned in the original link, this is one way of defining the complexity (not a "standard way"), and the it penalize number of leaves and the weights of the leaves using L2 norm.

$$\gamma$$ is a threshold for the gain.

if the gain is smaller than $$\gamma$$, we would do better not to add that branch.

$$\lambda$$ is a regularization parameter.

The larger the $$\gamma$$ and $$\lambda$$ are the more regularization on the model / simpler the model is.

check this link and search gamma and lambda.

gamma [default=0] minimum loss reduction required to make a further partition on a leaf node of the tree. the larger, the more conservative the algorithm will be.

lambda [default=1] L2 regularization term on weights, increase this value will make model more conservative.