Is there any way to use nonseparable losses with XGBoost (or other boosting libraries)?

[alekfrohlich]

I am dealing with the following loss function: $\frac{1}{n(n-1)}\sum_{i\neq j} f(x_i, y_j)^2 - 2\frac{1}{n}\sum_{i=1}^n f(x_i, y_i)$. I would like to find a function f that minimizes this loss. It is possible to take a functional-gradient point of view towards the loss, however XGBoost doesn't seem to support nonseparable losses. Any suggestion?

[trivialfis]

Hi, it's not entirely clear to me what exactly is the loss function here ("nonseparable losses"?). From a high level, XGBoost works with pointwise gradient. As long as you can derive the pointwise gradient and hessian and the hessian is positive (maybe after some transformations), it should work with XGBoost.

[alekfrohlich]

Thanks for the quick reply!

By nonseparable I mean that the loss cannot be written as $\sum_{i=1}^n l(x_i, y_i)$ nor $\mathbb{E}[l(X,Y)]$, as can mean-squared error, for instance. The loss involves terms of the form $l(x_i, y_j)$ for $i != j$ and $l(x_i, y_i)$. If it were only $l(x_i, y_i)$, then it would be separable taking an IID dataset $(x_i, y_i)$ and loss $l$. If it were only $l(x_i, y_j)$ one could take the dataset to be IID of all pairs $(x_i, y_j)$ for $i != j$. The two terms together don't allow me to write $L = E[l(X,Y)]$; the loss constrasts between two distributions: $P_{XY}$ and $P_{X} \times P_{Y}$ (product of marginals, i.e., X and Y independent).

From https://xgboost.readthedocs.io/en/latest/tutorials/advanced_custom_obj.html:
"The function must be additive with respect to rows / observations, such as a likelihood function with i.i.d. assumptions."

The exact way I am doing things is I have $f(x,y) = <u(x),v(y)>$, where $u(x)$ and $v(y)$ take values in $R^d$ for some latent dimension d. The loss $L(u,v)$ is a functional loss on u and v, which can be written as $\mathbb{E}[L_X]$ or $\mathbb{E}[L_Y]$ where $L_x$ is a pointwise loss on $x$ and $L_y$ is a pointwise loss on $y$. It is possible to compute the gradients of these losses wrt to $u$ and $v$, i.e., $\nabla_{u(x)}L_x$ so that one can greedily update $u_t$ from $u_{t-1}$ using functional "coordinate-descent", alternating in $u$ and $v$. I have implemented this in Python for a research project, and it works, but I miss all the nice features from a mature boosting library to achieve competitive performance.

[trivialfis]

GitHub markdown supports using the $ tex notation for equations, I edited your comment to make it more readable. Hope that helps.

If you are looking for pariwise loss function, then it's not "conventional" loss functions that XGBoost work with. However, we have some similar objectives like learning to rank, which can be pairwise and even list wise. If you are not familiar with learning to rank, the gist is that one can calculate gradient for $\hat{y_i}$ based on a pair of samples, searching "pairwise learning to rank" or "lambdamart" should get you started, other examples are "listwise", which is not yet implemented in XGBoost yet, but it's all within the scope of the objective function.

That said, it will be a research project instead of out-of-the-box optimization problem.