# Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations

arXiv: https://arxiv.org/abs/1308.1385 · HTML: https://mlsanity.com/paper/1308.1385/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2013.

## Built on by (most cited first, 17 of 17)

- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [Generating Private Synthetic Data with Genetic Algorithms](https://mlsanity.com/paper/2306.03257/) (2023)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Differentially Private Covariance Revisited](https://mlsanity.com/paper/2205.14324/) (2022)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [Statistical Theory of Differentially Private Marginal-based Data Synthesis Algorithms](https://mlsanity.com/paper/2301.08844/) (2023)
- [Relaxed Marginal Consistency for Differentially Private Query Answering](https://mlsanity.com/paper/2109.06153/) (2021)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation](https://mlsanity.com/paper/2301.13850/) (2023)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Private Evolution Converges](https://mlsanity.com/paper/2506.08312/) (2025)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [On Purely Private Covariance Estimation](https://mlsanity.com/paper/2510.26717/) (2025)
- [PRIMO: Private Regression in Multiple Outcomes](https://mlsanity.com/paper/2303.04195/) (2023)
- [Geometry-Adaptive Mechanisms for Private Synthetic Data](https://mlsanity.com/paper/2609.33363/) (2026)

## Abstract (arXiv)

Consider a database of n people, each represented by a bit-string of length d corresponding to the setting of d binary attributes. A k-way marginal query is specified by a subset S of k attributes, and a |S|-dimensional binary vector β specifying their values. The result for this query is a count of the number of people in the database whose attribute vector restricted to S agrees with β. Privately releasing approximate answers to a set of k-way marginal queries is one of the most important and well-motivated problems in differential privacy. Information theoretically, the error complexity of marginal queries is well-understood: the per-query additive error is known to be at least Omega(min√n,d^frack2) and at most tildeO(min√n d1/4,d^frack2). However, no polynomial time algorithm with error complexity as low as the information theoretic upper bound is known for small n. In this work we present a polynomial time algorithm that, for any distribution on marginal queries, achieves average error at most tildeO(√n d^fraclceil k/2 rceil4). This error bound is as good as the best known information theoretic upper bounds for k=2. This bound is an improvement over previous work on efficiently releasing marginals when k is small and when error o(n) is desirable. Using private boosting we are also able to give nearly matching worst-case error bounds. Our algorithms are based on the geometric techniques of Nikolov, Talwar, and Zhang. The main new ingredients are convex relaxations and careful use of the Frank-Wolfe algorithm for constrained convex minimization. To design our relaxations, we rely on the Grothendieck inequality from functional analysis.