2023/10/10 by Narayanan, Shyam · 1 citation
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2310.06289
We provide optimal lower bounds for two well-known parameter estimation (also known as statistical estimation) tasks in high dimensions with approximate differential privacy. First, we prove that for any α≤ O(1), estimating the covariance of a Gaussian up to spectral error α requires Ω(\fracd3/2αε + (d)/(α2)) samples, which is tight up to logarithmic factors. This result improves over previous work which established this for α≤ O((1)/(√(d))), and is also simpler than previous work. Next, we prove that estimating the mean of a heavy-tailed distribution with bounded kth moments requires Ω(\fracdαk/(k-1) ε + (d)/(α2)) samples. Previous work for this problem was only able to establish this lower bound against pure differential privacy, or in the special case of k = 2. Our techniques follow the method of fingerprinting and are generally quite simple. Our lower bound for heavy-tailed estimation is based on a black-box reduction from privately estimating identity-covariance Gaussians. Our lower bound for covariance estimation utilizes a Bayesian approach to show that, under an Inverse Wishart prior distribution for the covariance matrix, no private estimator can be accurate even in expectation, without sufficiently many samples.