Discrete Distribution Estimation under Local Privacy
It addresses privacy risks in data collection for service providers by enabling distribution learning without raw data, though it appears incremental as it builds on existing mechanisms like RAPPOR.
The paper tackles discrete distribution estimation under local privacy, presenting new mechanisms like hashed K-ary Randomized Response that empirically match or exceed existing methods in utility across all privacy levels, with theoretical results showing order-optimality for KRR and RAPPOR in different privacy regimes.
The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed K-ary Randomized Response (KRR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at different privacy regimes.