2
$\begingroup$

The following talk:

explains federated learning by averaging several node-specific models together. It provides a high-level example with neural networks. Using NN, it seems straightforward that any weight/bias in the averaged model will simply take the average of the values of the individual node models.

For XGBoost (or more generally for trees), how would such an "averaging" work? Would that even be possible? Would that take the form of a "random forest" of XGBoost models?

$\endgroup$
1
  • $\begingroup$ +1, this is a big and fun conversation. In short, yes, it is possible but requires some algorithmic gymnastics (hashing, encryption, etc.) on the background. I tried to give a bird's eye view in my post below. Let me know if you want some clarifications, I kept it a bit dense due to length considerations. $\endgroup$
    – usεr11852
    Oct 30, 2022 at 22:32

1 Answer 1

1
$\begingroup$

Preamble: Federated Learning (FL) is a decentralised machine learning paradigm. One of its core difference to standard "distributed learning" approach is that the training/testing data are held locally on edge devices and there is no raw data exchange, additionally, computations are primarily done on the edge rather than on some big remote server. A core distinction when working with a FL system is if we refer at horizontally or vertically partitioned system; horizontally the data are partitioned based on instances/subjects/etc. while vertically the data are partitioned against features/regressors. Do note that while we avoid the use of a big remote server for computations, FL systems require some orchestration and there is usually an "orchestrator" system too; Kairouz et al. (2021) "Advances and Open Problems in Federated Learning" is an exceptional reference on the matter if you haven't seen it yet.

FL and GBMs: There has been work to create Federated Learning variant of Gradient Boosting Machines (GBMs). The implementation are very much dependant if we expect horizontal or vertical data distribution. A "basic" horizontal implementation is in "Practical Federated Gradient Boosting Decision Trees" by Li et al. (2019) and a "basic" vertical implementation is "SecureBoost: A Lossless Federated Learning Framework" by Cheng et al. (2019). In the case of horizontal implementation we use what the authors describe as "Weighted Gradient Boosting" where based on Local-Sensitive Hashing (LSH) similarity we are able reweight our gradients from a subsample to approximate approximate the gradients from the whole sample. As such we never exchange "item"-specific information an the orchestrator only sees basic similarities. On the side of a vertical implementation now: in each iteration, the orchestrator system receives the encrypted gradient statistics based on the optimal splits suggested by (disjoint set of) features held in he edge devices. The orchestrator then estimates the best split based on all the gradients available using a homomorphic cryptosystem that does not allow it to deduce individual values. (Such cryptosystems are homomorphically additive; in the Cheng paper they use the Paillier cryptosystem but other additive systems should be fine too, in short in an additively homomorphic cryptosystem: $\text{Enc(5)} + \text{Enc(9)} = \text{Enc(14)}$ so we can "add" the cyphertexts (of the gradients) without having to know any of the plaintext values.)

In conclusion, yes it is possible to train GBMs using FL framework. Both the horizontal and the vertical approached described above, allow us to leverage all our data without directly sharing information about the data's values outside the node where they already reside. Somewhat, oversimplifying things, all the FL-GBM implementations try to share gradient information without revealing how the gradient has calculated because if the raw gradients were sent, they would betray their private data. In many implementations, the use of cryptosystems is a core design aspect but other ways to satisfy privacy guarantees are also gaining ground (usually related to differential privacy). Please note that FL is an extremely active research area and new implementations come out almost monthly. For example, newer systems aim to natively accommodate horizontal and vertical learning under the same paradigm (e.g. see "FederBoost: Private Federated Learning for GBDT" by Tian et al. (2022)) and reduce the need of expensive cryptographic operations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.