We introduce low complexity bounds on mutual information for efficient privacy-preserving feature selection with secure multi-party computation (MPC). Considering a discrete feature with N possible values and a discrete label with M possible values, our approach requires O(N) multiplications as opposed to O(NM) in a direct MPC implementation of mutual information. Our experimental results show that for regression tasks, we achieve a computation speed up of over 1,000× compared to a straightforward MPC implementation of mutual information, while achieving similar accuracy for the downstream machine learning model.
This research is funded by the EU Horizon Europe project HARPOCRATES (Grant ID. 101069535) and H2020 project CONCORDIA (Grant ID. 830927). We thank Tuomas Karhu for preparing the SpO2 data as well as help and advice in the process. We would also like to thank the anonymous reviewers for their comments and suggested improvements.