New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
28. listopadu 2022
Řečníci
Gautam Kamath
Řečník · 1 sledující
Argyris Mouzakis
Řečník · 0 sledujících
Vikrant Singhal
Řečník · 0 sledujících
O prezentaci
We prove new lower bounds for statistical estimation tasks under the constraint of (ε,δ)-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 Ω(d^2) samples, and in spectral norm requires Ω(d^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 Ω(d/(α^2 ε)) lower bound for estimating the mean of a distribution with bounded covariance to α-error in ℓ_2-distance. Prior known lower bounds for all these problems were either polynomially weaker or held under the stricter condition of (ε,0)-differential privacy.We prove new lower bounds for statistical estimation tasks under the constraint of (ε,δ)-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 Ω(d^2) samples, and in spectral norm requires Ω(d^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 fingerprint…
Organizátor
NeurIPS 2022
Účet · 962 sledujících
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího