Timezone: »

 
Exact Optimality in Communication-Privacy-Utility Tradeoffs
Berivan Isik · Wei-Ning Chen · Ayfer Ozgur · Tsachy Weissman · Albert No

@
in Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities »
Event URL: https://openreview.net/forum?id=TF2sP6bTUI »
We study the mean estimation problem under communication and local differential privacy constraints. While previous work has proposed order-optimal algorithms for the same problem (i.e., asymptotically optimal as we spend more bits), exact optimality (in the non-asymptotic setting) still has not been achieved. We take a step towards characterizing the exact-optimal approach in the presence of shared randomness and identify several necessary conditions for exact optimality. We prove that one of the necessary conditions is to utilize a rotationally symmetric shared random codebook. Based on this, we propose a randomization mechanism where the codebook is a randomly rotated simplex -- satisfying the necessary properties of the exact-optimal codebook. The proposed mechanism is based on a $k$-closest encoding which we prove to be exact-optimal for the randomly rotated simplex codebook.

Author Information

Berivan Isik (Stanford University)
Wei-Ning Chen (Stanford University)
Wei-Ning Chen

Wei-Ning Chen is currently a Ph.D. student at Stanford EE under the support of Stanford Graduate Fellowship (SGF). His research interests broadly lie in information-theoretic and algorithmic aspects of data science. He adopt tools mainly from information theory, theoretical machine learning, and statistical inference, with a current focus on distributed inference, federated learning and differential privacy.

Ayfer Ozgur (Stanford University)
Tsachy Weissman (Stanford University)
Albert No (Hongik University)

More from the Same Authors