Search papers, labs, and topics across Lattice.
This paper introduces Lambda-randomization, a novel approach to multi-dimensional randomized response that mitigates the curse of dimensionality. It achieves this by parameterizing randomization matrices using a set of per-attribute parameters between 0 and 1, the identity matrix, and the all-ones vector. The method enables efficient computation of unbiased estimates of underlying true distributions in high-dimensional anonymized datasets, while maintaining rigorous privacy guarantees.
Escape the curse of dimensionality in randomized response with Lambda-randomization, a surprisingly simple protocol that slashes computation costs while preserving privacy and accuracy for multi-dimensional data.
Randomized response is a popular local anonymization approach that can deliver anonymized multi-dimensional data sets with rigorous privacy guarantees. At the same time, it can ensure validity for exploratory analysis and machine learning tasks as, under fairly general conditions, unbiased estimates of the underlying true distributions can be retrieved. However, and like for many other anonymization techniques, one of the main pitfalls of this approach is the curse of dimensionality. When coping with data sets with many attributes, one quickly runs into unsustainable computational costs for estimating true distributions, as well as a degradation in their accuracies. Relying on new theoretical insights developed in this paper, we propose an approach to multi-dimensional randomized response that avoids these traditional limitations. From simple yet intuitive parameterizations of the randomization matrices that we introduce, we develop a protocol called Lambda-randomization that entails low computational costs to retrieve estimates of multivariate distributions, and that makes use of solely three simple elements: a set of parameters ranging between 0 and 1 (one per attribute of the data set), the identity matrix, and the all-ones vector. We also present an empirical application to illustrate the proposed protocol.
