Timezone: »

 
Oral
Optimal Algorithms for Mean Estimation under Local Differential Privacy
Hilal Asi · Vitaly Feldman · Kunal Talwar

Thu Jul 21 01:10 PM -- 01:30 PM (PDT) @ Room 318 - 320
in Social Aspects/Optimization »
We study the problem of mean estimation of $\ell_2$-bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achieve the (asymptotic) optimal rates for this problem, the performance of these algorithms in practice can vary significantly due to varying (and often large) hidden constants. In this work, we investigate the question of designing the randomizer with the smallest variance. We show that PrivUnit (Bhowmick et al. 2018) with optimized parameters achieves the optimal variance among a large family of natural randomizers. To prove this result, we establish some properties of local randomizers, and use symmetrization arguments that allow us to write the optimal randomizer as the optimizer of a certain linear program. These structural results, which should extend to other problems, then allow us to show that the optimal randomizer belongs to the PrivUnit family. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees. This allows us to establish several useful properties on the exact constants of the optimal error as well as to numerically estimate these constants.
Keywords: SA: Privacy-preserving Statistics and Machine Learning

Author Information

Hilal Asi (Stanford University)
Vitaly Feldman (Apple)
Kunal Talwar (Apple)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors