On the Use of Iterative Feedback in Private Frequency Estimation

This thesis evaluates iterative feedback as a mechanism to optimize privatization algorithms, specifically the family of Local Differential Privacy (LDP) algorithms. The main contribution is the Iterative LDP Algorithm which uses iterative feedback to outperform generic LDP mechanisms in certain scenarios, including those with low response rates (number of samples). This addresses a major pain point of LDP mechanisms currently, as they are prone to significant losses in utility in those scenarios. Conversely, it is less effective than existing methods as the number of responses tends to infinity. This work contains extensive comparison of the Iterative LDP Algorithm to several existing LDP mechanisms and baselines for frequency estimation. Experiments show gains in estimation performance in high privacy regimes over synthetic and real data. These experiments help discern scenarios where the Iterative LDP Algorithm actually learns from regularization induced performance gains. Learning and substantial performance gains were observed when samples are generated from the power law family of distributions (distributions that look linear on logarithmically scaled axes). Several epidemiological, social network, and other important internet based counting phenomena are known to follow such distributions[25][5]. The Iterative LDP Algorithm outperforms existing variable privacy LDP mechanisms in the aforementioned regimes. Thus, iterative feedback is a viable enhancement for existing LDP mechanisms.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Richardson, Yaateh

Advisor dc:contributor.advisor

• Raskar, Ramesh

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/138984

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/138984