2013/08/06 by Cynthia Dwork, Dwork, Cynthia, Aleksandar Nikolov +3 · 2 citations
Computer Science · Medicine · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Pharmacological Effects and Toxicity Studies #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1308.1385
openalex publication_date 2013/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a database of n people, each represented by a bit-string of length\nd corresponding to the setting of d binary attributes. A k-way marginal\nquery is specified by a subset S of k attributes, and a |S|-dimensional\nbinary vector \β specifying their values. The result for this query is a\ncount of the number of people in the database whose attribute vector restricted\nto S agrees with \β.\n Privately releasing approximate answers to a set of k-way marginal queries\nis one of the most important and well-motivated problems in differential\nprivacy. Information theoretically, the error complexity of marginal queries is\nwell-understood: the per-query additive error is known to be at least\n\Ω(\min \√(n),d\(k)/(2) ) and at most\n\O(\min \√(n) d1/4,d\(k)/(2) ). However, no polynomial\ntime algorithm with error complexity as low as the information theoretic upper\nbound is known for small n. In this work we present a polynomial time\nalgorithm that, for any distribution on marginal queries, achieves average\nerror at most \O(\√(n) d\( lceil k/2 rceil)/(4)). This error\nbound is as good as the best known information theoretic upper bounds for\nk=2. This bound is an improvement over previous work on efficiently releasing\nmarginals when k is small and when error o(n) is desirable. Using private\nboosting we are also able to give nearly matching worst-case error bounds.\n Our algorithms are based on the geometric techniques of Nikolov, Talwar, and\nZhang. The main new ingredients are convex relaxations and careful use of the\nFrank-Wolfe algorithm for constrained convex minimization. To design our\nrelaxations, we rely on the Grothendieck inequality from functional analysis.\n