# Faster Private Release of Marginals on Small Databases

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2013.

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

- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [Pure Differential Privacy for Functional Summaries with a Laplace-like Process](https://mlsanity.com/paper/2309.00125/) (2023)

## Abstract (arXiv)

We study the problem of answering k-way marginal queries on a database D ∈ (0,1d)n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of the database's records x ∈ 0,1d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses on a dataset, and designing efficient algorithms for privately answering marginal queries has been identified as an important open problem in private data analysis. For any k, we give a differentially private online algorithm that runs in time  minexp(d^1-Omega(1/√k)), exp(d / log.99 d)  per query and answers any (possibly superpolynomially long and adaptively chosen) sequence of k-way marginal queries up to error at most ± .01 on every query, provided n gtrsim d.51 . To the best of our knowledge, this is the first algorithm capable of privately answering marginal queries with a non-trivial worst-case accuracy guarantee on a database of size poly(d, k) in time exp(o(d)). Our algorithms are a variant of the private multiplicative weights algorithm (Hardt and Rothblum, FOCS '10), but using a different low-weight representation of the database. We derive our low-weight representation using approximations to the OR function by low-degree polynomials with coefficients of bounded L1-norm. We also prove a strong limitation on our approach that is of independent approximation-theoretic interest. Specifically, we show that for any k = o(log d), any polynomial with coefficients of L1-norm poly(d) that pointwise approximates the d-variate OR function on all inputs of Hamming weight at most k must have degree d^1-O(1/√k).