Constant Matters: Fine-grained Error Bound on Differentially Private Continual Observation
Jul 24, 2023
Speakers
Hendrik Fichtenberger
Speaker · 0 followers
Monika Henzinger
Speaker · 0 followers
Jalaj Upadhyay
Speaker · 0 followers
About
We study fine-grained error bounds for differentially private algorithms for counting under continual observation. Our main insight is that the matrix mechanism when using lower-triangular matrices can be used in the continual observation model. More specifically, we give an explicit factorization for the counting matrix M_𝖼𝗈𝗎𝗇𝗍 and upper bound the error explicitly. We also give a fine-grained analysis, specifying the exact constant in the upper bound. Our analysis is based on upper and lower bounds of the completely bounded norm (cb-norm) of M_𝖼𝗈𝗎𝗇𝗍. Along the way, we improve the best-known bound of 28 years by Mathias (SIAM Journal on Matrix Analysis and Applications, 1993) on the cb-norm of M_𝖼𝗈𝗎𝗇𝗍 for a large range of the dimension of M_𝖼𝗈𝗎𝗇𝗍. Furthermore, we are the first to give concrete error bounds for various problems under continual observation such as binary counting, maintaining a histogram, releasing an approximately cut-preserving synthetic graph, many graph-based statistics, and substring and episode counting. Finally, we note that our result can be used to get a fine-grained error bound for non-interactive local learning and the first lower bounds on the additive error for (ϵ,δ)-differentially-private counting under continual observation. Subsequent to this work, Henzinger et al. (SODA, 2023) showed that our factorization also achieves fine-grained mean-squared error.We study fine-grained error bounds for differentially private algorithms for counting under continual observation. Our main insight is that the matrix mechanism when using lower-triangular matrices can be used in the continual observation model. More specifically, we give an explicit factorization for the counting matrix M_𝖼𝗈𝗎𝗇𝗍 and upper bound the error explicitly. We also give a fine-grained analysis, specifying the exact constant in the upper bound. Our analysis is based on upper and low…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Training Normalizing Flows from Dependent Data
Watch later
Expected Gradients of Maxout Networks and Consequences to Parameter Initialization
Watch later
Hanna Tseran, …
Indigenous Design Methods influence on Human-Computer Interaction and AI Design
Watch later
