XGBoost question on weighted quantile sketch described in paper

Question

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?

Answer 1

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$.

You can see the negative sign in the solution of the optimization problem in (5).

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}. $$