What is non-decomposable and/or non-differentiable loss function?
Non-differentiable (loss) functions can be labelled according to the stardard definitions of differentiation: that the function has a derivative at all points in its domain. For example, the ReLU loss function is technically non-differentiable, because its gradient is not defined at zero (or wherever the two lines meet, if you're using a variant of the standard ReLU).

Non-decomposable functions must be looked at slightly differently. A loss function that is not decomposable is usually one that is composed of several statistics across the training metrics. Take the F1 score, for example:

$$
F1 = 2 \cdot \frac{precision \cdot recall}{precision + recall}
$$

Using this as a loss function means you would have to expand the terms for precision and recall in terms of your predictions over a batch, then work out the gradients of each function, finally combining them. It can be done (but it gets complicated), but I would imagine there are trade-offs when optimising at the level of such a metric, which really summarises your model's performance as an average over samples. Using a traditional loss function focusses on improving the model at the more granular sample level. This means the gradients are concentrated at the purest level and I would imagine better optimisation is possible. It could be that optimising at the more abstract level of the F1 score leads to less overfitting or even better generalisation. This is all just an idea though; I haven't seen any work making such comparisons directly.



Here is a short reddit thread with some interesting points and examples about when you might even consider trying to optimise such a non-decompasable function directly (i.e. using it as a loss function).

Have a look at this paper, which speak about non-decomposable loss functions and offers a way to deal with them. Reading through that and comparing the functions that the authors talk about should help you gain a better understanding of the key differences.