# The Power of Factorization Mechanisms in Local and Central Differential Privacy

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2019.

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

- [Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods](https://mlsanity.com/paper/2106.07153/) (2021)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [A Central Limit Theorem for Differentially Private Query Answering](https://mlsanity.com/paper/2103.08721/) (2021)
- [Instance-Optimal Differentially Private Estimation](https://mlsanity.com/paper/2210.15819/) (2022)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation](https://mlsanity.com/paper/2301.13850/) (2023)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting](https://mlsanity.com/paper/2509.14334/) (2025)
- [Private Synthetic Data with Hierarchical Structure](https://mlsanity.com/paper/2206.05942/) (2022)
- [Answering Private Linear Queries Adaptively using the Common Mechanism](https://mlsanity.com/paper/2212.00135/) (2022)
- [ResidualPlanner+: a scalable matrix mechanism for marginals and beyond](https://mlsanity.com/paper/2305.08175/) (2023)
- [Private Continual Counting of Unbounded Streams](https://mlsanity.com/paper/2506.15018/) (2025)
- [Denoising the US Census: Succinct Block Hierarchical Regression](https://mlsanity.com/paper/2603.10099/) (2026)
- [Accurate and Scalable Matrix Mechanisms via Divide and Conquer](https://mlsanity.com/paper/2604.00868/) (2026)
- [Learning versus Refutation in Noninteractive Local Differential Privacy](https://mlsanity.com/paper/2210.15439/) (2022)
- [PRIMO: Private Regression in Multiple Outcomes](https://mlsanity.com/paper/2303.04195/) (2023)
- [Online Distribution Learning with Local Private Constraints](https://mlsanity.com/paper/2402.00315/) (2024)
- [Differentially Private Range Queries with Correlated Input Perturbation](https://mlsanity.com/paper/2402.07066/) (2024)
- [Differentially Private Online Federated Learning with Correlated Noise](https://mlsanity.com/paper/2403.16542/) (2024)
- [Optimality of Matrix Mechanism on ℓpp-metric](https://mlsanity.com/paper/2406.02140/) (2024)
- [Prediction with Expert Advice under Local Differential Privacy](https://mlsanity.com/paper/2512.06971/) (2025)
- [Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy](https://mlsanity.com/paper/2601.22320/) (2026)
- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)

## Abstract (arXiv)

We give new characterizations of the sample complexity of answering linear queries (statistical queries) in the local and central models of differential privacy: *In the non-interactive local model, we give the first approximate characterization of the sample complexity. Informally our bounds are tight to within polylogarithmic factors in the number of queries and desired accuracy. Our characterization extends to agnostic learning in the local model. *In the central model, we give a characterization of the sample complexity in the high-accuracy regime that is analogous to that of Nikolov, Talwar, and Zhang (STOC 2013), but is both quantitatively tighter and has a dramatically simpler proof. Our lower bounds apply equally to the empirical and population estimation problems. In both cases, our characterizations show that a particular factorization mechanism is approximately optimal, and the optimal sample complexity is bounded from above and below by well studied factorization norms of a matrix associated with the queries.