# PhD Seminar • Algorithms and Complexity • New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma

Monday, October 3, 2022 — 3:00 PM to 4:00 PM EDT

## Please note: This PhD seminar will take place online and in DC 2310.

Argyris Mouzakis, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Gautam Kamath

We prove new lower bounds for statistical estimation tasks under the constraint of $(\varepsilon, \delta)$-differential privacy. First, we provide tight lower bounds for private covariance estimation of Gaussian distributions. We show that estimating the covariance matrix in Frobenius norm requires $\Omega(d^2)$ samples, and in spectral norm requires $\Omega(d^{\frac{3}{2}})$ samples, both matching upper bounds up to logarithmic factors. We prove these bounds via our main technical contribution, a broad generalization of the fingerprinting method to exponential families.

Additionally, using the private Assouad method of Acharya, Sun, and Zhang, we show a tight $\Omega(\frac{d}{\alpha^2 \varepsilon})$ lower bound for estimating the mean of a distribution with bounded covariance to $\alpha$-error in $\ell_2$-distance. Prior known lower bounds for all these problems were either polynomially weaker or held under the stricter condition of $(\varepsilon,0)$-differential privacy.

Based on joint work with Gautam Kamath and Vikrant Singhal. To appear in NeurIPS 2022.

To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/98315420695.

Location
DC - William G. Davis Computer Research Centre
Online PhD seminar | DC 2310
200 University Avenue West

Waterloo, ON N2L 3G1
Event tags

### February 2023

S M T W T F S
29
30
31
2
4
5
8
10
11
12
18
19
20
21
22
24
25
26
27
28
1
2
3
4
1. 2023 (39)
1. March (2)
2. February (15)
3. January (22)
2. 2022 (245)
1. December (20)
2. November (28)
3. October (15)
4. September (12)
5. August (29)
6. July (23)
7. June (17)
8. May (20)
9. April (24)
10. March (22)
11. February (16)
12. January (19)
3. 2021 (210)
4. 2020 (217)
5. 2019 (255)
6. 2018 (217)
7. 2017 (36)
8. 2016 (21)
9. 2015 (36)
10. 2014 (33)
11. 2013 (23)
12. 2012 (4)
13. 2011 (1)
14. 2010 (1)
15. 2009 (1)
16. 2008 (1)