# XGBoost question on weighted quantile sketch described in paper

The right-hand-side of Equation (3) in the XGBoost paper is $$\sum_{i=1}^n [g_i f_t(\mathbf{x}_i)+\frac{1}{2}h_if_t^2(\mathbf{x}_i)]+\Omega(f_t) \tag{3}$$

In the Section 3.3 "Weighted Quantile Sketch" it is stated this can be re-written (See just after equation (9)) $$\sum_{i=1}^n \frac{1}{2} h_i \left( f_t(\mathbf{x}_i)- \frac{g_i}{h_i} \right)^2 + \Omega(f_t)+const$$ and I don't see how they get this.

Equation (3) obviously equals $$\sum_{i=1}^n \frac{1}{2} h_i[2 \frac{g_i}{h_i} f_t(\mathbf{x}_i)+f_t^2(\mathbf{x}_i)]+\Omega(f_t)$$ Straightforward completing-the-square in this however yields a term $$(f_t(\mathbf{x}_i)+ \frac{g_i}{h_i})^2$$ which doesn't agree with the re-written squared loss form.

To generate the squared loss and match the re-written form it seems one would get $$\sum_{i=1}^n \frac{1}{2} h_i [ \left( f_t(\mathbf{x}_i)- \frac{g_i}{h_i} \right)^2 - \frac{{g_i}^2}{{h_i}^2} +4 \frac{g_i}{h_i}f_t ]+\Omega(f_t)$$ but this does not appear to add a constant due to the $$f_t$$.

How is this explained?

They most likely have a typo in the sign. It should be $$\sum_i\frac12 h_i(f_t(x_i) +g_i/h_i)^2$$ instead of $$\sum_i\frac12 h_i(f_t(x_i) - g_i/h_i)^2$$. It is a weighted square loss between $$f_t(x_i)$$ and labels $$-g_i/h_i$$.
In general the minimizer of $$w \mapsto \sum_i \alpha_i (w - \beta_i)^2$$ is $$w^* = \sum_i \alpha_i \beta_i / (\sum_i \alpha_i)$$.
In this problem, ignoring the regularizer, and assuming all the data are at the same leaf node, we are minimizing $$w \mapsto \sum_i h_i(w + g_i/h_i)^2$$ whose solution is $$w^* = \frac{\sum_i h_i(-g_i/h_i)}{\sum_i h_i} = - \frac{\sum_i g_i}{\sum_i h_i}.$$