BMI: Bounded Mutual Information for Efficient Privacy-Preserving Feature Selection

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 \(\times \) compared to a straightforward MPC implementation of mutual information, while achieving similar accuracy for the downstream machine learning model.