Welcome to the resource topic for 2022/225
Title:
Constant matters: Fine-grained Complexity of Differentially Private Continual Observation Using Completely Bounded Norms
Authors: Monika Henzinger, Jalaj Upadhyay
Abstract:We study fine-grained error bounds for differentially private algorithms for averaging and counting in the continual observation model. For this, we use the completely bounded spectral norm (cb norm) from operator algebra. For a matrix W, its cb norm is defined as [ |{W}|{\mathsf{cb}} = \max{Q} \left{ \frac{|{Q \bullet W}|}{|{Q}|} \right}, ] where Q \bullet W denotes the Schur product and \|{\cdot}\| denotes the spectral norm. We bound the cb norm of two fundamental matrices studied in differential privacy under the continual observation model: the counting matrix M_{\mathsf{counting}} and the averaging matrix M_{\mathsf{average}}. For M_{\mathsf{counting}}, we give lower and upper bound whose additive gap is 1 + \frac{1}{\pi}. Our factorization also has two desirable properties sufficient for streaming setting: the factorization contains of lower-triangular matrices and the number of distinct entries in the factorization is exactly T. This allows us to compute the factorization on the fly while requiring the curator to store a T-dimensional vector. For M_{\mathsf{average}}, we show an additive gap between the lower and upper bound of \approx 0.64.
ePrint: https://eprint.iacr.org/2022/225
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .