HDMM: Automatic optimization for accurately answering sets of high-dimensional queries under differential privacy

Summary:

‍Organizations that collect highly personal, individual-level data, like statistical agencies and medical institutions, rely on differential privacy algorithms for safe, reliable summaries. Many applications require generating private answers to large collections of statistical queries. In this case, much better accuracy is possible through sophisticated analysis of the query set of interest. Our new method, HDMM, automates and optimizes this process, offering state-of-the-art accuracy and dramatically better scalability than existing techniques.

HDMM is one of the techniques we delivered to the U.S. Census Bureau for use in the 2020 census. It is a scalable successor to the Matrix Mechanism, an algorithm co-invented by Tumult Labs co-founders Michael Hay and Gerome Miklau, and who received the ACM PODS Test-of-Time award in 2020. Both methods are cornerstones of the differential privacy literature.